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
27namespace 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.
36class BlobCache : public RefBase, public Flattenable {
37public:
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
112private:
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