xref: /aoo4110/main/store/source/storcach.cxx (revision b1cdbd2c)
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__anon03e89cd30111::Entry126     static void * operator new (size_t, void * p) { return p; }
operator delete__anon03e89cd30111::Entry127     static void   operator delete (void *, void *) {}
128 
129     /** Construction.
130      */
Entry__anon03e89cd30111::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__anon03e89cd30111::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     register 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     register 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