1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <assert.h> 69cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com#include <stdio.h> 79cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com#include <stdlib.h> 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 9fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/cache.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "port/port.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/hash.h" 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/mutexlock.h" 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCache::~Cache() { 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace { 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// LRU cache implementation 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// An entry is a variable length heap-allocated structure. Entries 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// are kept in a circular doubly linked list ordered by access time. 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstruct LRUHandle { 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void* value; 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void (*deleter)(const Slice&, void* value); 289cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* next_hash; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle* next; 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle* prev; 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t charge; // TODO(opt): Only allow uint32_t? 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t key_length; 33d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com uint32_t refs; 34d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com uint32_t hash; // Hash of key(); used for fast sharding and comparisons 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char key_data[1]; // Beginning of key 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice key() const { 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // For cheaper lookups, we allow a temporary Handle object 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // to store a pointer to a key in "value". 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (next == this) { 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return *(reinterpret_cast<Slice*>(value)); 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Slice(key_data, key_length); 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 489cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com// We provide our own simple hash table since it removes a whole bunch 499cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com// of porting hacks and is also faster than some of the built-in hash 509cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com// table implementations in some of the compiler/runtime combinations 519cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com// we have tested. E.g., readrandom speeds up by ~5% over the g++ 529cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com// 4.4.3's builtin hashtable. 539cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.comclass HandleTable { 549cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com public: 559cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); } 569cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com ~HandleTable() { delete[] list_; } 579cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com 58d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle* Lookup(const Slice& key, uint32_t hash) { 59d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return *FindPointer(key, hash); 609cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 619cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com 629cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* Insert(LRUHandle* h) { 63d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle** ptr = FindPointer(h->key(), h->hash); 649cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* old = *ptr; 659cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com h->next_hash = (old == NULL ? NULL : old->next_hash); 669cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com *ptr = h; 679cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (old == NULL) { 689cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com ++elems_; 699cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (elems_ > length_) { 709cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com // Since each cache entry is fairly large, we aim for a small 719cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com // average linked list length (<= 1). 729cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com Resize(); 739cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 759cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com return old; 769cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 779cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com 78d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle* Remove(const Slice& key, uint32_t hash) { 79d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle** ptr = FindPointer(key, hash); 809cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* result = *ptr; 819cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (result != NULL) { 829cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com *ptr = result->next_hash; 839cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com --elems_; 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 859cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com return result; 869cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 879cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com 889cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com private: 899cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com // The table consists of an array of buckets where each bucket is 909cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com // a linked list of cache entries that hash into the bucket. 919cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com uint32_t length_; 929cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com uint32_t elems_; 939cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle** list_; 949cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com 959cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com // Return a pointer to slot that points to a cache entry that 96d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // matches key/hash. If there is no such cache entry, return a 97d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // pointer to the trailing slot in the corresponding linked list. 98d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle** FindPointer(const Slice& key, uint32_t hash) { 999cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle** ptr = &list_[hash & (length_ - 1)]; 100d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com while (*ptr != NULL && 101d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com ((*ptr)->hash != hash || key != (*ptr)->key())) { 1029cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com ptr = &(*ptr)->next_hash; 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1049cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com return ptr; 1059cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1079cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com void Resize() { 1089cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com uint32_t new_length = 4; 1099cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com while (new_length < elems_) { 1109cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com new_length *= 2; 1119cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 1129cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle** new_list = new LRUHandle*[new_length]; 1139cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com memset(new_list, 0, sizeof(new_list[0]) * new_length); 1149cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com uint32_t count = 0; 115fbe4e3af3f4e368e0779b6d75cd6005d67469aa2dgrogan@chromium.org for (uint32_t i = 0; i < length_; i++) { 1169cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* h = list_[i]; 1179cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com while (h != NULL) { 1189cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* next = h->next_hash; 119d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com uint32_t hash = h->hash; 1209cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle** ptr = &new_list[hash & (new_length - 1)]; 1219cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com h->next_hash = *ptr; 1229cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com *ptr = h; 1239cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com h = next; 1249cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com count++; 1259cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 126179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1279cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com assert(elems_ == count); 1289cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com delete[] list_; 1299cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com list_ = new_list; 1309cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com length_ = new_length; 1319cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com } 1329cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com}; 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 134d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com// A single shard of sharded cache. 135d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comclass LRUCache { 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 137d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUCache(); 138d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com ~LRUCache(); 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 140d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // Separate from constructor so caller can easily make an array of LRUCache 141d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void SetCapacity(size_t capacity) { capacity_ = capacity; } 142d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 143d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // Like Cache methods, but with an extra "hash" parameter. 144d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com Cache::Handle* Insert(const Slice& key, uint32_t hash, 145d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void* value, size_t charge, 146d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void (*deleter)(const Slice& key, void* value)); 147d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com Cache::Handle* Lookup(const Slice& key, uint32_t hash); 148d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void Release(Cache::Handle* handle); 149d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void Erase(const Slice& key, uint32_t hash); 150179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 151179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 152179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void LRU_Remove(LRUHandle* e); 153179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void LRU_Append(LRUHandle* e); 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Unref(LRUHandle* e); 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 156d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // Initialized before use. 157d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com size_t capacity_; 158179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // mutex_ protects the following state. 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org port::Mutex mutex_; 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t usage_; 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Dummy head of LRU list. 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // lru.prev is newest entry, lru.next is oldest entry. 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle lru_; 166179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org HandleTable table_; 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 169179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 170d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comLRUCache::LRUCache() 171bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org : usage_(0) { 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Make empty circular linked list 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org lru_.next = &lru_; 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org lru_.prev = &lru_; 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgLRUCache::~LRUCache() { 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (LRUHandle* e = lru_.next; e != &lru_; ) { 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle* next = e->next; 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(e->refs == 1); // Error if caller has an unreleased handle 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Unref(e); 182179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e = next; 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid LRUCache::Unref(LRUHandle* e) { 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(e->refs > 0); 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->refs--; 189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (e->refs <= 0) { 190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org usage_ -= e->charge; 191179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (*e->deleter)(e->key(), e->value); 192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org free(e); 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid LRUCache::LRU_Remove(LRUHandle* e) { 197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->next->prev = e->prev; 198179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->prev->next = e->next; 199179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 200179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 201179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid LRUCache::LRU_Append(LRUHandle* e) { 202179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Make "e" newest entry by inserting just before lru_ 203179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->next = &lru_; 204179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->prev = lru_.prev; 205179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->prev->next = e; 206179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->next->prev = e; 207179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 208179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 209d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comCache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) { 210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MutexLock l(&mutex_); 211d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle* e = table_.Lookup(key, hash); 2129cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (e != NULL) { 213179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->refs++; 214179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Remove(e); 215179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Append(e); 216179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 217d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return reinterpret_cast<Cache::Handle*>(e); 218179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 219179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 220d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comvoid LRUCache::Release(Cache::Handle* handle) { 221179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MutexLock l(&mutex_); 222179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Unref(reinterpret_cast<LRUHandle*>(handle)); 223179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 224179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 225d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comCache::Handle* LRUCache::Insert( 226d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const Slice& key, uint32_t hash, void* value, size_t charge, 227d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void (*deleter)(const Slice& key, void* value)) { 228179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MutexLock l(&mutex_); 229179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 230179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle* e = reinterpret_cast<LRUHandle*>( 231179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org malloc(sizeof(LRUHandle)-1 + key.size())); 232179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->value = value; 233179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->deleter = deleter; 234179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->charge = charge; 235179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->key_length = key.size(); 236d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com e->hash = hash; 237179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org e->refs = 2; // One from LRUCache, one for the returned handle 238179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(e->key_data, key.data(), key.size()); 239179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Append(e); 240179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org usage_ += charge; 241179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 2429cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com LRUHandle* old = table_.Insert(e); 2439cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (old != NULL) { 244179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Remove(old); 245179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Unref(old); 246179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 247179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 248179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (usage_ > capacity_ && lru_.next != &lru_) { 249179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRUHandle* old = lru_.next; 250179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Remove(old); 251d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com table_.Remove(old->key(), old->hash); 252179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Unref(old); 253179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 254179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 255d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return reinterpret_cast<Cache::Handle*>(e); 256179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 257179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 258d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comvoid LRUCache::Erase(const Slice& key, uint32_t hash) { 259179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MutexLock l(&mutex_); 260d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle* e = table_.Remove(key, hash); 2619cb7b73e2668626608a4a8706d69d3e7000cebfcgabor@google.com if (e != NULL) { 262179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LRU_Remove(e); 263179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Unref(e); 264179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 265179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 266179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 267d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comstatic const int kNumShardBits = 4; 268d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comstatic const int kNumShards = 1 << kNumShardBits; 269d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 270d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comclass ShardedLRUCache : public Cache { 271d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com private: 272d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUCache shard_[kNumShards]; 273d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com port::Mutex id_mutex_; 274d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com uint64_t last_id_; 275d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 276d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com static inline uint32_t HashSlice(const Slice& s) { 277d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return Hash(s.data(), s.size(), 0); 278d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 279d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 280d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com static uint32_t Shard(uint32_t hash) { 281d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return hash >> (32 - kNumShardBits); 282d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 283d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 284d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com public: 285a7d6c3178930c1ebb77a45a7378b9251d707912agabor@google.com explicit ShardedLRUCache(size_t capacity) 286a7d6c3178930c1ebb77a45a7378b9251d707912agabor@google.com : last_id_(0) { 287d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards; 288d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com for (int s = 0; s < kNumShards; s++) { 289d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com shard_[s].SetCapacity(per_shard); 290d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 291d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 292d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual ~ShardedLRUCache() { } 293d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual Handle* Insert(const Slice& key, void* value, size_t charge, 294d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com void (*deleter)(const Slice& key, void* value)) { 295d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const uint32_t hash = HashSlice(key); 296d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter); 297d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 298d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual Handle* Lookup(const Slice& key) { 299d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const uint32_t hash = HashSlice(key); 300d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return shard_[Shard(hash)].Lookup(key, hash); 301d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 302d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual void Release(Handle* handle) { 303d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com LRUHandle* h = reinterpret_cast<LRUHandle*>(handle); 304d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com shard_[Shard(h->hash)].Release(handle); 305d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 306d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual void Erase(const Slice& key) { 307d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const uint32_t hash = HashSlice(key); 308d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com shard_[Shard(hash)].Erase(key, hash); 309d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 310d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual void* Value(Handle* handle) { 311d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return reinterpret_cast<LRUHandle*>(handle)->value; 312d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 313d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com virtual uint64_t NewId() { 314d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com MutexLock l(&id_mutex_); 315d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return ++(last_id_); 316d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 317d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com}; 318179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 319179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} // end anonymous namespace 320179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 321179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCache* NewLRUCache(size_t capacity) { 322d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com return new ShardedLRUCache(capacity); 323179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 324179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 32545b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 326