1 files changed, 362 insertions, 0 deletions
diff --git a/libutils/BlobCache.cpp b/libutils/BlobCache.cpp
new file mode 100644
index 0000000..0fb1d8e
--- /dev/null
+++ b/libutils/BlobCache.cpp
@@ -0,0 +1,362 @@
+/*
+ ** 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_TAG "BlobCache"
+//#define LOG_NDEBUG 0
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <utils/BlobCache.h>
+#include <utils/Errors.h>
+#include <utils/Log.h>
+
+namespace android {
+
+// BlobCache::Header::mMagicNumber value
+static const uint32_t blobCacheMagic = '_Bb$';
+
+// BlobCache::Header::mBlobCacheVersion value
+static const uint32_t blobCacheVersion = 1;
+
+// BlobCache::Header::mDeviceVersion value
+static const uint32_t blobCacheDeviceVersion = 1;
+
+BlobCache::BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize):
+        mMaxKeySize(maxKeySize),
+        mMaxValueSize(maxValueSize),
+        mMaxTotalSize(maxTotalSize),
+        mTotalSize(0) {
+    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
+#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", 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: %d (limit: %d)",
+                keySize, mMaxKeySize);
+        return;
+    }
+    if (mMaxValueSize < valueSize) {
+        ALOGV("set: not caching because the value is too large: %d (limit: %d)",
+                valueSize, mMaxValueSize);
+        return;
+    }
+    if (mMaxTotalSize < keySize + valueSize) {
+        ALOGV("set: not caching because the combined key/value size is too "
+                "large: %d (limit: %d)", 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;
+    }
+
+    sp<Blob> dummyKey(new Blob(key, keySize, false));
+    CacheEntry dummyEntry(dummyKey, NULL);
+
+    while (true) {
+        ssize_t index = mCacheEntries.indexOf(dummyEntry);
+        if (index < 0) {
+            // Create a new cache entry.
+            sp<Blob> keyBlob(new Blob(key, keySize, true));
+            sp<Blob> valueBlob(new Blob(value, valueSize, true));
+            size_t newTotalSize = mTotalSize + keySize + valueSize;
+            if (mMaxTotalSize < newTotalSize) {
+                if (isCleanable()) {
+                    // Clean the cache and try again.
+                    clean();
+                    continue;
+                } else {
+                    ALOGV("set: not caching new key/value pair because the "
+                            "total cache size limit would be exceeded: %d "
+                            "(limit: %d)",
+                            keySize + valueSize, mMaxTotalSize);
+                    break;
+                }
+            }
+            mCacheEntries.add(CacheEntry(keyBlob, valueBlob));
+            mTotalSize = newTotalSize;
+            ALOGV("set: created new cache entry with %d byte key and %d byte value",
+                    keySize, valueSize);
+        } else {
+            // Update the existing cache entry.
+            sp<Blob> valueBlob(new Blob(value, valueSize, true));
+            sp<Blob> oldValueBlob(mCacheEntries[index].getValue());
+            size_t newTotalSize = mTotalSize + valueSize - oldValueBlob->getSize();
+            if (mMaxTotalSize < newTotalSize) {
+                if (isCleanable()) {
+                    // Clean the cache and try again.
+                    clean();
+                    continue;
+                } else {
+                    ALOGV("set: not caching new value because the total cache "
+                            "size limit would be exceeded: %d (limit: %d)",
+                            keySize + valueSize, mMaxTotalSize);
+                    break;
+                }
+            }
+            mCacheEntries.editItemAt(index).setValue(valueBlob);
+            mTotalSize = newTotalSize;
+            ALOGV("set: updated existing cache entry with %d byte key and %d byte "
+                    "value", keySize, valueSize);
+        }
+        break;
+    }
+}
+
+size_t BlobCache::get(const void* key, size_t keySize, void* value,
+        size_t valueSize) {
+    if (mMaxKeySize < keySize) {
+        ALOGV("get: not searching because the key is too large: %d (limit %d)",
+                keySize, mMaxKeySize);
+        return 0;
+    }
+    sp<Blob> dummyKey(new Blob(key, keySize, false));
+    CacheEntry dummyEntry(dummyKey, NULL);
+    ssize_t index = mCacheEntries.indexOf(dummyEntry);
+    if (index < 0) {
+        ALOGV("get: no cache entry found for key of size %d", keySize);
+        return 0;
+    }
+
+    // The key was found. Return the value if the caller's buffer is large
+    // enough.
+    sp<Blob> valueBlob(mCacheEntries[index].getValue());
+    size_t valueBlobSize = valueBlob->getSize();
+    if (valueBlobSize <= valueSize) {
+        ALOGV("get: copying %d bytes to caller's buffer", valueBlobSize);
+        memcpy(value, valueBlob->getData(), valueBlobSize);
+    } else {
+        ALOGV("get: caller's buffer is too small for value: %d (needs %d)",
+                valueSize, valueBlobSize);
+    }
+    return valueBlobSize;
+}
+
+static inline size_t align4(size_t size) {
+    return (size + 3) & ~3;
+}
+
+size_t BlobCache::getFlattenedSize() const {
+    size_t size = sizeof(Header);
+    for (size_t i = 0; i < mCacheEntries.size(); i++) {
+        const CacheEntry& e(mCacheEntries[i]);
+        sp<Blob> keyBlob = e.getKey();
+        sp<Blob> valueBlob = e.getValue();
+        size = align4(size);
+        size += sizeof(EntryHeader) + keyBlob->getSize() +
+                valueBlob->getSize();
+    }
+    return size;
+}
+
+status_t 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 BAD_VALUE;
+    }
+    Header* header = reinterpret_cast<Header*>(buffer);
+    header->mMagicNumber = blobCacheMagic;
+    header->mBlobCacheVersion = blobCacheVersion;
+    header->mDeviceVersion = blobCacheDeviceVersion;
+    header->mNumEntries = mCacheEntries.size();
+
+    // Write cache entries
+    uint8_t* byteBuffer = reinterpret_cast<uint8_t*>(buffer);
+    off_t byteOffset = align4(sizeof(Header));
+    for (size_t i = 0; i < mCacheEntries.size(); i++) {
+        const CacheEntry& e(mCacheEntries[i]);
+        sp<Blob> keyBlob = e.getKey();
+        sp<Blob> valueBlob = e.getValue();
+        size_t keySize = keyBlob->getSize();
+        size_t valueSize = valueBlob->getSize();
+
+        size_t entrySize = sizeof(EntryHeader) + keySize + valueSize;
+        if (byteOffset + entrySize > size) {
+            ALOGE("flatten: not enough room for cache entries");
+            return BAD_VALUE;
+        }
+
+        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);
+
+        byteOffset += align4(entrySize);
+    }
+
+    return OK;
+}
+
+status_t 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 BAD_VALUE;
+    }
+    const Header* header = reinterpret_cast<const Header*>(buffer);
+    if (header->mMagicNumber != blobCacheMagic) {
+        ALOGE("unflatten: bad magic number: %d", header->mMagicNumber);
+        return BAD_VALUE;
+    }
+    if (header->mBlobCacheVersion != blobCacheVersion ||
+            header->mDeviceVersion != blobCacheDeviceVersion) {
+        // We treat version mismatches as an empty cache.
+        return OK;
+    }
+
+    // Read cache entries
+    const uint8_t* byteBuffer = reinterpret_cast<const uint8_t*>(buffer);
+    off_t byteOffset = align4(sizeof(Header));
+    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 headers");
+            return BAD_VALUE;
+        }
+
+        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;
+
+        if (byteOffset + entrySize > size) {
+            mCacheEntries.clear();
+            ALOGE("unflatten: not enough room for cache entry headers");
+            return BAD_VALUE;
+        }
+
+        const uint8_t* data = eheader->mData;
+        set(data, keySize, data + keySize, valueSize);
+
+        byteOffset += align4(entrySize);
+    }
+
+    return OK;
+}
+
+long int BlobCache::blob_random() {
+#ifdef _WIN32
+    return rand();
+#else
+    return nrand48(mRandState);
+#endif
+}
+
+void BlobCache::clean() {
+    // Remove a random cache entry until the total cache size gets below half
+    // the maximum total cache size.
+    while (mTotalSize > mMaxTotalSize / 2) {
+        size_t i = size_t(blob_random() % (mCacheEntries.size()));
+        const CacheEntry& entry(mCacheEntries[i]);
+        mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize();
+        mCacheEntries.removeAt(i);
+    }
+}
+
+bool BlobCache::isCleanable() const {
+    return mTotalSize > mMaxTotalSize / 2;
+}
+
+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() {
+}
+
+BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value):
+        mKey(key),
+        mValue(value) {
+}
+
+BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce):
+        mKey(ce.mKey),
+        mValue(ce.mValue) {
+}
+
+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;
+    return *this;
+}
+
+sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const {
+    return mKey;
+}
+
+sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const {
+    return mValue;
+}
+
+void BlobCache::CacheEntry::setValue(const sp<Blob>& value) {
+    mValue = value;
+}
+
+} // namespace android