xenium
hazard_eras.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 HAZARD_ERAS_IMPL
7 #error "This is an impl file and must not be included directly!"
8 #endif
9 
10 #include <xenium/aligned_object.hpp>
11 #include <xenium/detail/port.hpp>
12 
13 #include <algorithm>
14 #include <new>
15 #include <vector>
16 
17 #ifdef _MSC_VER
18 #pragma warning(push)
19 #pragma warning(disable: 4324) // structure was padded due to alignment specifier
20 #pragma warning(disable: 26495) // uninitialized member variable
21 #endif
22 
23 namespace xenium { namespace reclamation {
24 
25  template <class Traits>
26  template <class T, class MarkedPtr>
27  hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::guard_ptr(const MarkedPtr& p) :
28  base(p),
29  he()
30  {
31  if (this->ptr.get() != nullptr)
32  {
33  auto era = era_clock.load(std::memory_order_relaxed);
34  he = local_thread_data().alloc_hazard_era(era);
35  }
36  }
37 
38  template <class Traits>
39  template <class T, class MarkedPtr>
40  hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::guard_ptr(const guard_ptr& p) :
41  base(p.ptr),
42  he(p.he)
43  {
44  if (he)
45  he->add_guard();
46  }
47 
48  template <class Traits>
49  template <class T, class MarkedPtr>
50  hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::guard_ptr(guard_ptr&& p) noexcept :
51  base(p.ptr),
52  he(p.he)
53  {
54  p.ptr.reset();
55  p.he = nullptr;
56  }
57 
58  template <class Traits>
59  template <class T, class MarkedPtr>
60  auto hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::operator=(const guard_ptr& p) noexcept
61  -> guard_ptr&
62  {
63  if (&p == this)
64  return *this;
65 
66  reset();
67  this->ptr = p.ptr;
68  he = p.he;
69  if (he)
70  he->add_guard();
71  return *this;
72  }
73 
74  template <class Traits>
75  template <class T, class MarkedPtr>
76  auto hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::operator=(guard_ptr&& p) noexcept
77  -> guard_ptr&
78  {
79  if (&p == this)
80  return *this;
81 
82  reset();
83  this->ptr = std::move(p.ptr);
84  this->he = p.he;
85  p.ptr.reset();
86  p.he = nullptr;
87  return *this;
88  }
89 
90  template <class Traits>
91  template <class T, class MarkedPtr>
92  void hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::acquire(const concurrent_ptr<T>& p,
93  std::memory_order order)
94  {
95  if (order == std::memory_order_relaxed || order == std::memory_order_consume) {
96  // we have to use memory_order_acquire (or something stricter) to ensure that
97  // the era_clock.load cannot return an outdated value.
98  order = std::memory_order_acquire;
99  }
100  era_t prev_era = he == nullptr ? 0 : he->get_era();
101  for (;;) {
102  // (1) - this load operation synchronizes-with any release operation on p.
103  // we have to use acquire here to ensure that the subsequent era_clock.load
104  // sees a value >= p.construction_era
105  auto value = p.load(order);
106 
107  auto era = era_clock.load(std::memory_order_relaxed);
108  if (era == prev_era) {
109  this->ptr = value;
110  return;
111  }
112 
113  if (he != nullptr)
114  {
115  assert(he->get_era() != era);
116  if (he->guards() == 1)
117  {
118  // we are the only guard using this HE instance -> reuse it and simply update the era
119  he->set_era(era);
120  prev_era = era;
121  continue;
122  }
123  else {
124  he->release_guard();
125  he = nullptr;
126  }
127  }
128  assert(he == nullptr);
129  he = local_thread_data().alloc_hazard_era(era);
130  prev_era = era;
131  }
132  }
133 
134  template <class Traits>
135  template <class T, class MarkedPtr>
136  bool hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::acquire_if_equal(
137  const concurrent_ptr<T>& p,
138  const MarkedPtr& expected,
139  std::memory_order order)
140  {
141  if (order == std::memory_order_relaxed || order == std::memory_order_consume) {
142  // we have to use memory_order_acquire (or something stricter) to ensure that
143  // the era_clock.load cannot return an outdated value.
144  order = std::memory_order_acquire;
145  }
146 
147  // (2) - this load operation synchronizes-with any release operation on p.
148  // we have to use acquire here to ensure that the subsequent era_clock.load
149  // sees a value >= p.construction_era
150  auto p1 = p.load(order);
151  if (p1 == nullptr || p1 != expected) {
152  reset();
153  return p1 == expected;
154  }
155 
156  const auto era = era_clock.load(std::memory_order_relaxed);
157  if (he != nullptr && he->guards() == 1)
158  he->set_era(era);
159  else {
160  if (he != nullptr)
161  he->release_guard();
162 
163  he = local_thread_data().alloc_hazard_era(era);
164  }
165 
166  this->ptr = p.load(std::memory_order_relaxed);
167  if (this->ptr != p1)
168  {
169  reset();
170  return false;
171  }
172  return true;
173  }
174 
175  template <class Traits>
176  template <class T, class MarkedPtr>
177  void hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::reset() noexcept
178  {
179  local_thread_data().release_hazard_era(he);
180  assert(this->he == nullptr);
181  this->ptr.reset();
182  }
183 
184  template <class Traits>
185  template <class T, class MarkedPtr>
186  void hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::do_swap(guard_ptr& g) noexcept
187  {
188  std::swap(he, g.he);
189  }
190 
191  template <class Traits>
192  template <class T, class MarkedPtr>
193  void hazard_eras<Traits>::guard_ptr<T, MarkedPtr>::reclaim(Deleter d) noexcept
194  {
195  auto p = this->ptr.get();
196  reset();
197  p->set_deleter(std::move(d));
198  // (3) - this release fetch-add synchronizes-with the seq-cst fence (5)
199  p->retirement_era = era_clock.fetch_add(1, std::memory_order_release);
200 
201  if (local_thread_data().add_retired_node(p) >= allocation_strategy::retired_nodes_threshold())
202  local_thread_data().scan();
203  }
204 
205  namespace detail {
206  template <class Strategy, class Derived>
207  struct alignas(64) basic_he_thread_control_block :
208  detail::thread_block_list<Derived, detail::deletable_object_with_eras>::entry,
209  aligned_object<basic_he_thread_control_block<Strategy, Derived>>
210  {
211  using era_t = uint64_t;
212 
213  ~basic_he_thread_control_block() {
214  assert(last_hazard_era != nullptr);
215  }
216 
217  struct hazard_era
218  {
219  hazard_era(): value(nullptr), guard_cnt(0) {}
220 
221  void set_era(era_t era)
222  {
223  assert(era != 0);
224  // (4) - this release-store synchronizes-with the acquire-fence (10)
225  value.store(marked_ptr(reinterpret_cast<void**>(era << 1)), std::memory_order_release);
226  // This release is required because when acquire/acquire_if_equal is called on a
227  // guard_ptr with with an active HE entry, set_era is called without an intermediate
228  // call to set_link, i.e., the protected era is updated. This ensures the required
229  // happens-before relation between releasing a guard_ptr to a node and reclamation
230  // of that node.
231 
232  // (5) - this seq_cst-fence enforces a total order with the seq_cst-fence (9)
233  // and synchronizes-with the release-fetch-add (3)
234  std::atomic_thread_fence(std::memory_order_seq_cst);
235  }
236 
237  era_t get_era() const
238  {
239  era_t result = 0;
240  bool success = try_get_era(result);
241  (void)success;
242  assert(success);
243  assert(result != 0);
244  return result;
245  }
246 
247  uint64_t guards() const { return guard_cnt; }
248  uint64_t add_guard() { return ++guard_cnt; }
249  uint64_t release_guard() { return --guard_cnt; }
250 
251  bool try_get_era(era_t& result) const
252  {
253  // TSan does not support explicit fences, so we cannot rely on the acquire-fence (10)
254  // but have to perform an acquire-load here to avoid false positives.
255  constexpr auto memory_order = TSAN_MEMORY_ORDER(std::memory_order_acquire, std::memory_order_relaxed);
256  auto v = value.load(memory_order);
257  if (v.mark() == 0)
258  {
259  result = reinterpret_cast<era_t>(v.get()) >> 1;
260  return true;
261  }
262  return false; // value contains a link
263  }
264 
265  void set_link(hazard_era* link)
266  {
267  assert(guard_cnt == 0);
268  // (6) - this release store synchronizes-with the acquire fence (10)
269  value.store(marked_ptr(reinterpret_cast<void**>(link), 1), std::memory_order_release);
270  }
271  hazard_era* get_link() const
272  {
273  assert(is_link());
274  return reinterpret_cast<hazard_era*>(value.load(std::memory_order_relaxed).get());
275  }
276 
277  bool is_link() const
278  {
279  return value.load(std::memory_order_relaxed).mark() != 0;
280  }
281  private:
282  using marked_ptr = xenium::marked_ptr<void*, 1>;
283  // since we use the hazard era array to build our internal linked list of hazard eras we set
284  // the LSB to signal that this is an internal pointer and not a pointer to a protected object.
285  std::atomic<marked_ptr> value;
286  // the number of guard_ptrs that reference this instance and therefore observe the same era
287  uint64_t guard_cnt;
288  };
289 
290  using hint = hazard_era*;
291 
292  void initialize(hint& hint)
293  {
294  Strategy::number_of_active_hes.fetch_add(self().number_of_hes(), std::memory_order_relaxed);
295  hint = initialize_block(self());
296  }
297 
298  void abandon()
299  {
300  Strategy::number_of_active_hes.fetch_sub(self().number_of_hes(), std::memory_order_relaxed);
301  detail::thread_block_list<Derived, detail::deletable_object_with_eras>::entry::abandon();
302  }
303 
304  hazard_era* alloc_hazard_era(hint& hint, era_t era)
305  {
306  if (last_hazard_era && last_era == era) {
307  last_hazard_era->add_guard();
308  return last_hazard_era;
309  }
310  auto result = hint;
311  if (result == nullptr)
312  result = self().need_more_hes();
313 
314  hint = result->get_link();
315  result->set_era(era);
316  result->add_guard();
317 
318  last_hazard_era = result;
319  last_era = era;
320  return result;
321  }
322 
323  void release_hazard_era(hazard_era*& he, hint& hint)
324  {
325  assert(he != nullptr);
326  if (he->release_guard() == 0)
327  {
328  if (he == last_hazard_era)
329  last_hazard_era = nullptr;
330 
331  he->set_link(hint);
332  hint = he;
333  }
334  he = nullptr;
335  }
336 
337  protected:
338  Derived& self() { return static_cast<Derived&>(*this); }
339 
340  hazard_era* begin() { return &eras[0]; }
341  hazard_era* end() { return &eras[Strategy::K]; }
342  const hazard_era* begin() const { return &eras[0]; }
343  const hazard_era* end() const { return &eras[Strategy::K]; }
344 
345  template <typename T>
346  static hazard_era* initialize_block(T& block)
347  {
348  auto begin = block.begin();
349  auto end = block.end() - 1; // the last element is handled specially, so loop only over n-1 entries
350  for (auto it = begin; it != end;)
351  {
352  auto next = it + 1;
353  it->set_link(next);
354  it = next;
355  }
356  end->set_link(block.initialize_next_block());
357  return begin;
358  }
359 
360  static void gather_protected_eras(std::vector<era_t>& protected_eras,
361  const hazard_era* begin, const hazard_era* end)
362  {
363  for (auto it = begin; it != end; ++it)
364  {
365  era_t era;
366  if (it->try_get_era(era))
367  protected_eras.push_back(era);
368  }
369  }
370 
371  hazard_era* last_hazard_era;
372  era_t last_era;
373  hazard_era eras[Strategy::K];
374  };
375 
376  template <class Strategy>
377  struct static_he_thread_control_block :
378  basic_he_thread_control_block<Strategy, static_he_thread_control_block<Strategy>>
379  {
380  using base = basic_he_thread_control_block<Strategy, static_he_thread_control_block>;
381  using hazard_era = typename base::hazard_era;
382  using era_t = typename base::era_t;
383  friend base;
384 
385  void gather_protected_eras(std::vector<era_t>& protected_eras) const
386  {
387  base::gather_protected_eras(protected_eras, this->begin(), this->end());
388  }
389  private:
390  hazard_era* need_more_hes() {
391  throw bad_hazard_era_alloc("hazard era pool exceeded"); }
392  constexpr size_t number_of_hes() const { return Strategy::K; }
393  constexpr hazard_era* initialize_next_block() const { return nullptr; }
394  };
395 
396  template <class Strategy>
397  struct dynamic_he_thread_control_block :
398  basic_he_thread_control_block<Strategy, dynamic_he_thread_control_block<Strategy>>
399  {
400  using base = basic_he_thread_control_block<Strategy, dynamic_he_thread_control_block>;
401  using hazard_era = typename base::hazard_era;
402  using era_t = typename base::era_t;
403  friend base;
404 
405  void gather_protected_eras(std::vector<era_t>& protected_eras) const
406  {
407  gather_protected_eras(*this, protected_eras);
408  }
409 
410  private:
411  struct alignas(64) hazard_eras_block : aligned_object<hazard_eras_block>
412  {
413  hazard_eras_block(size_t size) : size(size) {
414  for (auto it = begin(); it != end(); ++it) {
415  new(it) hazard_era;
416  }
417  }
418 
419  hazard_era* begin() { return reinterpret_cast<hazard_era*>(this + 1); }
420  hazard_era* end() { return begin() + size; }
421 
422  const hazard_era* begin() const { return reinterpret_cast<const hazard_era*>(this + 1); }
423  const hazard_era* end() const { return begin() + size; }
424 
425  const hazard_eras_block* next_block() const { return next; }
426  hazard_era* initialize_next_block() { return next ? base::initialize_block(*next) : nullptr; }
427 
428  hazard_eras_block* next = nullptr;
429  const size_t size;
430  };
431 
432  const hazard_eras_block* next_block() const
433  {
434  // (7) - this acquire-load synchronizes-with the release-store (8)
435  return he_block.load(std::memory_order_acquire);
436  }
437  size_t number_of_hes() const { return total_number_of_hes; }
438  hazard_era* need_more_hes() { return allocate_new_hazard_eras_block(); }
439 
440 
441  hazard_era* initialize_next_block()
442  {
443  auto block = he_block.load(std::memory_order_relaxed);
444  return block ? base::initialize_block(*block) : nullptr;
445  }
446 
447  template <typename T>
448  static void gather_protected_eras(const T& block, std::vector<era_t>& protected_eras)
449  {
450  base::gather_protected_eras(protected_eras, block.begin(), block.end());
451 
452  auto next = block.next_block();
453  if (next)
454  gather_protected_eras(*next, protected_eras);
455  }
456 
457  hazard_era* allocate_new_hazard_eras_block()
458  {
459  size_t hes = std::max(static_cast<size_t>(Strategy::K), total_number_of_hes / 2);
460  total_number_of_hes += hes;
461  Strategy::number_of_active_hes.fetch_add(hes, std::memory_order_relaxed);
462 
463  size_t buffer_size = sizeof(hazard_eras_block) + hes * sizeof(hazard_era);
464  void* buffer = hazard_eras_block::operator new(buffer_size);
465  auto block = ::new(buffer) hazard_eras_block(hes);
466  auto result = this->initialize_block(*block);
467  block->next = he_block.load(std::memory_order_relaxed);
468  // (8) - this release-store synchronizes-with the acquire-load (7)
469  he_block.store(block, std::memory_order_release);
470  return result;
471  }
472 
473  size_t total_number_of_hes = Strategy::K;
474  std::atomic<hazard_eras_block*> he_block;
475  };
476  }
477 
478  template <class Traits>
479  struct alignas(64) hazard_eras<Traits>::thread_data : aligned_object<thread_data>
480  {
481  using HE = typename thread_control_block::hazard_era*;
482 
483  ~thread_data()
484  {
485  if (retire_list != nullptr)
486  {
487  scan();
488  if (retire_list != nullptr)
489  global_thread_block_list.abandon_retired_nodes(retire_list);
490  retire_list = nullptr;
491  }
492 
493  if (control_block != nullptr) {
494  global_thread_block_list.release_entry(control_block);
495  control_block = nullptr;
496  }
497  }
498 
499  HE alloc_hazard_era(era_t era)
500  {
501  ensure_has_control_block();
502  return control_block->alloc_hazard_era(hint, era);
503  }
504 
505  void release_hazard_era(HE& he)
506  {
507  if (he) {
508  assert(control_block != nullptr);
509  control_block->release_hazard_era(he, hint);
510  }
511  }
512 
513  std::size_t add_retired_node(detail::deletable_object_with_eras* p)
514  {
515  p->next = retire_list;
516  retire_list = p;
517  return ++number_of_retired_nodes;
518  }
519 
520  void scan()
521  {
522  std::vector<era_t> protected_eras;
523  protected_eras.reserve(allocation_strategy::number_of_active_hazard_eras());
524 
525  // (9) - this seq_cst-fence enforces a total order with the seq_cst-fence (5)
526  std::atomic_thread_fence(std::memory_order_seq_cst);
527 
528  auto adopted_nodes = global_thread_block_list.adopt_abandoned_retired_nodes();
529 
530  std::for_each(global_thread_block_list.begin(), global_thread_block_list.end(),
531  [&protected_eras](const auto& entry)
532  {
533  // TSan does not support explicit fences, so we cannot rely on the acquire-fence (10)
534  // but have to perform an acquire-load here to avoid false positives.
535  constexpr auto memory_order = TSAN_MEMORY_ORDER(std::memory_order_acquire, std::memory_order_relaxed);
536  if (entry.is_active(memory_order))
537  entry.gather_protected_eras(protected_eras);
538  });
539 
540  // (10) - this acquire-fence synchronizes-with the release-store (4, 6)
541  std::atomic_thread_fence(std::memory_order_acquire);
542 
543  std::sort(protected_eras.begin(), protected_eras.end());
544  auto last = std::unique(protected_eras.begin(), protected_eras.end());
545  protected_eras.erase(last, protected_eras.end());
546 
547  auto list = retire_list;
548  retire_list = nullptr;
549  number_of_retired_nodes = 0;
550  reclaim_nodes(list, protected_eras);
551  reclaim_nodes(adopted_nodes, protected_eras);
552  }
553 
554  private:
555  void ensure_has_control_block()
556  {
557  if (control_block == nullptr)
558  {
559  control_block = global_thread_block_list.acquire_inactive_entry();
560  control_block->initialize(hint);
561  control_block->activate();
562  }
563  }
564 
565  void reclaim_nodes(detail::deletable_object_with_eras* list,
566  const std::vector<era_t>& protected_eras)
567  {
568  while (list != nullptr)
569  {
570  auto cur = list;
571  list = list->next;
572 
573  auto era_it = std::lower_bound(protected_eras.begin(), protected_eras.end(), cur->construction_era);
574  if (era_it == protected_eras.end() || *era_it > cur->retirement_era)
575  cur->delete_self();
576  else
577  add_retired_node(cur);
578  }
579  }
580 
581  detail::deletable_object_with_eras* retire_list = nullptr;
582  std::size_t number_of_retired_nodes = 0;
583  typename thread_control_block::hint hint;
584 
585  thread_control_block* control_block = nullptr;
586 
587  friend class hazard_eras;
588  ALLOCATION_COUNTER(hazard_eras);
589  };
590 
591  template <class Traits>
592  inline typename hazard_eras<Traits>::thread_data& hazard_eras<Traits>::local_thread_data()
593  {
594  // workaround for a Clang-8 issue that causes multiple re-initializations of thread_local variables
595  static thread_local thread_data local_thread_data;
596  return local_thread_data;
597  }
598 
599 #ifdef TRACK_ALLOCATIONS
600  template <class Traits>
601  inline void hazard_eras<Traits>::count_allocation()
602  { local_thread_data().allocation_counter.count_allocation(); }
603 
604  template <class Traits>
605  inline void hazard_eras<Traits>::count_reclamation()
606  { local_thread_data().allocation_counter.count_reclamation(); }
607 #endif
608 }}
609 
610 #ifdef _MSC_VER
611 #pragma warning(pop)
612 #endif
xenium::marked_ptr
A pointer with an embedded mark/tag value.
Definition: marked_ptr.hpp:41