store/source/storcach.cxx

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