summaryrefslogtreecommitdiffstats
path: root/src/rocksdb/cache/lru_cache.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/rocksdb/cache/lru_cache.cc921
1 files changed, 921 insertions, 0 deletions
diff --git a/src/rocksdb/cache/lru_cache.cc b/src/rocksdb/cache/lru_cache.cc
new file mode 100644
index 000000000..c8e4d29ba
--- /dev/null
+++ b/src/rocksdb/cache/lru_cache.cc
@@ -0,0 +1,921 @@
+// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
+// This source code is licensed under both the GPLv2 (found in the
+// COPYING file in the root directory) and Apache 2.0 License
+// (found in the LICENSE.Apache file in the root directory).
+//
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "cache/lru_cache.h"
+
+#include <cassert>
+#include <cstdint>
+#include <cstdio>
+#include <cstdlib>
+
+#include "monitoring/perf_context_imp.h"
+#include "monitoring/statistics.h"
+#include "port/lang.h"
+#include "util/distributed_mutex.h"
+
+namespace ROCKSDB_NAMESPACE {
+namespace lru_cache {
+
+// A distinct pointer value for marking "dummy" cache entries
+void* const kDummyValueMarker = const_cast<char*>("kDummyValueMarker");
+
+LRUHandleTable::LRUHandleTable(int max_upper_hash_bits)
+ : length_bits_(/* historical starting size*/ 4),
+ list_(new LRUHandle* [size_t{1} << length_bits_] {}),
+ elems_(0),
+ max_length_bits_(max_upper_hash_bits) {}
+
+LRUHandleTable::~LRUHandleTable() {
+ ApplyToEntriesRange(
+ [](LRUHandle* h) {
+ if (!h->HasRefs()) {
+ h->Free();
+ }
+ },
+ 0, size_t{1} << length_bits_);
+}
+
+LRUHandle* LRUHandleTable::Lookup(const Slice& key, uint32_t hash) {
+ return *FindPointer(key, hash);
+}
+
+LRUHandle* LRUHandleTable::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_bits_) > 0) { // elems_ >= length
+ // Since each cache entry is fairly large, we aim for a small
+ // average linked list length (<= 1).
+ Resize();
+ }
+ }
+ return old;
+}
+
+LRUHandle* LRUHandleTable::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;
+}
+
+LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
+ LRUHandle** ptr = &list_[hash >> (32 - length_bits_)];
+ while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
+ ptr = &(*ptr)->next_hash;
+ }
+ return ptr;
+}
+
+void LRUHandleTable::Resize() {
+ if (length_bits_ >= max_length_bits_) {
+ // Due to reaching limit of hash information, if we made the table bigger,
+ // we would allocate more addresses but only the same number would be used.
+ return;
+ }
+ if (length_bits_ >= 31) {
+ // Avoid undefined behavior shifting uint32_t by 32.
+ return;
+ }
+
+ uint32_t old_length = uint32_t{1} << length_bits_;
+ int new_length_bits = length_bits_ + 1;
+ std::unique_ptr<LRUHandle* []> new_list {
+ new LRUHandle* [size_t{1} << new_length_bits] {}
+ };
+ uint32_t count = 0;
+ for (uint32_t i = 0; i < old_length; i++) {
+ LRUHandle* h = list_[i];
+ while (h != nullptr) {
+ LRUHandle* next = h->next_hash;
+ uint32_t hash = h->hash;
+ LRUHandle** ptr = &new_list[hash >> (32 - new_length_bits)];
+ h->next_hash = *ptr;
+ *ptr = h;
+ h = next;
+ count++;
+ }
+ }
+ assert(elems_ == count);
+ list_ = std::move(new_list);
+ length_bits_ = new_length_bits;
+}
+
+LRUCacheShard::LRUCacheShard(size_t capacity, bool strict_capacity_limit,
+ double high_pri_pool_ratio,
+ double low_pri_pool_ratio, bool use_adaptive_mutex,
+ CacheMetadataChargePolicy metadata_charge_policy,
+ int max_upper_hash_bits,
+ SecondaryCache* secondary_cache)
+ : CacheShardBase(metadata_charge_policy),
+ capacity_(0),
+ high_pri_pool_usage_(0),
+ low_pri_pool_usage_(0),
+ strict_capacity_limit_(strict_capacity_limit),
+ high_pri_pool_ratio_(high_pri_pool_ratio),
+ high_pri_pool_capacity_(0),
+ low_pri_pool_ratio_(low_pri_pool_ratio),
+ low_pri_pool_capacity_(0),
+ table_(max_upper_hash_bits),
+ usage_(0),
+ lru_usage_(0),
+ mutex_(use_adaptive_mutex),
+ secondary_cache_(secondary_cache) {
+ // Make empty circular linked list.
+ lru_.next = &lru_;
+ lru_.prev = &lru_;
+ lru_low_pri_ = &lru_;
+ lru_bottom_pri_ = &lru_;
+ SetCapacity(capacity);
+}
+
+void LRUCacheShard::EraseUnRefEntries() {
+ autovector<LRUHandle*> last_reference_list;
+ {
+ DMutexLock l(mutex_);
+ while (lru_.next != &lru_) {
+ LRUHandle* old = lru_.next;
+ // LRU list contains only elements which can be evicted.
+ assert(old->InCache() && !old->HasRefs());
+ LRU_Remove(old);
+ table_.Remove(old->key(), old->hash);
+ old->SetInCache(false);
+ assert(usage_ >= old->total_charge);
+ usage_ -= old->total_charge;
+ last_reference_list.push_back(old);
+ }
+ }
+
+ for (auto entry : last_reference_list) {
+ entry->Free();
+ }
+}
+
+void LRUCacheShard::ApplyToSomeEntries(
+ const std::function<void(const Slice& key, void* value, size_t charge,
+ DeleterFn deleter)>& callback,
+ size_t average_entries_per_lock, size_t* state) {
+ // The state is essentially going to be the starting hash, which works
+ // nicely even if we resize between calls because we use upper-most
+ // hash bits for table indexes.
+ DMutexLock l(mutex_);
+ int length_bits = table_.GetLengthBits();
+ size_t length = size_t{1} << length_bits;
+
+ assert(average_entries_per_lock > 0);
+ // Assuming we are called with same average_entries_per_lock repeatedly,
+ // this simplifies some logic (index_end will not overflow).
+ assert(average_entries_per_lock < length || *state == 0);
+
+ size_t index_begin = *state >> (sizeof(size_t) * 8u - length_bits);
+ size_t index_end = index_begin + average_entries_per_lock;
+ if (index_end >= length) {
+ // Going to end
+ index_end = length;
+ *state = SIZE_MAX;
+ } else {
+ *state = index_end << (sizeof(size_t) * 8u - length_bits);
+ }
+
+ table_.ApplyToEntriesRange(
+ [callback,
+ metadata_charge_policy = metadata_charge_policy_](LRUHandle* h) {
+ DeleterFn deleter = h->IsSecondaryCacheCompatible()
+ ? h->info_.helper->del_cb
+ : h->info_.deleter;
+ callback(h->key(), h->value, h->GetCharge(metadata_charge_policy),
+ deleter);
+ },
+ index_begin, index_end);
+}
+
+void LRUCacheShard::TEST_GetLRUList(LRUHandle** lru, LRUHandle** lru_low_pri,
+ LRUHandle** lru_bottom_pri) {
+ DMutexLock l(mutex_);
+ *lru = &lru_;
+ *lru_low_pri = lru_low_pri_;
+ *lru_bottom_pri = lru_bottom_pri_;
+}
+
+size_t LRUCacheShard::TEST_GetLRUSize() {
+ DMutexLock l(mutex_);
+ LRUHandle* lru_handle = lru_.next;
+ size_t lru_size = 0;
+ while (lru_handle != &lru_) {
+ lru_size++;
+ lru_handle = lru_handle->next;
+ }
+ return lru_size;
+}
+
+double LRUCacheShard::GetHighPriPoolRatio() {
+ DMutexLock l(mutex_);
+ return high_pri_pool_ratio_;
+}
+
+double LRUCacheShard::GetLowPriPoolRatio() {
+ DMutexLock l(mutex_);
+ return low_pri_pool_ratio_;
+}
+
+void LRUCacheShard::LRU_Remove(LRUHandle* e) {
+ assert(e->next != nullptr);
+ assert(e->prev != nullptr);
+ if (lru_low_pri_ == e) {
+ lru_low_pri_ = e->prev;
+ }
+ if (lru_bottom_pri_ == e) {
+ lru_bottom_pri_ = e->prev;
+ }
+ e->next->prev = e->prev;
+ e->prev->next = e->next;
+ e->prev = e->next = nullptr;
+ assert(lru_usage_ >= e->total_charge);
+ lru_usage_ -= e->total_charge;
+ assert(!e->InHighPriPool() || !e->InLowPriPool());
+ if (e->InHighPriPool()) {
+ assert(high_pri_pool_usage_ >= e->total_charge);
+ high_pri_pool_usage_ -= e->total_charge;
+ } else if (e->InLowPriPool()) {
+ assert(low_pri_pool_usage_ >= e->total_charge);
+ low_pri_pool_usage_ -= e->total_charge;
+ }
+}
+
+void LRUCacheShard::LRU_Insert(LRUHandle* e) {
+ assert(e->next == nullptr);
+ assert(e->prev == nullptr);
+ if (high_pri_pool_ratio_ > 0 && (e->IsHighPri() || e->HasHit())) {
+ // Inset "e" to head of LRU list.
+ e->next = &lru_;
+ e->prev = lru_.prev;
+ e->prev->next = e;
+ e->next->prev = e;
+ e->SetInHighPriPool(true);
+ e->SetInLowPriPool(false);
+ high_pri_pool_usage_ += e->total_charge;
+ MaintainPoolSize();
+ } else if (low_pri_pool_ratio_ > 0 &&
+ (e->IsHighPri() || e->IsLowPri() || e->HasHit())) {
+ // Insert "e" to the head of low-pri pool.
+ e->next = lru_low_pri_->next;
+ e->prev = lru_low_pri_;
+ e->prev->next = e;
+ e->next->prev = e;
+ e->SetInHighPriPool(false);
+ e->SetInLowPriPool(true);
+ low_pri_pool_usage_ += e->total_charge;
+ MaintainPoolSize();
+ lru_low_pri_ = e;
+ } else {
+ // Insert "e" to the head of bottom-pri pool.
+ e->next = lru_bottom_pri_->next;
+ e->prev = lru_bottom_pri_;
+ e->prev->next = e;
+ e->next->prev = e;
+ e->SetInHighPriPool(false);
+ e->SetInLowPriPool(false);
+ // if the low-pri pool is empty, lru_low_pri_ also needs to be updated.
+ if (lru_bottom_pri_ == lru_low_pri_) {
+ lru_low_pri_ = e;
+ }
+ lru_bottom_pri_ = e;
+ }
+ lru_usage_ += e->total_charge;
+}
+
+void LRUCacheShard::MaintainPoolSize() {
+ while (high_pri_pool_usage_ > high_pri_pool_capacity_) {
+ // Overflow last entry in high-pri pool to low-pri pool.
+ lru_low_pri_ = lru_low_pri_->next;
+ assert(lru_low_pri_ != &lru_);
+ lru_low_pri_->SetInHighPriPool(false);
+ lru_low_pri_->SetInLowPriPool(true);
+ assert(high_pri_pool_usage_ >= lru_low_pri_->total_charge);
+ high_pri_pool_usage_ -= lru_low_pri_->total_charge;
+ low_pri_pool_usage_ += lru_low_pri_->total_charge;
+ }
+
+ while (low_pri_pool_usage_ > low_pri_pool_capacity_) {
+ // Overflow last entry in low-pri pool to bottom-pri pool.
+ lru_bottom_pri_ = lru_bottom_pri_->next;
+ assert(lru_bottom_pri_ != &lru_);
+ lru_bottom_pri_->SetInHighPriPool(false);
+ lru_bottom_pri_->SetInLowPriPool(false);
+ assert(low_pri_pool_usage_ >= lru_bottom_pri_->total_charge);
+ low_pri_pool_usage_ -= lru_bottom_pri_->total_charge;
+ }
+}
+
+void LRUCacheShard::EvictFromLRU(size_t charge,
+ autovector<LRUHandle*>* deleted) {
+ while ((usage_ + charge) > capacity_ && lru_.next != &lru_) {
+ LRUHandle* old = lru_.next;
+ // LRU list contains only elements which can be evicted.
+ assert(old->InCache() && !old->HasRefs());
+ LRU_Remove(old);
+ table_.Remove(old->key(), old->hash);
+ old->SetInCache(false);
+ assert(usage_ >= old->total_charge);
+ usage_ -= old->total_charge;
+ deleted->push_back(old);
+ }
+}
+
+void LRUCacheShard::TryInsertIntoSecondaryCache(
+ autovector<LRUHandle*> evicted_handles) {
+ for (auto entry : evicted_handles) {
+ if (secondary_cache_ && entry->IsSecondaryCacheCompatible() &&
+ !entry->IsInSecondaryCache()) {
+ secondary_cache_->Insert(entry->key(), entry->value, entry->info_.helper)
+ .PermitUncheckedError();
+ }
+ // Free the entries here outside of mutex for performance reasons.
+ entry->Free();
+ }
+}
+
+void LRUCacheShard::SetCapacity(size_t capacity) {
+ autovector<LRUHandle*> last_reference_list;
+ {
+ DMutexLock l(mutex_);
+ capacity_ = capacity;
+ high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
+ low_pri_pool_capacity_ = capacity_ * low_pri_pool_ratio_;
+ EvictFromLRU(0, &last_reference_list);
+ }
+
+ TryInsertIntoSecondaryCache(last_reference_list);
+}
+
+void LRUCacheShard::SetStrictCapacityLimit(bool strict_capacity_limit) {
+ DMutexLock l(mutex_);
+ strict_capacity_limit_ = strict_capacity_limit;
+}
+
+Status LRUCacheShard::InsertItem(LRUHandle* e, LRUHandle** handle,
+ bool free_handle_on_fail) {
+ Status s = Status::OK();
+ autovector<LRUHandle*> last_reference_list;
+
+ {
+ DMutexLock l(mutex_);
+
+ // Free the space following strict LRU policy until enough space
+ // is freed or the lru list is empty.
+ EvictFromLRU(e->total_charge, &last_reference_list);
+
+ if ((usage_ + e->total_charge) > capacity_ &&
+ (strict_capacity_limit_ || handle == nullptr)) {
+ e->SetInCache(false);
+ if (handle == nullptr) {
+ // Don't insert the entry but still return ok, as if the entry inserted
+ // into cache and get evicted immediately.
+ last_reference_list.push_back(e);
+ } else {
+ if (free_handle_on_fail) {
+ free(e);
+ *handle = nullptr;
+ }
+ s = Status::MemoryLimit("Insert failed due to LRU cache being full.");
+ }
+ } else {
+ // Insert into the cache. Note that the cache might get larger than its
+ // capacity if not enough space was freed up.
+ LRUHandle* old = table_.Insert(e);
+ usage_ += e->total_charge;
+ if (old != nullptr) {
+ s = Status::OkOverwritten();
+ assert(old->InCache());
+ old->SetInCache(false);
+ if (!old->HasRefs()) {
+ // old is on LRU because it's in cache and its reference count is 0.
+ LRU_Remove(old);
+ assert(usage_ >= old->total_charge);
+ usage_ -= old->total_charge;
+ last_reference_list.push_back(old);
+ }
+ }
+ if (handle == nullptr) {
+ LRU_Insert(e);
+ } else {
+ // If caller already holds a ref, no need to take one here.
+ if (!e->HasRefs()) {
+ e->Ref();
+ }
+ *handle = e;
+ }
+ }
+ }
+
+ TryInsertIntoSecondaryCache(last_reference_list);
+
+ return s;
+}
+
+void LRUCacheShard::Promote(LRUHandle* e) {
+ SecondaryCacheResultHandle* secondary_handle = e->sec_handle;
+
+ assert(secondary_handle->IsReady());
+ // e is not thread-shared here; OK to modify "immutable" fields as well as
+ // "mutable" (normally requiring mutex)
+ e->SetIsPending(false);
+ e->value = secondary_handle->Value();
+ assert(e->total_charge == 0);
+ size_t value_size = secondary_handle->Size();
+ delete secondary_handle;
+
+ if (e->value) {
+ e->CalcTotalCharge(value_size, metadata_charge_policy_);
+ Status s;
+ if (e->IsStandalone()) {
+ assert(secondary_cache_ && secondary_cache_->SupportForceErase());
+
+ // Insert a dummy handle and return a standalone handle to caller.
+ // Charge the standalone handle.
+ autovector<LRUHandle*> last_reference_list;
+ bool free_standalone_handle{false};
+ {
+ DMutexLock l(mutex_);
+
+ // Free the space following strict LRU policy until enough space
+ // is freed or the lru list is empty.
+ EvictFromLRU(e->total_charge, &last_reference_list);
+
+ if ((usage_ + e->total_charge) > capacity_ && strict_capacity_limit_) {
+ free_standalone_handle = true;
+ } else {
+ usage_ += e->total_charge;
+ }
+ }
+
+ TryInsertIntoSecondaryCache(last_reference_list);
+ if (free_standalone_handle) {
+ e->Unref();
+ e->Free();
+ e = nullptr;
+ } else {
+ PERF_COUNTER_ADD(block_cache_standalone_handle_count, 1);
+ }
+
+ // Insert a dummy handle into the primary cache. This dummy handle is
+ // not IsSecondaryCacheCompatible().
+ // FIXME? This should not overwrite an existing non-dummy entry in the
+ // rare case that one exists
+ Cache::Priority priority =
+ e->IsHighPri() ? Cache::Priority::HIGH : Cache::Priority::LOW;
+ s = Insert(e->key(), e->hash, kDummyValueMarker, /*charge=*/0,
+ /*deleter=*/nullptr, /*helper=*/nullptr, /*handle=*/nullptr,
+ priority);
+ } else {
+ e->SetInCache(true);
+ LRUHandle* handle = e;
+ // This InsertItem() could fail if the cache is over capacity and
+ // strict_capacity_limit_ is true. In such a case, we don't want
+ // InsertItem() to free the handle, since the item is already in memory
+ // and the caller will most likely just read it from disk if we erase it
+ // here.
+ s = InsertItem(e, &handle, /*free_handle_on_fail=*/false);
+ if (s.ok()) {
+ PERF_COUNTER_ADD(block_cache_real_handle_count, 1);
+ }
+ }
+
+ if (!s.ok()) {
+ // Item is in memory, but not accounted against the cache capacity.
+ // When the handle is released, the item should get deleted.
+ assert(!e->InCache());
+ }
+ } else {
+ // Secondary cache lookup failed. The caller will take care of detecting
+ // this and eventually releasing e.
+ assert(!e->value);
+ assert(!e->InCache());
+ }
+}
+
+LRUHandle* LRUCacheShard::Lookup(const Slice& key, uint32_t hash,
+ const Cache::CacheItemHelper* helper,
+ const Cache::CreateCallback& create_cb,
+ Cache::Priority priority, bool wait,
+ Statistics* stats) {
+ LRUHandle* e = nullptr;
+ bool found_dummy_entry{false};
+ {
+ DMutexLock l(mutex_);
+ e = table_.Lookup(key, hash);
+ if (e != nullptr) {
+ assert(e->InCache());
+ if (e->value == kDummyValueMarker) {
+ // For a dummy handle, if it was retrieved from secondary cache,
+ // it may still exist in secondary cache.
+ // If the handle exists in secondary cache, the value should be
+ // erased from sec cache and be inserted into primary cache.
+ found_dummy_entry = true;
+ // Let the dummy entry be overwritten
+ e = nullptr;
+ } else {
+ if (!e->HasRefs()) {
+ // The entry is in LRU since it's in hash and has no external
+ // references.
+ LRU_Remove(e);
+ }
+ e->Ref();
+ e->SetHit();
+ }
+ }
+ }
+
+ // If handle table lookup failed or the handle is a dummy one, allocate
+ // a handle outside the mutex if we re going to lookup in the secondary cache.
+ //
+ // When a block is firstly Lookup from CompressedSecondaryCache, we just
+ // insert a dummy block into the primary cache (charging the actual size of
+ // the block) and don't erase the block from CompressedSecondaryCache. A
+ // standalone handle is returned to the caller. Only if the block is hit
+ // again, we erase it from CompressedSecondaryCache and add it into the
+ // primary cache.
+ if (!e && secondary_cache_ && helper && helper->saveto_cb) {
+ // For objects from the secondary cache, we expect the caller to provide
+ // a way to create/delete the primary cache object. The only case where
+ // a deleter would not be required is for dummy entries inserted for
+ // accounting purposes, which we won't demote to the secondary cache
+ // anyway.
+ assert(create_cb && helper->del_cb);
+ bool is_in_sec_cache{false};
+ std::unique_ptr<SecondaryCacheResultHandle> secondary_handle =
+ secondary_cache_->Lookup(key, create_cb, wait, found_dummy_entry,
+ is_in_sec_cache);
+ if (secondary_handle != nullptr) {
+ e = static_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
+
+ e->m_flags = 0;
+ e->im_flags = 0;
+ e->SetSecondaryCacheCompatible(true);
+ e->info_.helper = helper;
+ e->key_length = key.size();
+ e->hash = hash;
+ e->refs = 0;
+ e->next = e->prev = nullptr;
+ e->SetPriority(priority);
+ memcpy(e->key_data, key.data(), key.size());
+ e->value = nullptr;
+ e->sec_handle = secondary_handle.release();
+ e->total_charge = 0;
+ e->Ref();
+ e->SetIsInSecondaryCache(is_in_sec_cache);
+ e->SetIsStandalone(secondary_cache_->SupportForceErase() &&
+ !found_dummy_entry);
+
+ if (wait) {
+ Promote(e);
+ if (e) {
+ if (!e->value) {
+ // The secondary cache returned a handle, but the lookup failed.
+ e->Unref();
+ e->Free();
+ e = nullptr;
+ } else {
+ PERF_COUNTER_ADD(secondary_cache_hit_count, 1);
+ RecordTick(stats, SECONDARY_CACHE_HITS);
+ }
+ }
+ } else {
+ // If wait is false, we always return a handle and let the caller
+ // release the handle after checking for success or failure.
+ e->SetIsPending(true);
+ // This may be slightly inaccurate, if the lookup eventually fails.
+ // But the probability is very low.
+ PERF_COUNTER_ADD(secondary_cache_hit_count, 1);
+ RecordTick(stats, SECONDARY_CACHE_HITS);
+ }
+ } else {
+ // Caller will most likely overwrite the dummy entry with an Insert
+ // after this Lookup fails
+ assert(e == nullptr);
+ }
+ }
+ return e;
+}
+
+bool LRUCacheShard::Ref(LRUHandle* e) {
+ DMutexLock l(mutex_);
+ // To create another reference - entry must be already externally referenced.
+ assert(e->HasRefs());
+ // Pending handles are not for sharing
+ assert(!e->IsPending());
+ e->Ref();
+ return true;
+}
+
+void LRUCacheShard::SetHighPriorityPoolRatio(double high_pri_pool_ratio) {
+ DMutexLock l(mutex_);
+ high_pri_pool_ratio_ = high_pri_pool_ratio;
+ high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
+ MaintainPoolSize();
+}
+
+void LRUCacheShard::SetLowPriorityPoolRatio(double low_pri_pool_ratio) {
+ DMutexLock l(mutex_);
+ low_pri_pool_ratio_ = low_pri_pool_ratio;
+ low_pri_pool_capacity_ = capacity_ * low_pri_pool_ratio_;
+ MaintainPoolSize();
+}
+
+bool LRUCacheShard::Release(LRUHandle* e, bool /*useful*/,
+ bool erase_if_last_ref) {
+ if (e == nullptr) {
+ return false;
+ }
+ bool last_reference = false;
+ // Must Wait or WaitAll first on pending handles. Otherwise, would leak
+ // a secondary cache handle.
+ assert(!e->IsPending());
+ {
+ DMutexLock l(mutex_);
+ last_reference = e->Unref();
+ if (last_reference && e->InCache()) {
+ // The item is still in cache, and nobody else holds a reference to it.
+ if (usage_ > capacity_ || erase_if_last_ref) {
+ // The LRU list must be empty since the cache is full.
+ assert(lru_.next == &lru_ || erase_if_last_ref);
+ // Take this opportunity and remove the item.
+ table_.Remove(e->key(), e->hash);
+ e->SetInCache(false);
+ } else {
+ // Put the item back on the LRU list, and don't free it.
+ LRU_Insert(e);
+ last_reference = false;
+ }
+ }
+ // If it was the last reference, then decrement the cache usage.
+ if (last_reference) {
+ assert(usage_ >= e->total_charge);
+ usage_ -= e->total_charge;
+ }
+ }
+
+ // Free the entry here outside of mutex for performance reasons.
+ if (last_reference) {
+ e->Free();
+ }
+ return last_reference;
+}
+
+Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value,
+ size_t charge,
+ void (*deleter)(const Slice& key, void* value),
+ const Cache::CacheItemHelper* helper,
+ LRUHandle** handle, Cache::Priority priority) {
+ // Allocate the memory here outside of the mutex.
+ // If the cache is full, we'll have to release it.
+ // It shouldn't happen very often though.
+ LRUHandle* e =
+ static_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
+
+ e->value = value;
+ e->m_flags = 0;
+ e->im_flags = 0;
+ if (helper) {
+ // Use only one of the two parameters
+ assert(deleter == nullptr);
+ // value == nullptr is reserved for indicating failure for when secondary
+ // cache compatible
+ assert(value != nullptr);
+ e->SetSecondaryCacheCompatible(true);
+ e->info_.helper = helper;
+ } else {
+ e->info_.deleter = deleter;
+ }
+ e->key_length = key.size();
+ e->hash = hash;
+ e->refs = 0;
+ e->next = e->prev = nullptr;
+ e->SetInCache(true);
+ e->SetPriority(priority);
+ memcpy(e->key_data, key.data(), key.size());
+ e->CalcTotalCharge(charge, metadata_charge_policy_);
+
+ return InsertItem(e, handle, /* free_handle_on_fail */ true);
+}
+
+void LRUCacheShard::Erase(const Slice& key, uint32_t hash) {
+ LRUHandle* e;
+ bool last_reference = false;
+ {
+ DMutexLock l(mutex_);
+ e = table_.Remove(key, hash);
+ if (e != nullptr) {
+ assert(e->InCache());
+ e->SetInCache(false);
+ if (!e->HasRefs()) {
+ // The entry is in LRU since it's in hash and has no external references
+ LRU_Remove(e);
+ assert(usage_ >= e->total_charge);
+ usage_ -= e->total_charge;
+ last_reference = true;
+ }
+ }
+ }
+
+ // Free the entry here outside of mutex for performance reasons.
+ // last_reference will only be true if e != nullptr.
+ if (last_reference) {
+ e->Free();
+ }
+}
+
+bool LRUCacheShard::IsReady(LRUHandle* e) {
+ bool ready = true;
+ if (e->IsPending()) {
+ assert(secondary_cache_);
+ assert(e->sec_handle);
+ ready = e->sec_handle->IsReady();
+ }
+ return ready;
+}
+
+size_t LRUCacheShard::GetUsage() const {
+ DMutexLock l(mutex_);
+ return usage_;
+}
+
+size_t LRUCacheShard::GetPinnedUsage() const {
+ DMutexLock l(mutex_);
+ assert(usage_ >= lru_usage_);
+ return usage_ - lru_usage_;
+}
+
+size_t LRUCacheShard::GetOccupancyCount() const {
+ DMutexLock l(mutex_);
+ return table_.GetOccupancyCount();
+}
+
+size_t LRUCacheShard::GetTableAddressCount() const {
+ DMutexLock l(mutex_);
+ return size_t{1} << table_.GetLengthBits();
+}
+
+void LRUCacheShard::AppendPrintableOptions(std::string& str) const {
+ const int kBufferSize = 200;
+ char buffer[kBufferSize];
+ {
+ DMutexLock l(mutex_);
+ snprintf(buffer, kBufferSize, " high_pri_pool_ratio: %.3lf\n",
+ high_pri_pool_ratio_);
+ snprintf(buffer + strlen(buffer), kBufferSize - strlen(buffer),
+ " low_pri_pool_ratio: %.3lf\n", low_pri_pool_ratio_);
+ }
+ str.append(buffer);
+}
+
+LRUCache::LRUCache(size_t capacity, int num_shard_bits,
+ bool strict_capacity_limit, double high_pri_pool_ratio,
+ double low_pri_pool_ratio,
+ std::shared_ptr<MemoryAllocator> allocator,
+ bool use_adaptive_mutex,
+ CacheMetadataChargePolicy metadata_charge_policy,
+ std::shared_ptr<SecondaryCache> _secondary_cache)
+ : ShardedCache(capacity, num_shard_bits, strict_capacity_limit,
+ std::move(allocator)),
+ secondary_cache_(std::move(_secondary_cache)) {
+ size_t per_shard = GetPerShardCapacity();
+ SecondaryCache* secondary_cache = secondary_cache_.get();
+ InitShards([=](LRUCacheShard* cs) {
+ new (cs) LRUCacheShard(
+ per_shard, strict_capacity_limit, high_pri_pool_ratio,
+ low_pri_pool_ratio, use_adaptive_mutex, metadata_charge_policy,
+ /* max_upper_hash_bits */ 32 - num_shard_bits, secondary_cache);
+ });
+}
+
+void* LRUCache::Value(Handle* handle) {
+ auto h = reinterpret_cast<const LRUHandle*>(handle);
+ assert(!h->IsPending() || h->value == nullptr);
+ assert(h->value != kDummyValueMarker);
+ return h->value;
+}
+
+size_t LRUCache::GetCharge(Handle* handle) const {
+ return reinterpret_cast<const LRUHandle*>(handle)->GetCharge(
+ GetShard(0).metadata_charge_policy_);
+}
+
+Cache::DeleterFn LRUCache::GetDeleter(Handle* handle) const {
+ auto h = reinterpret_cast<const LRUHandle*>(handle);
+ if (h->IsSecondaryCacheCompatible()) {
+ return h->info_.helper->del_cb;
+ } else {
+ return h->info_.deleter;
+ }
+}
+
+size_t LRUCache::TEST_GetLRUSize() {
+ return SumOverShards([](LRUCacheShard& cs) { return cs.TEST_GetLRUSize(); });
+}
+
+double LRUCache::GetHighPriPoolRatio() {
+ return GetShard(0).GetHighPriPoolRatio();
+}
+
+void LRUCache::WaitAll(std::vector<Handle*>& handles) {
+ if (secondary_cache_) {
+ std::vector<SecondaryCacheResultHandle*> sec_handles;
+ sec_handles.reserve(handles.size());
+ for (Handle* handle : handles) {
+ if (!handle) {
+ continue;
+ }
+ LRUHandle* lru_handle = reinterpret_cast<LRUHandle*>(handle);
+ if (!lru_handle->IsPending()) {
+ continue;
+ }
+ sec_handles.emplace_back(lru_handle->sec_handle);
+ }
+ secondary_cache_->WaitAll(sec_handles);
+ for (Handle* handle : handles) {
+ if (!handle) {
+ continue;
+ }
+ LRUHandle* lru_handle = reinterpret_cast<LRUHandle*>(handle);
+ if (!lru_handle->IsPending()) {
+ continue;
+ }
+ GetShard(lru_handle->hash).Promote(lru_handle);
+ }
+ }
+}
+
+void LRUCache::AppendPrintableOptions(std::string& str) const {
+ ShardedCache::AppendPrintableOptions(str); // options from shard
+ if (secondary_cache_) {
+ str.append(" secondary_cache:\n");
+ str.append(secondary_cache_->GetPrintableOptions());
+ }
+}
+
+} // namespace lru_cache
+
+std::shared_ptr<Cache> NewLRUCache(
+ size_t capacity, int num_shard_bits, bool strict_capacity_limit,
+ double high_pri_pool_ratio,
+ std::shared_ptr<MemoryAllocator> memory_allocator, bool use_adaptive_mutex,
+ CacheMetadataChargePolicy metadata_charge_policy,
+ const std::shared_ptr<SecondaryCache>& secondary_cache,
+ double low_pri_pool_ratio) {
+ if (num_shard_bits >= 20) {
+ return nullptr; // The cache cannot be sharded into too many fine pieces.
+ }
+ if (high_pri_pool_ratio < 0.0 || high_pri_pool_ratio > 1.0) {
+ // Invalid high_pri_pool_ratio
+ return nullptr;
+ }
+ if (low_pri_pool_ratio < 0.0 || low_pri_pool_ratio > 1.0) {
+ // Invalid low_pri_pool_ratio
+ return nullptr;
+ }
+ if (low_pri_pool_ratio + high_pri_pool_ratio > 1.0) {
+ // Invalid high_pri_pool_ratio and low_pri_pool_ratio combination
+ return nullptr;
+ }
+ if (num_shard_bits < 0) {
+ num_shard_bits = GetDefaultCacheShardBits(capacity);
+ }
+ return std::make_shared<LRUCache>(
+ capacity, num_shard_bits, strict_capacity_limit, high_pri_pool_ratio,
+ low_pri_pool_ratio, std::move(memory_allocator), use_adaptive_mutex,
+ metadata_charge_policy, secondary_cache);
+}
+
+std::shared_ptr<Cache> NewLRUCache(const LRUCacheOptions& cache_opts) {
+ return NewLRUCache(cache_opts.capacity, cache_opts.num_shard_bits,
+ cache_opts.strict_capacity_limit,
+ cache_opts.high_pri_pool_ratio,
+ cache_opts.memory_allocator, cache_opts.use_adaptive_mutex,
+ cache_opts.metadata_charge_policy,
+ cache_opts.secondary_cache, cache_opts.low_pri_pool_ratio);
+}
+
+std::shared_ptr<Cache> NewLRUCache(
+ size_t capacity, int num_shard_bits, bool strict_capacity_limit,
+ double high_pri_pool_ratio,
+ std::shared_ptr<MemoryAllocator> memory_allocator, bool use_adaptive_mutex,
+ CacheMetadataChargePolicy metadata_charge_policy,
+ double low_pri_pool_ratio) {
+ return NewLRUCache(capacity, num_shard_bits, strict_capacity_limit,
+ high_pri_pool_ratio, memory_allocator, use_adaptive_mutex,
+ metadata_charge_policy, nullptr, low_pri_pool_ratio);
+}
+} // namespace ROCKSDB_NAMESPACE
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-16 10:29:29 +0000