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