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
23namespace 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
A pointer with an embedded mark/tag value.
Definition: marked_ptr.hpp:41