From 94c1f148bb655a3dd3c2a2167476239b41305ff0 Mon Sep 17 00:00:00 2001 From: Jamie Gennis Date: Sun, 30 Oct 2011 18:10:41 -0700 Subject: BlobCache: remove the mutex locking This change removes the mutex from the BlobCache class. The caller must be responsible for thread synchronization in order to properly implement the Flattenable interface, which is coming soon. Otherwise would be the potential for the cache contents to change between the call to the getFlattenedSize and flatten methods. Because the caller must do this synchronization anyway there's no reason to also some synchronization inside BlobCache. Change-Id: Ie1f4f6f82b78744f46a41ce863cac0cad276a20e --- libs/utils/BlobCache.cpp | 2 -- 1 file changed, 2 deletions(-) (limited to 'libs/utils/BlobCache.cpp') diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp index 590576a8d477..15155b25dc4d 100644 --- a/libs/utils/BlobCache.cpp +++ b/libs/utils/BlobCache.cpp @@ -67,7 +67,6 @@ void BlobCache::set(const void* key, size_t keySize, const void* value, return; } - Mutex::Autolock lock(mMutex); sp dummyKey(new Blob(key, keySize, false)); CacheEntry dummyEntry(dummyKey, NULL); @@ -129,7 +128,6 @@ size_t BlobCache::get(const void* key, size_t keySize, void* value, keySize, mMaxKeySize); return 0; } - Mutex::Autolock lock(mMutex); sp dummyKey(new Blob(key, keySize, false)); CacheEntry dummyEntry(dummyKey, NULL); ssize_t index = mCacheEntries.indexOf(dummyEntry); -- cgit v1.2.3-59-g8ed1b From 9d9768dbd7d8fe7af55fbd570dff9cf79a4d1807 Mon Sep 17 00:00:00 2001 From: Jamie Gennis Date: Thu, 12 May 2011 17:39:03 -0700 Subject: BlobCache: implement cache serialization This change adds serialization and deserialization functionality to BlobCache, conforming to the Flattenable interface. Change-Id: Ibc99cb1c3d015f363d57d0713eabccec07ff975e --- include/utils/BlobCache.h | 96 ++++++++++++++++++--- libs/utils/BlobCache.cpp | 140 +++++++++++++++++++++++++++++- libs/utils/tests/BlobCache_test.cpp | 164 ++++++++++++++++++++++++++++++++++++ 3 files changed, 386 insertions(+), 14 deletions(-) (limited to 'libs/utils/BlobCache.cpp') diff --git a/include/utils/BlobCache.h b/include/utils/BlobCache.h index 11d4246665b6..4f342a2adc6f 100644 --- a/include/utils/BlobCache.h +++ b/include/utils/BlobCache.h @@ -19,6 +19,7 @@ #include +#include #include #include #include @@ -28,10 +29,11 @@ namespace android { // 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 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. diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp index 15155b25dc4d..d38aae9cd4e3 100644 --- a/libs/utils/BlobCache.cpp +++ b/libs/utils/BlobCache.cpp @@ -21,10 +21,20 @@ #include #include +#include #include 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), @@ -71,7 +81,6 @@ void BlobCache::set(const void* key, size_t keySize, const void* value, CacheEntry dummyEntry(dummyKey, NULL); while (true) { - ssize_t index = mCacheEntries.indexOf(dummyEntry); if (index < 0) { // Create a new cache entry. @@ -150,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 keyBlob = e.getKey(); + sp 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(buffer); + header->mMagicNumber = blobCacheMagic; + header->mBlobCacheVersion = blobCacheVersion; + header->mDeviceVersion = blobCacheDeviceVersion; + header->mNumEntries = mCacheEntries.size(); + + // Write cache entries + uint8_t* byteBuffer = reinterpret_cast(buffer); + off_t byteOffset = align4(sizeof(Header)); + for (size_t i = 0; i < mCacheEntries.size(); i++) { + const CacheEntry& e(mCacheEntries[i]); + sp keyBlob = e.getKey(); + sp 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( + &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(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(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( + &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(); @@ -177,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(mData), data, size); } } diff --git a/libs/utils/tests/BlobCache_test.cpp b/libs/utils/tests/BlobCache_test.cpp index 653ea5e91cde..b64cc395650c 100644 --- a/libs/utils/tests/BlobCache_test.cpp +++ b/libs/utils/tests/BlobCache_test.cpp @@ -14,9 +14,13 @@ ** limitations under the License. */ +#include +#include + #include #include +#include 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 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 -- cgit v1.2.3-59-g8ed1b