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 <stdlib.h> 21 #include <string.h> 22 23 #include <utils/BlobCache.h> 24 #include <utils/Errors.h> 25 #include <utils/Log.h> 26 27 namespace android { 28 29 // BlobCache::Header::mMagicNumber value 30 static const uint32_t blobCacheMagic = '_Bb$'; 31 32 // BlobCache::Header::mBlobCacheVersion value 33 static const uint32_t blobCacheVersion = 1; 34 35 // BlobCache::Header::mDeviceVersion value 36 static const uint32_t blobCacheDeviceVersion = 1; 37 38 BlobCache::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 LOGV("initializing random seed using %lld", now); 52 } 53 54 void BlobCache::set(const void* key, size_t keySize, const void* value, 55 size_t valueSize) { 56 if (mMaxKeySize < keySize) { 57 LOGV("set: not caching because the key is too large: %d (limit: %d)", 58 keySize, mMaxKeySize); 59 return; 60 } 61 if (mMaxValueSize < valueSize) { 62 LOGV("set: not caching because the value is too large: %d (limit: %d)", 63 valueSize, mMaxValueSize); 64 return; 65 } 66 if (mMaxTotalSize < keySize + valueSize) { 67 LOGV("set: not caching because the combined key/value size is too " 68 "large: %d (limit: %d)", keySize + valueSize, mMaxTotalSize); 69 return; 70 } 71 if (keySize == 0) { 72 LOGW("set: not caching because keySize is 0"); 73 return; 74 } 75 if (valueSize <= 0) { 76 LOGW("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 LOGV("set: not caching new key/value pair because the " 97 "total cache size limit would be exceeded: %d " 98 "(limit: %d)", 99 keySize + valueSize, mMaxTotalSize); 100 break; 101 } 102 } 103 mCacheEntries.add(CacheEntry(keyBlob, valueBlob)); 104 mTotalSize = newTotalSize; 105 LOGV("set: created new cache entry with %d byte key and %d 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 LOGV("set: not caching new value because the total cache " 119 "size limit would be exceeded: %d (limit: %d)", 120 keySize + valueSize, mMaxTotalSize); 121 break; 122 } 123 } 124 mCacheEntries.editItemAt(index).setValue(valueBlob); 125 mTotalSize = newTotalSize; 126 LOGV("set: updated existing cache entry with %d byte key and %d byte " 127 "value", keySize, valueSize); 128 } 129 break; 130 } 131 } 132 133 size_t BlobCache::get(const void* key, size_t keySize, void* value, 134 size_t valueSize) { 135 if (mMaxKeySize < keySize) { 136 LOGV("get: not searching because the key is too large: %d (limit %d)", 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 LOGV("get: no cache entry found for key of size %d", 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 LOGV("get: copying %d bytes to caller's buffer", valueBlobSize); 154 memcpy(value, valueBlob->getData(), valueBlobSize); 155 } else { 156 LOGV("get: caller's buffer is too small for value: %d (needs %d)", 157 valueSize, valueBlobSize); 158 } 159 return valueBlobSize; 160 } 161 162 static inline size_t align4(size_t size) { 163 return (size + 3) & ~3; 164 } 165 166 size_t BlobCache::getFlattenedSize() const { 167 size_t size = sizeof(Header); 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(size); 173 size += sizeof(EntryHeader) + keyBlob->getSize() + 174 valueBlob->getSize(); 175 } 176 return size; 177 } 178 179 size_t BlobCache::getFdCount() const { 180 return 0; 181 } 182 183 status_t BlobCache::flatten(void* buffer, size_t size, int fds[], size_t count) 184 const { 185 if (count != 0) { 186 LOGE("flatten: nonzero fd count: %d", count); 187 return BAD_VALUE; 188 } 189 190 // Write the cache header 191 if (size < sizeof(Header)) { 192 LOGE("flatten: not enough room for cache header"); 193 return BAD_VALUE; 194 } 195 Header* header = reinterpret_cast<Header*>(buffer); 196 header->mMagicNumber = blobCacheMagic; 197 header->mBlobCacheVersion = blobCacheVersion; 198 header->mDeviceVersion = blobCacheDeviceVersion; 199 header->mNumEntries = mCacheEntries.size(); 200 201 // Write cache entries 202 uint8_t* byteBuffer = reinterpret_cast<uint8_t*>(buffer); 203 off_t byteOffset = align4(sizeof(Header)); 204 for (size_t i = 0; i < mCacheEntries.size(); i++) { 205 const CacheEntry& e(mCacheEntries[i]); 206 sp<Blob> keyBlob = e.getKey(); 207 sp<Blob> valueBlob = e.getValue(); 208 size_t keySize = keyBlob->getSize(); 209 size_t valueSize = valueBlob->getSize(); 210 211 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 212 if (byteOffset + entrySize > size) { 213 LOGE("flatten: not enough room for cache entries"); 214 return BAD_VALUE; 215 } 216 217 EntryHeader* eheader = reinterpret_cast<EntryHeader*>( 218 &byteBuffer[byteOffset]); 219 eheader->mKeySize = keySize; 220 eheader->mValueSize = valueSize; 221 222 memcpy(eheader->mData, keyBlob->getData(), keySize); 223 memcpy(eheader->mData + keySize, valueBlob->getData(), valueSize); 224 225 byteOffset += align4(entrySize); 226 } 227 228 return OK; 229 } 230 231 status_t BlobCache::unflatten(void const* buffer, size_t size, int fds[], 232 size_t count) { 233 // All errors should result in the BlobCache being in an empty state. 234 mCacheEntries.clear(); 235 236 if (count != 0) { 237 LOGE("unflatten: nonzero fd count: %d", count); 238 return BAD_VALUE; 239 } 240 241 // Read the cache header 242 if (size < sizeof(Header)) { 243 LOGE("unflatten: not enough room for cache header"); 244 return BAD_VALUE; 245 } 246 const Header* header = reinterpret_cast<const Header*>(buffer); 247 if (header->mMagicNumber != blobCacheMagic) { 248 LOGE("unflatten: bad magic number: %d", header->mMagicNumber); 249 return BAD_VALUE; 250 } 251 if (header->mBlobCacheVersion != blobCacheVersion || 252 header->mDeviceVersion != blobCacheDeviceVersion) { 253 // We treat version mismatches as an empty cache. 254 return OK; 255 } 256 257 // Read cache entries 258 const uint8_t* byteBuffer = reinterpret_cast<const uint8_t*>(buffer); 259 off_t byteOffset = align4(sizeof(Header)); 260 size_t numEntries = header->mNumEntries; 261 for (size_t i = 0; i < numEntries; i++) { 262 if (byteOffset + sizeof(EntryHeader) > size) { 263 mCacheEntries.clear(); 264 LOGE("unflatten: not enough room for cache entry headers"); 265 return BAD_VALUE; 266 } 267 268 const EntryHeader* eheader = reinterpret_cast<const EntryHeader*>( 269 &byteBuffer[byteOffset]); 270 size_t keySize = eheader->mKeySize; 271 size_t valueSize = eheader->mValueSize; 272 size_t entrySize = sizeof(EntryHeader) + keySize + valueSize; 273 274 if (byteOffset + entrySize > size) { 275 mCacheEntries.clear(); 276 LOGE("unflatten: not enough room for cache entry headers"); 277 return BAD_VALUE; 278 } 279 280 const uint8_t* data = eheader->mData; 281 set(data, keySize, data + keySize, valueSize); 282 283 byteOffset += align4(entrySize); 284 } 285 286 return OK; 287 } 288 289 long int BlobCache::blob_random() { 290 #ifdef _WIN32 291 return rand(); 292 #else 293 return nrand48(mRandState); 294 #endif 295 } 296 297 void BlobCache::clean() { 298 // Remove a random cache entry until the total cache size gets below half 299 // the maximum total cache size. 300 while (mTotalSize > mMaxTotalSize / 2) { 301 size_t i = size_t(blob_random() % (mCacheEntries.size())); 302 const CacheEntry& entry(mCacheEntries[i]); 303 mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize(); 304 mCacheEntries.removeAt(i); 305 } 306 } 307 308 bool BlobCache::isCleanable() const { 309 return mTotalSize > mMaxTotalSize / 2; 310 } 311 312 BlobCache::Blob::Blob(const void* data, size_t size, bool copyData): 313 mData(copyData ? malloc(size) : data), 314 mSize(size), 315 mOwnsData(copyData) { 316 if (data != NULL && copyData) { 317 memcpy(const_cast<void*>(mData), data, size); 318 } 319 } 320 321 BlobCache::Blob::~Blob() { 322 if (mOwnsData) { 323 free(const_cast<void*>(mData)); 324 } 325 } 326 327 bool BlobCache::Blob::operator<(const Blob& rhs) const { 328 if (mSize == rhs.mSize) { 329 return memcmp(mData, rhs.mData, mSize) < 0; 330 } else { 331 return mSize < rhs.mSize; 332 } 333 } 334 335 const void* BlobCache::Blob::getData() const { 336 return mData; 337 } 338 339 size_t BlobCache::Blob::getSize() const { 340 return mSize; 341 } 342 343 BlobCache::CacheEntry::CacheEntry() { 344 } 345 346 BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value): 347 mKey(key), 348 mValue(value) { 349 } 350 351 BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce): 352 mKey(ce.mKey), 353 mValue(ce.mValue) { 354 } 355 356 bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const { 357 return *mKey < *rhs.mKey; 358 } 359 360 const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) { 361 mKey = rhs.mKey; 362 mValue = rhs.mValue; 363 return *this; 364 } 365 366 sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const { 367 return mKey; 368 } 369 370 sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const { 371 return mValue; 372 } 373 374 void BlobCache::CacheEntry::setValue(const sp<Blob>& value) { 375 mValue = value; 376 } 377 378 } // namespace android 379