xenium
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 
23 namespace 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