LCOV - code coverage report
Current view: top level - store/source - storcach.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 176 0.0 %
Date: 2014-04-14 Functions: 0 28 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : #include "boost/static_assert.hpp"
      24             : 
      25             : #include "storcach.hxx"
      26             : 
      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           0 : storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset)
      42             : {
      43             :     OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
      44           0 :     if (nOffset == STORE_PAGE_NULL)
      45           0 :         return store_E_CantSeek;
      46             : 
      47           0 :     return lookupPageAt_Impl (rxPage, nOffset);
      48             : }
      49             : 
      50           0 : storeError PageCache::insertPageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
      51             : {
      52             :     // [SECURITY:ValInput]
      53           0 :     PageData const * pagedata = rxPage.get();
      54             :     OSL_PRECOND(!(pagedata == 0), "store::PageCache::insertPageAt(): invalid Page");
      55           0 :     if (pagedata == 0)
      56           0 :         return store_E_InvalidParameter;
      57             : 
      58           0 :     sal_uInt32 const offset = pagedata->location();
      59             :     OSL_PRECOND(!(nOffset != offset), "store::PageCache::insertPageAt(): inconsistent Offset");
      60           0 :     if (nOffset != offset)
      61           0 :         return store_E_InvalidParameter;
      62             : 
      63             :     OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::insertPageAt(): invalid Offset");
      64           0 :     if (nOffset == STORE_PAGE_NULL)
      65           0 :         return store_E_CantSeek;
      66             : 
      67           0 :     return insertPageAt_Impl (rxPage, nOffset);
      68             : }
      69             : 
      70           0 : storeError PageCache::updatePageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
      71             : {
      72             :     // [SECURITY:ValInput]
      73           0 :     PageData const * pagedata = rxPage.get();
      74             :     OSL_PRECOND(!(pagedata == 0), "store::PageCache::updatePageAt(): invalid Page");
      75           0 :     if (pagedata == 0)
      76           0 :         return store_E_InvalidParameter;
      77             : 
      78           0 :     sal_uInt32 const offset = pagedata->location();
      79             :     OSL_PRECOND(!(nOffset != offset), "store::PageCache::updatePageAt(): inconsistent Offset");
      80           0 :     if (nOffset != offset)
      81           0 :         return store_E_InvalidParameter;
      82             : 
      83             :     OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::updatePageAt(): invalid Offset");
      84           0 :     if (nOffset == STORE_PAGE_NULL)
      85           0 :         return store_E_CantSeek;
      86             : 
      87           0 :     return updatePageAt_Impl (rxPage, nOffset);
      88             : }
      89             : 
      90           0 : storeError PageCache::removePageAt (sal_uInt32 nOffset)
      91             : {
      92             :     OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset");
      93           0 :     if (nOffset == STORE_PAGE_NULL)
      94           0 :         return store_E_CantSeek;
      95             : 
      96           0 :     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           0 :     static void * operator new (size_t, void * p) { return p; }
     112           0 :     static void   operator delete (void *, void *) {}
     113             : 
     114             :     // Construction
     115           0 :     explicit Entry (PageHolder const & rxPage = PageHolder(), sal_uInt32 nOffset = STORE_PAGE_NULL)
     116           0 :         : m_xPage(rxPage), m_nOffset(nOffset), m_pNext(0)
     117           0 :     {}
     118             : 
     119             :     // Destruction
     120           0 :     ~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           0 : EntryCache & EntryCache::get()
     149             : {
     150           0 :     static EntryCache g_entry_cache;
     151           0 :     return g_entry_cache;
     152             : }
     153             : 
     154           0 : 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           0 :         );
     167           0 : }
     168             : 
     169           0 : EntryCache::~EntryCache()
     170             : {
     171           0 :     rtl_cache_destroy (m_entry_cache), m_entry_cache = 0;
     172           0 : }
     173             : 
     174           0 : Entry * EntryCache::create (PageHolder const & rxPage, sal_uInt32 nOffset)
     175             : {
     176           0 :     void * pAddr = rtl_cache_alloc (m_entry_cache);
     177           0 :     if (pAddr != 0)
     178             :     {
     179             :         // construct
     180           0 :         return new(pAddr) Entry (rxPage, nOffset);
     181             :     }
     182           0 :     return 0;
     183             : }
     184             : 
     185           0 : void EntryCache::destroy (Entry * entry)
     186             : {
     187           0 :     if (entry != 0)
     188             :     {
     189             :         // destruct
     190           0 :         entry->~Entry();
     191             : 
     192             :         // return to cache
     193           0 :         rtl_cache_free (m_entry_cache, entry);
     194             :     }
     195           0 : }
     196             : 
     197             : // highbit():= log2() + 1 (complexity O(1))
     198           0 : static int highbit(sal_Size n)
     199             : {
     200           0 :     int k = 1;
     201             : 
     202           0 :     if (n == 0)
     203           0 :         return (0);
     204             : #if SAL_TYPES_SIZEOFLONG == 8
     205             :     if (n & 0xffffffff00000000ul)
     206             :         k |= 32, n >>= 32;
     207             : #endif
     208           0 :     if (n & 0xffff0000)
     209           0 :         k |= 16, n >>= 16;
     210           0 :     if (n & 0xff00)
     211           0 :         k |= 8, n >>= 8;
     212           0 :     if (n & 0xf0)
     213           0 :         k |= 4, n >>= 4;
     214           0 :     if (n & 0x0c)
     215           0 :         k |= 2, n >>= 2;
     216           0 :     if (n & 0x02)
     217           0 :         k++;
     218             : 
     219           0 :     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             :     BOOST_STATIC_ASSERT(STORE_IMPL_ISP2(theTableSize));
     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           0 :     inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m)
     246             :     {
     247           0 :         return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m));
     248             :     }
     249           0 :     inline int hash_index_Impl (sal_uInt32 nOffset)
     250             :     {
     251           0 :         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             :     // Delegate multiple inherited IReference
     278             :     virtual oslInterlockedCount SAL_CALL acquire() SAL_OVERRIDE;
     279             :     virtual oslInterlockedCount SAL_CALL release() SAL_OVERRIDE;
     280             : 
     281             : protected:
     282             :     // Destruction
     283             :     virtual ~PageCache_Impl (void);
     284             : };
     285             : 
     286             : } // namespace store
     287             : 
     288           0 : PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize)
     289             :     : m_hash_table   (m_hash_table_0),
     290             :       m_hash_size    (theTableSize),
     291           0 :       m_hash_shift   (highbit(m_hash_size) - 1),
     292           0 :       m_page_shift   (highbit(nPageSize) - 1),
     293             :       m_hash_entries (0),
     294             :       m_nHit         (0),
     295           0 :       m_nMissed      (0)
     296             : {
     297             :     static size_t const theSize = SAL_N_ELEMENTS(m_hash_table_0);
     298             :     BOOST_STATIC_ASSERT(theSize == theTableSize);
     299           0 :     memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
     300           0 : }
     301             : 
     302           0 : PageCache_Impl::~PageCache_Impl()
     303             : {
     304           0 :     double s_x = 0.0;
     305           0 :     sal_Size i, n = m_hash_size;
     306           0 :     for (i = 0; i < n; i++)
     307             :     {
     308           0 :         int x = 0;
     309           0 :         Entry * entry = m_hash_table[i];
     310           0 :         while (entry != 0)
     311             :         {
     312           0 :             m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0;
     313           0 :             EntryCache::get().destroy (entry);
     314           0 :             entry = m_hash_table[i];
     315           0 :             x += 1;
     316             :         }
     317           0 :         s_x  += double(x);
     318             :     }
     319           0 :     double ave = s_x / double(n);
     320             :     OSL_TRACE("ave hash chain length: %g", ave);
     321             :     (void) ave;
     322             : 
     323           0 :     if (m_hash_table != m_hash_table_0)
     324             :     {
     325           0 :         rtl_freeMemory (m_hash_table);
     326           0 :         m_hash_table = m_hash_table_0;
     327           0 :         m_hash_size  = theTableSize;
     328           0 :         m_hash_shift = highbit(m_hash_size) - 1;
     329             :     }
     330             :     OSL_TRACE("Hits: %zu, Misses: %zu", m_nHit, m_nMissed);
     331           0 : }
     332             : 
     333           0 : oslInterlockedCount PageCache_Impl::acquire()
     334             : {
     335           0 :     return OStoreObject::acquire();
     336             : }
     337             : 
     338           0 : oslInterlockedCount PageCache_Impl::release()
     339             : {
     340           0 :     return OStoreObject::release();
     341             : }
     342             : 
     343           0 : void PageCache_Impl::rescale_Impl (sal_Size new_size)
     344             : {
     345           0 :     sal_Size new_bytes = new_size * sizeof(Entry*);
     346           0 :     Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes));
     347             : 
     348           0 :     if (new_table != 0)
     349             :     {
     350           0 :         Entry ** old_table = m_hash_table;
     351           0 :         sal_Size old_size  = m_hash_size;
     352             : 
     353             :         OSL_TRACE("ave chain length: %zu, total entries: %zu [old_size: %zu new_size: %zu]",
     354             :                   m_hash_entries >> m_hash_shift, m_hash_entries, old_size, new_size);
     355             : 
     356           0 :         memset (new_table, 0, new_bytes);
     357             : 
     358           0 :         m_hash_table = new_table;
     359           0 :         m_hash_size  = new_size;
     360           0 :         m_hash_shift = highbit(m_hash_size) - 1;
     361             : 
     362             :         sal_Size i;
     363           0 :         for (i = 0; i < old_size; i++)
     364             :         {
     365           0 :             Entry * curr = old_table[i];
     366           0 :             while (curr != 0)
     367             :             {
     368           0 :                 Entry * next = curr->m_pNext;
     369           0 :                 int index = hash_index_Impl(curr->m_nOffset);
     370           0 :                 curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr;
     371           0 :                 curr = next;
     372             :             }
     373           0 :             old_table[i] = 0;
     374             :         }
     375           0 :         if (old_table != m_hash_table_0)
     376             :         {
     377             : 
     378           0 :             rtl_freeMemory (old_table);
     379             :         }
     380             :     }
     381           0 : }
     382             : 
     383           0 : Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
     384             : {
     385           0 :     int lookups = 0;
     386           0 :     while (entry != 0)
     387             :     {
     388           0 :         if (entry->m_nOffset == nOffset)
     389           0 :             break;
     390             : 
     391           0 :         lookups += 1;
     392           0 :         entry = entry->m_pNext;
     393             :     }
     394           0 :     if (lookups > 2)
     395             :     {
     396           0 :         sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
     397           0 :         for (; ave > 4; new_size *= 2, ave /= 2)
     398           0 :             continue;
     399           0 :         if (new_size != m_hash_size)
     400           0 :             rescale_Impl (new_size);
     401             :     }
     402           0 :     return entry;
     403             : }
     404             : 
     405           0 : storeError PageCache_Impl::lookupPageAt_Impl (
     406             :     PageHolder & rxPage,
     407             :     sal_uInt32   nOffset)
     408             : {
     409           0 :     int index = hash_index_Impl(nOffset);
     410           0 :     Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
     411           0 :     if (entry != 0)
     412             :     {
     413             :         // Existing entry.
     414           0 :         rxPage = entry->m_xPage;
     415             : 
     416             :         // Update stats and leave.
     417           0 :         m_nHit += 1;
     418           0 :         return store_E_None;
     419             :     }
     420             : 
     421             :     // Cache miss. Update stats and leave.
     422           0 :     m_nMissed += 1;
     423           0 :     return store_E_NotExists;
     424             : }
     425             : 
     426           0 : storeError PageCache_Impl::insertPageAt_Impl (
     427             :     PageHolder const & rxPage,
     428             :     sal_uInt32         nOffset)
     429             : {
     430           0 :     Entry * entry = EntryCache::get().create (rxPage, nOffset);
     431           0 :     if (entry != 0)
     432             :     {
     433             :         // Insert new entry.
     434           0 :         int index = hash_index_Impl(nOffset);
     435           0 :         entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry;
     436             : 
     437             :         // Update stats and leave.
     438           0 :         m_hash_entries += 1;
     439           0 :         return store_E_None;
     440             :     }
     441           0 :     return store_E_OutOfMemory;
     442             : }
     443             : 
     444           0 : storeError PageCache_Impl::updatePageAt_Impl (
     445             :     PageHolder const & rxPage,
     446             :     sal_uInt32         nOffset)
     447             : {
     448           0 :     int index = hash_index_Impl(nOffset);
     449           0 :     Entry *  entry  = lookup_Impl (m_hash_table[index], nOffset);
     450           0 :     if (entry != 0)
     451             :     {
     452             :         // Update existing entry.
     453           0 :         entry->m_xPage = rxPage;
     454             : 
     455             :         // Update stats and leave. // m_nUpdHit += 1;
     456           0 :         return store_E_None;
     457             :     }
     458           0 :     return insertPageAt_Impl (rxPage, nOffset);
     459             : }
     460             : 
     461           0 : storeError PageCache_Impl::removePageAt_Impl (
     462             :     sal_uInt32 nOffset)
     463             : {
     464           0 :     Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
     465           0 :     while (*ppEntry != 0)
     466             :     {
     467           0 :         if ((*ppEntry)->m_nOffset == nOffset)
     468             :         {
     469             :             // Existing entry.
     470           0 :             Entry * entry = (*ppEntry);
     471             : 
     472             :             // Dequeue and destroy entry.
     473           0 :             (*ppEntry) = entry->m_pNext, entry->m_pNext = 0;
     474           0 :             EntryCache::get().destroy (entry);
     475             : 
     476             :             // Update stats and leave.
     477           0 :             m_hash_entries -= 1;
     478           0 :             return store_E_None;
     479             :         }
     480           0 :         ppEntry = &((*ppEntry)->m_pNext);
     481             :     }
     482           0 :     return store_E_NotExists;
     483             : }
     484             : 
     485             : /*
     486             :  *
     487             :  * Old OStorePageCache implementation.
     488             :  *
     489             :  * (two-way association (sorted address array, LRU chain)).
     490             :  * (external OStorePageData representation).
     491             :  *
     492             :  */
     493             : 
     494             : /*
     495             :  *
     496             :  * PageCache factory implementation.
     497             :  *
     498             :  */
     499             : namespace store {
     500             : 
     501             : storeError
     502           0 : PageCache_createInstance (
     503             :     rtl::Reference< store::PageCache > & rxCache,
     504             :     sal_uInt16                           nPageSize)
     505             : {
     506           0 :     rxCache = new PageCache_Impl (nPageSize);
     507           0 :     if (!rxCache.is())
     508           0 :         return store_E_OutOfMemory;
     509             : 
     510           0 :     return store_E_None;
     511             : }
     512             : 
     513             : } // namespace store
     514             : 
     515             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10