Merge "libutils: add a binary blob cache implementation."

4 files changed, 491 insertions, 0 deletions

diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk
index e8d40ba..093189c 100644
--- a/libs/utils/Android.mk
+++ b/libs/utils/Android.mk
@@ -21,6 +21,7 @@ commonSources:= \
 	Asset.cpp \
 	AssetDir.cpp \
 	AssetManager.cpp \
+	BlobCache.cpp \
 	BufferedTextOutput.cpp \
 	CallStack.cpp \
 	Debug.cpp \
diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp
new file mode 100644
index 0000000..1298fa7
--- /dev/null
+++ b/libs/utils/BlobCache.cpp
@@ -0,0 +1,232 @@
+/*
+ ** 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/Log.h>
+
+namespace android {
+
+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);
+    mRandState[0] = (now >> 0) & 0xFFFF;
+    mRandState[1] = (now >> 16) & 0xFFFF;
+    mRandState[2] = (now >> 32) & 0xFFFF;
+    LOGV("initializing random seed using %lld", now);
+}
+
+void BlobCache::set(const void* key, size_t keySize, const void* value,
+        size_t valueSize) {
+    if (mMaxKeySize < keySize) {
+        LOGV("set: not caching because the key is too large: %d (limit: %d)",
+                keySize, mMaxKeySize);
+        return;
+    }
+    if (mMaxValueSize < valueSize) {
+        LOGV("set: not caching because the value is too large: %d (limit: %d)",
+                valueSize, mMaxValueSize);
+        return;
+    }
+    if (mMaxTotalSize < keySize + valueSize) {
+        LOGV("set: not caching because the combined key/value size is too "
+                "large: %d (limit: %d)", keySize + valueSize, mMaxTotalSize);
+        return;
+    }
+    if (keySize == 0) {
+        LOGW("set: not caching because keySize is 0");
+        return;
+    }
+    if (valueSize <= 0) {
+        LOGW("set: not caching because valueSize is 0");
+        return;
+    }
+
+    Mutex::Autolock lock(mMutex);
+    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 {
+                    LOGV("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;
+            LOGV("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 {
+                    LOGV("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;
+            LOGV("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) {
+        LOGV("get: not searching because the key is too large: %d (limit %d)",
+                keySize, mMaxKeySize);
+        return 0;
+    }
+    Mutex::Autolock lock(mMutex);
+    sp<Blob> dummyKey(new Blob(key, keySize, false));
+    CacheEntry dummyEntry(dummyKey, NULL);
+    ssize_t index = mCacheEntries.indexOf(dummyEntry);
+    if (index < 0) {
+        LOGV("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) {
+        LOGV("get: copying %d bytes to caller's buffer", valueBlobSize);
+        memcpy(value, valueBlob->getData(), valueBlobSize);
+    } else {
+        LOGV("get: caller's buffer is too small for value: %d (needs %d)",
+                valueSize, valueBlobSize);
+    }
+    return valueBlobSize;
+}
+
+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(nrand48(mRandState) % (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 (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
diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk
index 72d4876..87ad98e 100644
--- a/libs/utils/tests/Android.mk
+++ b/libs/utils/tests/Android.mk
@@ -6,6 +6,7 @@ ifneq ($(TARGET_SIMULATOR),true)
 
 # Build the unit tests.
 test_src_files := \
+	BlobCache_test.cpp \
 	ObbFile_test.cpp \
 	Looper_test.cpp \
 	String8_test.cpp \
diff --git a/libs/utils/tests/BlobCache_test.cpp b/libs/utils/tests/BlobCache_test.cpp
new file mode 100644
index 0000000..653ea5e
--- /dev/null
+++ b/libs/utils/tests/BlobCache_test.cpp
@@ -0,0 +1,257 @@
+/*
+ ** 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.
+ */
+
+#include <gtest/gtest.h>
+
+#include <utils/BlobCache.h>
+
+namespace android {
+
+class BlobCacheTest : public ::testing::Test {
+protected:
+    enum {
+        MAX_KEY_SIZE = 6,
+        MAX_VALUE_SIZE = 8,
+        MAX_TOTAL_SIZE = 13,
+    };
+
+    virtual void SetUp() {
+        mBC = new BlobCache(MAX_KEY_SIZE, MAX_VALUE_SIZE, MAX_TOTAL_SIZE);
+    }
+
+    virtual void TearDown() {
+        mBC.clear();
+    }
+
+    sp<BlobCache> mBC;
+};
+
+TEST_F(BlobCacheTest, CacheSingleValueSucceeds) {
+    char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+    mBC->set("abcd", 4, "efgh", 4);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4));
+    ASSERT_EQ('e', buf[0]);
+    ASSERT_EQ('f', buf[1]);
+    ASSERT_EQ('g', buf[2]);
+    ASSERT_EQ('h', buf[3]);
+}
+
+TEST_F(BlobCacheTest, CacheTwoValuesSucceeds) {
+    char buf[2] = { 0xee, 0xee };
+    mBC->set("ab", 2, "cd", 2);
+    mBC->set("ef", 2, "gh", 2);
+    ASSERT_EQ(size_t(2), mBC->get("ab", 2, buf, 2));
+    ASSERT_EQ('c', buf[0]);
+    ASSERT_EQ('d', buf[1]);
+    ASSERT_EQ(size_t(2), mBC->get("ef", 2, buf, 2));
+    ASSERT_EQ('g', buf[0]);
+    ASSERT_EQ('h', buf[1]);
+}
+
+TEST_F(BlobCacheTest, GetOnlyWritesInsideBounds) {
+    char buf[6] = { 0xee, 0xee, 0xee, 0xee, 0xee, 0xee };
+    mBC->set("abcd", 4, "efgh", 4);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf+1, 4));
+    ASSERT_EQ(0xee, buf[0]);
+    ASSERT_EQ('e', buf[1]);
+    ASSERT_EQ('f', buf[2]);
+    ASSERT_EQ('g', buf[3]);
+    ASSERT_EQ('h', buf[4]);
+    ASSERT_EQ(0xee, buf[5]);
+}
+
+TEST_F(BlobCacheTest, GetOnlyWritesIfBufferIsLargeEnough) {
+    char buf[3] = { 0xee, 0xee, 0xee };
+    mBC->set("abcd", 4, "efgh", 4);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 3));
+    ASSERT_EQ(0xee, buf[0]);
+    ASSERT_EQ(0xee, buf[1]);
+    ASSERT_EQ(0xee, buf[2]);
+}
+
+TEST_F(BlobCacheTest, GetDoesntAccessNullBuffer) {
+    mBC->set("abcd", 4, "efgh", 4);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, NULL, 0));
+}
+
+TEST_F(BlobCacheTest, MultipleSetsCacheLatestValue) {
+    char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+    mBC->set("abcd", 4, "efgh", 4);
+    mBC->set("abcd", 4, "ijkl", 4);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4));
+    ASSERT_EQ('i', buf[0]);
+    ASSERT_EQ('j', buf[1]);
+    ASSERT_EQ('k', buf[2]);
+    ASSERT_EQ('l', buf[3]);
+}
+
+TEST_F(BlobCacheTest, SecondSetKeepsFirstValueIfTooLarge) {
+    char buf[MAX_VALUE_SIZE+1] = { 0xee, 0xee, 0xee, 0xee };
+    mBC->set("abcd", 4, "efgh", 4);
+    mBC->set("abcd", 4, buf, MAX_VALUE_SIZE+1);
+    ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4));
+    ASSERT_EQ('e', buf[0]);
+    ASSERT_EQ('f', buf[1]);
+    ASSERT_EQ('g', buf[2]);
+    ASSERT_EQ('h', buf[3]);
+}
+
+TEST_F(BlobCacheTest, DoesntCacheIfKeyIsTooBig) {
+    char key[MAX_KEY_SIZE+1];
+    char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+    for (int i = 0; i < MAX_KEY_SIZE+1; i++) {
+        key[i] = 'a';
+    }
+    mBC->set(key, MAX_KEY_SIZE+1, "bbbb", 4);
+    ASSERT_EQ(size_t(0), mBC->get(key, MAX_KEY_SIZE+1, buf, 4));
+    ASSERT_EQ(0xee, buf[0]);
+    ASSERT_EQ(0xee, buf[1]);
+    ASSERT_EQ(0xee, buf[2]);
+    ASSERT_EQ(0xee, buf[3]);
+}
+
+TEST_F(BlobCacheTest, DoesntCacheIfValueIsTooBig) {
+    char buf[MAX_VALUE_SIZE+1];
+    for (int i = 0; i < MAX_VALUE_SIZE+1; i++) {
+        buf[i] = 'b';
+    }
+    mBC->set("abcd", 4, buf, MAX_VALUE_SIZE+1);
+    for (int i = 0; i < MAX_VALUE_SIZE+1; i++) {
+        buf[i] = 0xee;
+    }
+    ASSERT_EQ(size_t(0), mBC->get("abcd", 4, buf, MAX_VALUE_SIZE+1));
+    for (int i = 0; i < MAX_VALUE_SIZE+1; i++) {
+        SCOPED_TRACE(i);
+        ASSERT_EQ(0xee, buf[i]);
+    }
+}
+
+TEST_F(BlobCacheTest, DoesntCacheIfKeyValuePairIsTooBig) {
+    // Check a testing assumptions
+    ASSERT_TRUE(MAX_TOTAL_SIZE < MAX_KEY_SIZE + MAX_VALUE_SIZE);
+    ASSERT_TRUE(MAX_KEY_SIZE < MAX_TOTAL_SIZE);
+
+    enum { bufSize = MAX_TOTAL_SIZE - MAX_KEY_SIZE + 1 };
+
+    char key[MAX_KEY_SIZE];
+    char buf[bufSize];
+    for (int i = 0; i < MAX_KEY_SIZE; i++) {
+        key[i] = 'a';
+    }
+    for (int i = 0; i < bufSize; i++) {
+        buf[i] = 'b';
+    }
+
+    mBC->set(key, MAX_KEY_SIZE, buf, MAX_VALUE_SIZE);
+    ASSERT_EQ(size_t(0), mBC->get(key, MAX_KEY_SIZE, NULL, 0));
+}
+
+TEST_F(BlobCacheTest, CacheMaxKeySizeSucceeds) {
+    char key[MAX_KEY_SIZE];
+    char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+    for (int i = 0; i < MAX_KEY_SIZE; i++) {
+        key[i] = 'a';
+    }
+    mBC->set(key, MAX_KEY_SIZE, "wxyz", 4);
+    ASSERT_EQ(size_t(4), mBC->get(key, MAX_KEY_SIZE, buf, 4));
+    ASSERT_EQ('w', buf[0]);
+    ASSERT_EQ('x', buf[1]);
+    ASSERT_EQ('y', buf[2]);
+    ASSERT_EQ('z', buf[3]);
+}
+
+TEST_F(BlobCacheTest, CacheMaxValueSizeSucceeds) {
+    char buf[MAX_VALUE_SIZE];
+    for (int i = 0; i < MAX_VALUE_SIZE; i++) {
+        buf[i] = 'b';
+    }
+    mBC->set("abcd", 4, buf, MAX_VALUE_SIZE);
+    for (int i = 0; i < MAX_VALUE_SIZE; i++) {
+        buf[i] = 0xee;
+    }
+    ASSERT_EQ(size_t(MAX_VALUE_SIZE), mBC->get("abcd", 4, buf,
+            MAX_VALUE_SIZE));
+    for (int i = 0; i < MAX_VALUE_SIZE; i++) {
+        SCOPED_TRACE(i);
+        ASSERT_EQ('b', buf[i]);
+    }
+}
+
+TEST_F(BlobCacheTest, CacheMaxKeyValuePairSizeSucceeds) {
+    // Check a testing assumption
+    ASSERT_TRUE(MAX_KEY_SIZE < MAX_TOTAL_SIZE);
+
+    enum { bufSize = MAX_TOTAL_SIZE - MAX_KEY_SIZE };
+
+    char key[MAX_KEY_SIZE];
+    char buf[bufSize];
+    for (int i = 0; i < MAX_KEY_SIZE; i++) {
+        key[i] = 'a';
+    }
+    for (int i = 0; i < bufSize; i++) {
+        buf[i] = 'b';
+    }
+
+    mBC->set(key, MAX_KEY_SIZE, buf, bufSize);
+    ASSERT_EQ(size_t(bufSize), mBC->get(key, MAX_KEY_SIZE, NULL, 0));
+}
+
+TEST_F(BlobCacheTest, CacheMinKeyAndValueSizeSucceeds) {
+    char buf[1] = { 0xee };
+    mBC->set("x", 1, "y", 1);
+    ASSERT_EQ(size_t(1), mBC->get("x", 1, buf, 1));
+    ASSERT_EQ('y', buf[0]);
+}
+
+TEST_F(BlobCacheTest, CacheSizeDoesntExceedTotalLimit) {
+    for (int i = 0; i < 256; i++) {
+        uint8_t k = i;
+        mBC->set(&k, 1, "x", 1);
+    }
+    int numCached = 0;
+    for (int i = 0; i < 256; i++) {
+        uint8_t k = i;
+        if (mBC->get(&k, 1, NULL, 0) == 1) {
+            numCached++;
+        }
+    }
+    ASSERT_GE(MAX_TOTAL_SIZE / 2, numCached);
+}
+
+TEST_F(BlobCacheTest, ExceedingTotalLimitHalvesCacheSize) {
+    // Fill up the entire cache with 1 char key/value pairs.
+    const int maxEntries = MAX_TOTAL_SIZE / 2;
+    for (int i = 0; i < maxEntries; i++) {
+        uint8_t k = i;
+        mBC->set(&k, 1, "x", 1);
+    }
+    // Insert one more entry, causing a cache overflow.
+    {
+        uint8_t k = maxEntries;
+        mBC->set(&k, 1, "x", 1);
+    }
+    // Count the number of entries in the cache.
+    int numCached = 0;
+    for (int i = 0; i < maxEntries+1; i++) {
+        uint8_t k = i;
+        if (mBC->get(&k, 1, NULL, 0) == 1) {
+            numCached++;
+        }
+    }
+    ASSERT_EQ(maxEntries/2 + 1, numCached);
+}
+
+} // namespace android