BlobCache.cpp revision 6807e59e0ff943cc6225d46e3c33a8a7eae9b3d7 
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#define LOG_TAG "BlobCache"
18//#define LOG_NDEBUG 0
19
20#include <stdlib.h>
21#include <string.h>
22
23#include <utils/BlobCache.h>
24#include <utils/Log.h>
25
26namespace android {
27
28BlobCache::BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize):
29        mMaxKeySize(maxKeySize),
30        mMaxValueSize(maxValueSize),
31        mMaxTotalSize(maxTotalSize),
32        mTotalSize(0) {
33    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
34#ifdef _WIN32
35    srand(now);
36#else
37    mRandState[0] = (now >> 0) & 0xFFFF;
38    mRandState[1] = (now >> 16) & 0xFFFF;
39    mRandState[2] = (now >> 32) & 0xFFFF;
40#endif
41    ALOGV("initializing random seed using %lld", now);
42}
43
44void BlobCache::set(const void* key, size_t keySize, const void* value,
45        size_t valueSize) {
46    if (mMaxKeySize < keySize) {
47        ALOGV("set: not caching because the key is too large: %d (limit: %d)",
48                keySize, mMaxKeySize);
49        return;
50    }
51    if (mMaxValueSize < valueSize) {
52        ALOGV("set: not caching because the value is too large: %d (limit: %d)",
53                valueSize, mMaxValueSize);
54        return;
55    }
56    if (mMaxTotalSize < keySize + valueSize) {
57        ALOGV("set: not caching because the combined key/value size is too "
58                "large: %d (limit: %d)", keySize + valueSize, mMaxTotalSize);
59        return;
60    }
61    if (keySize == 0) {
62        LOGW("set: not caching because keySize is 0");
63        return;
64    }
65    if (valueSize <= 0) {
66        LOGW("set: not caching because valueSize is 0");
67        return;
68    }
69
70    Mutex::Autolock lock(mMutex);
71    sp<Blob> dummyKey(new Blob(key, keySize, false));
72    CacheEntry dummyEntry(dummyKey, NULL);
73
74    while (true) {
75
76        ssize_t index = mCacheEntries.indexOf(dummyEntry);
77        if (index < 0) {
78            // Create a new cache entry.
79            sp<Blob> keyBlob(new Blob(key, keySize, true));
80            sp<Blob> valueBlob(new Blob(value, valueSize, true));
81            size_t newTotalSize = mTotalSize + keySize + valueSize;
82            if (mMaxTotalSize < newTotalSize) {
83                if (isCleanable()) {
84                    // Clean the cache and try again.
85                    clean();
86                    continue;
87                } else {
88                    ALOGV("set: not caching new key/value pair because the "
89                            "total cache size limit would be exceeded: %d "
90                            "(limit: %d)",
91                            keySize + valueSize, mMaxTotalSize);
92                    break;
93                }
94            }
95            mCacheEntries.add(CacheEntry(keyBlob, valueBlob));
96            mTotalSize = newTotalSize;
97            ALOGV("set: created new cache entry with %d byte key and %d byte value",
98                    keySize, valueSize);
99        } else {
100            // Update the existing cache entry.
101            sp<Blob> valueBlob(new Blob(value, valueSize, true));
102            sp<Blob> oldValueBlob(mCacheEntries[index].getValue());
103            size_t newTotalSize = mTotalSize + valueSize - oldValueBlob->getSize();
104            if (mMaxTotalSize < newTotalSize) {
105                if (isCleanable()) {
106                    // Clean the cache and try again.
107                    clean();
108                    continue;
109                } else {
110                    ALOGV("set: not caching new value because the total cache "
111                            "size limit would be exceeded: %d (limit: %d)",
112                            keySize + valueSize, mMaxTotalSize);
113                    break;
114                }
115            }
116            mCacheEntries.editItemAt(index).setValue(valueBlob);
117            mTotalSize = newTotalSize;
118            ALOGV("set: updated existing cache entry with %d byte key and %d byte "
119                    "value", keySize, valueSize);
120        }
121        break;
122    }
123}
124
125size_t BlobCache::get(const void* key, size_t keySize, void* value,
126        size_t valueSize) {
127    if (mMaxKeySize < keySize) {
128        ALOGV("get: not searching because the key is too large: %d (limit %d)",
129                keySize, mMaxKeySize);
130        return 0;
131    }
132    Mutex::Autolock lock(mMutex);
133    sp<Blob> dummyKey(new Blob(key, keySize, false));
134    CacheEntry dummyEntry(dummyKey, NULL);
135    ssize_t index = mCacheEntries.indexOf(dummyEntry);
136    if (index < 0) {
137        ALOGV("get: no cache entry found for key of size %d", keySize);
138        return 0;
139    }
140
141    // The key was found. Return the value if the caller's buffer is large
142    // enough.
143    sp<Blob> valueBlob(mCacheEntries[index].getValue());
144    size_t valueBlobSize = valueBlob->getSize();
145    if (valueBlobSize <= valueSize) {
146        ALOGV("get: copying %d bytes to caller's buffer", valueBlobSize);
147        memcpy(value, valueBlob->getData(), valueBlobSize);
148    } else {
149        ALOGV("get: caller's buffer is too small for value: %d (needs %d)",
150                valueSize, valueBlobSize);
151    }
152    return valueBlobSize;
153}
154
155long int BlobCache::blob_random() {
156#ifdef _WIN32
157    return rand();
158#else
159    return nrand48(mRandState);
160#endif
161}
162
163void BlobCache::clean() {
164    // Remove a random cache entry until the total cache size gets below half
165    // the maximum total cache size.
166    while (mTotalSize > mMaxTotalSize / 2) {
167        size_t i = size_t(blob_random() % (mCacheEntries.size()));
168        const CacheEntry& entry(mCacheEntries[i]);
169        mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize();
170        mCacheEntries.removeAt(i);
171    }
172}
173
174bool BlobCache::isCleanable() const {
175    return mTotalSize > mMaxTotalSize / 2;
176}
177
178BlobCache::Blob::Blob(const void* data, size_t size, bool copyData):
179        mData(copyData ? malloc(size) : data),
180        mSize(size),
181        mOwnsData(copyData) {
182    if (copyData) {
183        memcpy(const_cast<void*>(mData), data, size);
184    }
185}
186
187BlobCache::Blob::~Blob() {
188    if (mOwnsData) {
189        free(const_cast<void*>(mData));
190    }
191}
192
193bool BlobCache::Blob::operator<(const Blob& rhs) const {
194    if (mSize == rhs.mSize) {
195        return memcmp(mData, rhs.mData, mSize) < 0;
196    } else {
197        return mSize < rhs.mSize;
198    }
199}
200
201const void* BlobCache::Blob::getData() const {
202    return mData;
203}
204
205size_t BlobCache::Blob::getSize() const {
206    return mSize;
207}
208
209BlobCache::CacheEntry::CacheEntry() {
210}
211
212BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value):
213        mKey(key),
214        mValue(value) {
215}
216
217BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce):
218        mKey(ce.mKey),
219        mValue(ce.mValue) {
220}
221
222bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const {
223    return *mKey < *rhs.mKey;
224}
225
226const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) {
227    mKey = rhs.mKey;
228    mValue = rhs.mValue;
229    return *this;
230}
231
232sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const {
233    return mKey;
234}
235
236sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const {
237    return mValue;
238}
239
240void BlobCache::CacheEntry::setValue(const sp<Blob>& value) {
241    mValue = value;
242}
243
244} // namespace android
245