1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #include "cache/lru_cache.h"
11
12 #include <cassert>
13 #include <cstdint>
14 #include <cstdio>
15
16 #include "monitoring/perf_context_imp.h"
17 #include "monitoring/statistics.h"
18 #include "util/mutexlock.h"
19
20 namespace ROCKSDB_NAMESPACE {
21
LRUHandleTable(int max_upper_hash_bits)22 LRUHandleTable::LRUHandleTable(int max_upper_hash_bits)
23 : length_bits_(/* historical starting size*/ 4),
24 list_(new LRUHandle* [size_t{1} << length_bits_] {}),
25 elems_(0),
26 max_length_bits_(max_upper_hash_bits) {}
27
~LRUHandleTable()28 LRUHandleTable::~LRUHandleTable() {
29 ApplyToEntriesRange(
30 [](LRUHandle* h) {
31 if (!h->HasRefs()) {
32 h->Free();
33 }
34 },
35 0, uint32_t{1} << length_bits_);
36 }
37
Lookup(const Slice & key,uint32_t hash)38 LRUHandle* LRUHandleTable::Lookup(const Slice& key, uint32_t hash) {
39 return *FindPointer(key, hash);
40 }
41
Insert(LRUHandle * h)42 LRUHandle* LRUHandleTable::Insert(LRUHandle* h) {
43 LRUHandle** ptr = FindPointer(h->key(), h->hash);
44 LRUHandle* old = *ptr;
45 h->next_hash = (old == nullptr ? nullptr : old->next_hash);
46 *ptr = h;
47 if (old == nullptr) {
48 ++elems_;
49 if ((elems_ >> length_bits_) > 0) { // elems_ >= length
50 // Since each cache entry is fairly large, we aim for a small
51 // average linked list length (<= 1).
52 Resize();
53 }
54 }
55 return old;
56 }
57
Remove(const Slice & key,uint32_t hash)58 LRUHandle* LRUHandleTable::Remove(const Slice& key, uint32_t hash) {
59 LRUHandle** ptr = FindPointer(key, hash);
60 LRUHandle* result = *ptr;
61 if (result != nullptr) {
62 *ptr = result->next_hash;
63 --elems_;
64 }
65 return result;
66 }
67
FindPointer(const Slice & key,uint32_t hash)68 LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
69 LRUHandle** ptr = &list_[hash >> (32 - length_bits_)];
70 while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
71 ptr = &(*ptr)->next_hash;
72 }
73 return ptr;
74 }
75
Resize()76 void LRUHandleTable::Resize() {
77 if (length_bits_ >= max_length_bits_) {
78 // Due to reaching limit of hash information, if we made the table
79 // bigger, we would allocate more addresses but only the same
80 // number would be used.
81 return;
82 }
83 if (length_bits_ >= 31) {
84 // Avoid undefined behavior shifting uint32_t by 32
85 return;
86 }
87
88 uint32_t old_length = uint32_t{1} << length_bits_;
89 int new_length_bits = length_bits_ + 1;
90 std::unique_ptr<LRUHandle* []> new_list {
91 new LRUHandle* [size_t{1} << new_length_bits] {}
92 };
93 uint32_t count = 0;
94 for (uint32_t i = 0; i < old_length; i++) {
95 LRUHandle* h = list_[i];
96 while (h != nullptr) {
97 LRUHandle* next = h->next_hash;
98 uint32_t hash = h->hash;
99 LRUHandle** ptr = &new_list[hash >> (32 - new_length_bits)];
100 h->next_hash = *ptr;
101 *ptr = h;
102 h = next;
103 count++;
104 }
105 }
106 assert(elems_ == count);
107 list_ = std::move(new_list);
108 length_bits_ = new_length_bits;
109 }
110
LRUCacheShard(size_t capacity,bool strict_capacity_limit,double high_pri_pool_ratio,bool use_adaptive_mutex,CacheMetadataChargePolicy metadata_charge_policy,int max_upper_hash_bits,const std::shared_ptr<SecondaryCache> & secondary_cache)111 LRUCacheShard::LRUCacheShard(
112 size_t capacity, bool strict_capacity_limit, double high_pri_pool_ratio,
113 bool use_adaptive_mutex, CacheMetadataChargePolicy metadata_charge_policy,
114 int max_upper_hash_bits,
115 const std::shared_ptr<SecondaryCache>& secondary_cache)
116 : capacity_(0),
117 high_pri_pool_usage_(0),
118 strict_capacity_limit_(strict_capacity_limit),
119 high_pri_pool_ratio_(high_pri_pool_ratio),
120 high_pri_pool_capacity_(0),
121 table_(max_upper_hash_bits),
122 usage_(0),
123 lru_usage_(0),
124 mutex_(use_adaptive_mutex),
125 secondary_cache_(secondary_cache) {
126 set_metadata_charge_policy(metadata_charge_policy);
127 // Make empty circular linked list
128 lru_.next = &lru_;
129 lru_.prev = &lru_;
130 lru_low_pri_ = &lru_;
131 SetCapacity(capacity);
132 }
133
EraseUnRefEntries()134 void LRUCacheShard::EraseUnRefEntries() {
135 autovector<LRUHandle*> last_reference_list;
136 {
137 MutexLock l(&mutex_);
138 while (lru_.next != &lru_) {
139 LRUHandle* old = lru_.next;
140 // LRU list contains only elements which can be evicted
141 assert(old->InCache() && !old->HasRefs());
142 LRU_Remove(old);
143 table_.Remove(old->key(), old->hash);
144 old->SetInCache(false);
145 size_t total_charge = old->CalcTotalCharge(metadata_charge_policy_);
146 assert(usage_ >= total_charge);
147 usage_ -= total_charge;
148 last_reference_list.push_back(old);
149 }
150 }
151
152 for (auto entry : last_reference_list) {
153 entry->Free();
154 }
155 }
156
ApplyToSomeEntries(const std::function<void (const Slice & key,void * value,size_t charge,DeleterFn deleter)> & callback,uint32_t average_entries_per_lock,uint32_t * state)157 void LRUCacheShard::ApplyToSomeEntries(
158 const std::function<void(const Slice& key, void* value, size_t charge,
159 DeleterFn deleter)>& callback,
160 uint32_t average_entries_per_lock, uint32_t* state) {
161 // The state is essentially going to be the starting hash, which works
162 // nicely even if we resize between calls because we use upper-most
163 // hash bits for table indexes.
164 MutexLock l(&mutex_);
165 uint32_t length_bits = table_.GetLengthBits();
166 uint32_t length = uint32_t{1} << length_bits;
167
168 assert(average_entries_per_lock > 0);
169 // Assuming we are called with same average_entries_per_lock repeatedly,
170 // this simplifies some logic (index_end will not overflow)
171 assert(average_entries_per_lock < length || *state == 0);
172
173 uint32_t index_begin = *state >> (32 - length_bits);
174 uint32_t index_end = index_begin + average_entries_per_lock;
175 if (index_end >= length) {
176 // Going to end
177 index_end = length;
178 *state = UINT32_MAX;
179 } else {
180 *state = index_end << (32 - length_bits);
181 }
182
183 table_.ApplyToEntriesRange(
184 [callback](LRUHandle* h) {
185 DeleterFn deleter = h->IsSecondaryCacheCompatible()
186 ? h->info_.helper->del_cb
187 : h->info_.deleter;
188 callback(h->key(), h->value, h->charge, deleter);
189 },
190 index_begin, index_end);
191 }
192
TEST_GetLRUList(LRUHandle ** lru,LRUHandle ** lru_low_pri)193 void LRUCacheShard::TEST_GetLRUList(LRUHandle** lru, LRUHandle** lru_low_pri) {
194 MutexLock l(&mutex_);
195 *lru = &lru_;
196 *lru_low_pri = lru_low_pri_;
197 }
198
TEST_GetLRUSize()199 size_t LRUCacheShard::TEST_GetLRUSize() {
200 MutexLock l(&mutex_);
201 LRUHandle* lru_handle = lru_.next;
202 size_t lru_size = 0;
203 while (lru_handle != &lru_) {
204 lru_size++;
205 lru_handle = lru_handle->next;
206 }
207 return lru_size;
208 }
209
GetHighPriPoolRatio()210 double LRUCacheShard::GetHighPriPoolRatio() {
211 MutexLock l(&mutex_);
212 return high_pri_pool_ratio_;
213 }
214
LRU_Remove(LRUHandle * e)215 void LRUCacheShard::LRU_Remove(LRUHandle* e) {
216 assert(e->next != nullptr);
217 assert(e->prev != nullptr);
218 if (lru_low_pri_ == e) {
219 lru_low_pri_ = e->prev;
220 }
221 e->next->prev = e->prev;
222 e->prev->next = e->next;
223 e->prev = e->next = nullptr;
224 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
225 assert(lru_usage_ >= total_charge);
226 lru_usage_ -= total_charge;
227 if (e->InHighPriPool()) {
228 assert(high_pri_pool_usage_ >= total_charge);
229 high_pri_pool_usage_ -= total_charge;
230 }
231 }
232
LRU_Insert(LRUHandle * e)233 void LRUCacheShard::LRU_Insert(LRUHandle* e) {
234 assert(e->next == nullptr);
235 assert(e->prev == nullptr);
236 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
237 if (high_pri_pool_ratio_ > 0 && (e->IsHighPri() || e->HasHit())) {
238 // Inset "e" to head of LRU list.
239 e->next = &lru_;
240 e->prev = lru_.prev;
241 e->prev->next = e;
242 e->next->prev = e;
243 e->SetInHighPriPool(true);
244 high_pri_pool_usage_ += total_charge;
245 MaintainPoolSize();
246 } else {
247 // Insert "e" to the head of low-pri pool. Note that when
248 // high_pri_pool_ratio is 0, head of low-pri pool is also head of LRU list.
249 e->next = lru_low_pri_->next;
250 e->prev = lru_low_pri_;
251 e->prev->next = e;
252 e->next->prev = e;
253 e->SetInHighPriPool(false);
254 lru_low_pri_ = e;
255 }
256 lru_usage_ += total_charge;
257 }
258
MaintainPoolSize()259 void LRUCacheShard::MaintainPoolSize() {
260 while (high_pri_pool_usage_ > high_pri_pool_capacity_) {
261 // Overflow last entry in high-pri pool to low-pri pool.
262 lru_low_pri_ = lru_low_pri_->next;
263 assert(lru_low_pri_ != &lru_);
264 lru_low_pri_->SetInHighPriPool(false);
265 size_t total_charge =
266 lru_low_pri_->CalcTotalCharge(metadata_charge_policy_);
267 assert(high_pri_pool_usage_ >= total_charge);
268 high_pri_pool_usage_ -= total_charge;
269 }
270 }
271
EvictFromLRU(size_t charge,autovector<LRUHandle * > * deleted)272 void LRUCacheShard::EvictFromLRU(size_t charge,
273 autovector<LRUHandle*>* deleted) {
274 while ((usage_ + charge) > capacity_ && lru_.next != &lru_) {
275 LRUHandle* old = lru_.next;
276 // LRU list contains only elements which can be evicted
277 assert(old->InCache() && !old->HasRefs());
278 LRU_Remove(old);
279 table_.Remove(old->key(), old->hash);
280 old->SetInCache(false);
281 size_t old_total_charge = old->CalcTotalCharge(metadata_charge_policy_);
282 assert(usage_ >= old_total_charge);
283 usage_ -= old_total_charge;
284 deleted->push_back(old);
285 }
286 }
287
SetCapacity(size_t capacity)288 void LRUCacheShard::SetCapacity(size_t capacity) {
289 autovector<LRUHandle*> last_reference_list;
290 {
291 MutexLock l(&mutex_);
292 capacity_ = capacity;
293 high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
294 EvictFromLRU(0, &last_reference_list);
295 }
296
297 // Try to insert the evicted entries into tiered cache
298 // Free the entries outside of mutex for performance reasons
299 for (auto entry : last_reference_list) {
300 if (secondary_cache_ && entry->IsSecondaryCacheCompatible() &&
301 !entry->IsPromoted()) {
302 secondary_cache_->Insert(entry->key(), entry->value, entry->info_.helper)
303 .PermitUncheckedError();
304 }
305 entry->Free();
306 }
307 }
308
SetStrictCapacityLimit(bool strict_capacity_limit)309 void LRUCacheShard::SetStrictCapacityLimit(bool strict_capacity_limit) {
310 MutexLock l(&mutex_);
311 strict_capacity_limit_ = strict_capacity_limit;
312 }
313
InsertItem(LRUHandle * e,Cache::Handle ** handle,bool free_handle_on_fail)314 Status LRUCacheShard::InsertItem(LRUHandle* e, Cache::Handle** handle,
315 bool free_handle_on_fail) {
316 Status s = Status::OK();
317 autovector<LRUHandle*> last_reference_list;
318 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
319
320 {
321 MutexLock l(&mutex_);
322
323 // Free the space following strict LRU policy until enough space
324 // is freed or the lru list is empty
325 EvictFromLRU(total_charge, &last_reference_list);
326
327 if ((usage_ + total_charge) > capacity_ &&
328 (strict_capacity_limit_ || handle == nullptr)) {
329 e->SetInCache(false);
330 if (handle == nullptr) {
331 // Don't insert the entry but still return ok, as if the entry inserted
332 // into cache and get evicted immediately.
333 last_reference_list.push_back(e);
334 } else {
335 if (free_handle_on_fail) {
336 delete[] reinterpret_cast<char*>(e);
337 *handle = nullptr;
338 }
339 s = Status::Incomplete("Insert failed due to LRU cache being full.");
340 }
341 } else {
342 // Insert into the cache. Note that the cache might get larger than its
343 // capacity if not enough space was freed up.
344 LRUHandle* old = table_.Insert(e);
345 usage_ += total_charge;
346 if (old != nullptr) {
347 s = Status::OkOverwritten();
348 assert(old->InCache());
349 old->SetInCache(false);
350 if (!old->HasRefs()) {
351 // old is on LRU because it's in cache and its reference count is 0
352 LRU_Remove(old);
353 size_t old_total_charge =
354 old->CalcTotalCharge(metadata_charge_policy_);
355 assert(usage_ >= old_total_charge);
356 usage_ -= old_total_charge;
357 last_reference_list.push_back(old);
358 }
359 }
360 if (handle == nullptr) {
361 LRU_Insert(e);
362 } else {
363 // If caller already holds a ref, no need to take one here
364 if (!e->HasRefs()) {
365 e->Ref();
366 }
367 *handle = reinterpret_cast<Cache::Handle*>(e);
368 }
369 }
370 }
371
372 // Try to insert the evicted entries into the secondary cache
373 // Free the entries here outside of mutex for performance reasons
374 for (auto entry : last_reference_list) {
375 if (secondary_cache_ && entry->IsSecondaryCacheCompatible() &&
376 !entry->IsPromoted()) {
377 secondary_cache_->Insert(entry->key(), entry->value, entry->info_.helper)
378 .PermitUncheckedError();
379 }
380 entry->Free();
381 }
382
383 return s;
384 }
385
Promote(LRUHandle * e)386 void LRUCacheShard::Promote(LRUHandle* e) {
387 SecondaryCacheResultHandle* secondary_handle = e->sec_handle;
388
389 assert(secondary_handle->IsReady());
390 e->SetIncomplete(false);
391 e->SetInCache(true);
392 e->SetPromoted(true);
393 e->value = secondary_handle->Value();
394 e->charge = secondary_handle->Size();
395 delete secondary_handle;
396
397 // This call could fail if the cache is over capacity and
398 // strict_capacity_limit_ is true. In such a case, we don't want
399 // InsertItem() to free the handle, since the item is already in memory
400 // and the caller will most likely just read from disk if we erase it here.
401 if (e->value) {
402 Cache::Handle* handle = reinterpret_cast<Cache::Handle*>(e);
403 Status s = InsertItem(e, &handle, /*free_handle_on_fail=*/false);
404 if (!s.ok()) {
405 // Item is in memory, but not accounted against the cache capacity.
406 // When the handle is released, the item should get deleted
407 assert(!e->InCache());
408 }
409 } else {
410 // Since the secondary cache lookup failed, mark the item as not in cache
411 // Don't charge the cache as its only metadata that'll shortly be released
412 MutexLock l(&mutex_);
413 e->charge = 0;
414 e->SetInCache(false);
415 }
416 }
417
Lookup(const Slice & key,uint32_t hash,const ShardedCache::CacheItemHelper * helper,const ShardedCache::CreateCallback & create_cb,Cache::Priority priority,bool wait,Statistics * stats)418 Cache::Handle* LRUCacheShard::Lookup(
419 const Slice& key, uint32_t hash,
420 const ShardedCache::CacheItemHelper* helper,
421 const ShardedCache::CreateCallback& create_cb, Cache::Priority priority,
422 bool wait, Statistics* stats) {
423 LRUHandle* e = nullptr;
424 {
425 MutexLock l(&mutex_);
426 e = table_.Lookup(key, hash);
427 if (e != nullptr) {
428 assert(e->InCache());
429 if (!e->HasRefs()) {
430 // The entry is in LRU since it's in hash and has no external references
431 LRU_Remove(e);
432 }
433 e->Ref();
434 e->SetHit();
435 }
436 }
437
438 // If handle table lookup failed, then allocate a handle outside the
439 // mutex if we're going to lookup in the secondary cache
440 // Only support synchronous for now
441 // TODO: Support asynchronous lookup in secondary cache
442 if (!e && secondary_cache_ && helper && helper->saveto_cb) {
443 // For objects from the secondary cache, we expect the caller to provide
444 // a way to create/delete the primary cache object. The only case where
445 // a deleter would not be required is for dummy entries inserted for
446 // accounting purposes, which we won't demote to the secondary cache
447 // anyway.
448 assert(create_cb && helper->del_cb);
449 std::unique_ptr<SecondaryCacheResultHandle> secondary_handle =
450 secondary_cache_->Lookup(key, create_cb, wait);
451 if (secondary_handle != nullptr) {
452 e = reinterpret_cast<LRUHandle*>(
453 new char[sizeof(LRUHandle) - 1 + key.size()]);
454
455 e->flags = 0;
456 e->SetSecondaryCacheCompatible(true);
457 e->info_.helper = helper;
458 e->key_length = key.size();
459 e->hash = hash;
460 e->refs = 0;
461 e->next = e->prev = nullptr;
462 e->SetPriority(priority);
463 memcpy(e->key_data, key.data(), key.size());
464 e->value = nullptr;
465 e->sec_handle = secondary_handle.release();
466 e->Ref();
467
468 if (wait) {
469 Promote(e);
470 if (!e->value) {
471 // The secondary cache returned a handle, but the lookup failed
472 e->Unref();
473 e->Free();
474 e = nullptr;
475 } else {
476 PERF_COUNTER_ADD(secondary_cache_hit_count, 1);
477 RecordTick(stats, SECONDARY_CACHE_HITS);
478 }
479 } else {
480 // If wait is false, we always return a handle and let the caller
481 // release the handle after checking for success or failure
482 e->SetIncomplete(true);
483 // This may be slightly inaccurate, if the lookup eventually fails.
484 // But the probability is very low.
485 PERF_COUNTER_ADD(secondary_cache_hit_count, 1);
486 RecordTick(stats, SECONDARY_CACHE_HITS);
487 }
488 }
489 }
490 return reinterpret_cast<Cache::Handle*>(e);
491 }
492
Ref(Cache::Handle * h)493 bool LRUCacheShard::Ref(Cache::Handle* h) {
494 LRUHandle* e = reinterpret_cast<LRUHandle*>(h);
495 MutexLock l(&mutex_);
496 // To create another reference - entry must be already externally referenced
497 assert(e->HasRefs());
498 e->Ref();
499 return true;
500 }
501
SetHighPriorityPoolRatio(double high_pri_pool_ratio)502 void LRUCacheShard::SetHighPriorityPoolRatio(double high_pri_pool_ratio) {
503 MutexLock l(&mutex_);
504 high_pri_pool_ratio_ = high_pri_pool_ratio;
505 high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
506 MaintainPoolSize();
507 }
508
Release(Cache::Handle * handle,bool force_erase)509 bool LRUCacheShard::Release(Cache::Handle* handle, bool force_erase) {
510 if (handle == nullptr) {
511 return false;
512 }
513 LRUHandle* e = reinterpret_cast<LRUHandle*>(handle);
514 bool last_reference = false;
515 {
516 MutexLock l(&mutex_);
517 last_reference = e->Unref();
518 if (last_reference && e->InCache()) {
519 // The item is still in cache, and nobody else holds a reference to it
520 if (usage_ > capacity_ || force_erase) {
521 // The LRU list must be empty since the cache is full
522 assert(lru_.next == &lru_ || force_erase);
523 // Take this opportunity and remove the item
524 table_.Remove(e->key(), e->hash);
525 e->SetInCache(false);
526 } else {
527 // Put the item back on the LRU list, and don't free it
528 LRU_Insert(e);
529 last_reference = false;
530 }
531 }
532 // If it was the last reference, and the entry is either not secondary
533 // cache compatible (i.e a dummy entry for accounting), or is secondary
534 // cache compatible and has a non-null value, then decrement the cache
535 // usage. If value is null in the latter case, taht means the lookup
536 // failed and we didn't charge the cache.
537 if (last_reference && (!e->IsSecondaryCacheCompatible() || e->value)) {
538 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
539 assert(usage_ >= total_charge);
540 usage_ -= total_charge;
541 }
542 }
543
544 // Free the entry here outside of mutex for performance reasons
545 if (last_reference) {
546 e->Free();
547 }
548 return last_reference;
549 }
550
Insert(const Slice & key,uint32_t hash,void * value,size_t charge,void (* deleter)(const Slice & key,void * value),const Cache::CacheItemHelper * helper,Cache::Handle ** handle,Cache::Priority priority)551 Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value,
552 size_t charge,
553 void (*deleter)(const Slice& key, void* value),
554 const Cache::CacheItemHelper* helper,
555 Cache::Handle** handle, Cache::Priority priority) {
556 // Allocate the memory here outside of the mutex
557 // If the cache is full, we'll have to release it
558 // It shouldn't happen very often though.
559 LRUHandle* e = reinterpret_cast<LRUHandle*>(
560 new char[sizeof(LRUHandle) - 1 + key.size()]);
561
562 e->value = value;
563 e->flags = 0;
564 if (helper) {
565 e->SetSecondaryCacheCompatible(true);
566 e->info_.helper = helper;
567 } else {
568 #ifdef __SANITIZE_THREAD__
569 e->is_secondary_cache_compatible_for_tsan = false;
570 #endif // __SANITIZE_THREAD__
571 e->info_.deleter = deleter;
572 }
573 e->charge = charge;
574 e->key_length = key.size();
575 e->hash = hash;
576 e->refs = 0;
577 e->next = e->prev = nullptr;
578 e->SetInCache(true);
579 e->SetPriority(priority);
580 memcpy(e->key_data, key.data(), key.size());
581
582 return InsertItem(e, handle, /* free_handle_on_fail */ true);
583 }
584
Erase(const Slice & key,uint32_t hash)585 void LRUCacheShard::Erase(const Slice& key, uint32_t hash) {
586 LRUHandle* e;
587 bool last_reference = false;
588 {
589 MutexLock l(&mutex_);
590 e = table_.Remove(key, hash);
591 if (e != nullptr) {
592 assert(e->InCache());
593 e->SetInCache(false);
594 if (!e->HasRefs()) {
595 // The entry is in LRU since it's in hash and has no external references
596 LRU_Remove(e);
597 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
598 assert(usage_ >= total_charge);
599 usage_ -= total_charge;
600 last_reference = true;
601 }
602 }
603 }
604
605 // Free the entry here outside of mutex for performance reasons
606 // last_reference will only be true if e != nullptr
607 if (last_reference) {
608 e->Free();
609 }
610 }
611
IsReady(Cache::Handle * handle)612 bool LRUCacheShard::IsReady(Cache::Handle* handle) {
613 LRUHandle* e = reinterpret_cast<LRUHandle*>(handle);
614 MutexLock l(&mutex_);
615 bool ready = true;
616 if (e->IsPending()) {
617 assert(secondary_cache_);
618 assert(e->sec_handle);
619 ready = e->sec_handle->IsReady();
620 }
621 return ready;
622 }
623
GetUsage() const624 size_t LRUCacheShard::GetUsage() const {
625 MutexLock l(&mutex_);
626 return usage_;
627 }
628
GetPinnedUsage() const629 size_t LRUCacheShard::GetPinnedUsage() const {
630 MutexLock l(&mutex_);
631 assert(usage_ >= lru_usage_);
632 return usage_ - lru_usage_;
633 }
634
GetPrintableOptions() const635 std::string LRUCacheShard::GetPrintableOptions() const {
636 const int kBufferSize = 200;
637 char buffer[kBufferSize];
638 {
639 MutexLock l(&mutex_);
640 snprintf(buffer, kBufferSize, " high_pri_pool_ratio: %.3lf\n",
641 high_pri_pool_ratio_);
642 }
643 return std::string(buffer);
644 }
645
LRUCache(size_t capacity,int num_shard_bits,bool strict_capacity_limit,double high_pri_pool_ratio,std::shared_ptr<MemoryAllocator> allocator,bool use_adaptive_mutex,CacheMetadataChargePolicy metadata_charge_policy,const std::shared_ptr<SecondaryCache> & secondary_cache)646 LRUCache::LRUCache(size_t capacity, int num_shard_bits,
647 bool strict_capacity_limit, double high_pri_pool_ratio,
648 std::shared_ptr<MemoryAllocator> allocator,
649 bool use_adaptive_mutex,
650 CacheMetadataChargePolicy metadata_charge_policy,
651 const std::shared_ptr<SecondaryCache>& secondary_cache)
652 : ShardedCache(capacity, num_shard_bits, strict_capacity_limit,
653 std::move(allocator)) {
654 num_shards_ = 1 << num_shard_bits;
655 shards_ = reinterpret_cast<LRUCacheShard*>(
656 port::cacheline_aligned_alloc(sizeof(LRUCacheShard) * num_shards_));
657 size_t per_shard = (capacity + (num_shards_ - 1)) / num_shards_;
658 for (int i = 0; i < num_shards_; i++) {
659 new (&shards_[i]) LRUCacheShard(
660 per_shard, strict_capacity_limit, high_pri_pool_ratio,
661 use_adaptive_mutex, metadata_charge_policy,
662 /* max_upper_hash_bits */ 32 - num_shard_bits, secondary_cache);
663 }
664 secondary_cache_ = secondary_cache;
665 }
666
~LRUCache()667 LRUCache::~LRUCache() {
668 if (shards_ != nullptr) {
669 assert(num_shards_ > 0);
670 for (int i = 0; i < num_shards_; i++) {
671 shards_[i].~LRUCacheShard();
672 }
673 port::cacheline_aligned_free(shards_);
674 }
675 }
676
GetShard(uint32_t shard)677 CacheShard* LRUCache::GetShard(uint32_t shard) {
678 return reinterpret_cast<CacheShard*>(&shards_[shard]);
679 }
680
GetShard(uint32_t shard) const681 const CacheShard* LRUCache::GetShard(uint32_t shard) const {
682 return reinterpret_cast<CacheShard*>(&shards_[shard]);
683 }
684
Value(Handle * handle)685 void* LRUCache::Value(Handle* handle) {
686 return reinterpret_cast<const LRUHandle*>(handle)->value;
687 }
688
GetCharge(Handle * handle) const689 size_t LRUCache::GetCharge(Handle* handle) const {
690 return reinterpret_cast<const LRUHandle*>(handle)->charge;
691 }
692
GetDeleter(Handle * handle) const693 Cache::DeleterFn LRUCache::GetDeleter(Handle* handle) const {
694 auto h = reinterpret_cast<const LRUHandle*>(handle);
695 if (h->IsSecondaryCacheCompatible()) {
696 return h->info_.helper->del_cb;
697 } else {
698 return h->info_.deleter;
699 }
700 }
701
GetHash(Handle * handle) const702 uint32_t LRUCache::GetHash(Handle* handle) const {
703 return reinterpret_cast<const LRUHandle*>(handle)->hash;
704 }
705
DisownData()706 void LRUCache::DisownData() {
707 // Do not drop data if compile with ASAN to suppress leak warning.
708 #ifndef MUST_FREE_HEAP_ALLOCATIONS
709 shards_ = nullptr;
710 num_shards_ = 0;
711 #endif
712 }
713
TEST_GetLRUSize()714 size_t LRUCache::TEST_GetLRUSize() {
715 size_t lru_size_of_all_shards = 0;
716 for (int i = 0; i < num_shards_; i++) {
717 lru_size_of_all_shards += shards_[i].TEST_GetLRUSize();
718 }
719 return lru_size_of_all_shards;
720 }
721
GetHighPriPoolRatio()722 double LRUCache::GetHighPriPoolRatio() {
723 double result = 0.0;
724 if (num_shards_ > 0) {
725 result = shards_[0].GetHighPriPoolRatio();
726 }
727 return result;
728 }
729
WaitAll(std::vector<Handle * > & handles)730 void LRUCache::WaitAll(std::vector<Handle*>& handles) {
731 if (secondary_cache_) {
732 std::vector<SecondaryCacheResultHandle*> sec_handles;
733 sec_handles.reserve(handles.size());
734 for (Handle* handle : handles) {
735 if (!handle) {
736 continue;
737 }
738 LRUHandle* lru_handle = reinterpret_cast<LRUHandle*>(handle);
739 if (!lru_handle->IsPending()) {
740 continue;
741 }
742 sec_handles.emplace_back(lru_handle->sec_handle);
743 }
744 secondary_cache_->WaitAll(sec_handles);
745 for (Handle* handle : handles) {
746 if (!handle) {
747 continue;
748 }
749 LRUHandle* lru_handle = reinterpret_cast<LRUHandle*>(handle);
750 if (!lru_handle->IsPending()) {
751 continue;
752 }
753 uint32_t hash = GetHash(handle);
754 LRUCacheShard* shard = static_cast<LRUCacheShard*>(GetShard(Shard(hash)));
755 shard->Promote(lru_handle);
756 }
757 }
758 }
759
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)760 std::shared_ptr<Cache> NewLRUCache(
761 size_t capacity, int num_shard_bits, bool strict_capacity_limit,
762 double high_pri_pool_ratio,
763 std::shared_ptr<MemoryAllocator> memory_allocator, bool use_adaptive_mutex,
764 CacheMetadataChargePolicy metadata_charge_policy,
765 const std::shared_ptr<SecondaryCache>& secondary_cache) {
766 if (num_shard_bits >= 20) {
767 return nullptr; // the cache cannot be sharded into too many fine pieces
768 }
769 if (high_pri_pool_ratio < 0.0 || high_pri_pool_ratio > 1.0) {
770 // invalid high_pri_pool_ratio
771 return nullptr;
772 }
773 if (num_shard_bits < 0) {
774 num_shard_bits = GetDefaultCacheShardBits(capacity);
775 }
776 return std::make_shared<LRUCache>(
777 capacity, num_shard_bits, strict_capacity_limit, high_pri_pool_ratio,
778 std::move(memory_allocator), use_adaptive_mutex, metadata_charge_policy,
779 secondary_cache);
780 }
781
NewLRUCache(const LRUCacheOptions & cache_opts)782 std::shared_ptr<Cache> NewLRUCache(const LRUCacheOptions& cache_opts) {
783 return NewLRUCache(
784 cache_opts.capacity, cache_opts.num_shard_bits,
785 cache_opts.strict_capacity_limit, cache_opts.high_pri_pool_ratio,
786 cache_opts.memory_allocator, cache_opts.use_adaptive_mutex,
787 cache_opts.metadata_charge_policy, cache_opts.secondary_cache);
788 }
789
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)790 std::shared_ptr<Cache> NewLRUCache(
791 size_t capacity, int num_shard_bits, bool strict_capacity_limit,
792 double high_pri_pool_ratio,
793 std::shared_ptr<MemoryAllocator> memory_allocator, bool use_adaptive_mutex,
794 CacheMetadataChargePolicy metadata_charge_policy) {
795 return NewLRUCache(capacity, num_shard_bits, strict_capacity_limit,
796 high_pri_pool_ratio, memory_allocator, use_adaptive_mutex,
797 metadata_charge_policy, nullptr);
798 }
799 } // namespace ROCKSDB_NAMESPACE
800