File indexing completed on 2024-05-12 03:54:54

 /*
     This file is part of the KDE project.
 
     SPDX-FileCopyrightText: 2010, 2012 Michael Pyne <mpyne@kde.org>
     SPDX-FileCopyrightText: 2012 Ralf Jung <ralfjung-e@gmx.de>
 
     SPDX-License-Identifier: LGPL-2.0-only
 */
 
 #include "kshareddatacache.h"
 #include "kcoreaddons_debug.h"
 #include "ksdcmapping_p.h"
 #include "ksdcmemory_p.h"
 
 #include "kshareddatacache_p.h" // Various auxiliary support code
 
 #include <QByteArray>
 #include <QDir>
 #include <QFile>
 #include <QRandomGenerator>
 #include <QStandardPaths>
 
 // The per-instance private data, such as map size, whether
 // attached or not, pointer to shared memory, etc.
 class Q_DECL_HIDDEN KSharedDataCache::Private
 {
 public:
     Private(const QString &name, unsigned defaultCacheSize, unsigned expectedItemSize)
         : m_cacheName(name)
         , shm(nullptr)
         , m_mapping(nullptr)
         , m_defaultCacheSize(defaultCacheSize)
         , m_expectedItemSize(expectedItemSize)
     {
         createMemoryMapping();
     }
 
     void createMemoryMapping()
     {
         shm = nullptr;
         m_mapping.reset();
 
         // 0-sized caches are fairly useless.
         unsigned cacheSize = qMax(m_defaultCacheSize, uint(SharedMemory::MINIMUM_CACHE_SIZE));
         unsigned pageSize = SharedMemory::equivalentPageSize(m_expectedItemSize);
 
         // Ensure that the cache is sized such that there is a minimum number of
         // pages available. (i.e. a cache consisting of only 1 page is fairly
         // useless and probably crash-prone).
         cacheSize = qMax(pageSize * 256, cacheSize);
 
         // The m_cacheName is used to find the file to store the cache in.
         const QString cacheDir = QStandardPaths::writableLocation(QStandardPaths::GenericCacheLocation);
         QString cacheName = cacheDir + QLatin1String("/") + m_cacheName + QLatin1String(".kcache");
         QFile file(cacheName);
         QFileInfo fileInfo(file);
         if (!QDir().mkpath(fileInfo.absolutePath())) {
             qCWarning(KCOREADDONS_DEBUG) << "Failed to create cache dir" << fileInfo.absolutePath();
         }
 
         // The basic idea is to open the file that we want to map into shared
         // memory, and then actually establish the mapping. Once we have mapped the
         // file into shared memory we can close the file handle, the mapping will
         // still be maintained (unless the file is resized to be shorter than
         // expected, which we don't handle yet :-( )
 
         // size accounts for the overhead over the desired cacheSize
         uint size = SharedMemory::totalSize(cacheSize, pageSize);
         Q_ASSERT(size >= cacheSize);
 
         // Open the file and resize to some sane value if the file is too small.
         if (file.open(QIODevice::ReadWrite) && (file.size() >= size || (ensureFileAllocated(file.handle(), size) && file.resize(size)))) {
             try {
                 m_mapping.reset(new KSDCMapping(&file, size, cacheSize, pageSize));
                 shm = m_mapping->m_mapped;
             } catch (KSDCCorrupted) {
                 shm = nullptr;
                 m_mapping.reset();
 
                 qCWarning(KCOREADDONS_DEBUG) << "Deleting corrupted cache" << cacheName;
                 file.remove();
                 QFile file(cacheName);
                 if (file.open(QIODevice::ReadWrite) && ensureFileAllocated(file.handle(), size) && file.resize(size)) {
                     try {
                         m_mapping.reset(new KSDCMapping(&file, size, cacheSize, pageSize));
                     } catch (KSDCCorrupted) {
                         m_mapping.reset();
                         qCCritical(KCOREADDONS_DEBUG) << "Even a brand-new cache starts off corrupted, something is"
                                                       << "seriously wrong. :-(";
                     }
                 }
             }
         }
 
         if (!m_mapping) {
             m_mapping.reset(new KSDCMapping(nullptr, size, cacheSize, pageSize));
             shm = m_mapping->m_mapped;
         }
     }
 
     // Called whenever the cache is apparently corrupt (for instance, a timeout trying to
     // lock the cache). In this situation it is safer just to destroy it all and try again.
     void recoverCorruptedCache()
     {
         qCWarning(KCOREADDONS_DEBUG) << "Deleting corrupted cache" << m_cacheName;
 
         KSharedDataCache::deleteCache(m_cacheName);
 
         createMemoryMapping();
     }
 
     class CacheLocker
     {
         mutable Private *d;
 
         bool cautiousLock()
         {
             int lockCount = 0;
 
             // Locking can fail due to a timeout. If it happens too often even though
             // we're taking corrective action assume there's some disastrous problem
             // and give up.
             while (!d->m_mapping->lock() && !d->m_mapping->isLockedCacheSafe()) {
                 d->recoverCorruptedCache();
 
                 if (!d->m_mapping->isValid()) {
                     qCWarning(KCOREADDONS_DEBUG) << "Lost the connection to shared memory for cache" << d->m_cacheName;
                     return false;
                 }
 
                 if (lockCount++ > 4) {
                     qCCritical(KCOREADDONS_DEBUG) << "There is a very serious problem with the KDE data cache" << d->m_cacheName
                                                   << "giving up trying to access cache.";
                     return false;
                 }
             }
 
             return true;
         }
 
     public:
         CacheLocker(const Private *_d)
             : d(const_cast<Private *>(_d))
         {
             if (Q_UNLIKELY(!d || !cautiousLock())) {
                 d = nullptr;
             }
         }
 
         ~CacheLocker()
         {
             if (d) {
                 d->m_mapping->unlock();
             }
         }
 
         CacheLocker(const CacheLocker &) = delete;
         CacheLocker &operator=(const CacheLocker &) = delete;
 
         bool failed() const
         {
             return !d;
         }
     };
 
     QString m_cacheName;
     SharedMemory *shm;
     std::unique_ptr<KSDCMapping> m_mapping;
     uint m_defaultCacheSize;
     uint m_expectedItemSize;
 };
 
 KSharedDataCache::KSharedDataCache(const QString &cacheName, unsigned defaultCacheSize, unsigned expectedItemSize)
     : d(nullptr)
 {
     try {
         d = new Private(cacheName, defaultCacheSize, expectedItemSize);
     } catch (KSDCCorrupted) {
         qCCritical(KCOREADDONS_DEBUG) << "Failed to initialize KSharedDataCache!";
         d = nullptr; // Just in case
     }
 }
 
 KSharedDataCache::~KSharedDataCache()
 {
     if (!d) {
         return;
     }
 
     delete d;
 }
 
 bool KSharedDataCache::insert(const QString &key, const QByteArray &data)
 {
     try {
         Private::CacheLocker lock(d);
         if (lock.failed()) {
             return false;
         }
 
         QByteArray encodedKey = key.toUtf8();
         uint keyHash = SharedMemory::generateHash(encodedKey);
         uint position = keyHash % d->shm->indexTableSize();
 
         // See if we're overwriting an existing entry.
         IndexTableEntry *indices = d->shm->indexTable();
 
         // In order to avoid the issue of a very long-lived cache having items
         // with a use count of 1 near-permanently, we attempt to artifically
         // reduce the use count of long-lived items when there is high load on
         // the cache. We do this randomly, with a weighting that makes the event
         // impossible if load < 0.5, and guaranteed if load >= 0.96.
         const static double startCullPoint = 0.5l;
         const static double mustCullPoint = 0.96l;
 
         // cacheAvail is in pages, cacheSize is in bytes.
         double loadFactor = 1.0 - (1.0l * d->shm->cacheAvail * d->shm->cachePageSize() / d->shm->cacheSize);
         bool cullCollisions = false;
 
         if (Q_UNLIKELY(loadFactor >= mustCullPoint)) {
             cullCollisions = true;
         } else if (loadFactor > startCullPoint) {
             const int tripWireValue = RAND_MAX * (loadFactor - startCullPoint) / (mustCullPoint - startCullPoint);
             if (QRandomGenerator::global()->bounded(RAND_MAX) >= tripWireValue) {
                 cullCollisions = true;
             }
         }
 
         // In case of collisions in the index table (i.e. identical positions), use
         // quadratic chaining to attempt to find an empty slot. The equation we use
         // is:
         // position = (hash + (i + i*i) / 2) % size, where i is the probe number.
         uint probeNumber = 1;
         while (indices[position].useCount > 0 && probeNumber < SharedMemory::MAX_PROBE_COUNT) {
             // If we actually stumbled upon an old version of the key we are
             // overwriting, then use that position, do not skip over it.
 
             if (Q_UNLIKELY(indices[position].fileNameHash == keyHash)) {
                 break;
             }
 
             // If we are "culling" old entries, see if this one is old and if so
             // reduce its use count. If it reduces to zero then eliminate it and
             // use its old spot.
 
             if (cullCollisions && (::time(nullptr) - indices[position].lastUsedTime) > 60) {
                 indices[position].useCount >>= 1;
                 if (indices[position].useCount == 0) {
                     qCDebug(KCOREADDONS_DEBUG) << "Overwriting existing old cached entry due to collision.";
                     d->shm->removeEntry(position); // Remove it first
                     break;
                 }
             }
 
             position = (keyHash + (probeNumber + probeNumber * probeNumber) / 2) % d->shm->indexTableSize();
             probeNumber++;
         }
 
         if (indices[position].useCount > 0 && indices[position].firstPage >= 0) {
             qCDebug(KCOREADDONS_DEBUG) << "Overwriting existing cached entry due to collision.";
             d->shm->removeEntry(position); // Remove it first
         }
 
         // Data will be stored as fileNamefoo\0PNGimagedata.....
         // So total size required is the length of the encoded file name + 1
         // for the trailing null, and then the length of the image data.
         uint fileNameLength = 1 + encodedKey.length();
         uint requiredSize = fileNameLength + data.size();
         uint pagesNeeded = SharedMemory::intCeil(requiredSize, d->shm->cachePageSize());
         uint firstPage(-1);
 
         if (pagesNeeded >= d->shm->pageTableSize()) {
             qCWarning(KCOREADDONS_DEBUG) << key << "is too large to be cached.";
             return false;
         }
 
         // If the cache has no room, or the fragmentation is too great to find
         // the required number of consecutive free pages, take action.
         if (pagesNeeded > d->shm->cacheAvail || (firstPage = d->shm->findEmptyPages(pagesNeeded)) >= d->shm->pageTableSize()) {
             // If we have enough free space just defragment
             uint freePagesDesired = 3 * qMax(1u, pagesNeeded / 2);
 
             if (d->shm->cacheAvail > freePagesDesired) {
                 // TODO: How the hell long does this actually take on real
                 // caches?
                 d->shm->defragment();
                 firstPage = d->shm->findEmptyPages(pagesNeeded);
             } else {
                 // If we already have free pages we don't want to remove a ton
                 // extra. However we can't rely on the return value of
                 // removeUsedPages giving us a good location since we're not
                 // passing in the actual number of pages that we need.
                 d->shm->removeUsedPages(qMin(2 * freePagesDesired, d->shm->pageTableSize()) - d->shm->cacheAvail);
                 firstPage = d->shm->findEmptyPages(pagesNeeded);
             }
 
             if (firstPage >= d->shm->pageTableSize() || d->shm->cacheAvail < pagesNeeded) {
                 qCCritical(KCOREADDONS_DEBUG) << "Unable to free up memory for" << key;
                 return false;
             }
         }
 
         // Update page table
         PageTableEntry *table = d->shm->pageTable();
         for (uint i = 0; i < pagesNeeded; ++i) {
             table[firstPage + i].index = position;
         }
 
         // Update index
         indices[position].fileNameHash = keyHash;
         indices[position].totalItemSize = requiredSize;
         indices[position].useCount = 1;
         indices[position].addTime = ::time(nullptr);
         indices[position].lastUsedTime = indices[position].addTime;
         indices[position].firstPage = firstPage;
 
         // Update cache
         d->shm->cacheAvail -= pagesNeeded;
 
         // Actually move the data in place
         void *dataPage = d->shm->page(firstPage);
         if (Q_UNLIKELY(!dataPage)) {
             throw KSDCCorrupted();
         }
 
         // Verify it will all fit
         d->m_mapping->verifyProposedMemoryAccess(dataPage, requiredSize);
 
         // Cast for byte-sized pointer arithmetic
         uchar *startOfPageData = reinterpret_cast<uchar *>(dataPage);
         ::memcpy(startOfPageData, encodedKey.constData(), fileNameLength);
         ::memcpy(startOfPageData + fileNameLength, data.constData(), data.size());
 
         return true;
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
         return false;
     }
 }
 
 bool KSharedDataCache::find(const QString &key, QByteArray *destination) const
 {
     try {
         Private::CacheLocker lock(d);
         if (lock.failed()) {
             return false;
         }
 
         // Search in the index for our data, hashed by key;
         QByteArray encodedKey = key.toUtf8();
         qint32 entry = d->shm->findNamedEntry(encodedKey);
 
         if (entry >= 0) {
             const IndexTableEntry *header = &d->shm->indexTable()[entry];
             const void *resultPage = d->shm->page(header->firstPage);
             if (Q_UNLIKELY(!resultPage)) {
                 throw KSDCCorrupted();
             }
 
             d->m_mapping->verifyProposedMemoryAccess(resultPage, header->totalItemSize);
 
             header->useCount++;
             header->lastUsedTime = ::time(nullptr);
 
             // Our item is the key followed immediately by the data, so skip
             // past the key.
             const char *cacheData = reinterpret_cast<const char *>(resultPage);
             cacheData += encodedKey.size();
             cacheData++; // Skip trailing null -- now we're pointing to start of data
 
             if (destination) {
                 *destination = QByteArray(cacheData, header->totalItemSize - encodedKey.size() - 1);
             }
 
             return true;
         }
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
     }
 
     return false;
 }
 
 void KSharedDataCache::clear()
 {
     try {
         Private::CacheLocker lock(d);
 
         if (!lock.failed()) {
             d->shm->clear();
         }
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
     }
 }
 
 bool KSharedDataCache::contains(const QString &key) const
 {
     try {
         Private::CacheLocker lock(d);
         if (lock.failed()) {
             return false;
         }
 
         return d->shm->findNamedEntry(key.toUtf8()) >= 0;
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
         return false;
     }
 }
 
 void KSharedDataCache::deleteCache(const QString &cacheName)
 {
     QString cachePath = QStandardPaths::writableLocation(QStandardPaths::GenericCacheLocation) + QLatin1String("/") + cacheName + QLatin1String(".kcache");
 
     // Note that it is important to simply unlink the file, and not truncate it
     // smaller first to avoid SIGBUS errors and similar with shared memory
     // attached to the underlying inode.
     qCDebug(KCOREADDONS_DEBUG) << "Removing cache at" << cachePath;
     QFile::remove(cachePath);
 }
 
 unsigned KSharedDataCache::totalSize() const
 {
     try {
         Private::CacheLocker lock(d);
         if (lock.failed()) {
             return 0u;
         }
 
         return d->shm->cacheSize;
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
         return 0u;
     }
 }
 
 unsigned KSharedDataCache::freeSize() const
 {
     try {
         Private::CacheLocker lock(d);
         if (lock.failed()) {
             return 0u;
         }
 
         return d->shm->cacheAvail * d->shm->cachePageSize();
     } catch (KSDCCorrupted) {
         d->recoverCorruptedCache();
         return 0u;
     }
 }
 
 KSharedDataCache::EvictionPolicy KSharedDataCache::evictionPolicy() const
 {
     if (d && d->shm) {
         return static_cast<EvictionPolicy>(d->shm->evictionPolicy.fetchAndAddAcquire(0));
     }
 
     return NoEvictionPreference;
 }
 
 void KSharedDataCache::setEvictionPolicy(EvictionPolicy newPolicy)
 {
     if (d && d->shm) {
         d->shm->evictionPolicy.fetchAndStoreRelease(static_cast<int>(newPolicy));
     }
 }
 
 unsigned KSharedDataCache::timestamp() const
 {
     if (d && d->shm) {
         return static_cast<unsigned>(d->shm->cacheTimestamp.fetchAndAddAcquire(0));
     }
 
     return 0;
 }
 
 void KSharedDataCache::setTimestamp(unsigned newTimestamp)
 {
     if (d && d->shm) {
         d->shm->cacheTimestamp.fetchAndStoreRelease(static_cast<int>(newTimestamp));
     }
 }