summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJamie Gennis <jgennis@google.com>2011-11-03 18:55:14 +0000
committerAndroid Git Automerger <android-git-automerger@android.com>2011-11-03 18:55:14 +0000
commit7fbb39960e5af2319aeed653ee07751762d6bd8a (patch)
tree87f25f1182fd261bef78f0d49bec1beab008425f
parent464f048cddcb6b88bb4b7793f6b8b7f4be077f20 (diff)
parent3aed920fccbab5797de6f79d55848a8511ac7af9 (diff)
downloadframeworks_native-7fbb39960e5af2319aeed653ee07751762d6bd8a.zip
frameworks_native-7fbb39960e5af2319aeed653ee07751762d6bd8a.tar.gz
frameworks_native-7fbb39960e5af2319aeed653ee07751762d6bd8a.tar.bz2
am 236aea35: Merge changes Ibc99cb1c,Ie1f4f6f8 into ics-mr1
* commit '236aea3579787961fdd41d87574760b63323c0c1': BlobCache: implement cache serialization BlobCache: remove the mutex locking
-rw-r--r--include/utils/BlobCache.h107
-rw-r--r--libs/utils/BlobCache.cpp142
-rw-r--r--libs/utils/tests/BlobCache_test.cpp164
3 files changed, 389 insertions, 24 deletions
diff --git a/include/utils/BlobCache.h b/include/utils/BlobCache.h
index dc45ff0..4f342a2 100644
--- a/include/utils/BlobCache.h
+++ b/include/utils/BlobCache.h
@@ -19,19 +19,21 @@
#include <stddef.h>
+#include <utils/Flattenable.h>
#include <utils/RefBase.h>
#include <utils/SortedVector.h>
#include <utils/threads.h>
namespace android {
-// A BlobCache is an in-memory cache for binary key/value pairs. All the public
-// methods are thread-safe.
+// A BlobCache is an in-memory cache for binary key/value pairs. A BlobCache
+// does NOT provide any thread-safety guarantees.
//
-// The cache contents can be serialized to a file and reloaded in a subsequent
-// execution of the program. This serialization is non-portable and should only
-// be loaded by the device that generated it.
-class BlobCache : public RefBase {
+// The cache contents can be serialized to an in-memory buffer or mmap'd file
+// and then reloaded in a subsequent execution of the program. This
+// serialization is non-portable and the data should only be used by the device
+// that generated it.
+class BlobCache : public RefBase, public Flattenable {
public:
// Create an empty blob cache. The blob cache will cache key/value pairs
@@ -58,14 +60,13 @@ public:
void set(const void* key, size_t keySize, const void* value,
size_t valueSize);
- // The get function retrieves from the cache the binary value associated
- // with a given binary key. If the key is present in the cache then the
- // length of the binary value associated with that key is returned. If the
- // value argument is non-NULL and the size of the cached value is less than
- // valueSize bytes then the cached value is copied into the buffer pointed
- // to by the value argument. If the key is not present in the cache then 0
- // is returned and the buffer pointed to by the value argument is not
- // modified.
+ // get retrieves from the cache the binary value associated with a given
+ // binary key. If the key is present in the cache then the length of the
+ // binary value associated with that key is returned. If the value argument
+ // is non-NULL and the size of the cached value is less than valueSize bytes
+ // then the cached value is copied into the buffer pointed to by the value
+ // argument. If the key is not present in the cache then 0 is returned and
+ // the buffer pointed to by the value argument is not modified.
//
// Note that when calling get multiple times with the same key, the later
// calls may fail, returning 0, even if earlier calls succeeded. The return
@@ -77,6 +78,37 @@ public:
// 0 <= valueSize
size_t get(const void* key, size_t keySize, void* value, size_t valueSize);
+ // getFlattenedSize returns the number of bytes needed to store the entire
+ // serialized cache.
+ virtual size_t getFlattenedSize() const;
+
+ // getFdCount returns the number of file descriptors that will result from
+ // flattening the cache. This will always return 0 so as to allow the
+ // flattened cache to be saved to disk and then later restored.
+ virtual size_t getFdCount() const;
+
+ // flatten serializes the current contents of the cache into the memory
+ // pointed to by 'buffer'. The serialized cache contents can later be
+ // loaded into a BlobCache object using the unflatten method. The contents
+ // of the BlobCache object will not be modified.
+ //
+ // Preconditions:
+ // size >= this.getFlattenedSize()
+ // count == 0
+ virtual status_t flatten(void* buffer, size_t size, int fds[],
+ size_t count) const;
+
+ // unflatten replaces the contents of the cache with the serialized cache
+ // contents in the memory pointed to by 'buffer'. The previous contents of
+ // the BlobCache will be evicted from the cache. If an error occurs while
+ // unflattening the serialized cache contents then the BlobCache will be
+ // left in an empty state.
+ //
+ // Preconditions:
+ // count == 0
+ virtual status_t unflatten(void const* buffer, size_t size, int fds[],
+ size_t count);
+
private:
// Copying is disallowed.
BlobCache(const BlobCache&);
@@ -144,6 +176,46 @@ private:
sp<Blob> mValue;
};
+ // A Header is the header for the entire BlobCache serialization format. No
+ // need to make this portable, so we simply write the struct out.
+ struct Header {
+ // mMagicNumber is the magic number that identifies the data as
+ // serialized BlobCache contents. It must always contain 'Blb$'.
+ uint32_t mMagicNumber;
+
+ // mBlobCacheVersion is the serialization format version.
+ uint32_t mBlobCacheVersion;
+
+ // mDeviceVersion is the device-specific version of the cache. This can
+ // be used to invalidate the cache.
+ uint32_t mDeviceVersion;
+
+ // mNumEntries is number of cache entries following the header in the
+ // data.
+ size_t mNumEntries;
+ };
+
+ // An EntryHeader is the header for a serialized cache entry. No need to
+ // make this portable, so we simply write the struct out. Each EntryHeader
+ // is followed imediately by the key data and then the value data.
+ //
+ // The beginning of each serialized EntryHeader is 4-byte aligned, so the
+ // number of bytes that a serialized cache entry will occupy is:
+ //
+ // ((sizeof(EntryHeader) + keySize + valueSize) + 3) & ~3
+ //
+ struct EntryHeader {
+ // mKeySize is the size of the entry key in bytes.
+ size_t mKeySize;
+
+ // mValueSize is the size of the entry value in bytes.
+ size_t mValueSize;
+
+ // mData contains both the key and value data for the cache entry. The
+ // key comes first followed immediately by the value.
+ uint8_t mData[];
+ };
+
// mMaxKeySize is the maximum key size that will be cached. Calls to
// BlobCache::set with a keySize parameter larger than mMaxKeySize will
// simply not add the key/value pair to the cache.
@@ -166,17 +238,12 @@ private:
size_t mTotalSize;
// mRandState is the pseudo-random number generator state. It is passed to
- // nrand48 to generate random numbers when needed. It must be protected by
- // mMutex.
+ // nrand48 to generate random numbers when needed.
unsigned short mRandState[3];
// mCacheEntries stores all the cache entries that are resident in memory.
// Cache entries are added to it by the 'set' method.
SortedVector<CacheEntry> mCacheEntries;
-
- // mMutex is used to synchronize access to all member variables. It must be
- // locked any time the member variables are written or read.
- Mutex mMutex;
};
}
diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp
index 4039807..4970828 100644
--- a/libs/utils/BlobCache.cpp
+++ b/libs/utils/BlobCache.cpp
@@ -21,10 +21,20 @@
#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),
@@ -67,12 +77,10 @@ void BlobCache::set(const void* key, size_t keySize, const void* value,
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.
@@ -129,7 +137,6 @@ size_t BlobCache::get(const void* key, size_t keySize, void* value,
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);
@@ -152,6 +159,133 @@ size_t BlobCache::get(const void* key, size_t keySize, void* value,
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;
+}
+
+size_t BlobCache::getFdCount() const {
+ return 0;
+}
+
+status_t BlobCache::flatten(void* buffer, size_t size, int fds[], size_t count)
+ const {
+ if (count != 0) {
+ LOGE("flatten: nonzero fd count: %d", count);
+ return BAD_VALUE;
+ }
+
+ // Write the cache header
+ if (size < sizeof(Header)) {
+ LOGE("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) {
+ LOGE("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, int fds[],
+ size_t count) {
+ // All errors should result in the BlobCache being in an empty state.
+ mCacheEntries.clear();
+
+ if (count != 0) {
+ LOGE("unflatten: nonzero fd count: %d", count);
+ return BAD_VALUE;
+ }
+
+ // Read the cache header
+ if (size < sizeof(Header)) {
+ LOGE("unflatten: not enough room for cache header");
+ return BAD_VALUE;
+ }
+ const Header* header = reinterpret_cast<const Header*>(buffer);
+ if (header->mMagicNumber != blobCacheMagic) {
+ LOGE("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();
+ LOGE("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();
+ LOGE("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();
@@ -179,7 +313,7 @@ BlobCache::Blob::Blob(const void* data, size_t size, bool copyData):
mData(copyData ? malloc(size) : data),
mSize(size),
mOwnsData(copyData) {
- if (copyData) {
+ if (data != NULL && copyData) {
memcpy(const_cast<void*>(mData), data, size);
}
}
diff --git a/libs/utils/tests/BlobCache_test.cpp b/libs/utils/tests/BlobCache_test.cpp
index 653ea5e..b64cc39 100644
--- a/libs/utils/tests/BlobCache_test.cpp
+++ b/libs/utils/tests/BlobCache_test.cpp
@@ -14,9 +14,13 @@
** limitations under the License.
*/
+#include <fcntl.h>
+#include <stdio.h>
+
#include <gtest/gtest.h>
#include <utils/BlobCache.h>
+#include <utils/Errors.h>
namespace android {
@@ -254,4 +258,164 @@ TEST_F(BlobCacheTest, ExceedingTotalLimitHalvesCacheSize) {
ASSERT_EQ(maxEntries/2 + 1, numCached);
}
+class BlobCacheFlattenTest : public BlobCacheTest {
+protected:
+ virtual void SetUp() {
+ BlobCacheTest::SetUp();
+ mBC2 = new BlobCache(MAX_KEY_SIZE, MAX_VALUE_SIZE, MAX_TOTAL_SIZE);
+ }
+
+ virtual void TearDown() {
+ mBC2.clear();
+ BlobCacheTest::TearDown();
+ }
+
+ void roundTrip() {
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+ ASSERT_EQ(OK, mBC2->unflatten(flat, size, NULL, 0));
+ delete[] flat;
+ }
+
+ sp<BlobCache> mBC2;
+};
+
+TEST_F(BlobCacheFlattenTest, FlattenOneValue) {
+ char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+ mBC->set("abcd", 4, "efgh", 4);
+ roundTrip();
+ ASSERT_EQ(size_t(4), mBC2->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(BlobCacheFlattenTest, FlattenFullCache) {
+ // 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, &k, 1);
+ }
+
+ roundTrip();
+
+ // Verify the deserialized cache
+ for (int i = 0; i < maxEntries; i++) {
+ uint8_t k = i;
+ uint8_t v = 0xee;
+ ASSERT_EQ(size_t(1), mBC2->get(&k, 1, &v, 1));
+ ASSERT_EQ(k, v);
+ }
+}
+
+TEST_F(BlobCacheFlattenTest, FlattenDoesntChangeCache) {
+ // 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, &k, 1);
+ }
+
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+ delete[] flat;
+
+ // Verify the cache that we just serialized
+ for (int i = 0; i < maxEntries; i++) {
+ uint8_t k = i;
+ uint8_t v = 0xee;
+ ASSERT_EQ(size_t(1), mBC->get(&k, 1, &v, 1));
+ ASSERT_EQ(k, v);
+ }
+}
+
+TEST_F(BlobCacheFlattenTest, FlattenCatchesBufferTooSmall) {
+ // 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, &k, 1);
+ }
+
+ size_t size = mBC->getFlattenedSize() - 1;
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(BAD_VALUE, mBC->flatten(flat, size, NULL, 0));
+ delete[] flat;
+}
+
+TEST_F(BlobCacheFlattenTest, UnflattenCatchesBadMagic) {
+ char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+ mBC->set("abcd", 4, "efgh", 4);
+
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+ flat[1] = ~flat[1];
+
+ // Bad magic should cause an error.
+ ASSERT_EQ(BAD_VALUE, mBC2->unflatten(flat, size, NULL, 0));
+ delete[] flat;
+
+ // The error should cause the unflatten to result in an empty cache
+ ASSERT_EQ(size_t(0), mBC2->get("abcd", 4, buf, 4));
+}
+
+TEST_F(BlobCacheFlattenTest, UnflattenCatchesBadBlobCacheVersion) {
+ char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+ mBC->set("abcd", 4, "efgh", 4);
+
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+ flat[5] = ~flat[5];
+
+ // Version mismatches shouldn't cause errors, but should not use the
+ // serialized entries
+ ASSERT_EQ(OK, mBC2->unflatten(flat, size, NULL, 0));
+ delete[] flat;
+
+ // The version mismatch should cause the unflatten to result in an empty
+ // cache
+ ASSERT_EQ(size_t(0), mBC2->get("abcd", 4, buf, 4));
+}
+
+TEST_F(BlobCacheFlattenTest, UnflattenCatchesBadBlobCacheDeviceVersion) {
+ char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+ mBC->set("abcd", 4, "efgh", 4);
+
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+ flat[10] = ~flat[10];
+
+ // Version mismatches shouldn't cause errors, but should not use the
+ // serialized entries
+ ASSERT_EQ(OK, mBC2->unflatten(flat, size, NULL, 0));
+ delete[] flat;
+
+ // The version mismatch should cause the unflatten to result in an empty
+ // cache
+ ASSERT_EQ(size_t(0), mBC2->get("abcd", 4, buf, 4));
+}
+
+TEST_F(BlobCacheFlattenTest, UnflattenCatchesBufferTooSmall) {
+ char buf[4] = { 0xee, 0xee, 0xee, 0xee };
+ mBC->set("abcd", 4, "efgh", 4);
+
+ size_t size = mBC->getFlattenedSize();
+ uint8_t* flat = new uint8_t[size];
+ ASSERT_EQ(OK, mBC->flatten(flat, size, NULL, 0));
+
+ // A buffer truncation shouldt cause an error
+ ASSERT_EQ(BAD_VALUE, mBC2->unflatten(flat, size-1, NULL, 0));
+ delete[] flat;
+
+ // The error should cause the unflatten to result in an empty cache
+ ASSERT_EQ(size_t(0), mBC2->get("abcd", 4, buf, 4));
+}
+
} // namespace android