• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

KDECore

  • kdecore
  • util
kshareddatacache.cpp
Go to the documentation of this file.
1/*
2 * This file is part of the KDE project.
3 * Copyright © 2010, 2012 Michael Pyne <mpyne@kde.org>
4 * Copyright © 2012 Ralf Jung <ralfjung-e@gmx.de>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License version 2 as published by the Free Software Foundation.
9 *
10 * This library includes "MurmurHash" code from Austin Appleby, which is
11 * placed in the public domain. See http://sites.google.com/site/murmurhash/
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public License
19 * along with this library; see the file COPYING.LIB. If not, write to
20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
22 */
23
24#include "kshareddatacache.h"
25#include "kshareddatacache_p.h" // Various auxiliary support code
26
27#include <kdebug.h>
28#include <kglobal.h>
29#include <kstandarddirs.h>
30#include <krandom.h>
31
32#include <QtCore/QDateTime>
33#include <QtCore/QSharedPointer>
34#include <QtCore/QByteArray>
35#include <QtCore/QFile>
36#include <QtCore/QAtomicInt>
37#include <QtCore/QList>
38
39#include <sys/types.h>
40#include <sys/mman.h>
41#include <stdlib.h>
42
45static const uint MAX_PROBE_COUNT = 6;
46
47int ksdcArea()
48{
49 static int s_ksdcArea = KDebug::registerArea("KSharedDataCache", false);
50 return s_ksdcArea;
51}
52
61class KSDCCorrupted
62{
63 public:
64 KSDCCorrupted()
65 {
66 kError(ksdcArea()) << "Error detected in cache, re-generating";
67 }
68};
69
70//-----------------------------------------------------------------------------
71// MurmurHashAligned, by Austin Appleby
72// (Released to the public domain, or licensed under the MIT license where
73// software may not be released to the public domain. See
74// http://sites.google.com/site/murmurhash/)
75
76// Same algorithm as MurmurHash, but only does aligned reads - should be safer
77// on certain platforms.
78static unsigned int MurmurHashAligned(const void *key, int len, unsigned int seed)
79{
80 const unsigned int m = 0xc6a4a793;
81 const int r = 16;
82
83 const unsigned char * data = reinterpret_cast<const unsigned char *>(key);
84
85 unsigned int h = seed ^ (len * m);
86
87 int align = reinterpret_cast<quintptr>(data) & 3;
88
89 if(align & (len >= 4))
90 {
91 // Pre-load the temp registers
92
93 unsigned int t = 0, d = 0;
94
95 switch(align)
96 {
97 case 1: t |= data[2] << 16;
98 case 2: t |= data[1] << 8;
99 case 3: t |= data[0];
100 }
101
102 t <<= (8 * align);
103
104 data += 4-align;
105 len -= 4-align;
106
107 int sl = 8 * (4-align);
108 int sr = 8 * align;
109
110 // Mix
111
112 while(len >= 4)
113 {
114 d = *reinterpret_cast<const unsigned int *>(data);
115 t = (t >> sr) | (d << sl);
116 h += t;
117 h *= m;
118 h ^= h >> r;
119 t = d;
120
121 data += 4;
122 len -= 4;
123 }
124
125 // Handle leftover data in temp registers
126
127 int pack = len < align ? len : align;
128
129 d = 0;
130
131 switch(pack)
132 {
133 case 3: d |= data[2] << 16;
134 case 2: d |= data[1] << 8;
135 case 1: d |= data[0];
136 case 0: h += (t >> sr) | (d << sl);
137 h *= m;
138 h ^= h >> r;
139 }
140
141 data += pack;
142 len -= pack;
143 }
144 else
145 {
146 while(len >= 4)
147 {
148 h += *reinterpret_cast<const unsigned int *>(data);
149 h *= m;
150 h ^= h >> r;
151
152 data += 4;
153 len -= 4;
154 }
155 }
156
157 //----------
158 // Handle tail bytes
159
160 switch(len)
161 {
162 case 3: h += data[2] << 16;
163 case 2: h += data[1] << 8;
164 case 1: h += data[0];
165 h *= m;
166 h ^= h >> r;
167 };
168
169 h *= m;
170 h ^= h >> 10;
171 h *= m;
172 h ^= h >> 17;
173
174 return h;
175}
176
181static quint32 generateHash(const QByteArray &buffer)
182{
183 // The final constant is the "seed" for MurmurHash. Do *not* change it
184 // without incrementing the cache version.
185 return MurmurHashAligned(buffer.data(), buffer.size(), 0xF0F00F0F);
186}
187
188// Alignment concerns become a big deal when we're dealing with shared memory,
189// since trying to access a structure sized at, say 8 bytes at an address that
190// is not evenly divisible by 8 is a crash-inducing error on some
191// architectures. The compiler would normally take care of this, but with
192// shared memory the compiler will not necessarily know the alignment expected,
193// so make sure we account for this ourselves. To do so we need a way to find
194// out the expected alignment. Enter ALIGNOF...
195#ifndef ALIGNOF
196#if defined(Q_CC_GNU) || defined(Q_CC_SUN)
197#define ALIGNOF(x) (__alignof__ (x)) // GCC provides what we want directly
198#else
199
200#include <stddef.h> // offsetof
201
202template<class T>
203struct __alignmentHack
204{
205 char firstEntry;
206 T obj;
207 static const size_t size = offsetof(__alignmentHack, obj);
208};
209#define ALIGNOF(x) (__alignmentHack<x>::size)
210#endif // Non gcc
211#endif // ALIGNOF undefined
212
213// Returns a pointer properly aligned to handle size alignment.
214// size should be a power of 2. start is assumed to be the lowest
215// permissible address, therefore the return value will be >= start.
216template<class T>
217T* alignTo(const void *start, uint size = ALIGNOF(T))
218{
219 quintptr mask = size - 1;
220
221 // Cast to int-type to handle bit-twiddling
222 quintptr basePointer = reinterpret_cast<quintptr>(start);
223
224 // If (and only if) we are already aligned, adding mask into basePointer
225 // will not increment any of the bits in ~mask and we get the right answer.
226 basePointer = (basePointer + mask) & ~mask;
227
228 return reinterpret_cast<T *>(basePointer);
229}
230
237template<class T>
238const T *offsetAs(const void *const base, qint32 offset)
239{
240 const char *ptr = reinterpret_cast<const char*>(base);
241 return alignTo<const T>(ptr + offset);
242}
243
244// Same as above, but for non-const objects
245template<class T>
246T *offsetAs(void *const base, qint32 offset)
247{
248 char *ptr = reinterpret_cast<char *>(base);
249 return alignTo<T>(ptr + offset);
250}
251
257static unsigned intCeil(unsigned a, unsigned b)
258{
259 // The overflow check is unsigned and so is actually defined behavior.
260 if (KDE_ISUNLIKELY(b == 0 || ((a + b) < a)))
261 {
262 throw KSDCCorrupted();
263 }
264
265 return (a + b - 1) / b;
266}
267
271static unsigned countSetBits(unsigned value)
272{
273 // K&R / Wegner's algorithm used. GCC supports __builtin_popcount but we
274 // expect there to always be only 1 bit set so this should be perhaps a bit
275 // faster 99.9% of the time.
276 unsigned count = 0;
277 for (count = 0; value != 0; count++) {
278 value &= (value - 1); // Clears least-significant set bit.
279 }
280 return count;
281}
282
283typedef qint32 pageID;
284
285// =========================================================================
286// Description of the cache:
287//
288// The shared memory cache is designed to be handled as two separate objects,
289// all contained in the same global memory segment. First off, there is the
290// basic header data, consisting of the global header followed by the
291// accounting data necessary to hold items (described in more detail
292// momentarily). Following the accounting data is the start of the "page table"
293// (essentially just as you'd see it in an Operating Systems text).
294//
295// The page table contains shared memory split into fixed-size pages, with a
296// configurable page size. In the event that the data is too large to fit into
297// a single logical page, it will need to occupy consecutive pages of memory.
298//
299// The accounting data that was referenced earlier is split into two:
300//
301// 1. index table, containing a fixed-size list of possible cache entries.
302// Each index entry is of type IndexTableEntry (below), and holds the various
303// accounting data and a pointer to the first page.
304//
305// 2. page table, which is used to speed up the process of searching for
306// free pages of memory. There is one entry for every page in the page table,
307// and it contains the index of the one entry in the index table actually
308// holding the page (or <0 if the page is free).
309//
310// The entire segment looks like so:
311// ?════════?═════════════?════════════?═══════?═══════?═══════?═══════?═══?
312// ? Header │ Index Table │ Page Table ? Pages │ │ │ │...?
313// ?════════?═════════════?════════════?═══════?═══════?═══════?═══════?═══?
314// =========================================================================
315
316// All elements of this struct must be "plain old data" (POD) types since it
317// will be in shared memory. In addition, no pointers! To point to something
318// you must use relative offsets since the pointer start addresses will be
319// different in each process.
320struct IndexTableEntry
321{
322 uint fileNameHash;
323 uint totalItemSize; // in bytes
324 mutable uint useCount;
325 time_t addTime;
326 mutable time_t lastUsedTime;
327 pageID firstPage;
328};
329
330// Page table entry
331struct PageTableEntry
332{
333 // int so we can use values <0 for unassigned pages.
334 qint32 index;
335};
336
337// Each individual page contains the cached data. The first page starts off with
338// the utf8-encoded key, a null '\0', and then the data follows immediately
339// from the next byte, possibly crossing consecutive page boundaries to hold
340// all of the data.
341// There is, however, no specific struct for a page, it is simply a location in
342// memory.
343
344// This is effectively the layout of the shared memory segment. The variables
345// contained within form the header, data contained afterwards is pointed to
346// by using special accessor functions.
347struct SharedMemory
348{
356 enum {
357 PIXMAP_CACHE_VERSION = 12,
358 MINIMUM_CACHE_SIZE = 4096
359 };
360
361 // Note to those who follow me. You should not, under any circumstances, ever
362 // re-arrange the following two fields, even if you change the version number
363 // for later revisions of this code.
364 QAtomicInt ready;
365 quint8 version;
366
367 // See kshareddatacache_p.h
368 SharedLock shmLock;
369
370 uint cacheSize;
371 uint cacheAvail;
372 QAtomicInt evictionPolicy;
373
374 // pageSize and cacheSize determine the number of pages. The number of
375 // pages determine the page table size and (indirectly) the index table
376 // size.
377 QAtomicInt pageSize;
378
379 // This variable is added to reserve space for later cache timestamping
380 // support. The idea is this variable will be updated when the cache is
381 // written to, to allow clients to detect a changed cache quickly.
382 QAtomicInt cacheTimestamp;
383
387 static unsigned equivalentPageSize(unsigned itemSize)
388 {
389 if (itemSize == 0) {
390 return 4096; // Default average item size.
391 }
392
393 int log2OfSize = 0;
394 while ((itemSize >>= 1) != 0) {
395 log2OfSize++;
396 }
397
398 // Bound page size between 512 bytes and 256 KiB.
399 // If this is adjusted, also alter validSizeMask in cachePageSize
400 log2OfSize = qBound(9, log2OfSize, 18);
401
402 return (1 << log2OfSize);
403 }
404
405 // Returns pageSize in unsigned format.
406 unsigned cachePageSize() const
407 {
408 unsigned _pageSize = static_cast<unsigned>(pageSize);
409 // bits 9-18 may be set.
410 static const unsigned validSizeMask = 0x7FE00u;
411
412 // Check for page sizes that are not a power-of-2, or are too low/high.
413 if (KDE_ISUNLIKELY(countSetBits(_pageSize) != 1 || (_pageSize & ~validSizeMask))) {
414 throw KSDCCorrupted();
415 }
416
417 return _pageSize;
418 }
419
432 bool performInitialSetup(uint _cacheSize, uint _pageSize)
433 {
434 if (_cacheSize < MINIMUM_CACHE_SIZE) {
435 kError(ksdcArea()) << "Internal error: Attempted to create a cache sized < "
436 << MINIMUM_CACHE_SIZE;
437 return false;
438 }
439
440 if (_pageSize == 0) {
441 kError(ksdcArea()) << "Internal error: Attempted to create a cache with 0-sized pages.";
442 return false;
443 }
444
445 shmLock.type = findBestSharedLock();
446 if (shmLock.type == LOCKTYPE_INVALID) {
447 kError(ksdcArea()) << "Unable to find an appropriate lock to guard the shared cache. "
448 << "This *should* be essentially impossible. :(";
449 return false;
450 }
451
452 bool isProcessShared = false;
453 QSharedPointer<KSDCLock> tempLock(createLockFromId(shmLock.type, shmLock));
454
455 if (!tempLock->initialize(isProcessShared)) {
456 kError(ksdcArea()) << "Unable to initialize the lock for the cache!";
457 return false;
458 }
459
460 if (!isProcessShared) {
461 kWarning(ksdcArea()) << "Cache initialized, but does not support being"
462 << "shared across processes.";
463 }
464
465 // These must be updated to make some of our auxiliary functions
466 // work right since their values will be based on the cache size.
467 cacheSize = _cacheSize;
468 pageSize = _pageSize;
469 version = PIXMAP_CACHE_VERSION;
470 cacheTimestamp = static_cast<unsigned>(::time(0));
471
472 clearInternalTables();
473
474 // Unlock the mini-lock, and introduce a total memory barrier to make
475 // sure all changes have propagated even without a mutex.
476 ready.ref();
477
478 return true;
479 }
480
481 void clearInternalTables()
482 {
483 // Assumes we're already locked somehow.
484 cacheAvail = pageTableSize();
485
486 // Setup page tables to point nowhere
487 PageTableEntry *table = pageTable();
488 for (uint i = 0; i < pageTableSize(); ++i) {
489 table[i].index = -1;
490 }
491
492 // Setup index tables to be accurate.
493 IndexTableEntry *indices = indexTable();
494 for (uint i = 0; i < indexTableSize(); ++i) {
495 indices[i].firstPage = -1;
496 indices[i].useCount = 0;
497 indices[i].fileNameHash = 0;
498 indices[i].totalItemSize = 0;
499 indices[i].addTime = 0;
500 indices[i].lastUsedTime = 0;
501 }
502 }
503
504 const IndexTableEntry *indexTable() const
505 {
506 // Index Table goes immediately after this struct, at the first byte
507 // where alignment constraints are met (accounted for by offsetAs).
508 return offsetAs<IndexTableEntry>(this, sizeof(*this));
509 }
510
511 const PageTableEntry *pageTable() const
512 {
513 const IndexTableEntry *base = indexTable();
514 base += indexTableSize();
515
516 // Let's call wherever we end up the start of the page table...
517 return alignTo<PageTableEntry>(base);
518 }
519
520 const void *cachePages() const
521 {
522 const PageTableEntry *tableStart = pageTable();
523 tableStart += pageTableSize();
524
525 // Let's call wherever we end up the start of the data...
526 return alignTo<void>(tableStart, cachePageSize());
527 }
528
529 const void *page(pageID at) const
530 {
531 if (static_cast<uint>(at) >= pageTableSize()) {
532 return 0;
533 }
534
535 // We must manually calculate this one since pageSize varies.
536 const char *pageStart = reinterpret_cast<const char *>(cachePages());
537 pageStart += (at * cachePageSize());
538
539 return reinterpret_cast<const void *>(pageStart);
540 }
541
542 // The following are non-const versions of some of the methods defined
543 // above. They use const_cast<> because I feel that is better than
544 // duplicating the code. I suppose template member functions (?)
545 // may work, may investigate later.
546 IndexTableEntry *indexTable()
547 {
548 const SharedMemory *that = const_cast<const SharedMemory*>(this);
549 return const_cast<IndexTableEntry *>(that->indexTable());
550 }
551
552 PageTableEntry *pageTable()
553 {
554 const SharedMemory *that = const_cast<const SharedMemory*>(this);
555 return const_cast<PageTableEntry *>(that->pageTable());
556 }
557
558 void *cachePages()
559 {
560 const SharedMemory *that = const_cast<const SharedMemory*>(this);
561 return const_cast<void *>(that->cachePages());
562 }
563
564 void *page(pageID at)
565 {
566 const SharedMemory *that = const_cast<const SharedMemory*>(this);
567 return const_cast<void *>(that->page(at));
568 }
569
570 uint pageTableSize() const
571 {
572 return cacheSize / cachePageSize();
573 }
574
575 uint indexTableSize() const
576 {
577 // Assume 2 pages on average are needed -> the number of entries
578 // would be half of the number of pages.
579 return pageTableSize() / 2;
580 }
581
586 pageID findEmptyPages(uint pagesNeeded) const
587 {
588 if (KDE_ISUNLIKELY(pagesNeeded > pageTableSize())) {
589 return pageTableSize();
590 }
591
592 // Loop through the page table, find the first empty page, and just
593 // makes sure that there are enough free pages.
594 const PageTableEntry *table = pageTable();
595 uint contiguousPagesFound = 0;
596 pageID base = 0;
597 for (pageID i = 0; i < static_cast<int>(pageTableSize()); ++i) {
598 if (table[i].index < 0) {
599 if (contiguousPagesFound == 0) {
600 base = i;
601 }
602 contiguousPagesFound++;
603 }
604 else {
605 contiguousPagesFound = 0;
606 }
607
608 if (contiguousPagesFound == pagesNeeded) {
609 return base;
610 }
611 }
612
613 return pageTableSize();
614 }
615
616 // left < right?
617 static bool lruCompare(const IndexTableEntry &l, const IndexTableEntry &r)
618 {
619 // Ensure invalid entries migrate to the end
620 if (l.firstPage < 0 && r.firstPage >= 0) {
621 return false;
622 }
623 if (l.firstPage >= 0 && r.firstPage < 0) {
624 return true;
625 }
626
627 // Most recently used will have the highest absolute time =>
628 // least recently used (lowest) should go first => use left < right
629 return l.lastUsedTime < r.lastUsedTime;
630 }
631
632 // left < right?
633 static bool seldomUsedCompare(const IndexTableEntry &l, const IndexTableEntry &r)
634 {
635 // Ensure invalid entries migrate to the end
636 if (l.firstPage < 0 && r.firstPage >= 0) {
637 return false;
638 }
639 if (l.firstPage >= 0 && r.firstPage < 0) {
640 return true;
641 }
642
643 // Put lowest use count at start by using left < right
644 return l.useCount < r.useCount;
645 }
646
647 // left < right?
648 static bool ageCompare(const IndexTableEntry &l, const IndexTableEntry &r)
649 {
650 // Ensure invalid entries migrate to the end
651 if (l.firstPage < 0 && r.firstPage >= 0) {
652 return false;
653 }
654 if (l.firstPage >= 0 && r.firstPage < 0) {
655 return true;
656 }
657
658 // Oldest entries die first -- they have the lowest absolute add time,
659 // so just like the others use left < right
660 return l.addTime < r.addTime;
661 }
662
663 void defragment()
664 {
665 if (cacheAvail * cachePageSize() == cacheSize) {
666 return; // That was easy
667 }
668
669 kDebug(ksdcArea()) << "Defragmenting the shared cache";
670
671 // Just do a linear scan, and anytime there is free space, swap it
672 // with the pages to its right. In order to meet the precondition
673 // we need to skip any used pages first.
674
675 pageID currentPage = 0;
676 pageID idLimit = static_cast<pageID>(pageTableSize());
677 PageTableEntry *pages = pageTable();
678
679 if (KDE_ISUNLIKELY(!pages || idLimit <= 0)) {
680 throw KSDCCorrupted();
681 }
682
683 // Skip used pages
684 while (currentPage < idLimit && pages[currentPage].index >= 0) {
685 ++currentPage;
686 }
687
688 pageID freeSpot = currentPage;
689
690 // Main loop, starting from a free page, skip to the used pages and
691 // move them back.
692 while (currentPage < idLimit) {
693 // Find the next used page
694 while (currentPage < idLimit && pages[currentPage].index < 0) {
695 ++currentPage;
696 }
697
698 if (currentPage >= idLimit) {
699 break;
700 }
701
702 // Found an entry, move it.
703 qint32 affectedIndex = pages[currentPage].index;
704 if (KDE_ISUNLIKELY(affectedIndex < 0 ||
705 affectedIndex >= idLimit ||
706 indexTable()[affectedIndex].firstPage != currentPage))
707 {
708 throw KSDCCorrupted();
709 }
710
711 indexTable()[affectedIndex].firstPage = freeSpot;
712
713 // Moving one page at a time guarantees we can use memcpy safely
714 // (in other words, the source and destination will not overlap).
715 while (currentPage < idLimit && pages[currentPage].index >= 0) {
716 const void *const sourcePage = page(currentPage);
717 void *const destinationPage = page(freeSpot);
718
719 // We always move used pages into previously-found empty spots,
720 // so check ordering as well for logic errors.
721 if(KDE_ISUNLIKELY(!sourcePage || !destinationPage ||
722 sourcePage < destinationPage))
723 {
724 throw KSDCCorrupted();
725 }
726
727 ::memcpy(destinationPage, sourcePage, cachePageSize());
728 pages[freeSpot].index = affectedIndex;
729 pages[currentPage].index = -1;
730 ++currentPage;
731 ++freeSpot;
732
733 // If we've just moved the very last page and it happened to
734 // be at the very end of the cache then we're done.
735 if (currentPage >= idLimit) {
736 break;
737 }
738
739 // We're moving consecutive used pages whether they belong to
740 // our affected entry or not, so detect if we've started moving
741 // the data for a different entry and adjust if necessary.
742 if (affectedIndex != pages[currentPage].index) {
743 indexTable()[pages[currentPage].index].firstPage = freeSpot;
744 }
745 affectedIndex = pages[currentPage].index;
746 }
747
748 // At this point currentPage is on a page that is unused, and the
749 // cycle repeats. However, currentPage is not the first unused
750 // page, freeSpot is, so leave it alone.
751 }
752 }
753
760 qint32 findNamedEntry(const QByteArray &key) const
761 {
762 uint keyHash = generateHash(key);
763 uint position = keyHash % indexTableSize();
764 uint probeNumber = 1; // See insert() for description
765
766 // Imagine 3 entries A, B, C in this logical probing chain. If B is
767 // later removed then we can't find C either. So, we must keep
768 // searching for probeNumber number of tries (or we find the item,
769 // obviously).
770 while (indexTable()[position].fileNameHash != keyHash &&
771 probeNumber < MAX_PROBE_COUNT)
772 {
773 position = (keyHash + (probeNumber + probeNumber * probeNumber) / 2)
774 % indexTableSize();
775 probeNumber++;
776 }
777
778 if (indexTable()[position].fileNameHash == keyHash) {
779 pageID firstPage = indexTable()[position].firstPage;
780 if (firstPage < 0 || static_cast<uint>(firstPage) >= pageTableSize()) {
781 return -1;
782 }
783
784 const void *resultPage = page(firstPage);
785 if (KDE_ISUNLIKELY(!resultPage)) {
786 throw KSDCCorrupted();
787 }
788
789 const char *utf8FileName = reinterpret_cast<const char *>(resultPage);
790 if (qstrncmp(utf8FileName, key.constData(), cachePageSize()) == 0) {
791 return position;
792 }
793 }
794
795 return -1; // Not found, or a different one found.
796 }
797
798 // Function to use with QSharedPointer in removeUsedPages below...
799 static void deleteTable(IndexTableEntry *table) {
800 delete [] table;
801 }
802
813 uint removeUsedPages(uint numberNeeded)
814 {
815 if (numberNeeded == 0) {
816 kError(ksdcArea()) << "Internal error: Asked to remove exactly 0 pages for some reason.";
817 throw KSDCCorrupted();
818 }
819
820 if (numberNeeded > pageTableSize()) {
821 kError(ksdcArea()) << "Internal error: Requested more space than exists in the cache.";
822 kError(ksdcArea()) << numberNeeded << "requested, " << pageTableSize() << "is the total possible.";
823 throw KSDCCorrupted();
824 }
825
826 // If the cache free space is large enough we will defragment first
827 // instead since it's likely we're highly fragmented.
828 // Otherwise, we will (eventually) simply remove entries per the
829 // eviction order set for the cache until there is enough room
830 // available to hold the number of pages we need.
831
832 kDebug(ksdcArea()) << "Removing old entries to free up" << numberNeeded << "pages,"
833 << cacheAvail << "are already theoretically available.";
834
835 if (cacheAvail > 3 * numberNeeded) {
836 defragment();
837 uint result = findEmptyPages(numberNeeded);
838
839 if (result < pageTableSize()) {
840 return result;
841 }
842 else {
843 kError(ksdcArea()) << "Just defragmented a locked cache, but still there"
844 << "isn't enough room for the current request.";
845 }
846 }
847
848 // At this point we know we'll have to free some space up, so sort our
849 // list of entries by whatever the current criteria are and start
850 // killing expired entries.
851 QSharedPointer<IndexTableEntry> tablePtr(new IndexTableEntry[indexTableSize()], deleteTable);
852
853 if (!tablePtr) {
854 kError(ksdcArea()) << "Unable to allocate temporary memory for sorting the cache!";
855 clearInternalTables();
856 throw KSDCCorrupted();
857 }
858
859 // We use tablePtr to ensure the data is destroyed, but do the access
860 // via a helper pointer to allow for array ops.
861 IndexTableEntry *table = tablePtr.data();
862
863 ::memcpy(table, indexTable(), sizeof(IndexTableEntry) * indexTableSize());
864
865 // Our entry ID is simply its index into the
866 // index table, which qSort will rearrange all willy-nilly, so first
867 // we'll save the *real* entry ID into firstPage (which is useless in
868 // our copy of the index table). On the other hand if the entry is not
869 // used then we note that with -1.
870 for (uint i = 0; i < indexTableSize(); ++i) {
871 table[i].firstPage = table[i].useCount > 0 ? static_cast<pageID>(i)
872 : -1;
873 }
874
875 // Declare the comparison function that we'll use to pass to qSort,
876 // based on our cache eviction policy.
877 bool (*compareFunction)(const IndexTableEntry &, const IndexTableEntry &);
878 switch((int) evictionPolicy) {
879 case (int) KSharedDataCache::EvictLeastOftenUsed:
880 case (int) KSharedDataCache::NoEvictionPreference:
881 default:
882 compareFunction = seldomUsedCompare;
883 break;
884
885 case (int) KSharedDataCache::EvictLeastRecentlyUsed:
886 compareFunction = lruCompare;
887 break;
888
889 case (int) KSharedDataCache::EvictOldest:
890 compareFunction = ageCompare;
891 break;
892 }
893
894 qSort(table, table + indexTableSize(), compareFunction);
895
896 // Least recently used entries will be in the front.
897 // Start killing until we have room.
898
899 // Note on removeEntry: It expects an index into the index table,
900 // but our sorted list is all jumbled. But we stored the real index
901 // in the firstPage member.
902 // Remove entries until we've removed at least the required number
903 // of pages.
904 uint i = 0;
905 while (i < indexTableSize() && numberNeeded > cacheAvail) {
906 int curIndex = table[i++].firstPage; // Really an index, not a page
907
908 // Removed everything, still no luck (or curIndex is set but too high).
909 if (curIndex < 0 || static_cast<uint>(curIndex) >= indexTableSize()) {
910 kError(ksdcArea()) << "Trying to remove index" << curIndex
911 << "out-of-bounds for index table of size" << indexTableSize();
912 throw KSDCCorrupted();
913 }
914
915 kDebug(ksdcArea()) << "Removing entry of" << indexTable()[curIndex].totalItemSize
916 << "size";
917 removeEntry(curIndex);
918 }
919
920 // At this point let's see if we have freed up enough data by
921 // defragmenting first and seeing if we can find that free space.
922 defragment();
923
924 pageID result = pageTableSize();
925 while (i < indexTableSize() &&
926 (static_cast<uint>(result = findEmptyPages(numberNeeded))) >= pageTableSize())
927 {
928 int curIndex = table[i++].firstPage;
929
930 if (curIndex < 0) {
931 // One last shot.
932 defragment();
933 return findEmptyPages(numberNeeded);
934 }
935
936 if (KDE_ISUNLIKELY(static_cast<uint>(curIndex) >= indexTableSize())) {
937 throw KSDCCorrupted();
938 }
939
940 removeEntry(curIndex);
941 }
942
943 // Whew.
944 return result;
945 }
946
947 // Returns the total size required for a given cache size.
948 static uint totalSize(uint cacheSize, uint effectivePageSize)
949 {
950 uint numberPages = intCeil(cacheSize, effectivePageSize);
951 uint indexTableSize = numberPages / 2;
952
953 // Knowing the number of pages, we can determine what addresses we'd be
954 // using (properly aligned), and from there determine how much memory
955 // we'd use.
956 IndexTableEntry *indexTableStart =
957 offsetAs<IndexTableEntry>(static_cast<void*>(0), sizeof (SharedMemory));
958
959 indexTableStart += indexTableSize;
960
961 PageTableEntry *pageTableStart = reinterpret_cast<PageTableEntry *>(indexTableStart);
962 pageTableStart = alignTo<PageTableEntry>(pageTableStart);
963 pageTableStart += numberPages;
964
965 // The weird part, we must manually adjust the pointer based on the page size.
966 char *cacheStart = reinterpret_cast<char *>(pageTableStart);
967 cacheStart += (numberPages * effectivePageSize);
968
969 // ALIGNOF gives pointer alignment
970 cacheStart = alignTo<char>(cacheStart, ALIGNOF(void*));
971
972 // We've traversed the header, index, page table, and cache.
973 // Wherever we're at now is the size of the enchilada.
974 return static_cast<uint>(reinterpret_cast<quintptr>(cacheStart));
975 }
976
977 uint fileNameHash(const QByteArray &utf8FileName) const
978 {
979 return generateHash(utf8FileName) % indexTableSize();
980 }
981
982 void clear()
983 {
984 clearInternalTables();
985 }
986
987 void removeEntry(uint index);
988};
989
990// The per-instance private data, such as map size, whether
991// attached or not, pointer to shared memory, etc.
992class KSharedDataCache::Private
993{
994 public:
995 Private(const QString &name,
996 unsigned defaultCacheSize,
997 unsigned expectedItemSize
998 )
999 : m_cacheName(name)
1000 , shm(0)
1001 , m_lock(0)
1002 , m_mapSize(0)
1003 , m_defaultCacheSize(defaultCacheSize)
1004 , m_expectedItemSize(expectedItemSize)
1005 , m_expectedType(LOCKTYPE_INVALID)
1006 {
1007 mapSharedMemory();
1008 }
1009
1010 // Put the cache in a condition to be able to call mapSharedMemory() by
1011 // completely detaching from shared memory (such as to respond to an
1012 // unrecoverable error).
1013 // m_mapSize must already be set to the amount of memory mapped to shm.
1014 void detachFromSharedMemory()
1015 {
1016 // The lock holds a reference into shared memory, so this must be
1017 // cleared before shm is removed.
1018 m_lock.clear();
1019
1020 if (shm && 0 != ::munmap(shm, m_mapSize)) {
1021 kError(ksdcArea()) << "Unable to unmap shared memory segment"
1022 << static_cast<void*>(shm) << ":" << ::strerror(errno);
1023 }
1024
1025 shm = 0;
1026 m_mapSize = 0;
1027 }
1028
1029 // This function does a lot of the important work, attempting to connect to shared
1030 // memory, a private anonymous mapping if that fails, and failing that, nothing (but
1031 // the cache remains "valid", we just don't actually do anything).
1032 void mapSharedMemory()
1033 {
1034 // 0-sized caches are fairly useless.
1035 unsigned cacheSize = qMax(m_defaultCacheSize, uint(SharedMemory::MINIMUM_CACHE_SIZE));
1036 unsigned pageSize = SharedMemory::equivalentPageSize(m_expectedItemSize);
1037
1038 // Ensure that the cache is sized such that there is a minimum number of
1039 // pages available. (i.e. a cache consisting of only 1 page is fairly
1040 // useless and probably crash-prone).
1041 cacheSize = qMax(pageSize * 256, cacheSize);
1042
1043 // The m_cacheName is used to find the file to store the cache in.
1044 QString cacheName = KGlobal::dirs()->locateLocal("cache", m_cacheName + QLatin1String(".kcache"));
1045 QFile file(cacheName);
1046
1047 // The basic idea is to open the file that we want to map into shared
1048 // memory, and then actually establish the mapping. Once we have mapped the
1049 // file into shared memory we can close the file handle, the mapping will
1050 // still be maintained (unless the file is resized to be shorter than
1051 // expected, which we don't handle yet :-( )
1052
1053 // size accounts for the overhead over the desired cacheSize
1054 uint size = SharedMemory::totalSize(cacheSize, pageSize);
1055 void *mapAddress = MAP_FAILED;
1056
1057 if (size < cacheSize) {
1058 kError(ksdcArea()) << "Asked for a cache size less than requested size somehow -- Logic Error :(";
1059 return;
1060 }
1061
1062 // We establish the shared memory mapping here, only if we will have appropriate
1063 // mutex support (systemSupportsProcessSharing), then we:
1064 // Open the file and resize to some sane value if the file is too small.
1065 if (file.open(QIODevice::ReadWrite) &&
1066 (file.size() >= size ||
1067 (file.resize(size) && ensureFileAllocated(file.handle(), size))))
1068 {
1069 // Use mmap directly instead of QFile::map since the QFile (and its
1070 // shared mapping) will disappear unless we hang onto the QFile for no
1071 // reason (see the note below, we don't care about the file per se...)
1072 mapAddress = ::mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, file.handle(), 0);
1073
1074 // So... it is possible that someone else has mapped this cache already
1075 // with a larger size. If that's the case we need to at least match
1076 // the size to be able to access every entry, so fixup the mapping.
1077 if (mapAddress != MAP_FAILED) {
1078 SharedMemory *mapped = reinterpret_cast<SharedMemory *>(mapAddress);
1079
1080 // First make sure that the version of the cache on disk is
1081 // valid. We also need to check that version != 0 to
1082 // disambiguate against an uninitialized cache.
1083 if (mapped->version != SharedMemory::PIXMAP_CACHE_VERSION &&
1084 mapped->version > 0)
1085 {
1086 kWarning(ksdcArea()) << "Deleting wrong version of cache" << cacheName;
1087
1088 // CAUTION: Potentially recursive since the recovery
1089 // involves calling this function again.
1090 m_mapSize = size;
1091 shm = mapped;
1092 recoverCorruptedCache();
1093 return;
1094 }
1095 else if (mapped->cacheSize > cacheSize) {
1096 // This order is very important. We must save the cache size
1097 // before we remove the mapping, but unmap before overwriting
1098 // the previous mapping size...
1099 cacheSize = mapped->cacheSize;
1100 unsigned actualPageSize = mapped->cachePageSize();
1101 ::munmap(mapAddress, size);
1102 size = SharedMemory::totalSize(cacheSize, actualPageSize);
1103 mapAddress = ::mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, file.handle(), 0);
1104 }
1105 }
1106 }
1107
1108 // We could be here without the mapping established if:
1109 // 1) Process-shared synchronization is not supported, either at compile or run time,
1110 // 2) Unable to open the required file.
1111 // 3) Unable to resize the file to be large enough.
1112 // 4) Establishing the mapping failed.
1113 // 5) The mapping succeeded, but the size was wrong and we were unable to map when
1114 // we tried again.
1115 // 6) The incorrect version of the cache was detected.
1116 // 7) The file could be created, but posix_fallocate failed to commit it fully to disk.
1117 // In any of these cases, attempt to fallback to the
1118 // better-supported anonymous private page style of mmap. This memory won't
1119 // be shared, but our code will still work the same.
1120 // NOTE: We never use the on-disk representation independently of the
1121 // shared memory. If we don't get shared memory the disk info is ignored,
1122 // if we do get shared memory we never look at disk again.
1123 if (mapAddress == MAP_FAILED) {
1124 kWarning(ksdcArea()) << "Failed to establish shared memory mapping, will fallback"
1125 << "to private memory -- memory usage will increase";
1126
1127 mapAddress = ::mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
1128 }
1129
1130 // Well now we're really hosed. We can still work, but we can't even cache
1131 // data.
1132 if (mapAddress == MAP_FAILED) {
1133 kError(ksdcArea()) << "Unable to allocate shared memory segment for shared data cache"
1134 << cacheName << "of size" << cacheSize;
1135 return;
1136 }
1137
1138 m_mapSize = size;
1139
1140 // We never actually construct shm, but we assign it the same address as the
1141 // shared memory we just mapped, so effectively shm is now a SharedMemory that
1142 // happens to be located at mapAddress.
1143 shm = reinterpret_cast<SharedMemory *>(mapAddress);
1144
1145 // If we were first to create this memory map, all data will be 0.
1146 // Therefore if ready == 0 we're not initialized. A fully initialized
1147 // header will have ready == 2. Why?
1148 // Because 0 means "safe to initialize"
1149 // 1 means "in progress of initing"
1150 // 2 means "ready"
1151 uint usecSleepTime = 8; // Start by sleeping for 8 microseconds
1152 while (shm->ready != 2) {
1153 if (KDE_ISUNLIKELY(usecSleepTime >= (1 << 21))) {
1154 // Didn't acquire within ~8 seconds? Assume an issue exists
1155 kError(ksdcArea()) << "Unable to acquire shared lock, is the cache corrupt?";
1156
1157 file.remove(); // Unlink the cache in case it's corrupt.
1158 detachFromSharedMemory();
1159 return; // Fallback to QCache (later)
1160 }
1161
1162 if (shm->ready.testAndSetAcquire(0, 1)) {
1163 if (!shm->performInitialSetup(cacheSize, pageSize)) {
1164 kError(ksdcArea()) << "Unable to perform initial setup, this system probably "
1165 "does not really support process-shared pthreads or "
1166 "semaphores, even though it claims otherwise.";
1167
1168 file.remove();
1169 detachFromSharedMemory();
1170 return;
1171 }
1172 }
1173 else {
1174 usleep(usecSleepTime); // spin
1175
1176 // Exponential fallback as in Ethernet and similar collision resolution methods
1177 usecSleepTime *= 2;
1178 }
1179 }
1180
1181 m_expectedType = shm->shmLock.type;
1182 m_lock = QSharedPointer<KSDCLock>(createLockFromId(m_expectedType, shm->shmLock));
1183 bool isProcessSharingSupported = false;
1184
1185 if (!m_lock->initialize(isProcessSharingSupported)) {
1186 kError(ksdcArea()) << "Unable to setup shared cache lock, although it worked when created.";
1187 detachFromSharedMemory();
1188 }
1189 }
1190
1191 // Called whenever the cache is apparently corrupt (for instance, a timeout trying to
1192 // lock the cache). In this situation it is safer just to destroy it all and try again.
1193 void recoverCorruptedCache()
1194 {
1195 KSharedDataCache::deleteCache(m_cacheName);
1196
1197 detachFromSharedMemory();
1198
1199 // Do this even if we weren't previously cached -- it might work now.
1200 mapSharedMemory();
1201 }
1202
1203 // This should be called for any memory access to shared memory. This
1204 // function will verify that the bytes [base, base+accessLength) are
1205 // actually mapped to d->shm. The cache itself may have incorrect cache
1206 // page sizes, incorrect cache size, etc. so this function should be called
1207 // despite the cache data indicating it should be safe.
1208 //
1209 // If the access is /not/ safe then a KSDCCorrupted exception will be
1210 // thrown, so be ready to catch that.
1211 void verifyProposedMemoryAccess(const void *base, unsigned accessLength) const
1212 {
1213 quintptr startOfAccess = reinterpret_cast<quintptr>(base);
1214 quintptr startOfShm = reinterpret_cast<quintptr>(shm);
1215
1216 if (KDE_ISUNLIKELY(startOfAccess < startOfShm)) {
1217 throw KSDCCorrupted();
1218 }
1219
1220 quintptr endOfShm = startOfShm + m_mapSize;
1221 quintptr endOfAccess = startOfAccess + accessLength;
1222
1223 // Check for unsigned integer wraparound, and then
1224 // bounds access
1225 if (KDE_ISUNLIKELY((endOfShm < startOfShm) ||
1226 (endOfAccess < startOfAccess) ||
1227 (endOfAccess > endOfShm)))
1228 {
1229 throw KSDCCorrupted();
1230 }
1231 }
1232
1233 bool lock() const
1234 {
1235 if (KDE_ISLIKELY(shm && shm->shmLock.type == m_expectedType)) {
1236 return m_lock->lock();
1237 }
1238
1239 // No shm or wrong type --> corrupt!
1240 throw KSDCCorrupted();
1241 }
1242
1243 void unlock() const
1244 {
1245 m_lock->unlock();
1246 }
1247
1248 class CacheLocker
1249 {
1250 mutable Private * d;
1251
1252 bool cautiousLock()
1253 {
1254 int lockCount = 0;
1255
1256 // Locking can fail due to a timeout. If it happens too often even though
1257 // we're taking corrective action assume there's some disastrous problem
1258 // and give up.
1259 while (!d->lock() && !isLockedCacheSafe()) {
1260 d->recoverCorruptedCache();
1261
1262 if (!d->shm) {
1263 kWarning(ksdcArea()) << "Lost the connection to shared memory for cache"
1264 << d->m_cacheName;
1265 return false;
1266 }
1267
1268 if (lockCount++ > 4) {
1269 kError(ksdcArea()) << "There is a very serious problem with the KDE data cache"
1270 << d->m_cacheName << "giving up trying to access cache.";
1271 d->detachFromSharedMemory();
1272 return false;
1273 }
1274 }
1275
1276 return true;
1277 }
1278
1279 // Runs a quick battery of tests on an already-locked cache and returns
1280 // false as soon as a sanity check fails. The cache remains locked in this
1281 // situation.
1282 bool isLockedCacheSafe() const
1283 {
1284 // Note that cachePageSize() itself runs a check that can throw.
1285 uint testSize = SharedMemory::totalSize(d->shm->cacheSize, d->shm->cachePageSize());
1286
1287 if (KDE_ISUNLIKELY(d->m_mapSize != testSize)) {
1288 return false;
1289 }
1290 if (KDE_ISUNLIKELY(d->shm->version != SharedMemory::PIXMAP_CACHE_VERSION)) {
1291 return false;
1292 }
1293 switch (d->shm->evictionPolicy) {
1294 case NoEvictionPreference: // fallthrough
1295 case EvictLeastRecentlyUsed: // fallthrough
1296 case EvictLeastOftenUsed: // fallthrough
1297 case EvictOldest:
1298 break;
1299 default:
1300 return false;
1301 }
1302
1303 return true;
1304 }
1305
1306 public:
1307 CacheLocker(const Private *_d) : d(const_cast<Private *>(_d))
1308 {
1309 if (KDE_ISUNLIKELY(!d || !d->shm || !cautiousLock())) {
1310 d = 0;
1311 }
1312 }
1313
1314 ~CacheLocker()
1315 {
1316 if (d && d->shm) {
1317 d->unlock();
1318 }
1319 }
1320
1321 bool failed() const
1322 {
1323 return !d || d->shm == 0;
1324 }
1325 };
1326
1327 QString m_cacheName;
1328 SharedMemory *shm;
1329 QSharedPointer<KSDCLock> m_lock;
1330 uint m_mapSize;
1331 uint m_defaultCacheSize;
1332 uint m_expectedItemSize;
1333 SharedLockId m_expectedType;
1334};
1335
1336// Must be called while the lock is already held!
1337void SharedMemory::removeEntry(uint index)
1338{
1339 if (index >= indexTableSize() || cacheAvail > pageTableSize()) {
1340 throw KSDCCorrupted();
1341 }
1342
1343 PageTableEntry *pageTableEntries = pageTable();
1344 IndexTableEntry *entriesIndex = indexTable();
1345
1346 // Update page table first
1347 pageID firstPage = entriesIndex[index].firstPage;
1348 if (firstPage < 0 || static_cast<quint32>(firstPage) >= pageTableSize()) {
1349 kDebug(ksdcArea()) << "Trying to remove an entry which is already invalid. This "
1350 << "cache is likely corrupt.";
1351 throw KSDCCorrupted();
1352 }
1353
1354 if (index != static_cast<uint>(pageTableEntries[firstPage].index)) {
1355 kError(ksdcArea()) << "Removing entry" << index << "but the matching data"
1356 << "doesn't link back -- cache is corrupt, clearing.";
1357 throw KSDCCorrupted();
1358 }
1359
1360 uint entriesToRemove = intCeil(entriesIndex[index].totalItemSize, cachePageSize());
1361 uint savedCacheSize = cacheAvail;
1362 for (uint i = firstPage; i < pageTableSize() &&
1363 (uint) pageTableEntries[i].index == index; ++i)
1364 {
1365 pageTableEntries[i].index = -1;
1366 cacheAvail++;
1367 }
1368
1369 if ((cacheAvail - savedCacheSize) != entriesToRemove) {
1370 kError(ksdcArea()) << "We somehow did not remove" << entriesToRemove
1371 << "when removing entry" << index << ", instead we removed"
1372 << (cacheAvail - savedCacheSize);
1373 throw KSDCCorrupted();
1374 }
1375
1376 // For debugging
1377#ifdef NDEBUG
1378 void *const startOfData = page(firstPage);
1379 if (startOfData) {
1380 QByteArray str((const char *) startOfData);
1381 str.prepend(" REMOVED: ");
1382 str.prepend(QByteArray::number(index));
1383 str.prepend("ENTRY ");
1384
1385 ::memcpy(startOfData, str.constData(), str.size() + 1);
1386 }
1387#endif
1388
1389 // Update the index
1390 entriesIndex[index].fileNameHash = 0;
1391 entriesIndex[index].totalItemSize = 0;
1392 entriesIndex[index].useCount = 0;
1393 entriesIndex[index].lastUsedTime = 0;
1394 entriesIndex[index].addTime = 0;
1395 entriesIndex[index].firstPage = -1;
1396}
1397
1398KSharedDataCache::KSharedDataCache(const QString &cacheName,
1399 unsigned defaultCacheSize,
1400 unsigned expectedItemSize)
1401 : d(0)
1402{
1403 try {
1404 d = new Private(cacheName, defaultCacheSize, expectedItemSize);
1405 }
1406 catch(KSDCCorrupted) {
1407 KSharedDataCache::deleteCache(cacheName);
1408
1409 // Try only once more
1410 try {
1411 d = new Private(cacheName, defaultCacheSize, expectedItemSize);
1412 }
1413 catch(KSDCCorrupted) {
1414 kError(ksdcArea())
1415 << "Even a brand-new cache starts off corrupted, something is"
1416 << "seriously wrong. :-(";
1417 d = 0; // Just in case
1418 }
1419 }
1420}
1421
1422KSharedDataCache::~KSharedDataCache()
1423{
1424 // Note that there is no other actions required to separate from the
1425 // shared memory segment, simply unmapping is enough. This makes things
1426 // *much* easier so I'd recommend maintaining this ideal.
1427 if (!d) {
1428 return;
1429 }
1430
1431 if (d->shm) {
1432#ifdef KSDC_MSYNC_SUPPORTED
1433 ::msync(d->shm, d->m_mapSize, MS_INVALIDATE | MS_ASYNC);
1434#endif
1435 ::munmap(d->shm, d->m_mapSize);
1436 }
1437
1438 // Do not delete d->shm, it was never constructed, it's just an alias.
1439 d->shm = 0;
1440
1441 delete d;
1442}
1443
1444bool KSharedDataCache::insert(const QString &key, const QByteArray &data)
1445{
1446 try {
1447 Private::CacheLocker lock(d);
1448 if (lock.failed()) {
1449 return false;
1450 }
1451
1452 QByteArray encodedKey = key.toUtf8();
1453 uint keyHash = generateHash(encodedKey);
1454 uint position = keyHash % d->shm->indexTableSize();
1455
1456 // See if we're overwriting an existing entry.
1457 IndexTableEntry *indices = d->shm->indexTable();
1458
1459 // In order to avoid the issue of a very long-lived cache having items
1460 // with a use count of 1 near-permanently, we attempt to artifically
1461 // reduce the use count of long-lived items when there is high load on
1462 // the cache. We do this randomly, with a weighting that makes the event
1463 // impossible if load < 0.5, and guaranteed if load >= 0.96.
1464 const static double startCullPoint = 0.5l;
1465 const static double mustCullPoint = 0.96l;
1466
1467 // cacheAvail is in pages, cacheSize is in bytes.
1468 double loadFactor = 1.0 - (1.0l * d->shm->cacheAvail * d->shm->cachePageSize()
1469 / d->shm->cacheSize);
1470 bool cullCollisions = false;
1471
1472 if (KDE_ISUNLIKELY(loadFactor >= mustCullPoint)) {
1473 cullCollisions = true;
1474 }
1475 else if (loadFactor > startCullPoint) {
1476 const int tripWireValue = RAND_MAX * (loadFactor - startCullPoint) / (mustCullPoint - startCullPoint);
1477 if (KRandom::random() >= tripWireValue) {
1478 cullCollisions = true;
1479 }
1480 }
1481
1482 // In case of collisions in the index table (i.e. identical positions), use
1483 // quadratic chaining to attempt to find an empty slot. The equation we use
1484 // is:
1485 // position = (hash + (i + i*i) / 2) % size, where i is the probe number.
1486 uint probeNumber = 1;
1487 while (indices[position].useCount > 0 && probeNumber < MAX_PROBE_COUNT) {
1488 // If we actually stumbled upon an old version of the key we are
1489 // overwriting, then use that position, do not skip over it.
1490
1491 if (KDE_ISUNLIKELY(indices[position].fileNameHash == keyHash)) {
1492 break;
1493 }
1494
1495 // If we are "culling" old entries, see if this one is old and if so
1496 // reduce its use count. If it reduces to zero then eliminate it and
1497 // use its old spot.
1498
1499 if (cullCollisions && (::time(0) - indices[position].lastUsedTime) > 60) {
1500 indices[position].useCount >>= 1;
1501 if (indices[position].useCount == 0) {
1502 kDebug(ksdcArea()) << "Overwriting existing old cached entry due to collision.";
1503 d->shm->removeEntry(position); // Remove it first
1504
1505 break;
1506 }
1507 }
1508
1509 position = (keyHash + (probeNumber + probeNumber * probeNumber) / 2)
1510 % d->shm->indexTableSize();
1511 probeNumber++;
1512 }
1513
1514 if (indices[position].useCount > 0 && indices[position].firstPage >= 0) {
1515 kDebug(ksdcArea()) << "Overwriting existing cached entry due to collision.";
1516 d->shm->removeEntry(position); // Remove it first
1517 }
1518
1519 // Data will be stored as fileNamefoo\0PNGimagedata.....
1520 // So total size required is the length of the encoded file name + 1
1521 // for the trailing null, and then the length of the image data.
1522 uint fileNameLength = 1 + encodedKey.length();
1523 uint requiredSize = fileNameLength + data.size();
1524 uint pagesNeeded = intCeil(requiredSize, d->shm->cachePageSize());
1525 uint firstPage = (uint) -1;
1526
1527 if (pagesNeeded >= d->shm->pageTableSize()) {
1528 kWarning(ksdcArea()) << key << "is too large to be cached.";
1529 return false;
1530 }
1531
1532 // If the cache has no room, or the fragmentation is too great to find
1533 // the required number of consecutive free pages, take action.
1534 if (pagesNeeded > d->shm->cacheAvail ||
1535 (firstPage = d->shm->findEmptyPages(pagesNeeded)) >= d->shm->pageTableSize())
1536 {
1537 // If we have enough free space just defragment
1538 uint freePagesDesired = 3 * qMax(1u, pagesNeeded / 2);
1539
1540 if (d->shm->cacheAvail > freePagesDesired) {
1541 // TODO: How the hell long does this actually take on real
1542 // caches?
1543 d->shm->defragment();
1544 firstPage = d->shm->findEmptyPages(pagesNeeded);
1545 }
1546 else {
1547 // If we already have free pages we don't want to remove a ton
1548 // extra. However we can't rely on the return value of
1549 // removeUsedPages giving us a good location since we're not
1550 // passing in the actual number of pages that we need.
1551 d->shm->removeUsedPages(qMin(2 * freePagesDesired, d->shm->pageTableSize())
1552 - d->shm->cacheAvail);
1553 firstPage = d->shm->findEmptyPages(pagesNeeded);
1554 }
1555
1556 if (firstPage >= d->shm->pageTableSize() ||
1557 d->shm->cacheAvail < pagesNeeded)
1558 {
1559 kError(ksdcArea()) << "Unable to free up memory for" << key;
1560 return false;
1561 }
1562 }
1563
1564 // Update page table
1565 PageTableEntry *table = d->shm->pageTable();
1566 for (uint i = 0; i < pagesNeeded; ++i) {
1567 table[firstPage + i].index = position;
1568 }
1569
1570 // Update index
1571 indices[position].fileNameHash = keyHash;
1572 indices[position].totalItemSize = requiredSize;
1573 indices[position].useCount = 1;
1574 indices[position].addTime = ::time(0);
1575 indices[position].lastUsedTime = indices[position].addTime;
1576 indices[position].firstPage = firstPage;
1577
1578 // Update cache
1579 d->shm->cacheAvail -= pagesNeeded;
1580
1581 // Actually move the data in place
1582 void *dataPage = d->shm->page(firstPage);
1583 if (KDE_ISUNLIKELY(!dataPage)) {
1584 throw KSDCCorrupted();
1585 }
1586
1587 // Verify it will all fit
1588 d->verifyProposedMemoryAccess(dataPage, requiredSize);
1589
1590 // Cast for byte-sized pointer arithmetic
1591 uchar *startOfPageData = reinterpret_cast<uchar *>(dataPage);
1592 ::memcpy(startOfPageData, encodedKey.constData(), fileNameLength);
1593 ::memcpy(startOfPageData + fileNameLength, data.constData(), data.size());
1594
1595 return true;
1596 }
1597 catch(KSDCCorrupted) {
1598 d->recoverCorruptedCache();
1599 return false;
1600 }
1601}
1602
1603bool KSharedDataCache::find(const QString &key, QByteArray *destination) const
1604{
1605 try {
1606 Private::CacheLocker lock(d);
1607 if (lock.failed()) {
1608 return false;
1609 }
1610
1611 // Search in the index for our data, hashed by key;
1612 QByteArray encodedKey = key.toUtf8();
1613 qint32 entry = d->shm->findNamedEntry(encodedKey);
1614
1615 if (entry >= 0) {
1616 const IndexTableEntry *header = &d->shm->indexTable()[entry];
1617 const void *resultPage = d->shm->page(header->firstPage);
1618 if (KDE_ISUNLIKELY(!resultPage)) {
1619 throw KSDCCorrupted();
1620 }
1621
1622 d->verifyProposedMemoryAccess(resultPage, header->totalItemSize);
1623
1624 header->useCount++;
1625 header->lastUsedTime = ::time(0);
1626
1627 // Our item is the key followed immediately by the data, so skip
1628 // past the key.
1629 const char *cacheData = reinterpret_cast<const char *>(resultPage);
1630 cacheData += encodedKey.size();
1631 cacheData++; // Skip trailing null -- now we're pointing to start of data
1632
1633 if (destination) {
1634 *destination = QByteArray(cacheData, header->totalItemSize - encodedKey.size() - 1);
1635 }
1636
1637 return true;
1638 }
1639 }
1640 catch(KSDCCorrupted) {
1641 d->recoverCorruptedCache();
1642 }
1643
1644 return false;
1645}
1646
1647void KSharedDataCache::clear()
1648{
1649 try {
1650 Private::CacheLocker lock(d);
1651
1652 if(!lock.failed()) {
1653 d->shm->clear();
1654 }
1655 }
1656 catch(KSDCCorrupted) {
1657 d->recoverCorruptedCache();
1658 }
1659}
1660
1661bool KSharedDataCache::contains(const QString &key) const
1662{
1663 try {
1664 Private::CacheLocker lock(d);
1665 if (lock.failed()) {
1666 return false;
1667 }
1668
1669 return d->shm->findNamedEntry(key.toUtf8()) >= 0;
1670 }
1671 catch(KSDCCorrupted) {
1672 d->recoverCorruptedCache();
1673 return false;
1674 }
1675}
1676
1677void KSharedDataCache::deleteCache(const QString &cacheName)
1678{
1679 QString cachePath = KGlobal::dirs()->locateLocal("cache", cacheName + QLatin1String(".kcache"));
1680
1681 // Note that it is important to simply unlink the file, and not truncate it
1682 // smaller first to avoid SIGBUS errors and similar with shared memory
1683 // attached to the underlying inode.
1684 kDebug(ksdcArea()) << "Removing cache at" << cachePath;
1685 QFile::remove(cachePath);
1686}
1687
1688unsigned KSharedDataCache::totalSize() const
1689{
1690 try {
1691 Private::CacheLocker lock(d);
1692 if (lock.failed()) {
1693 return 0u;
1694 }
1695
1696 return d->shm->cacheSize;
1697 }
1698 catch(KSDCCorrupted) {
1699 d->recoverCorruptedCache();
1700 return 0u;
1701 }
1702}
1703
1704unsigned KSharedDataCache::freeSize() const
1705{
1706 try {
1707 Private::CacheLocker lock(d);
1708 if (lock.failed()) {
1709 return 0u;
1710 }
1711
1712 return d->shm->cacheAvail * d->shm->cachePageSize();
1713 }
1714 catch(KSDCCorrupted) {
1715 d->recoverCorruptedCache();
1716 return 0u;
1717 }
1718}
1719
1720KSharedDataCache::EvictionPolicy KSharedDataCache::evictionPolicy() const
1721{
1722 if (d && d->shm) {
1723 return static_cast<EvictionPolicy>(d->shm->evictionPolicy.fetchAndAddAcquire(0));
1724 }
1725
1726 return NoEvictionPreference;
1727}
1728
1729void KSharedDataCache::setEvictionPolicy(EvictionPolicy newPolicy)
1730{
1731 if (d && d->shm) {
1732 d->shm->evictionPolicy.fetchAndStoreRelease(static_cast<int>(newPolicy));
1733 }
1734}
1735
1736unsigned KSharedDataCache::timestamp() const
1737{
1738 if (d && d->shm) {
1739 return static_cast<unsigned>(d->shm->cacheTimestamp.fetchAndAddAcquire(0));
1740 }
1741
1742 return 0;
1743}
1744
1745void KSharedDataCache::setTimestamp(unsigned newTimestamp)
1746{
1747 if (d && d->shm) {
1748 d->shm->cacheTimestamp.fetchAndStoreRelease(static_cast<int>(newTimestamp));
1749 }
1750}
KDebug::registerArea
static int registerArea(const QByteArray &areaName, bool enabled=true)
Definition: kdebug.cpp:856
KSharedDataCache::EvictionPolicy
EvictionPolicy
Definition: kshareddatacache.h:84
KSharedDataCache::EvictLeastOftenUsed
@ EvictLeastOftenUsed
Definition: kshareddatacache.h:89
KSharedDataCache::NoEvictionPreference
@ NoEvictionPreference
Definition: kshareddatacache.h:87
KSharedDataCache::EvictOldest
@ EvictOldest
Definition: kshareddatacache.h:90
KSharedDataCache::EvictLeastRecentlyUsed
@ EvictLeastRecentlyUsed
Definition: kshareddatacache.h:88
KSharedDataCache::freeSize
unsigned freeSize() const
Returns the amount of free space in the cache, in bytes.
Definition: kshareddatacache.cpp:1704
KSharedDataCache::deleteCache
static void deleteCache(const QString &cacheName)
Removes the underlying file from the cache.
Definition: kshareddatacache.cpp:1677
KSharedDataCache::clear
void clear()
Removes all entries from the cache.
Definition: kshareddatacache.cpp:1647
KSharedDataCache::~KSharedDataCache
~KSharedDataCache()
Definition: kshareddatacache.cpp:1422
KSharedDataCache::totalSize
unsigned totalSize() const
Returns the usable cache size in bytes.
Definition: kshareddatacache.cpp:1688
KSharedDataCache::setEvictionPolicy
void setEvictionPolicy(EvictionPolicy newPolicy)
Sets the entry removal policy for the shared cache to newPolicy.
Definition: kshareddatacache.cpp:1729
KSharedDataCache::KSharedDataCache
KSharedDataCache(const QString &cacheName, unsigned defaultCacheSize, unsigned expectedItemSize=0)
Attaches to a shared cache, creating it if necessary.
Definition: kshareddatacache.cpp:1398
KSharedDataCache::insert
bool insert(const QString &key, const QByteArray &data)
Attempts to insert the entry data into the shared cache, named by key, and returns true only if succe...
Definition: kshareddatacache.cpp:1444
KSharedDataCache::timestamp
unsigned timestamp() const
Definition: kshareddatacache.cpp:1736
KSharedDataCache::contains
bool contains(const QString &key) const
Returns true if the cache currently contains the image for the given filename.
Definition: kshareddatacache.cpp:1661
KSharedDataCache::evictionPolicy
EvictionPolicy evictionPolicy() const
Definition: kshareddatacache.cpp:1720
KSharedDataCache::setTimestamp
void setTimestamp(unsigned newTimestamp)
Sets the shared timestamp of the cache.
Definition: kshareddatacache.cpp:1745
KSharedDataCache::find
bool find(const QString &key, QByteArray *destination) const
Returns the data in the cache named by key (even if it's some other process's data named with the sam...
Definition: kshareddatacache.cpp:1603
KStandardDirs::locateLocal
static QString locateLocal(const char *type, const QString &filename, const KComponentData &cData=KGlobal::mainComponent())
This function is much like locate.
Definition: kstandarddirs.cpp:2097
QString
bool
qint32
quint32
header
const char header[]
Definition: fake/kauth-policy-gen-polkit.cpp:26
kDebug
#define kDebug
Definition: kdebug.h:316
kWarning
#define kWarning
Definition: kdebug.h:322
kError
static QDebug kError(bool cond, int area=KDE_DEFAULT_DEBUG_AREA)
Definition: kdebug.h:187
mask
#define mask
kdebug.h
kglobal.h
krandom.h
alignTo
T * alignTo(const void *start, uint size=ALIGNOF(T))
Definition: kshareddatacache.cpp:217
offsetAs
const T * offsetAs(const void *const base, qint32 offset)
Returns a pointer to a const object of type T, assumed to be offset BYTES greater than the base addre...
Definition: kshareddatacache.cpp:238
intCeil
static unsigned intCeil(unsigned a, unsigned b)
Definition: kshareddatacache.cpp:257
pageID
qint32 pageID
Definition: kshareddatacache.cpp:283
ALIGNOF
#define ALIGNOF(x)
Definition: kshareddatacache.cpp:209
generateHash
static quint32 generateHash(const QByteArray &buffer)
This is the hash function used for our data to hopefully make the hashing used to place the QByteArra...
Definition: kshareddatacache.cpp:181
MurmurHashAligned
static unsigned int MurmurHashAligned(const void *key, int len, unsigned int seed)
Definition: kshareddatacache.cpp:78
MAX_PROBE_COUNT
static const uint MAX_PROBE_COUNT
The maximum number of probes to make while searching for a bucket in the presence of collisions in th...
Definition: kshareddatacache.cpp:45
countSetBits
static unsigned countSetBits(unsigned value)
Definition: kshareddatacache.cpp:271
ksdcArea
int ksdcArea()
Definition: kshareddatacache.cpp:47
kshareddatacache.h
kshareddatacache_p.h
ensureFileAllocated
static bool ensureFileAllocated(int fd, size_t fileSize)
Definition: kshareddatacache_p.h:471
SharedLockId
SharedLockId
Definition: kshareddatacache_p.h:332
LOCKTYPE_INVALID
@ LOCKTYPE_INVALID
Definition: kshareddatacache_p.h:333
findBestSharedLock
static SharedLockId findBestSharedLock()
This is a method to determine the best lock type to use for a shared cache, based on local support.
Definition: kshareddatacache_p.h:368
createLockFromId
static KSDCLock * createLockFromId(SharedLockId id, SharedLock &lock)
Definition: kshareddatacache_p.h:434
kstandarddirs.h
T
#define T
MAP_FAILED
#define MAP_FAILED
Definition: ksycoca.cpp:70
KGlobal::dirs
KStandardDirs * dirs()
Returns the application standard dirs object.
KRandom::random
int random()
Generates a uniform random number.
Definition: krandom.cpp:32
offsetof
#define offsetof(TYPE, MEMBER)
Definition: netsupp.cpp:69
SharedLock
Definition: kshareddatacache_p.h:342
SharedLock::type
SharedLockId type
Definition: kshareddatacache_p.h:360
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Mon Feb 20 2023 00:00:00 by doxygen 1.9.6 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

KDECore

Skip menu "KDECore"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Modules
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal