Branch data 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 "port/thread_annotations.h"
12 : : #include "util/hash.h"
13 : : #include "util/mutexlock.h"
14 : :
15 : : namespace leveldb {
16 : :
17 : 978 : Cache::~Cache() {}
18 : :
19 : : namespace {
20 : :
21 : : // LRU cache implementation
22 : : //
23 : : // Cache entries have an "in_cache" boolean indicating whether the cache has a
24 : : // reference on the entry. The only ways that this can become false without the
25 : : // entry being passed to its "deleter" are via Erase(), via Insert() when
26 : : // an element with a duplicate key is inserted, or on destruction of the cache.
27 : : //
28 : : // The cache keeps two linked lists of items in the cache. All items in the
29 : : // cache are in one list or the other, and never both. Items still referenced
30 : : // by clients but erased from the cache are in neither list. The lists are:
31 : : // - in-use: contains the items currently referenced by clients, in no
32 : : // particular order. (This list is used for invariant checking. If we
33 : : // removed the check, elements that would otherwise be on this list could be
34 : : // left as disconnected singleton lists.)
35 : : // - LRU: contains the items not currently referenced by clients, in LRU order
36 : : // Elements are moved between these lists by the Ref() and Unref() methods,
37 : : // when they detect an element in the cache acquiring or losing its only
38 : : // external reference.
39 : :
40 : : // An entry is a variable length heap-allocated structure. Entries
41 : : // are kept in a circular doubly linked list ordered by access time.
42 : : struct LRUHandle {
43 : : void* value;
44 : : void (*deleter)(const Slice&, void* value);
45 : : LRUHandle* next_hash;
46 : : LRUHandle* next;
47 : : LRUHandle* prev;
48 : : size_t charge; // TODO(opt): Only allow uint32_t?
49 : : size_t key_length;
50 : : bool in_cache; // Whether entry is in the cache.
51 : : uint32_t refs; // References, including cache reference, if present.
52 : : uint32_t hash; // Hash of key(); used for fast sharding and comparisons
53 : : char key_data[1]; // Beginning of key
54 : :
55 : 1356753 : Slice key() const {
56 : : // next_ is only equal to this if the LRU handle is the list head of an
57 : : // empty list. List heads never have meaningful keys.
58 [ - + ]: 1356753 : assert(next != this);
59 : :
60 : 1356753 : return Slice(key_data, key_length);
61 : : }
62 : : };
63 : :
64 : : // We provide our own simple hash table since it removes a whole bunch
65 : : // of porting hacks and is also faster than some of the built-in hash
66 : : // table implementations in some of the compiler/runtime combinations
67 : : // we have tested. E.g., readrandom speeds up by ~5% over the g++
68 : : // 4.4.3's builtin hashtable.
69 : : class HandleTable {
70 : : public:
71 : 15648 : HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
72 : 15648 : ~HandleTable() { delete[] list_; }
73 : :
74 : 1357788 : LRUHandle* Lookup(const Slice& key, uint32_t hash) {
75 : 2715576 : return *FindPointer(key, hash);
76 : : }
77 : :
78 : 410 : LRUHandle* Insert(LRUHandle* h) {
79 : 410 : LRUHandle** ptr = FindPointer(h->key(), h->hash);
80 : 410 : LRUHandle* old = *ptr;
81 [ - + ]: 410 : h->next_hash = (old == nullptr ? nullptr : old->next_hash);
82 : 410 : *ptr = h;
83 [ + - ]: 410 : if (old == nullptr) {
84 : 410 : ++elems_;
85 [ + + ]: 410 : if (elems_ > length_) {
86 : : // Since each cache entry is fairly large, we aim for a small
87 : : // average linked list length (<= 1).
88 : 41 : Resize();
89 : : }
90 : : }
91 : 410 : return old;
92 : : }
93 : :
94 : 45 : LRUHandle* Remove(const Slice& key, uint32_t hash) {
95 : 45 : LRUHandle** ptr = FindPointer(key, hash);
96 : 45 : LRUHandle* result = *ptr;
97 [ + + ]: 45 : if (result != nullptr) {
98 : 44 : *ptr = result->next_hash;
99 : 44 : --elems_;
100 : : }
101 : 45 : return result;
102 : : }
103 : :
104 : : private:
105 : : // The table consists of an array of buckets where each bucket is
106 : : // a linked list of cache entries that hash into the bucket.
107 : : uint32_t length_;
108 : : uint32_t elems_;
109 : : LRUHandle** list_;
110 : :
111 : : // Return a pointer to slot that points to a cache entry that
112 : : // matches key/hash. If there is no such cache entry, return a
113 : : // pointer to the trailing slot in the corresponding linked list.
114 : 1358243 : LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
115 : 1358243 : LRUHandle** ptr = &list_[hash & (length_ - 1)];
116 [ + + + + : 1376958 : while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
- + ]
117 : 18715 : ptr = &(*ptr)->next_hash;
118 : : }
119 : 1358243 : return ptr;
120 : : }
121 : :
122 : 15689 : void Resize() {
123 : 15689 : uint32_t new_length = 4;
124 [ + + ]: 15765 : while (new_length < elems_) {
125 : 76 : new_length *= 2;
126 : : }
127 : 15689 : LRUHandle** new_list = new LRUHandle*[new_length];
128 : 15689 : memset(new_list, 0, sizeof(new_list[0]) * new_length);
129 : 15689 : uint32_t count = 0;
130 [ + + ]: 16033 : for (uint32_t i = 0; i < length_; i++) {
131 : 344 : LRUHandle* h = list_[i];
132 [ + + ]: 729 : while (h != nullptr) {
133 : 385 : LRUHandle* next = h->next_hash;
134 : 385 : uint32_t hash = h->hash;
135 : 385 : LRUHandle** ptr = &new_list[hash & (new_length - 1)];
136 : 385 : h->next_hash = *ptr;
137 : 385 : *ptr = h;
138 : 385 : h = next;
139 : 385 : count++;
140 : : }
141 : : }
142 [ - + ]: 15689 : assert(elems_ == count);
143 [ + + ]: 15689 : delete[] list_;
144 : 15689 : list_ = new_list;
145 : 15689 : length_ = new_length;
146 : 15689 : }
147 : : };
148 : :
149 : : // A single shard of sharded cache.
150 : : class LRUCache {
151 : : public:
152 : : LRUCache();
153 : : ~LRUCache();
154 : :
155 : : // Separate from constructor so caller can easily make an array of LRUCache
156 : 15648 : void SetCapacity(size_t capacity) { capacity_ = capacity; }
157 : :
158 : : // Like Cache methods, but with an extra "hash" parameter.
159 : : Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
160 : : size_t charge,
161 : : void (*deleter)(const Slice& key, void* value));
162 : : Cache::Handle* Lookup(const Slice& key, uint32_t hash);
163 : : void Release(Cache::Handle* handle);
164 : : void Erase(const Slice& key, uint32_t hash);
165 : : void Prune();
166 : 0 : size_t TotalCharge() const {
167 : 0 : MutexLock l(&mutex_);
168 : 0 : return usage_;
169 : 0 : }
170 : :
171 : : private:
172 : : void LRU_Remove(LRUHandle* e);
173 : : void LRU_Append(LRUHandle* list, LRUHandle* e);
174 : : void Ref(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
175 : : void Unref(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
176 : : bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
177 : :
178 : : // Initialized before use.
179 : : size_t capacity_;
180 : :
181 : : // mutex_ protects the following state.
182 : : mutable port::Mutex mutex_;
183 : : size_t usage_ GUARDED_BY(mutex_);
184 : :
185 : : // Dummy head of LRU list.
186 : : // lru.prev is newest entry, lru.next is oldest entry.
187 : : // Entries have refs==1 and in_cache==true.
188 : : LRUHandle lru_ GUARDED_BY(mutex_);
189 : :
190 : : // Dummy head of in-use list.
191 : : // Entries are in use by clients, and have refs >= 2 and in_cache==true.
192 : : LRUHandle in_use_ GUARDED_BY(mutex_);
193 : :
194 : : HandleTable table_ GUARDED_BY(mutex_);
195 : : };
196 : :
197 : 15648 : LRUCache::LRUCache() : capacity_(0), usage_(0) {
198 : : // Make empty circular linked lists.
199 : 15648 : lru_.next = &lru_;
200 : 15648 : lru_.prev = &lru_;
201 : 15648 : in_use_.next = &in_use_;
202 : 15648 : in_use_.prev = &in_use_;
203 : 15648 : }
204 : :
205 : 15648 : LRUCache::~LRUCache() {
206 [ - + ]: 15648 : assert(in_use_.next == &in_use_); // Error if caller has an unreleased handle
207 [ + + ]: 16014 : for (LRUHandle* e = lru_.next; e != &lru_;) {
208 : 366 : LRUHandle* next = e->next;
209 [ - + ]: 366 : assert(e->in_cache);
210 : 366 : e->in_cache = false;
211 [ - + ]: 366 : assert(e->refs == 1); // Invariant of lru_ list.
212 : 366 : Unref(e);
213 : 366 : e = next;
214 : : }
215 [ + - ]: 15648 : }
216 : :
217 : 1355889 : void LRUCache::Ref(LRUHandle* e) {
218 [ + + + - ]: 1355889 : if (e->refs == 1 && e->in_cache) { // If on lru_ list, move to in_use_ list.
219 : 1354795 : LRU_Remove(e);
220 : 1354795 : LRU_Append(&in_use_, e);
221 : : }
222 : 1355889 : e->refs++;
223 : 1355889 : }
224 : :
225 : 1356709 : void LRUCache::Unref(LRUHandle* e) {
226 [ - + ]: 1356709 : assert(e->refs > 0);
227 : 1356709 : e->refs--;
228 [ + + ]: 1356709 : if (e->refs == 0) { // Deallocate.
229 [ - + ]: 410 : assert(!e->in_cache);
230 : 410 : (*e->deleter)(e->key(), e->value);
231 : 410 : free(e);
232 [ + - + + ]: 1356299 : } else if (e->in_cache && e->refs == 1) {
233 : : // No longer in use; move to lru_ list.
234 : 1355205 : LRU_Remove(e);
235 : 1355205 : LRU_Append(&lru_, e);
236 : : }
237 : 1356709 : }
238 : :
239 : 2710044 : void LRUCache::LRU_Remove(LRUHandle* e) {
240 : 2710044 : e->next->prev = e->prev;
241 : 2710044 : e->prev->next = e->next;
242 : 2710044 : }
243 : :
244 : 2710410 : void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
245 : : // Make "e" newest entry by inserting just before *list
246 : 2710410 : e->next = list;
247 : 2710410 : e->prev = list->prev;
248 : 2710410 : e->prev->next = e;
249 : 2710410 : e->next->prev = e;
250 : 2710410 : }
251 : :
252 : 1357788 : Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
253 : 1357788 : MutexLock l(&mutex_);
254 : 1357788 : LRUHandle* e = table_.Lookup(key, hash);
255 [ + + ]: 1357788 : if (e != nullptr) {
256 : 1355889 : Ref(e);
257 : : }
258 : 1357788 : return reinterpret_cast<Cache::Handle*>(e);
259 : 1357788 : }
260 : :
261 : 1356299 : void LRUCache::Release(Cache::Handle* handle) {
262 : 1356299 : MutexLock l(&mutex_);
263 [ + - ]: 1356299 : Unref(reinterpret_cast<LRUHandle*>(handle));
264 : 1356299 : }
265 : :
266 : 410 : Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
267 : : size_t charge,
268 : : void (*deleter)(const Slice& key,
269 : : void* value)) {
270 : 410 : MutexLock l(&mutex_);
271 : :
272 [ + - ]: 410 : LRUHandle* e =
273 : 410 : reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
274 : 410 : e->value = value;
275 : 410 : e->deleter = deleter;
276 : 410 : e->charge = charge;
277 : 410 : e->key_length = key.size();
278 : 410 : e->hash = hash;
279 : 410 : e->in_cache = false;
280 : 410 : e->refs = 1; // for the returned handle.
281 [ + - ]: 410 : memcpy(e->key_data, key.data(), key.size());
282 : :
283 [ + - ]: 410 : if (capacity_ > 0) {
284 : 410 : e->refs++; // for the cache's reference.
285 : 410 : e->in_cache = true;
286 : 410 : LRU_Append(&in_use_, e);
287 : 410 : usage_ += charge;
288 [ + - + - ]: 410 : FinishErase(table_.Insert(e));
289 : : } else { // don't cache. (capacity_==0 is supported and turns off caching.)
290 : : // next is read by key() in an assert, so it must be initialized
291 : 0 : e->next = nullptr;
292 : : }
293 [ - + - - ]: 410 : while (usage_ > capacity_ && lru_.next != &lru_) {
294 : 0 : LRUHandle* old = lru_.next;
295 [ # # ]: 0 : assert(old->refs == 1);
296 [ # # ]: 0 : bool erased = FinishErase(table_.Remove(old->key(), old->hash));
297 [ # # ]: 0 : if (!erased) { // to avoid unused variable when compiled NDEBUG
298 : 0 : assert(erased);
299 : : }
300 : : }
301 : :
302 : 410 : return reinterpret_cast<Cache::Handle*>(e);
303 : 410 : }
304 : :
305 : : // If e != nullptr, finish removing *e from the cache; it has already been
306 : : // removed from the hash table. Return whether e != nullptr.
307 : 455 : bool LRUCache::FinishErase(LRUHandle* e) {
308 [ + + ]: 455 : if (e != nullptr) {
309 [ - + ]: 44 : assert(e->in_cache);
310 : 44 : LRU_Remove(e);
311 : 44 : e->in_cache = false;
312 : 44 : usage_ -= e->charge;
313 : 44 : Unref(e);
314 : : }
315 : 455 : return e != nullptr;
316 : : }
317 : :
318 : 45 : void LRUCache::Erase(const Slice& key, uint32_t hash) {
319 : 45 : MutexLock l(&mutex_);
320 [ + - ]: 45 : FinishErase(table_.Remove(key, hash));
321 : 45 : }
322 : :
323 : 0 : void LRUCache::Prune() {
324 : 0 : MutexLock l(&mutex_);
325 [ # # ]: 0 : while (lru_.next != &lru_) {
326 : 0 : LRUHandle* e = lru_.next;
327 [ # # ]: 0 : assert(e->refs == 1);
328 [ # # ]: 0 : bool erased = FinishErase(table_.Remove(e->key(), e->hash));
329 [ # # ]: 0 : if (!erased) { // to avoid unused variable when compiled NDEBUG
330 : 0 : assert(erased);
331 : : }
332 : : }
333 : 0 : }
334 : :
335 : : static const int kNumShardBits = 4;
336 : : static const int kNumShards = 1 << kNumShardBits;
337 : :
338 : : class ShardedLRUCache : public Cache {
339 : : private:
340 : : LRUCache shard_[kNumShards];
341 : : port::Mutex id_mutex_;
342 : : uint64_t last_id_;
343 : :
344 : 1358243 : static inline uint32_t HashSlice(const Slice& s) {
345 : 1358243 : return Hash(s.data(), s.size(), 0);
346 : : }
347 : :
348 : 2714542 : static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }
349 : :
350 : : public:
351 [ + - + + : 16626 : explicit ShardedLRUCache(size_t capacity) : last_id_(0) {
- - - - ]
352 : 978 : const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
353 [ + + ]: 16626 : for (int s = 0; s < kNumShards; s++) {
354 : 15648 : shard_[s].SetCapacity(per_shard);
355 : : }
356 : 978 : }
357 [ + + ]: 17604 : ~ShardedLRUCache() override {}
358 : 410 : Handle* Insert(const Slice& key, void* value, size_t charge,
359 : : void (*deleter)(const Slice& key, void* value)) override {
360 : 410 : const uint32_t hash = HashSlice(key);
361 : 410 : return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
362 : : }
363 : 1357788 : Handle* Lookup(const Slice& key) override {
364 : 1357788 : const uint32_t hash = HashSlice(key);
365 : 1357788 : return shard_[Shard(hash)].Lookup(key, hash);
366 : : }
367 : 1356299 : void Release(Handle* handle) override {
368 : 1356299 : LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
369 : 1356299 : shard_[Shard(h->hash)].Release(handle);
370 : 1356299 : }
371 : 45 : void Erase(const Slice& key) override {
372 : 45 : const uint32_t hash = HashSlice(key);
373 : 45 : shard_[Shard(hash)].Erase(key, hash);
374 : 45 : }
375 : 1356044 : void* Value(Handle* handle) override {
376 : 1356044 : return reinterpret_cast<LRUHandle*>(handle)->value;
377 : : }
378 : 155 : uint64_t NewId() override {
379 : 155 : MutexLock l(&id_mutex_);
380 : 155 : return ++(last_id_);
381 : 155 : }
382 : 0 : void Prune() override {
383 [ # # ]: 0 : for (int s = 0; s < kNumShards; s++) {
384 : 0 : shard_[s].Prune();
385 : : }
386 : 0 : }
387 : 0 : size_t TotalCharge() const override {
388 : 0 : size_t total = 0;
389 [ # # ]: 0 : for (int s = 0; s < kNumShards; s++) {
390 : 0 : total += shard_[s].TotalCharge();
391 : : }
392 : 0 : return total;
393 : : }
394 : : };
395 : :
396 : : } // end anonymous namespace
397 : :
398 [ + - ]: 978 : Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }
399 : :
400 : : } // namespace leveldb
|
