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