2 // Use of this source code is governed by a BSD-style license that can be
5 #include "leveldb/cache.h"
18 Cache::~Cache() {}  in ~Cache()
22 // LRU cache implementation
24 // Cache entries have an "in_cache" boolean indicating whether the cache has a
27 // an element with a duplicate key is inserted, or on destruction of the cache.
29 // The cache keeps two linked lists of items in the cache.  All items in the
30 // cache are in one list or the other, and never both.  Items still referenced
31 // by clients but erased from the cache are in neither list.  The lists are:
32 // - in-use:  contains the items currently referenced by clients, in no
36 // - LRU:  contains the items not currently referenced by clients, in LRU order
38 // when they detect an element in the cache acquiring or losing its only
41 // An entry is a variable length heap-allocated structure.  Entries
51   bool in_cache;     // Whether entry is in the cache.
52   uint32_t refs;     // References, including cache reference, if present.
57     // next_ is only equal to this if the LRU handle is the list head of an  in key()
66 // of porting hacks and is also faster than some of the built-in hash
80     LRUHandle** ptr = FindPointer(h->key(), h->hash);  in Insert()
82     h->next_hash = (old == nullptr ? nullptr : old->next_hash);  in Insert()
87         // Since each cache entry is fairly large, we aim for a small  in Insert()
99       *ptr = result->next_hash;  in Remove()
100       --elems_;  in Remove()
107   // a linked list of cache entries that hash into the bucket.
112   // Return a pointer to slot that points to a cache entry that
113   // matches key/hash.  If there is no such cache entry, return a
116     LRUHandle** ptr = &list_[hash & (length_ - 1)];  in FindPointer()
117     while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {  in FindPointer()
118       ptr = &(*ptr)->next_hash;  in FindPointer()
134         LRUHandle* next = h->next_hash;  in Resize()
135         uint32_t hash = h->hash;  in Resize()
136         LRUHandle** ptr = &new_list[hash & (new_length - 1)];  in Resize()
137         h->next_hash = *ptr;  in Resize()
150 // A single shard of sharded cache.
159   // Like Cache methods, but with an extra "hash" parameter.
160   Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
163   Cache::Handle* Lookup(const Slice& key, uint32_t hash);
164   void Release(Cache::Handle* handle);
186   // Dummy head of LRU list.
187   // lru.prev is newest entry, lru.next is oldest entry.
191   // Dummy head of in-use list.
209     LRUHandle* next = e->next;  in ~LRUCache()
210     assert(e->in_cache);  in ~LRUCache()
211     e->in_cache = false;  in ~LRUCache()
212     assert(e->refs == 1);  // Invariant of lru_ list.  in ~LRUCache()
219   if (e->refs == 1 && e->in_cache) {  // If on lru_ list, move to in_use_ list.  in Ref()
223   e->refs++;  in Ref()
227   assert(e->refs > 0);  in Unref()
228   e->refs--;  in Unref()
229   if (e->refs == 0) {  // Deallocate.  in Unref()
230     assert(!e->in_cache);  in Unref()
231     (*e->deleter)(e->key(), e->value);  in Unref()
233   } else if (e->in_cache && e->refs == 1) {  in Unref()
241   e->next->prev = e->prev;  in LRU_Remove()
242   e->prev->next = e->next;  in LRU_Remove()
247   e->next = list;  in LRU_Append()
248   e->prev = list->prev;  in LRU_Append()
249   e->prev->next = e;  in LRU_Append()
250   e->next->prev = e;  in LRU_Append()
253 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {  in Lookup()
259   return reinterpret_cast<Cache::Handle*>(e);  in Lookup()
262 void LRUCache::Release(Cache::Handle* handle) {  in Release()
267 Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,  in Insert()
274       reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));  in Insert()
275   e->value = value;  in Insert()
276   e->deleter = deleter;  in Insert()
277   e->charge = charge;  in Insert()
278   e->key_length = key.size();  in Insert()
279   e->hash = hash;  in Insert()
280   e->in_cache = false;  in Insert()
281   e->refs = 1;  // for the returned handle.  in Insert()
282   std::memcpy(e->key_data, key.data(), key.size());  in Insert()
285     e->refs++;  // for the cache's reference.  in Insert()
286     e->in_cache = true;  in Insert()
290   } else {  // don't cache. (capacity_==0 is supported and turns off caching.)  in Insert()
292     e->next = nullptr;  in Insert()
296     assert(old->refs == 1);  in Insert()
297     bool erased = FinishErase(table_.Remove(old->key(), old->hash));  in Insert()
303   return reinterpret_cast<Cache::Handle*>(e);  in Insert()
306 // If e != nullptr, finish removing *e from the cache; it has already been
310     assert(e->in_cache);  in FinishErase()
312     e->in_cache = false;  in FinishErase()
313     usage_ -= e->charge;  in FinishErase()
328     assert(e->refs == 1);  in Prune()
329     bool erased = FinishErase(table_.Remove(e->key(), e->hash));  in Prune()
339 class ShardedLRUCache : public Cache {
349   static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }  in Shard()
353     const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;  in ShardedLRUCache()
370     shard_[Shard(h->hash)].Release(handle);  in Release()
377     return reinterpret_cast<LRUHandle*>(handle)->value;  in Value()
399 Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }  in NewLRUCache()