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