xenium
hazard_pointer.hpp
1 //
2 // Copyright (c) 2018-2020 Manuel Pöter.
3 // Licensed under the MIT License. See LICENSE file in the project root for full license information.
4 //
5 
6 #ifndef XENIUM_HAZARD_POINTER_HPP
7 #define XENIUM_HAZARD_POINTER_HPP
8 
9 #include <xenium/reclamation/detail/concurrent_ptr.hpp>
10 #include <xenium/reclamation/detail/guard_ptr.hpp>
11 #include <xenium/reclamation/detail/deletable_object.hpp>
12 #include <xenium/reclamation/detail/thread_block_list.hpp>
13 #include <xenium/reclamation/detail/allocation_tracker.hpp>
14 
15 #include <xenium/acquire_guard.hpp>
16 #include <xenium/parameter.hpp>
17 #include <xenium/policy.hpp>
18 
19 #include <memory>
20 #include <stdexcept>
21 
22 namespace xenium { namespace reclamation {
23 
29  class bad_hazard_pointer_alloc : public std::runtime_error {
30  using std::runtime_error::runtime_error;
31  };
32 
33  namespace detail {
34  template <class Strategy, class Derived>
35  struct basic_hp_thread_control_block;
36 
37  template <size_t K_, size_t A, size_t B, template <class> class ThreadControlBlock>
38  struct generic_hp_allocation_strategy
39  {
40  static constexpr size_t K = K_;
41 
42  static size_t retired_nodes_threshold() {
43  return A * number_of_active_hazard_pointers() + B;
44  }
45 
46  static size_t number_of_active_hazard_pointers() {
47  return number_of_active_hps.load(std::memory_order_relaxed);
48  }
49 
50  using thread_control_block = ThreadControlBlock<generic_hp_allocation_strategy>;
51  private:
52  friend thread_control_block;
53  friend basic_hp_thread_control_block<generic_hp_allocation_strategy, thread_control_block>;
54 
55  inline static std::atomic<size_t> number_of_active_hps{0};
56  };
57 
58  template <class Strategy>
59  struct static_hp_thread_control_block;
60 
61  template <class Strategy>
62  struct dynamic_hp_thread_control_block;
63  }
64 
65  namespace hp_allocation {
76  template <size_t K = 2, size_t A = 2, size_t B = 100>
77  struct static_strategy :
78  detail::generic_hp_allocation_strategy<K, A, B, detail::static_hp_thread_control_block> {};
79 
101  template <size_t K = 2, size_t A = 2, size_t B = 100>
103  detail::generic_hp_allocation_strategy<K, A, B, detail::dynamic_hp_thread_control_block> {};
104  }
105 
106  template <class AllocationStrategy = hp_allocation::static_strategy<3>>
107  struct hazard_pointer_traits {
108  using allocation_strategy = AllocationStrategy;
109 
110  template <class... Policies>
111  using with = hazard_pointer_traits<
112  parameter::type_param_t<policy::allocation_strategy, AllocationStrategy, Policies...>
113  >;
114  };
115 
134  template <typename Traits = hazard_pointer_traits<>>
136  {
137  using allocation_strategy = typename Traits::allocation_strategy;
138  using thread_control_block = typename allocation_strategy::thread_control_block;
139  friend detail::basic_hp_thread_control_block<allocation_strategy, thread_control_block>;
140 
141  template <class T, class MarkedPtr>
142  class guard_ptr;
143 
144  public:
155  template <class... Policies>
156  using with = hazard_pointer<typename Traits::template with<Policies...>>;
157 
158  template <class T, std::size_t N = 0, class Deleter = std::default_delete<T>>
159  class enable_concurrent_ptr;
160 
161  class region_guard {};
162 
163  template <class T, std::size_t N = T::number_of_mark_bits>
164  using concurrent_ptr = detail::concurrent_ptr<T, N, guard_ptr>;
165 
166  ALLOCATION_TRACKER;
167  private:
168  struct thread_data;
169 
170  inline static detail::thread_block_list<thread_control_block> global_thread_block_list;
171  inline static thread_local thread_data local_thread_data;
172 
173  ALLOCATION_TRACKING_FUNCTIONS;
174  };
175 
176  template <typename Traits>
177  template <class T, std::size_t N, class Deleter>
178  class hazard_pointer<Traits>::enable_concurrent_ptr :
179  private detail::deletable_object_impl<T, Deleter>,
180  private detail::tracked_object<hazard_pointer>
181  {
182  public:
183  static constexpr std::size_t number_of_mark_bits = N;
184  protected:
185  enable_concurrent_ptr() noexcept = default;
186  enable_concurrent_ptr(const enable_concurrent_ptr&) noexcept = default;
187  enable_concurrent_ptr(enable_concurrent_ptr&&) noexcept = default;
188  enable_concurrent_ptr& operator=(const enable_concurrent_ptr&) noexcept = default;
189  enable_concurrent_ptr& operator=(enable_concurrent_ptr&&) noexcept = default;
190  ~enable_concurrent_ptr() noexcept = default;
191  private:
192  friend detail::deletable_object_impl<T, Deleter>;
193 
194  template <class, class>
195  friend class guard_ptr;
196  };
197 
198  template <typename Traits>
199  template <class T, class MarkedPtr>
200  class hazard_pointer<Traits>::guard_ptr : public detail::guard_ptr<T, MarkedPtr, guard_ptr<T, MarkedPtr>>
201  {
202  using base = detail::guard_ptr<T, MarkedPtr, guard_ptr>;
203  using Deleter = typename T::Deleter;
204  public:
205  guard_ptr() noexcept = default;
206 
207  // Guard a marked ptr.
208  explicit guard_ptr(const MarkedPtr& p);
209  guard_ptr(const guard_ptr& p);
210  guard_ptr(guard_ptr&& p) noexcept;
211 
212  guard_ptr& operator=(const guard_ptr& p) noexcept;
213  guard_ptr& operator=(guard_ptr&& p) noexcept;
214 
215  // Atomically take snapshot of p, and *if* it points to unreclaimed object, acquire shared ownership of it.
216  void acquire(const concurrent_ptr<T>& p, std::memory_order order = std::memory_order_seq_cst);
217 
218  // Like acquire, but quit early if a snapshot != expected.
219  bool acquire_if_equal(const concurrent_ptr<T>& p,
220  const MarkedPtr& expected,
221  std::memory_order order = std::memory_order_seq_cst);
222 
223  // Release ownership. Postcondition: get() == nullptr.
224  void reset() noexcept;
225 
226  // Reset. Deleter d will be applied some time after all owners release their ownership.
227  void reclaim(Deleter d = Deleter()) noexcept;
228 
229  private:
230  using enable_concurrent_ptr = hazard_pointer::enable_concurrent_ptr<T, MarkedPtr::number_of_mark_bits, Deleter>;
231 
232  friend base;
233  void do_swap(guard_ptr& g) noexcept;
234 
235  typename thread_control_block::hazard_pointer* hp = nullptr;
236  };
237 }}
238 
239 #define HAZARD_POINTER_IMPL
240 #include <xenium/reclamation/impl/hazard_pointer.hpp>
241 #undef HAZARD_POINTER_IMPL
242 
243 #endif
This exception is thrown if a thread tries to allocate a new hazard pointer, but the number of availa...
Definition: hazard_pointer.hpp:29
T must be derived from enable_concurrent_ptr<T>. D is a deleter.
Definition: concurrent_ptr.hpp:21
An implementation of the hazard pointers reclamation scheme as proposed by Michael [Mic04].
Definition: hazard_pointer.hpp:136
Policy to configure the allocation strategy.
Definition: policy.hpp:97
Hazard pointer allocation strategy for a dynamic number of hazard pointers per thread.
Definition: hazard_pointer.hpp:103
Hazard pointer allocation strategy for a static number of hazard pointers per thread.
Definition: hazard_pointer.hpp:78