Inside Bitcoin

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
15namespace leveldb {
16
17Cache::~Cache() {}
18
19namespace {
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.
42struct 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.
69class 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.
150class 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
197LRUCache::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
205LRUCache::~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
217void 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
225void 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
239void LRUCache::LRU_Remove(LRUHandle* e) {
240  e->next->prev = e->prev;
241  e->prev->next = e->next;
242}
243
244void 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}