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