cache/BlobCache/BlobCache.cpp

/*
 ** Copyright 2011, The Android Open Source Project
 **
 ** Licensed under the Apache License, Version 2.0 (the "License");
 ** you may not use this file except in compliance with the License.
 ** You may obtain a copy of the License at
 **
 **     http://www.apache.org/licenses/LICENSE-2.0
 **
 ** Unless required by applicable law or agreed to in writing, software
 ** distributed under the License is distributed on an "AS IS" BASIS,
 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 ** See the License for the specific language governing permissions and
 ** limitations under the License.
 */

//#define LOG_NDEBUG 0

#include "BlobCache.h"

#include <errno.h>
#include <inttypes.h>

#if defined(__ANDROID__)
#include <cutils/properties.h>
#else
#include <string.h>

#include <algorithm>
static const char property_value[] = "[HOST]";
#define PROPERTY_VALUE_MAX (sizeof(property_value) - 1)
static int property_get(const char* key, char* value, const char* default_value) {
    if (!strcmp(key, "ro.build.id")) {
        memcpy(value, property_value, PROPERTY_VALUE_MAX);
        return PROPERTY_VALUE_MAX;
    }
    if (default_value) {
        const size_t len = std::max(strlen(default_value) + 1, size_t(PROPERTY_VALUE_MAX));
        memcpy(value, default_value, len);
    }
    return 0;
}
#endif

#include <log/log.h>

#include <algorithm>
#include <chrono>
#include <memory>

namespace android {

// BlobCache::Header::mMagicNumber value
static const uint32_t blobCacheMagic = ('_' << 24) + ('B' << 16) + ('b' << 8) + '$';

// BlobCache::Header::mBlobCacheVersion value
static const uint32_t blobCacheVersion = 3;

// BlobCache::Header::mDeviceVersion value
static const uint32_t blobCacheDeviceVersion = 1;

BlobCache::BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize, Policy policy)
    : mMaxKeySize(maxKeySize),
      mMaxValueSize(maxValueSize),
      mMaxTotalSize(maxTotalSize),
      mPolicySelect(policy.first),
      mPolicyCapacity(policy.second),
      mTotalSize(0),
      mAccessCount(0) {
    int64_t now = std::chrono::steady_clock::now().time_since_epoch().count();
#ifdef _WIN32
    srand(now);
#else
    mRandState[0] = (now >> 0) & 0xFFFF;
    mRandState[1] = (now >> 16) & 0xFFFF;
    mRandState[2] = (now >> 32) & 0xFFFF;
#endif
    ALOGV("initializing random seed using %lld", (unsigned long long)now);
}

void BlobCache::set(const void* key, size_t keySize, const void* value, size_t valueSize) {
    if (mMaxKeySize < keySize) {
        ALOGV("set: not caching because the key is too large: %zu (limit: %zu)", keySize,
              mMaxKeySize);
        return;
    }
    if (mMaxValueSize < valueSize) {
        ALOGV("set: not caching because the value is too large: %zu (limit: %zu)", valueSize,
              mMaxValueSize);
        return;
    }
    if (mMaxTotalSize < keySize + valueSize) {
        ALOGV("set: not caching because the combined key/value size is too "
              "large: %zu (limit: %zu)",
              keySize + valueSize, mMaxTotalSize);
        return;
    }
    if (keySize == 0) {
        ALOGW("set: not caching because keySize is 0");
        return;
    }
    if (valueSize <= 0) {
        ALOGW("set: not caching because valueSize is 0");
        return;
    }

    std::shared_ptr<Blob> dummyKey(new Blob(key, keySize, false));
    CacheEntry dummyEntry(dummyKey, NULL, 0);

    while (true) {
        auto index = std::lower_bound(mCacheEntries.begin(), mCacheEntries.end(), dummyEntry);
        if (index == mCacheEntries.end() || dummyEntry < *index) {
            // Create a new cache entry.
            std::shared_ptr<Blob> keyBlob(new Blob(key, keySize, true));
            std::shared_ptr<Blob> valueBlob(new Blob(value, valueSize, true));
            size_t newEntrySize = keySize + valueSize;
            size_t newTotalSize = mTotalSize + newEntrySize;
            if (mMaxTotalSize < newTotalSize) {
                if (isCleanable()) {
                    // Clean the cache and try again.
                    if (!clean(newEntrySize, NoEntry)) {
                        // We have some kind of logic error -- perhaps
                        // an inconsistency between isCleanable() and
                        // findDownTo().
                        ALOGE("set: not caching new key/value pair because "
                              "cleaning failed");
                        break;
                    }
                    continue;
                } else {
                    ALOGV("set: not caching new key/value pair because the "
                          "total cache size limit would be exceeded: %zu "
                          "(limit: %zu)",
                          keySize + valueSize, mMaxTotalSize);
                    break;
                }
            }
            mCacheEntries.insert(index, CacheEntry(keyBlob, valueBlob, ++mAccessCount));
            mTotalSize = newTotalSize;
            ALOGV("set: created new cache entry with %zu byte key and %zu byte value", keySize,
                  valueSize);
        } else {
            // Update the existing cache entry.
            std::shared_ptr<Blob> valueBlob(new Blob(value, valueSize, true));
            std::shared_ptr<Blob> oldValueBlob(index->getValue());
            size_t newTotalSize = mTotalSize + valueSize - oldValueBlob->getSize();
            if (mMaxTotalSize < newTotalSize) {
                if (isCleanable()) {
                    // Clean the cache and try again.
                    if (!clean(index->getKey()->getSize() + valueSize,
                               index - mCacheEntries.begin())) {
                        // We have some kind of logic error -- perhaps
                        // an inconsistency between isCleanable() and
                        // findDownTo().
                        ALOGE("set: not caching new value because "
                              "cleaning failed");
                        break;
                    }
                    continue;
                } else {
                    ALOGV("set: not caching new value because the total cache "
                          "size limit would be exceeded: %zu (limit: %zu)",
                          keySize + valueSize, mMaxTotalSize);
                    break;
                }
            }
            index->setValue(valueBlob);
            index->setRecency(++mAccessCount);
            mTotalSize = newTotalSize;
            ALOGV("set: updated existing cache entry with %zu byte key and %zu byte "
                  "value",
                  keySize, valueSize);
        }
        break;
    }
}

