xenium
Loading...
Searching...
No Matches
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
22namespace 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>
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