storcach.cxx 10.6 KB
Newer Older
1
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
Michael Meeks's avatar
Michael Meeks committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * This file is part of the LibreOffice project.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * This file incorporates work covered by the following license notice:
 *
 *   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 .
 */
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
19

20
#include <sal/config.h>
21

22 23
#include "storcach.hxx"

24 25 26 27 28
#include <sal/log.hxx>
#include <sal/types.h>
#include <sal/macros.h>
#include <rtl/alloc.h>
#include <osl/diagnose.h>
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
29

30
#include <store/types.h>
31 32
#include "storbase.hxx"

33
#include <memory>
34
#include <string.h>
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
35

36
using namespace store;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
37

38
// Entry
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
39

Noel Grandin's avatar
Noel Grandin committed
40
namespace store {
41 42
struct Entry
{
43
    // Representation
44
    std::shared_ptr<PageData> m_xPage;
45
    sal_uInt32 const m_nOffset;
46
    Entry *    m_pNext;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
47

48
    // Allocation
49 50
    static void * operator new (size_t, void * p) { return p; }
    static void   operator delete (void *, void *) {}
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
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
    {}
};
Noel Grandin's avatar
Noel Grandin committed
57
};
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
58

59
// EntryCache interface
60 61
namespace
{
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
62

63 64 65
class EntryCache
{
    rtl_cache_type * m_entry_cache;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
66

67 68
public:
    static EntryCache & get();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
69

70
    Entry * create (std::shared_ptr<PageData> const & rxPage, sal_uInt32 nOffset);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
71

72
    void destroy (Entry * entry);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
73

74 75 76
protected:
    EntryCache();
    ~EntryCache();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
77 78
};

79
} // namespace
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
80

81
// EntryCache implementation
82 83 84 85 86 87 88
EntryCache & EntryCache::get()
{
    static EntryCache g_entry_cache;
    return g_entry_cache;
}

EntryCache::EntryCache()
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
89
{
90 91 92 93
    m_entry_cache = rtl_cache_create (
        "store_cache_entry_cache",
        sizeof(Entry),
        0, // objalign
94 95 96 97 98
        nullptr, // constructor
        nullptr, // destructor
        nullptr, // reclaim
        nullptr, // userarg
        nullptr, // default source
99 100 101 102 103 104
        0  // flags
        );
}

EntryCache::~EntryCache()
{
105 106
    rtl_cache_destroy (m_entry_cache);
    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)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
113
    {
114
        // construct
115
        return new(pAddr) Entry (rxPage, nOffset);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
116
    }
117
    return nullptr;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
118 119
}

