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