]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/utilities/persistent_cache/hash_table_evictable.h
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).
12 #include "util/random.h"
13 #include "utilities/persistent_cache/hash_table.h"
14 #include "utilities/persistent_cache/lrulist.h"
16 namespace ROCKSDB_NAMESPACE
{
18 // Evictable Hash Table
20 // Hash table index where least accessed (or one of the least accessed) elements
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
> {
27 using hash_table
= HashTable
<T
*, Hash
, Equal
>;
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_
]) {
37 virtual ~EvictableHashTable() { AssertEmptyLRU(); }
40 // Insert given record to hash table (and LRU list)
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
);
49 if (hash_table::Insert(&bucket
, t
)) {
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
);
69 if (hash_table::Find(&bucket
, t
, ret
)) {
78 // Evict one of the least recently used object
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_
;
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_
;
89 WriteLock
_(&hash_table::locks_
[idx
]);
90 LRUListType
& lru
= lru_lists_
[idx
];
91 if (!lru
.IsEmpty() && (t
= lru
.Pop()) != nullptr) {
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
);
97 bool status
= hash_table::Erase(&bucket
, t
, &tmp
);
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_
) {
121 bucket
.list_
.clear();
123 // make sure that all LRU lists are emptied
127 void AssertEmptyLRU() {
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());
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
141 port::RWMutex
* GetMutex(T
* t
) { return hash_table::GetMutex(t
); }
144 using LRUListType
= LRUList
<T
>;
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
];
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
];
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
];
163 std::unique_ptr
<LRUListType
[]> lru_lists_
;
166 } // namespace ROCKSDB_NAMESPACE