Line data Source code
1 : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file. See the AUTHORS file for names of contributors.
4 :
5 : #include <assert.h>
6 : #include <stdio.h>
7 : #include <stdlib.h>
8 :
9 : #include "leveldb/cache.h"
10 : #include "port/port.h"
11 : #include "util/hash.h"
12 : #include "util/mutexlock.h"
13 :
14 : namespace leveldb {
15 :
16 488 : Cache::~Cache() {
17 488 : }
18 :
19 : namespace {
20 :
21 : // LRU cache implementation
22 :
23 : // An entry is a variable length heap-allocated structure. Entries
24 : // are kept in a circular doubly linked list ordered by access time.
25 : struct LRUHandle {
26 : void* value;
27 : void (*deleter)(const Slice&, void* value);
28 : LRUHandle* next_hash;
29 : LRUHandle* next;
30 : LRUHandle* prev;
31 : size_t charge; // TODO(opt): Only allow uint32_t?
32 : size_t key_length;
33 : uint32_t refs;
34 : uint32_t hash; // Hash of key(); used for fast sharding and comparisons
35 : char key_data[1]; // Beginning of key
36 :
37 : Slice key() const {
38 : // For cheaper lookups, we allow a temporary Handle object
39 : // to store a pointer to a key in "value".
40 17283 : if (next == this) {
41 0 : return *(reinterpret_cast<Slice*>(value));
42 : } else {
43 17283 : return Slice(key_data, key_length);
44 : }
45 : }
46 : };
47 :
48 : // We provide our own simple hash table since it removes a whole bunch
49 : // of porting hacks and is also faster than some of the built-in hash
50 : // table implementations in some of the compiler/runtime combinations
51 : // we have tested. E.g., readrandom speeds up by ~5% over the g++
52 : // 4.4.3's builtin hashtable.
53 : class HandleTable {
54 : public:
55 7808 : HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
56 7808 : ~HandleTable() { delete[] list_; }
57 :
58 : LRUHandle* Lookup(const Slice& key, uint32_t hash) {
59 29524 : return *FindPointer(key, hash);
60 : }
61 :
62 160 : LRUHandle* Insert(LRUHandle* h) {
63 320 : LRUHandle** ptr = FindPointer(h->key(), h->hash);
64 160 : LRUHandle* old = *ptr;
65 160 : h->next_hash = (old == NULL ? NULL : old->next_hash);
66 160 : *ptr = h;
67 160 : if (old == NULL) {
68 160 : ++elems_;
69 160 : if (elems_ > length_) {
70 : // Since each cache entry is fairly large, we aim for a small
71 : // average linked list length (<= 1).
72 0 : Resize();
73 : }
74 : }
75 160 : return old;
76 : }
77 :
78 15 : LRUHandle* Remove(const Slice& key, uint32_t hash) {
79 15 : LRUHandle** ptr = FindPointer(key, hash);
80 15 : LRUHandle* result = *ptr;
81 15 : if (result != NULL) {
82 15 : *ptr = result->next_hash;
83 15 : --elems_;
84 : }
85 15 : return result;
86 : }
87 :
88 : private:
89 : // The table consists of an array of buckets where each bucket is
90 : // a linked list of cache entries that hash into the bucket.
91 : uint32_t length_;
92 : uint32_t elems_;
93 : LRUHandle** list_;
94 :
95 : // Return a pointer to slot that points to a cache entry that
96 : // matches key/hash. If there is no such cache entry, return a
97 : // pointer to the trailing slot in the corresponding linked list.
98 29699 : LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
99 29699 : LRUHandle** ptr = &list_[hash & (length_ - 1)];
100 76361 : while (*ptr != NULL &&
101 67852 : ((*ptr)->hash != hash || key != (*ptr)->key())) {
102 0 : ptr = &(*ptr)->next_hash;
103 : }
104 29699 : return ptr;
105 : }
106 :
107 7808 : void Resize() {
108 7808 : uint32_t new_length = 4;
109 15616 : while (new_length < elems_) {
110 0 : new_length *= 2;
111 : }
112 7808 : LRUHandle** new_list = new LRUHandle*[new_length];
113 7808 : memset(new_list, 0, sizeof(new_list[0]) * new_length);
114 7808 : uint32_t count = 0;
115 7808 : for (uint32_t i = 0; i < length_; i++) {
116 0 : LRUHandle* h = list_[i];
117 0 : while (h != NULL) {
118 0 : LRUHandle* next = h->next_hash;
119 0 : uint32_t hash = h->hash;
120 0 : LRUHandle** ptr = &new_list[hash & (new_length - 1)];
121 0 : h->next_hash = *ptr;
122 0 : *ptr = h;
123 0 : h = next;
124 0 : count++;
125 : }
126 : }
127 7808 : assert(elems_ == count);
128 7808 : delete[] list_;
129 7808 : list_ = new_list;
130 7808 : length_ = new_length;
131 7808 : }
132 : };
133 :
134 : // A single shard of sharded cache.
135 : class LRUCache {
136 : public:
137 : LRUCache();
138 : ~LRUCache();
139 :
140 : // Separate from constructor so caller can easily make an array of LRUCache
141 7808 : void SetCapacity(size_t capacity) { capacity_ = capacity; }
142 :
143 : // Like Cache methods, but with an extra "hash" parameter.
144 : Cache::Handle* Insert(const Slice& key, uint32_t hash,
145 : void* value, size_t charge,
146 : void (*deleter)(const Slice& key, void* value));
147 : Cache::Handle* Lookup(const Slice& key, uint32_t hash);
148 : void Release(Cache::Handle* handle);
149 : void Erase(const Slice& key, uint32_t hash);
150 :
151 : private:
152 : void LRU_Remove(LRUHandle* e);
153 : void LRU_Append(LRUHandle* e);
154 : void Unref(LRUHandle* e);
155 :
156 : // Initialized before use.
157 : size_t capacity_;
158 :
159 : // mutex_ protects the following state.
160 : port::Mutex mutex_;
161 : size_t usage_;
162 :
163 : // Dummy head of LRU list.
164 : // lru.prev is newest entry, lru.next is oldest entry.
165 : LRUHandle lru_;
166 :
167 : HandleTable table_;
168 : };
169 :
170 7808 : LRUCache::LRUCache()
171 7808 : : usage_(0) {
172 : // Make empty circular linked list
173 7808 : lru_.next = &lru_;
174 7808 : lru_.prev = &lru_;
175 7808 : }
176 :
177 23424 : LRUCache::~LRUCache() {
178 15761 : for (LRUHandle* e = lru_.next; e != &lru_; ) {
179 145 : LRUHandle* next = e->next;
180 145 : assert(e->refs == 1); // Error if caller has an unreleased handle
181 145 : Unref(e);
182 145 : e = next;
183 : }
184 7808 : }
185 :
186 17268 : void LRUCache::Unref(LRUHandle* e) {
187 17268 : assert(e->refs > 0);
188 17268 : e->refs--;
189 17268 : if (e->refs <= 0) {
190 160 : usage_ -= e->charge;
191 320 : (*e->deleter)(e->key(), e->value);
192 160 : free(e);
193 : }
194 17268 : }
195 :
196 0 : void LRUCache::LRU_Remove(LRUHandle* e) {
197 16963 : e->next->prev = e->prev;
198 16963 : e->prev->next = e->next;
199 0 : }
200 :
201 : void LRUCache::LRU_Append(LRUHandle* e) {
202 : // Make "e" newest entry by inserting just before lru_
203 17108 : e->next = &lru_;
204 17108 : e->prev = lru_.prev;
205 17108 : e->prev->next = e;
206 17108 : e->next->prev = e;
207 : }
208 :
209 29524 : Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
210 29524 : MutexLock l(&mutex_);
211 59048 : LRUHandle* e = table_.Lookup(key, hash);
212 29524 : if (e != NULL) {
213 16948 : e->refs++;
214 16948 : LRU_Remove(e);
215 : LRU_Append(e);
216 : }
217 59048 : return reinterpret_cast<Cache::Handle*>(e);
218 : }
219 :
220 17108 : void LRUCache::Release(Cache::Handle* handle) {
221 17108 : MutexLock l(&mutex_);
222 17108 : Unref(reinterpret_cast<LRUHandle*>(handle));
223 17108 : }
224 :
225 160 : Cache::Handle* LRUCache::Insert(
226 : const Slice& key, uint32_t hash, void* value, size_t charge,
227 : void (*deleter)(const Slice& key, void* value)) {
228 160 : MutexLock l(&mutex_);
229 :
230 : LRUHandle* e = reinterpret_cast<LRUHandle*>(
231 160 : malloc(sizeof(LRUHandle)-1 + key.size()));
232 160 : e->value = value;
233 160 : e->deleter = deleter;
234 160 : e->charge = charge;
235 160 : e->key_length = key.size();
236 160 : e->hash = hash;
237 160 : e->refs = 2; // One from LRUCache, one for the returned handle
238 160 : memcpy(e->key_data, key.data(), key.size());
239 : LRU_Append(e);
240 160 : usage_ += charge;
241 :
242 160 : LRUHandle* old = table_.Insert(e);
243 160 : if (old != NULL) {
244 0 : LRU_Remove(old);
245 0 : Unref(old);
246 : }
247 :
248 160 : while (usage_ > capacity_ && lru_.next != &lru_) {
249 0 : LRUHandle* old = lru_.next;
250 0 : LRU_Remove(old);
251 0 : table_.Remove(old->key(), old->hash);
252 0 : Unref(old);
253 : }
254 :
255 320 : return reinterpret_cast<Cache::Handle*>(e);
256 : }
257 :
258 15 : void LRUCache::Erase(const Slice& key, uint32_t hash) {
259 15 : MutexLock l(&mutex_);
260 15 : LRUHandle* e = table_.Remove(key, hash);
261 15 : if (e != NULL) {
262 15 : LRU_Remove(e);
263 15 : Unref(e);
264 : }
265 15 : }
266 :
267 : static const int kNumShardBits = 4;
268 : static const int kNumShards = 1 << kNumShardBits;
269 :
270 : class ShardedLRUCache : public Cache {
271 : private:
272 : LRUCache shard_[kNumShards];
273 : port::Mutex id_mutex_;
274 : uint64_t last_id_;
275 :
276 : static inline uint32_t HashSlice(const Slice& s) {
277 29699 : return Hash(s.data(), s.size(), 0);
278 : }
279 :
280 : static uint32_t Shard(uint32_t hash) {
281 46807 : return hash >> (32 - kNumShardBits);
282 : }
283 :
284 : public:
285 488 : explicit ShardedLRUCache(size_t capacity)
286 976 : : last_id_(0) {
287 488 : const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
288 8296 : for (int s = 0; s < kNumShards; s++) {
289 7808 : shard_[s].SetCapacity(per_shard);
290 : }
291 488 : }
292 1464 : virtual ~ShardedLRUCache() { }
293 160 : virtual Handle* Insert(const Slice& key, void* value, size_t charge,
294 : void (*deleter)(const Slice& key, void* value)) {
295 160 : const uint32_t hash = HashSlice(key);
296 160 : return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
297 : }
298 29524 : virtual Handle* Lookup(const Slice& key) {
299 29524 : const uint32_t hash = HashSlice(key);
300 29524 : return shard_[Shard(hash)].Lookup(key, hash);
301 : }
302 17108 : virtual void Release(Handle* handle) {
303 17108 : LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
304 34216 : shard_[Shard(h->hash)].Release(handle);
305 17108 : }
306 15 : virtual void Erase(const Slice& key) {
307 15 : const uint32_t hash = HashSlice(key);
308 15 : shard_[Shard(hash)].Erase(key, hash);
309 15 : }
310 17108 : virtual void* Value(Handle* handle) {
311 17108 : return reinterpret_cast<LRUHandle*>(handle)->value;
312 : }
313 160 : virtual uint64_t NewId() {
314 160 : MutexLock l(&id_mutex_);
315 320 : return ++(last_id_);
316 : }
317 : };
318 :
319 : } // end anonymous namespace
320 :
321 488 : Cache* NewLRUCache(size_t capacity) {
322 488 : return new ShardedLRUCache(capacity);
323 : }
324 :
325 : } // namespace leveldb
|
