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
14namespace leveldb {
15
16Cache::~Cache() {
17}
18
19namespace {
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.
25struct 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    if (next == this) {
41      return *(reinterpret_cast<Slice*>(value));
42    } else {
43      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.
53class HandleTable {
54 public:
55  HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
56  ~HandleTable() { delete[] list_; }
57
58  LRUHandle* Lookup(const Slice& key, uint32_t hash) {
59    return *FindPointer(key, hash);
60  }
61
62  LRUHandle* Insert(LRUHandle* h) {
63    LRUHandle** ptr = FindPointer(h->key(), h->hash);
64    LRUHandle* old = *ptr;
65    h->next_hash = (old == NULL ? NULL : old->next_hash);
66    *ptr = h;
67    if (old == NULL) {
68      ++elems_;
69      if (elems_ > length_) {
70        // Since each cache entry is fairly large, we aim for a small
71        // average linked list length (<= 1).
72        Resize();
73      }
74    }
75    return old;
76  }
77
78  LRUHandle* Remove(const Slice& key, uint32_t hash) {
79    LRUHandle** ptr = FindPointer(key, hash);
80    LRUHandle* result = *ptr;
81    if (result != NULL) {
82      *ptr = result->next_hash;
83      --elems_;
84    }
85    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  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
99    LRUHandle** ptr = &list_[hash & (length_ - 1)];
100    while (*ptr != NULL &&
101           ((*ptr)->hash != hash || key != (*ptr)->key())) {
102      ptr = &(*ptr)->next_hash;
103    }
104    return ptr;
105  }
106
107  void Resize() {
108    uint32_t new_length = 4;
109    while (new_length < elems_) {
110      new_length *= 2;
111    }
112    LRUHandle** new_list = new LRUHandle*[new_length];
113    memset(new_list, 0, sizeof(new_list[0]) * new_length);
114    uint32_t count = 0;
115    for (uint32_t i = 0; i < length_; i++) {
116      LRUHandle* h = list_[i];
117      while (h != NULL) {
118        LRUHandle* next = h->next_hash;
119        uint32_t hash = h->hash;
120        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
121        h->next_hash = *ptr;
122        *ptr = h;
123        h = next;
124        count++;
125      }
126    }
127    assert(elems_ == count);
128    delete[] list_;
129    list_ = new_list;
130    length_ = new_length;
131  }
132};
133
134// A single shard of sharded cache.
135class LRUCache {
136 public:
137  LRUCache();
138  ~LRUCache();
139
140  // Separate from constructor so caller can easily make an array of LRUCache
141  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
170LRUCache::LRUCache()
171    : usage_(0) {
172  // Make empty circular linked list
173  lru_.next = &lru_;
174  lru_.prev = &lru_;
175}
176
177LRUCache::~LRUCache() {
178  for (LRUHandle* e = lru_.next; e != &lru_; ) {
179    LRUHandle* next = e->next;
180    assert(e->refs == 1);  // Error if caller has an unreleased handle
181    Unref(e);
182    e = next;
183  }
184}
185
186void LRUCache::Unref(LRUHandle* e) {
187  assert(e->refs > 0);
188  e->refs--;
189  if (e->refs <= 0) {
190    usage_ -= e->charge;
191    (*e->deleter)(e->key(), e->value);
192    free(e);
193  }
194}
195
196void LRUCache::LRU_Remove(LRUHandle* e) {
197  e->next->prev = e->prev;
198  e->prev->next = e->next;
199}
200
201void LRUCache::LRU_Append(LRUHandle* e) {
202  // Make "e" newest entry by inserting just before lru_
203  e->next = &lru_;
204  e->prev = lru_.prev;
205  e->prev->next = e;
206  e->next->prev = e;
207}
208
209Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
210  MutexLock l(&mutex_);
211  LRUHandle* e = table_.Lookup(key, hash);
212  if (e != NULL) {
213    e->refs++;
214    LRU_Remove(e);
215    LRU_Append(e);
216  }
217  return reinterpret_cast<Cache::Handle*>(e);
218}
219
220void LRUCache::Release(Cache::Handle* handle) {
221  MutexLock l(&mutex_);
222  Unref(reinterpret_cast<LRUHandle*>(handle));
223}
224
225Cache::Handle* LRUCache::Insert(
226    const Slice& key, uint32_t hash, void* value, size_t charge,
227    void (*deleter)(const Slice& key, void* value)) {
228  MutexLock l(&mutex_);
229
230  LRUHandle* e = reinterpret_cast<LRUHandle*>(
231      malloc(sizeof(LRUHandle)-1 + key.size()));
232  e->value = value;
233  e->deleter = deleter;
234  e->charge = charge;
235  e->key_length = key.size();
236  e->hash = hash;
237  e->refs = 2;  // One from LRUCache, one for the returned handle
238  memcpy(e->key_data, key.data(), key.size());
239  LRU_Append(e);
240  usage_ += charge;
241
242  LRUHandle* old = table_.Insert(e);
243  if (old != NULL) {
244    LRU_Remove(old);
245    Unref(old);
246  }
247
248  while (usage_ > capacity_ && lru_.next != &lru_) {
249    LRUHandle* old = lru_.next;
250    LRU_Remove(old);
251    table_.Remove(old->key(), old->hash);
252    Unref(old);
253  }
254
255  return reinterpret_cast<Cache::Handle*>(e);
256}
257
258void LRUCache::Erase(const Slice& key, uint32_t hash) {
259  MutexLock l(&mutex_);
260  LRUHandle* e = table_.Remove(key, hash);
261  if (e != NULL) {
262    LRU_Remove(e);
263    Unref(e);
264  }
265}
266
267static const int kNumShardBits = 4;
268static const int kNumShards = 1 << kNumShardBits;
269
270class 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    return Hash(s.data(), s.size(), 0);
278  }
279
280  static uint32_t Shard(uint32_t hash) {
281    return hash >> (32 - kNumShardBits);
282  }
283
284 public:
285  explicit ShardedLRUCache(size_t capacity)
286      : last_id_(0) {
287    const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
288    for (int s = 0; s < kNumShards; s++) {
289      shard_[s].SetCapacity(per_shard);
290    }
291  }
292  virtual ~ShardedLRUCache() { }
293  virtual Handle* Insert(const Slice& key, void* value, size_t charge,
294                         void (*deleter)(const Slice& key, void* value)) {
295    const uint32_t hash = HashSlice(key);
296    return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
297  }
298  virtual Handle* Lookup(const Slice& key) {
299    const uint32_t hash = HashSlice(key);
300    return shard_[Shard(hash)].Lookup(key, hash);
301  }
302  virtual void Release(Handle* handle) {
303    LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
304    shard_[Shard(h->hash)].Release(handle);
305  }
306  virtual void Erase(const Slice& key) {
307    const uint32_t hash = HashSlice(key);
308    shard_[Shard(hash)].Erase(key, hash);
309  }
310  virtual void* Value(Handle* handle) {
311    return reinterpret_cast<LRUHandle*>(handle)->value;
312  }
313  virtual uint64_t NewId() {
314    MutexLock l(&id_mutex_);
315    return ++(last_id_);
316  }
317};
318
319}  // end anonymous namespace
320
321Cache* NewLRUCache(size_t capacity) {
322  return new ShardedLRUCache(capacity);
323}
324
325}  // namespace leveldb
326