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 <assert.h>
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string>
16
17 #include "util/mutexlock.h"
18
19 namespace ROCKSDB_NAMESPACE {
20
LRUHandleTable()21 LRUHandleTable::LRUHandleTable() : list_(nullptr), length_(0), elems_(0) {
22 Resize();
23 }
24
~LRUHandleTable()25 LRUHandleTable::~LRUHandleTable() {
26 ApplyToAllCacheEntries([](LRUHandle* h) {
27 if (!h->HasRefs()) {
28 h->Free();
29 }
30 });
31 delete[] list_;
32 }
33
Lookup(const Slice & key,uint32_t hash)34 LRUHandle* LRUHandleTable::Lookup(const Slice& key, uint32_t hash) {
35 return *FindPointer(key, hash);
36 }
37
Insert(LRUHandle * h)38 LRUHandle* LRUHandleTable::Insert(LRUHandle* h) {
39 LRUHandle** ptr = FindPointer(h->key(), h->hash);
40 LRUHandle* old = *ptr;
41 h->next_hash = (old == nullptr ? nullptr : old->next_hash);
42 *ptr = h;
43 if (old == nullptr) {
44 ++elems_;
45 if (elems_ > length_) {
46 // Since each cache entry is fairly large, we aim for a small
47 // average linked list length (<= 1).
48 Resize();
49 }
50 }
51 return old;
52 }
53
Remove(const Slice & key,uint32_t hash)54 LRUHandle* LRUHandleTable::Remove(const Slice& key, uint32_t hash) {
55 LRUHandle** ptr = FindPointer(key, hash);
56 LRUHandle* result = *ptr;
57 if (result != nullptr) {
58 *ptr = result->next_hash;
59 --elems_;
60 }
61 return result;
62 }
63
FindPointer(const Slice & key,uint32_t hash)64 LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
65 LRUHandle** ptr = &list_[hash & (length_ - 1)];
66 while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
67 ptr = &(*ptr)->next_hash;
68 }
69 return ptr;
70 }
71
Resize()72 void LRUHandleTable::Resize() {
73 uint32_t new_length = 16;
74 while (new_length < elems_ * 1.5) {
75 new_length *= 2;
76 }
77 LRUHandle** new_list = new LRUHandle*[new_length];
78 memset(new_list, 0, sizeof(new_list[0]) * new_length);
79 uint32_t count = 0;
80 for (uint32_t i = 0; i < length_; i++) {
81 LRUHandle* h = list_[i];
82 while (h != nullptr) {
83 LRUHandle* next = h->next_hash;
84 uint32_t hash = h->hash;
85 LRUHandle** ptr = &new_list[hash & (new_length - 1)];
86 h->next_hash = *ptr;
87 *ptr = h;
88 h = next;
89 count++;
90 }
91 }
92 assert(elems_ == count);
93 delete[] list_;
94 list_ = new_list;
95 length_ = new_length;
96 }
97
LRUCacheShard(size_t capacity,bool strict_capacity_limit,double high_pri_pool_ratio,bool use_adaptive_mutex,CacheMetadataChargePolicy metadata_charge_policy)98 LRUCacheShard::LRUCacheShard(size_t capacity, bool strict_capacity_limit,
99 double high_pri_pool_ratio,
100 bool use_adaptive_mutex,
101 CacheMetadataChargePolicy metadata_charge_policy)
102 : capacity_(0),
103 high_pri_pool_usage_(0),
104 strict_capacity_limit_(strict_capacity_limit),
105 high_pri_pool_ratio_(high_pri_pool_ratio),
106 high_pri_pool_capacity_(0),
107 usage_(0),
108 lru_usage_(0),
109 mutex_(use_adaptive_mutex) {
110 set_metadata_charge_policy(metadata_charge_policy);
111 // Make empty circular linked list
112 lru_.next = &lru_;
113 lru_.prev = &lru_;
114 lru_low_pri_ = &lru_;
115 SetCapacity(capacity);
116 }
117
EraseUnRefEntries()118 void LRUCacheShard::EraseUnRefEntries() {
119 autovector<LRUHandle*> last_reference_list;
120 {
121 MutexLock l(&mutex_);
122 while (lru_.next != &lru_) {
123 LRUHandle* old = lru_.next;
124 // LRU list contains only elements which can be evicted
125 assert(old->InCache() && !old->HasRefs());
126 LRU_Remove(old);
127 table_.Remove(old->key(), old->hash);
128 old->SetInCache(false);
129 size_t total_charge = old->CalcTotalCharge(metadata_charge_policy_);
130 assert(usage_ >= total_charge);
131 usage_ -= total_charge;
132 last_reference_list.push_back(old);
133 }
134 }
135
136 for (auto entry : last_reference_list) {
137 entry->Free();
138 }
139 }
140
ApplyToAllCacheEntries(void (* callback)(void *,size_t),bool thread_safe)141 void LRUCacheShard::ApplyToAllCacheEntries(void (*callback)(void*, size_t),
142 bool thread_safe) {
143 const auto applyCallback = [&]() {
144 table_.ApplyToAllCacheEntries(
145 [callback](LRUHandle* h) { callback(h->value, h->charge); });
146 };
147
148 if (thread_safe) {
149 MutexLock l(&mutex_);
150 applyCallback();
151 } else {
152 applyCallback();
153 }
154 }
155
TEST_GetLRUList(LRUHandle ** lru,LRUHandle ** lru_low_pri)156 void LRUCacheShard::TEST_GetLRUList(LRUHandle** lru, LRUHandle** lru_low_pri) {
157 MutexLock l(&mutex_);
158 *lru = &lru_;
159 *lru_low_pri = lru_low_pri_;
160 }
161
TEST_GetLRUSize()162 size_t LRUCacheShard::TEST_GetLRUSize() {
163 MutexLock l(&mutex_);
164 LRUHandle* lru_handle = lru_.next;
165 size_t lru_size = 0;
166 while (lru_handle != &lru_) {
167 lru_size++;
168 lru_handle = lru_handle->next;
169 }
170 return lru_size;
171 }
172
GetHighPriPoolRatio()173 double LRUCacheShard::GetHighPriPoolRatio() {
174 MutexLock l(&mutex_);
175 return high_pri_pool_ratio_;
176 }
177
LRU_Remove(LRUHandle * e)178 void LRUCacheShard::LRU_Remove(LRUHandle* e) {
179 assert(e->next != nullptr);
180 assert(e->prev != nullptr);
181 if (lru_low_pri_ == e) {
182 lru_low_pri_ = e->prev;
183 }
184 e->next->prev = e->prev;
185 e->prev->next = e->next;
186 e->prev = e->next = nullptr;
187 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
188 assert(lru_usage_ >= total_charge);
189 lru_usage_ -= total_charge;
190 if (e->InHighPriPool()) {
191 assert(high_pri_pool_usage_ >= total_charge);
192 high_pri_pool_usage_ -= total_charge;
193 }
194 }
195
LRU_Insert(LRUHandle * e)196 void LRUCacheShard::LRU_Insert(LRUHandle* e) {
197 assert(e->next == nullptr);
198 assert(e->prev == nullptr);
199 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
200 if (high_pri_pool_ratio_ > 0 && (e->IsHighPri() || e->HasHit())) {
201 // Inset "e" to head of LRU list.
202 e->next = &lru_;
203 e->prev = lru_.prev;
204 e->prev->next = e;
205 e->next->prev = e;
206 e->SetInHighPriPool(true);
207 high_pri_pool_usage_ += total_charge;
208 MaintainPoolSize();
209 } else {
210 // Insert "e" to the head of low-pri pool. Note that when
211 // high_pri_pool_ratio is 0, head of low-pri pool is also head of LRU list.
212 e->next = lru_low_pri_->next;
213 e->prev = lru_low_pri_;
214 e->prev->next = e;
215 e->next->prev = e;
216 e->SetInHighPriPool(false);
217 lru_low_pri_ = e;
218 }
219 lru_usage_ += total_charge;
220 }
221
MaintainPoolSize()222 void LRUCacheShard::MaintainPoolSize() {
223 while (high_pri_pool_usage_ > high_pri_pool_capacity_) {
224 // Overflow last entry in high-pri pool to low-pri pool.
225 lru_low_pri_ = lru_low_pri_->next;
226 assert(lru_low_pri_ != &lru_);
227 lru_low_pri_->SetInHighPriPool(false);
228 size_t total_charge =
229 lru_low_pri_->CalcTotalCharge(metadata_charge_policy_);
230 assert(high_pri_pool_usage_ >= total_charge);
231 high_pri_pool_usage_ -= total_charge;
232 }
233 }
234
EvictFromLRU(size_t charge,autovector<LRUHandle * > * deleted)235 void LRUCacheShard::EvictFromLRU(size_t charge,
236 autovector<LRUHandle*>* deleted) {
237 while ((usage_ + charge) > capacity_ && lru_.next != &lru_) {
238 LRUHandle* old = lru_.next;
239 // LRU list contains only elements which can be evicted
240 assert(old->InCache() && !old->HasRefs());
241 LRU_Remove(old);
242 table_.Remove(old->key(), old->hash);
243 old->SetInCache(false);
244 size_t old_total_charge = old->CalcTotalCharge(metadata_charge_policy_);
245 assert(usage_ >= old_total_charge);
246 usage_ -= old_total_charge;
247 deleted->push_back(old);
248 }
249 }
250
SetCapacity(size_t capacity)251 void LRUCacheShard::SetCapacity(size_t capacity) {
252 autovector<LRUHandle*> last_reference_list;
253 {
254 MutexLock l(&mutex_);
255 capacity_ = capacity;
256 high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
257 EvictFromLRU(0, &last_reference_list);
258 }
259
260 // Free the entries outside of mutex for performance reasons
261 for (auto entry : last_reference_list) {
262 entry->Free();
263 }
264 }
265
SetStrictCapacityLimit(bool strict_capacity_limit)266 void LRUCacheShard::SetStrictCapacityLimit(bool strict_capacity_limit) {
267 MutexLock l(&mutex_);
268 strict_capacity_limit_ = strict_capacity_limit;
269 }
270
Lookup(const Slice & key,uint32_t hash)271 Cache::Handle* LRUCacheShard::Lookup(const Slice& key, uint32_t hash) {
272 MutexLock l(&mutex_);
273 LRUHandle* e = table_.Lookup(key, hash);
274 if (e != nullptr) {
275 assert(e->InCache());
276 if (!e->HasRefs()) {
277 // The entry is in LRU since it's in hash and has no external references
278 LRU_Remove(e);
279 }
280 e->Ref();
281 e->SetHit();
282 }
283 return reinterpret_cast<Cache::Handle*>(e);
284 }
285
Ref(Cache::Handle * h)286 bool LRUCacheShard::Ref(Cache::Handle* h) {
287 LRUHandle* e = reinterpret_cast<LRUHandle*>(h);
288 MutexLock l(&mutex_);
289 // To create another reference - entry must be already externally referenced
290 assert(e->HasRefs());
291 e->Ref();
292 return true;
293 }
294
SetHighPriorityPoolRatio(double high_pri_pool_ratio)295 void LRUCacheShard::SetHighPriorityPoolRatio(double high_pri_pool_ratio) {
296 MutexLock l(&mutex_);
297 high_pri_pool_ratio_ = high_pri_pool_ratio;
298 high_pri_pool_capacity_ = capacity_ * high_pri_pool_ratio_;
299 MaintainPoolSize();
300 }
301
Release(Cache::Handle * handle,bool force_erase)302 bool LRUCacheShard::Release(Cache::Handle* handle, bool force_erase) {
303 if (handle == nullptr) {
304 return false;
305 }
306 LRUHandle* e = reinterpret_cast<LRUHandle*>(handle);
307 bool last_reference = false;
308 {
309 MutexLock l(&mutex_);
310 last_reference = e->Unref();
311 if (last_reference && e->InCache()) {
312 // The item is still in cache, and nobody else holds a reference to it
313 if (usage_ > capacity_ || force_erase) {
314 // The LRU list must be empty since the cache is full
315 assert(lru_.next == &lru_ || force_erase);
316 // Take this opportunity and remove the item
317 table_.Remove(e->key(), e->hash);
318 e->SetInCache(false);
319 } else {
320 // Put the item back on the LRU list, and don't free it
321 LRU_Insert(e);
322 last_reference = false;
323 }
324 }
325 if (last_reference) {
326 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
327 assert(usage_ >= total_charge);
328 usage_ -= total_charge;
329 }
330 }
331
332 // Free the entry here outside of mutex for performance reasons
333 if (last_reference) {
334 e->Free();
335 }
336 return last_reference;
337 }
338
Insert(const Slice & key,uint32_t hash,void * value,size_t charge,void (* deleter)(const Slice & key,void * value),Cache::Handle ** handle,Cache::Priority priority)339 Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value,
340 size_t charge,
341 void (*deleter)(const Slice& key, void* value),
342 Cache::Handle** handle, Cache::Priority priority) {
343 // Allocate the memory here outside of the mutex
344 // If the cache is full, we'll have to release it
345 // It shouldn't happen very often though.
346 LRUHandle* e = reinterpret_cast<LRUHandle*>(
347 new char[sizeof(LRUHandle) - 1 + key.size()]);
348 Status s = Status::OK();
349 autovector<LRUHandle*> last_reference_list;
350
351 e->value = value;
352 e->deleter = deleter;
353 e->charge = charge;
354 e->key_length = key.size();
355 e->flags = 0;
356 e->hash = hash;
357 e->refs = 0;
358 e->next = e->prev = nullptr;
359 e->SetInCache(true);
360 e->SetPriority(priority);
361 memcpy(e->key_data, key.data(), key.size());
362 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
363
364 {
365 MutexLock l(&mutex_);
366
367 // Free the space following strict LRU policy until enough space
368 // is freed or the lru list is empty
369 EvictFromLRU(total_charge, &last_reference_list);
370
371 if ((usage_ + total_charge) > capacity_ &&
372 (strict_capacity_limit_ || handle == nullptr)) {
373 if (handle == nullptr) {
374 // Don't insert the entry but still return ok, as if the entry inserted
375 // into cache and get evicted immediately.
376 e->SetInCache(false);
377 last_reference_list.push_back(e);
378 } else {
379 delete[] reinterpret_cast<char*>(e);
380 *handle = nullptr;
381 s = Status::Incomplete("Insert failed due to LRU cache being full.");
382 }
383 } else {
384 // Insert into the cache. Note that the cache might get larger than its
385 // capacity if not enough space was freed up.
386 LRUHandle* old = table_.Insert(e);
387 usage_ += total_charge;
388 if (old != nullptr) {
389 assert(old->InCache());
390 old->SetInCache(false);
391 if (!old->HasRefs()) {
392 // old is on LRU because it's in cache and its reference count is 0
393 LRU_Remove(old);
394 size_t old_total_charge =
395 old->CalcTotalCharge(metadata_charge_policy_);
396 assert(usage_ >= old_total_charge);
397 usage_ -= old_total_charge;
398 last_reference_list.push_back(old);
399 }
400 }
401 if (handle == nullptr) {
402 LRU_Insert(e);
403 } else {
404 e->Ref();
405 *handle = reinterpret_cast<Cache::Handle*>(e);
406 }
407 }
408 }
409
410 // Free the entries here outside of mutex for performance reasons
411 for (auto entry : last_reference_list) {
412 entry->Free();
413 }
414
415 return s;
416 }
417
Erase(const Slice & key,uint32_t hash)418 void LRUCacheShard::Erase(const Slice& key, uint32_t hash) {
419 LRUHandle* e;
420 bool last_reference = false;
421 {
422 MutexLock l(&mutex_);
423 e = table_.Remove(key, hash);
424 if (e != nullptr) {
425 assert(e->InCache());
426 e->SetInCache(false);
427 if (!e->HasRefs()) {
428 // The entry is in LRU since it's in hash and has no external references
429 LRU_Remove(e);
430 size_t total_charge = e->CalcTotalCharge(metadata_charge_policy_);
431 assert(usage_ >= total_charge);
432 usage_ -= total_charge;
433 last_reference = true;
434 }
435 }
436 }
437
438 // Free the entry here outside of mutex for performance reasons
439 // last_reference will only be true if e != nullptr
440 if (last_reference) {
441 e->Free();
442 }
443 }
444
GetUsage() const445 size_t LRUCacheShard::GetUsage() const {
446 MutexLock l(&mutex_);
447 return usage_;
448 }
449
GetPinnedUsage() const450 size_t LRUCacheShard::GetPinnedUsage() const {
451 MutexLock l(&mutex_);
452 assert(usage_ >= lru_usage_);
453 return usage_ - lru_usage_;
454 }
455
GetPrintableOptions() const456 std::string LRUCacheShard::GetPrintableOptions() const {
457 const int kBufferSize = 200;
458 char buffer[kBufferSize];
459 {
460 MutexLock l(&mutex_);
461 snprintf(buffer, kBufferSize, " high_pri_pool_ratio: %.3lf\n",
462 high_pri_pool_ratio_);
463 }
464 return std::string(buffer);
465 }
466
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)467 LRUCache::LRUCache(size_t capacity, int num_shard_bits,
468 bool strict_capacity_limit, double high_pri_pool_ratio,
469 std::shared_ptr<MemoryAllocator> allocator,
470 bool use_adaptive_mutex,
471 CacheMetadataChargePolicy metadata_charge_policy)
472 : ShardedCache(capacity, num_shard_bits, strict_capacity_limit,
473 std::move(allocator)) {
474 num_shards_ = 1 << num_shard_bits;
475 shards_ = reinterpret_cast<LRUCacheShard*>(
476 port::cacheline_aligned_alloc(sizeof(LRUCacheShard) * num_shards_));
477 size_t per_shard = (capacity + (num_shards_ - 1)) / num_shards_;
478 for (int i = 0; i < num_shards_; i++) {
479 new (&shards_[i])
480 LRUCacheShard(per_shard, strict_capacity_limit, high_pri_pool_ratio,
481 use_adaptive_mutex, metadata_charge_policy);
482 }
483 }
484
~LRUCache()485 LRUCache::~LRUCache() {
486 if (shards_ != nullptr) {
487 assert(num_shards_ > 0);
488 for (int i = 0; i < num_shards_; i++) {
489 shards_[i].~LRUCacheShard();
490 }
491 port::cacheline_aligned_free(shards_);
492 }
493 }
494
GetShard(int shard)495 CacheShard* LRUCache::GetShard(int shard) {
496 return reinterpret_cast<CacheShard*>(&shards_[shard]);
497 }
498
GetShard(int shard) const499 const CacheShard* LRUCache::GetShard(int shard) const {
500 return reinterpret_cast<CacheShard*>(&shards_[shard]);
501 }
502
Value(Handle * handle)503 void* LRUCache::Value(Handle* handle) {
504 return reinterpret_cast<const LRUHandle*>(handle)->value;
505 }
506
GetCharge(Handle * handle) const507 size_t LRUCache::GetCharge(Handle* handle) const {
508 return reinterpret_cast<const LRUHandle*>(handle)->charge;
509 }
510
GetHash(Handle * handle) const511 uint32_t LRUCache::GetHash(Handle* handle) const {
512 return reinterpret_cast<const LRUHandle*>(handle)->hash;
513 }
514
DisownData()515 void LRUCache::DisownData() {
516 // Do not drop data if compile with ASAN to suppress leak warning.
517 #if defined(__clang__)
518 #if !defined(__has_feature) || !__has_feature(address_sanitizer)
519 shards_ = nullptr;
520 num_shards_ = 0;
521 #endif
522 #else // __clang__
523 #ifndef __SANITIZE_ADDRESS__
524 shards_ = nullptr;
525 num_shards_ = 0;
526 #endif // !__SANITIZE_ADDRESS__
527 #endif // __clang__
528 }
529
TEST_GetLRUSize()530 size_t LRUCache::TEST_GetLRUSize() {
531 size_t lru_size_of_all_shards = 0;
532 for (int i = 0; i < num_shards_; i++) {
533 lru_size_of_all_shards += shards_[i].TEST_GetLRUSize();
534 }
535 return lru_size_of_all_shards;
536 }
537
GetHighPriPoolRatio()538 double LRUCache::GetHighPriPoolRatio() {
539 double result = 0.0;
540 if (num_shards_ > 0) {
541 result = shards_[0].GetHighPriPoolRatio();
542 }
543 return result;
544 }
545
NewLRUCache(const LRUCacheOptions & cache_opts)546 std::shared_ptr<Cache> NewLRUCache(const LRUCacheOptions& cache_opts) {
547 return NewLRUCache(cache_opts.capacity, cache_opts.num_shard_bits,
548 cache_opts.strict_capacity_limit,
549 cache_opts.high_pri_pool_ratio,
550 cache_opts.memory_allocator, cache_opts.use_adaptive_mutex,
551 cache_opts.metadata_charge_policy);
552 }
553
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)554 std::shared_ptr<Cache> NewLRUCache(
555 size_t capacity, int num_shard_bits, bool strict_capacity_limit,
556 double high_pri_pool_ratio,
557 std::shared_ptr<MemoryAllocator> memory_allocator, bool use_adaptive_mutex,
558 CacheMetadataChargePolicy metadata_charge_policy) {
559 if (num_shard_bits >= 20) {
560 return nullptr; // the cache cannot be sharded into too many fine pieces
561 }
562 if (high_pri_pool_ratio < 0.0 || high_pri_pool_ratio > 1.0) {
563 // invalid high_pri_pool_ratio
564 return nullptr;
565 }
566 if (num_shard_bits < 0) {
567 num_shard_bits = GetDefaultCacheShardBits(capacity);
568 }
569 return std::make_shared<LRUCache>(
570 capacity, num_shard_bits, strict_capacity_limit, high_pri_pool_ratio,
571 std::move(memory_allocator), use_adaptive_mutex, metadata_charge_policy);
572 }
573
574 } // namespace ROCKSDB_NAMESPACE
575