32#include <QtCore/QDateTime>
33#include <QtCore/QSharedPointer>
34#include <QtCore/QByteArray>
35#include <QtCore/QFile>
36#include <QtCore/QAtomicInt>
37#include <QtCore/QList>
80 const unsigned int m = 0xc6a4a793;
83 const unsigned char * data =
reinterpret_cast<const unsigned char *
>(key);
85 unsigned int h =
seed ^ (len *
m);
89 if(
align & (len >= 4))
93 unsigned int t = 0, d = 0;
97 case 1:
t |= data[2] << 16;
98 case 2:
t |= data[1] << 8;
114 d = *
reinterpret_cast<const unsigned int *
>(data);
115 t = (
t >>
sr) | (d <<
sl);
133 case 3: d |= data[2] << 16;
134 case 2: d |= data[1] << 8;
135 case 1: d |= data[0];
136 case 0: h += (
t >>
sr) | (d <<
sl);
148 h += *
reinterpret_cast<const unsigned int *
>(data);
162 case 3: h += data[2] << 16;
163 case 2: h += data[1] << 8;
164 case 1: h += data[0];
196#if defined(Q_CC_GNU) || defined(Q_CC_SUN)
197#define ALIGNOF(x) (__alignof__ (x))
203struct __alignmentHack
207 static const size_t size =
offsetof(__alignmentHack, obj);
209#define ALIGNOF(x) (__alignmentHack<x>::size)
240 const char *ptr =
reinterpret_cast<const char*
>(
base);
248 char *ptr =
reinterpret_cast<char *
>(
base);
262 throw KSDCCorrupted();
265 return (
a + b - 1) / b;
277 for (count = 0; value != 0; count++) {
278 value &= (value - 1);
320struct IndexTableEntry
324 mutable uint useCount;
326 mutable time_t lastUsedTime;
357 PIXMAP_CACHE_VERSION = 12,
358 MINIMUM_CACHE_SIZE = 4096
372 QAtomicInt evictionPolicy;
382 QAtomicInt cacheTimestamp;
387 static unsigned equivalentPageSize(
unsigned itemSize)
406 unsigned cachePageSize()
const
408 unsigned _pageSize =
static_cast<unsigned>(pageSize);
414 throw KSDCCorrupted();
435 kError(
ksdcArea()) <<
"Internal error: Attempted to create a cache sized < "
436 << MINIMUM_CACHE_SIZE;
441 kError(
ksdcArea()) <<
"Internal error: Attempted to create a cache with 0-sized pages.";
447 kError(
ksdcArea()) <<
"Unable to find an appropriate lock to guard the shared cache. "
448 <<
"This *should* be essentially impossible. :(";
456 kError(
ksdcArea()) <<
"Unable to initialize the lock for the cache!";
462 <<
"shared across processes.";
469 version = PIXMAP_CACHE_VERSION;
470 cacheTimestamp =
static_cast<unsigned>(::time(0));
472 clearInternalTables();
481 void clearInternalTables()
484 cacheAvail = pageTableSize();
487 PageTableEntry *
table = pageTable();
488 for (uint i = 0; i < pageTableSize(); ++i) {
493 IndexTableEntry *
indices = indexTable();
494 for (uint i = 0; i < indexTableSize(); ++i) {
504 const IndexTableEntry *indexTable()
const
511 const PageTableEntry *pageTable()
const
513 const IndexTableEntry *
base = indexTable();
514 base += indexTableSize();
520 const void *cachePages()
const
522 const PageTableEntry *
tableStart = pageTable();
529 const void *page(
pageID at)
const
531 if (
static_cast<uint
>(at) >= pageTableSize()) {
536 const char *
pageStart =
reinterpret_cast<const char *
>(cachePages());
539 return reinterpret_cast<const void *
>(
pageStart);
546 IndexTableEntry *indexTable()
548 const SharedMemory *
that =
const_cast<const SharedMemory*
>(
this);
549 return const_cast<IndexTableEntry *
>(
that->indexTable());
552 PageTableEntry *pageTable()
554 const SharedMemory *
that =
const_cast<const SharedMemory*
>(
this);
555 return const_cast<PageTableEntry *
>(
that->pageTable());
560 const SharedMemory *
that =
const_cast<const SharedMemory*
>(
this);
561 return const_cast<void *
>(
that->cachePages());
566 const SharedMemory *
that =
const_cast<const SharedMemory*
>(
this);
567 return const_cast<void *
>(
that->page(at));
570 uint pageTableSize()
const
572 return cacheSize / cachePageSize();
575 uint indexTableSize()
const
579 return pageTableSize() / 2;
589 return pageTableSize();
594 const PageTableEntry *
table = pageTable();
598 if (
table[i].index < 0) {
613 return pageTableSize();
617 static bool lruCompare(
const IndexTableEntry &
l,
const IndexTableEntry &
r)
620 if (
l.firstPage < 0 &&
r.firstPage >= 0) {
623 if (
l.firstPage >= 0 &&
r.firstPage < 0) {
629 return l.lastUsedTime <
r.lastUsedTime;
633 static bool seldomUsedCompare(
const IndexTableEntry &
l,
const IndexTableEntry &
r)
636 if (
l.firstPage < 0 &&
r.firstPage >= 0) {
639 if (
l.firstPage >= 0 &&
r.firstPage < 0) {
644 return l.useCount <
r.useCount;
648 static bool ageCompare(
const IndexTableEntry &
l,
const IndexTableEntry &
r)
651 if (
l.firstPage < 0 &&
r.firstPage >= 0) {
654 if (
l.firstPage >= 0 &&
r.firstPage < 0) {
660 return l.addTime <
r.addTime;
665 if (cacheAvail * cachePageSize() == cacheSize) {
677 PageTableEntry *
pages = pageTable();
680 throw KSDCCorrupted();
708 throw KSDCCorrupted();
724 throw KSDCCorrupted();
760 qint32 findNamedEntry(
const QByteArray &key)
const
763 uint position =
keyHash % indexTableSize();
770 while (indexTable()[position].fileNameHash !=
keyHash &&
778 if (indexTable()[position].fileNameHash ==
keyHash) {
779 pageID firstPage = indexTable()[position].firstPage;
780 if (firstPage < 0 ||
static_cast<uint
>(firstPage) >= pageTableSize()) {
786 throw KSDCCorrupted();
799 static void deleteTable(IndexTableEntry *
table) {
816 kError(
ksdcArea()) <<
"Internal error: Asked to remove exactly 0 pages for some reason.";
817 throw KSDCCorrupted();
821 kError(
ksdcArea()) <<
"Internal error: Requested more space than exists in the cache.";
823 throw KSDCCorrupted();
833 << cacheAvail <<
"are already theoretically available.";
839 if (result < pageTableSize()) {
843 kError(
ksdcArea()) <<
"Just defragmented a locked cache, but still there"
844 <<
"isn't enough room for the current request.";
854 kError(
ksdcArea()) <<
"Unable to allocate temporary memory for sorting the cache!";
855 clearInternalTables();
856 throw KSDCCorrupted();
863 ::memcpy(
table, indexTable(),
sizeof(IndexTableEntry) * indexTableSize());
870 for (uint i = 0; i < indexTableSize(); ++i) {
878 switch((
int) evictionPolicy) {
905 while (i < indexTableSize() &&
numberNeeded > cacheAvail) {
911 <<
"out-of-bounds for index table of size" << indexTableSize();
912 throw KSDCCorrupted();
924 pageID result = pageTableSize();
925 while (i < indexTableSize() &&
926 (
static_cast<uint
>(result = findEmptyPages(
numberNeeded))) >= pageTableSize())
937 throw KSDCCorrupted();
984 clearInternalTables();
987 void removeEntry(uint index);
992class KSharedDataCache::Private
1014 void detachFromSharedMemory()
1020 if (shm && 0 !=
::munmap(shm, m_mapSize)) {
1032 void mapSharedMemory()
1035 unsigned cacheSize =
qMax(m_defaultCacheSize, uint(SharedMemory::MINIMUM_CACHE_SIZE));
1036 unsigned pageSize = SharedMemory::equivalentPageSize(m_expectedItemSize);
1041 cacheSize =
qMax(pageSize * 256, cacheSize);
1054 uint size = SharedMemory::totalSize(cacheSize, pageSize);
1057 if (size < cacheSize) {
1058 kError(
ksdcArea()) <<
"Asked for a cache size less than requested size somehow -- Logic Error :(";
1065 if (file.open(QIODevice::ReadWrite) &&
1066 (file.size() >= size ||
1083 if (
mapped->version != SharedMemory::PIXMAP_CACHE_VERSION &&
1092 recoverCorruptedCache();
1095 else if (
mapped->cacheSize > cacheSize) {
1099 cacheSize =
mapped->cacheSize;
1124 kWarning(
ksdcArea()) <<
"Failed to establish shared memory mapping, will fallback"
1125 <<
"to private memory -- memory usage will increase";
1133 kError(
ksdcArea()) <<
"Unable to allocate shared memory segment for shared data cache"
1143 shm =
reinterpret_cast<SharedMemory *
>(
mapAddress);
1152 while (shm->ready != 2) {
1155 kError(
ksdcArea()) <<
"Unable to acquire shared lock, is the cache corrupt?";
1158 detachFromSharedMemory();
1162 if (shm->ready.testAndSetAcquire(0, 1)) {
1163 if (!shm->performInitialSetup(cacheSize, pageSize)) {
1164 kError(
ksdcArea()) <<
"Unable to perform initial setup, this system probably "
1165 "does not really support process-shared pthreads or "
1166 "semaphores, even though it claims otherwise.";
1169 detachFromSharedMemory();
1181 m_expectedType = shm->shmLock.
type;
1186 kError(
ksdcArea()) <<
"Unable to setup shared cache lock, although it worked when created.";
1187 detachFromSharedMemory();
1193 void recoverCorruptedCache()
1197 detachFromSharedMemory();
1211 void verifyProposedMemoryAccess(
const void *
base,
unsigned accessLength)
const
1217 throw KSDCCorrupted();
1229 throw KSDCCorrupted();
1236 return m_lock->lock();
1240 throw KSDCCorrupted();
1250 mutable Private * d;
1259 while (!d->lock() && !isLockedCacheSafe()) {
1260 d->recoverCorruptedCache();
1269 kError(
ksdcArea()) <<
"There is a very serious problem with the KDE data cache"
1270 << d->m_cacheName <<
"giving up trying to access cache.";
1271 d->detachFromSharedMemory();
1282 bool isLockedCacheSafe()
const
1285 uint
testSize = SharedMemory::totalSize(d->shm->cacheSize, d->shm->cachePageSize());
1290 if (
KDE_ISUNLIKELY(d->shm->version != SharedMemory::PIXMAP_CACHE_VERSION)) {
1293 switch (d->shm->evictionPolicy) {
1323 return !d || d->shm == 0;
1331 uint m_defaultCacheSize;
1332 uint m_expectedItemSize;
1337void SharedMemory::removeEntry(uint index)
1339 if (index >= indexTableSize() || cacheAvail > pageTableSize()) {
1340 throw KSDCCorrupted();
1348 if (firstPage < 0 ||
static_cast<quint32>(firstPage) >= pageTableSize()) {
1349 kDebug(
ksdcArea()) <<
"Trying to remove an entry which is already invalid. This "
1350 <<
"cache is likely corrupt.";
1351 throw KSDCCorrupted();
1355 kError(
ksdcArea()) <<
"Removing entry" << index <<
"but the matching data"
1356 <<
"doesn't link back -- cache is corrupt, clearing.";
1357 throw KSDCCorrupted();
1362 for (uint i = firstPage; i < pageTableSize() &&
1371 <<
"when removing entry" << index <<
", instead we removed"
1373 throw KSDCCorrupted();
1381 str.prepend(
" REMOVED: ");
1382 str.prepend(QByteArray::number(index));
1383 str.prepend(
"ENTRY ");
1406 catch(KSDCCorrupted) {
1413 catch(KSDCCorrupted) {
1415 <<
"Even a brand-new cache starts off corrupted, something is"
1416 <<
"seriously wrong. :-(";
1432#ifdef KSDC_MSYNC_SUPPORTED
1447 Private::CacheLocker lock(d);
1448 if (lock.failed()) {
1454 uint position =
keyHash % d->shm->indexTableSize();
1457 IndexTableEntry *
indices = d->shm->indexTable();
1468 double loadFactor = 1.0 - (1.0l * d->shm->cacheAvail * d->shm->cachePageSize()
1469 / d->shm->cacheSize);
1500 indices[position].useCount >>= 1;
1501 if (
indices[position].useCount == 0) {
1502 kDebug(
ksdcArea()) <<
"Overwriting existing old cached entry due to collision.";
1503 d->shm->removeEntry(position);
1510 % d->shm->indexTableSize();
1514 if (
indices[position].useCount > 0 &&
indices[position].firstPage >= 0) {
1515 kDebug(
ksdcArea()) <<
"Overwriting existing cached entry due to collision.";
1516 d->shm->removeEntry(position);
1525 uint firstPage = (uint) -1;
1535 (firstPage = d->shm->findEmptyPages(
pagesNeeded)) >= d->shm->pageTableSize())
1543 d->shm->defragment();
1552 - d->shm->cacheAvail);
1556 if (firstPage >= d->shm->pageTableSize() ||
1565 PageTableEntry *
table = d->shm->pageTable();
1567 table[firstPage + i].index = position;
1573 indices[position].useCount = 1;
1574 indices[position].addTime = ::time(0);
1576 indices[position].firstPage = firstPage;
1582 void *
dataPage = d->shm->page(firstPage);
1584 throw KSDCCorrupted();
1597 catch(KSDCCorrupted) {
1598 d->recoverCorruptedCache();
1606 Private::CacheLocker lock(d);
1607 if (lock.failed()) {
1616 const IndexTableEntry *
header = &d->shm->indexTable()[entry];
1619 throw KSDCCorrupted();
1625 header->lastUsedTime = ::time(0);
1640 catch(KSDCCorrupted) {
1641 d->recoverCorruptedCache();
1650 Private::CacheLocker lock(d);
1652 if(!lock.failed()) {
1656 catch(KSDCCorrupted) {
1657 d->recoverCorruptedCache();
1664 Private::CacheLocker lock(d);
1665 if (lock.failed()) {
1669 return d->shm->findNamedEntry(key.toUtf8()) >= 0;
1671 catch(KSDCCorrupted) {
1672 d->recoverCorruptedCache();
1691 Private::CacheLocker lock(d);
1692 if (lock.failed()) {
1696 return d->shm->cacheSize;
1698 catch(KSDCCorrupted) {
1699 d->recoverCorruptedCache();
1707 Private::CacheLocker lock(d);
1708 if (lock.failed()) {
1712 return d->shm->cacheAvail * d->shm->cachePageSize();
1714 catch(KSDCCorrupted) {
1715 d->recoverCorruptedCache();
1723 return static_cast<EvictionPolicy>(d->shm->evictionPolicy.fetchAndAddAcquire(0));
1732 d->shm->evictionPolicy.fetchAndStoreRelease(
static_cast<int>(
newPolicy));
1739 return static_cast<unsigned>(d->shm->cacheTimestamp.fetchAndAddAcquire(0));
1748 d->shm->cacheTimestamp.fetchAndStoreRelease(
static_cast<int>(
newTimestamp));
static int registerArea(const QByteArray &areaName, bool enabled=true)
unsigned freeSize() const
Returns the amount of free space in the cache, in bytes.
static void deleteCache(const QString &cacheName)
Removes the underlying file from the cache.
void clear()
Removes all entries from the cache.
unsigned totalSize() const
Returns the usable cache size in bytes.
void setEvictionPolicy(EvictionPolicy newPolicy)
Sets the entry removal policy for the shared cache to newPolicy.
KSharedDataCache(const QString &cacheName, unsigned defaultCacheSize, unsigned expectedItemSize=0)
Attaches to a shared cache, creating it if necessary.
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 timestamp() const
bool contains(const QString &key) const
Returns true if the cache currently contains the image for the given filename.
EvictionPolicy evictionPolicy() const
void setTimestamp(unsigned newTimestamp)
Sets the shared timestamp of the cache.
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...
static QString locateLocal(const char *type, const QString &filename, const KComponentData &cData=KGlobal::mainComponent())
This function is much like locate.
static QDebug kError(bool cond, int area=KDE_DEFAULT_DEBUG_AREA)
T * alignTo(const void *start, uint size=ALIGNOF(T))
const T * offsetAs(const void *const base, qint32 offset)
Returns a pointer to a const object of type T, assumed to be offset BYTES greater than the base addre...
static unsigned intCeil(unsigned a, unsigned b)
static quint32 generateHash(const QByteArray &buffer)
This is the hash function used for our data to hopefully make the hashing used to place the QByteArra...
static unsigned int MurmurHashAligned(const void *key, int len, unsigned int seed)
static const uint MAX_PROBE_COUNT
The maximum number of probes to make while searching for a bucket in the presence of collisions in th...
static unsigned countSetBits(unsigned value)
static bool ensureFileAllocated(int fd, size_t fileSize)
static SharedLockId findBestSharedLock()
This is a method to determine the best lock type to use for a shared cache, based on local support.
static KSDCLock * createLockFromId(SharedLockId id, SharedLock &lock)
KStandardDirs * dirs()
Returns the application standard dirs object.
int random()
Generates a uniform random number.
#define offsetof(TYPE, MEMBER)