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 14 namespace leveldb { 15 16 Cache::~Cache() { 17 } 18 19 namespace { 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. 25 struct 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. 53 class 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. 135 class 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 170 LRUCache::LRUCache() 171 : usage_(0) { 172 // Make empty circular linked list 173 lru_.next = &lru_; 174 lru_.prev = &lru_; 175 } 176 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 181 Unref(e); 182 e = next; 183 } 184 } 185 186 void 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 196 void LRUCache::LRU_Remove(LRUHandle* e) { 197 e->next->prev = e->prev; 198 e->prev->next = e->next; 199 } 200 201 void 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 209 Cache::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 220 void LRUCache::Release(Cache::Handle* handle) { 221 MutexLock l(&mutex_); 222 Unref(reinterpret_cast<LRUHandle*>(handle)); 223 } 224 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_); 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 258 void 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 267 static const int kNumShardBits = 4; 268 static const int kNumShards = 1 << kNumShardBits; 269 270 class 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 321 Cache* NewLRUCache(size_t capacity) { 322 return new ShardedLRUCache(capacity); 323 } 324 325 } // namespace leveldb 326