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>
20 #pragma warning(disable: 4324)
23 namespace xenium {
namespace reclamation {
25 struct stamp_it::thread_control_block :
26 aligned_object<thread_control_block, 1 << MarkBits>,
27 detail::thread_block_list<thread_control_block>::entry
29 using concurrent_ptr = std::atomic<marked_ptr<thread_control_block, MarkBits>>;
34 std::atomic<stamp_t> stamp;
36 #ifdef WITH_PERF_COUNTER
37 performance_counters counters;
38 friend class thread_order_queue;
42 class stamp_it::thread_order_queue
45 using marked_ptr = xenium::marked_ptr<thread_control_block, MarkBits>;
46 using concurrent_ptr = std::atomic<marked_ptr>;
50 head = new thread_control_block();
51 tail = new thread_control_block();
52 tail->next.store(head, std::memory_order_relaxed);
53 tail->stamp.store(StampInc, std::memory_order_relaxed);
54 head->prev.store(tail, std::memory_order_relaxed);
55 head->stamp.store(StampInc, std::memory_order_relaxed);
58 void push(thread_control_block* block)
60 INC_PERF_CNT(block->counters.push_calls);
61 PERF_COUNTER(iterations, block->counters.push_iterations)
64 block->next.store(make_clean_marked(head, block->next), std::memory_order_release);
66 marked_ptr head_prev = head->prev.load(std::memory_order_relaxed);
73 assert((head_prev.mark() & DeleteMark) == 0 &&
"head must never be marked");
74 marked_ptr head_prev2 = head->prev.load(std::memory_order_relaxed);
75 if (head_prev != head_prev2)
77 head_prev = head_prev2;
84 stamp = head->stamp.fetch_add(StampInc, std::memory_order_seq_cst);
85 auto pending_stamp = stamp - (StampInc - PendingPush);
86 assert((pending_stamp & PendingPush) && !(pending_stamp & NotInList));
91 block->stamp.store(pending_stamp, std::memory_order_release);
93 if (head->prev.load(std::memory_order_relaxed) != head_prev)
96 my_prev = make_clean_marked(head_prev.get(), block->prev);
99 block->prev.store(my_prev, std::memory_order_release);
104 if (head->prev.compare_exchange_weak(head_prev, make_marked(block, head_prev),
105 std::memory_order_acq_rel,
106 std::memory_order_relaxed))
113 block->stamp.store(stamp, std::memory_order_release);
117 auto link = my_prev->next.load(std::memory_order_acquire);
120 if (link.get() == block ||
121 link.mark() & DeleteMark ||
122 block->prev.load(std::memory_order_relaxed) != my_prev)
125 assert(link.get() != tail);
130 if (my_prev->next.compare_exchange_weak(link, make_marked(block, link),
131 std::memory_order_release,
132 std::memory_order_acquire))
138 bool remove(marked_ptr block)
140 INC_PERF_CNT(block->counters.remove_calls);
152 marked_ptr prev = set_mark_flag(block->prev, std::memory_order_acq_rel);
153 marked_ptr next = set_mark_flag(block->next, std::memory_order_relaxed);
155 bool fully_removed = remove_from_prev_list(prev, block, next);
157 remove_from_next_list(prev, block, next);
159 auto stamp = block->stamp.load(std::memory_order_relaxed);
160 assert((stamp & (PendingPush | NotInList)) == 0);
162 block->stamp.store(stamp + NotInList, std::memory_order_relaxed);
164 bool wasTail = block->prev.load(std::memory_order_relaxed).get() == tail;
169 update_tail_stamp(stamp + StampInc);
175 void add_to_global_retired_nodes(deletable_object_with_stamp* chunk)
177 add_to_global_retired_nodes(chunk, chunk);
180 void add_to_global_retired_nodes(deletable_object_with_stamp* first_chunk, deletable_object_with_stamp* last_chunk)
182 assert(first_chunk !=
nullptr && last_chunk !=
nullptr);
183 auto n = global_retired_nodes.load(std::memory_order_relaxed);
186 last_chunk->next_chunk = n;
188 }
while (!global_retired_nodes.compare_exchange_weak(n, first_chunk,
189 std::memory_order_release,
190 std::memory_order_relaxed));
193 deletable_object_with_stamp* steal_global_retired_nodes()
195 if (global_retired_nodes.load(std::memory_order_relaxed) !=
nullptr)
197 return global_retired_nodes.exchange(
nullptr, std::memory_order_acquire);
201 stamp_t head_stamp() {
203 return head->stamp.load(std::memory_order_seq_cst);
205 stamp_t tail_stamp() {
207 return tail->stamp.load(std::memory_order_acquire);
210 thread_control_block* acquire_control_block()
212 return global_thread_block_list.acquire_entry();
216 static const unsigned DeleteMark = 1;
217 static const unsigned TagInc = 2;
218 static const unsigned MarkMask = (1 << MarkBits) - 1;
220 marked_ptr make_marked(thread_control_block* p,
const marked_ptr& mark)
222 return marked_ptr(p, (mark.mark() + TagInc) & MarkMask);
225 marked_ptr make_clean_marked(thread_control_block* p,
const concurrent_ptr& mark)
227 auto m = mark.load(std::memory_order_relaxed);
228 return marked_ptr(p, (m.mark() + TagInc) & MarkMask & ~DeleteMark);
231 void update_tail_stamp(
size_t stamp)
239 auto last = tail->next.load(std::memory_order_acquire);
241 auto last_prev = last->prev.load(std::memory_order_acquire);
242 auto last_stamp = last->stamp.load(std::memory_order_relaxed);
243 if (last_stamp > stamp &&
244 last_prev.get() == tail &&
245 tail->next.load(std::memory_order_relaxed) == last)
247 assert((last_stamp & PendingPush) == 0);
248 assert((last_stamp & NotInList) == 0);
249 assert(last_stamp >= stamp);
250 if (last.get() != head)
261 if (stamp < last_stamp - StampInc &&
262 head->prev.compare_exchange_strong(last_prev, make_marked(last_prev.get(), last_prev),
263 std::memory_order_relaxed))
269 auto tail_stamp = tail->stamp.load(std::memory_order_relaxed);
270 while (tail_stamp < stamp)
273 if (tail->stamp.compare_exchange_weak(tail_stamp, stamp, std::memory_order_release))
278 bool remove_from_prev_list(marked_ptr& prev, marked_ptr b, marked_ptr& next)
280 PERF_COUNTER(iterations, b->counters.remove_prev_iterations);
282 const auto my_stamp = b->stamp.load(std::memory_order_relaxed);
283 marked_ptr last =
nullptr;
289 if (next.get() == prev.get())
291 next = b->next.load(std::memory_order_relaxed);
295 auto prev_prev = prev->prev.load(std::memory_order_relaxed);
296 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
299 if (prev_stamp > my_stamp ||
300 prev_stamp & NotInList)
305 if (prev_prev.mark() & DeleteMark)
307 if (!mark_next(prev, prev_stamp))
318 prev = prev->prev.load(std::memory_order_acquire);
329 auto next_prev = next->prev.load(std::memory_order_acquire);
331 auto next_stamp = next->stamp.load(std::memory_order_acquire);
333 if (next_prev != next->prev.load(std::memory_order_relaxed))
336 if (next_stamp < my_stamp)
338 next = b->next.load(std::memory_order_relaxed);
348 if (next_stamp & (NotInList | PendingPush))
350 if (last.get() !=
nullptr)
357 next = next->next.load(std::memory_order_acquire);
361 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
365 if (next_prev.get() != b.get())
367 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
373 if (next->prev.compare_exchange_strong(next_prev, make_marked(prev.get(), next_prev),
374 std::memory_order_release,
375 std::memory_order_relaxed))
382 void remove_from_next_list(marked_ptr prev, marked_ptr removed, marked_ptr next)
384 PERF_COUNTER(iterations, removed->counters.remove_next_iterations);
386 const auto my_stamp = removed->stamp.load(std::memory_order_relaxed);
388 marked_ptr last =
nullptr;
399 auto next_prev = next->prev.load(std::memory_order_acquire);
401 auto next_stamp = next->stamp.load(std::memory_order_acquire);
403 if (next_prev != next->prev.load(std::memory_order_relaxed))
407 if (next_stamp & (NotInList | PendingPush))
409 if (last.get() !=
nullptr)
417 next = next->next.load(std::memory_order_acquire);
423 auto prev_next = prev->next.load(std::memory_order_acquire);
424 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
426 assert(prev.get() != removed.get() || prev_stamp > my_stamp);
429 if (prev_stamp > my_stamp || prev_stamp & NotInList)
436 if (prev_next.mark() & DeleteMark)
441 prev = prev->prev.load(std::memory_order_acquire);
445 if (next.get() == prev.get())
448 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
452 if (next_prev.get() != prev.get())
454 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
458 if (next_stamp <= my_stamp || prev_next.get() == next.get())
461 auto new_next = make_marked(next.get(), prev_next);
462 if (next->prev.load(std::memory_order_relaxed) == next_prev &&
464 prev->next.compare_exchange_weak(prev_next, new_next,
465 std::memory_order_release,
466 std::memory_order_relaxed))
468 if ((next->next.load(std::memory_order_relaxed).mark() & DeleteMark) == 0)
475 bool remove_or_skip_marked_block(marked_ptr &next, marked_ptr &last,
476 marked_ptr next_prev, stamp_t next_stamp)
479 if (next_prev.mark() & DeleteMark)
481 if (last.get() !=
nullptr)
484 assert((next.mark() & DeleteMark) == 0);
485 if (mark_next(next, next_stamp) &&
486 last->prev.load(std::memory_order_relaxed) == next)
490 last->prev.compare_exchange_strong(next, make_marked(next_prev.get(), next),
491 std::memory_order_release,
492 std::memory_order_relaxed);
499 next = next->next.load(std::memory_order_acquire);
506 void save_next_as_last_and_move_next_to_next_prev(
507 marked_ptr next_prev, marked_ptr& next, marked_ptr& last)
510 size_t next_prev_stamp = next_prev->stamp.load(std::memory_order_acquire);
512 if (next_prev_stamp & PendingPush && next_prev == next->prev.load(std::memory_order_relaxed))
514 assert((next_prev_stamp & NotInList) == 0);
518 auto expected = next_prev_stamp;
519 const auto new_stamp = next_prev_stamp + (StampInc - PendingPush);
520 if (!next_prev->stamp.compare_exchange_strong(expected, new_stamp, std::memory_order_relaxed))
525 if (expected != new_stamp)
537 marked_ptr set_mark_flag(concurrent_ptr& ptr, std::memory_order order)
539 auto link = ptr.load(std::memory_order_relaxed);
542 if (link.mark() & DeleteMark ||
543 ptr.compare_exchange_weak(link, marked_ptr(link.get(), link.mark() | DeleteMark),
544 order, std::memory_order_relaxed))
550 bool mark_next(marked_ptr block,
size_t stamp)
552 assert((stamp & (NotInList | PendingPush)) == 0);
554 auto link = block->next.load(std::memory_order_acquire);
558 while (block->stamp.load(std::memory_order_relaxed) == stamp)
560 auto mark = link.mark();
561 if (mark & DeleteMark ||
563 block->next.compare_exchange_weak(link,
564 marked_ptr(link.get(), mark | DeleteMark),
565 std::memory_order_relaxed,
566 std::memory_order_acquire))
578 thread_control_block* head;
579 thread_control_block* tail;
581 alignas(64) std::atomic<deletable_object_with_stamp*> global_retired_nodes{
nullptr};
582 alignas(64) detail::thread_block_list<thread_control_block> global_thread_block_list{};
583 friend class stamp_it;
586 struct stamp_it::thread_data
590 assert(region_entries == 0);
591 if (control_block ==
nullptr)
594 control_block->abandon();
595 control_block =
nullptr;
598 process_local_nodes();
599 if (first_retired_node)
603 queue.add_to_global_retired_nodes(first_retired_node);
609 if (++region_entries == 1)
611 ensure_has_control_block();
612 queue.push(control_block);
618 if (--region_entries == 0)
620 auto wasLast = queue.remove(control_block);
623 process_global_nodes();
626 process_local_nodes();
627 if (number_of_retired_nodes > max_remaining_retired_nodes)
629 queue.add_to_global_retired_nodes(first_retired_node);
630 first_retired_node =
nullptr;
631 prev_retired_node = &first_retired_node;
632 number_of_retired_nodes = 0;
638 void add_retired_node(deletable_object_with_stamp* p)
640 p->stamp = queue.head_stamp();
641 *prev_retired_node = p;
642 prev_retired_node = &p->next;
644 ++number_of_retired_nodes;
645 if (number_of_retired_nodes > try_reclaim_threshold)
646 process_local_nodes();
650 void ensure_has_control_block()
652 if (control_block ==
nullptr)
654 control_block = queue.acquire_control_block();
655 #ifdef WITH_PERF_COUNTER
656 control_block->counters = performance_counters{};
661 void process_local_nodes()
663 auto tail_stamp = queue.tail_stamp();
665 auto cur = first_retired_node;
666 for (deletable_object_with_stamp* next =
nullptr; cur !=
nullptr; cur = next)
669 if (cur->stamp <= tail_stamp)
678 first_retired_node = cur;
680 prev_retired_node = &first_retired_node;
681 number_of_retired_nodes -= cnt;
684 void process_global_nodes()
686 auto tail_stamp = queue.tail_stamp();
687 auto cur_chunk = queue.steal_global_retired_nodes();
689 if (first_retired_node !=
nullptr)
691 first_retired_node->next_chunk = cur_chunk;
692 cur_chunk = first_retired_node;
693 first_retired_node =
nullptr;
694 prev_retired_node = &first_retired_node;
695 number_of_retired_nodes = 0;
697 if (cur_chunk ==
nullptr)
700 stamp_t lowest_stamp;
701 auto process_chunk_nodes = [tail_stamp, &lowest_stamp](deletable_object_with_stamp* chunk)
706 if (cur->stamp <= tail_stamp)
708 lowest_stamp = std::min(lowest_stamp, cur->stamp);
709 auto next = cur->next;
720 lowest_stamp = std::numeric_limits<stamp_t>::max();
721 deletable_object_with_stamp* first_remaining_chunk =
nullptr;
722 deletable_object_with_stamp* last_remaining_chunk =
nullptr;
723 deletable_object_with_stamp** prev_remaining_chunk = &first_remaining_chunk;
726 auto next_chunk = cur_chunk->next_chunk;
727 auto remaining_chunk = process_chunk_nodes(cur_chunk);
730 *prev_remaining_chunk = remaining_chunk;
731 last_remaining_chunk = remaining_chunk;
732 prev_remaining_chunk = &remaining_chunk->next_chunk;
734 cur_chunk = next_chunk;
737 *prev_remaining_chunk =
nullptr;
738 if (first_remaining_chunk)
740 auto new_tail_stamp = queue.tail_stamp();
741 if (lowest_stamp < new_tail_stamp)
743 cur_chunk = first_remaining_chunk;
744 tail_stamp = new_tail_stamp;
749 assert(last_remaining_chunk !=
nullptr);
750 queue.add_to_global_retired_nodes(first_remaining_chunk, last_remaining_chunk);
758 static const std::size_t try_reclaim_threshold = 40;
762 static const std::size_t max_remaining_retired_nodes = 20;
764 thread_control_block* control_block =
nullptr;
765 unsigned region_entries = 0;
766 std::size_t number_of_retired_nodes = 0;
768 deletable_object_with_stamp* first_retired_node =
nullptr;
769 deletable_object_with_stamp** prev_retired_node = &first_retired_node;
771 friend class stamp_it;
772 ALLOCATION_COUNTER(stamp_it);
775 inline stamp_it::region_guard::region_guard() noexcept
777 local_thread_data().enter_region();
780 inline stamp_it::region_guard::~region_guard()
782 local_thread_data().leave_region();
785 template <
class T,
class MarkedPtr>
786 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(
const MarkedPtr& p) noexcept :
790 local_thread_data().enter_region();
793 template <
class T,
class MarkedPtr>
794 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(
const guard_ptr& p) noexcept :
795 guard_ptr(MarkedPtr(p))
798 template <
class T,
class MarkedPtr>
799 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(guard_ptr&& p) noexcept :
805 template <
class T,
class MarkedPtr>
806 typename stamp_it::guard_ptr<T, MarkedPtr>&
807 stamp_it::guard_ptr<T, MarkedPtr>::operator=(
const guard_ptr& p) noexcept
815 local_thread_data().enter_region();
820 template <
class T,
class MarkedPtr>
821 typename stamp_it::guard_ptr<T, MarkedPtr>&
822 stamp_it::guard_ptr<T, MarkedPtr>::operator=(guard_ptr&& p) noexcept
828 this->ptr = std::move(p.ptr);
834 template <
class T,
class MarkedPtr>
835 void stamp_it::guard_ptr<T, MarkedPtr>::acquire(
const concurrent_ptr<T>& p,
836 std::memory_order order) noexcept
838 if (p.load(std::memory_order_relaxed) ==
nullptr)
845 local_thread_data().enter_region();
846 this->ptr = p.load(order);
848 local_thread_data().leave_region();
851 template <
class T,
class MarkedPtr>
852 bool stamp_it::guard_ptr<T, MarkedPtr>::acquire_if_equal(
853 const concurrent_ptr<T>& p,
const MarkedPtr& expected, std::memory_order order) noexcept
855 auto actual = p.load(std::memory_order_relaxed);
856 if (actual ==
nullptr || actual != expected)
859 return actual == expected;
863 local_thread_data().enter_region();
864 this->ptr = p.load(order);
865 if (!this->ptr || this->ptr != expected)
867 local_thread_data().leave_region();
871 return this->ptr == expected;
874 template <
class T,
class MarkedPtr>
875 void stamp_it::guard_ptr<T, MarkedPtr>::reset() noexcept
878 local_thread_data().leave_region();
882 template <
class T,
class MarkedPtr>
883 void stamp_it::guard_ptr<T, MarkedPtr>::reclaim(Deleter d) noexcept
885 this->ptr->set_deleter(std::move(d));
886 local_thread_data().add_retired_node(this->ptr.get());
890 inline stamp_it::thread_data& stamp_it::local_thread_data()
893 static thread_local thread_data local_thread_data;
894 return local_thread_data;
898 __declspec(selectany) stamp_it::thread_order_queue stamp_it::queue;
900 inline stamp_it::thread_order_queue stamp_it::queue;
903 #ifdef WITH_PERF_COUNTER
904 inline stamp_it::performance_counters stamp_it::get_performance_counters()
906 performance_counters result{};
907 std::for_each(queue.global_thread_block_list.begin(),
908 queue.global_thread_block_list.end(),
909 [&result](
const auto& block)
911 result.push_calls += block.counters.push_calls;
912 result.push_iterations += block.counters.push_iterations;
913 result.remove_calls += block.counters.remove_calls;
914 result.remove_prev_iterations += block.counters.remove_prev_iterations;
915 result.remove_next_iterations += block.counters.remove_next_iterations;
922 #ifdef TRACK_ALLOCATIONS
923 inline void stamp_it::count_allocation()
924 { local_thread_data().allocation_counter.count_allocation(); }
926 inline void stamp_it::count_reclamation()
927 { local_thread_data().allocation_counter.count_reclamation(); }