BlobCache.cpp revision 5bed8036644f552210a7cfcbed2d6d20cf2981b0
1/* 2 ** Copyright 2011, The Android Open Source Project 3 ** 4 ** Licensed under the Apache License, Version 2.0 (the "License"); 5 ** you may not use this file except in compliance with the License. 6 ** You may obtain a copy of the License at 7 ** 8 ** http://www.apache.org/licenses/LICENSE-2.0 9 ** 10 ** Unless required by applicable law or agreed to in writing, software 11 ** distributed under the License is distributed on an "AS IS" BASIS, 12 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 ** See the License for the specific language governing permissions and 14 ** limitations under the License. 15 */ 16 17#define LOG_TAG "BlobCache" 18//#define LOG_NDEBUG 0 19 20#include <inttypes.h> 21#include <stdlib.h> 22#include <string.h> 23 24#include <utils/BlobCache.h> 25#include <utils/Errors.h> 26#include <utils/Log.h> 27 28namespace android { 29 30// BlobCache::Header::mMagicNumber value 31static const uint32_t blobCacheMagic = ('_' << 24) + ('B' << 16) + ('b' << 8) + '$'; 32 33// BlobCache::Header::mBlobCacheVersion value 34static const uint32_t blobCacheVersion = 1; 35 36// BlobCache::Header::mDeviceVersion value 37static const uint32_t blobCacheDeviceVersion = 1; 38 39BlobCache::BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize): 40 mMaxKeySize(maxKeySize), 41 mMaxValueSize(maxValueSize), 42 mMaxTotalSize(maxTotalSize), 43 mTotalSize(0) { 44 nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC); 45#ifdef _WIN32 46 srand(now); 47#else 48 mRandState[0] = (now >> 0) & 0xFFFF; 49 mRandState[1] = (now >> 16) & 0xFFFF; 50 mRandState[2] = (now >> 32) & 0xFFFF; 51#endif 52 ALOGV("initializing random seed using %lld", (unsigned long long)now); 53} 54 55void BlobCache::set(const void* key, size_t keySize, const void* value, 56 size_t valueSize) { 57 if (mMaxKeySize < keySize) { 58 ALOGV("set: not caching because the key is too large: %zu (limit: %zu)", 59 keySize, mMaxKeySize); 60 return; 61 } 62 if (mMaxValueSize < valueSize) { 63 ALOGV("set: not caching because the value is too large: %zu (limit: %zu)", 64 valueSize, mMaxValueSize); 65 return; 66 } 67 if (mMaxTotalSize < keySize + valueSize) { 68 ALOGV("set: not caching because the combined key/value size is too " 69 "large: %zu (limit: %zu)", keySize + valueSize, mMaxTotalSize); 70 return; 71 } 72 if (keySize == 0) { 73 ALOGW("set: not caching because keySize is 0"); 74 return; 75 } 76 if (valueSize <= 0) { 77 ALOGW("set: not caching because valueSize is 0"); 78 return; 79 } 80 81 sp<Blob> dummyKey(new Blob(key, keySize, false)); 82 CacheEntry dummyEntry(dummyKey, NULL); 83 84 while (true) { 85 ssize_t index = mCacheEntries.indexOf(dummyEntry); 86 if (index < 0) { 87 // Create a new cache entry. 88 sp<Blob> keyBlob(new Blob(key, keySize, true)); 89 sp<Blob> valueBlob(new Blob(value, valueSize, true)); 90 size_t newTotalSize = mTotalSize + keySize + valueSize; 91 if (mMaxTotalSize < newTotalSize) { 92 if (isCleanable()) { 93 // Clean the cache and try again. 94 clean(); 95 continue; 96 } else { 97 ALOGV("set: not caching new key/value pair because the " 98 "total cache size limit would be exceeded: %zu " 99 "(limit: %zu)", 100 keySize + valueSize, mMaxTotalSize); 101 break; 102 } 103 } 104 mCacheEntries.add(CacheEntry(keyBlob, valueBlob)); 105 mTotalSize = newTotalSize; 106 ALOGV("set: created new cache entry with %zu byte key and %zu byte value", 107 keySize, valueSize); 108 } else { 109 // Update the existing cache entry. 110 sp<Blob> valueBlob(new Blob(value, valueSize, true)); 111 sp<Blob> oldValueBlob(mCacheEntries[index].getValue()); 112 size_t newTotalSize = mTotalSize + valueSize - oldValueBlob->getSize(); 113 if (mMaxTotalSize < newTotalSize) { 114 if (isCleanable()) { 115 // Clean the cache and try again. 116 clean(); 117 continue; 118 } else { 119 ALOGV("set: not caching new value because the total cache " 120 "size limit would be exceeded: %zu (limit: %zu)", 121 keySize + valueSize, mMaxTotalSize); 122 break; 123 } 124 } 125 mCacheEntries.editItemAt(index).setValue(valueBlob); 126 mTotalSize = newTotalSize; 127 ALOGV("set: updated existing cache entry with %zu byte key and %zu byte " 128 "value", keySize, valueSize); 129 } 130 break; 131 } 132} 133 134size_t BlobCache::get(const void* key, size_t keySize, void* value, 135 size_t valueSize) { 136 if (mMaxKeySize < keySize) { 137 ALOGV("get: not searching because the key is too large: %zu (limit %zu)", 138 keySize, mMaxKeySize); 139 return 0; 140 } 141 sp<Blob> dummyKey(new Blob(key, keySize, false)); 142 CacheEntry dummyEntry(dummyKey, NULL); 143 ssize_t index = mCacheEntries.indexOf(dummyEntry); 144 if (index < 0) { 145 ALOGV("get: no cache entry found for key of size %zu", keySize); 146 return 0; 147 } 148 149 // The key was found. Return the value if the caller's buffer is large 150 // enough. 151 sp<Blob> valueBlob(mCacheEntries[index].getValue()); 152 size_t valueBlobSize = valueBlob->getSize(); 153 if (valueBlobSize <= valueSize) { 154 ALOGV("get: copying %zu bytes to caller's buffer", valueBlobSize); 155 memcpy(value, valueBlob->getData(), valueBlobSize); 156 } else { 157 ALOGV("get: caller's buffer is too small for value: %zu (needs %zu)", 158 valueSize, valueBlobSize); 159 } 160 return valueBlobSize; 161} 162 163static inline size_t align4(size_t size) { 164 return (size + 3) & ~3; 165} 166 167size_t BlobCache::getFlattenedSize() const { 168 size_t size = sizeof(Header); 169 for (size_t i = 0; i < mCacheEntries.size(); i++) { 170 const CacheEntry& e(mCacheEntries[i]); 171 sp<Blob> keyBlob = e.getKey(); 172 sp<Blob> valueBlob = e.getValue(); 173 size = align4(size); 174 size += sizeof(EntryHeader) + keyBlob->getSize() + 175 valueBlob->getSize(); 176 } 177 return size; 178} 179 180status_t BlobCache::flatten(void* buffer, size_t size) const { 181 // Write the cache header 182 if (size < sizeof(Header)) { 183 ALOGE("flatten: not enough room for cache header"); 184 return BAD_VALUE; 185 } 186 Header* header = reinterpret_cast<Header*>(buffer); 187 header->mMagicNumber = blobCacheMagic; 188 header->mBlobCacheVersion = blobCacheVersion; 189 header->mDeviceVersion = blobCacheDeviceVersion; 190 header->mNumEntries = mCacheEntries.size(); 191 192 // Write cache entries 193 uint8_t* byteBuffer = reinterpret_cast<uint8_t*>(buffer); 194 off_t byteOffset = align4(sizeof(Header)); 195 for (size_t i = 0; i < mCacheEntries.size(); i++) { 196 const CacheEntry& e(mCacheEntries[i]); 197 sp<Blob> keyBlob = e.getKey(); 198 sp<Blob> valueBlob = e.getValue(); 199 size_t keySize = keyBlob->getSize(); 200 size_t valueSize = valueBlob->getSize(); 201 202 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 203 if (byteOffset + entrySize > size) { 204 ALOGE("flatten: not enough room for cache entries"); 205 return BAD_VALUE; 206 } 207 208 EntryHeader* eheader = reinterpret_cast<EntryHeader*>( 209 &byteBuffer[byteOffset]); 210 eheader->mKeySize = keySize; 211 eheader->mValueSize = valueSize; 212 213 memcpy(eheader->mData, keyBlob->getData(), keySize); 214 memcpy(eheader->mData + keySize, valueBlob->getData(), valueSize); 215 216 byteOffset += align4(entrySize); 217 } 218 219 return OK; 220} 221 222status_t BlobCache::unflatten(void const* buffer, size_t size) { 223 // All errors should result in the BlobCache being in an empty state. 224 mCacheEntries.clear(); 225 226 // Read the cache header 227 if (size < sizeof(Header)) { 228 ALOGE("unflatten: not enough room for cache header"); 229 return BAD_VALUE; 230 } 231 const Header* header = reinterpret_cast<const Header*>(buffer); 232 if (header->mMagicNumber != blobCacheMagic) { 233 ALOGE("unflatten: bad magic number: %" PRIu32, header->mMagicNumber); 234 return BAD_VALUE; 235 } 236 if (header->mBlobCacheVersion != blobCacheVersion || 237 header->mDeviceVersion != blobCacheDeviceVersion) { 238 // We treat version mismatches as an empty cache. 239 return OK; 240 } 241 242 // Read cache entries 243 const uint8_t* byteBuffer = reinterpret_cast<const uint8_t*>(buffer); 244 off_t byteOffset = align4(sizeof(Header)); 245 size_t numEntries = header->mNumEntries; 246 for (size_t i = 0; i < numEntries; i++) { 247 if (byteOffset + sizeof(EntryHeader) > size) { 248 mCacheEntries.clear(); 249 ALOGE("unflatten: not enough room for cache entry headers"); 250 return BAD_VALUE; 251 } 252 253 const EntryHeader* eheader = reinterpret_cast<const EntryHeader*>( 254 &byteBuffer[byteOffset]); 255 size_t keySize = eheader->mKeySize; 256 size_t valueSize = eheader->mValueSize; 257 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 258 259 if (byteOffset + entrySize > size) { 260 mCacheEntries.clear(); 261 ALOGE("unflatten: not enough room for cache entry headers"); 262 return BAD_VALUE; 263 } 264 265 const uint8_t* data = eheader->mData; 266 set(data, keySize, data + keySize, valueSize); 267 268 byteOffset += align4(entrySize); 269 } 270 271 return OK; 272} 273 274long int BlobCache::blob_random() { 275#ifdef _WIN32 276 return rand(); 277#else 278 return nrand48(mRandState); 279#endif 280} 281 282void BlobCache::clean() { 283 // Remove a random cache entry until the total cache size gets below half 284 // the maximum total cache size. 285 while (mTotalSize > mMaxTotalSize / 2) { 286 size_t i = size_t(blob_random() % (mCacheEntries.size())); 287 const CacheEntry& entry(mCacheEntries[i]); 288 mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize(); 289 mCacheEntries.removeAt(i); 290 } 291} 292 293bool BlobCache::isCleanable() const { 294 return mTotalSize > mMaxTotalSize / 2; 295} 296 297BlobCache::Blob::Blob(const void* data, size_t size, bool copyData): 298 mData(copyData ? malloc(size) : data), 299 mSize(size), 300 mOwnsData(copyData) { 301 if (data != NULL && copyData) { 302 memcpy(const_cast<void*>(mData), data, size); 303 } 304} 305 306BlobCache::Blob::~Blob() { 307 if (mOwnsData) { 308 free(const_cast<void*>(mData)); 309 } 310} 311 312bool BlobCache::Blob::operator<(const Blob& rhs) const { 313 if (mSize == rhs.mSize) { 314 return memcmp(mData, rhs.mData, mSize) < 0; 315 } else { 316 return mSize < rhs.mSize; 317 } 318} 319 320const void* BlobCache::Blob::getData() const { 321 return mData; 322} 323 324size_t BlobCache::Blob::getSize() const { 325 return mSize; 326} 327 328BlobCache::CacheEntry::CacheEntry() { 329} 330 331BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value): 332 mKey(key), 333 mValue(value) { 334} 335 336BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce): 337 mKey(ce.mKey), 338 mValue(ce.mValue) { 339} 340 341bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const { 342 return *mKey < *rhs.mKey; 343} 344 345const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) { 346 mKey = rhs.mKey; 347 mValue = rhs.mValue; 348 return *this; 349} 350 351sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const { 352 return mKey; 353} 354 355sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const { 356 return mValue; 357} 358 359void BlobCache::CacheEntry::setValue(const sp<Blob>& value) { 360 mValue = value; 361} 362 363} // namespace android 364