]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2013, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
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 | ||
f67539c2 | 16 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
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 | ||
37 | virtual ~EvictableHashTable() { AssertEmptyLRU(); } | |
38 | ||
39 | // | |
40 | // Insert given record to hash table (and LRU list) | |
41 | // | |
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. | |
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]; | |
11fdf7f2 | 91 | if (!lru.IsEmpty() && (t = lru.Pop()) != nullptr) { |
7c673cae FG |
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 | ||
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 | ||
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. | |
141 | port::RWMutex* GetMutex(T* t) { return hash_table::GetMutex(t); } | |
142 | ||
143 | private: | |
144 | typedef LRUList<T> LRUListType; | |
145 | ||
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 | ||
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 | ||
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 | ||
f67539c2 | 166 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
167 | |
168 | #endif |