src/leveldb/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         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