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