KCoreAddons

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

KDE's Doxygen guidelines are available online.