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.
9 #include "leveldb/cache.h"
10 #include "port/port.h"
11 #include "util/hash.h"
12 #include "util/mutexlock.h"
21 // LRU cache implementation
23 // An entry is a variable length heap-allocated structure. Entries
24 // are kept in a circular doubly linked list ordered by access time.
27 void (*deleter)(const Slice&, void* value);
31 size_t charge; // TODO(opt): Only allow uint32_t?
34 uint32_t hash; // Hash of key(); used for fast sharding and comparisons
35 char key_data[1]; // Beginning of key
38 // For cheaper lookups, we allow a temporary Handle object
39 // to store a pointer to a key in "value".
41 return *(reinterpret_cast<Slice*>(value));
43 return Slice(key_data, key_length);
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.
55 HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
56 ~HandleTable() { delete[] list_; }
58 LRUHandle* Lookup(const Slice& key, uint32_t hash) {
59 return *FindPointer(key, hash);
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);
69 if (elems_ > length_) {
70 // Since each cache entry is fairly large, we aim for a small
71 // average linked list length (<= 1).
78 LRUHandle* Remove(const Slice& key, uint32_t hash) {
79 LRUHandle** ptr = FindPointer(key, hash);
80 LRUHandle* result = *ptr;
82 *ptr = result->next_hash;
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.
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;
108 uint32_t new_length = 4;
109 while (new_length < elems_) {
112 LRUHandle** new_list = new LRUHandle*[new_length];
113 memset(new_list, 0, sizeof(new_list[0]) * new_length);
115 for (uint32_t i = 0; i < length_; i++) {
116 LRUHandle* h = list_[i];
118 LRUHandle* next = h->next_hash;
119 uint32_t hash = h->hash;
120 LRUHandle** ptr = &new_list[hash & (new_length - 1)];
127 assert(elems_ == count);
130 length_ = new_length;
134 // A single shard of sharded cache.
140 // Separate from constructor so caller can easily make an array of LRUCache
141 void SetCapacity(size_t capacity) { capacity_ = capacity; }
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);
152 void LRU_Remove(LRUHandle* e);
153 void LRU_Append(LRUHandle* e);
154 void Unref(LRUHandle* e);
156 // Initialized before use.
159 // mutex_ protects the following state.
163 // Dummy head of LRU list.
164 // lru.prev is newest entry, lru.next is oldest entry.
172 // Make empty circular linked list
177 LRUCache::~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
186 void LRUCache::Unref(LRUHandle* e) {
191 (*e->deleter)(e->key(), e->value);
196 void LRUCache::LRU_Remove(LRUHandle* e) {
197 e->next->prev = e->prev;
198 e->prev->next = e->next;
201 void LRUCache::LRU_Append(LRUHandle* e) {
202 // Make "e" newest entry by inserting just before lru_
209 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
210 MutexLock l(&mutex_);
211 LRUHandle* e = table_.Lookup(key, hash);
217 return reinterpret_cast<Cache::Handle*>(e);
220 void LRUCache::Release(Cache::Handle* handle) {
221 MutexLock l(&mutex_);
222 Unref(reinterpret_cast<LRUHandle*>(handle));
225 Cache::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_);
230 LRUHandle* e = reinterpret_cast<LRUHandle*>(
231 malloc(sizeof(LRUHandle)-1 + key.size()));
233 e->deleter = deleter;
235 e->key_length = key.size();
237 e->refs = 2; // One from LRUCache, one for the returned handle
238 memcpy(e->key_data, key.data(), key.size());
242 LRUHandle* old = table_.Insert(e);
248 while (usage_ > capacity_ && lru_.next != &lru_) {
249 LRUHandle* old = lru_.next;
251 table_.Remove(old->key(), old->hash);
255 return reinterpret_cast<Cache::Handle*>(e);
258 void LRUCache::Erase(const Slice& key, uint32_t hash) {
259 MutexLock l(&mutex_);
260 LRUHandle* e = table_.Remove(key, hash);
267 static const int kNumShardBits = 4;
268 static const int kNumShards = 1 << kNumShardBits;
270 class ShardedLRUCache : public Cache {
272 LRUCache shard_[kNumShards];
273 port::Mutex id_mutex_;
276 static inline uint32_t HashSlice(const Slice& s) {
277 return Hash(s.data(), s.size(), 0);
280 static uint32_t Shard(uint32_t hash) {
281 return hash >> (32 - kNumShardBits);
285 explicit ShardedLRUCache(size_t capacity)
287 const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
288 for (int s = 0; s < kNumShards; s++) {
289 shard_[s].SetCapacity(per_shard);
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);
298 virtual Handle* Lookup(const Slice& key) {
299 const uint32_t hash = HashSlice(key);
300 return shard_[Shard(hash)].Lookup(key, hash);
302 virtual void Release(Handle* handle) {
303 LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
304 shard_[Shard(h->hash)].Release(handle);
306 virtual void Erase(const Slice& key) {
307 const uint32_t hash = HashSlice(key);
308 shard_[Shard(hash)].Erase(key, hash);
310 virtual void* Value(Handle* handle) {
311 return reinterpret_cast<LRUHandle*>(handle)->value;
313 virtual uint64_t NewId() {
314 MutexLock l(&id_mutex_);
319 } // end anonymous namespace
321 Cache* NewLRUCache(size_t capacity) {
322 return new ShardedLRUCache(capacity);
325 } // namespace leveldb