store/source/storcach.cxx

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