1 // Copyright 2018 The Chromium Authors. All rights reserved.
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 <cstdint>
9 #include <vector>
10
11 #include "base/atomicops.h"
12 #include "base/logging.h"
13
14 namespace base {
15
16 // A hash set container that provides lock-free versions of
17 // |Insert|, |Remove|, and |Contains| operations.
18 // It does not support concurrent write operations |Insert| and |Remove|
19 // over the same key. Concurrent writes of distinct keys are ok.
20 // |Contains| method can be executed concurrently with other |Insert|, |Remove|,
21 // or |Contains| even over the same key.
22 // However, please note the result of concurrent execution of |Contains|
23 // with |Insert| or |Remove| is racy.
24 //
25 // The hash set never rehashes, so the number of buckets stays the same
26 // for the lifetime of the set.
27 //
28 // Internally the hashset is implemented as a vector of N buckets
29 // (N has to be a power of 2). Each bucket holds a single-linked list of
30 // nodes each corresponding to a key.
31 // It is not possible to really delete nodes from the list as there might
32 // be concurrent reads being executed over the node. The |Remove| operation
33 // just marks the node as empty by placing nullptr into its key field.
34 // Consequent |Insert| operations may reuse empty nodes when possible.
35 //
36 // The structure of the hashset for N buckets is the following:
37 // 0: {*}--> {key1,*}--> {key2,*}--> NULL
38 // 1: {*}--> NULL
39 // 2: {*}--> {NULL,*}--> {key3,*}--> {key4,*}--> NULL
40 // ...
41 // N-1: {*}--> {keyM,*}--> NULL
42 class BASE_EXPORT LockFreeAddressHashSet {
43 public:
44 explicit LockFreeAddressHashSet(size_t buckets_count);
45 ~LockFreeAddressHashSet();
46
47 // Checks if the |key| is in the set. Can be executed concurrently with
48 // |Insert|, |Remove|, and |Contains| operations.
49 bool Contains(void* key) const;
50
51 // Removes the |key| from the set. The key must be present in the set before
52 // the invocation.
53 // Can be concurrent with other |Insert| and |Remove| executions, provided
54 // they operate over distinct keys.
55 // Concurrent |Insert| or |Remove| executions over the same key are not
56 // supported.
57 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 // Can be concurrent with other |Insert| and |Remove| executions, provided
62 // they operate over distinct keys.
63 // Concurrent |Insert| or |Remove| executions over the same key are not
64 // supported.
65 void Insert(void* key);
66
67 // Copies contents of |other| set into the current set. The current set
68 // must be empty before the call.
69 // The operation cannot be executed concurrently with any other methods.
70 void Copy(const LockFreeAddressHashSet& other);
71
buckets_count()72 size_t buckets_count() const { return buckets_.size(); }
size()73 size_t size() const {
74 return static_cast<size_t>(subtle::NoBarrier_Load(&size_));
75 }
76
77 // Returns the average bucket utilization.
load_factor()78 float load_factor() const { return 1.f * size() / buckets_.size(); }
79
80 private:
81 friend class LockFreeAddressHashSetTest;
82
83 struct Node {
NodeNode84 Node() : key(0), next(0) {}
85 explicit Node(void* key);
86
87 subtle::AtomicWord key;
88 subtle::AtomicWord next;
89 };
90
91 static uint32_t Hash(void* key);
92 Node* FindNode(void* key) const;
93 Node* Bucket(void* key) const;
next_node(Node * node)94 static Node* next_node(Node* node) {
95 return reinterpret_cast<Node*>(subtle::NoBarrier_Load(&node->next));
96 }
97
98 std::vector<subtle::AtomicWord> buckets_;
99 size_t bucket_mask_;
100 subtle::AtomicWord size_ = 0;
101 };
102
Node(void * a_key)103 inline LockFreeAddressHashSet::Node::Node(void* a_key) {
104 subtle::NoBarrier_Store(&key, reinterpret_cast<subtle::AtomicWord>(a_key));
105 subtle::NoBarrier_Store(&next, 0);
106 }
107
Contains(void * key)108 inline bool LockFreeAddressHashSet::Contains(void* key) const {
109 return FindNode(key) != nullptr;
110 }
111
Remove(void * key)112 inline void LockFreeAddressHashSet::Remove(void* key) {
113 Node* node = FindNode(key);
114 // TODO(alph): Replace with DCHECK.
115 CHECK(node != nullptr);
116 // We can never delete the node, nor detach it from the current bucket
117 // as there may always be another thread currently iterating over it.
118 // Instead we just mark it as empty, so |Insert| can reuse it later.
119 subtle::NoBarrier_Store(&node->key, 0);
120 subtle::NoBarrier_AtomicIncrement(&size_, -1);
121 }
122
FindNode(void * key)123 inline LockFreeAddressHashSet::Node* LockFreeAddressHashSet::FindNode(
124 void* key) const {
125 for (Node* node = Bucket(key); node != nullptr; node = next_node(node)) {
126 void* k = reinterpret_cast<void*>(subtle::NoBarrier_Load(&node->key));
127 if (k == key)
128 return node;
129 }
130 return nullptr;
131 }
132
Bucket(void * key)133 inline LockFreeAddressHashSet::Node* LockFreeAddressHashSet::Bucket(
134 void* key) const {
135 // TODO(alph): Replace with DCHECK.
136 CHECK(key != nullptr);
137 uint32_t h = Hash(key);
138 return reinterpret_cast<Node*>(
139 subtle::NoBarrier_Load(&buckets_[h & bucket_mask_]));
140 }
141
142 // static
Hash(void * key)143 inline uint32_t LockFreeAddressHashSet::Hash(void* key) {
144 // A simple fast hash function for addresses.
145 uint64_t k = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(key));
146 uint64_t random_bits = 0x4bfdb9df5a6f243bull;
147 return static_cast<uint32_t>((k * random_bits) >> 32);
148 }
149
150 } // namespace base
151
152 #endif // BASE_SAMPLING_HEAP_PROFILER_LOCK_FREE_ADDRESS_HASH_SET_H_
153