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