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