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 561 : storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset)
42 : {
43 : OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
44 561 : if (nOffset == STORE_PAGE_NULL)
45 0 : return store_E_CantSeek;
46 :
47 561 : 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 1226 : ~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 2452 : EntryCache & EntryCache::get()
149 : {
150 2452 : static EntryCache g_entry_cache;
151 2452 : 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 1226 : void EntryCache::destroy (Entry * entry)
186 : {
187 1226 : if (entry != 0)
188 : {
189 : // destruct
190 1226 : entry->~Entry();
191 :
192 : // return to cache
193 1226 : rtl_cache_free (m_entry_cache, entry);
194 : }
195 1226 : }
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 : if (n & 0xffffffff00000000ul)
206 : 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 : 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 4537 : inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m)
246 : {
247 4537 : return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m));
248 : }
249 4537 : inline int hash_index_Impl (sal_uInt32 nOffset)
250 : {
251 4537 : 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 : // Delegate multiple inherited IReference
278 : virtual oslInterlockedCount SAL_CALL acquire() SAL_OVERRIDE;
279 : virtual oslInterlockedCount SAL_CALL release() SAL_OVERRIDE;
280 :
281 : protected:
282 : // Destruction
283 : virtual ~PageCache_Impl (void);
284 : };
285 :
286 : } // namespace store
287 :
288 148 : PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize)
289 : : m_hash_table (m_hash_table_0),
290 : m_hash_size (theTableSize),
291 148 : m_hash_shift (highbit(m_hash_size) - 1),
292 148 : m_page_shift (highbit(nPageSize) - 1),
293 : m_hash_entries (0),
294 : m_nHit (0),
295 444 : m_nMissed (0)
296 : {
297 : static size_t const theSize = SAL_N_ELEMENTS(m_hash_table_0);
298 : BOOST_STATIC_ASSERT(theSize == theTableSize);
299 148 : memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
300 148 : }
301 :
302 444 : PageCache_Impl::~PageCache_Impl()
303 : {
304 148 : double s_x = 0.0;
305 148 : sal_Size i, n = m_hash_size;
306 4884 : for (i = 0; i < n; i++)
307 : {
308 4736 : int x = 0;
309 4736 : Entry * entry = m_hash_table[i];
310 10688 : while (entry != 0)
311 : {
312 1216 : m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0;
313 1216 : EntryCache::get().destroy (entry);
314 1216 : entry = m_hash_table[i];
315 1216 : x += 1;
316 : }
317 4736 : s_x += double(x);
318 : }
319 148 : double ave = s_x / double(n);
320 : OSL_TRACE("ave hash chain length: %g", ave);
321 : (void) ave;
322 :
323 148 : if (m_hash_table != m_hash_table_0)
324 : {
325 0 : rtl_freeMemory (m_hash_table);
326 0 : m_hash_table = m_hash_table_0;
327 0 : m_hash_size = theTableSize;
328 0 : m_hash_shift = highbit(m_hash_size) - 1;
329 : }
330 : OSL_TRACE("Hits: %zu, Misses: %zu", m_nHit, m_nMissed);
331 296 : }
332 :
333 148 : oslInterlockedCount PageCache_Impl::acquire()
334 : {
335 148 : return OStoreObject::acquire();
336 : }
337 :
338 148 : oslInterlockedCount PageCache_Impl::release()
339 : {
340 148 : return OStoreObject::release();
341 : }
342 :
343 0 : void PageCache_Impl::rescale_Impl (sal_Size new_size)
344 : {
345 0 : sal_Size new_bytes = new_size * sizeof(Entry*);
346 0 : Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes));
347 :
348 0 : if (new_table != 0)
349 : {
350 0 : Entry ** old_table = m_hash_table;
351 0 : sal_Size old_size = m_hash_size;
352 :
353 : OSL_TRACE("ave chain length: %zu, total entries: %zu [old_size: %zu new_size: %zu]",
354 : m_hash_entries >> m_hash_shift, m_hash_entries, old_size, new_size);
355 :
356 0 : memset (new_table, 0, new_bytes);
357 :
358 0 : m_hash_table = new_table;
359 0 : m_hash_size = new_size;
360 0 : m_hash_shift = highbit(m_hash_size) - 1;
361 :
362 : sal_Size i;
363 0 : for (i = 0; i < old_size; i++)
364 : {
365 0 : Entry * curr = old_table[i];
366 0 : while (curr != 0)
367 : {
368 0 : Entry * next = curr->m_pNext;
369 0 : int index = hash_index_Impl(curr->m_nOffset);
370 0 : curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr;
371 0 : curr = next;
372 : }
373 0 : old_table[i] = 0;
374 : }
375 0 : if (old_table != m_hash_table_0)
376 : {
377 :
378 0 : rtl_freeMemory (old_table);
379 : }
380 : }
381 0 : }
382 :
383 3301 : Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
384 : {
385 3301 : int lookups = 0;
386 6602 : while (entry != 0)
387 : {
388 1927 : if (entry->m_nOffset == nOffset)
389 1927 : break;
390 :
391 0 : lookups += 1;
392 0 : entry = entry->m_pNext;
393 : }
394 3301 : if (lookups > 2)
395 : {
396 0 : sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
397 0 : for (; ave > 4; new_size *= 2, ave /= 2)
398 0 : continue;
399 0 : if (new_size != m_hash_size)
400 0 : rescale_Impl (new_size);
401 : }
402 3301 : return entry;
403 : }
404 :
405 561 : storeError PageCache_Impl::lookupPageAt_Impl (
406 : PageHolder & rxPage,
407 : sal_uInt32 nOffset)
408 : {
409 561 : int index = hash_index_Impl(nOffset);
410 561 : Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
411 561 : if (entry != 0)
412 : {
413 : // Existing entry.
414 413 : rxPage = entry->m_xPage;
415 :
416 : // Update stats and leave.
417 413 : m_nHit += 1;
418 413 : return store_E_None;
419 : }
420 :
421 : // Cache miss. Update stats and leave.
422 148 : m_nMissed += 1;
423 148 : return store_E_NotExists;
424 : }
425 :
426 1226 : storeError PageCache_Impl::insertPageAt_Impl (
427 : PageHolder const & rxPage,
428 : sal_uInt32 nOffset)
429 : {
430 1226 : Entry * entry = EntryCache::get().create (rxPage, nOffset);
431 1226 : if (entry != 0)
432 : {
433 : // Insert new entry.
434 1226 : int index = hash_index_Impl(nOffset);
435 1226 : entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry;
436 :
437 : // Update stats and leave.
438 1226 : m_hash_entries += 1;
439 1226 : return store_E_None;
440 : }
441 0 : return store_E_OutOfMemory;
442 : }
443 :
444 2740 : storeError PageCache_Impl::updatePageAt_Impl (
445 : PageHolder const & rxPage,
446 : sal_uInt32 nOffset)
447 : {
448 2740 : int index = hash_index_Impl(nOffset);
449 2740 : Entry * entry = lookup_Impl (m_hash_table[index], nOffset);
450 2740 : if (entry != 0)
451 : {
452 : // Update existing entry.
453 1514 : entry->m_xPage = rxPage;
454 :
455 : // Update stats and leave. // m_nUpdHit += 1;
456 1514 : return store_E_None;
457 : }
458 1226 : return insertPageAt_Impl (rxPage, nOffset);
459 : }
460 :
461 10 : storeError PageCache_Impl::removePageAt_Impl (
462 : sal_uInt32 nOffset)
463 : {
464 10 : Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
465 20 : while (*ppEntry != 0)
466 : {
467 10 : if ((*ppEntry)->m_nOffset == nOffset)
468 : {
469 : // Existing entry.
470 10 : Entry * entry = (*ppEntry);
471 :
472 : // Dequeue and destroy entry.
473 10 : (*ppEntry) = entry->m_pNext, entry->m_pNext = 0;
474 10 : EntryCache::get().destroy (entry);
475 :
476 : // Update stats and leave.
477 10 : m_hash_entries -= 1;
478 10 : return store_E_None;
479 : }
480 0 : ppEntry = &((*ppEntry)->m_pNext);
481 : }
482 0 : return store_E_NotExists;
483 : }
484 :
485 : /*
486 : *
487 : * Old OStorePageCache implementation.
488 : *
489 : * (two-way association (sorted address array, LRU chain)).
490 : * (external OStorePageData representation).
491 : *
492 : */
493 :
494 : /*
495 : *
496 : * PageCache factory implementation.
497 : *
498 : */
499 : namespace store {
500 :
501 : storeError
502 148 : PageCache_createInstance (
503 : rtl::Reference< store::PageCache > & rxCache,
504 : sal_uInt16 nPageSize)
505 : {
506 148 : rxCache = new PageCache_Impl (nPageSize);
507 148 : if (!rxCache.is())
508 0 : return store_E_OutOfMemory;
509 :
510 148 : return store_E_None;
511 : }
512 :
513 : } // namespace store
514 :
515 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
