util/cache.cc

   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         Slice key = h->key();
 120         uint32_t hash = h->hash;
 121         LRUHandle** ptr = &new_list[hash & (new_length - 1)];
 122         h->next_hash = *ptr;
 123         *ptr = h;
 124         h = next;
 125         count++;
 126       }
 127     }
 128     assert(elems_ == count);
 129     delete[] list_;
 130     list_ = new_list;
 131     length_ = new_length;
 132   }
 133 };
 134
 135 // A single shard of sharded cache.
 136 class LRUCache {
 137  public:
 138   LRUCache();
 139   ~LRUCache();
 140
 141   // Separate from constructor so caller can easily make an array of LRUCache
 142   void SetCapacity(size_t capacity) { capacity_ = capacity; }
 143
 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);
 151
 152  private:
 153   void LRU_Remove(LRUHandle* e);
 154   void LRU_Append(LRUHandle* e);
 155   void Unref(LRUHandle* e);
 156
 157   // Initialized before use.
 158   size_t capacity_;
 159
 160   // mutex_ protects the following state.
 161   port::Mutex mutex_;
 162   size_t usage_;
 163   uint64_t last_id_;
 164
 165   // Dummy head of LRU list.
 166   // lru.prev is newest entry, lru.next is oldest entry.
 167   LRUHandle lru_;
 168
 169   HandleTable table_;
 170 };
 171
 172 LRUCache::LRUCache()
 173     : usage_(0),
 174       last_id_(0) {
 175   // Make empty circular linked list
 176   lru_.next = &lru_;
 177   lru_.prev = &lru_;
 178 }
 179
 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
 184     Unref(e);
 185     e = next;
 186   }
 187 }
 188
 189 void LRUCache::Unref(LRUHandle* e) {
 190   assert(e->refs > 0);
 191   e->refs--;
 192   if (e->refs <= 0) {
 193     usage_ -= e->charge;
 194     (*e->deleter)(e->key(), e->value);
 195     free(e);
 196   }
 197 }
 198
 199 void LRUCache::LRU_Remove(LRUHandle* e) {
 200   e->next->prev = e->prev;
 201   e->prev->next = e->next;
 202 }
 203
 204 void LRUCache::LRU_Append(LRUHandle* e) {
 205   // Make "e" newest entry by inserting just before lru_
 206   e->next = &lru_;
 207   e->prev = lru_.prev;
 208   e->prev->next = e;
 209   e->next->prev = e;
 210 }
 211
 212 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
 213   MutexLock l(&mutex_);
 214   LRUHandle* e = table_.Lookup(key, hash);
 215   if (e != NULL) {
 216     e->refs++;
 217     LRU_Remove(e);
 218     LRU_Append(e);
 219   }
 220   return reinterpret_cast<Cache::Handle*>(e);
 221 }
 222
 223 void LRUCache::Release(Cache::Handle* handle) {
 224   MutexLock l(&mutex_);
 225   Unref(reinterpret_cast<LRUHandle*>(handle));
 226 }
 227
 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_);
 232
 233   LRUHandle* e = reinterpret_cast<LRUHandle*>(
 234       malloc(sizeof(LRUHandle)-1 + key.size()));
 235   e->value = value;
 236   e->deleter = deleter;
 237   e->charge = charge;
 238   e->key_length = key.size();
 239   e->hash = hash;
 240   e->refs = 2;  // One from LRUCache, one for the returned handle
 241   memcpy(e->key_data, key.data(), key.size());
 242   LRU_Append(e);
 243   usage_ += charge;
 244
 245   LRUHandle* old = table_.Insert(e);
 246   if (old != NULL) {
 247     LRU_Remove(old);
 248     Unref(old);
 249   }
 250
 251   while (usage_ > capacity_ && lru_.next != &lru_) {
 252     LRUHandle* old = lru_.next;
 253     LRU_Remove(old);
 254     table_.Remove(old->key(), old->hash);
 255     Unref(old);
 256   }
 257
 258   return reinterpret_cast<Cache::Handle*>(e);
 259 }
 260
 261 void LRUCache::Erase(const Slice& key, uint32_t hash) {
 262   MutexLock l(&mutex_);
 263   LRUHandle* e = table_.Remove(key, hash);
 264   if (e != NULL) {
 265     LRU_Remove(e);
 266     Unref(e);
 267   }
 268 }
 269
 270 static const int kNumShardBits = 4;
 271 static const int kNumShards = 1 << kNumShardBits;
 272
 273 class ShardedLRUCache : public Cache {
 274  private:
 275   LRUCache shard_[kNumShards];
 276   port::Mutex id_mutex_;
 277   uint64_t last_id_;
 278
 279   static inline uint32_t HashSlice(const Slice& s) {
 280     return Hash(s.data(), s.size(), 0);
 281   }
 282
 283   static uint32_t Shard(uint32_t hash) {
 284     return hash >> (32 - kNumShardBits);
 285   }
 286
 287  public:
 288   explicit ShardedLRUCache(size_t capacity)
 289       : last_id_(0) {
 290     const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
 291     for (int s = 0; s < kNumShards; s++) {
 292       shard_[s].SetCapacity(per_shard);
 293     }
 294   }
 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);
 300   }
 301   virtual Handle* Lookup(const Slice& key) {
 302     const uint32_t hash = HashSlice(key);
 303     return shard_[Shard(hash)].Lookup(key, hash);
 304   }
 305   virtual void Release(Handle* handle) {
 306     LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
 307     shard_[Shard(h->hash)].Release(handle);
 308   }
 309   virtual void Erase(const Slice& key) {
 310     const uint32_t hash = HashSlice(key);
 311     shard_[Shard(hash)].Erase(key, hash);
 312   }
 313   virtual void* Value(Handle* handle) {
 314     return reinterpret_cast<LRUHandle*>(handle)->value;
 315   }
 316   virtual uint64_t NewId() {
 317     MutexLock l(&id_mutex_);
 318     return ++(last_id_);
 319   }
 320 };
 321
 322 }  // end anonymous namespace
 323
 324 Cache* NewLRUCache(size_t capacity) {
 325   return new ShardedLRUCache(capacity);
 326 }
 327
 328 }  // namespace leveldb