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 336784 : storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset)
43 : {
44 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
45 336784 : if (nOffset == STORE_PAGE_NULL)
46 0 : return store_E_CantSeek;
47 :
48 336784 : return lookupPageAt_Impl (rxPage, nOffset);
49 : }
50 :
51 87083 : storeError PageCache::insertPageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
52 : {
53 : // [SECURITY:ValInput]
54 87083 : PageData const * pagedata = rxPage.get();
55 : OSL_PRECOND(!(pagedata == 0), "store::PageCache::insertPageAt(): invalid Page");
56 87083 : if (pagedata == 0)
57 0 : return store_E_InvalidParameter;
58 :
59 87083 : sal_uInt32 const offset = pagedata->location();
60 : OSL_PRECOND(!(nOffset != offset), "store::PageCache::insertPageAt(): inconsistent Offset");
61 87083 : if (nOffset != offset)
62 0 : return store_E_InvalidParameter;
63 :
64 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::insertPageAt(): invalid Offset");
65 87083 : if (nOffset == STORE_PAGE_NULL)
66 0 : return store_E_CantSeek;
67 :
68 87083 : return insertPageAt_Impl (rxPage, nOffset);
69 : }
70 :
71 0 : storeError PageCache::updatePageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
72 : {
73 : // [SECURITY:ValInput]
74 0 : PageData const * pagedata = rxPage.get();
75 : OSL_PRECOND(!(pagedata == 0), "store::PageCache::updatePageAt(): invalid Page");
76 0 : if (pagedata == 0)
77 0 : return store_E_InvalidParameter;
78 :
79 0 : sal_uInt32 const offset = pagedata->location();
80 : OSL_PRECOND(!(nOffset != offset), "store::PageCache::updatePageAt(): inconsistent Offset");
81 0 : if (nOffset != offset)
82 0 : return store_E_InvalidParameter;
83 :
84 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::updatePageAt(): invalid Offset");
85 0 : if (nOffset == STORE_PAGE_NULL)
86 0 : return store_E_CantSeek;
87 :
88 0 : return updatePageAt_Impl (rxPage, nOffset);
89 : }
90 :
91 0 : storeError PageCache::removePageAt (sal_uInt32 nOffset)
92 : {
93 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset");
94 0 : if (nOffset == STORE_PAGE_NULL)
95 0 : return store_E_CantSeek;
96 :
97 0 : 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 87083 : static void * operator new (size_t, void * p) { return p; }
119 0 : static void operator delete (void *, void *) {}
120 :
121 : /** Construction.
122 : */
123 87083 : explicit Entry (PageHolder const & rxPage = PageHolder(), sal_uInt32 nOffset = STORE_PAGE_NULL)
124 87083 : : m_xPage(rxPage), m_nOffset(nOffset), m_pNext(0)
125 87083 : {}
126 :
127 : /** Destruction.
128 : */
129 46610 : ~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 133693 : EntryCache & EntryCache::get()
167 : {
168 133693 : static EntryCache g_entry_cache;
169 133693 : return g_entry_cache;
170 : }
171 :
172 114 : 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 114 : );
185 114 : }
186 :
187 114 : EntryCache::~EntryCache()
188 : {
189 114 : rtl_cache_destroy (m_entry_cache), m_entry_cache = 0;
190 114 : }
191 :
192 87083 : Entry * EntryCache::create (PageHolder const & rxPage, sal_uInt32 nOffset)
193 : {
194 87083 : void * pAddr = rtl_cache_alloc (m_entry_cache);
195 87083 : if (pAddr != 0)
196 : {
197 : // construct.
198 87083 : return new(pAddr) Entry (rxPage, nOffset);
199 : }
200 0 : return 0;
201 : }
202 :
203 46610 : void EntryCache::destroy (Entry * entry)
204 : {
205 46610 : if (entry != 0)
206 : {
207 : // destruct.
208 46610 : entry->~Entry();
209 :
210 : // return to cache.
211 46610 : rtl_cache_free (m_entry_cache, entry);
212 : }
213 46610 : }
214 :
215 : /*========================================================================
216 : *
217 : * highbit():= log2() + 1 (complexity O(1))
218 : *
219 : *======================================================================*/
220 892 : static int highbit(sal_Size n)
221 : {
222 892 : register int k = 1;
223 :
224 892 : 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 892 : if (n & 0xffff0000)
231 0 : k |= 16, n >>= 16;
232 892 : if (n & 0xff00)
233 351 : k |= 8, n >>= 8;
234 892 : if (n & 0xf0)
235 541 : k |= 4, n >>= 4;
236 892 : if (n & 0x0c)
237 187 : k |= 2, n >>= 2;
238 892 : if (n & 0x02)
239 712 : k++;
240 :
241 892 : 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 517651 : inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m)
272 : {
273 517651 : return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m));
274 : }
275 517651 : inline int hash_index_Impl (sal_uInt32 nOffset)
276 : {
277 517651 : 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 282 : PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize)
324 : : m_hash_table (m_hash_table_0),
325 : m_hash_size (theTableSize),
326 282 : m_hash_shift (highbit(m_hash_size) - 1),
327 282 : m_page_shift (highbit(nPageSize) - 1),
328 : m_hash_entries (0),
329 : m_nHit (0),
330 846 : m_nMissed (0)
331 : {
332 : static size_t const theSize = SAL_N_ELEMENTS(m_hash_table_0);
333 : STORE_STATIC_ASSERT(theSize == theTableSize);
334 282 : memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
335 282 : }
336 :
337 672 : PageCache_Impl::~PageCache_Impl()
338 : {
339 224 : double s_x = 0.0;
340 224 : sal_Size i, n = m_hash_size;
341 17184 : for (i = 0; i < n; i++)
342 : {
343 16960 : int x = 0;
344 16960 : Entry * entry = m_hash_table[i];
345 80530 : while (entry != 0)
346 : {
347 46610 : m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0;
348 46610 : EntryCache::get().destroy (entry);
349 46610 : entry = m_hash_table[i];
350 46610 : x += 1;
351 : }
352 16960 : s_x += double(x);
353 : }
354 224 : double ave = s_x / double(n);
355 : OSL_TRACE("ave hash chain length: %g", ave);
356 : (void) ave;
357 :
358 224 : if (m_hash_table != m_hash_table_0)
359 : {
360 74 : rtl_freeMemory (m_hash_table);
361 74 : m_hash_table = m_hash_table_0;
362 74 : m_hash_size = theTableSize;
363 74 : m_hash_shift = highbit(m_hash_size) - 1;
364 : }
365 : OSL_TRACE("Hits: %u, Misses: %u", m_nHit, m_nMissed);
366 448 : }
367 :
368 282 : oslInterlockedCount PageCache_Impl::acquire()
369 : {
370 282 : return OStoreObject::acquire();
371 : }
372 :
373 224 : oslInterlockedCount PageCache_Impl::release()
374 : {
375 224 : return OStoreObject::release();
376 : }
377 :
378 254 : void PageCache_Impl::rescale_Impl (sal_Size new_size)
379 : {
380 254 : sal_Size new_bytes = new_size * sizeof(Entry*);
381 254 : Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes));
382 :
383 254 : if (new_table != 0)
384 : {
385 254 : Entry ** old_table = m_hash_table;
386 254 : 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 254 : memset (new_table, 0, new_bytes);
392 :
393 254 : m_hash_table = new_table;
394 254 : m_hash_size = new_size;
395 254 : m_hash_shift = highbit(m_hash_size) - 1;
396 :
397 : sal_Size i;
398 19006 : for (i = 0; i < old_size; i++)
399 : {
400 18752 : Entry * curr = old_table[i];
401 131288 : while (curr != 0)
402 : {
403 93784 : Entry * next = curr->m_pNext;
404 93784 : int index = hash_index_Impl(curr->m_nOffset);
405 93784 : curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr;
406 93784 : curr = next;
407 : }
408 18752 : old_table[i] = 0;
409 : }
410 254 : if (old_table != m_hash_table_0)
411 : {
412 : //
413 134 : rtl_freeMemory (old_table);
414 : }
415 : }
416 254 : }
417 :
418 336784 : Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
419 : {
420 336784 : register int lookups = 0;
421 1248741 : while (entry != 0)
422 : {
423 824874 : if (entry->m_nOffset == nOffset)
424 249701 : break;
425 :
426 575173 : lookups += 1;
427 575173 : entry = entry->m_pNext;
428 : }
429 336784 : if (lookups > 2)
430 : {
431 98624 : sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
432 98878 : for (; ave > 4; new_size *= 2, ave /= 2)
433 254 : continue;
434 98624 : if (new_size != m_hash_size)
435 254 : rescale_Impl (new_size);
436 : }
437 336784 : return entry;
438 : }
439 :
440 336784 : storeError PageCache_Impl::lookupPageAt_Impl (
441 : PageHolder & rxPage,
442 : sal_uInt32 nOffset)
443 : {
444 336784 : int index = hash_index_Impl(nOffset);
445 336784 : Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
446 336784 : if (entry != 0)
447 : {
448 : // Existing entry.
449 249701 : rxPage = entry->m_xPage;
450 :
451 : // Update stats and leave.
452 249701 : m_nHit += 1;
453 249701 : return store_E_None;
454 : }
455 :
456 : // Cache miss. Update stats and leave.
457 87083 : m_nMissed += 1;
458 87083 : return store_E_NotExists;
459 : }
460 :
461 87083 : storeError PageCache_Impl::insertPageAt_Impl (
462 : PageHolder const & rxPage,
463 : sal_uInt32 nOffset)
464 : {
465 87083 : Entry * entry = EntryCache::get().create (rxPage, nOffset);
466 87083 : if (entry != 0)
467 : {
468 : // Insert new entry.
469 87083 : int index = hash_index_Impl(nOffset);
470 87083 : entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry;
471 :
472 : // Update stats and leave.
473 87083 : m_hash_entries += 1;
474 87083 : return store_E_None;
475 : }
476 0 : return store_E_OutOfMemory;
477 : }
478 :
479 0 : storeError PageCache_Impl::updatePageAt_Impl (
480 : PageHolder const & rxPage,
481 : sal_uInt32 nOffset)
482 : {
483 0 : int index = hash_index_Impl(nOffset);
484 0 : Entry * entry = lookup_Impl (m_hash_table[index], nOffset);
485 0 : if (entry != 0)
486 : {
487 : // Update existing entry.
488 0 : entry->m_xPage = rxPage;
489 :
490 : // Update stats and leave. // m_nUpdHit += 1;
491 0 : return store_E_None;
492 : }
493 0 : return insertPageAt_Impl (rxPage, nOffset);
494 : }
495 :
496 0 : storeError PageCache_Impl::removePageAt_Impl (
497 : sal_uInt32 nOffset)
498 : {
499 0 : Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
500 0 : while (*ppEntry != 0)
501 : {
502 0 : if ((*ppEntry)->m_nOffset == nOffset)
503 : {
504 : // Existing entry.
505 0 : Entry * entry = (*ppEntry);
506 :
507 : // Dequeue and destroy entry.
508 0 : (*ppEntry) = entry->m_pNext, entry->m_pNext = 0;
509 0 : EntryCache::get().destroy (entry);
510 :
511 : // Update stats and leave.
512 0 : m_hash_entries -= 1;
513 0 : return store_E_None;
514 : }
515 0 : ppEntry = &((*ppEntry)->m_pNext);
516 : }
517 0 : 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 282 : PageCache_createInstance (
538 : rtl::Reference< store::PageCache > & rxCache,
539 : sal_uInt16 nPageSize)
540 : {
541 282 : rxCache = new PageCache_Impl (nPageSize);
542 282 : if (!rxCache.is())
543 0 : return store_E_OutOfMemory;
544 :
545 282 : return store_E_None;
546 : }
547 :
548 : } // namespace store
549 :
550 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
