13 #include "kshareddatacache.h" 14 #include "kcoreaddons_debug.h" 15 #include "kshareddatacache_p.h" 17 #include <QStandardPaths> 18 #include <qplatformdefs.h> 25 #include <QRandomGenerator> 26 #include <QSharedPointer> 30 #include <sys/types.h> 34 static const uint MAX_PROBE_COUNT = 6;
49 qCCritical(KCOREADDONS_DEBUG) <<
"Error detected in cache, re-generating";
61 static unsigned int MurmurHashAligned(
const void *key,
int len,
unsigned int seed)
63 const unsigned int m = 0xc6a4a793;
66 const unsigned char *data =
reinterpret_cast<const unsigned char *
>(key);
68 unsigned int h = seed ^ (len * m);
70 int align =
reinterpret_cast<quintptr
>(data) & 3;
72 if (align && len >= 4) {
75 unsigned int t = 0, d = 0;
93 int sl = 8 * (4 - align);
99 d = *
reinterpret_cast<const unsigned int *
>(data);
100 t = (t >> sr) | (d << sl);
112 int pack = len < align ? len : align;
127 h += (t >> sr) | (d << sl);
136 h += *
reinterpret_cast<const unsigned int *
>(data);
173 static quint32 generateHash(
const QByteArray &buffer)
177 return MurmurHashAligned(buffer.
data(), buffer.
size(), 0xF0F00F0F);
188 #if defined(Q_CC_GNU) || defined(Q_CC_SUN) 189 #define ALIGNOF(x) (__alignof__(x)) // GCC provides what we want directly 195 struct __alignmentHack {
198 static const size_t size = offsetof(__alignmentHack, obj);
200 #define ALIGNOF(x) (__alignmentHack<x>::size) 202 #endif // ALIGNOF undefined 208 T *alignTo(
const void *start, uint size = ALIGNOF(T))
210 quintptr mask = size - 1;
213 quintptr basePointer =
reinterpret_cast<quintptr
>(start);
217 basePointer = (basePointer + mask) & ~mask;
219 return reinterpret_cast<T *
>(basePointer);
229 const T *offsetAs(
const void *
const base, qint32 offset)
231 const char *ptr =
reinterpret_cast<const char *
>(base);
232 return alignTo<const T>(ptr + offset);
237 T *offsetAs(
void *
const base, qint32 offset)
239 char *ptr =
reinterpret_cast<char *
>(base);
240 return alignTo<T>(ptr + offset);
248 static unsigned intCeil(
unsigned a,
unsigned b)
251 if (Q_UNLIKELY(b == 0 || ((a + b) < a))) {
252 throw KSDCCorrupted();
255 return (a + b - 1) / b;
261 static unsigned countSetBits(
unsigned value)
267 for (count = 0; value != 0; count++) {
268 value &= (value - 1);
273 typedef qint32 pageID;
310 struct IndexTableEntry {
313 mutable uint useCount;
315 mutable time_t lastUsedTime;
320 struct PageTableEntry {
335 struct SharedMemory {
344 PIXMAP_CACHE_VERSION = 12,
345 MINIMUM_CACHE_SIZE = 4096,
374 static unsigned equivalentPageSize(
unsigned itemSize)
381 while ((itemSize >>= 1) != 0) {
387 log2OfSize = qBound(9, log2OfSize, 18);
389 return (1 << log2OfSize);
393 unsigned cachePageSize()
const 395 unsigned _pageSize =
static_cast<unsigned>(pageSize.
loadRelaxed());
397 static const unsigned validSizeMask = 0x7FE00u;
400 if (Q_UNLIKELY(countSetBits(_pageSize) != 1 || (_pageSize & ~validSizeMask))) {
401 throw KSDCCorrupted();
419 bool performInitialSetup(uint _cacheSize, uint _pageSize)
421 if (_cacheSize < MINIMUM_CACHE_SIZE) {
422 qCCritical(KCOREADDONS_DEBUG) <<
"Internal error: Attempted to create a cache sized < " << MINIMUM_CACHE_SIZE;
426 if (_pageSize == 0) {
427 qCCritical(KCOREADDONS_DEBUG) <<
"Internal error: Attempted to create a cache with 0-sized pages.";
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. :(";
438 bool isProcessShared =
false;
441 if (!tempLock->initialize(isProcessShared)) {
442 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to initialize the lock for the cache!";
446 if (!isProcessShared) {
447 qCWarning(KCOREADDONS_DEBUG) <<
"Cache initialized, but does not support being" 448 <<
"shared across processes.";
453 cacheSize = _cacheSize;
454 pageSize = _pageSize;
455 version = PIXMAP_CACHE_VERSION;
456 cacheTimestamp =
static_cast<unsigned>(::time(
nullptr));
458 clearInternalTables();
467 void clearInternalTables()
470 cacheAvail = pageTableSize();
473 PageTableEntry *table = pageTable();
474 for (uint i = 0; i < pageTableSize(); ++i) {
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;
490 const IndexTableEntry *indexTable()
const 494 return offsetAs<IndexTableEntry>(
this,
sizeof(*this));
497 const PageTableEntry *pageTable()
const 499 const IndexTableEntry *base = indexTable();
500 base += indexTableSize();
503 return alignTo<PageTableEntry>(base);
506 const void *cachePages()
const 508 const PageTableEntry *tableStart = pageTable();
509 tableStart += pageTableSize();
512 return alignTo<void>(tableStart, cachePageSize());
515 const void *page(pageID at)
const 517 if (static_cast<uint>(at) >= pageTableSize()) {
522 const char *pageStart =
reinterpret_cast<const char *
>(cachePages());
523 pageStart += (at * cachePageSize());
525 return reinterpret_cast<const void *
>(pageStart);
532 IndexTableEntry *indexTable()
534 const SharedMemory *that =
const_cast<const SharedMemory *
>(
this);
535 return const_cast<IndexTableEntry *
>(that->indexTable());
538 PageTableEntry *pageTable()
540 const SharedMemory *that =
const_cast<const SharedMemory *
>(
this);
541 return const_cast<PageTableEntry *
>(that->pageTable());
546 const SharedMemory *that =
const_cast<const SharedMemory *
>(
this);
547 return const_cast<void *
>(that->cachePages());
550 void *page(pageID at)
552 const SharedMemory *that =
const_cast<const SharedMemory *
>(
this);
553 return const_cast<void *
>(that->page(at));
556 uint pageTableSize()
const 558 return cacheSize / cachePageSize();
561 uint indexTableSize()
const 565 return pageTableSize() / 2;
572 pageID findEmptyPages(uint pagesNeeded)
const 574 if (Q_UNLIKELY(pagesNeeded > pageTableSize())) {
575 return pageTableSize();
580 const PageTableEntry *table = pageTable();
581 uint contiguousPagesFound = 0;
583 for (pageID i = 0; i < static_cast<int>(pageTableSize()); ++i) {
584 if (table[i].index < 0) {
585 if (contiguousPagesFound == 0) {
588 contiguousPagesFound++;
590 contiguousPagesFound = 0;
593 if (contiguousPagesFound == pagesNeeded) {
598 return pageTableSize();
602 static bool lruCompare(
const IndexTableEntry &l,
const IndexTableEntry &r)
605 if (l.firstPage < 0 && r.firstPage >= 0) {
608 if (l.firstPage >= 0 && r.firstPage < 0) {
614 return l.lastUsedTime < r.lastUsedTime;
618 static bool seldomUsedCompare(
const IndexTableEntry &l,
const IndexTableEntry &r)
621 if (l.firstPage < 0 && r.firstPage >= 0) {
624 if (l.firstPage >= 0 && r.firstPage < 0) {
629 return l.useCount < r.useCount;
633 static bool ageCompare(
const IndexTableEntry &l,
const IndexTableEntry &r)
636 if (l.firstPage < 0 && r.firstPage >= 0) {
639 if (l.firstPage >= 0 && r.firstPage < 0) {
645 return l.addTime < r.addTime;
650 if (cacheAvail * cachePageSize() == cacheSize) {
654 qCDebug(KCOREADDONS_DEBUG) <<
"Defragmenting the shared cache";
660 pageID currentPage = 0;
661 pageID idLimit =
static_cast<pageID
>(pageTableSize());
662 PageTableEntry *pages = pageTable();
664 if (Q_UNLIKELY(!pages || idLimit <= 0)) {
665 throw KSDCCorrupted();
669 while (currentPage < idLimit && pages[currentPage].index >= 0) {
673 pageID freeSpot = currentPage;
677 while (currentPage < idLimit) {
679 while (currentPage < idLimit && pages[currentPage].index < 0) {
683 if (currentPage >= idLimit) {
688 qint32 affectedIndex = pages[currentPage].index;
689 if (Q_UNLIKELY(affectedIndex < 0 || affectedIndex >= idLimit || indexTable()[affectedIndex].firstPage != currentPage)) {
690 throw KSDCCorrupted();
693 indexTable()[affectedIndex].firstPage = freeSpot;
697 while (currentPage < idLimit && pages[currentPage].index >= 0) {
698 const void *
const sourcePage = page(currentPage);
699 void *
const destinationPage = page(freeSpot);
703 if (Q_UNLIKELY(!sourcePage || !destinationPage || sourcePage < destinationPage)) {
704 throw KSDCCorrupted();
707 ::memcpy(destinationPage, sourcePage, cachePageSize());
708 pages[freeSpot].index = affectedIndex;
709 pages[currentPage].index = -1;
715 if (currentPage >= idLimit) {
722 if (affectedIndex != pages[currentPage].index) {
723 indexTable()[pages[currentPage].index].firstPage = freeSpot;
725 affectedIndex = pages[currentPage].index;
740 qint32 findNamedEntry(
const QByteArray &key)
const 742 uint keyHash = generateHash(key);
743 uint position = keyHash % indexTableSize();
744 uint probeNumber = 1;
750 while (indexTable()[position].fileNameHash != keyHash && probeNumber < MAX_PROBE_COUNT) {
751 position = (keyHash + (probeNumber + probeNumber * probeNumber) / 2) % indexTableSize();
755 if (indexTable()[position].fileNameHash == keyHash) {
756 pageID
firstPage = indexTable()[position].firstPage;
757 if (firstPage < 0 || static_cast<uint>(firstPage) >= pageTableSize()) {
761 const void *resultPage = page(firstPage);
762 if (Q_UNLIKELY(!resultPage)) {
763 throw KSDCCorrupted();
766 const char *utf8FileName =
reinterpret_cast<const char *
>(resultPage);
767 if (qstrncmp(utf8FileName, key.
constData(), cachePageSize()) == 0) {
776 static void deleteTable(IndexTableEntry *table)
791 uint removeUsedPages(uint numberNeeded)
793 if (numberNeeded == 0) {
794 qCCritical(KCOREADDONS_DEBUG) <<
"Internal error: Asked to remove exactly 0 pages for some reason.";
795 throw KSDCCorrupted();
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();
810 qCDebug(KCOREADDONS_DEBUG) <<
"Removing old entries to free up" << numberNeeded <<
"pages," << cacheAvail <<
"are already theoretically available.";
812 if (cacheAvail > 3 * numberNeeded) {
814 uint result = findEmptyPages(numberNeeded);
816 if (result < pageTableSize()) {
819 qCCritical(KCOREADDONS_DEBUG) <<
"Just defragmented a locked cache, but still there" 820 <<
"isn't enough room for the current request.";
830 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to allocate temporary memory for sorting the cache!";
831 clearInternalTables();
832 throw KSDCCorrupted();
837 IndexTableEntry *table = tablePtr.data();
839 ::memcpy(table, indexTable(),
sizeof(IndexTableEntry) * indexTableSize());
846 for (uint i = 0; i < indexTableSize(); ++i) {
847 table[i].firstPage = table[i].useCount > 0 ?
static_cast<pageID
>(i) : -1;
852 bool (*compareFunction)(
const IndexTableEntry &,
const IndexTableEntry &);
854 case KSharedDataCache::EvictLeastOftenUsed:
855 case KSharedDataCache::NoEvictionPreference:
857 compareFunction = seldomUsedCompare;
860 case KSharedDataCache::EvictLeastRecentlyUsed:
861 compareFunction = lruCompare;
864 case KSharedDataCache::EvictOldest:
865 compareFunction = ageCompare;
869 std::sort(table, table + indexTableSize(), compareFunction);
880 while (i < indexTableSize() && numberNeeded > cacheAvail) {
881 int curIndex = table[i++].firstPage;
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();
889 qCDebug(KCOREADDONS_DEBUG) <<
"Removing entry of" << indexTable()[curIndex].totalItemSize <<
"size";
890 removeEntry(curIndex);
897 pageID result = pageTableSize();
898 while (i < indexTableSize() && (static_cast<uint>(result = findEmptyPages(numberNeeded))) >= pageTableSize()) {
899 int curIndex = table[i++].firstPage;
904 return findEmptyPages(numberNeeded);
907 if (Q_UNLIKELY(static_cast<uint>(curIndex) >= indexTableSize())) {
908 throw KSDCCorrupted();
911 removeEntry(curIndex);
919 static uint totalSize(uint cacheSize, uint effectivePageSize)
921 uint numberPages = intCeil(cacheSize, effectivePageSize);
922 uint indexTableSize = numberPages / 2;
927 IndexTableEntry *indexTableStart = offsetAs<IndexTableEntry>(
static_cast<void *
>(
nullptr),
sizeof(SharedMemory));
929 indexTableStart += indexTableSize;
931 PageTableEntry *pageTableStart =
reinterpret_cast<PageTableEntry *
>(indexTableStart);
932 pageTableStart = alignTo<PageTableEntry>(pageTableStart);
933 pageTableStart += numberPages;
936 char *cacheStart =
reinterpret_cast<char *
>(pageTableStart);
937 cacheStart += (numberPages * effectivePageSize);
940 cacheStart = alignTo<char>(cacheStart, ALIGNOF(
void *));
944 return static_cast<uint
>(
reinterpret_cast<quintptr
>(cacheStart));
947 uint fileNameHash(
const QByteArray &utf8FileName)
const 949 return generateHash(utf8FileName) % indexTableSize();
954 clearInternalTables();
957 void removeEntry(uint index);
965 Private(
const QString &name,
unsigned defaultCacheSize,
unsigned expectedItemSize)
970 , m_defaultCacheSize(defaultCacheSize)
971 , m_expectedItemSize(expectedItemSize)
972 , m_expectedType(LOCKTYPE_INVALID)
981 void detachFromSharedMemory()
987 if (shm && 0 != ::munmap(shm, m_mapSize)) {
988 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to unmap shared memory segment" <<
static_cast<void *
>(shm) <<
":" << ::strerror(errno);
998 void mapSharedMemory()
1001 unsigned cacheSize = qMax(m_defaultCacheSize, uint(SharedMemory::MINIMUM_CACHE_SIZE));
1002 unsigned pageSize = SharedMemory::equivalentPageSize(m_expectedItemSize);
1007 cacheSize = qMax(pageSize * 256, cacheSize);
1012 QFile file(cacheName);
1014 if (!
QDir().
mkpath(fileInfo.absolutePath())) {
1025 uint size = SharedMemory::totalSize(cacheSize, pageSize);
1026 void *mapAddress = MAP_FAILED;
1028 if (size < cacheSize) {
1029 qCCritical(KCOREADDONS_DEBUG) <<
"Asked for a cache size less than requested size somehow -- Logic Error :(";
1036 if (file.open(
QIODevice::ReadWrite) && (file.size() >= size || (file.resize(size) && ensureFileAllocated(file.handle(), size)))) {
1040 mapAddress = QT_MMAP(
nullptr, size, PROT_READ | PROT_WRITE, MAP_SHARED, file.handle(), 0);
1045 if (mapAddress != MAP_FAILED) {
1046 SharedMemory *
mapped =
reinterpret_cast<SharedMemory *
>(mapAddress);
1051 if (mapped->version != SharedMemory::PIXMAP_CACHE_VERSION && mapped->version > 0) {
1052 qCWarning(KCOREADDONS_DEBUG) <<
"Deleting wrong version of cache" << cacheName;
1058 recoverCorruptedCache();
1060 }
else if (mapped->cacheSize > cacheSize) {
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);
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";
1092 mapAddress = QT_MMAP(
nullptr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
1097 if (mapAddress == MAP_FAILED) {
1098 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to allocate shared memory segment for shared data cache" << cacheName <<
"of size" << cacheSize;
1107 shm =
reinterpret_cast<SharedMemory *
>(mapAddress);
1115 uint usecSleepTime = 8;
1116 while (shm->ready.loadRelaxed() != 2) {
1117 if (Q_UNLIKELY(usecSleepTime >= (1 << 21))) {
1119 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to acquire shared lock, is the cache corrupt?";
1122 detachFromSharedMemory();
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.";
1133 detachFromSharedMemory();
1137 usleep(usecSleepTime);
1144 m_expectedType = shm->shmLock.type;
1146 bool isProcessSharingSupported =
false;
1148 if (!m_lock->initialize(isProcessSharingSupported)) {
1149 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to setup shared cache lock, although it worked when created.";
1150 detachFromSharedMemory();
1156 void recoverCorruptedCache()
1160 detachFromSharedMemory();
1174 void verifyProposedMemoryAccess(
const void *base,
unsigned accessLength)
const 1176 quintptr startOfAccess =
reinterpret_cast<quintptr
>(base);
1177 quintptr startOfShm =
reinterpret_cast<quintptr
>(shm);
1179 if (Q_UNLIKELY(startOfAccess < startOfShm)) {
1180 throw KSDCCorrupted();
1183 quintptr endOfShm = startOfShm + m_mapSize;
1184 quintptr endOfAccess = startOfAccess + accessLength;
1188 if (Q_UNLIKELY((endOfShm < startOfShm) || (endOfAccess < startOfAccess) || (endOfAccess > endOfShm))) {
1189 throw KSDCCorrupted();
1195 if (Q_LIKELY(shm && shm->shmLock.type == m_expectedType)) {
1196 return m_lock->lock();
1200 throw KSDCCorrupted();
1219 while (!d->lock() && !isLockedCacheSafe()) {
1220 d->recoverCorruptedCache();
1223 qCWarning(KCOREADDONS_DEBUG) <<
"Lost the connection to shared memory for cache" << d->m_cacheName;
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();
1241 bool isLockedCacheSafe()
const 1244 uint testSize = SharedMemory::totalSize(d->shm->cacheSize, d->shm->cachePageSize());
1246 if (Q_UNLIKELY(d->m_mapSize != testSize)) {
1249 if (Q_UNLIKELY(d->shm->version != SharedMemory::PIXMAP_CACHE_VERSION)) {
1252 switch (d->shm->evictionPolicy.loadRelaxed()) {
1253 case NoEvictionPreference:
1254 case EvictLeastRecentlyUsed:
1255 case EvictLeastOftenUsed:
1266 CacheLocker(
const Private *_d)
1267 : d(const_cast<Private *>(_d))
1269 if (Q_UNLIKELY(!d || !d->shm || !cautiousLock())) {
1281 CacheLocker(
const CacheLocker &) =
delete;
1282 CacheLocker &operator=(
const CacheLocker &) =
delete;
1286 return !d || d->shm ==
nullptr;
1294 uint m_defaultCacheSize;
1295 uint m_expectedItemSize;
1296 SharedLockId m_expectedType;
1300 void SharedMemory::removeEntry(uint index)
1302 if (index >= indexTableSize() || cacheAvail > pageTableSize()) {
1303 throw KSDCCorrupted();
1306 PageTableEntry *pageTableEntries = pageTable();
1307 IndexTableEntry *entriesIndex = indexTable();
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();
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();
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;
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();
1338 void *
const startOfData = page(firstPage);
1341 str.prepend(
" REMOVED: ");
1343 str.prepend(
"ENTRY ");
1345 ::memcpy(startOfData, str.constData(), str.size() + 1);
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;
1362 d =
new Private(cacheName, defaultCacheSize, expectedItemSize);
1363 }
catch (KSDCCorrupted) {
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. :-(";
1377 KSharedDataCache::~KSharedDataCache()
1387 #ifdef KSDC_MSYNC_SUPPORTED 1388 ::msync(d->shm, d->m_mapSize, MS_INVALIDATE | MS_ASYNC);
1390 ::munmap(d->shm, d->m_mapSize);
1402 Private::CacheLocker lock(d);
1403 if (lock.failed()) {
1408 uint keyHash = generateHash(encodedKey);
1409 uint position = keyHash % d->shm->indexTableSize();
1412 IndexTableEntry *indices = d->shm->indexTable();
1419 const static double startCullPoint = 0.5l;
1420 const static double mustCullPoint = 0.96l;
1423 double loadFactor = 1.0 - (1.0l * d->shm->cacheAvail * d->shm->cachePageSize() / d->shm->cacheSize);
1424 bool cullCollisions =
false;
1426 if (Q_UNLIKELY(loadFactor >= mustCullPoint)) {
1427 cullCollisions =
true;
1428 }
else if (loadFactor > startCullPoint) {
1429 const int tripWireValue = RAND_MAX * (loadFactor - startCullPoint) / (mustCullPoint - startCullPoint);
1431 cullCollisions =
true;
1439 uint probeNumber = 1;
1440 while (indices[position].useCount > 0 && probeNumber < MAX_PROBE_COUNT) {
1444 if (Q_UNLIKELY(indices[position].fileNameHash == keyHash)) {
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);
1461 position = (keyHash + (probeNumber + probeNumber * probeNumber) / 2) % d->shm->indexTableSize();
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);
1473 uint fileNameLength = 1 + encodedKey.
length();
1474 uint requiredSize = fileNameLength + data.
size();
1475 uint pagesNeeded = intCeil(requiredSize, d->shm->cachePageSize());
1478 if (pagesNeeded >= d->shm->pageTableSize()) {
1479 qCWarning(KCOREADDONS_DEBUG) << key <<
"is too large to be cached.";
1485 if (pagesNeeded > d->shm->cacheAvail || (firstPage = d->shm->findEmptyPages(pagesNeeded)) >= d->shm->pageTableSize()) {
1487 uint freePagesDesired = 3 * qMax(1u, pagesNeeded / 2);
1489 if (d->shm->cacheAvail > freePagesDesired) {
1492 d->shm->defragment();
1493 firstPage = d->shm->findEmptyPages(pagesNeeded);
1499 d->shm->removeUsedPages(qMin(2 * freePagesDesired, d->shm->pageTableSize()) - d->shm->cacheAvail);
1500 firstPage = d->shm->findEmptyPages(pagesNeeded);
1503 if (firstPage >= d->shm->pageTableSize() || d->shm->cacheAvail < pagesNeeded) {
1504 qCCritical(KCOREADDONS_DEBUG) <<
"Unable to free up memory for" << key;
1510 PageTableEntry *table = d->shm->pageTable();
1511 for (uint i = 0; i < pagesNeeded; ++i) {
1512 table[firstPage + i].index = position;
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;
1524 d->shm->cacheAvail -= pagesNeeded;
1527 void *dataPage = d->shm->page(firstPage);
1528 if (Q_UNLIKELY(!dataPage)) {
1529 throw KSDCCorrupted();
1533 d->verifyProposedMemoryAccess(dataPage, requiredSize);
1536 uchar *startOfPageData =
reinterpret_cast<uchar *
>(dataPage);
1537 ::memcpy(startOfPageData, encodedKey.
constData(), fileNameLength);
1538 ::memcpy(startOfPageData + fileNameLength, data.
constData(), data.
size());
1541 }
catch (KSDCCorrupted) {
1542 d->recoverCorruptedCache();
1550 Private::CacheLocker lock(d);
1551 if (lock.failed()) {
1557 qint32 entry = d->shm->findNamedEntry(encodedKey);
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();
1566 d->verifyProposedMemoryAccess(resultPage, header->totalItemSize);
1569 header->lastUsedTime = ::time(
nullptr);
1573 const char *cacheData =
reinterpret_cast<const char *
>(resultPage);
1574 cacheData += encodedKey.
size();
1578 *destination =
QByteArray(cacheData, header->totalItemSize - encodedKey.
size() - 1);
1583 }
catch (KSDCCorrupted) {
1584 d->recoverCorruptedCache();
1593 Private::CacheLocker lock(d);
1595 if (!lock.failed()) {
1598 }
catch (KSDCCorrupted) {
1599 d->recoverCorruptedCache();
1606 Private::CacheLocker lock(d);
1607 if (lock.failed()) {
1611 return d->shm->findNamedEntry(key.
toUtf8()) >= 0;
1612 }
catch (KSDCCorrupted) {
1613 d->recoverCorruptedCache();
1625 qCDebug(KCOREADDONS_DEBUG) <<
"Removing cache at" << cachePath;
1632 Private::CacheLocker lock(d);
1633 if (lock.failed()) {
1637 return d->shm->cacheSize;
1638 }
catch (KSDCCorrupted) {
1639 d->recoverCorruptedCache();
1647 Private::CacheLocker lock(d);
1648 if (lock.failed()) {
1652 return d->shm->cacheAvail * d->shm->cachePageSize();
1653 }
catch (KSDCCorrupted) {
1654 d->recoverCorruptedCache();
1662 return static_cast<EvictionPolicy
>(d->shm->evictionPolicy.fetchAndAddAcquire(0));
1665 return NoEvictionPreference;
1671 d->shm->evictionPolicy.fetchAndStoreRelease(static_cast<int>(newPolicy));
1678 return static_cast<unsigned>(d->shm->cacheTimestamp.fetchAndAddAcquire(0));
1687 d->shm->cacheTimestamp.fetchAndStoreRelease(static_cast<int>(newTimestamp));
QString writableLocation(QStandardPaths::StandardLocation type)
KIOCORE_EXPORT MkpathJob * mkpath(const QUrl &url, const QUrl &baseUrl=QUrl(), JobFlags flags=DefaultFlags)
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)
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's some other process'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)
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.
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...
QByteArray toUtf8() const const