xenium
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 
20 namespace xenium {
21 
22 namespace 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 
81 namespace 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 
165 namespace 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 
296  template <class Traits>
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 
314  template <class, class>
315  friend class guard_ptr;
316  };
317 
318  template <class Traits>
319  template <class T, class MarkedPtr>
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.
334  void acquire(const concurrent_ptr<T>& p, std::memory_order order = std::memory_order_seq_cst) noexcept;
335 
336  // Like acquire, but quit early if a snapshot != expected.
337  bool acquire_if_equal(const concurrent_ptr<T>& p,
338  const MarkedPtr& expected,
339  std::memory_order order = std::memory_order_seq_cst) noexcept;
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 
353 namespace 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
xenium::policy::scan
Policy to configure the scan strategy for generic_epoch_based reclamation.
Definition: generic_epoch_based.hpp:116
xenium::reclamation::scan::n_threads
Scan N threads.
Definition: generic_epoch_based.hpp:34
xenium::reclamation::abandon::never
Never abandon any nodes (except when the thread terminates).
Definition: generic_epoch_based.hpp:90
xenium::policy::region_extension
Policy to configure the extension of critical regions in generic_epoch_based reclamation.
Definition: generic_epoch_based.hpp:162
xenium::reclamation::detail::concurrent_ptr
T must be derived from enable_concurrent_ptr<T>. D is a deleter.
Definition: concurrent_ptr.hpp:21
xenium::reclamation::generic_epoch_based
A generalized implementation of epoch based reclamation.
Definition: generic_epoch_based.hpp:240
xenium::reclamation::abandon::always
Always abandon the remaining retired nodes when the thread leaves its critical region.
Definition: generic_epoch_based.hpp:99
xenium::reclamation::abandon::when_exceeds_threshold
Abandon the retired nodes upon leaving the critical region when the number of nodes exceeds the speci...
Definition: generic_epoch_based.hpp:53
xenium::policy::scan_frequency
Policy to configure the scan frequency for generic_epoch_based reclamation.
Definition: generic_epoch_based.hpp:96
xenium::reclamation::scan::one_thread
Scan a single thread (default behaviour in DEBRA).
Definition: generic_epoch_based.hpp:80
xenium::reclamation::scan::all_threads
Scan all threads (default behaviour in EBR/NEBR).
Definition: generic_epoch_based.hpp:23
xenium::policy::abandon
Policy to configure the abandon strategy for generic_epoch_based reclamation.
Definition: generic_epoch_based.hpp:139