/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ // MARKER(update_precomp.py): autogen include statement, do not remove #include "precompiled_store.hxx" #include "storcach.hxx" #include "sal/types.h" #include "rtl/alloc.h" #include "osl/diagnose.h" #include "store/types.h" #include "object.hxx" #include "storbase.hxx" #ifndef INCLUDED_STDDEF_H #include #define INCLUDED_STDDEF_H #endif using namespace store; /*======================================================================== * * PageCache (non-virtual interface) implementation. * *======================================================================*/ storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset) { OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset"); if (nOffset == STORE_PAGE_NULL) return store_E_CantSeek; return lookupPageAt_Impl (rxPage, nOffset); } storeError PageCache::insertPageAt (PageHolder const & rxPage, sal_uInt32 nOffset) { // [SECURITY:ValInput] PageData const * pagedata = rxPage.get(); OSL_PRECOND(!(pagedata == 0), "store::PageCache::insertPageAt(): invalid Page"); if (pagedata == 0) return store_E_InvalidParameter; sal_uInt32 const offset = pagedata->location(); OSL_PRECOND(!(nOffset != offset), "store::PageCache::insertPageAt(): inconsistent Offset"); if (nOffset != offset) return store_E_InvalidParameter; OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::insertPageAt(): invalid Offset"); if (nOffset == STORE_PAGE_NULL) return store_E_CantSeek; return insertPageAt_Impl (rxPage, nOffset); } storeError PageCache::updatePageAt (PageHolder const & rxPage, sal_uInt32 nOffset) { // [SECURITY:ValInput] PageData const * pagedata = rxPage.get(); OSL_PRECOND(!(pagedata == 0), "store::PageCache::updatePageAt(): invalid Page"); if (pagedata == 0) return store_E_InvalidParameter; sal_uInt32 const offset = pagedata->location(); OSL_PRECOND(!(nOffset != offset), "store::PageCache::updatePageAt(): inconsistent Offset"); if (nOffset != offset) return store_E_InvalidParameter; OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::updatePageAt(): invalid Offset"); if (nOffset == STORE_PAGE_NULL) return store_E_CantSeek; return updatePageAt_Impl (rxPage, nOffset); } storeError PageCache::removePageAt (sal_uInt32 nOffset) { OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset"); if (nOffset == STORE_PAGE_NULL) return store_E_CantSeek; return removePageAt_Impl (nOffset); } /*======================================================================== * * Entry. * *======================================================================*/ namespace { struct Entry { /** Representation. */ PageHolder m_xPage; sal_uInt32 m_nOffset; Entry * m_pNext; /** Allocation. */ static void * operator new (size_t, void * p) { return p; } static void operator delete (void *, void *) {} /** Construction. */ explicit Entry (PageHolder const & rxPage = PageHolder(), sal_uInt32 nOffset = STORE_PAGE_NULL) : m_xPage(rxPage), m_nOffset(nOffset), m_pNext(0) {} /** Destruction. */ ~Entry() {} }; } // namespace /*======================================================================== * * EntryCache interface. * *======================================================================*/ namespace { class EntryCache { rtl_cache_type * m_entry_cache; public: static EntryCache & get(); Entry * create (PageHolder const & rxPage, sal_uInt32 nOffset); void destroy (Entry * entry); protected: EntryCache(); ~EntryCache(); }; } // namespace /*======================================================================== * * EntryCache implementation. * *======================================================================*/ EntryCache & EntryCache::get() { static EntryCache g_entry_cache; return g_entry_cache; } EntryCache::EntryCache() { m_entry_cache = rtl_cache_create ( "store_cache_entry_cache", sizeof(Entry), 0, // objalign 0, // constructor 0, // destructor 0, // reclaim 0, // userarg 0, // default source 0 // flags ); } EntryCache::~EntryCache() { rtl_cache_destroy (m_entry_cache), m_entry_cache = 0; } Entry * EntryCache::create (PageHolder const & rxPage, sal_uInt32 nOffset) { void * pAddr = rtl_cache_alloc (m_entry_cache); if (pAddr != 0) { // construct. return new(pAddr) Entry (rxPage, nOffset); } return 0; } void EntryCache::destroy (Entry * entry) { if (entry != 0) { // destruct. entry->~Entry(); // return to cache. rtl_cache_free (m_entry_cache, entry); } } /*======================================================================== * * highbit():= log2() + 1 (complexity O(1)) * *======================================================================*/ static int highbit(sal_Size n) { register int k = 1; if (n == 0) return (0); #if SAL_TYPES_SIZEOFLONG == 8 if (n & 0xffffffff00000000ul) k |= 32, n >>= 32; #endif if (n & 0xffff0000) k |= 16, n >>= 16; if (n & 0xff00) k |= 8, n >>= 8; if (n & 0xf0) k |= 4, n >>= 4; if (n & 0x0c) k |= 2, n >>= 2; if (n & 0x02) k++; return (k); } /*======================================================================== * * PageCache_Impl implementation. * *======================================================================*/ namespace store { class PageCache_Impl : public store::OStoreObject, public store::PageCache { /** Representation. */ static size_t const theTableSize = 32; STORE_STATIC_ASSERT(STORE_IMPL_ISP2(theTableSize)); Entry ** m_hash_table; Entry * m_hash_table_0[theTableSize]; size_t m_hash_size; size_t m_hash_shift; size_t const m_page_shift; size_t m_hash_entries; // total number of entries in table. size_t m_nHit; size_t m_nMissed; inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m) { return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m)); } inline int hash_index_Impl (sal_uInt32 nOffset) { return hash_Impl(nOffset, m_hash_shift, m_page_shift, m_hash_size - 1); } Entry * lookup_Impl (Entry * entry, sal_uInt32 nOffset); void rescale_Impl (sal_Size new_size); /** PageCache Implementation. */ virtual storeError lookupPageAt_Impl ( PageHolder & rxPage, sal_uInt32 nOffset); virtual storeError insertPageAt_Impl ( PageHolder const & rxPage, sal_uInt32 nOffset); virtual storeError updatePageAt_Impl ( PageHolder const & rxPage, sal_uInt32 nOffset); virtual storeError removePageAt_Impl ( sal_uInt32 nOffset); /** Not implemented. */ PageCache_Impl (PageCache_Impl const &); PageCache_Impl & operator= (PageCache_Impl const &); public: /** Construction. */ explicit PageCache_Impl (sal_uInt16 nPageSize); /** Delegate multiple inherited IReference. */ virtual oslInterlockedCount SAL_CALL acquire(); virtual oslInterlockedCount SAL_CALL release(); protected: /** Destruction. */ virtual ~PageCache_Impl (void); }; } // namespace store PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize) : m_hash_table (m_hash_table_0), m_hash_size (theTableSize), m_hash_shift (highbit(m_hash_size) - 1), m_page_shift (highbit(nPageSize) - 1), m_hash_entries (0), m_nHit (0), m_nMissed (0) { static size_t const theSize = sizeof(m_hash_table_0) / sizeof(m_hash_table_0[0]); STORE_STATIC_ASSERT(theSize == theTableSize); memset(m_hash_table_0, 0, sizeof(m_hash_table_0)); } PageCache_Impl::~PageCache_Impl() { double s_x = 0.0, s_xx = 0.0; sal_Size i, n = m_hash_size; for (i = 0; i < n; i++) { int x = 0; Entry * entry = m_hash_table[i]; while (entry != 0) { m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0; EntryCache::get().destroy (entry); entry = m_hash_table[i]; x += 1; } s_x += double(x); s_xx += double(x) * double(x); } double ave = s_x / double(n); OSL_TRACE("ave hash chain length: %g", ave); (void) ave; if (m_hash_table != m_hash_table_0) { rtl_freeMemory (m_hash_table); m_hash_table = m_hash_table_0; m_hash_size = theTableSize; m_hash_shift = highbit(m_hash_size) - 1; } OSL_TRACE("Hits: %u, Misses: %u", m_nHit, m_nMissed); } oslInterlockedCount PageCache_Impl::acquire() { return OStoreObject::acquire(); } oslInterlockedCount PageCache_Impl::release() { return OStoreObject::release(); } void PageCache_Impl::rescale_Impl (sal_Size new_size) { sal_Size new_bytes = new_size * sizeof(Entry*); Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes)); if (new_table != 0) { Entry ** old_table = m_hash_table; sal_Size old_size = m_hash_size; OSL_TRACE("ave chain length: %u, total entries: %u [old_size: %u, new_size: %u]", m_hash_entries >> m_hash_shift, m_hash_entries, old_size, new_size); memset (new_table, 0, new_bytes); m_hash_table = new_table; m_hash_size = new_size; m_hash_shift = highbit(m_hash_size) - 1; sal_Size i; for (i = 0; i < old_size; i++) { Entry * curr = old_table[i]; while (curr != 0) { Entry * next = curr->m_pNext; int index = hash_index_Impl(curr->m_nOffset); curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr; curr = next; } old_table[i] = 0; } if (old_table != m_hash_table_0) { // rtl_freeMemory (old_table); } } } Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset) { register int lookups = 0; while (entry != 0) { if (entry->m_nOffset == nOffset) break; lookups += 1; entry = entry->m_pNext; } if (lookups > 2) { sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift; for (; ave > 4; new_size *= 2, ave /= 2) continue; if (new_size != m_hash_size) rescale_Impl (new_size); } return entry; } storeError PageCache_Impl::lookupPageAt_Impl ( PageHolder & rxPage, sal_uInt32 nOffset) { int index = hash_index_Impl(nOffset); Entry const * entry = lookup_Impl (m_hash_table[index], nOffset); if (entry != 0) { // Existing entry. rxPage = entry->m_xPage; // Update stats and leave. m_nHit += 1; return store_E_None; } // Cache miss. Update stats and leave. m_nMissed += 1; return store_E_NotExists; } storeError PageCache_Impl::insertPageAt_Impl ( PageHolder const & rxPage, sal_uInt32 nOffset) { Entry * entry = EntryCache::get().create (rxPage, nOffset); if (entry != 0) { // Insert new entry. int index = hash_index_Impl(nOffset); entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry; // Update stats and leave. m_hash_entries += 1; return store_E_None; } return store_E_OutOfMemory; } storeError PageCache_Impl::updatePageAt_Impl ( PageHolder const & rxPage, sal_uInt32 nOffset) { int index = hash_index_Impl(nOffset); Entry * entry = lookup_Impl (m_hash_table[index], nOffset); if (entry != 0) { // Update existing entry. entry->m_xPage = rxPage; // Update stats and leave. // m_nUpdHit += 1; return store_E_None; } return insertPageAt_Impl (rxPage, nOffset); } storeError PageCache_Impl::removePageAt_Impl ( sal_uInt32 nOffset) { Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]); while (*ppEntry != 0) { if ((*ppEntry)->m_nOffset == nOffset) { // Existing entry. Entry * entry = (*ppEntry); // Dequeue and destroy entry. (*ppEntry) = entry->m_pNext, entry->m_pNext = 0; EntryCache::get().destroy (entry); // Update stats and leave. m_hash_entries -= 1; return store_E_None; } ppEntry = &((*ppEntry)->m_pNext); } return store_E_NotExists; } /*======================================================================== * * Old OStorePageCache implementation. * * (two-way association (sorted address array, LRU chain)). * (external OStorePageData representation). * *======================================================================*/ /*======================================================================== * * PageCache factory implementation. * *======================================================================*/ namespace store { storeError PageCache_createInstance ( rtl::Reference< store::PageCache > & rxCache, sal_uInt16 nPageSize) { rxCache = new PageCache_Impl (nPageSize); if (!rxCache.is()) return store_E_OutOfMemory; return store_E_None; } } // namespace store