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

KDE's Doxygen guidelines are available online.