Home | History | Annotate | Download | only in util
      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