store/source/storcach.cxx

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