123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401 |
- #include "leveldb/cache.h"
- #include <cassert>
- #include <cstdio>
- #include <cstdlib>
- #include "port/port.h"
- #include "port/thread_annotations.h"
- #include "util/hash.h"
- #include "util/mutexlock.h"
- namespace leveldb {
- Cache::~Cache() {}
- namespace {
- struct LRUHandle {
- void* value;
- void (*deleter)(const Slice&, void* value);
- LRUHandle* next_hash;
- LRUHandle* next;
- LRUHandle* prev;
- size_t charge;
- size_t key_length;
- bool in_cache;
- uint32_t refs;
- uint32_t hash;
- char key_data[1];
- Slice key() const {
-
-
- assert(next != this);
- return Slice(key_data, key_length);
- }
- };
- class HandleTable {
- public:
- HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
- ~HandleTable() { delete[] list_; }
- LRUHandle* Lookup(const Slice& key, uint32_t hash) {
- return *FindPointer(key, hash);
- }
- LRUHandle* Insert(LRUHandle* h) {
- LRUHandle** ptr = FindPointer(h->key(), h->hash);
- LRUHandle* old = *ptr;
- h->next_hash = (old == nullptr ? nullptr : old->next_hash);
- *ptr = h;
- if (old == nullptr) {
- ++elems_;
- if (elems_ > length_) {
-
-
- Resize();
- }
- }
- return old;
- }
- LRUHandle* Remove(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = FindPointer(key, hash);
- LRUHandle* result = *ptr;
- if (result != nullptr) {
- *ptr = result->next_hash;
- --elems_;
- }
- return result;
- }
- private:
-
-
- uint32_t length_;
- uint32_t elems_;
- LRUHandle** list_;
-
-
-
- LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = &list_[hash & (length_ - 1)];
- while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
- ptr = &(*ptr)->next_hash;
- }
- return ptr;
- }
- void Resize() {
- uint32_t new_length = 4;
- while (new_length < elems_) {
- new_length *= 2;
- }
- LRUHandle** new_list = new LRUHandle*[new_length];
- memset(new_list, 0, sizeof(new_list[0]) * new_length);
- uint32_t count = 0;
- for (uint32_t i = 0; i < length_; i++) {
- LRUHandle* h = list_[i];
- while (h != nullptr) {
- LRUHandle* next = h->next_hash;
- uint32_t hash = h->hash;
- LRUHandle** ptr = &new_list[hash & (new_length - 1)];
- h->next_hash = *ptr;
- *ptr = h;
- h = next;
- count++;
- }
- }
- assert(elems_ == count);
- delete[] list_;
- list_ = new_list;
- length_ = new_length;
- }
- };
- class LRUCache {
- public:
- LRUCache();
- ~LRUCache();
-
- void SetCapacity(size_t capacity) { capacity_ = capacity; }
-
- Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
- size_t charge,
- void (*deleter)(const Slice& key, void* value));
- Cache::Handle* Lookup(const Slice& key, uint32_t hash);
- void Release(Cache::Handle* handle);
- void Erase(const Slice& key, uint32_t hash);
- void Prune();
- size_t TotalCharge() const {
- MutexLock l(&mutex_);
- return usage_;
- }
- private:
- void LRU_Remove(LRUHandle* e);
- void LRU_Append(LRUHandle* list, LRUHandle* e);
- void Ref(LRUHandle* e);
- void Unref(LRUHandle* e);
- bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
-
- size_t capacity_;
-
- mutable port::Mutex mutex_;
- size_t usage_ GUARDED_BY(mutex_);
-
-
-
- LRUHandle lru_ GUARDED_BY(mutex_);
-
-
- LRUHandle in_use_ GUARDED_BY(mutex_);
- HandleTable table_ GUARDED_BY(mutex_);
- };
- LRUCache::LRUCache() : capacity_(0), usage_(0) {
-
- lru_.next = &lru_;
- lru_.prev = &lru_;
- in_use_.next = &in_use_;
- in_use_.prev = &in_use_;
- }
- LRUCache::~LRUCache() {
- assert(in_use_.next == &in_use_);
- for (LRUHandle* e = lru_.next; e != &lru_;) {
- LRUHandle* next = e->next;
- assert(e->in_cache);
- e->in_cache = false;
- assert(e->refs == 1);
- Unref(e);
- e = next;
- }
- }
- void LRUCache::Ref(LRUHandle* e) {
- if (e->refs == 1 && e->in_cache) {
- LRU_Remove(e);
- LRU_Append(&in_use_, e);
- }
- e->refs++;
- }
- void LRUCache::Unref(LRUHandle* e) {
- assert(e->refs > 0);
- e->refs--;
- if (e->refs == 0) {
- assert(!e->in_cache);
- (*e->deleter)(e->key(), e->value);
- free(e);
- } else if (e->in_cache && e->refs == 1) {
-
- LRU_Remove(e);
- LRU_Append(&lru_, e);
- }
- }
- void LRUCache::LRU_Remove(LRUHandle* e) {
- e->next->prev = e->prev;
- e->prev->next = e->next;
- }
- void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
-
- e->next = list;
- e->prev = list->prev;
- e->prev->next = e;
- e->next->prev = e;
- }
- Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
- MutexLock l(&mutex_);
- LRUHandle* e = table_.Lookup(key, hash);
- if (e != nullptr) {
- Ref(e);
- }
- return reinterpret_cast<Cache::Handle*>(e);
- }
- void LRUCache::Release(Cache::Handle* handle) {
- MutexLock l(&mutex_);
- Unref(reinterpret_cast<LRUHandle*>(handle));
- }
- Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
- size_t charge,
- void (*deleter)(const Slice& key,
- void* value)) {
- MutexLock l(&mutex_);
- LRUHandle* e =
- reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
- e->value = value;
- e->deleter = deleter;
- e->charge = charge;
- e->key_length = key.size();
- e->hash = hash;
- e->in_cache = false;
- e->refs = 1;
- std::memcpy(e->key_data, key.data(), key.size());
- if (capacity_ > 0) {
- e->refs++;
- e->in_cache = true;
- LRU_Append(&in_use_, e);
- usage_ += charge;
- FinishErase(table_.Insert(e));
- } else {
-
- e->next = nullptr;
- }
- while (usage_ > capacity_ && lru_.next != &lru_) {
- LRUHandle* old = lru_.next;
- assert(old->refs == 1);
- bool erased = FinishErase(table_.Remove(old->key(), old->hash));
- if (!erased) {
- assert(erased);
- }
- }
- return reinterpret_cast<Cache::Handle*>(e);
- }
- bool LRUCache::FinishErase(LRUHandle* e) {
- if (e != nullptr) {
- assert(e->in_cache);
- LRU_Remove(e);
- e->in_cache = false;
- usage_ -= e->charge;
- Unref(e);
- }
- return e != nullptr;
- }
- void LRUCache::Erase(const Slice& key, uint32_t hash) {
- MutexLock l(&mutex_);
- FinishErase(table_.Remove(key, hash));
- }
- void LRUCache::Prune() {
- MutexLock l(&mutex_);
- while (lru_.next != &lru_) {
- LRUHandle* e = lru_.next;
- assert(e->refs == 1);
- bool erased = FinishErase(table_.Remove(e->key(), e->hash));
- if (!erased) {
- assert(erased);
- }
- }
- }
- static const int kNumShardBits = 4;
- static const int kNumShards = 1 << kNumShardBits;
- class ShardedLRUCache : public Cache {
- private:
- LRUCache shard_[kNumShards];
- port::Mutex id_mutex_;
- uint64_t last_id_;
- static inline uint32_t HashSlice(const Slice& s) {
- return Hash(s.data(), s.size(), 0);
- }
- static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }
- public:
- explicit ShardedLRUCache(size_t capacity) : last_id_(0) {
- const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
- for (int s = 0; s < kNumShards; s++) {
- shard_[s].SetCapacity(per_shard);
- }
- }
- ~ShardedLRUCache() override {}
- Handle* Insert(const Slice& key, void* value, size_t charge,
- void (*deleter)(const Slice& key, void* value)) override {
- const uint32_t hash = HashSlice(key);
- return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
- }
- Handle* Lookup(const Slice& key) override {
- const uint32_t hash = HashSlice(key);
- return shard_[Shard(hash)].Lookup(key, hash);
- }
- void Release(Handle* handle) override {
- LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
- shard_[Shard(h->hash)].Release(handle);
- }
- void Erase(const Slice& key) override {
- const uint32_t hash = HashSlice(key);
- shard_[Shard(hash)].Erase(key, hash);
- }
- void* Value(Handle* handle) override {
- return reinterpret_cast<LRUHandle*>(handle)->value;
- }
- uint64_t NewId() override {
- MutexLock l(&id_mutex_);
- return ++(last_id_);
- }
- void Prune() override {
- for (int s = 0; s < kNumShards; s++) {
- shard_[s].Prune();
- }
- }
- size_t TotalCharge() const override {
- size_t total = 0;
- for (int s = 0; s < kNumShards; s++) {
- total += shard_[s].TotalCharge();
- }
- return total;
- }
- };
- }
- Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }
- }
|