libutils/BlobCache.cpp - android_system_core - Gitiles

 /*
  ** 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 <inttypes.h>
 #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: %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;
     }

     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: %zu "
                             "(limit: %zu)",
                             keySize + valueSize, mMaxTotalSize);
                     break;
                 }
             }
             mCacheEntries.add(CacheEntry(keyBlob, valueBlob));
             mTotalSize = newTotalSize;
             ALOGV("set: created new cache entry with %zu byte key and %zu 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: %zu (limit: %zu)",
                             keySize + valueSize, mMaxTotalSize);
                     break;
                 }
             }
             mCacheEntries.editItemAt(index).setValue(valueBlob);
             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) {
     if (mMaxKeySize < keySize) {
         ALOGV("get: not searching because the key is too large: %zu (limit %zu)",
                 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 %zu", 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 %zu bytes to caller's buffer", valueBlobSize);
         memcpy(value, valueBlob->getData(), valueBlobSize);
     } else {
         ALOGV("get: caller's buffer is too small for value: %zu (needs %zu)",
                 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: %" PRIu32, 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
	/*
	** 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 <inttypes.h>
	#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: %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;
	}

	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: %zu "
	"(limit: %zu)",
	keySize + valueSize, mMaxTotalSize);
	break;
	}
	}
	mCacheEntries.add(CacheEntry(keyBlob, valueBlob));
	mTotalSize = newTotalSize;
	ALOGV("set: created new cache entry with %zu byte key and %zu 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: %zu (limit: %zu)",
	keySize + valueSize, mMaxTotalSize);
	break;
	}
	}
	mCacheEntries.editItemAt(index).setValue(valueBlob);
	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) {
	if (mMaxKeySize < keySize) {
	ALOGV("get: not searching because the key is too large: %zu (limit %zu)",
	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 %zu", 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 %zu bytes to caller's buffer", valueBlobSize);
	memcpy(value, valueBlob->getData(), valueBlobSize);
	} else {
	ALOGV("get: caller's buffer is too small for value: %zu (needs %zu)",
	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: %" PRIu32, 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