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