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