store/source/storcach.cxx

/**************************************************************
 *
 * 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 <stddef.h>
#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