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