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 72 size_t buckets_count() const { return buckets_.size(); } 73 size_t size() const { 74 return static_cast<size_t>(subtle::NoBarrier_Load(&size_)); 75 } 76 77 // Returns the average bucket utilization. 78 float load_factor() const { return 1.f * size() / buckets_.size(); } 79 80 private: 81 friend class LockFreeAddressHashSetTest; 82 83 struct Node { 84 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; 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 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 108 inline bool LockFreeAddressHashSet::Contains(void* key) const { 109 return FindNode(key) != nullptr; 110 } 111 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 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 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 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
