1 // Copyright 2018 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_SAMPLING_HEAP_PROFILER_LOCK_FREE_ADDRESS_HASH_SET_H_
6 #define BASE_SAMPLING_HEAP_PROFILER_LOCK_FREE_ADDRESS_HASH_SET_H_
7
8 #include <atomic>
9 #include <cstdint>
10 #include <vector>
11
12 #include "base/base_export.h"
13 #include "base/check_op.h"
14 #include "base/compiler_specific.h"
15 #include "base/memory/raw_ptr_exclusion.h"
16
17 namespace base {
18
19 // A hash set container that provides lock-free version of |Contains| operation.
20 // It does not support concurrent write operations |Insert| and |Remove|.
21 // All write operations if performed from multiple threads must be properly
22 // guarded with a lock.
23 // |Contains| method can be executed concurrently with other |Insert|, |Remove|,
24 // or |Contains| even over the same key.
25 // However, please note the result of concurrent execution of |Contains|
26 // with |Insert| or |Remove| over the same key is racy.
27 //
28 // The hash set never rehashes, so the number of buckets stays the same
29 // for the lifetime of the set.
30 //
31 // Internally the hashset is implemented as a vector of N buckets
32 // (N has to be a power of 2). Each bucket holds a single-linked list of
33 // nodes each corresponding to a key.
34 // It is not possible to really delete nodes from the list as there might
35 // be concurrent reads being executed over the node. The |Remove| operation
36 // just marks the node as empty by placing nullptr into its key field.
37 // Consequent |Insert| operations may reuse empty nodes when possible.
38 //
39 // The structure of the hashset for N buckets is the following:
40 // 0: {*}--> {key1,*}--> {key2,*}--> NULL
41 // 1: {*}--> NULL
42 // 2: {*}--> {NULL,*}--> {key3,*}--> {key4,*}--> NULL
43 // ...
44 // N-1: {*}--> {keyM,*}--> NULL
45 class BASE_EXPORT LockFreeAddressHashSet {
46 public:
47 explicit LockFreeAddressHashSet(size_t buckets_count);
48 ~LockFreeAddressHashSet();
49
50 // Checks if the |key| is in the set. Can be executed concurrently with
51 // |Insert|, |Remove|, and |Contains| operations.
52 ALWAYS_INLINE bool Contains(void* key) const;
53
54 // Removes the |key| from the set. The key must be present in the set before
55 // the invocation.
56 // Concurrent execution of |Insert|, |Remove|, or |Copy| is not supported.
57 ALWAYS_INLINE void Remove(void* key);
58
59 // Inserts the |key| into the set. The key must not be present in the set
60 // before the invocation.
61 // Concurrent execution of |Insert|, |Remove|, or |Copy| is not supported.
62 void Insert(void* key);
63
64 // Copies contents of |other| set into the current set. The current set
65 // must be empty before the call.
66 // Concurrent execution of |Insert|, |Remove|, or |Copy| is not supported.
67 void Copy(const LockFreeAddressHashSet& other);
68
buckets_count()69 size_t buckets_count() const { return buckets_.size(); }
size()70 size_t size() const { return size_; }
71
72 // Returns the average bucket utilization.
load_factor()73 float load_factor() const { return 1.f * size() / buckets_.size(); }
74
75 private:
76 friend class LockFreeAddressHashSetTest;
77
78 struct Node {
79 ALWAYS_INLINE Node(void* key, Node* next);
80 std::atomic<void*> key;
81 // This field is not a raw_ptr<> to avoid out-of-line destructor.
82 RAW_PTR_EXCLUSION Node* next;
83 };
84
85 ALWAYS_INLINE static uint32_t Hash(void* key);
86 ALWAYS_INLINE Node* FindNode(void* key) const;
87
88 std::vector<std::atomic<Node*>> buckets_;
89 size_t size_ = 0;
90 const size_t bucket_mask_;
91 };
92
Node(void * key,Node * next)93 ALWAYS_INLINE LockFreeAddressHashSet::Node::Node(void* key, Node* next)
94 : next(next) {
95 this->key.store(key, std::memory_order_relaxed);
96 }
97
Contains(void * key)98 ALWAYS_INLINE bool LockFreeAddressHashSet::Contains(void* key) const {
99 return FindNode(key) != nullptr;
100 }
101
Remove(void * key)102 ALWAYS_INLINE void LockFreeAddressHashSet::Remove(void* key) {
103 Node* node = FindNode(key);
104 DCHECK_NE(node, nullptr);
105 // We can never delete the node, nor detach it from the current bucket
106 // as there may always be another thread currently iterating over it.
107 // Instead we just mark it as empty, so |Insert| can reuse it later.
108 node->key.store(nullptr, std::memory_order_relaxed);
109 --size_;
110 }
111
FindNode(void * key)112 ALWAYS_INLINE LockFreeAddressHashSet::Node* LockFreeAddressHashSet::FindNode(
113 void* key) const {
114 DCHECK_NE(key, nullptr);
115 const std::atomic<Node*>& bucket = buckets_[Hash(key) & bucket_mask_];
116 // It's enough to use std::memory_order_consume ordering here, as the
117 // node->next->...->next loads form dependency chain.
118 // However std::memory_order_consume is temporary deprecated in C++17.
119 // See https://isocpp.org/files/papers/p0636r0.html#removed
120 // Make use of more strong std::memory_order_acquire for now.
121 for (Node* node = bucket.load(std::memory_order_acquire); node != nullptr;
122 node = node->next) {
123 if (node->key.load(std::memory_order_relaxed) == key)
124 return node;
125 }
126 return nullptr;
127 }
128
129 // static
Hash(void * key)130 ALWAYS_INLINE uint32_t LockFreeAddressHashSet::Hash(void* key) {
131 // A simple fast hash function for addresses.
132 constexpr uintptr_t random_bits = static_cast<uintptr_t>(0x4bfdb9df5a6f243b);
133 uint64_t k = reinterpret_cast<uintptr_t>(key);
134 return static_cast<uint32_t>((k * random_bits) >> 32);
135 }
136
137 } // namespace base
138
139 #endif // BASE_SAMPLING_HEAP_PROFILER_LOCK_FREE_ADDRESS_HASH_SET_H_
140