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