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