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