120
void EntryCache::destroy (Entry * entry)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
121
{
122
    if (entry != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
123
    {
124
        // destruct
125
        entry->~Entry();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
126

127
        // return to cache
128
        rtl_cache_free (m_entry_cache, entry);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
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 140
#if SAL_TYPES_SIZEOFLONG == 8
    if (n & 0xffffffff00000000ul)
141 142 143 144
    {
        k |= 32;
        n >>= 32;
    }
145 146
#endif
    if (n & 0xffff0000)
147 148 149 150
    {
        k |= 16;
        n >>= 16;
    }
151
    if (n & 0xff00)
152 153 154 155
    {
        k |= 8;
        n >>= 8;
    }
156
    if (n & 0xf0)
157 158 159 160
    {
        k |= 4;
        n >>= 4;
    }
161
    if (n & 0x0c)
162 163 164 165
    {
        k |= 2;
        n >>= 2;
    }
166 167 168
    if (n & 0x02)
        k++;

169
    return k;
170 171
}

172

Noel Grandin's avatar
Noel Grandin committed
173
PageCache::PageCache (sal_uInt16 nPageSize)
174 175 176 177 178 179 180 181
    : 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)
{
182
    static size_t const theSize = SAL_N_ELEMENTS(m_hash_table_0);
183
    static_assert(theSize == theTableSize, "must be equal");
184
    memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
185 186
}

Noel Grandin's avatar
Noel Grandin committed
187
PageCache::~PageCache()
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
188
{
189
    double s_x = 0.0;
190
    std::size_t i, n = m_hash_size;
191
    for (i = 0; i < n; i++)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
192
    {
193 194
        int x = 0;
        Entry * entry = m_hash_table[i];
195
        while (entry != nullptr)
196
        {
197 198
            m_hash_table[i] = entry->m_pNext;
            entry->m_pNext = nullptr;
199 200 201 202 203
            EntryCache::get().destroy (entry);
            entry = m_hash_table[i];
            x += 1;
        }
        s_x  += double(x);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
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)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
209
    {
210
        std::free (m_hash_table);
211 212 213
        m_hash_table = m_hash_table_0;
        m_hash_size  = theTableSize;
        m_hash_shift = highbit(m_hash_size) - 1;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
214
    }
215
    SAL_INFO("store", "Hits: " << m_nHit << ", Misses: " <<  m_nMissed);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
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 224
    if (new_table == nullptr)
        return;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
225

226 227
    Entry ** old_table = m_hash_table;
    std::size_t old_size  = m_hash_size;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
228

229 230 231 232 233
    SAL_INFO(
        "store",
        "ave chain length: " << (m_hash_entries >> m_hash_shift)
            << ", total entries: " << m_hash_entries << " [old_size: "
            << old_size << " new_size: " << new_size << "]");
234

235
    memset (new_table, 0, new_bytes);
236

237 238 239 240 241 242 243 244 245
    m_hash_table = new_table;
    m_hash_size  = new_size;
    m_hash_shift = highbit(m_hash_size) - 1;

    std::size_t i;
    for (i = 0; i < old_size; i++)
    {
        Entry * curr = old_table[i];
        while (curr != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
246
        {
247 248 249 250 251
            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;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
252
        }
253 254 255 256
        old_table[i] = nullptr;
    }
    if (old_table != m_hash_table_0)
    {
257

258
        std::free (old_table);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
259 260 261
    }
}

Noel Grandin's avatar
Noel Grandin committed
262
Entry * PageCache::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
263
{
264
    int lookups = 0;
265
    while (entry != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
266
    {
267 268
        if (entry->m_nOffset == nOffset)
            break;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
269

270 271
        lookups += 1;
        entry = entry->m_pNext;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
272
    }
273 274
    if (lookups > 2)
    {
275
        std::size_t new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
276 277 278 279 280 281 282
        for (; ave > 4; new_size *= 2, ave /= 2)
            continue;
        if (new_size != m_hash_size)
            rescale_Impl (new_size);
    }
    return entry;
}
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
283

284
storeError PageCache::lookupPageAt (std::shared_ptr<PageData> & rxPage, sal_uInt32 nOffset)
285
{
Noel Grandin's avatar
Noel Grandin committed
286 287 288 289
    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
    if (nOffset == STORE_PAGE_NULL)
        return store_E_CantSeek;

290 291
    int index = hash_index_Impl(nOffset);
    Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
292
    if (entry != nullptr)
293 294 295
    {
        // Existing entry.
        rxPage = entry->m_xPage;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
296

297 298 299 300
        // Update stats and leave.
        m_nHit += 1;
        return store_E_None;
    }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
301

302 303 304
    // Cache miss. Update stats and leave.
    m_nMissed += 1;
    return store_E_NotExists;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
305 306
}

307
storeError PageCache::insertPageAt (std::shared_ptr<PageData> const & rxPage, sal_uInt32 nOffset)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
308
{
Noel Grandin's avatar
Noel Grandin committed
309 310
    // [SECURITY:ValInput]
    PageData const * pagedata = rxPage.get();
311 312
    OSL_PRECOND(!(pagedata == nullptr), "store::PageCache::insertPageAt(): invalid Page");
    if (pagedata == nullptr)
Noel Grandin's avatar
Noel Grandin committed
313 314 315 316 317 318 319 320 321 322 323
        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;

324
    Entry * entry = EntryCache::get().create (rxPage, nOffset);
325
    if (entry != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
326
    {
327 328
        // Insert new entry.
        int index = hash_index_Impl(nOffset);
329 330
        entry->m_pNext = m_hash_table[index];
        m_hash_table[index] = entry;
331 332 333 334

        // Update stats and leave.
        m_hash_entries += 1;
        return store_E_None;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
335
    }
336 337
    return store_E_OutOfMemory;
}
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
338

339
storeError PageCache::updatePageAt (std::shared_ptr<PageData> const & rxPage, sal_uInt32 nOffset)
340
{
Noel Grandin's avatar
Noel Grandin committed
341 342
    // [SECURITY:ValInput]
    PageData const * pagedata = rxPage.get();
343 344
    OSL_PRECOND(!(pagedata == nullptr), "store::PageCache::updatePageAt(): invalid Page");
    if (pagedata == nullptr)
Noel Grandin's avatar
Noel Grandin committed
345 346 347 348 349 350 351 352 353 354 355
        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;

356 357
    int index = hash_index_Impl(nOffset);
    Entry *  entry  = lookup_Impl (m_hash_table[index], nOffset);
358
    if (entry != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
359
    {
360 361
        // Update existing entry.
        entry->m_xPage = rxPage;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
362

363 364
        // Update stats and leave. // m_nUpdHit += 1;
        return store_E_None;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
365
    }
Noel Grandin's avatar
Noel Grandin committed
366
    return insertPageAt (rxPage, nOffset);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
367 368
}

Noel Grandin's avatar
Noel Grandin committed
369
storeError PageCache::removePageAt (sal_uInt32 nOffset)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
370
{
Noel Grandin's avatar
Noel Grandin committed
371 372 373 374
    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset");
    if (nOffset == STORE_PAGE_NULL)
        return store_E_CantSeek;

375
    Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
376
    while (*ppEntry != nullptr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
377
    {
378
        if ((*ppEntry)->m_nOffset == nOffset)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
379
        {
380
            // Existing entry.
381
            Entry * entry = *ppEntry;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
382

383
            // Dequeue and destroy entry.
384 385
            (*ppEntry) = entry->m_pNext;
            entry->m_pNext = nullptr;
386 387 388 389 390
            EntryCache::get().destroy (entry);

            // Update stats and leave.
            m_hash_entries -= 1;
            return store_E_None;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
391
        }
392
        ppEntry = &((*ppEntry)->m_pNext);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
393
    }
394
    return store_E_NotExists;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
395 396
}

397
/*
398 399 400 401
 *
 * Old OStorePageCache implementation.
 *
 * (two-way association (sorted address array, LRU chain)).
402
 * (external PageData representation).
403
 *
404
 */
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
405

406
/*
407 408 409
 *
 * PageCache factory implementation.
 *
410
 */
411 412 413 414 415 416 417
namespace store {

storeError
PageCache_createInstance (
    rtl::Reference< store::PageCache > & rxCache,
    sal_uInt16                           nPageSize)
{
Noel Grandin's avatar
Noel Grandin committed
418
    rxCache = new PageCache (nPageSize);
419 420
    if (!rxCache.is())
        return store_E_OutOfMemory;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
421

422
    return store_E_None;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
423
}
424 425

} // namespace store
426 427

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */