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