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
Slice key = h->key();
120
uint32_t hash = h->hash;
121
LRUHandle** ptr = &new_list[hash & (new_length - 1)];
128
assert(elems_ == count);
131
length_ = new_length;
135
// A single shard of sharded cache.
141
// Separate from constructor so caller can easily make an array of LRUCache
142
void SetCapacity(size_t capacity) { capacity_ = capacity; }
144
// Like Cache methods, but with an extra "hash" parameter.
145
Cache::Handle* Insert(const Slice& key, uint32_t hash,
146
void* value, size_t charge,
147
void (*deleter)(const Slice& key, void* value));
148
Cache::Handle* Lookup(const Slice& key, uint32_t hash);
149
void Release(Cache::Handle* handle);
150
void Erase(const Slice& key, uint32_t hash);
153
void LRU_Remove(LRUHandle* e);
154
void LRU_Append(LRUHandle* e);
155
void Unref(LRUHandle* e);
157
// Initialized before use.
160
// mutex_ protects the following state.
165
// Dummy head of LRU list.
166
// lru.prev is newest entry, lru.next is oldest entry.
175
// Make empty circular linked list
180
LRUCache::~LRUCache() {
181
for (LRUHandle* e = lru_.next; e != &lru_; ) {
182
LRUHandle* next = e->next;
183
assert(e->refs == 1); // Error if caller has an unreleased handle
189
void LRUCache::Unref(LRUHandle* e) {
194
(*e->deleter)(e->key(), e->value);
199
void LRUCache::LRU_Remove(LRUHandle* e) {
200
e->next->prev = e->prev;
201
e->prev->next = e->next;
204
void LRUCache::LRU_Append(LRUHandle* e) {
205
// Make "e" newest entry by inserting just before lru_
212
Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
213
MutexLock l(&mutex_);
214
LRUHandle* e = table_.Lookup(key, hash);
220
return reinterpret_cast<Cache::Handle*>(e);
223
void LRUCache::Release(Cache::Handle* handle) {
224
MutexLock l(&mutex_);
225
Unref(reinterpret_cast<LRUHandle*>(handle));
228
Cache::Handle* LRUCache::Insert(
229
const Slice& key, uint32_t hash, void* value, size_t charge,
230
void (*deleter)(const Slice& key, void* value)) {
231
MutexLock l(&mutex_);
233
LRUHandle* e = reinterpret_cast<LRUHandle*>(
234
malloc(sizeof(LRUHandle)-1 + key.size()));
236
e->deleter = deleter;
238
e->key_length = key.size();
240
e->refs = 2; // One from LRUCache, one for the returned handle
241
memcpy(e->key_data, key.data(), key.size());
245
LRUHandle* old = table_.Insert(e);
251
while (usage_ > capacity_ && lru_.next != &lru_) {
252
LRUHandle* old = lru_.next;
254
table_.Remove(old->key(), old->hash);
258
return reinterpret_cast<Cache::Handle*>(e);
261
void LRUCache::Erase(const Slice& key, uint32_t hash) {
262
MutexLock l(&mutex_);
263
LRUHandle* e = table_.Remove(key, hash);
270
static const int kNumShardBits = 4;
271
static const int kNumShards = 1 << kNumShardBits;
273
class ShardedLRUCache : public Cache {
275
LRUCache shard_[kNumShards];
276
port::Mutex id_mutex_;
279
static inline uint32_t HashSlice(const Slice& s) {
280
return Hash(s.data(), s.size(), 0);
283
static uint32_t Shard(uint32_t hash) {
284
return hash >> (32 - kNumShardBits);
288
explicit ShardedLRUCache(size_t capacity)
290
const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
291
for (int s = 0; s < kNumShards; s++) {
292
shard_[s].SetCapacity(per_shard);
295
virtual ~ShardedLRUCache() { }
296
virtual Handle* Insert(const Slice& key, void* value, size_t charge,
297
void (*deleter)(const Slice& key, void* value)) {
298
const uint32_t hash = HashSlice(key);
299
return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
301
virtual Handle* Lookup(const Slice& key) {
302
const uint32_t hash = HashSlice(key);
303
return shard_[Shard(hash)].Lookup(key, hash);
305
virtual void Release(Handle* handle) {
306
LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
307
shard_[Shard(h->hash)].Release(handle);
309
virtual void Erase(const Slice& key) {
310
const uint32_t hash = HashSlice(key);
311
shard_[Shard(hash)].Erase(key, hash);
313
virtual void* Value(Handle* handle) {
314
return reinterpret_cast<LRUHandle*>(handle)->value;
316
virtual uint64_t NewId() {
317
MutexLock l(&id_mutex_);
322
} // end anonymous namespace
324
Cache* NewLRUCache(size_t capacity) {
325
return new ShardedLRUCache(capacity);
328
} // namespace leveldb
added
removed
src/leveldb/util/cache.cc
