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