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 = 2; 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 = align4(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(sizeof(EntryHeader) + keyBlob->getSize() + 174 valueBlob->getSize()); 175 } 176 return size; 177} 178 179status_t BlobCache::flatten(void* buffer, size_t size) const { 180 // Write the cache header 181 if (size < sizeof(Header)) { 182 ALOGE("flatten: not enough room for cache header"); 183 return BAD_VALUE; 184 } 185 Header* header = reinterpret_cast<Header*>(buffer); 186 header->mMagicNumber = blobCacheMagic; 187 header->mBlobCacheVersion = blobCacheVersion; 188 header->mDeviceVersion = blobCacheDeviceVersion; 189 header->mNumEntries = mCacheEntries.size(); 190 191 // Write cache entries 192 uint8_t* byteBuffer = reinterpret_cast<uint8_t*>(buffer); 193 off_t byteOffset = align4(sizeof(Header)); 194 for (size_t i = 0; i < mCacheEntries.size(); i++) { 195 const CacheEntry& e(mCacheEntries[i]); 196 sp<Blob> keyBlob = e.getKey(); 197 sp<Blob> valueBlob = e.getValue(); 198 size_t keySize = keyBlob->getSize(); 199 size_t valueSize = valueBlob->getSize(); 200 201 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 202 size_t totalSize = align4(entrySize); 203 if (byteOffset + totalSize > 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 if (totalSize > entrySize) { 217 // We have padding bytes. Those will get written to storage, and contribute to the CRC, 218 // so make sure we zero-them to have reproducible results. 219 memset(eheader->mData + keySize + valueSize, 0, totalSize - entrySize); 220 } 221 222 byteOffset += totalSize; 223 } 224 225 return OK; 226} 227 228status_t BlobCache::unflatten(void const* buffer, size_t size) { 229 // All errors should result in the BlobCache being in an empty state. 230 mCacheEntries.clear(); 231 232 // Read the cache header 233 if (size < sizeof(Header)) { 234 ALOGE("unflatten: not enough room for cache header"); 235 return BAD_VALUE; 236 } 237 const Header* header = reinterpret_cast<const Header*>(buffer); 238 if (header->mMagicNumber != blobCacheMagic) { 239 ALOGE("unflatten: bad magic number: %" PRIu32, header->mMagicNumber); 240 return BAD_VALUE; 241 } 242 if (header->mBlobCacheVersion != blobCacheVersion || 243 header->mDeviceVersion != blobCacheDeviceVersion) { 244 // We treat version mismatches as an empty cache. 245 return OK; 246 } 247 248 // Read cache entries 249 const uint8_t* byteBuffer = reinterpret_cast<const uint8_t*>(buffer); 250 off_t byteOffset = align4(sizeof(Header)); 251 size_t numEntries = header->mNumEntries; 252 for (size_t i = 0; i < numEntries; i++) { 253 if (byteOffset + sizeof(EntryHeader) > size) { 254 mCacheEntries.clear(); 255 ALOGE("unflatten: not enough room for cache entry headers"); 256 return BAD_VALUE; 257 } 258 259 const EntryHeader* eheader = reinterpret_cast<const EntryHeader*>( 260 &byteBuffer[byteOffset]); 261 size_t keySize = eheader->mKeySize; 262 size_t valueSize = eheader->mValueSize; 263 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 264 265 size_t totalSize = align4(entrySize); 266 if (byteOffset + totalSize > size) { 267 mCacheEntries.clear(); 268 ALOGE("unflatten: not enough room for cache entry headers"); 269 return BAD_VALUE; 270 } 271 272 const uint8_t* data = eheader->mData; 273 set(data, keySize, data + keySize, valueSize); 274 275 byteOffset += totalSize; 276 } 277 278 return OK; 279} 280 281long int BlobCache::blob_random() { 282#ifdef _WIN32 283 return rand(); 284#else 285 return nrand48(mRandState); 286#endif 287} 288 289void BlobCache::clean() { 290 // Remove a random cache entry until the total cache size gets below half 291 // the maximum total cache size. 292 while (mTotalSize > mMaxTotalSize / 2) { 293 size_t i = size_t(blob_random() % (mCacheEntries.size())); 294 const CacheEntry& entry(mCacheEntries[i]); 295 mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize(); 296 mCacheEntries.removeAt(i); 297 } 298} 299 300bool BlobCache::isCleanable() const { 301 return mTotalSize > mMaxTotalSize / 2; 302} 303 304BlobCache::Blob::Blob(const void* data, size_t size, bool copyData): 305 mData(copyData ? malloc(size) : data), 306 mSize(size), 307 mOwnsData(copyData) { 308 if (data != NULL && copyData) { 309 memcpy(const_cast<void*>(mData), data, size); 310 } 311} 312 313BlobCache::Blob::~Blob() { 314 if (mOwnsData) { 315 free(const_cast<void*>(mData)); 316 } 317} 318 319bool BlobCache::Blob::operator<(const Blob& rhs) const { 320 if (mSize == rhs.mSize) { 321 return memcmp(mData, rhs.mData, mSize) < 0; 322 } else { 323 return mSize < rhs.mSize; 324 } 325} 326 327const void* BlobCache::Blob::getData() const { 328 return mData; 329} 330 331size_t BlobCache::Blob::getSize() const { 332 return mSize; 333} 334 335BlobCache::CacheEntry::CacheEntry() { 336} 337 338BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value): 339 mKey(key), 340 mValue(value) { 341} 342 343BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce): 344 mKey(ce.mKey), 345 mValue(ce.mValue) { 346} 347 348bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const { 349 return *mKey < *rhs.mKey; 350} 351 352const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) { 353 mKey = rhs.mKey; 354 mValue = rhs.mValue; 355 return *this; 356} 357 358sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const { 359 return mKey; 360} 361 362sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const { 363 return mValue; 364} 365 366void BlobCache::CacheEntry::setValue(const sp<Blob>& value) { 367 mValue = value; 368} 369 370} // namespace android 371