xenium
Loading...
Searching...
No Matches
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 STAMP_IT_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/reclamation/detail/perf_counter.hpp>
12#include <xenium/detail/port.hpp>
13#include <xenium/reclamation/detail/thread_block_list.hpp>
14
15#include <algorithm>
16#include <limits>
17
18#ifdef _MSC_VER
19#pragma warning(push)
20#pragma warning(disable: 4324) // structure was padded due to alignment specifier
21#endif
22
23namespace xenium { namespace reclamation {
24
25 struct stamp_it::thread_control_block :
26 aligned_object<thread_control_block, 1 << MarkBits>,
27 detail::thread_block_list<thread_control_block>::entry
28 {
29 using concurrent_ptr = std::atomic<marked_ptr<thread_control_block, MarkBits>>;
30
31 concurrent_ptr prev;
32 concurrent_ptr next;
33
34 std::atomic<stamp_t> stamp;
35
36#ifdef WITH_PERF_COUNTER
37 performance_counters counters;
38 friend class thread_order_queue;
39#endif
40 };
41
42 class stamp_it::thread_order_queue
43 {
44 public:
45 using marked_ptr = xenium::marked_ptr<thread_control_block, MarkBits>;
46 using concurrent_ptr = std::atomic<marked_ptr>;
47
48 thread_order_queue()
49 {
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);
56 }
57
58 void push(thread_control_block* block)
59 {
60 INC_PERF_CNT(block->counters.push_calls);
61 PERF_COUNTER(iterations, block->counters.push_iterations)
62
63 // (1) - this release-store synchronizes-with the acquire-loads (7, 8, 20, 24, 25, 29, 31, 32)
64 block->next.store(make_clean_marked(head, block->next), std::memory_order_release);
65
66 marked_ptr head_prev = head->prev.load(std::memory_order_relaxed);
67 marked_ptr my_prev;
68 size_t stamp;
69 for (;;)
70 {
71 iterations.inc();
72
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)
76 {
77 head_prev = head_prev2;
78 continue;
79 }
80
81 // fetch a new stamp and set the PendingPush flag
82 // (2) - this seq_cst-fetch-add enforces a total order with (12)
83 // and synchronizes-with the acquire-loads (19, 23)
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));
87
88 // We need release-semantic here to establish synchronize-with relation with
89 // the load in save_next_as_last_and_move_next_to_next_prev.
90 // (3) - this release-store synchronizes-with the acquire-loads (19, 23, 30)
91 block->stamp.store(pending_stamp, std::memory_order_release);
92
93 if (head->prev.load(std::memory_order_relaxed) != head_prev)
94 continue;
95
96 my_prev = make_clean_marked(head_prev.get(), block->prev);
97
98 // (4) - this release-store synchronizes-with the acquire-loads (15, 17, 18, 22, 26)
99 block->prev.store(my_prev, std::memory_order_release);
100
101 // (5) - in this acq_rel-CAS the:
102 // - acquire-load synchronizes-with the release-stores (5, 21, 28)
103 // - release-store synchronizes-with the acquire-loads (5, 15, 18, 22)
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))
107 break;
108 // Back-Off
109 }
110
111 // reset the PendingPush flag
112 // (6) - this release-store synchronizes-with the acquire-load (19, 23, 30)
113 block->stamp.store(stamp, std::memory_order_release);
114
115 // try to update our successor's next pointer
116 // (7) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
117 auto link = my_prev->next.load(std::memory_order_acquire);
118 for (;;)
119 {
120 if (link.get() == block ||
121 link.mark() & DeleteMark ||
122 block->prev.load(std::memory_order_relaxed) != my_prev)
123 break; // our successor is in the process of getting removed or has been removed already -> never mind
124
125 assert(link.get() != tail);
126
127 // (8) - in this CAS the:
128 // - release-store synchronizes-with the acquire-loads (7, 8, 14, 20, 24, 25, 29, 31, 32)
129 // - acquire-reload synchronizes-with the release-stores (1, 8, 27)
130 if (my_prev->next.compare_exchange_weak(link, make_marked(block, link),
131 std::memory_order_release,
132 std::memory_order_acquire))
133 break;
134 // Back-Off
135 }
136 }
137
138 bool remove(marked_ptr block)
139 {
140 INC_PERF_CNT(block->counters.remove_calls);
141
142 // We need acq-rel semantic here to ensure the happens-before relation
143 // between the remove operation and the reclamation of any node.
144 // - acquire to establish sychnronize-with relation with previous blocks
145 // that removed themselves by updating our prev.
146 // - release to establish synchronize-with relation with other threads
147 // that potentially remove our own block before we can do so.
148
149 // (9) - in this acq_rel CAS the:
150 // - acquire-load synchronizes-with the release-stores (21, 28)
151 // - release-store synchronizes-with the acquire-loads (15, 17, 18, 22, 26)
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);
154
155 bool fully_removed = remove_from_prev_list(prev, block, next);
156 if (!fully_removed)
157 remove_from_next_list(prev, block, next);
158
159 auto stamp = block->stamp.load(std::memory_order_relaxed);
160 assert((stamp & (PendingPush | NotInList)) == 0);
161 // set the NotInList flag to signal that this block is no longer part of the queue
162 block->stamp.store(stamp + NotInList, std::memory_order_relaxed);
163
164 bool wasTail = block->prev.load(std::memory_order_relaxed).get() == tail;
165 if (wasTail)
166 {
167 // since the stamps of the blocks between tail and head are strong monotonically increasing we can
168 // call update_tail_stamp with the next higher stamp (i.e., stamp + StampInc) as the 'next best guess'
169 update_tail_stamp(stamp + StampInc);
170 }
171
172 return wasTail;
173 }
174
175 void add_to_global_retired_nodes(deletable_object_with_stamp* chunk)
176 {
177 add_to_global_retired_nodes(chunk, chunk);
178 }
179
180 void add_to_global_retired_nodes(deletable_object_with_stamp* first_chunk, deletable_object_with_stamp* last_chunk)
181 {
182 assert(first_chunk != nullptr && last_chunk != nullptr);
183 auto n = global_retired_nodes.load(std::memory_order_relaxed);
184 do
185 {
186 last_chunk->next_chunk = n;
187 // (10) - this release-CAS synchronizes-with the acquire_xchg (11)
188 } while (!global_retired_nodes.compare_exchange_weak(n, first_chunk,
189 std::memory_order_release,
190 std::memory_order_relaxed));
191 }
192
193 deletable_object_with_stamp* steal_global_retired_nodes()
194 {
195 if (global_retired_nodes.load(std::memory_order_relaxed) != nullptr)
196 // (11) - this acquire-xchg synchronizes-with the release-CAS (10)
197 return global_retired_nodes.exchange(nullptr, std::memory_order_acquire);
198 return nullptr;
199 }
200
201 stamp_t head_stamp() {
202 // (12) - this seq-cst-load enforces a total order with (2)
203 return head->stamp.load(std::memory_order_seq_cst);
204 }
205 stamp_t tail_stamp() {
206 // (13) - this acquire-load synchronizes-with the release-CAS (16)
207 return tail->stamp.load(std::memory_order_acquire);
208 }
209
210 thread_control_block* acquire_control_block()
211 {
212 return global_thread_block_list.acquire_entry();
213 }
214
215 private:
216 static const unsigned DeleteMark = 1;
217 static const unsigned TagInc = 2;
218 static const unsigned MarkMask = (1 << MarkBits) - 1;
219
220 marked_ptr make_marked(thread_control_block* p, const marked_ptr& mark)
221 {
222 return marked_ptr(p, (mark.mark() + TagInc) & MarkMask);
223 }
224
225 marked_ptr make_clean_marked(thread_control_block* p, const concurrent_ptr& mark)
226 {
227 auto m = mark.load(std::memory_order_relaxed);
228 return marked_ptr(p, (m.mark() + TagInc) & MarkMask & ~DeleteMark);
229 }
230
231 void update_tail_stamp(size_t stamp)
232 {
233 // In the best case the stamp of tail equals the stamp of tail's predecessor (in prev
234 // direction), but we don't want to waste too much time finding the "actual" predecessor.
235 // Therefore we simply check whether the block referenced by tail->next is the actual
236 // predecessor and if so take its stamp. Otherwise we simply use the stamp that was
237 // passed (which is kind of a "best guess").
238 // (14) - this acquire-load synchronizes-with the release-stores (8, 27)
239 auto last = tail->next.load(std::memory_order_acquire);
240 // (15) - this acquire-load synchronizes-with the release-stores (4, 5, 9, 21, 28)
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)
246 {
247 assert((last_stamp & PendingPush) == 0);
248 assert((last_stamp & NotInList) == 0);
249 assert(last_stamp >= stamp);
250 if (last.get() != head)
251 stamp = last_stamp;
252 else
253 {
254 // Special case when we take the stamp from head - the stamp in head gets incremented
255 // before a new block is actually inserted, but we must not use such a value if the block
256 // is not yet inserted. By updating prev with an incremented version a pending insertion
257 // would fail and cause a retry, therefore enforcing the strict odering.
258 // However, since we are potentially disturbing push operations, we only want to do this if
259 // it is "worth it", i.e., if the stamp we read from head is at least one increment ahead
260 // of our "next best guess".
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))
264 stamp = last_stamp;
265 }
266 }
267
268 // Try to update tail->stamp, but only as long as our new value is actually greater.
269 auto tail_stamp = tail->stamp.load(std::memory_order_relaxed);
270 while (tail_stamp < stamp)
271 {
272 // (16) - this release-CAS synchronizes-with the acquire-load (13)
273 if (tail->stamp.compare_exchange_weak(tail_stamp, stamp, std::memory_order_release))
274 break;
275 }
276 }
277
278 bool remove_from_prev_list(marked_ptr& prev, marked_ptr b, marked_ptr& next)
279 {
280 PERF_COUNTER(iterations, b->counters.remove_prev_iterations);
281
282 const auto my_stamp = b->stamp.load(std::memory_order_relaxed);
283 marked_ptr last = nullptr;
284 for (;;)
285 {
286 iterations.inc();
287
288 // check if the block is already deleted
289 if (next.get() == prev.get())
290 {
291 next = b->next.load(std::memory_order_relaxed);
292 return false;
293 }
294
295 auto prev_prev = prev->prev.load(std::memory_order_relaxed);
296 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
297
298 // check if prev has been removed
299 if (prev_stamp > my_stamp || // prev has been reinserted already
300 prev_stamp & NotInList) // prev has been removed
301 {
302 return true;
303 }
304
305 if (prev_prev.mark() & DeleteMark)
306 {
307 if (!mark_next(prev, prev_stamp))
308 {
309 // prev is marked for deletion, but mark_next failed because the stamp
310 // of prev has been updated - i.e., prev has been deleted already (and
311 // maybe even reinserted)
312 // -> this implies that b must have been removed as well.
313 return true;
314 }
315 // This acquire-reload is needed to establish a happens-before relation
316 // between the remove operations and the reclamation of a node.
317 // (17) - this acquire-load synchronizes-with the release-stores (4, 9, 21, 28)
318 prev = prev->prev.load(std::memory_order_acquire);
319 continue;
320 }
321
322 // We need need to obtain a consistent set of "prev" and "stamp" values
323 // from next, otherwise we could wrongfully update next_prev's stamp in
324 // save_next_as_last_and_move_next_to_next_prev, since we cannot be sure
325 // if the "prev" value we see in the reload belongs to a block that is
326 // part of the list.
327
328 // (18) - this acquire-load synchronizes-with the release-stores (4, 5, 9, 21, 28)
329 auto next_prev = next->prev.load(std::memory_order_acquire);
330 // (19) - this acquire-load synchronizes-with the release-stores (2, 3, 6)
331 auto next_stamp = next->stamp.load(std::memory_order_acquire);
332
333 if (next_prev != next->prev.load(std::memory_order_relaxed))
334 continue;
335
336 if (next_stamp < my_stamp)
337 {
338 next = b->next.load(std::memory_order_relaxed);
339 return false;
340 }
341
342 // Check if next has been removed from list or whether it is currently getting inserted.
343 // It could be that the block is already inserted, but the PendingPush flag has not yet
344 // been cleared. Unfortunately, there is no way to identify this case here, so we have
345 // to go back yet another block.
346 // We can help resetting this flag once we are sure that the block is already part of the
347 // list, which is exactly what happens in save_next_as_last_and_move_next_to_next_prev.
348 if (next_stamp & (NotInList | PendingPush))
349 {
350 if (last.get() != nullptr)
351 {
352 next = last;
353 last.reset();
354 }
355 else
356 // (20) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
357 next = next->next.load(std::memory_order_acquire);
358 continue;
359 }
360
361 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
362 continue;
363
364 // check if next is the predecessor of b
365 if (next_prev.get() != b.get())
366 {
367 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
368 continue;
369 }
370
371 // unlink "b" from prev list
372 // (21) - this release-CAS synchronizes-with the acquire-loads (5, 9, 15, 17, 18, 22, 26)
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))
376 return false;
377
378 // Back-Off
379 }
380 }
381
382 void remove_from_next_list(marked_ptr prev, marked_ptr removed, marked_ptr next)
383 {
384 PERF_COUNTER(iterations, removed->counters.remove_next_iterations);
385
386 const auto my_stamp = removed->stamp.load(std::memory_order_relaxed);
387
388 marked_ptr last = nullptr;
389 for (;;)
390 {
391 iterations.inc();
392
393 // FIXME - why do we have to load next_prev before prev_next??
394 // We have to ensure that next is part of the list before obtaining the
395 // pointer we have to update, in order to ensure that we don't set the
396 // pointer to a block that has been removed in the meantime.
397
398 // (22) - this acquire-load synchronizes-with the release-stores (4, 5, 9, 21, 28)
399 auto next_prev = next->prev.load(std::memory_order_acquire);
400 // (23) - this acquire-load synchronizes-with the release-stores (2, 3, 6)
401 auto next_stamp = next->stamp.load(std::memory_order_acquire);
402
403 if (next_prev != next->prev.load(std::memory_order_relaxed))
404 continue;
405
406 // check if next has been removed from list
407 if (next_stamp & (NotInList | PendingPush))
408 {
409 if (last.get() != nullptr)
410 {
411 next = last;
412 last.reset();
413 }
414 else
415 {
416 // (24) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
417 next = next->next.load(std::memory_order_acquire);
418 }
419 continue;
420 }
421
422 // (25) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
423 auto prev_next = prev->next.load(std::memory_order_acquire);
424 auto prev_stamp = prev->stamp.load(std::memory_order_relaxed);
425
426 assert(prev.get() != removed.get() || prev_stamp > my_stamp);
427
428 // check if prev has a higher stamp than the block we want to remove.
429 if (prev_stamp > my_stamp || prev_stamp & NotInList)
430 {
431 // due to strict order of stamps the prev block must have been removed already - and with it b.
432 return;
433 }
434
435 // check if prev block is marked for deletion
436 if (prev_next.mark() & DeleteMark)
437 {
438 // This acquire-load is needed to establish a happens-before relation
439 // between the different remove operations and the reclamation of a node.
440 // (26) - this acquire-load synchronizes-with the release-stores (4, 9, 21, 28)
441 prev = prev->prev.load(std::memory_order_acquire);
442 continue;
443 }
444
445 if (next.get() == prev.get())
446 return;
447
448 if (remove_or_skip_marked_block(next, last, next_prev, next_stamp))
449 continue;
450
451 // check if next is the predecessor of prev
452 if (next_prev.get() != prev.get())
453 {
454 save_next_as_last_and_move_next_to_next_prev(next_prev, next, last);
455 continue;
456 }
457
458 if (next_stamp <= my_stamp || prev_next.get() == next.get())
459 return;
460
461 auto new_next = make_marked(next.get(), prev_next);
462 if (next->prev.load(std::memory_order_relaxed) == next_prev &&
463 // (27) - this release-CAS synchronizes-with the acquire-loads (7, 8, 14, 20, 24, 25, 29, 31, 32)
464 prev->next.compare_exchange_weak(prev_next, new_next,
465 std::memory_order_release,
466 std::memory_order_relaxed))
467 {
468 if ((next->next.load(std::memory_order_relaxed).mark() & DeleteMark) == 0)
469 return;
470 }
471 // Back-Off
472 }
473 }
474
475 bool remove_or_skip_marked_block(marked_ptr &next, marked_ptr &last,
476 marked_ptr next_prev, stamp_t next_stamp)
477 {
478 // check if next is marked
479 if (next_prev.mark() & DeleteMark)
480 {
481 if (last.get() != nullptr)
482 {
483 // check if next has "overtaken" last
484 assert((next.mark() & DeleteMark) == 0);
485 if (mark_next(next, next_stamp) &&
486 last->prev.load(std::memory_order_relaxed) == next)
487 {
488 // unlink next from prev-list
489 // (28) - this release-CAS synchronizes-with the acquire-loads (5, 9, 15, 17, 18, 22, 26)
490 last->prev.compare_exchange_strong(next, make_marked(next_prev.get(), next),
491 std::memory_order_release,
492 std::memory_order_relaxed);
493 }
494 next = last;
495 last.reset();
496 }
497 else
498 // (29) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
499 next = next->next.load(std::memory_order_acquire);
500
501 return true;
502 }
503 return false;
504 }
505
506 void save_next_as_last_and_move_next_to_next_prev(
507 marked_ptr next_prev, marked_ptr& next, marked_ptr& last)
508 {
509 // (30) - this acquire-load synchronizes-with the release-stores (3, 6)
510 size_t next_prev_stamp = next_prev->stamp.load(std::memory_order_acquire);
511
512 if (next_prev_stamp & PendingPush && next_prev == next->prev.load(std::memory_order_relaxed))
513 {
514 assert((next_prev_stamp & NotInList) == 0);
515 // since we got here via an (unmarked) prev pointer next_prev has been added to
516 // the "prev-list", but the PendingPush flag has not been cleared yet.
517 // i.e., the push operation for next_prev is still pending -> help clear the PendingPush flag
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))
521 {
522 // CAS operation failed, i.e., the stamp of next_prev has been changed
523 // since we read it. Check if some other thread cleared the flag already
524 // or whether next_prev has been removed (and potentially readded).
525 if (expected != new_stamp)
526 {
527 // the stamp has been updated to an unexpected value, so next_prev has been removed
528 // already -> we cannot move to next_prev, but we can keep the current next and last.
529 return;
530 }
531 }
532 }
533 last = next;
534 next = next_prev;
535 }
536
537 marked_ptr set_mark_flag(concurrent_ptr& ptr, std::memory_order order)
538 {
539 auto link = ptr.load(std::memory_order_relaxed);
540 for (;;)
541 {
542 if (link.mark() & DeleteMark ||
543 ptr.compare_exchange_weak(link, marked_ptr(link.get(), link.mark() | DeleteMark),
544 order, std::memory_order_relaxed))
545 return link;
546 }
547 }
548
549 // tries to mark the next ptr of 'block', as long as block's stamp matches the given stamp
550 bool mark_next(marked_ptr block, size_t stamp)
551 {
552 assert((stamp & (NotInList | PendingPush)) == 0);
553 // (31) - this acquire-load synchronizes-with the release-stores (1, 8, 27)
554 auto link = block->next.load(std::memory_order_acquire);
555 // We need acquire to synchronize-with the release store in push. This way it is
556 // guaranteed that the following stamp.load sees the NotInList flag or some newer
557 // stamp, thus causing termination of the loop.
558 while (block->stamp.load(std::memory_order_relaxed) == stamp)
559 {
560 auto mark = link.mark();
561 if (mark & DeleteMark ||
562 // (32) - this acquire-reload synchronizes-with the release-stores (1, 8, 27)
563 block->next.compare_exchange_weak(link,
564 marked_ptr(link.get(), mark | DeleteMark),
565 std::memory_order_relaxed,
566 std::memory_order_acquire))
567 // Note: the C++11 standard states that "the failure argument shall be no stronger than
568 // the success argument". However, this has been relaxed in C++17.
569 // (see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0418r1.html)
570 // Some implementations (e.g., the Microsoft STL) perform runtime checks to enforce these
571 // requirements. So in case the above CAS operation causes runtime errors, one has to use
572 // release instead of relaxed order.
573 return true;
574 }
575 return false;
576 }
577
578 thread_control_block* head;
579 thread_control_block* tail;
580
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;
584 };
585
586 struct stamp_it::thread_data
587 {
588 ~thread_data()
589 {
590 assert(region_entries == 0);
591 if (control_block == nullptr)
592 return;
593
594 control_block->abandon();
595 control_block = nullptr;
596
597 // reclaim as much nodes as possible
598 process_local_nodes();
599 if (first_retired_node)
600 {
601 // we still have retired nodes that cannot yet be reclaimed
602 // -> add them to the global list.
603 queue.add_to_global_retired_nodes(first_retired_node);
604 }
605 }
606
607 void enter_region()
608 {
609 if (++region_entries == 1)
610 {
611 ensure_has_control_block();
612 queue.push(control_block);
613 }
614 }
615
616 void leave_region()
617 {
618 if (--region_entries == 0)
619 {
620 auto wasLast = queue.remove(control_block);
621
622 if (wasLast)
623 process_global_nodes();
624 else
625 {
626 process_local_nodes();
627 if (number_of_retired_nodes > max_remaining_retired_nodes)
628 {
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;
633 }
634 }
635 }
636 }
637
638 void add_retired_node(deletable_object_with_stamp* p)
639 {
640 p->stamp = queue.head_stamp();
641 *prev_retired_node = p;
642 prev_retired_node = &p->next;
643
644 ++number_of_retired_nodes;
645 if (number_of_retired_nodes > try_reclaim_threshold)
646 process_local_nodes();
647 }
648
649 private:
650 void ensure_has_control_block()
651 {
652 if (control_block == nullptr)
653 {
654 control_block = queue.acquire_control_block();
655#ifdef WITH_PERF_COUNTER
656 control_block->counters = performance_counters{}; // reset counters
657#endif
658 }
659 }
660
661 void process_local_nodes()
662 {
663 auto tail_stamp = queue.tail_stamp();
664 std::size_t cnt = 0;
665 auto cur = first_retired_node;
666 for (deletable_object_with_stamp* next = nullptr; cur != nullptr; cur = next)
667 {
668 next = cur->next;
669 if (cur->stamp <= tail_stamp)
670 {
671 cur->delete_self();
672 ++cnt;
673 }
674 else
675 break;
676 }
677
678 first_retired_node = cur;
679 if (cur == nullptr)
680 prev_retired_node = &first_retired_node;
681 number_of_retired_nodes -= cnt;
682 }
683
684 void process_global_nodes()
685 {
686 auto tail_stamp = queue.tail_stamp();
687 auto cur_chunk = queue.steal_global_retired_nodes();
688
689 if (first_retired_node != nullptr)
690 {
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;
696 }
697 if (cur_chunk == nullptr)
698 return;
699
700 stamp_t lowest_stamp;
701 auto process_chunk_nodes = [tail_stamp, &lowest_stamp](deletable_object_with_stamp* chunk)
702 {
703 auto cur = chunk;
704 while (cur)
705 {
706 if (cur->stamp <= tail_stamp)
707 {
708 lowest_stamp = std::min(lowest_stamp, cur->stamp);
709 auto next = cur->next;
710 cur->delete_self();
711 cur = next;
712 }
713 else
714 break; // we cannot process any more nodes from this chunk
715 }
716 return cur;
717 };
718
719 restart:
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;
724 while (cur_chunk)
725 {
726 auto next_chunk = cur_chunk->next_chunk;
727 auto remaining_chunk = process_chunk_nodes(cur_chunk);
728 if (remaining_chunk)
729 {
730 *prev_remaining_chunk = remaining_chunk;
731 last_remaining_chunk = remaining_chunk;
732 prev_remaining_chunk = &remaining_chunk->next_chunk;
733 }
734 cur_chunk = next_chunk;
735 }
736
737 *prev_remaining_chunk = nullptr;
738 if (first_remaining_chunk)
739 {
740 auto new_tail_stamp = queue.tail_stamp();
741 if (lowest_stamp < new_tail_stamp)
742 {
743 cur_chunk = first_remaining_chunk;
744 tail_stamp = new_tail_stamp;
745 goto restart;
746 }
747 else
748 {
749 assert(last_remaining_chunk != nullptr);
750 queue.add_to_global_retired_nodes(first_remaining_chunk, last_remaining_chunk);
751 }
752 }
753 }
754
755 // This threshold defines the max. number of nodes a thread may collect
756 // in the local retire-list before trying to reclaim them. It is checked
757 // every time a new node is added to the local retire-list.
758 static const std::size_t try_reclaim_threshold = 40;
759 // The max. number of nodes that may remain a threads local retire-list
760 // when it leaves it's critical region. If there are more nodes in the
761 // list, then the whole list will be added to the global retire-list.
762 static const std::size_t max_remaining_retired_nodes = 20;
763
764 thread_control_block* control_block = nullptr;
765 unsigned region_entries = 0;
766 std::size_t number_of_retired_nodes = 0;
767
768 deletable_object_with_stamp* first_retired_node = nullptr;
769 deletable_object_with_stamp** prev_retired_node = &first_retired_node;
770
771 friend class stamp_it;
772 ALLOCATION_COUNTER(stamp_it);
773 };
774
775 inline stamp_it::region_guard::region_guard() noexcept
776 {
777 local_thread_data().enter_region();
778 }
779
780 inline stamp_it::region_guard::~region_guard() //noexcept ??
781 {
782 local_thread_data().leave_region();
783 }
784
785 template <class T, class MarkedPtr>
786 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(const MarkedPtr& p) noexcept :
787 base(p)
788 {
789 if (this->ptr)
790 local_thread_data().enter_region();
791 }
792
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))
796 {}
797
798 template <class T, class MarkedPtr>
799 stamp_it::guard_ptr<T, MarkedPtr>::guard_ptr(guard_ptr&& p) noexcept :
800 base(p.ptr)
801 {
802 p.ptr.reset();
803 }
804
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
808 {
809 if (&p == this)
810 return *this;
811
812 reset();
813 this->ptr = p.ptr;
814 if (this->ptr)
815 local_thread_data().enter_region();
816
817 return *this;
818 }
819
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
823 {
824 if (&p == this)
825 return *this;
826
827 reset();
828 this->ptr = std::move(p.ptr);
829 p.ptr.reset();
830
831 return *this;
832 }
833
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
837 {
838 if (p.load(std::memory_order_relaxed) == nullptr)
839 {
840 reset();
841 return;
842 }
843
844 if (!this->ptr)
845 local_thread_data().enter_region();
846 this->ptr = p.load(order);
847 if (!this->ptr)
848 local_thread_data().leave_region();
849 }
850
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
854 {
855 auto actual = p.load(std::memory_order_relaxed);
856 if (actual == nullptr || actual != expected)
857 {
858 reset();
859 return actual == expected;
860 }
861
862 if (!this->ptr)
863 local_thread_data().enter_region();
864 this->ptr = p.load(order);
865 if (!this->ptr || this->ptr != expected)
866 {
867 local_thread_data().leave_region();
868 this->ptr.reset();
869 }
870
871 return this->ptr == expected;
872 }
873
874 template <class T, class MarkedPtr>
875 void stamp_it::guard_ptr<T, MarkedPtr>::reset() noexcept
876 {
877 if (this->ptr)
878 local_thread_data().leave_region();
879 this->ptr.reset();
880 }
881
882 template <class T, class MarkedPtr>
883 void stamp_it::guard_ptr<T, MarkedPtr>::reclaim(Deleter d) noexcept
884 {
885 this->ptr->set_deleter(std::move(d));
886 local_thread_data().add_retired_node(this->ptr.get());
887 reset();
888 }
889
890 inline stamp_it::thread_data& stamp_it::local_thread_data()
891 {
892 // workaround for a GCC issue with multiple definitions of __tls_guard
893 static thread_local thread_data local_thread_data;
894 return local_thread_data;
895 }
896
897#if _MSC_VER
898 __declspec(selectany) stamp_it::thread_order_queue stamp_it::queue;
899#else
900 inline stamp_it::thread_order_queue stamp_it::queue;
901#endif
902
903#ifdef WITH_PERF_COUNTER
904 inline stamp_it::performance_counters stamp_it::get_performance_counters()
905 {
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)
910 {
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;
916 });
917
918 return result;
919 }
920#endif
921
922#ifdef TRACK_ALLOCATIONS
923 inline void stamp_it::count_allocation()
924 { local_thread_data().allocation_counter.count_allocation(); }
925
926 inline void stamp_it::count_reclamation()
927 { local_thread_data().allocation_counter.count_reclamation(); }
928#endif
929}}
930
931#ifdef _MSC_VER
932#pragma warning(pop)
933#endif