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 <functional> 23 #include <memory> 24 #include <utility> 25 #include <vector> 26 27 namespace android { 28 29 // A BlobCache is an in-memory cache for binary key/value pairs. A BlobCache 30 // does NOT provide any thread-safety guarantees. 31 // 32 // The cache contents can be serialized to an in-memory buffer or mmap'd file 33 // and then reloaded in a subsequent execution of the program. This 34 // serialization is non-portable and the data should only be used by the device 35 // that generated it. 36 class BlobCache { 37 public: 38 enum class Select { 39 RANDOM, // evict random entries 40 LRU, // evict least-recently-used entries 41 42 DEFAULT = RANDOM, 43 }; 44 45 enum class Capacity { 46 // cut back to no more than half capacity; new/replacement 47 // entry still might not fit 48 HALVE, 49 50 // cut back to whatever is necessary to fit new/replacement 51 // entry 52 FIT, 53 54 // cut back to no more than half capacity and ensure that 55 // there's enough space for new/replacement entry 56 FIT_HALVE, 57 58 DEFAULT = HALVE, 59 }; 60 61 // When we're inserting or replacing an entry in the cache, and 62 // there's not enough space, how do we clean the cache? 63 typedef std::pair<Select, Capacity> Policy; 64 65 static Policy defaultPolicy() { return Policy(Select::DEFAULT, Capacity::DEFAULT); } 66 67 // Create an empty blob cache. The blob cache will cache key/value pairs 68 // with key and value sizes less than or equal to maxKeySize and 69 // maxValueSize, respectively. The total combined size of ALL cache entries 70 // (key sizes plus value sizes) will not exceed maxTotalSize. 71 BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize, 72 Policy policy = defaultPolicy()); 73 74 // set inserts a new binary value into the cache and associates it with the 75 // given binary key. If the key or value are too large for the cache then 76 // the cache remains unchanged. This includes the case where a different 77 // value was previously associated with the given key - the old value will 78 // remain in the cache. If the given key and value are small enough to be 79 // put in the cache (based on the maxKeySize, maxValueSize, and maxTotalSize 80 // values specified to the BlobCache constructor), then the key/value pair 81 // will be in the cache after set returns. Note, however, that a subsequent 82 // call to set may evict old key/value pairs from the cache. 83 // 84 // Preconditions: 85 // key != NULL 86 // 0 < keySize 87 // value != NULL 88 // 0 < valueSize 89 void set(const void* key, size_t keySize, const void* value, 90 size_t valueSize); 91 92 // get retrieves from the cache the binary value associated with a given 93 // binary key. If the key is present in the cache then the length of the 94 // binary value associated with that key is returned. If the key 95 // is not present in the cache then 0 is returned. 96 // 97 // There are two variants of get: one takes a buffer (value, valueSize) 98 // and one takes an allocator (value, alloc). 99 // 100 // For the BUFFER variant, if the value argument is non-NULL and 101 // the size of the cached value is less than valueSize bytes then 102 // the cached value is copied into the buffer pointed to by the 103 // value argument. If the key is not present in the cache then 104 // the buffer pointed to by the value argument is not modified. 105 // 106 // Preconditions: 107 // key != NULL 108 // 0 < keySize 109 // 0 <= valueSize 110 // 111 // For the ALLOCATOR variant, if it is possible to allocate a 112 // buffer for the cached value via a call to the allocator by 113 // 114 // size_t cached_value_size = ...; 115 // void* buf = alloc(cached_value_size); 116 // 117 // then the cached value is copied into the newly-allocated buffer 118 // and *value is set to the address of the newly-allocated buffer. 119 // If the allocator returns NULL, or the key is not present in the 120 // cache, then *value is set to NULL. 121 // 122 // Preconditions: 123 // key != NULL 124 // 0 < keySize 125 // value != NULL 126 // 127 // Note that when calling get multiple times with the same key, the later 128 // calls may fail, returning 0, even if earlier calls succeeded. The return 129 // value must be checked for each call. 130 size_t get(const void* key, size_t keySize, void* value, size_t valueSize); 131 size_t get(const void* key, size_t keySize, void** value, std::function<void*(size_t)> alloc); 132 template <typename T> 133 size_t get(const void* key, size_t keySize, T** value, std::function<void*(size_t)> alloc) { 134 void *valueVoid; 135 const size_t size = get(key, keySize, &valueVoid, alloc); 136 *value = static_cast<T*>(valueVoid); 137 return size; 138 } 139 140 // getFlattenedSize returns the number of bytes needed to store the entire 141 // serialized cache. 142 size_t getFlattenedSize() const; 143 144 // flatten serializes the current contents of the cache into the memory 145 // pointed to by 'buffer'. The serialized cache contents can later be 146 // loaded into a BlobCache object using the unflatten method. The contents 147 // of the BlobCache object will not be modified. 148 // 149 // Preconditions: 150 // size >= this.getFlattenedSize() 151 int flatten(void* buffer, size_t size) const; 152 153 // unflatten replaces the contents of the cache with the serialized cache 154 // contents in the memory pointed to by 'buffer'. The previous contents of 155 // the BlobCache will be evicted from the cache. If an error occurs while 156 // unflattening the serialized cache contents then the BlobCache will be 157 // left in an empty state. 158 // 159 int unflatten(void const* buffer, size_t size); 160 161 private: 162 // Copying is disallowed. 163 BlobCache(const BlobCache&); 164 void operator=(const BlobCache&); 165 166 // A random function helper to get around MinGW not having nrand48() 167 long int blob_random(); 168 169 // Use this in place of a cache entry index to indicate that no 170 // entry is being designated. 171 static const size_t NoEntry = ~size_t(0); 172 173 // Is this Capacity value one of the *FIT* values? 174 static bool isFit(Capacity capacity); 175 176 // clean evicts a selected set of entries from the cache to make 177 // room for a new entry or for replacing an entry with a larger 178 // one. mSelect determines how to pick entries to evict, and 179 // mCapacity determines when to stop evicting entries. 180 // 181 // newEntrySize is the size of the entry we want to add to the 182 // cache, or the new size of the entry we want to replace in the 183 // cache. 184 // 185 // If we are replacing an entry in the cache, then onBehalfOf is 186 // the index of that entry in the cache; otherwise, it is NoEntry. 187 // 188 // Returns true if at least one entry is evicted. 189 bool clean(size_t newEntrySize, size_t onBehalfOf); 190 191 // isCleanable returns true if the cache is full enough for the clean method 192 // to have some effect, and false otherwise. 193 bool isCleanable() const; 194 195 // findVictim selects an entry to remove from the cache. The 196 // cache must not be empty. 197 size_t findVictim(); 198 199 // findDownTo determines how far to clean the cache -- until it 200 // results in a total size that does not exceed the return value 201 // of findDownTo. newEntrySize and onBehalfOf have the same 202 // meanings they do for clean. 203 size_t findDownTo(size_t newEntrySize, size_t onBehalfOf); 204 205 // A Blob is an immutable sized unstructured data blob. 206 class Blob { 207 public: 208 Blob(const void* data, size_t size, bool copyData); 209 ~Blob(); 210 211 bool operator<(const Blob& rhs) const; 212 213 const void* getData() const; 214 size_t getSize() const; 215 216 private: 217 // Copying is not allowed. 218 Blob(const Blob&); 219 void operator=(const Blob&); 220 221 // mData points to the buffer containing the blob data. 222 const void* mData; 223 224 // mSize is the size of the blob data in bytes. 225 size_t mSize; 226 227 // mOwnsData indicates whether or not this Blob object should free the 228 // memory pointed to by mData when the Blob gets destructed. 229 bool mOwnsData; 230 }; 231 232 // A CacheEntry is a single key/value pair in the cache. 233 class CacheEntry { 234 public: 235 CacheEntry(); 236 CacheEntry(const std::shared_ptr<Blob>& key, const std::shared_ptr<Blob>& value, uint32_t recency); 237 CacheEntry(const CacheEntry& ce); 238 239 bool operator<(const CacheEntry& rhs) const; 240 const CacheEntry& operator=(const CacheEntry&); 241 242 std::shared_ptr<Blob> getKey() const; 243 std::shared_ptr<Blob> getValue() const; 244 245 void setValue(const std::shared_ptr<Blob>& value); 246 247 uint32_t getRecency() const; 248 void setRecency(uint32_t recency); 249 250 private: 251 252 // mKey is the key that identifies the cache entry. 253 std::shared_ptr<Blob> mKey; 254 255 // mValue is the cached data associated with the key. 256 std::shared_ptr<Blob> mValue; 257 258 // mRecency is the last "time" (as indicated by 259 // BlobCache::mAccessCount) that this entry was accessed. 260 uint32_t mRecency; 261 }; 262 263 // A Header is the header for the entire BlobCache serialization format. No 264 // need to make this portable, so we simply write the struct out. 265 struct Header { 266 // mMagicNumber is the magic number that identifies the data as 267 // serialized BlobCache contents. It must always contain 'Blb$'. 268 uint32_t mMagicNumber; 269 270 // mBlobCacheVersion is the serialization format version. 271 uint32_t mBlobCacheVersion; 272 273 // mDeviceVersion is the device-specific version of the cache. This can 274 // be used to invalidate the cache. 275 uint32_t mDeviceVersion; 276 277 // mNumEntries is number of cache entries following the header in the 278 // data. 279 size_t mNumEntries; 280 281 // mBuildId is the build id of the device when the cache was created. 282 // When an update to the build happens (via an OTA or other update) this 283 // is used to invalidate the cache. 284 int mBuildIdLength; 285 char mBuildId[]; 286 }; 287 288 // An EntryHeader is the header for a serialized cache entry. No need to 289 // make this portable, so we simply write the struct out. Each EntryHeader 290 // is followed imediately by the key data and then the value data. 291 // 292 // The beginning of each serialized EntryHeader is 4-byte aligned, so the 293 // number of bytes that a serialized cache entry will occupy is: 294 // 295 // ((sizeof(EntryHeader) + keySize + valueSize) + 3) & ~3 296 // 297 struct EntryHeader { 298 // mKeySize is the size of the entry key in bytes. 299 size_t mKeySize; 300 301 // mValueSize is the size of the entry value in bytes. 302 size_t mValueSize; 303 304 // mData contains both the key and value data for the cache entry. The 305 // key comes first followed immediately by the value. 306 uint8_t mData[]; 307 }; 308 309 // mMaxKeySize is the maximum key size that will be cached. Calls to 310 // BlobCache::set with a keySize parameter larger than mMaxKeySize will 311 // simply not add the key/value pair to the cache. 312 const size_t mMaxKeySize; 313 314 // mMaxValueSize is the maximum value size that will be cached. Calls to 315 // BlobCache::set with a valueSize parameter larger than mMaxValueSize will 316 // simply not add the key/value pair to the cache. 317 const size_t mMaxValueSize; 318 319 // mMaxTotalSize is the maximum size that all cache entries can occupy. This 320 // includes space for both keys and values. When a call to BlobCache::set 321 // would otherwise cause this limit to be exceeded, either the key/value 322 // pair passed to BlobCache::set will not be cached or other cache entries 323 // will be evicted from the cache to make room for the new entry. 324 const size_t mMaxTotalSize; 325 326 // mPolicySelect indicates how we pick entries to evict from the cache. 327 const Select mPolicySelect; 328 329 // mPolicyCapacity indicates how we decide when to stop evicting 330 // entries from the cache. 331 const Capacity mPolicyCapacity; 332 333 // mTotalSize is the total combined size of all keys and values currently in 334 // the cache. 335 size_t mTotalSize; 336 337 // mAccessCount is the number of times an entry has been 338 // added/replaced by set(), or its content (not just its size) 339 // retrieved by get(). It serves as a clock for recognizing how 340 // recently an entry was accessed, for the Select::LRU policy. 341 uint32_t mAccessCount; 342 343 // mRandState is the pseudo-random number generator state. It is passed to 344 // nrand48 to generate random numbers when needed. 345 unsigned short mRandState[3]; 346 347 // mCacheEntries stores all the cache entries that are resident in memory. 348 // Cache entries are added to it by the 'set' method. 349 std::vector<CacheEntry> mCacheEntries; 350 }; 351 352 } 353 354 #endif // ANDROID_BLOB_CACHE_H 355