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 namespace android {
     29 
     30 // BlobCache::Header::mMagicNumber value
     31 static const uint32_t blobCacheMagic = ('_' << 24) + ('B' << 16) + ('b' << 8) + '$';
     32 
     33 // BlobCache::Header::mBlobCacheVersion value
     34 static const uint32_t blobCacheVersion = 2;
     35 
     36 // BlobCache::Header::mDeviceVersion value
     37 static const uint32_t blobCacheDeviceVersion = 1;
     38 
     39 BlobCache::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 
     55 void 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 
    134 size_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 
    163 static inline size_t align4(size_t size) {
    164     return (size + 3) & ~3;
    165 }
    166 
    167 size_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 
    179 status_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 
    228 status_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 
    281 long int BlobCache::blob_random() {
    282 #ifdef _WIN32
    283     return rand();
    284 #else
    285     return nrand48(mRandState);
    286 #endif
    287 }
    288 
    289 void 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 
    300 bool BlobCache::isCleanable() const {
    301     return mTotalSize > mMaxTotalSize / 2;
    302 }
    303 
    304 BlobCache::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 
    313 BlobCache::Blob::~Blob() {
    314     if (mOwnsData) {
    315         free(const_cast<void*>(mData));
    316     }
    317 }
    318 
    319 bool 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 
    327 const void* BlobCache::Blob::getData() const {
    328     return mData;
    329 }
    330 
    331 size_t BlobCache::Blob::getSize() const {
    332     return mSize;
    333 }
    334 
    335 BlobCache::CacheEntry::CacheEntry() {
    336 }
    337 
    338 BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value):
    339         mKey(key),
    340         mValue(value) {
    341 }
    342 
    343 BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce):
    344         mKey(ce.mKey),
    345         mValue(ce.mValue) {
    346 }
    347 
    348 bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const {
    349     return *mKey < *rhs.mKey;
    350 }
    351 
    352 const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) {
    353     mKey = rhs.mKey;
    354     mValue = rhs.mValue;
    355     return *this;
    356 }
    357 
    358 sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const {
    359     return mKey;
    360 }
    361 
    362 sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const {
    363     return mValue;
    364 }
    365 
    366 void BlobCache::CacheEntry::setValue(const sp<Blob>& value) {
    367     mValue = value;
    368 }
    369 
    370 } // namespace android
    371