size_t BlobCache::get(const void* key, size_t keySize, void* value, size_t valueSize) {
    void* dummy;
    return get(key, keySize, &dummy, [value, valueSize](size_t allocSize) {
        return (allocSize <= valueSize ? value : nullptr);
    });
}

size_t BlobCache::get(const void* key, size_t keySize, void** value,
                      std::function<void*(size_t)> alloc) {
    if (mMaxKeySize < keySize) {
        ALOGV("get: not searching because the key is too large: %zu (limit %zu)", keySize,
              mMaxKeySize);
        *value = nullptr;
        return 0;
    }
    std::shared_ptr<Blob> dummyKey(new Blob(key, keySize, false));
    CacheEntry dummyEntry(dummyKey, NULL, 0);
    auto index = std::lower_bound(mCacheEntries.begin(), mCacheEntries.end(), dummyEntry);
    if (index == mCacheEntries.end() || dummyEntry < *index) {
        ALOGV("get: no cache entry found for key of size %zu", keySize);
        *value = nullptr;
        return 0;
    }

    // The key was found. Return the value if we can allocate a buffer.
    std::shared_ptr<Blob> valueBlob(index->getValue());
    size_t valueBlobSize = valueBlob->getSize();
    void* buf = alloc(valueBlobSize);
    if (buf != nullptr) {
        ALOGV("get: copying %zu bytes to caller's buffer", valueBlobSize);
        memcpy(buf, valueBlob->getData(), valueBlobSize);
        *value = buf;
        index->setRecency(++mAccessCount);
    } else {
        ALOGV("get: cannot allocate caller's buffer: needs %zu", valueBlobSize);
        *value = nullptr;
    }
    return valueBlobSize;
}

static inline size_t align_sizet(size_t size) {
    constexpr size_t alignment = alignof(size_t) - 1;
    return (size + alignment) & ~alignment;
}

size_t BlobCache::getFlattenedSize() const {
    size_t size = align_sizet(sizeof(Header) + PROPERTY_VALUE_MAX);
    for (const CacheEntry& e : mCacheEntries) {
        std::shared_ptr<Blob> const& keyBlob = e.getKey();
        std::shared_ptr<Blob> const& valueBlob = e.getValue();
        size += align_sizet(sizeof(EntryHeader) + keyBlob->getSize() + valueBlob->getSize());
    }
    return size;
}

