cache.cc raw
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 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 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 assert(next != this);
59
60 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 HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
72 ~HandleTable() { delete[] list_; }
73
74 LRUHandle* Lookup(const Slice& key, uint32_t hash) {
75 return *FindPointer(key, hash);
76 }
77
78 LRUHandle* Insert(LRUHandle* h) {
79 LRUHandle** ptr = FindPointer(h->key(), h->hash);
80 LRUHandle* old = *ptr;
81 h->next_hash = (old == nullptr ? nullptr : old->next_hash);
82 *ptr = h;
83 if (old == nullptr) {
84 ++elems_;
85 if (elems_ > length_) {
86 // Since each cache entry is fairly large, we aim for a small
87 // average linked list length (<= 1).
88 Resize();
89 }
90 }
91 return old;
92 }
93
94 LRUHandle* Remove(const Slice& key, uint32_t hash) {
95 LRUHandle** ptr = FindPointer(key, hash);
96 LRUHandle* result = *ptr;
97 if (result != nullptr) {
98 *ptr = result->next_hash;
99 --elems_;
100 }
101 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 LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
115 LRUHandle** ptr = &list_[hash & (length_ - 1)];
116 while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
117 ptr = &(*ptr)->next_hash;
118 }
119 return ptr;
120 }
121
122 void Resize() {
123 uint32_t new_length = 4;
124 while (new_length < elems_) {
125 new_length *= 2;
126 }
127 LRUHandle** new_list = new LRUHandle*[new_length];
128 memset(new_list, 0, sizeof(new_list[0]) * new_length);
129 uint32_t count = 0;
130 for (uint32_t i = 0; i < length_; i++) {
131 LRUHandle* h = list_[i];
132 while (h != nullptr) {
133 LRUHandle* next = h->next_hash;
134 uint32_t hash = h->hash;
135 LRUHandle** ptr = &new_list[hash & (new_length - 1)];
136 h->next_hash = *ptr;
137 *ptr = h;
138 h = next;
139 count++;
140 }
141 }
142 assert(elems_ == count);
143 delete[] list_;
144 list_ = new_list;
145 length_ = new_length;
146 }
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 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 size_t TotalCharge() const {
167 MutexLock l(&mutex_);
168 return usage_;
169 }
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 LRUCache::LRUCache() : capacity_(0), usage_(0) {
198 // Make empty circular linked lists.
199 lru_.next = &lru_;
200 lru_.prev = &lru_;
201 in_use_.next = &in_use_;
202 in_use_.prev = &in_use_;
203 }
204
205 LRUCache::~LRUCache() {
206 assert(in_use_.next == &in_use_); // Error if caller has an unreleased handle
207 for (LRUHandle* e = lru_.next; e != &lru_;) {
208 LRUHandle* next = e->next;
209 assert(e->in_cache);
210 e->in_cache = false;
211 assert(e->refs == 1); // Invariant of lru_ list.
212 Unref(e);
213 e = next;
214 }
215 }
216
217 void LRUCache::Ref(LRUHandle* e) {
218 if (e->refs == 1 && e->in_cache) { // If on lru_ list, move to in_use_ list.
219 LRU_Remove(e);
220 LRU_Append(&in_use_, e);
221 }
222 e->refs++;
223 }
224
225 void LRUCache::Unref(LRUHandle* e) {
226 assert(e->refs > 0);
227 e->refs--;
228 if (e->refs == 0) { // Deallocate.
229 assert(!e->in_cache);
230 (*e->deleter)(e->key(), e->value);
231 free(e);
232 } else if (e->in_cache && e->refs == 1) {
233 // No longer in use; move to lru_ list.
234 LRU_Remove(e);
235 LRU_Append(&lru_, e);
236 }
237 }
238
239 void LRUCache::LRU_Remove(LRUHandle* e) {
240 e->next->prev = e->prev;
241 e->prev->next = e->next;
242 }
243
244 void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
245 // Make "e" newest entry by inserting just before *list
246 e->next = list;
247 e->prev = list->prev;
248 e->prev->next = e;
249 e->next->prev = e;
250 }
251
252 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
253 MutexLock l(&mutex_);
254 LRUHandle* e = table_.Lookup(key, hash);
255 if (e != nullptr) {
256 Ref(e);
257 }
258 return reinterpret_cast<Cache::Handle*>(e);
259 }
260
261 void LRUCache::Release(Cache::Handle* handle) {
262 MutexLock l(&mutex_);
263 Unref(reinterpret_cast<LRUHandle*>(handle));
264 }
265
266 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 MutexLock l(&mutex_);
271
272 LRUHandle* e =
273 reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
274 e->value = value;
275 e->deleter = deleter;
276 e->charge = charge;
277 e->key_length = key.size();
278 e->hash = hash;
279 e->in_cache = false;
280 e->refs = 1; // for the returned handle.
281 memcpy(e->key_data, key.data(), key.size());
282
283 if (capacity_ > 0) {
284 e->refs++; // for the cache's reference.
285 e->in_cache = true;
286 LRU_Append(&in_use_, e);
287 usage_ += charge;
288 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 e->next = nullptr;
292 }
293 while (usage_ > capacity_ && lru_.next != &lru_) {
294 LRUHandle* old = lru_.next;
295 assert(old->refs == 1);
296 bool erased = FinishErase(table_.Remove(old->key(), old->hash));
297 if (!erased) { // to avoid unused variable when compiled NDEBUG
298 assert(erased);
299 }
300 }
301
302 return reinterpret_cast<Cache::Handle*>(e);
303 }
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 bool LRUCache::FinishErase(LRUHandle* e) {
308 if (e != nullptr) {
309 assert(e->in_cache);
310 LRU_Remove(e);
311 e->in_cache = false;
312 usage_ -= e->charge;
313 Unref(e);
314 }
315 return e != nullptr;
316 }
317
318 void LRUCache::Erase(const Slice& key, uint32_t hash) {
319 MutexLock l(&mutex_);
320 FinishErase(table_.Remove(key, hash));
321 }
322
323 void LRUCache::Prune() {
324 MutexLock l(&mutex_);
325 while (lru_.next != &lru_) {
326 LRUHandle* e = lru_.next;
327 assert(e->refs == 1);
328 bool erased = FinishErase(table_.Remove(e->key(), e->hash));
329 if (!erased) { // to avoid unused variable when compiled NDEBUG
330 assert(erased);
331 }
332 }
333 }
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 static inline uint32_t HashSlice(const Slice& s) {
345 return Hash(s.data(), s.size(), 0);
346 }
347
348 static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }
349
350 public:
351 explicit ShardedLRUCache(size_t capacity) : last_id_(0) {
352 const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
353 for (int s = 0; s < kNumShards; s++) {
354 shard_[s].SetCapacity(per_shard);
355 }
356 }
357 ~ShardedLRUCache() override {}
358 Handle* Insert(const Slice& key, void* value, size_t charge,
359 void (*deleter)(const Slice& key, void* value)) override {
360 const uint32_t hash = HashSlice(key);
361 return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
362 }
363 Handle* Lookup(const Slice& key) override {
364 const uint32_t hash = HashSlice(key);
365 return shard_[Shard(hash)].Lookup(key, hash);
366 }
367 void Release(Handle* handle) override {
368 LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
369 shard_[Shard(h->hash)].Release(handle);
370 }
371 void Erase(const Slice& key) override {
372 const uint32_t hash = HashSlice(key);
373 shard_[Shard(hash)].Erase(key, hash);
374 }
375 void* Value(Handle* handle) override {
376 return reinterpret_cast<LRUHandle*>(handle)->value;
377 }
378 uint64_t NewId() override {
379 MutexLock l(&id_mutex_);
380 return ++(last_id_);
381 }
382 void Prune() override {
383 for (int s = 0; s < kNumShards; s++) {
384 shard_[s].Prune();
385 }
386 }
387 size_t TotalCharge() const override {
388 size_t total = 0;
389 for (int s = 0; s < kNumShards; s++) {
390 total += shard_[s].TotalCharge();
391 }
392 return total;
393 }
394 };
395
396 } // end anonymous namespace
397
398 Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }
399
400 } // namespace leveldb
401