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

KDE's Doxygen guidelines are available online.