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