int BlobCache::flatten(void* buffer, size_t size) const {
    // Write the cache header
    if (size < sizeof(Header)) {
        ALOGE("flatten: not enough room for cache header");
        return 0;
    }
    Header* header = reinterpret_cast<Header*>(buffer);
    header->mMagicNumber = blobCacheMagic;
    header->mBlobCacheVersion = blobCacheVersion;
    header->mDeviceVersion = blobCacheDeviceVersion;
    header->mNumEntries = mCacheEntries.size();
    char buildId[PROPERTY_VALUE_MAX];
    header->mBuildIdLength = property_get("ro.build.id", buildId, "");
    memcpy(header->mBuildId, buildId, header->mBuildIdLength);

    // Write cache entries
    uint8_t* byteBuffer = reinterpret_cast<uint8_t*>(buffer);
    off_t byteOffset = align_sizet(sizeof(Header) + header->mBuildIdLength);
    for (const CacheEntry& e : mCacheEntries) {
        std::shared_ptr<Blob> const& keyBlob = e.getKey();
        std::shared_ptr<Blob> const& valueBlob = e.getValue();
        size_t keySize = keyBlob->getSize();
        size_t valueSize = valueBlob->getSize();

        size_t entrySize = sizeof(EntryHeader) + keySize + valueSize;
        size_t totalSize = align_sizet(entrySize);
        if (byteOffset + totalSize > size) {
            ALOGE("flatten: not enough room for cache entries");
            return -EINVAL;
        }

        EntryHeader* eheader = reinterpret_cast<EntryHeader*>(&byteBuffer[byteOffset]);
        eheader->mKeySize = keySize;
        eheader->mValueSize = valueSize;

        memcpy(eheader->mData, keyBlob->getData(), keySize);
        memcpy(eheader->mData + keySize, valueBlob->getData(), valueSize);

        if (totalSize > entrySize) {
            // We have padding bytes. Those will get written to storage, and contribute to the CRC,
            // so make sure we zero-them to have reproducible results.
            memset(eheader->mData + keySize + valueSize, 0, totalSize - entrySize);
        }

        byteOffset += totalSize;
    }

    return 0;
}

int BlobCache::unflatten(void const* buffer, size_t size) {
    // All errors should result in the BlobCache being in an empty state.
    mCacheEntries.clear();

    // Read the cache header
    if (size < sizeof(Header)) {
        ALOGE("unflatten: not enough room for cache header");
        return -EINVAL;
    }
    const Header* header = reinterpret_cast<const Header*>(buffer);
    if (header->mMagicNumber != blobCacheMagic) {
        ALOGE("unflatten: bad magic number: %" PRIu32, header->mMagicNumber);
        return -EINVAL;
    }
    char buildId[PROPERTY_VALUE_MAX];
    int len = property_get("ro.build.id", buildId, "");
    if (header->mBlobCacheVersion != blobCacheVersion ||
        header->mDeviceVersion != blobCacheDeviceVersion || len != header->mBuildIdLength ||
        strncmp(buildId, header->mBuildId, len)) {
        // We treat version mismatches as an empty cache.
        return 0;
    }

    // Read cache entries
    const uint8_t* byteBuffer = reinterpret_cast<const uint8_t*>(buffer);
    off_t byteOffset = align_sizet(sizeof(Header) + header->mBuildIdLength);
    size_t numEntries = header->mNumEntries;
    for (size_t i = 0; i < numEntries; i++) {
        if (byteOffset + sizeof(EntryHeader) > size) {
            mCacheEntries.clear();
            ALOGE("unflatten: not enough room for cache entry header");
            return -EINVAL;
        }

        const EntryHeader* eheader = reinterpret_cast<const EntryHeader*>(&byteBuffer[byteOffset]);
        size_t keySize = eheader->mKeySize;
        size_t valueSize = eheader->mValueSize;
        size_t entrySize = sizeof(EntryHeader) + keySize + valueSize;

        size_t totalSize = align_sizet(entrySize);
        if (byteOffset + totalSize > size) {
            mCacheEntries.clear();
            ALOGE("unflatten: not enough room for cache entry");
            return -EINVAL;
        }

        const uint8_t* data = eheader->mData;
        set(data, keySize, data + keySize, valueSize);

        byteOffset += totalSize;
    }

    return 0;
}

long int BlobCache::blob_random() {
#ifdef _WIN32
    return rand();
#else
    return nrand48(mRandState);
#endif
}

size_t BlobCache::findVictim() {
    switch (mPolicySelect) {
        case Select::RANDOM:
            return size_t(blob_random() % (mCacheEntries.size()));
        case Select::LRU:
            return std::min_element(mCacheEntries.begin(), mCacheEntries.end(),
                                    [](const CacheEntry& a, const CacheEntry& b) {
                                        return a.getRecency() < b.getRecency();
                                    }) -
                   mCacheEntries.begin();
        default:
            ALOGE("findVictim: unknown mPolicySelect: %d", mPolicySelect);
            return 0;
    }
}

