xenium
Loading...
Searching...
No Matches
generic_epoch_based.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_GENERIC_EPOCH_BASED_HPP
7#define XENIUM_GENERIC_EPOCH_BASED_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/retire_list.hpp>
14#include <xenium/reclamation/detail/allocation_tracker.hpp>
15#include <xenium/acquire_guard.hpp>
16#include <xenium/parameter.hpp>
17
18#include <algorithm>
19
20namespace xenium {
21
22namespace reclamation {
30 namespace scan {
31 struct all_threads;
32 struct one_thread;
33 template <unsigned N>
34 struct n_threads;
35 }
36
49 namespace abandon {
50 struct never;
51 struct always;
52 template <size_t Threshold>
54 }
55
59 enum class region_extension {
64 none,
65
70 eager,
71
77 lazy
78 };
79}
80
81namespace policy {
96 template <std::size_t Value> struct scan_frequency;
97
116 template <class T> struct scan;
117
139 template <class T> struct abandon;
140
162 template <reclamation::region_extension Value> struct region_extension;
163}
164
165namespace reclamation {
166 template <
167 std::size_t ScanFrequency = 100,
168 class ScanStrategy = scan::all_threads,
169 class AbandonStrategy = abandon::never,
170 region_extension RegionExtension = region_extension::eager
171 >
172 struct generic_epoch_based_traits {
173 static constexpr std::size_t scan_frequency = ScanFrequency;
174 using scan_strategy = ScanStrategy;
175 using abandon_strategy = AbandonStrategy;
176 static constexpr region_extension region_extension_type = RegionExtension;
177
178 template <class... Policies>
179 using with = generic_epoch_based_traits<
180 parameter::value_param_t<std::size_t, policy::scan_frequency, ScanFrequency, Policies...>::value,
181 parameter::type_param_t<policy::scan, ScanStrategy, Policies...>,
182 parameter::type_param_t<policy::abandon, AbandonStrategy, Policies...>,
183 parameter::value_param_t<region_extension, policy::region_extension, RegionExtension, Policies...>::value
184 >;
185 };
186
238 template <class Traits = generic_epoch_based_traits<>>
240 {
241 template <class T, class MarkedPtr>
242 class guard_ptr;
243
244 template <unsigned N>
245 friend struct scan::n_threads;
246 friend struct scan::all_threads;
247
248 public:
259 template <class... Policies>
260 using with = generic_epoch_based<typename Traits::template with<Policies...>>;
261
262 template <class T, std::size_t N = 0, class Deleter = std::default_delete<T>>
263 class enable_concurrent_ptr;
264
265 struct region_guard
266 {
267 region_guard() noexcept;
268 ~region_guard() noexcept;
269
270 region_guard(const region_guard&) = delete;
271 region_guard(region_guard&&) = delete;
272 region_guard& operator=(const region_guard&) = delete;
273 region_guard& operator=(region_guard&&) = delete;
274 };
275
276 template <class T, std::size_t N = T::number_of_mark_bits>
277 using concurrent_ptr = xenium::reclamation::detail::concurrent_ptr<T, N, guard_ptr>;
278
279 ALLOCATION_TRACKER;
280 private:
281 using epoch_t = size_t;
282
283 static constexpr epoch_t number_epochs = 3;
284
285 struct thread_data;
286 struct thread_control_block;
287
288 inline static std::atomic<epoch_t> global_epoch;
289 inline static detail::thread_block_list<thread_control_block> global_thread_block_list;
290 inline static std::array<detail::orphan_list<>, number_epochs> orphans;
291 inline static thread_local thread_data local_thread_data;
292
293 ALLOCATION_TRACKING_FUNCTIONS;
294 };
295
297 template <class T, std::size_t N, class Deleter>
298 class generic_epoch_based<Traits>::enable_concurrent_ptr :
299 private detail::deletable_object_impl<T, Deleter>,
300 private detail::tracked_object<generic_epoch_based>
301 {
302 public:
303 static constexpr std::size_t number_of_mark_bits = N;
304 protected:
305 enable_concurrent_ptr() noexcept = default;
306 enable_concurrent_ptr(const enable_concurrent_ptr&) noexcept = default;
307 enable_concurrent_ptr(enable_concurrent_ptr&&) noexcept = default;
308 enable_concurrent_ptr& operator=(const enable_concurrent_ptr&) noexcept = default;
309 enable_concurrent_ptr& operator=(enable_concurrent_ptr&&) noexcept = default;
310 ~enable_concurrent_ptr() noexcept = default;
311 private:
312 friend detail::deletable_object_impl<T, Deleter>;
313
315 friend class guard_ptr;
316 };
317
320 class generic_epoch_based<Traits>::guard_ptr : public detail::guard_ptr<T, MarkedPtr, guard_ptr<T, MarkedPtr>>
321 {
322 using base = detail::guard_ptr<T, MarkedPtr, guard_ptr>;
323 using Deleter = typename T::Deleter;
324 public:
325 // Guard a marked ptr.
326 explicit guard_ptr(const MarkedPtr& p = MarkedPtr()) noexcept;
327 guard_ptr(const guard_ptr& p) noexcept;
328 guard_ptr(guard_ptr&& p) noexcept;
329
330 guard_ptr& operator=(const guard_ptr& p) noexcept;
331 guard_ptr& operator=(guard_ptr&& p) noexcept;
332
333 // Atomically take snapshot of p, and *if* it points to unreclaimed object, acquire shared ownership of it.
335
336 // Like acquire, but quit early if a snapshot != expected.
337 bool acquire_if_equal(const concurrent_ptr<T>& p,
340
341 // Release ownership. Postcondition: get() == nullptr.
342 void reset() noexcept;
343
344 // Reset. Deleter d will be applied some time after all owners release their ownership.
345 void reclaim(Deleter d = Deleter()) noexcept;
346 };
347}}
348
349#define GENERIC_EPOCH_BASED_IMPL
350#include "impl/generic_epoch_based.hpp"
351#undef GENERIC_EPOCH_BASED_IMPL
352
353namespace xenium { namespace reclamation {
354 template <class... Policies>
359 Policies...
360 >;
361
362 template <class... Policies>
367 Policies...
368 >;
369
370 template <class... Policies>
375 Policies...
376 >;
377}}
378
379#endif
T must be derived from enable_concurrent_ptr<T>. D is a deleter.
Definition concurrent_ptr.hpp:21
A generalized implementation of epoch based reclamation.
Definition generic_epoch_based.hpp:240
Slim wrapper around std::hash with specialization for pointer types.
Definition hash.hpp:25
Policy to configure the abandon strategy for generic_epoch_based reclamation.
Definition generic_epoch_based.hpp:139
Policy to configure the hash function.
Definition policy.hpp:86
Policy to configure the extension of critical regions in generic_epoch_based reclamation.
Definition generic_epoch_based.hpp:162
Policy to configure the scan frequency for generic_epoch_based reclamation.
Definition generic_epoch_based.hpp:96
Policy to configure the scan strategy for generic_epoch_based reclamation.
Definition generic_epoch_based.hpp:116
Always abandon the remaining retired nodes when the thread leaves its critical region.
Definition generic_epoch_based.hpp:99
Never abandon any nodes (except when the thread terminates).
Definition generic_epoch_based.hpp:90
Abandon the retired nodes upon leaving the critical region when the number of nodes exceeds the speci...
Definition generic_epoch_based.hpp:113
Scan all threads (default behaviour in EBR/NEBR).
Definition generic_epoch_based.hpp:23
Scan N threads.
Definition generic_epoch_based.hpp:49
Scan a single thread (default behaviour in DEBRA).
Definition generic_epoch_based.hpp:80