1 // Copyright (c) 2013, 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 #pragma once 7 8 #ifndef ROCKSDB_LITE 9 10 #include <functional> 11 12 #include "util/random.h" 13 #include "utilities/persistent_cache/hash_table.h" 14 #include "utilities/persistent_cache/lrulist.h" 15 16 namespace ROCKSDB_NAMESPACE { 17 18 // Evictable Hash Table 19 // 20 // Hash table index where least accessed (or one of the least accessed) elements 21 // can be evicted. 22 // 23 // Please note EvictableHashTable can only be created for pointer type objects 24 template <class T, class Hash, class Equal> 25 class EvictableHashTable : private HashTable<T*, Hash, Equal> { 26 public: 27 typedef HashTable<T*, Hash, Equal> hash_table; 28 29 explicit EvictableHashTable(const size_t capacity = 1024 * 1024, 30 const float load_factor = 2.0, 31 const uint32_t nlocks = 256) 32 : HashTable<T*, Hash, Equal>(capacity, load_factor, nlocks), 33 lru_lists_(new LRUList<T>[hash_table::nlocks_]) { 34 assert(lru_lists_); 35 } 36 ~EvictableHashTable()37 virtual ~EvictableHashTable() { AssertEmptyLRU(); } 38 39 // 40 // Insert given record to hash table (and LRU list) 41 // Insert(T * t)42 bool Insert(T* t) { 43 const uint64_t h = Hash()(t); 44 typename hash_table::Bucket& bucket = GetBucket(h); 45 LRUListType& lru = GetLRUList(h); 46 port::RWMutex& lock = GetMutex(h); 47 48 WriteLock _(&lock); 49 if (hash_table::Insert(&bucket, t)) { 50 lru.Push(t); 51 return true; 52 } 53 return false; 54 } 55 56 // 57 // Lookup hash table 58 // 59 // Please note that read lock should be held by the caller. This is because 60 // the caller owns the data, and should hold the read lock as long as he 61 // operates on the data. Find(T * t,T ** ret)62 bool Find(T* t, T** ret) { 63 const uint64_t h = Hash()(t); 64 typename hash_table::Bucket& bucket = GetBucket(h); 65 LRUListType& lru = GetLRUList(h); 66 port::RWMutex& lock = GetMutex(h); 67 68 ReadLock _(&lock); 69 if (hash_table::Find(&bucket, t, ret)) { 70 ++(*ret)->refs_; 71 lru.Touch(*ret); 72 return true; 73 } 74 return false; 75 } 76 77 // 78 // Evict one of the least recently used object 79 // 80 T* Evict(const std::function<void(T*)>& fn = nullptr) { 81 uint32_t random = Random::GetTLSInstance()->Next(); 82 const size_t start_idx = random % hash_table::nlocks_; 83 T* t = nullptr; 84 85 // iterate from start_idx .. 0 .. start_idx 86 for (size_t i = 0; !t && i < hash_table::nlocks_; ++i) { 87 const size_t idx = (start_idx + i) % hash_table::nlocks_; 88 89 WriteLock _(&hash_table::locks_[idx]); 90 LRUListType& lru = lru_lists_[idx]; 91 if (!lru.IsEmpty() && (t = lru.Pop()) != nullptr) { 92 assert(!t->refs_); 93 // We got an item to evict, erase from the bucket 94 const uint64_t h = Hash()(t); 95 typename hash_table::Bucket& bucket = GetBucket(h); 96 T* tmp = nullptr; 97 bool status = hash_table::Erase(&bucket, t, &tmp); 98 assert(t == tmp); 99 (void)status; 100 assert(status); 101 if (fn) { 102 fn(t); 103 } 104 break; 105 } 106 assert(!t); 107 } 108 return t; 109 } 110 Clear(void (* fn)(T *))111 void Clear(void (*fn)(T*)) { 112 for (uint32_t i = 0; i < hash_table::nbuckets_; ++i) { 113 const uint32_t lock_idx = i % hash_table::nlocks_; 114 WriteLock _(&hash_table::locks_[lock_idx]); 115 auto& lru_list = lru_lists_[lock_idx]; 116 auto& bucket = hash_table::buckets_[i]; 117 for (auto* t : bucket.list_) { 118 lru_list.Unlink(t); 119 (*fn)(t); 120 } 121 bucket.list_.clear(); 122 } 123 // make sure that all LRU lists are emptied 124 AssertEmptyLRU(); 125 } 126 AssertEmptyLRU()127 void AssertEmptyLRU() { 128 #ifndef NDEBUG 129 for (uint32_t i = 0; i < hash_table::nlocks_; ++i) { 130 WriteLock _(&hash_table::locks_[i]); 131 auto& lru_list = lru_lists_[i]; 132 assert(lru_list.IsEmpty()); 133 } 134 #endif 135 } 136 137 // 138 // Fetch the mutex associated with a key 139 // This call is used to hold the lock for a given data for extended period of 140 // time. GetMutex(T * t)141 port::RWMutex* GetMutex(T* t) { return hash_table::GetMutex(t); } 142 143 private: 144 typedef LRUList<T> LRUListType; 145 GetBucket(const uint64_t h)146 typename hash_table::Bucket& GetBucket(const uint64_t h) { 147 const uint32_t bucket_idx = h % hash_table::nbuckets_; 148 return hash_table::buckets_[bucket_idx]; 149 } 150 GetLRUList(const uint64_t h)151 LRUListType& GetLRUList(const uint64_t h) { 152 const uint32_t bucket_idx = h % hash_table::nbuckets_; 153 const uint32_t lock_idx = bucket_idx % hash_table::nlocks_; 154 return lru_lists_[lock_idx]; 155 } 156 GetMutex(const uint64_t h)157 port::RWMutex& GetMutex(const uint64_t h) { 158 const uint32_t bucket_idx = h % hash_table::nbuckets_; 159 const uint32_t lock_idx = bucket_idx % hash_table::nlocks_; 160 return hash_table::locks_[lock_idx]; 161 } 162 163 std::unique_ptr<LRUListType[]> lru_lists_; 164 }; 165 166 } // namespace ROCKSDB_NAMESPACE 167 168 #endif 169