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
25namespace 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.
34class BlobCache {
35public:
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
100private:
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