lock_free_address_hash_set.h 5.0 KB

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