7 #error "This is an impl file and must not be included directly!"
10 #include <xenium/aligned_object.hpp>
11 #include <xenium/reclamation/detail/perf_counter.hpp>
12 #include <xenium/detail/port.hpp>
13 #include <xenium/reclamation/detail/thread_block_list.hpp>
19 #pragma warning(disable: 4324)
22 namespace xenium {
namespace reclamation {
24 struct stamp_it::thread_control_block :
25 aligned_object<thread_control_block, 1 << MarkBits>,
26 detail::thread_block_list<thread_control_block>::entry
28 using concurrent_ptr = std::atomic<marked_ptr<thread_control_block, MarkBits>>;
33 std::atomic<stamp_t> stamp;
35 #ifdef WITH_PERF_COUNTER
36 performance_counters counters;
37 friend class thread_order_queue;
41 class stamp_it::thread_order_queue
44 using marked_ptr = xenium::marked_ptr<thread_control_block, MarkBits>;
45 using concurrent_ptr = std::atomic<marked_ptr>;
49 head = new thread_control_block();
50 tail = new thread_control_block();
51 tail->next.store(head, std::memory_order_relaxed);
52 tail->stamp.store(StampInc, std::memory_order_relaxed);
53 head->prev.store(tail, std::memory_order_relaxed);
54 head->stamp.store(StampInc, std::memory_order_relaxed);
57 void push(thread_control_block* block)
59 INC_PERF_CNT(block->counters.push_calls);
60 PERF_COUNTER(iterations, block->counters.push_iterations)
63 block->next.store(make_clean_marked(head, block->next), std::memory_order_release);
65 marked_ptr head_prev = head->prev.load(std::memory_order_relaxed);
72 assert((head_prev.mark() & DeleteMark) == 0 &&
"head must never be marked");
73 marked_ptr head_prev2 = head->prev.load(std::memory_order_relaxed);
74 if (head_prev != head_prev2)
76 head_prev = head_prev2;
83 stamp = head->stamp.fetch_add(StampInc, std::memory_order_seq_cst);
84 auto pending_stamp = stamp - (StampInc - PendingPush);
85 assert((pending_stamp & PendingPush) && !(pending_stamp & NotInList));
90 block->stamp.store(pending_stamp, std::memory_order_release);
92 if (head->prev.load(std::memory_order_relaxed) != head_prev)
95 my_prev = make_clean_marked(head_prev.get(), block->prev);
98 block->prev.store(my_prev, std::memory_order_release);
103 if (head->prev.compare_exchange_weak(head_prev, make_marked(block, head_prev),
104 std::memory_order_acq_rel,
105 std::memory_order_relaxed))
112 block->stamp.store(stamp, std::memory_order_release);
116 auto link = my_prev->next.load(std::memory_order_acquire);
119 if (link.get() == block ||
120 link.mark() & DeleteMark ||
121 block->prev.load(std::memory_order_relaxed) != my_prev)
124 assert(link.get() != tail);
129 if (my_prev->next.compare_exchange_weak(link, make_marked(block, link),
130 std::memory_order_release,
131 std::memory_order_acquire))
137 bool remove(marked_ptr block)
139 INC_PERF_CNT(block->counters.remove_calls);
151 marked_ptr prev = set_mark_flag(block->prev, std::memory_order_acq_rel);
152 marked_ptr next = set_mark_flag(block->next, std::memory_order_relaxed);
154 bool fully_removed = remove_from_prev_list(prev, block, next);
156 remove_from_next_list(prev, block, next);
158 auto stamp = block->stamp.load(std::memory_order_relaxed);
159 assert((stamp & (PendingPush | NotInList)) == 0);
161 block->stamp.store(stamp + NotInList, std::memory_order_relaxed);
163 bool wasTail = block->prev.load(std::memory_order_relaxed).get() == tail;
168 update_tail_stamp(stamp + StampInc);
174 void add_to_global_retired_nodes(deletable_object_with_stamp* chunk)
176 add_to_global_retired_nodes(chunk, chunk);
179 void add_to_global_retired_nodes(deletable_object_with_stamp* first_chunk, deletable_object_with_stamp* last_chunk)
181 assert(first_chunk !=
nullptr && last_chunk !=
nullptr);
182 auto n = global_retired_nodes.load(std::memory_order_relaxed);
185 last_chunk->next_chunk = n;
187 }
while (!global_retired_nodes.compare_exchange_weak(n, first_chunk,
188 std::memory_order_release,
189 std::memory_order_relaxed));
192 deletable_object_with_stamp* steal_global_retired_nodes()
194 if (global_retired_nodes.load(std::memory_order_relaxed) !=
nullptr)
196 return global_retired_nodes.exchange(
nullptr, std::memory_order_acquire);
200 stamp_t head_stamp() {
202 return head->stamp.load(std::memory_order_seq_cst);
204 stamp_t tail_stamp() {
206 return tail->stamp.load(std::memory_order_acquire);
209 thread_control_block* acquire_control_block()
211 return global_thread_block_list.acquire_entry();
215 static const unsigned DeleteMark = 1;
216 static const unsigned TagInc = 2;
217 static const unsigned MarkMask = (1 << MarkBits) - 1;
219 marked_ptr make_marked(thread_control_block* p,
const marked_ptr& mark)
221 return marked_ptr(p, (mark.mark() + TagInc) & MarkMask);
224 marked_ptr make_clean_marked(thread_control_block* p,
const concurrent_ptr& mark)
226 auto m = mark.load(std::memory_order_relaxed);
227 return marked_ptr(p, (m.mark() + TagInc) & MarkMask & ~DeleteMark);
230 void update_tail_stamp(
size_t stamp)
238 auto last = tail->next.load(std::memory_order_acquire);
240 auto last_prev = last->prev.load(std::memory_order_acquire);
241 auto last_stamp = last->stamp.load(std::memory_order_relaxed);
242 if (last_stamp > stamp &&
243 last_prev.get() == tail &&
244 tail->next.load(std::memory_order_relaxed) == last)
246 assert((last_stamp & PendingPush) == 0);
247 assert((last_stamp & NotInList) == 0);
248 assert(last_stamp >= stamp);
249 if (last.get() != head)
260 if (stamp < last_stamp - StampInc &&
261 head->prev.compare_exchange_strong(last_prev, make_marked(last_prev.get(), last_prev),
262 std::memory_order_relaxed))
268 auto tail_stamp = tail->stamp.load(std::memory_order_relaxed);
269 while (tail_stamp < stamp)
272 if (tail->stamp.compare_exchange_weak(tail_stamp, stamp, std::memory_order_release))
277 bool remove_from_prev_list(marked_ptr& prev, marked_ptr b, marked_ptr& next)
279 PERF_COUNTER(iterations, b->counters.remove_prev_iterations);
281 const auto my_stamp = b->stamp.load(std::memory_order_relaxed);
282 marked_ptr last =
nullptr;
288 if (next.get() == prev.get())
290 next = b->next.load(std::memory_order_relaxed);
294 auto prev_prev = prev->prev.load(std::memory_order_relaxed);
295 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
298 if (prev_stamp > my_stamp ||
299 prev_stamp & NotInList)
304 if (prev_prev.mark() & DeleteMark)
306 if (!mark_next(prev, prev_stamp))
317 prev = prev->prev.load(std::memory_order_acquire);
328 auto next_prev = next->prev.load(std::memory_order_acquire);
330 auto next_stamp = next->stamp.load(std::memory_order_acquire);
332 if (next_prev != next->prev.load(std::memory_order_relaxed))
335 if (next_stamp < my_stamp)
337 next = b->next.load(std::memory_order_relaxed);
347 if (next_stamp & (NotInList | PendingPush))
349 if (last.get() !=
nullptr)
356 next = next->next.load(std::memory_order_acquire);
360 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
364 if (next_prev.get() != b.get())
366 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
372 if (next->prev.compare_exchange_strong(next_prev, make_marked(prev.get(), next_prev),
373 std::memory_order_release,
374 std::memory_order_relaxed))
381 void remove_from_next_list(marked_ptr prev, marked_ptr removed, marked_ptr next)
383 PERF_COUNTER(iterations, removed->counters.remove_next_iterations);
385 const auto my_stamp = removed->stamp.load(std::memory_order_relaxed);
387 marked_ptr last =
nullptr;
398 auto next_prev = next->prev.load(std::memory_order_acquire);
400 auto next_stamp = next->stamp.load(std::memory_order_acquire);
402 if (next_prev != next->prev.load(std::memory_order_relaxed))
406 if (next_stamp & (NotInList | PendingPush))
408 if (last.get() !=
nullptr)
416 next = next->next.load(std::memory_order_acquire);
422 auto prev_next = prev->next.load(std::memory_order_acquire);
423 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
425 assert(prev.get() != removed.get() || prev_stamp > my_stamp);
428 if (prev_stamp > my_stamp || prev_stamp & NotInList)
435 if (prev_next.mark() & DeleteMark)
440 prev = prev->prev.load(std::memory_order_acquire);
444 if (next.get() == prev.get())
447 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
451 if (next_prev.get() != prev.get())
453 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
457 if (next_stamp <= my_stamp || prev_next.get() == next.get())
460 auto new_next = make_marked(next.get(), prev_next);
461 if (next->prev.load(std::memory_order_relaxed) == next_prev &&
463 prev->next.compare_exchange_weak(prev_next, new_next,
464 std::memory_order_release,
465 std::memory_order_relaxed))
467 if ((next->next.load(std::memory_order_relaxed).mark() & DeleteMark) == 0)
474 bool remove_or_skip_marked_block(marked_ptr &next, marked_ptr &last,
475 marked_ptr next_prev, stamp_t next_stamp)
478 if (next_prev.mark() & DeleteMark)
480 if (last.get() !=
nullptr)
483 assert((next.mark() & DeleteMark) == 0);
484 if (mark_next(next, next_stamp) &&
485 last->prev.load(std::memory_order_relaxed) == next)
489 last->prev.compare_exchange_strong(next, make_marked(next_prev.get(), next),
490 std::memory_order_release,
491 std::memory_order_relaxed);
498 next = next->next.load(std::memory_order_acquire);
505 void save_next_as_last_and_move_next_to_next_prev(
506 marked_ptr next_prev, marked_ptr& next, marked_ptr& last)
509 size_t next_prev_stamp = next_prev->stamp.load(std::memory_order_acquire);
511 if (next_prev_stamp & PendingPush && next_prev == next->prev.load(std::memory_order_relaxed))
513 assert((next_prev_stamp & NotInList) == 0);
517 auto expected = next_prev_stamp;
518 const auto new_stamp = next_prev_stamp + (StampInc - PendingPush);
519 if (!next_prev->stamp.compare_exchange_strong(expected, new_stamp, std::memory_order_relaxed))
524 if (expected != new_stamp)
536 marked_ptr set_mark_flag(concurrent_ptr& ptr, std::memory_order order)
538 auto link = ptr.load(std::memory_order_relaxed);
541 if (link.mark() & DeleteMark ||
542 ptr.compare_exchange_weak(link, marked_ptr(link.get(), link.mark() | DeleteMark),
543 order, std::memory_order_relaxed))
549 bool mark_next(marked_ptr block,
size_t stamp)
551 assert((stamp & (NotInList | PendingPush)) == 0);
553 auto link = block->next.load(std::memory_order_acquire);
557 while (block->stamp.load(std::memory_order_relaxed) == stamp)
559 auto mark = link.mark();
560 if (mark & DeleteMark ||
562 block->next.compare_exchange_weak(link,
563 marked_ptr(link.get(), mark | DeleteMark),
564 std::memory_order_relaxed,
565 std::memory_order_acquire))
577 thread_control_block* head;
578 thread_control_block* tail;
580 alignas(64) std::atomic<deletable_object_with_stamp*> global_retired_nodes{
nullptr};
581 alignas(64) detail::thread_block_list<thread_control_block> global_thread_block_list{};
582 friend class stamp_it;
585 struct stamp_it::thread_data
589 assert(region_entries == 0);
590 if (control_block ==
nullptr)
593 control_block->abandon();
594 control_block =
nullptr;
597 process_local_nodes();
598 if (first_retired_node)
602 queue.add_to_global_retired_nodes(first_retired_node);
608 if (++region_entries == 1)
610 ensure_has_control_block();
611 queue.push(control_block);
617 if (--region_entries == 0)
619 auto wasLast = queue.remove(control_block);
622 process_global_nodes();
625 process_local_nodes();
626 if (number_of_retired_nodes > max_remaining_retired_nodes)
628 queue.add_to_global_retired_nodes(first_retired_node);
629 first_retired_node =
nullptr;
630 prev_retired_node = &first_retired_node;
631 number_of_retired_nodes = 0;
637 void add_retired_node(deletable_object_with_stamp* p)
639 p->stamp = queue.head_stamp();
640 *prev_retired_node = p;
641 prev_retired_node = &p->next;
643 ++number_of_retired_nodes;
644 if (number_of_retired_nodes > try_reclaim_threshold)
645 process_local_nodes();
649 void ensure_has_control_block()
651 if (control_block ==
nullptr)
653 control_block = queue.acquire_control_block();
654 #ifdef WITH_PERF_COUNTER
655 control_block->counters = performance_counters{};
660 void process_local_nodes()
662 auto tail_stamp = queue.tail_stamp();
664 auto cur = first_retired_node;
665 for (deletable_object_with_stamp* next =
nullptr; cur !=
nullptr; cur = next)
668 if (cur->stamp <= tail_stamp)
677 first_retired_node = cur;
679 prev_retired_node = &first_retired_node;
680 number_of_retired_nodes -= cnt;
683 void process_global_nodes()
685 auto tail_stamp = queue.tail_stamp();
686 auto cur_chunk = queue.steal_global_retired_nodes();
688 if (first_retired_node !=
nullptr)
690 first_retired_node->next_chunk = cur_chunk;
691 cur_chunk = first_retired_node;
692 first_retired_node =
nullptr;
693 prev_retired_node = &first_retired_node;
694 number_of_retired_nodes = 0;
696 if (cur_chunk ==
nullptr)
699 stamp_t lowest_stamp;
700 auto process_chunk_nodes = [tail_stamp, &lowest_stamp](deletable_object_with_stamp* chunk)
705 if (cur->stamp <= tail_stamp)
707 lowest_stamp = std::min(lowest_stamp, cur->stamp);
708 auto next = cur->next;
719 lowest_stamp = std::numeric_limits<stamp_t>::max();
720 deletable_object_with_stamp* first_remaining_chunk =
nullptr;
721 deletable_object_with_stamp* last_remaining_chunk =
nullptr;
722 deletable_object_with_stamp** prev_remaining_chunk = &first_remaining_chunk;
725 auto next_chunk = cur_chunk->next_chunk;
726 auto remaining_chunk = process_chunk_nodes(cur_chunk);
729 *prev_remaining_chunk = remaining_chunk;
730 last_remaining_chunk = remaining_chunk;
731 prev_remaining_chunk = &remaining_chunk->next_chunk;
733 cur_chunk = next_chunk;
736 *prev_remaining_chunk =
nullptr;
737 if (first_remaining_chunk)
739 auto new_tail_stamp = queue.tail_stamp();
740 if (lowest_stamp < new_tail_stamp)
742 cur_chunk = first_remaining_chunk;
743 tail_stamp = new_tail_stamp;
748 assert(last_remaining_chunk !=
nullptr);
749 queue.add_to_global_retired_nodes(first_remaining_chunk, last_remaining_chunk);
757 static const std::size_t try_reclaim_threshold = 40;
761 static const std::size_t max_remaining_retired_nodes = 20;
763 thread_control_block* control_block =
nullptr;
764 unsigned region_entries = 0;
765 std::size_t number_of_retired_nodes = 0;
767 deletable_object_with_stamp* first_retired_node =
nullptr;
768 deletable_object_with_stamp** prev_retired_node = &first_retired_node;
770 friend class stamp_it;
771 ALLOCATION_COUNTER(stamp_it);
774 inline stamp_it::region_guard::region_guard() noexcept
776 local_thread_data().enter_region();
779 inline stamp_it::region_guard::~region_guard()
781 local_thread_data().leave_region();
784 template <
class T,
class MarkedPtr>
785 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(
const MarkedPtr& p) noexcept :
789 local_thread_data().enter_region();
792 template <
class T,
class MarkedPtr>
793 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(
const guard_ptr& p) noexcept :
794 guard_ptr(MarkedPtr(p))
797 template <
class T,
class MarkedPtr>
798 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(guard_ptr&& p) noexcept :
804 template <
class T,
class MarkedPtr>
805 typename stamp_it::guard_ptr<T, MarkedPtr>&
806 stamp_it::guard_ptr<T, MarkedPtr>::operator=(
const guard_ptr& p) noexcept
814 local_thread_data().enter_region();
819 template <
class T,
class MarkedPtr>
820 typename stamp_it::guard_ptr<T, MarkedPtr>&
821 stamp_it::guard_ptr<T, MarkedPtr>::operator=(guard_ptr&& p) noexcept
827 this->ptr = std::move(p.ptr);
833 template <
class T,
class MarkedPtr>
834 void stamp_it::guard_ptr<T, MarkedPtr>::acquire(
const concurrent_ptr<T>& p,
835 std::memory_order order) noexcept
837 if (p.load(std::memory_order_relaxed) ==
nullptr)
844 local_thread_data().enter_region();
845 this->ptr = p.load(order);
847 local_thread_data().leave_region();
850 template <
class T,
class MarkedPtr>
851 bool stamp_it::guard_ptr<T, MarkedPtr>::acquire_if_equal(
852 const concurrent_ptr<T>& p,
const MarkedPtr& expected, std::memory_order order) noexcept
854 auto actual = p.load(std::memory_order_relaxed);
855 if (actual ==
nullptr || actual != expected)
858 return actual == expected;
862 local_thread_data().enter_region();
863 this->ptr = p.load(order);
864 if (!this->ptr || this->ptr != expected)
866 local_thread_data().leave_region();
870 return this->ptr == expected;
873 template <
class T,
class MarkedPtr>
874 void stamp_it::guard_ptr<T, MarkedPtr>::reset() noexcept
877 local_thread_data().leave_region();
881 template <
class T,
class MarkedPtr>
882 void stamp_it::guard_ptr<T, MarkedPtr>::reclaim(Deleter d) noexcept
884 this->ptr->set_deleter(std::move(d));
885 local_thread_data().add_retired_node(this->ptr.get());
889 inline stamp_it::thread_data& stamp_it::local_thread_data()
892 static thread_local thread_data local_thread_data;
893 return local_thread_data;
897 __declspec(selectany) stamp_it::thread_order_queue stamp_it::queue;
899 inline stamp_it::thread_order_queue stamp_it::queue;
902 #ifdef WITH_PERF_COUNTER
903 inline stamp_it::performance_counters stamp_it::get_performance_counters()
905 performance_counters result{};
906 std::for_each(queue.global_thread_block_list.begin(),
907 queue.global_thread_block_list.end(),
908 [&result](
const auto& block)
910 result.push_calls += block.counters.push_calls;
911 result.push_iterations += block.counters.push_iterations;
912 result.remove_calls += block.counters.remove_calls;
913 result.remove_prev_iterations += block.counters.remove_prev_iterations;
914 result.remove_next_iterations += block.counters.remove_next_iterations;
921 #ifdef TRACK_ALLOCATIONS
922 inline void stamp_it::count_allocation()
923 { local_thread_data().allocation_counter.count_allocation(); }
925 inline void stamp_it::count_reclamation()
926 { local_thread_data().allocation_counter.count_reclamation(); }