xenium
stamp_it.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_STAMP_IT_HPP
7 #define XENIUM_STAMP_IT_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 
17 namespace xenium { namespace reclamation {
18 
22  class stamp_it
23  {
24  template <class T, class MarkedPtr>
25  class guard_ptr;
26 
27  public:
28  template <class T, std::size_t N = 0, class Deleter = std::default_delete<T>>
29  class enable_concurrent_ptr;
30 
31  struct region_guard
32  {
33  region_guard() noexcept;
34  ~region_guard();
35 
36  region_guard(const region_guard&) = delete;
37  region_guard(region_guard&&) = delete;
38  region_guard& operator=(const region_guard&) = delete;
39  region_guard& operator=(region_guard&&) = delete;
40  };
41 
42  template <class T, std::size_t N = T::number_of_mark_bits>
44 
45 #ifdef WITH_PERF_COUNTER
46  struct performance_counters
47  {
48  size_t push_calls = 0;
49  size_t push_iterations = 0;
50  size_t remove_calls = 0;
51  size_t remove_next_iterations = 0;
52  size_t remove_prev_iterations = 0;
53  };
54  static performance_counters get_performance_counters();
55 #endif
56 
57  ALLOCATION_TRACKER;
58  private:
59  static constexpr size_t MarkBits = 18;
60 
61  using stamp_t = size_t;
62 
63  struct deletable_object_with_stamp;
64  struct thread_control_block;
65  struct thread_data;
66 
67  class thread_order_queue;
68 
69  static constexpr stamp_t NotInList = 1;
70  static constexpr stamp_t PendingPush = 2;
71  static constexpr stamp_t StampInc = 4;
72 
73  static thread_order_queue queue;
74  static thread_data& local_thread_data();
75 
76  ALLOCATION_TRACKING_FUNCTIONS;
77  };
78 
79  struct stamp_it::deletable_object_with_stamp
80  {
81  virtual void delete_self() = 0;
82  deletable_object_with_stamp* next = nullptr;
83  deletable_object_with_stamp* next_chunk = nullptr;
84  protected:
85  virtual ~deletable_object_with_stamp() = default;
86  private:
87  stamp_t stamp{};
88  friend class stamp_it;
89  };
90 
91  template <class T, std::size_t N, class Deleter>
92  class stamp_it::enable_concurrent_ptr :
93  private detail::deletable_object_impl<T, Deleter, deletable_object_with_stamp>,
94  private detail::tracked_object<stamp_it>
95  {
96  public:
97  static constexpr std::size_t number_of_mark_bits = N;
98  protected:
99  enable_concurrent_ptr() noexcept = default;
100  enable_concurrent_ptr(const enable_concurrent_ptr&) noexcept = default;
101  enable_concurrent_ptr(enable_concurrent_ptr&&) noexcept = default;
102  enable_concurrent_ptr& operator=(const enable_concurrent_ptr&) noexcept = default;
103  enable_concurrent_ptr& operator=(enable_concurrent_ptr&&) noexcept = default;
104  ~enable_concurrent_ptr() noexcept = default;
105  private:
106  friend detail::deletable_object_impl<T, Deleter, deletable_object_with_stamp>;
107 
108  template <class, class>
109  friend class guard_ptr;
110  };
111 
112  template <class T, class MarkedPtr>
113  class stamp_it::guard_ptr : public detail::guard_ptr<T, MarkedPtr, guard_ptr<T, MarkedPtr>>
114  {
115  using base = detail::guard_ptr<T, MarkedPtr, guard_ptr>;
116  using Deleter = typename T::Deleter;
117  public:
118  // Guard a marked ptr.
119  explicit guard_ptr(const MarkedPtr& p = MarkedPtr()) noexcept;
120  guard_ptr(const guard_ptr& p) noexcept;
121  guard_ptr(guard_ptr&& p) noexcept;
122 
123  guard_ptr& operator=(const guard_ptr& p) noexcept;
124  guard_ptr& operator=(guard_ptr&& p) noexcept;
125 
126  // Atomically take snapshot of p, and *if* it points to unreclaimed object, acquire shared ownership of it.
127  void acquire(const concurrent_ptr<T>& p, std::memory_order order = std::memory_order_seq_cst) noexcept;
128 
129  // Like acquire, but quit early if a snapshot != expected.
130  bool acquire_if_equal(const concurrent_ptr<T>& p,
131  const MarkedPtr& expected,
132  std::memory_order order = std::memory_order_seq_cst) noexcept;
133 
134  // Release ownership. Postcondition: get() == nullptr.
135  void reset() noexcept;
136 
137  // Reset. Deleter d will be applied some time after all owners release their ownership.
138  void reclaim(Deleter d = Deleter()) noexcept;
139  };
140 }}
141 
142 #define STAMP_IT_IMPL
143 #include <xenium/reclamation/impl/stamp_it.hpp>
144 #undef STAMP_IT_IMPL
145 
146 #endif
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::stamp_it
Stamp-it.
Definition: stamp_it.hpp:23