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 #ifndef ANDROID_BLOB_CACHE_H 18 #define ANDROID_BLOB_CACHE_H 19 20 #include <stddef.h> 21 22 #include <memory> 23 #include <vector> 24 25 namespace android { 26 27 // A BlobCache is an in-memory cache for binary key/value pairs. A BlobCache 28 // does NOT provide any thread-safety guarantees. 29 // 30 // The cache contents can be serialized to an in-memory buffer or mmap'd file 31 // and then reloaded in a subsequent execution of the program. This 32 // serialization is non-portable and the data should only be used by the device 33 // that generated it. 34 class BlobCache { 35 public: 36 // Create an empty blob cache. The blob cache will cache key/value pairs 37 // with key and value sizes less than or equal to maxKeySize and 38 // maxValueSize, respectively. The total combined size of ALL cache entries 39 // (key sizes plus value sizes) will not exceed maxTotalSize. 40 BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize); 41 42 // set inserts a new binary value into the cache and associates it with the 43 // given binary key. If the key or value are too large for the cache then 44 // the cache remains unchanged. This includes the case where a different 45 // value was previously associated with the given key - the old value will 46 // remain in the cache. If the given key and value are small enough to be 47 // put in the cache (based on the maxKeySize, maxValueSize, and maxTotalSize 48 // values specified to the BlobCache constructor), then the key/value pair 49 // will be in the cache after set returns. Note, however, that a subsequent 50 // call to set may evict old key/value pairs from the cache. 51 // 52 // Preconditions: 53 // key != NULL 54 // 0 < keySize 55 // value != NULL 56 // 0 < valueSize 57 void set(const void* key, size_t keySize, const void* value, 58 size_t valueSize); 59 60 // get retrieves from the cache the binary value associated with a given 61 // binary key. If the key is present in the cache then the length of the 62 // binary value associated with that key is returned. If the value argument 63 // is non-NULL and the size of the cached value is less than valueSize bytes 64 // then the cached value is copied into the buffer pointed to by the value 65 // argument. If the key is not present in the cache then 0 is returned and 66 // the buffer pointed to by the value argument is not modified. 67 // 68 // Note that when calling get multiple times with the same key, the later 69 // calls may fail, returning 0, even if earlier calls succeeded. The return 70 // value must be checked for each call. 71 // 72 // Preconditions: 73 // key != NULL 74 // 0 < keySize 75 // 0 <= valueSize 76 size_t get(const void* key, size_t keySize, void* value, size_t valueSize); 77 78 79 // getFlattenedSize returns the number of bytes needed to store the entire 80 // serialized cache. 81 size_t getFlattenedSize() const; 82 83 // flatten serializes the current contents of the cache into the memory 84 // pointed to by 'buffer'. The serialized cache contents can later be 85 // loaded into a BlobCache object using the unflatten method. The contents 86 // of the BlobCache object will not be modified. 87 // 88 // Preconditions: 89 // size >= this.getFlattenedSize() 90 int flatten(void* buffer, size_t size) const; 91 92 // unflatten replaces the contents of the cache with the serialized cache 93 // contents in the memory pointed to by 'buffer'. The previous contents of 94 // the BlobCache will be evicted from the cache. If an error occurs while 95 // unflattening the serialized cache contents then the BlobCache will be 96 // left in an empty state. 97 // 98 int unflatten(void const* buffer, size_t size); 99 100 private: 101 // Copying is disallowed. 102 BlobCache(const BlobCache&); 103 void operator=(const BlobCache&); 104 105 // A random function helper to get around MinGW not having nrand48() 106 long int blob_random(); 107 108 // clean evicts a randomly chosen set of entries from the cache such that 109 // the total size of all remaining entries is less than mMaxTotalSize/2. 110 void clean(); 111 112 // isCleanable returns true if the cache is full enough for the clean method 113 // to have some effect, and false otherwise. 114 bool isCleanable() const; 115 116 // A Blob is an immutable sized unstructured data blob. 117 class Blob { 118 public: 119 Blob(const void* data, size_t size, bool copyData); 120 ~Blob(); 121 122 bool operator<(const Blob& rhs) const; 123 124 const void* getData() const; 125 size_t getSize() const; 126 127 private: 128 // Copying is not allowed. 129 Blob(const Blob&); 130 void operator=(const Blob&); 131 132 // mData points to the buffer containing the blob data. 133 const void* mData; 134 135 // mSize is the size of the blob data in bytes. 136 size_t mSize; 137 138 // mOwnsData indicates whether or not this Blob object should free the 139 // memory pointed to by mData when the Blob gets destructed. 140 bool mOwnsData; 141 }; 142 143 // A CacheEntry is a single key/value pair in the cache. 144 class CacheEntry { 145 public: 146 CacheEntry(); 147 CacheEntry(const std::shared_ptr<Blob>& key, const std::shared_ptr<Blob>& value); 148 CacheEntry(const CacheEntry& ce); 149 150 bool operator<(const CacheEntry& rhs) const; 151 const CacheEntry& operator=(const CacheEntry&); 152 153 std::shared_ptr<Blob> getKey() const; 154 std::shared_ptr<Blob> getValue() const; 155 156 void setValue(const std::shared_ptr<Blob>& value); 157 158 private: 159 160 // mKey is the key that identifies the cache entry. 161 std::shared_ptr<Blob> mKey; 162 163 // mValue is the cached data associated with the key. 164 std::shared_ptr<Blob> mValue; 165 }; 166 167 // A Header is the header for the entire BlobCache serialization format. No 168 // need to make this portable, so we simply write the struct out. 169 struct Header { 170 // mMagicNumber is the magic number that identifies the data as 171 // serialized BlobCache contents. It must always contain 'Blb$'. 172 uint32_t mMagicNumber; 173 174 // mBlobCacheVersion is the serialization format version. 175 uint32_t mBlobCacheVersion; 176 177 // mDeviceVersion is the device-specific version of the cache. This can 178 // be used to invalidate the cache. 179 uint32_t mDeviceVersion; 180 181 // mNumEntries is number of cache entries following the header in the 182 // data. 183 size_t mNumEntries; 184 185 // mBuildId is the build id of the device when the cache was created. 186 // When an update to the build happens (via an OTA or other update) this 187 // is used to invalidate the cache. 188 int mBuildIdLength; 189 char mBuildId[]; 190 }; 191 192 // An EntryHeader is the header for a serialized cache entry. No need to 193 // make this portable, so we simply write the struct out. Each EntryHeader 194 // is followed imediately by the key data and then the value data. 195 // 196 // The beginning of each serialized EntryHeader is 4-byte aligned, so the 197 // number of bytes that a serialized cache entry will occupy is: 198 // 199 // ((sizeof(EntryHeader) + keySize + valueSize) + 3) & ~3 200 // 201 struct EntryHeader { 202 // mKeySize is the size of the entry key in bytes. 203 size_t mKeySize; 204 205 // mValueSize is the size of the entry value in bytes. 206 size_t mValueSize; 207 208 // mData contains both the key and value data for the cache entry. The 209 // key comes first followed immediately by the value. 210 uint8_t mData[]; 211 }; 212 213 // mMaxKeySize is the maximum key size that will be cached. Calls to 214 // BlobCache::set with a keySize parameter larger than mMaxKeySize will 215 // simply not add the key/value pair to the cache. 216 const size_t mMaxKeySize; 217 218 // mMaxValueSize is the maximum value size that will be cached. Calls to 219 // BlobCache::set with a valueSize parameter larger than mMaxValueSize will 220 // simply not add the key/value pair to the cache. 221 const size_t mMaxValueSize; 222 223 // mMaxTotalSize is the maximum size that all cache entries can occupy. This 224 // includes space for both keys and values. When a call to BlobCache::set 225 // would otherwise cause this limit to be exceeded, either the key/value 226 // pair passed to BlobCache::set will not be cached or other cache entries 227 // will be evicted from the cache to make room for the new entry. 228 const size_t mMaxTotalSize; 229 230 // mTotalSize is the total combined size of all keys and values currently in 231 // the cache. 232 size_t mTotalSize; 233 234 // mRandState is the pseudo-random number generator state. It is passed to 235 // nrand48 to generate random numbers when needed. 236 unsigned short mRandState[3]; 237 238 // mCacheEntries stores all the cache entries that are resident in memory. 239 // Cache entries are added to it by the 'set' method. 240 std::vector<CacheEntry> mCacheEntries; 241 }; 242 243 } 244 245 #endif // ANDROID_BLOB_CACHE_H 246