Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include "sal/config.h"
21 :
22 : #include "boost/static_assert.hpp"
23 :
24 : #include "storcach.hxx"
25 :
26 : #include "sal/types.h"
27 : #include "sal/macros.h"
28 : #include "rtl/alloc.h"
29 : #include "osl/diagnose.h"
30 :
31 : #include "store/types.h"
32 : #include "object.hxx"
33 : #include "storbase.hxx"
34 :
35 : #include <stddef.h>
36 :
37 : using namespace store;
38 :
39 : /*========================================================================
40 : *
41 : * PageCache (non-virtual interface) implementation.
42 : *
43 : *======================================================================*/
44 :
45 851012 : storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset)
46 : {
47 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
48 851012 : if (nOffset == STORE_PAGE_NULL)
49 0 : return store_E_CantSeek;
50 :
51 851012 : return lookupPageAt_Impl (rxPage, nOffset);
52 : }
53 :
54 121724 : storeError PageCache::insertPageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
55 : {
56 : // [SECURITY:ValInput]
57 121724 : PageData const * pagedata = rxPage.get();
58 : OSL_PRECOND(!(pagedata == 0), "store::PageCache::insertPageAt(): invalid Page");
59 121724 : if (pagedata == 0)
60 0 : return store_E_InvalidParameter;
61 :
62 121724 : sal_uInt32 const offset = pagedata->location();
63 : OSL_PRECOND(!(nOffset != offset), "store::PageCache::insertPageAt(): inconsistent Offset");
64 121724 : if (nOffset != offset)
65 0 : return store_E_InvalidParameter;
66 :
67 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::insertPageAt(): invalid Offset");
68 121724 : if (nOffset == STORE_PAGE_NULL)
69 0 : return store_E_CantSeek;
70 :
71 121724 : return insertPageAt_Impl (rxPage, nOffset);
72 : }
73 :
74 246696 : storeError PageCache::updatePageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
75 : {
76 : // [SECURITY:ValInput]
77 246696 : PageData const * pagedata = rxPage.get();
78 : OSL_PRECOND(!(pagedata == 0), "store::PageCache::updatePageAt(): invalid Page");
79 246696 : if (pagedata == 0)
80 0 : return store_E_InvalidParameter;
81 :
82 246696 : sal_uInt32 const offset = pagedata->location();
83 : OSL_PRECOND(!(nOffset != offset), "store::PageCache::updatePageAt(): inconsistent Offset");
84 246696 : if (nOffset != offset)
85 0 : return store_E_InvalidParameter;
86 :
87 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::updatePageAt(): invalid Offset");
88 246696 : if (nOffset == STORE_PAGE_NULL)
89 0 : return store_E_CantSeek;
90 :
91 246696 : return updatePageAt_Impl (rxPage, nOffset);
92 : }
93 :
94 10 : storeError PageCache::removePageAt (sal_uInt32 nOffset)
95 : {
96 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset");
97 10 : if (nOffset == STORE_PAGE_NULL)
98 0 : return store_E_CantSeek;
99 :
100 10 : return removePageAt_Impl (nOffset);
101 : }
102 :
103 : /*========================================================================
104 : *
105 : * Entry.
106 : *
107 : *======================================================================*/
108 : namespace
109 : {
110 :
111 : struct Entry
112 : {
113 : /** Representation.
114 : */
115 : PageHolder m_xPage;
116 : sal_uInt32 m_nOffset;
117 : Entry * m_pNext;
118 :
119 : /** Allocation.
120 : */
121 215201 : static void * operator new (size_t, void * p) { return p; }
122 0 : static void operator delete (void *, void *) {}
123 :
124 : /** Construction.
125 : */
126 215201 : explicit Entry (PageHolder const & rxPage = PageHolder(), sal_uInt32 nOffset = STORE_PAGE_NULL)
127 215201 : : m_xPage(rxPage), m_nOffset(nOffset), m_pNext(0)
128 215201 : {}
129 :
130 : /** Destruction.
131 : */
132 215201 : ~Entry() {}
133 : };
134 :
135 : } // namespace
136 :
137 : /*========================================================================
138 : *
139 : * EntryCache interface.
140 : *
141 : *======================================================================*/
142 : namespace
143 : {
144 :
145 : class EntryCache
146 : {
147 : rtl_cache_type * m_entry_cache;
148 :
149 : public:
150 : static EntryCache & get();
151 :
152 : Entry * create (PageHolder const & rxPage, sal_uInt32 nOffset);
153 :
154 : void destroy (Entry * entry);
155 :
156 : protected:
157 : EntryCache();
158 : ~EntryCache();
159 : };
160 :
161 : } // namespace
162 :
163 : /*========================================================================
164 : *
165 : * EntryCache implementation.
166 : *
167 : *======================================================================*/
168 :
169 430402 : EntryCache & EntryCache::get()
170 : {
171 430402 : static EntryCache g_entry_cache;
172 430402 : return g_entry_cache;
173 : }
174 :
175 300 : EntryCache::EntryCache()
176 : {
177 : m_entry_cache = rtl_cache_create (
178 : "store_cache_entry_cache",
179 : sizeof(Entry),
180 : 0, // objalign
181 : 0, // constructor
182 : 0, // destructor
183 : 0, // reclaim
184 : 0, // userarg
185 : 0, // default source
186 : 0 // flags
187 300 : );
188 300 : }
189 :
190 300 : EntryCache::~EntryCache()
191 : {
192 300 : rtl_cache_destroy (m_entry_cache), m_entry_cache = 0;
193 300 : }
194 :
195 215201 : Entry * EntryCache::create (PageHolder const & rxPage, sal_uInt32 nOffset)
196 : {
197 215201 : void * pAddr = rtl_cache_alloc (m_entry_cache);
198 215201 : if (pAddr != 0)
199 : {
200 : // construct.
201 215201 : return new(pAddr) Entry (rxPage, nOffset);
202 : }
203 0 : return 0;
204 : }
205 :
206 215201 : void EntryCache::destroy (Entry * entry)
207 : {
208 215201 : if (entry != 0)
209 : {
210 : // destruct.
211 215201 : entry->~Entry();
212 :
213 : // return to cache.
214 215201 : rtl_cache_free (m_entry_cache, entry);
215 : }
216 215201 : }
217 :
218 : /*========================================================================
219 : *
220 : * highbit():= log2() + 1 (complexity O(1))
221 : *
222 : *======================================================================*/
223 21570 : static int highbit(sal_Size n)
224 : {
225 21570 : int k = 1;
226 :
227 21570 : if (n == 0)
228 0 : return (0);
229 : #if SAL_TYPES_SIZEOFLONG == 8
230 : if (n & 0xffffffff00000000ul)
231 : k |= 32, n >>= 32;
232 : #endif
233 21570 : if (n & 0xffff0000)
234 0 : k |= 16, n >>= 16;
235 21570 : if (n & 0xff00)
236 10779 : k |= 8, n >>= 8;
237 21570 : if (n & 0xf0)
238 10795 : k |= 4, n >>= 4;
239 21570 : if (n & 0x0c)
240 44 : k |= 2, n >>= 2;
241 21570 : if (n & 0x02)
242 21526 : k++;
243 :
244 21570 : return (k);
245 : }
246 :
247 : /*========================================================================
248 : *
249 : * PageCache_Impl implementation.
250 : *
251 : *======================================================================*/
252 : namespace store
253 : {
254 :
255 : class PageCache_Impl :
256 : public store::OStoreObject,
257 : public store::PageCache
258 : {
259 : /** Representation.
260 : */
261 : static size_t const theTableSize = 32;
262 : BOOST_STATIC_ASSERT(STORE_IMPL_ISP2(theTableSize));
263 :
264 : Entry ** m_hash_table;
265 : Entry * m_hash_table_0[theTableSize];
266 : size_t m_hash_size;
267 : size_t m_hash_shift;
268 : size_t const m_page_shift;
269 :
270 : size_t m_hash_entries; // total number of entries in table.
271 : size_t m_nHit;
272 : size_t m_nMissed;
273 :
274 1418840 : inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m)
275 : {
276 1418840 : return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m));
277 : }
278 1418840 : inline int hash_index_Impl (sal_uInt32 nOffset)
279 : {
280 1418840 : return hash_Impl(nOffset, m_hash_shift, m_page_shift, m_hash_size - 1);
281 : }
282 :
283 : Entry * lookup_Impl (Entry * entry, sal_uInt32 nOffset);
284 : void rescale_Impl (sal_Size new_size);
285 :
286 : /** PageCache Implementation.
287 : */
288 : virtual storeError lookupPageAt_Impl (
289 : PageHolder & rxPage,
290 : sal_uInt32 nOffset);
291 :
292 : virtual storeError insertPageAt_Impl (
293 : PageHolder const & rxPage,
294 : sal_uInt32 nOffset);
295 :
296 : virtual storeError updatePageAt_Impl (
297 : PageHolder const & rxPage,
298 : sal_uInt32 nOffset);
299 :
300 : virtual storeError removePageAt_Impl (
301 : sal_uInt32 nOffset);
302 :
303 : /** Not implemented.
304 : */
305 : PageCache_Impl (PageCache_Impl const &);
306 : PageCache_Impl & operator= (PageCache_Impl const &);
307 :
308 : public:
309 : /** Construction.
310 : */
311 : explicit PageCache_Impl (sal_uInt16 nPageSize);
312 :
313 : /** Delegate multiple inherited IReference.
314 : */
315 : virtual oslInterlockedCount SAL_CALL acquire();
316 : virtual oslInterlockedCount SAL_CALL release();
317 :
318 : protected:
319 : /** Destruction.
320 : */
321 : virtual ~PageCache_Impl (void);
322 : };
323 :
324 : } // namespace store
325 :
326 10741 : PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize)
327 : : m_hash_table (m_hash_table_0),
328 : m_hash_size (theTableSize),
329 10741 : m_hash_shift (highbit(m_hash_size) - 1),
330 10741 : m_page_shift (highbit(nPageSize) - 1),
331 : m_hash_entries (0),
332 : m_nHit (0),
333 32223 : m_nMissed (0)
334 : {
335 : static size_t const theSize = SAL_N_ELEMENTS(m_hash_table_0);
336 : BOOST_STATIC_ASSERT(theSize == theTableSize);
337 10741 : memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
338 10741 : }
339 :
340 32223 : PageCache_Impl::~PageCache_Impl()
341 : {
342 10741 : double s_x = 0.0;
343 10741 : sal_Size i, n = m_hash_size;
344 375637 : for (i = 0; i < n; i++)
345 : {
346 364896 : int x = 0;
347 364896 : Entry * entry = m_hash_table[i];
348 944983 : while (entry != 0)
349 : {
350 215191 : m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0;
351 215191 : EntryCache::get().destroy (entry);
352 215191 : entry = m_hash_table[i];
353 215191 : x += 1;
354 : }
355 364896 : s_x += double(x);
356 : }
357 10741 : double ave = s_x / double(n);
358 : OSL_TRACE("ave hash chain length: %g", ave);
359 : (void) ave;
360 :
361 10741 : if (m_hash_table != m_hash_table_0)
362 : {
363 18 : rtl_freeMemory (m_hash_table);
364 18 : m_hash_table = m_hash_table_0;
365 18 : m_hash_size = theTableSize;
366 18 : m_hash_shift = highbit(m_hash_size) - 1;
367 : }
368 : OSL_TRACE("Hits: %u, Misses: %u", m_nHit, m_nMissed);
369 21482 : }
370 :
371 10741 : oslInterlockedCount PageCache_Impl::acquire()
372 : {
373 10741 : return OStoreObject::acquire();
374 : }
375 :
376 10741 : oslInterlockedCount PageCache_Impl::release()
377 : {
378 10741 : return OStoreObject::release();
379 : }
380 :
381 70 : void PageCache_Impl::rescale_Impl (sal_Size new_size)
382 : {
383 70 : sal_Size new_bytes = new_size * sizeof(Entry*);
384 70 : Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes));
385 :
386 70 : if (new_table != 0)
387 : {
388 70 : Entry ** old_table = m_hash_table;
389 70 : sal_Size old_size = m_hash_size;
390 :
391 : OSL_TRACE("ave chain length: %u, total entries: %u [old_size: %u, new_size: %u]",
392 : m_hash_entries >> m_hash_shift, m_hash_entries, old_size, new_size);
393 :
394 70 : memset (new_table, 0, new_bytes);
395 :
396 70 : m_hash_table = new_table;
397 70 : m_hash_size = new_size;
398 70 : m_hash_shift = highbit(m_hash_size) - 1;
399 :
400 : sal_Size i;
401 21254 : for (i = 0; i < old_size; i++)
402 : {
403 21184 : Entry * curr = old_table[i];
404 148289 : while (curr != 0)
405 : {
406 105921 : Entry * next = curr->m_pNext;
407 105921 : int index = hash_index_Impl(curr->m_nOffset);
408 105921 : curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr;
409 105921 : curr = next;
410 : }
411 21184 : old_table[i] = 0;
412 : }
413 70 : if (old_table != m_hash_table_0)
414 : {
415 : //
416 52 : rtl_freeMemory (old_table);
417 : }
418 : }
419 70 : }
420 :
421 1097708 : Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
422 : {
423 1097708 : int lookups = 0;
424 3389307 : while (entry != 0)
425 : {
426 2070958 : if (entry->m_nOffset == nOffset)
427 877067 : break;
428 :
429 1193891 : lookups += 1;
430 1193891 : entry = entry->m_pNext;
431 : }
432 1097708 : if (lookups > 2)
433 : {
434 209553 : sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
435 209623 : for (; ave > 4; new_size *= 2, ave /= 2)
436 70 : continue;
437 209553 : if (new_size != m_hash_size)
438 70 : rescale_Impl (new_size);
439 : }
440 1097708 : return entry;
441 : }
442 :
443 851012 : storeError PageCache_Impl::lookupPageAt_Impl (
444 : PageHolder & rxPage,
445 : sal_uInt32 nOffset)
446 : {
447 851012 : int index = hash_index_Impl(nOffset);
448 851012 : Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
449 851012 : if (entry != 0)
450 : {
451 : // Existing entry.
452 723848 : rxPage = entry->m_xPage;
453 :
454 : // Update stats and leave.
455 723848 : m_nHit += 1;
456 723848 : return store_E_None;
457 : }
458 :
459 : // Cache miss. Update stats and leave.
460 127164 : m_nMissed += 1;
461 127164 : return store_E_NotExists;
462 : }
463 :
464 215201 : storeError PageCache_Impl::insertPageAt_Impl (
465 : PageHolder const & rxPage,
466 : sal_uInt32 nOffset)
467 : {
468 215201 : Entry * entry = EntryCache::get().create (rxPage, nOffset);
469 215201 : if (entry != 0)
470 : {
471 : // Insert new entry.
472 215201 : int index = hash_index_Impl(nOffset);
473 215201 : entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry;
474 :
475 : // Update stats and leave.
476 215201 : m_hash_entries += 1;
477 215201 : return store_E_None;
478 : }
479 0 : return store_E_OutOfMemory;
480 : }
481 :
482 246696 : storeError PageCache_Impl::updatePageAt_Impl (
483 : PageHolder const & rxPage,
484 : sal_uInt32 nOffset)
485 : {
486 246696 : int index = hash_index_Impl(nOffset);
487 246696 : Entry * entry = lookup_Impl (m_hash_table[index], nOffset);
488 246696 : if (entry != 0)
489 : {
490 : // Update existing entry.
491 153219 : entry->m_xPage = rxPage;
492 :
493 : // Update stats and leave. // m_nUpdHit += 1;
494 153219 : return store_E_None;
495 : }
496 93477 : return insertPageAt_Impl (rxPage, nOffset);
497 : }
498 :
499 10 : storeError PageCache_Impl::removePageAt_Impl (
500 : sal_uInt32 nOffset)
501 : {
502 10 : Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
503 20 : while (*ppEntry != 0)
504 : {
505 10 : if ((*ppEntry)->m_nOffset == nOffset)
506 : {
507 : // Existing entry.
508 10 : Entry * entry = (*ppEntry);
509 :
510 : // Dequeue and destroy entry.
511 10 : (*ppEntry) = entry->m_pNext, entry->m_pNext = 0;
512 10 : EntryCache::get().destroy (entry);
513 :
514 : // Update stats and leave.
515 10 : m_hash_entries -= 1;
516 10 : return store_E_None;
517 : }
518 0 : ppEntry = &((*ppEntry)->m_pNext);
519 : }
520 0 : return store_E_NotExists;
521 : }
522 :
523 : /*========================================================================
524 : *
525 : * Old OStorePageCache implementation.
526 : *
527 : * (two-way association (sorted address array, LRU chain)).
528 : * (external OStorePageData representation).
529 : *
530 : *======================================================================*/
531 :
532 : /*========================================================================
533 : *
534 : * PageCache factory implementation.
535 : *
536 : *======================================================================*/
537 : namespace store {
538 :
539 : storeError
540 10741 : PageCache_createInstance (
541 : rtl::Reference< store::PageCache > & rxCache,
542 : sal_uInt16 nPageSize)
543 : {
544 10741 : rxCache = new PageCache_Impl (nPageSize);
545 10741 : if (!rxCache.is())
546 0 : return store_E_OutOfMemory;
547 :
548 10741 : return store_E_None;
549 : }
550 :
551 : } // namespace store
552 :
553 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