size_t BlobCache::findDownTo(size_t newEntrySize, size_t onBehalfOf) {
    auto oldEntrySize = [this, onBehalfOf]() -> size_t {
        if (onBehalfOf == NoEntry) return 0;
        const auto& entry = mCacheEntries[onBehalfOf];
        return entry.getKey()->getSize() + entry.getValue()->getSize();
    };
    switch (mPolicyCapacity) {
        case Capacity::HALVE:
            return mMaxTotalSize / 2;
        case Capacity::FIT:
            return mMaxTotalSize - (newEntrySize - oldEntrySize());
        case Capacity::FIT_HALVE:
            return std::min(mMaxTotalSize - (newEntrySize - oldEntrySize()), mMaxTotalSize / 2);
        default:
            ALOGE("findDownTo: unknown mPolicyCapacity: %d", mPolicyCapacity);
            return 0;
    }
}

bool BlobCache::isFit(Capacity capacity) {
    switch (capacity) {
        case Capacity::HALVE:
            return false;
        case Capacity::FIT:
        case Capacity::FIT_HALVE:
            return true;
        default:
            ALOGE("isFit: unknown capacity: %d", capacity);
            return false;
    }
}

bool BlobCache::clean(size_t newEntrySize, size_t onBehalfOf) {
    // Remove a selected cache entry until the total cache size does
    // not exceed downTo.
    const size_t downTo = findDownTo(newEntrySize, onBehalfOf);

    bool cleaned = false;
    while (mTotalSize > downTo) {
        const size_t i = findVictim();
        const CacheEntry& entry(mCacheEntries[i]);
        const size_t entrySize = entry.getKey()->getSize() + entry.getValue()->getSize();
        mTotalSize -= entrySize;
        mCacheEntries.erase(mCacheEntries.begin() + i);
        cleaned = true;
    }
    return cleaned;
}

bool BlobCache::isCleanable() const {
    switch (mPolicyCapacity) {
        case Capacity::HALVE:
            return mTotalSize > mMaxTotalSize / 2;
        default:
            ALOGE("isCleanable: unknown mPolicyCapacity: %d", mPolicyCapacity);
            [[fallthrough]];
        case Capacity::FIT:
        case Capacity::FIT_HALVE:
            return mTotalSize > 0;
    }
}

BlobCache::Blob::Blob(const void* data, size_t size, bool copyData)
    : mData(copyData ? malloc(size) : data), mSize(size), mOwnsData(copyData) {
    if (data != NULL && copyData) {
        memcpy(const_cast<void*>(mData), data, size);
    }
}

BlobCache::Blob::~Blob() {
    if (mOwnsData) {
        free(const_cast<void*>(mData));
    }
}

bool BlobCache::Blob::operator<(const Blob& rhs) const {
    if (mSize == rhs.mSize) {
        return memcmp(mData, rhs.mData, mSize) < 0;
    } else {
        return mSize < rhs.mSize;
    }
}

const void* BlobCache::Blob::getData() const {
    return mData;
}

size_t BlobCache::Blob::getSize() const {
    return mSize;
}

BlobCache::CacheEntry::CacheEntry() : mRecency(0) {}

BlobCache::CacheEntry::CacheEntry(const std::shared_ptr<Blob>& key,
                                  const std::shared_ptr<Blob>& value, uint32_t recency)
    : mKey(key), mValue(value), mRecency(recency) {}

BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce)
    : mKey(ce.mKey), mValue(ce.mValue), mRecency(ce.mRecency) {}

bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const {
    return *mKey < *rhs.mKey;
}

const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) {
    mKey = rhs.mKey;
    mValue = rhs.mValue;
    mRecency = rhs.mRecency;
    return *this;
}

std::shared_ptr<BlobCache::Blob> BlobCache::CacheEntry::getKey() const {
    return mKey;
}

std::shared_ptr<BlobCache::Blob> BlobCache::CacheEntry::getValue() const {
    return mValue;
}

void BlobCache::CacheEntry::setValue(const std::shared_ptr<Blob>& value) {
    mValue = value;
}

uint32_t BlobCache::CacheEntry::getRecency() const {
    return mRecency;
}

void BlobCache::CacheEntry::setRecency(uint32_t recency) {
    mRecency = recency;
}

}  // namespace android