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