1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <folly/synchronization/Hazptr.h>
18
19 #include <atomic>
20 #include <thread>
21
22 #include <folly/Singleton.h>
23 #include <folly/portability/GFlags.h>
24 #include <folly/portability/GTest.h>
25 #include <folly/synchronization/HazptrThreadPoolExecutor.h>
26 #include <folly/synchronization/example/HazptrLockFreeLIFO.h>
27 #include <folly/synchronization/example/HazptrSWMRSet.h>
28 #include <folly/synchronization/example/HazptrWideCAS.h>
29 #include <folly/synchronization/test/Barrier.h>
30 #include <folly/test/DeterministicSchedule.h>
31
32 DEFINE_bool(bench, false, "run benchmark");
33 DEFINE_int64(num_reps, 10, "Number of test reps");
34 DEFINE_int32(num_threads, 6, "Number of threads");
35 DEFINE_int64(num_ops, 1003, "Number of ops or pairs of ops per rep");
36
37 using folly::default_hazptr_domain;
38 using folly::hazard_pointer;
39 using folly::hazard_pointer_clean_up;
40 using folly::hazard_pointer_default_domain;
41 using folly::hazard_pointer_obj_base;
42 using folly::hazptr_array;
43 using folly::hazptr_cleanup;
44 using folly::hazptr_domain;
45 using folly::hazptr_holder;
46 using folly::hazptr_local;
47 using folly::hazptr_obj_base;
48 using folly::hazptr_obj_base_linked;
49 using folly::hazptr_obj_cohort;
50 using folly::hazptr_retire;
51 using folly::hazptr_root;
52 using folly::hazptr_tc;
53 using folly::hazptr_tc_evict;
54 using folly::HazptrLockFreeLIFO;
55 using folly::HazptrSWMRSet;
56 using folly::HazptrWideCAS;
57 using folly::make_hazard_pointer;
58 using folly::make_hazard_pointer_array;
59 using folly::test::Barrier;
60 using folly::test::DeterministicAtomic;
61
62 using DSched = folly::test::DeterministicSchedule;
63
64 // Structures
65
66 /** Count */
67 class Count {
68 std::atomic<int> ctors_{0};
69 std::atomic<int> dtors_{0};
70 std::atomic<int> retires_{0};
71
72 public:
clear()73 void clear() noexcept {
74 ctors_.store(0);
75 dtors_.store(0);
76 retires_.store(0);
77 }
78
ctors() const79 int ctors() const noexcept { return ctors_.load(); }
80
dtors() const81 int dtors() const noexcept { return dtors_.load(); }
82
retires() const83 int retires() const noexcept { return retires_.load(); }
84
inc_ctors()85 void inc_ctors() noexcept { ctors_.fetch_add(1); }
86
inc_dtors()87 void inc_dtors() noexcept { dtors_.fetch_add(1); }
88
inc_retires()89 void inc_retires() noexcept { retires_.fetch_add(1); }
90 }; // Count
91
92 static Count c_;
93
94 /** Node */
95 template <template <typename> class Atom = std::atomic>
96 class Node : public hazptr_obj_base<Node<Atom>, Atom> {
97 int val_;
98 Atom<Node<Atom>*> next_;
99
100 public:
Node(int v=0,Node * n=nullptr,bool=false)101 explicit Node(int v = 0, Node* n = nullptr, bool = false) noexcept
102 : val_(v), next_(n) {
103 c_.inc_ctors();
104 }
105
~Node()106 ~Node() { c_.inc_dtors(); }
107
value() const108 int value() const noexcept { return val_; }
109
next() const110 Node<Atom>* next() const noexcept {
111 return next_.load(std::memory_order_acquire);
112 }
113
ptr_next()114 Atom<Node<Atom>*>* ptr_next() noexcept { return &next_; }
115 }; // Node
116
117 /** NodeRC */
118 template <bool Mutable, template <typename> class Atom = std::atomic>
119 class NodeRC : public hazptr_obj_base_linked<NodeRC<Mutable, Atom>, Atom> {
120 Atom<NodeRC<Mutable, Atom>*> next_;
121 int val_;
122
123 public:
NodeRC(int v=0,NodeRC * n=nullptr,bool acq=false)124 explicit NodeRC(int v = 0, NodeRC* n = nullptr, bool acq = false) noexcept
125 : next_(n), val_(v) {
126 this->set_deleter();
127 c_.inc_ctors();
128 if (acq) {
129 if (Mutable) {
130 this->acquire_link_safe();
131 } else {
132 this->acquire_ref_safe();
133 }
134 }
135 }
136
~NodeRC()137 ~NodeRC() { c_.inc_dtors(); }
138
value() const139 int value() const noexcept { return val_; }
140
next() const141 NodeRC<Mutable, Atom>* next() const noexcept {
142 return next_.load(std::memory_order_acquire);
143 }
144
145 template <typename S>
push_links(bool m,S & s)146 void push_links(bool m, S& s) {
147 if (Mutable == m) {
148 auto p = next();
149 if (p) {
150 s.push(p);
151 }
152 }
153 }
154 }; // NodeRC
155
156 /** List */
157 template <typename T, template <typename> class Atom = std::atomic>
158 struct List {
159 Atom<T*> head_{nullptr};
160
161 public:
ListList162 explicit List(int size) {
163 auto p = head_.load(std::memory_order_relaxed);
164 for (int i = 0; i < size - 1; ++i) {
165 p = new T(i + 10000, p, true);
166 }
167 p = new T(size + 9999, p);
168 head_.store(p, std::memory_order_relaxed);
169 }
170
~ListList171 ~List() {
172 auto curr = head_.load(std::memory_order_relaxed);
173 while (curr) {
174 auto next = curr->next();
175 curr->retire();
176 curr = next;
177 }
178 }
179
hand_over_handList180 bool hand_over_hand(
181 int val, hazptr_holder<Atom>* hptr_prev, hazptr_holder<Atom>* hptr_curr) {
182 while (true) {
183 auto prev = &head_;
184 auto curr = prev->load(std::memory_order_acquire);
185 while (true) {
186 if (!curr) {
187 return false;
188 }
189 if (!hptr_curr->try_protect(curr, *prev)) {
190 break;
191 }
192 auto next = curr->next();
193 if (prev->load(std::memory_order_acquire) != curr) {
194 break;
195 }
196 if (curr->value() == val) {
197 return true;
198 }
199 prev = curr->ptr_next();
200 curr = next;
201 std::swap(hptr_curr, hptr_prev);
202 }
203 }
204 }
205
hand_over_handList206 bool hand_over_hand(int val) {
207 hazptr_local<2, Atom> hptr;
208 return hand_over_hand(val, &hptr[0], &hptr[1]);
209 }
210
protect_allList211 bool protect_all(int val, hazptr_holder<Atom>& hptr) {
212 auto curr = hptr.protect(head_);
213 while (curr) {
214 auto next = curr->next();
215 if (curr->value() == val) {
216 return true;
217 }
218 curr = next;
219 }
220 return false;
221 }
222
protect_allList223 bool protect_all(int val) {
224 hazptr_local<1, Atom> hptr;
225 return protect_all(val, hptr[0]);
226 }
227 }; // List
228
229 /** NodeAuto */
230 template <template <typename> class Atom = std::atomic>
231 class NodeAuto : public hazptr_obj_base_linked<NodeAuto<Atom>, Atom> {
232 Atom<NodeAuto<Atom>*> link_[2];
233
234 public:
NodeAuto(NodeAuto * l1=nullptr,NodeAuto * l2=nullptr)235 explicit NodeAuto(NodeAuto* l1 = nullptr, NodeAuto* l2 = nullptr) noexcept {
236 this->set_deleter();
237 link_[0].store(l1, std::memory_order_relaxed);
238 link_[1].store(l2, std::memory_order_relaxed);
239 c_.inc_ctors();
240 }
241
~NodeAuto()242 ~NodeAuto() { c_.inc_dtors(); }
243
link(size_t i)244 NodeAuto<Atom>* link(size_t i) {
245 return link_[i].load(std::memory_order_acquire);
246 }
247
248 template <typename S>
push_links(bool m,S & s)249 void push_links(bool m, S& s) {
250 if (m == false) { // Immutable
251 for (int i = 0; i < 2; ++i) {
252 auto p = link(i);
253 if (p) {
254 s.push(p);
255 }
256 }
257 }
258 }
259 }; // NodeAuto
260
261 // Test Functions
262
263 template <template <typename> class Atom = std::atomic>
basic_objects_test()264 void basic_objects_test() {
265 c_.clear();
266 int num = 0;
267 {
268 ++num;
269 auto obj = new Node<Atom>;
270 obj->retire();
271 }
272 {
273 ++num;
274 auto obj = new NodeRC<false, Atom>(0, nullptr);
275 obj->retire();
276 }
277 {
278 ++num;
279 auto obj = new NodeRC<false, Atom>(0, nullptr);
280 obj->acquire_link_safe();
281 obj->unlink();
282 }
283 {
284 ++num;
285 auto obj = new NodeRC<false, Atom>(0, nullptr);
286 obj->acquire_link_safe();
287 obj->unlink_and_reclaim_unchecked();
288 }
289 {
290 ++num;
291 auto obj = new NodeRC<false, Atom>(0, nullptr);
292 obj->acquire_link_safe();
293 hazptr_root<NodeRC<false, Atom>> root(obj);
294 }
295 ASSERT_EQ(c_.ctors(), num);
296 hazptr_cleanup<Atom>();
297 ASSERT_EQ(c_.dtors(), num);
298 }
299
300 template <template <typename> class Atom = std::atomic>
copy_and_move_test()301 void copy_and_move_test() {
302 struct Obj : hazptr_obj_base<Obj, Atom> {
303 int a;
304 };
305
306 auto p1 = new Obj();
307 auto p2 = new Obj(*p1);
308 p1->retire();
309 p2->retire();
310
311 p1 = new Obj();
312 p2 = new Obj(std::move(*p1));
313 p1->retire();
314 p2->retire();
315
316 p1 = new Obj();
317 p2 = new Obj();
318 *p2 = *p1;
319 p1->retire();
320 p2->retire();
321
322 p1 = new Obj();
323 p2 = new Obj();
324 *p2 = std::move(*p1);
325 p1->retire();
326 p2->retire();
327 hazptr_cleanup<Atom>();
328 }
329
330 template <template <typename> class Atom = std::atomic>
basic_holders_test()331 void basic_holders_test() {
332 { hazptr_holder<Atom> h = make_hazard_pointer<Atom>(); }
333 { hazptr_array<2, Atom> h = make_hazard_pointer_array<2, Atom>(); }
334 { hazptr_local<2, Atom> h; }
335 }
336
337 template <template <typename> class Atom = std::atomic>
basic_protection_test()338 void basic_protection_test() {
339 c_.clear();
340 auto obj = new Node<Atom>;
341 hazptr_holder<Atom> h = make_hazard_pointer<Atom>();
342 h.reset_protection(obj);
343 obj->retire();
344 ASSERT_EQ(c_.ctors(), 1);
345 hazptr_cleanup<Atom>();
346 ASSERT_EQ(c_.dtors(), 0);
347 h.reset_protection();
348 hazptr_cleanup<Atom>();
349 ASSERT_EQ(c_.dtors(), 1);
350 }
351
352 template <template <typename> class Atom = std::atomic>
virtual_test()353 void virtual_test() {
354 struct Thing : public hazptr_obj_base<Thing, Atom> {
355 virtual ~Thing() {}
356 int a;
357 };
358 for (int i = 0; i < 100; i++) {
359 auto bar = new Thing;
360 bar->a = i;
361
362 hazptr_holder<Atom> hptr = make_hazard_pointer<Atom>();
363 hptr.reset_protection(bar);
364 bar->retire();
365 ASSERT_EQ(bar->a, i);
366 }
367 hazptr_cleanup<Atom>();
368 }
369
370 template <template <typename> class Atom = std::atomic>
destruction_test(hazptr_domain<Atom> & domain)371 void destruction_test(hazptr_domain<Atom>& domain) {
372 struct Thing : public hazptr_obj_base<Thing, Atom> {
373 Thing* next;
374 hazptr_domain<Atom>* domain;
375 int val;
376 Thing(int v, Thing* n, hazptr_domain<Atom>* d)
377 : next(n), domain(d), val(v) {}
378 ~Thing() {
379 if (next) {
380 next->retire(*domain);
381 }
382 }
383 };
384 Thing* last{nullptr};
385 for (int i = 0; i < 2000; i++) {
386 last = new Thing(i, last, &domain);
387 }
388 last->retire(domain);
389 hazptr_cleanup<Atom>();
390 }
391
392 template <template <typename> class Atom = std::atomic>
move_test()393 void move_test() {
394 for (int i = 0; i < 100; ++i) {
395 auto x = new Node<Atom>(i);
396 hazptr_holder<Atom> hptr0 = make_hazard_pointer<Atom>();
397 // Protect object
398 hptr0.reset_protection(x);
399 // Retire object
400 x->retire();
401 // Move constructor - still protected
402 hazptr_holder<Atom> hptr1(std::move(hptr0));
403 // Self move is no-op - still protected
404 auto phptr1 = &hptr1;
405 ASSERT_EQ(phptr1, &hptr1);
406 hptr1 = std::move(*phptr1);
407 // Empty constructor
408 hazptr_holder<Atom> hptr2;
409 // Move assignment - still protected
410 hptr2 = std::move(hptr1);
411 // Access object
412 ASSERT_EQ(x->value(), i);
413 // Unprotect object - hptr2 is nonempty
414 hptr2.reset_protection();
415 }
416 hazptr_cleanup<Atom>();
417 }
418
419 template <template <typename> class Atom = std::atomic>
array_test()420 void array_test() {
421 for (int i = 0; i < 100; ++i) {
422 auto x = new Node<Atom>(i);
423 hazptr_array<3, Atom> hptr = make_hazard_pointer_array<3, Atom>();
424 // Protect object
425 hptr[2].reset_protection(x);
426 // Empty array
427 hazptr_array<3, Atom> h;
428 // Move assignment
429 h = std::move(hptr);
430 // Retire object
431 x->retire();
432 ASSERT_EQ(x->value(), i);
433 // Unprotect object - hptr2 is nonempty
434 h[2].reset_protection();
435 }
436 hazptr_cleanup<Atom>();
437 }
438
439 template <template <typename> class Atom = std::atomic>
array_dtor_full_tc_test()440 void array_dtor_full_tc_test() {
441 #if FOLLY_HAZPTR_THR_LOCAL
442 const uint8_t M = hazptr_tc<Atom>::capacity();
443 #else
444 const uint8_t M = 3;
445 #endif
446 {
447 // Fill the thread cache
448 hazptr_array<M, Atom> w = make_hazard_pointer_array<M, Atom>();
449 }
450 {
451 // Empty array x
452 hazptr_array<M, Atom> x;
453 {
454 // y ctor gets elements from the thread cache filled by w dtor.
455 hazptr_array<M, Atom> y = make_hazard_pointer_array<M, Atom>();
456 // z ctor gets elements from the default domain.
457 hazptr_array<M, Atom> z = make_hazard_pointer_array<M, Atom>();
458 // Elements of y are moved to x.
459 x = std::move(y);
460 // z dtor fills the thread cache.
461 }
462 // x dtor finds the thread cache full. It has to call
463 // ~hazptr_holder() for each of its elements, which were
464 // previously taken from the thread cache by y ctor.
465 }
466 }
467
468 template <template <typename> class Atom = std::atomic>
local_test()469 void local_test() {
470 for (int i = 0; i < 100; ++i) {
471 auto x = new Node<Atom>(i);
472 hazptr_local<3, Atom> hptr;
473 // Protect object
474 hptr[2].reset_protection(x);
475 // Retire object
476 x->retire();
477 // Unprotect object - hptr2 is nonempty
478 hptr[2].reset_protection();
479 }
480 hazptr_cleanup<Atom>();
481 }
482
483 template <bool Mutable, template <typename> class Atom = std::atomic>
linked_test()484 void linked_test() {
485 c_.clear();
486 NodeRC<Mutable, Atom>* p = nullptr;
487 int num = 193;
488 for (int i = 0; i < num - 1; ++i) {
489 p = new NodeRC<Mutable, Atom>(i, p, true);
490 }
491 p = new NodeRC<Mutable, Atom>(num - 1, p, Mutable);
492 hazptr_holder<Atom> hptr = make_hazard_pointer<Atom>();
493 hptr.reset_protection(p);
494 if (!Mutable) {
495 for (auto q = p->next(); q; q = q->next()) {
496 q->retire();
497 }
498 }
499 int v = num;
500 for (auto q = p; q; q = q->next()) {
501 ASSERT_GT(v, 0);
502 --v;
503 ASSERT_EQ(q->value(), v);
504 }
505
506 hazptr_cleanup<Atom>();
507 ASSERT_EQ(c_.ctors(), num);
508 ASSERT_EQ(c_.dtors(), 0);
509
510 if (Mutable) {
511 hazptr_root<NodeRC<Mutable, Atom>, Atom> root(p);
512 } else {
513 p->retire();
514 }
515 hazptr_cleanup<Atom>();
516 ASSERT_EQ(c_.dtors(), 0);
517
518 hptr.reset_protection();
519 hazptr_cleanup<Atom>();
520 ASSERT_EQ(c_.dtors(), num);
521 }
522
523 template <bool Mutable, template <typename> class Atom = std::atomic>
mt_linked_test()524 void mt_linked_test() {
525 c_.clear();
526
527 Atom<bool> ready(false);
528 Atom<bool> done(false);
529 Atom<int> setHazptrs(0);
530 hazptr_root<NodeRC<Mutable, Atom>, Atom> head;
531
532 int num = FLAGS_num_ops;
533 int nthr = FLAGS_num_threads;
534 ASSERT_GT(FLAGS_num_threads, 0);
535 std::vector<std::thread> thr(nthr);
536 for (int i = 0; i < nthr; ++i) {
537 thr[i] = DSched::thread([&] {
538 while (!ready.load()) {
539 /* spin */
540 }
541 hazptr_holder<Atom> hptr = make_hazard_pointer<Atom>();
542 auto p = hptr.protect(head());
543 ++setHazptrs;
544 /* Concurrent with removal */
545 int v = num;
546 for (auto q = p; q; q = q->next()) {
547 ASSERT_GT(v, 0);
548 --v;
549 ASSERT_EQ(q->value(), v);
550 }
551 ASSERT_EQ(v, 0);
552 while (!done.load()) {
553 /* spin */
554 }
555 });
556 }
557
558 NodeRC<Mutable, Atom>* p = nullptr;
559 for (int i = 0; i < num - 1; ++i) {
560 p = new NodeRC<Mutable, Atom>(i, p, true);
561 }
562 p = new NodeRC<Mutable, Atom>(num - 1, p, Mutable);
563 ASSERT_EQ(c_.ctors(), num);
564 head().store(p);
565 ready.store(true);
566 while (setHazptrs.load() < nthr) {
567 /* spin */
568 }
569
570 /* this is concurrent with traversal by readers */
571 head().store(nullptr);
572 if (Mutable) {
573 p->unlink();
574 } else {
575 for (auto q = p; q; q = q->next()) {
576 q->retire();
577 }
578 }
579 ASSERT_EQ(c_.dtors(), 0);
580 done.store(true);
581
582 for (auto& t : thr) {
583 DSched::join(t);
584 }
585
586 hazptr_cleanup<Atom>();
587 ASSERT_EQ(c_.dtors(), num);
588 }
589
590 template <template <typename> class Atom = std::atomic>
auto_retire_test()591 void auto_retire_test() {
592 c_.clear();
593 auto d = new NodeAuto<Atom>;
594 d->acquire_link_safe();
595 auto c = new NodeAuto<Atom>(d);
596 d->acquire_link_safe();
597 auto b = new NodeAuto<Atom>(d);
598 c->acquire_link_safe();
599 b->acquire_link_safe();
600 auto a = new NodeAuto<Atom>(b, c);
601 hazptr_holder<Atom> h = make_hazard_pointer<Atom>();
602 {
603 hazptr_root<NodeAuto<Atom>> root;
604 a->acquire_link_safe();
605 root().store(a);
606 ASSERT_EQ(c_.ctors(), 4);
607 /* So far the links and link counts are:
608 root-->a a-->b a-->c b-->d c-->d
609 a(1,0) b(1,0) c(1,0) d(2,0)
610 */
611 h.reset_protection(c); /* h protects c */
612 hazptr_cleanup<Atom>();
613 ASSERT_EQ(c_.dtors(), 0);
614 /* Nothing is retired or reclaimed yet */
615 }
616 /* root dtor calls a->unlink, which calls a->release_link, which
617 changes a's link counts from (1,0) to (0,0), which triggers calls
618 to c->downgrade_link, b->downgrade_link, and a->retire.
619
620 c->downgrade_link changes c's link counts from (1,0) to (0,1),
621 which triggers calls to d->downgrade_link and c->retire.
622
623 d->downgrade_link changes d's link counts from (2,0) to (1,1).
624
625 b->downgrade_link changes b's link counts from (1,0) to (0,1),
626 which triggers calls to d->downgrade_link and b->retire.
627
628 d->downgrade_link changes d's link counts from (1,1) to (0,2),
629 which triggers a call to d->retire.
630
631 So far (assuming retire-s did not trigger bulk_reclaim):
632 a-->b a-->c b-->d c-->d
633 a(0,0) b(0,1) c(0,1) d(0,2)
634 Retired: a b c d
635 Protected: c
636 */
637 hazptr_cleanup<Atom>();
638 /* hazptr_cleanup calls bulk_reclaim which finds a, b, and d
639 unprotected, which triggers calls to a->release_ref,
640 b->release_ref, and d->release_ref (not necessarily in that
641 order).
642
643 a->release_ref finds a's link counts to be (0,0), which triggers
644 calls to c->release_ref, b->release_ref and delete a.
645
646 The call to c->release_ref changes its link counts from (0,1) to
647 (0,0).
648
649 The first call to b->release_ref changes b's link counts to
650 (0,0). The second call finds the link counts to be (0,0), which
651 triggers a call to d->release_ref and delete b.
652
653 The first call to d->release_ref changes its link counts to
654 (0,1), and the second call changes them to (0,0);
655
656 So far:
657 c-->d
658 a(deleted) b(deleted) c(0,0) d(0,0)
659 Retired and protected: c
660 bulk_reclamed-ed (i.e, found not protected): d
661 */
662 ASSERT_EQ(c_.dtors(), 2);
663 h.reset_protection(); /* c is now no longer protected */
664 hazptr_cleanup<Atom>();
665 /* hazptr_cleanup calls bulk_reclaim which finds c unprotected,
666 which triggers a call to c->release_ref.
667
668 c->release_ref finds c's link counts to be (0,0), which
669 triggers calls to d->release_ref and delete c.
670
671 d->release_ref finds d's link counts to be (0,0), which triggers
672 a call to delete d.
673
674 Finally:
675 a(deleted) b(deleted) c(deleted) d(deleted)
676 */
677 ASSERT_EQ(c_.dtors(), 4);
678 }
679
680 template <template <typename> class Atom = std::atomic>
free_function_retire_test()681 void free_function_retire_test() {
682 auto foo = new int;
683 hazptr_retire<Atom>(foo);
684 auto foo2 = new int;
685 hazptr_retire<Atom>(foo2, [](int* obj) { delete obj; });
686
687 bool retired = false;
688 {
689 hazptr_domain<Atom> myDomain0;
690 struct delret {
691 bool* retired_;
692 explicit delret(bool* retire) : retired_(retire) {}
693 ~delret() { *retired_ = true; }
694 };
695 auto foo3 = new delret(&retired);
696 myDomain0.retire(foo3);
697 }
698 ASSERT_TRUE(retired);
699 }
700
701 template <template <typename> class Atom = std::atomic>
cleanup_test()702 void cleanup_test() {
703 int threadOps = 1007;
704 int mainOps = 19;
705 c_.clear();
706 Atom<int> threadsDone{0};
707 Atom<bool> mainDone{false};
708 std::vector<std::thread> threads(FLAGS_num_threads);
709 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
710 threads[tid] = DSched::thread([&, tid]() {
711 for (int j = tid; j < threadOps; j += FLAGS_num_threads) {
712 auto p = new Node<Atom>;
713 p->retire();
714 }
715 threadsDone.fetch_add(1);
716 while (!mainDone.load()) {
717 /* spin */;
718 }
719 });
720 }
721 { // include the main thread in the test
722 for (int i = 0; i < mainOps; ++i) {
723 auto p = new Node<Atom>;
724 p->retire();
725 }
726 }
727 while (threadsDone.load() < FLAGS_num_threads) {
728 /* spin */;
729 }
730 ASSERT_EQ(c_.ctors(), threadOps + mainOps);
731 hazptr_cleanup<Atom>();
732 ASSERT_EQ(c_.dtors(), threadOps + mainOps);
733 mainDone.store(true);
734 for (auto& t : threads) {
735 DSched::join(t);
736 }
737 { // Cleanup after using array
738 c_.clear();
739 { hazptr_array<2, Atom> h = make_hazard_pointer_array<2, Atom>(); }
740 {
741 hazptr_array<2, Atom> h = make_hazard_pointer_array<2, Atom>();
742 auto p0 = new Node<Atom>;
743 auto p1 = new Node<Atom>;
744 h[0].reset_protection(p0);
745 h[1].reset_protection(p1);
746 p0->retire();
747 p1->retire();
748 }
749 ASSERT_EQ(c_.ctors(), 2);
750 hazptr_cleanup<Atom>();
751 ASSERT_EQ(c_.dtors(), 2);
752 }
753 { // Cleanup after using local
754 c_.clear();
755 { hazptr_local<2, Atom> h; }
756 {
757 hazptr_local<2, Atom> h;
758 auto p0 = new Node<Atom>;
759 auto p1 = new Node<Atom>;
760 h[0].reset_protection(p0);
761 h[1].reset_protection(p1);
762 p0->retire();
763 p1->retire();
764 }
765 ASSERT_EQ(c_.ctors(), 2);
766 hazptr_cleanup<Atom>();
767 ASSERT_EQ(c_.dtors(), 2);
768 }
769 }
770
771 template <template <typename> class Atom = std::atomic>
priv_dtor_test()772 void priv_dtor_test() {
773 c_.clear();
774 using NodeT = NodeRC<true, Atom>;
775 auto y = new NodeT;
776 y->acquire_link_safe();
777 struct Foo : hazptr_obj_base<Foo, Atom> {
778 hazptr_root<NodeT, Atom> r_;
779 };
780 auto x = new Foo;
781 x->r_().store(y);
782 /* Thread retires x. Dtor of TLS priv list pushes x to domain, which
783 triggers bulk reclaim due to timed cleanup (when the test is run
784 by itself). Reclamation of x unlinks and retires y. y should
785 not be pushed into the thread's priv list. It should be pushed to
786 domain instead. */
787 auto thr = DSched::thread([&]() { x->retire(); });
788 DSched::join(thr);
789 ASSERT_EQ(c_.ctors(), 1);
790 hazptr_cleanup<Atom>();
791 ASSERT_EQ(c_.dtors(), 1);
792 }
793
794 template <template <typename> class Atom = std::atomic>
cohort_test()795 void cohort_test() {
796 int num = 10001;
797 using NodeT = Node<Atom>;
798 c_.clear();
799 {
800 hazptr_obj_cohort<Atom> cohort;
801 auto thr = DSched::thread([&]() {
802 for (int i = 0; i < num; ++i) {
803 auto p = new NodeT;
804 p->set_cohort_no_tag(&cohort);
805 p->retire();
806 }
807 });
808 DSched::join(thr);
809 }
810 ASSERT_EQ(c_.ctors(), num);
811 // ASSERT_GT(c_.dtors(), 0);
812 hazptr_cleanup<Atom>();
813 c_.clear();
814 {
815 hazptr_obj_cohort<Atom> cohort;
816 auto thr = DSched::thread([&]() {
817 for (int i = 0; i < num; ++i) {
818 auto p = new NodeT;
819 p->set_cohort_tag(&cohort);
820 p->retire();
821 }
822 });
823 DSched::join(thr);
824 }
825 ASSERT_EQ(c_.ctors(), num);
826 ASSERT_GT(c_.dtors(), 0);
827 hazptr_cleanup<Atom>();
828 }
829
830 template <template <typename> class Atom = std::atomic>
recursive_destruction_test()831 void recursive_destruction_test() {
832 struct Foo : public hazptr_obj_base<Foo, Atom> {
833 hazptr_obj_cohort<Atom> cohort_;
834 Foo* foo_{nullptr};
835 explicit Foo(hazptr_obj_cohort<Atom>* b) {
836 this->set_cohort_tag(b);
837 c_.inc_ctors();
838 }
839 ~Foo() {
840 set(nullptr);
841 c_.inc_dtors();
842 }
843 void set(Foo* foo) {
844 if (foo_) {
845 foo_->retire();
846 }
847 foo_ = foo;
848 }
849 hazptr_obj_cohort<Atom>* cohort() { return &cohort_; }
850 };
851
852 int num1 = 101;
853 int num2 = 42;
854 int nthr = FLAGS_num_threads;
855 c_.clear();
856 std::vector<std::thread> threads(nthr);
857 for (int tid = 0; tid < nthr; ++tid) {
858 threads[tid] = DSched::thread([&, tid]() {
859 hazptr_obj_cohort<Atom> b0;
860 Foo* foo0 = new Foo(&b0);
861 for (int i = tid; i < num1; i += nthr) {
862 Foo* foo1 = new Foo(foo0->cohort());
863 foo0->set(foo1);
864 for (int j = 0; j < num2; ++j) {
865 foo1->set(new Foo(foo1->cohort()));
866 }
867 }
868 foo0->retire();
869 });
870 }
871 for (auto& t : threads) {
872 DSched::join(t);
873 }
874 int total = nthr + num1 + num1 * num2;
875 ASSERT_EQ(c_.ctors(), total);
876 ASSERT_EQ(c_.dtors(), total);
877 }
878
879 // Used in cohort_safe_list_children_test
880 struct NodeA : hazptr_obj_base_linked<NodeA> {
881 std::atomic<NodeA*> next_{nullptr};
882 int& sum_;
883 int val_;
884
NodeANodeA885 NodeA(hazptr_obj_cohort<>& coh, int& sum, int v = 0) : sum_(sum), val_(v) {
886 this->set_cohort_tag(&coh);
887 }
~NodeANodeA888 ~NodeA() { sum_ += val_; }
set_nextNodeA889 void set_next(NodeA* ptr) { next_.store(ptr); }
890 template <typename S>
push_linksNodeA891 void push_links(bool m, S& s) {
892 if (m) {
893 auto p = next_.load();
894 if (p) {
895 s.push(p);
896 }
897 }
898 }
899 };
900
cohort_safe_list_children_test()901 void cohort_safe_list_children_test() {
902 int sum = 0;
903 hazptr_obj_cohort<> cohort;
904 NodeA* p1 = new NodeA(cohort, sum, 1000);
905 NodeA* p2 = new NodeA(cohort, sum, 2000);
906 p2->acquire_link_safe();
907 p1->set_next(p2); // p2 is p1's child
908 hazard_pointer<> h = make_hazard_pointer<>();
909 h.reset_protection(p2);
910 /* When p1 is retired, it is inserted into cohort, then pushed into
911 the domain's tagged list, then when p1 is found unprotected by
912 hazard pointers it will be pushed into cohort's safe list. When
913 p1 is reclaimed, p2 (p1's child) will be automatically retired to
914 the domain's tagged list. */
915 p1->retire();
916 /* Retire enough nodes to invoke asynchronous reclamation until p1
917 and/or p2 are reclaimed. */
918 while (sum == 0) {
919 NodeA* p = new NodeA(cohort, sum);
920 p->retire();
921 }
922 /* At this point p1 must be already reclaimed but not p2 */
923 DCHECK_EQ(sum, 1000);
924 NodeA* p3 = new NodeA(cohort, sum, 3000);
925 p3->retire();
926 /* Retire more nodes to invoke asynchronous reclamation until p3
927 and/or p2 are reclaimed. */
928 while (sum == 1000) {
929 NodeA* p = new NodeA(cohort, sum);
930 p->retire();
931 }
932 /* At this point p3 must be already reclaimed but not p2 */
933 DCHECK_EQ(sum, 4000);
934 }
935
fork_test()936 void fork_test() {
937 folly::enable_hazptr_thread_pool_executor();
938 auto trigger_reclamation = [] {
939 hazptr_obj_cohort b;
940 for (int i = 0; i < 2001; ++i) {
941 auto p = new Node;
942 p->set_cohort_no_tag(&b);
943 p->retire();
944 }
945 };
946 std::thread t1(trigger_reclamation);
947 t1.join();
948 folly::SingletonVault::singleton()->destroyInstances();
949 auto pid = fork();
950 folly::SingletonVault::singleton()->reenableInstances();
951 if (pid > 0) {
952 // parent
953 int status = -1;
954 auto pid2 = waitpid(pid, &status, 0);
955 EXPECT_EQ(status, 0);
956 EXPECT_EQ(pid, pid2);
957 trigger_reclamation();
958 } else if (pid == 0) {
959 // child
960 c_.clear();
961 std::thread t2(trigger_reclamation);
962 t2.join();
963 exit(0); // Do not print gtest results
964 } else {
965 PLOG(FATAL) << "Failed to fork()";
966 }
967 }
968
969 template <template <typename> class Atom = std::atomic>
lifo_test()970 void lifo_test() {
971 for (int i = 0; i < FLAGS_num_reps; ++i) {
972 Atom<int> sum{0};
973 HazptrLockFreeLIFO<int, Atom> s;
974 std::vector<std::thread> threads(FLAGS_num_threads);
975 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
976 threads[tid] = DSched::thread([&, tid]() {
977 int local = 0;
978 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
979 s.push(j);
980 int v;
981 ASSERT_TRUE(s.pop(v));
982 local += v;
983 }
984 sum.fetch_add(local);
985 });
986 }
987 for (auto& t : threads) {
988 DSched::join(t);
989 }
990 hazptr_cleanup<Atom>();
991 int expected = FLAGS_num_ops * (FLAGS_num_ops - 1) / 2;
992 ASSERT_EQ(sum.load(), expected);
993 }
994 }
995
996 template <template <typename> class Atom = std::atomic>
swmr_test()997 void swmr_test() {
998 using T = uint64_t;
999 for (int i = 0; i < FLAGS_num_reps; ++i) {
1000 HazptrSWMRSet<T, Atom> s;
1001 std::vector<std::thread> threads(FLAGS_num_threads);
1002 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
1003 threads[tid] = DSched::thread([&s, tid]() {
1004 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
1005 s.contains(j);
1006 }
1007 });
1008 }
1009 for (int j = 0; j < 10; ++j) {
1010 s.add(j);
1011 }
1012 for (int j = 0; j < 10; ++j) {
1013 s.remove(j);
1014 }
1015 for (auto& t : threads) {
1016 DSched::join(t);
1017 }
1018 hazptr_cleanup<Atom>();
1019 }
1020 }
1021
1022 template <template <typename> class Atom = std::atomic>
wide_cas_test()1023 void wide_cas_test() {
1024 HazptrWideCAS<std::string, Atom> s;
1025 std::string u = "";
1026 std::string v = "11112222";
1027 auto ret = s.cas(u, v);
1028 ASSERT_TRUE(ret);
1029 u = "";
1030 v = "11112222";
1031 ret = s.cas(u, v);
1032 ASSERT_FALSE(ret);
1033 u = "11112222";
1034 v = "22223333";
1035 ret = s.cas(u, v);
1036 ASSERT_TRUE(ret);
1037 u = "22223333";
1038 v = "333344445555";
1039 ret = s.cas(u, v);
1040 ASSERT_TRUE(ret);
1041 hazptr_cleanup<Atom>();
1042 }
1043
1044 class HazptrPreInitTest : public testing::Test {
1045 private:
1046 // pre-init to avoid deadlock when using DeterministicAtomic
1047 hazptr_domain<DeterministicAtomic>& defaultDomainHelper_{
1048 folly::hazptr_default_domain_helper<DeterministicAtomic>::get()};
1049 };
1050
1051 // Tests
1052
TEST(HazptrTest,basic_objects)1053 TEST(HazptrTest, basic_objects) {
1054 basic_objects_test();
1055 }
1056
TEST_F(HazptrPreInitTest,dsched_basic_objects)1057 TEST_F(HazptrPreInitTest, dsched_basic_objects) {
1058 DSched sched(DSched::uniform(0));
1059 basic_objects_test<DeterministicAtomic>();
1060 }
1061
TEST(HazptrTest,copy_and_move)1062 TEST(HazptrTest, copy_and_move) {
1063 copy_and_move_test();
1064 }
1065
TEST_F(HazptrPreInitTest,dsched_copy_and_move)1066 TEST_F(HazptrPreInitTest, dsched_copy_and_move) {
1067 DSched sched(DSched::uniform(0));
1068 copy_and_move_test<DeterministicAtomic>();
1069 }
1070
TEST(HazptrTest,basic_holders)1071 TEST(HazptrTest, basic_holders) {
1072 basic_holders_test();
1073 }
1074
TEST_F(HazptrPreInitTest,dsched_basic_holders)1075 TEST_F(HazptrPreInitTest, dsched_basic_holders) {
1076 DSched sched(DSched::uniform(0));
1077 basic_holders_test<DeterministicAtomic>();
1078 }
1079
TEST(HazptrTest,basic_protection)1080 TEST(HazptrTest, basic_protection) {
1081 basic_protection_test();
1082 }
1083
TEST_F(HazptrPreInitTest,dsched_basic_protection)1084 TEST_F(HazptrPreInitTest, dsched_basic_protection) {
1085 DSched sched(DSched::uniform(0));
1086 basic_protection_test<DeterministicAtomic>();
1087 }
1088
TEST(HazptrTest,virtual)1089 TEST(HazptrTest, virtual) {
1090 virtual_test();
1091 }
1092
TEST_F(HazptrPreInitTest,dsched_virtual)1093 TEST_F(HazptrPreInitTest, dsched_virtual) {
1094 DSched sched(DSched::uniform(0));
1095 virtual_test<DeterministicAtomic>();
1096 }
1097
TEST(HazptrTest,destruction)1098 TEST(HazptrTest, destruction) {
1099 {
1100 hazptr_domain<> myDomain0;
1101 destruction_test(myDomain0);
1102 }
1103 destruction_test(default_hazptr_domain<std::atomic>());
1104 }
1105
TEST_F(HazptrPreInitTest,dsched_destruction)1106 TEST_F(HazptrPreInitTest, dsched_destruction) {
1107 DSched sched(DSched::uniform(0));
1108 {
1109 hazptr_domain<DeterministicAtomic> myDomain0;
1110 destruction_test<DeterministicAtomic>(myDomain0);
1111 }
1112 destruction_test<DeterministicAtomic>(
1113 default_hazptr_domain<DeterministicAtomic>());
1114 }
1115
TEST(HazptrTest,move)1116 TEST(HazptrTest, move) {
1117 move_test();
1118 }
1119
TEST_F(HazptrPreInitTest,dsched_move)1120 TEST_F(HazptrPreInitTest, dsched_move) {
1121 DSched sched(DSched::uniform(0));
1122 move_test<DeterministicAtomic>();
1123 }
1124
TEST(HazptrTest,array)1125 TEST(HazptrTest, array) {
1126 array_test();
1127 }
1128
TEST_F(HazptrPreInitTest,dsched_array)1129 TEST_F(HazptrPreInitTest, dsched_array) {
1130 DSched sched(DSched::uniform(0));
1131 array_test<DeterministicAtomic>();
1132 }
1133
TEST(HazptrTest,array_dtor_full_tc)1134 TEST(HazptrTest, array_dtor_full_tc) {
1135 array_dtor_full_tc_test();
1136 }
1137
TEST_F(HazptrPreInitTest,dsched_array_dtor_full_tc)1138 TEST_F(HazptrPreInitTest, dsched_array_dtor_full_tc) {
1139 DSched sched(DSched::uniform(0));
1140 array_dtor_full_tc_test<DeterministicAtomic>();
1141 }
1142
TEST(HazptrTest,local)1143 TEST(HazptrTest, local) {
1144 local_test();
1145 }
1146
TEST_F(HazptrPreInitTest,dsched_local)1147 TEST_F(HazptrPreInitTest, dsched_local) {
1148 DSched sched(DSched::uniform(0));
1149 local_test<DeterministicAtomic>();
1150 }
1151
TEST(HazptrTest,linked_mutable)1152 TEST(HazptrTest, linked_mutable) {
1153 linked_test<true>();
1154 }
1155
TEST_F(HazptrPreInitTest,dsched_linked_mutable)1156 TEST_F(HazptrPreInitTest, dsched_linked_mutable) {
1157 DSched sched(DSched::uniform(0));
1158 linked_test<true, DeterministicAtomic>();
1159 }
1160
TEST(HazptrTest,linked_immutable)1161 TEST(HazptrTest, linked_immutable) {
1162 linked_test<false>();
1163 }
1164
TEST_F(HazptrPreInitTest,dsched_linked_immutable)1165 TEST_F(HazptrPreInitTest, dsched_linked_immutable) {
1166 DSched sched(DSched::uniform(0));
1167 linked_test<false, DeterministicAtomic>();
1168 }
1169
TEST(HazptrTest,mt_linked_mutable)1170 TEST(HazptrTest, mt_linked_mutable) {
1171 mt_linked_test<true>();
1172 }
1173
TEST_F(HazptrPreInitTest,dsched_mt_linked_mutable)1174 TEST_F(HazptrPreInitTest, dsched_mt_linked_mutable) {
1175 DSched sched(DSched::uniform(0));
1176 mt_linked_test<true, DeterministicAtomic>();
1177 }
1178
TEST(HazptrTest,mt_linked_immutable)1179 TEST(HazptrTest, mt_linked_immutable) {
1180 mt_linked_test<false>();
1181 }
1182
TEST_F(HazptrPreInitTest,dsched_mt_linked_immutable)1183 TEST_F(HazptrPreInitTest, dsched_mt_linked_immutable) {
1184 DSched sched(DSched::uniform(0));
1185 mt_linked_test<false, DeterministicAtomic>();
1186 }
1187
TEST(HazptrTest,auto_retire)1188 TEST(HazptrTest, auto_retire) {
1189 auto_retire_test();
1190 }
1191
TEST_F(HazptrPreInitTest,dsched_auto_retire)1192 TEST_F(HazptrPreInitTest, dsched_auto_retire) {
1193 DSched sched(DSched::uniform(0));
1194 auto_retire_test<DeterministicAtomic>();
1195 }
1196
TEST(HazptrTest,free_function_retire)1197 TEST(HazptrTest, free_function_retire) {
1198 free_function_retire_test();
1199 }
1200
TEST_F(HazptrPreInitTest,dsched_free_function_retire)1201 TEST_F(HazptrPreInitTest, dsched_free_function_retire) {
1202 DSched sched(DSched::uniform(0));
1203 free_function_retire_test<DeterministicAtomic>();
1204 }
1205
TEST(HazptrTest,cleanup)1206 TEST(HazptrTest, cleanup) {
1207 cleanup_test();
1208 }
1209
TEST_F(HazptrPreInitTest,dsched_cleanup)1210 TEST_F(HazptrPreInitTest, dsched_cleanup) {
1211 DSched sched(DSched::uniform(0));
1212 cleanup_test<DeterministicAtomic>();
1213 }
1214
TEST(HazptrTest,priv_dtor)1215 TEST(HazptrTest, priv_dtor) {
1216 priv_dtor_test();
1217 }
1218
TEST_F(HazptrPreInitTest,dsched_priv_dtor)1219 TEST_F(HazptrPreInitTest, dsched_priv_dtor) {
1220 DSched sched(DSched::uniform(0));
1221 priv_dtor_test<DeterministicAtomic>();
1222 }
1223
TEST(HazptrTest,cohort)1224 TEST(HazptrTest, cohort) {
1225 cohort_test();
1226 }
1227
TEST(HazptrTest,dsched_cohort)1228 TEST(HazptrTest, dsched_cohort) {
1229 DSched sched(DSched::uniform(0));
1230 cohort_test<DeterministicAtomic>();
1231 }
1232
TEST(HazptrTest,recursive_destruction)1233 TEST(HazptrTest, recursive_destruction) {
1234 recursive_destruction_test();
1235 }
1236
TEST(HazptrTest,dsched_recursive_destruction)1237 TEST(HazptrTest, dsched_recursive_destruction) {
1238 recursive_destruction_test<DeterministicAtomic>();
1239 }
1240
TEST(HazptrTest,cohort_safe_list_children)1241 TEST(HazptrTest, cohort_safe_list_children) {
1242 cohort_safe_list_children_test();
1243 }
1244
TEST(HazptrTest,fork)1245 TEST(HazptrTest, fork) {
1246 fork_test();
1247 }
1248
TEST(HazptrTest,lifo)1249 TEST(HazptrTest, lifo) {
1250 lifo_test();
1251 }
1252
TEST_F(HazptrPreInitTest,dsched_lifo)1253 TEST_F(HazptrPreInitTest, dsched_lifo) {
1254 DSched sched(DSched::uniform(0));
1255 lifo_test<DeterministicAtomic>();
1256 }
1257
TEST(HazptrTest,swmr)1258 TEST(HazptrTest, swmr) {
1259 swmr_test();
1260 }
1261
TEST_F(HazptrPreInitTest,dsched_swmr)1262 TEST_F(HazptrPreInitTest, dsched_swmr) {
1263 DSched sched(DSched::uniform(0));
1264 swmr_test<DeterministicAtomic>();
1265 }
1266
TEST(HazptrTest,wide_cas)1267 TEST(HazptrTest, wide_cas) {
1268 wide_cas_test();
1269 }
1270
TEST_F(HazptrPreInitTest,dsched_wide_cas)1271 TEST_F(HazptrPreInitTest, dsched_wide_cas) {
1272 DSched sched(DSched::uniform(0));
1273 wide_cas_test<DeterministicAtomic>();
1274 }
1275
TEST(HazptrTest,reclamation_without_calling_cleanup)1276 TEST(HazptrTest, reclamation_without_calling_cleanup) {
1277 c_.clear();
1278 int nthr = 5;
1279 int objs = folly::detail::hazptr_domain_rcount_threshold();
1280 std::vector<std::thread> thr(nthr);
1281 for (int tid = 0; tid < nthr; ++tid) {
1282 thr[tid] = std::thread([&, tid] {
1283 for (int i = tid; i < objs; i += nthr) {
1284 auto p = new Node<>;
1285 p->retire();
1286 }
1287 });
1288 }
1289 for (auto& t : thr) {
1290 t.join();
1291 }
1292 while (c_.dtors() == 0)
1293 /* Wait for asynchronous reclamation. */;
1294 ASSERT_GT(c_.dtors(), 0);
1295 }
1296
TEST(HazptrTest,standard_names)1297 TEST(HazptrTest, standard_names) {
1298 struct Foo : hazard_pointer_obj_base<Foo> {};
1299 DCHECK_EQ(&hazard_pointer_default_domain<>(), &default_hazptr_domain<>());
1300 hazard_pointer<> h = make_hazard_pointer();
1301 hazard_pointer_clean_up<>();
1302 }
1303
1304 // Benchmark drivers
1305
1306 template <typename InitFunc, typename Func, typename EndFunc>
run_once(int nthreads,const InitFunc & init,const Func & fn,const EndFunc & endFn)1307 uint64_t run_once(
1308 int nthreads, const InitFunc& init, const Func& fn, const EndFunc& endFn) {
1309 Barrier b(nthreads + 1);
1310 init();
1311 std::vector<std::thread> threads(nthreads);
1312 for (int tid = 0; tid < nthreads; ++tid) {
1313 threads[tid] = std::thread([&, tid] {
1314 b.wait();
1315 b.wait();
1316 fn(tid);
1317 });
1318 }
1319 b.wait();
1320 // begin time measurement
1321 auto tbegin = std::chrono::steady_clock::now();
1322 b.wait();
1323 for (auto& t : threads) {
1324 t.join();
1325 }
1326 hazptr_cleanup();
1327 // end time measurement
1328 auto tend = std::chrono::steady_clock::now();
1329 endFn();
1330 return std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin)
1331 .count();
1332 }
1333
1334 template <typename RepFunc>
bench(std::string name,int ops,const RepFunc & repFn)1335 uint64_t bench(std::string name, int ops, const RepFunc& repFn) {
1336 int reps = 10;
1337 uint64_t min = UINTMAX_MAX;
1338 uint64_t max = 0;
1339 uint64_t sum = 0;
1340
1341 repFn(); // sometimes first run is outlier
1342 for (int r = 0; r < reps; ++r) {
1343 uint64_t dur = repFn();
1344 sum += dur;
1345 min = std::min(min, dur);
1346 max = std::max(max, dur);
1347 }
1348
1349 const std::string unit = " ns";
1350 uint64_t avg = sum / reps;
1351 uint64_t res = min;
1352 std::cout << name;
1353 std::cout << " " << std::setw(4) << max / ops << unit;
1354 std::cout << " " << std::setw(4) << avg / ops << unit;
1355 std::cout << " " << std::setw(4) << res / ops << unit;
1356 std::cout << std::endl;
1357 return res;
1358 }
1359
1360 //
1361 // Benchmarks
1362 //
1363 const int ops = 1000000;
1364
holder_bench(std::string name,int nthreads)1365 inline uint64_t holder_bench(std::string name, int nthreads) {
1366 auto repFn = [&] {
1367 auto init = [] {};
1368 auto fn = [&](int tid) {
1369 for (int j = tid; j < 10 * ops; j += nthreads) {
1370 hazptr_holder<> h = make_hazard_pointer<>();
1371 }
1372 };
1373 auto endFn = [] {};
1374 return run_once(nthreads, init, fn, endFn);
1375 };
1376 return bench(name, ops, repFn);
1377 }
1378
1379 template <size_t M>
array_bench(std::string name,int nthreads)1380 inline uint64_t array_bench(std::string name, int nthreads) {
1381 auto repFn = [&] {
1382 auto init = [] {};
1383 auto fn = [&](int tid) {
1384 for (int j = tid; j < 10 * ops; j += nthreads) {
1385 hazptr_array<M> a = make_hazard_pointer_array<M>();
1386 }
1387 };
1388 auto endFn = [] {};
1389 return run_once(nthreads, init, fn, endFn);
1390 };
1391 return bench(name, ops, repFn);
1392 }
1393
1394 template <size_t M>
local_bench(std::string name,int nthreads)1395 inline uint64_t local_bench(std::string name, int nthreads) {
1396 auto repFn = [&] {
1397 auto init = [] {};
1398 auto fn = [&](int tid) {
1399 for (int j = tid; j < 10 * ops; j += nthreads) {
1400 hazptr_local<M> a;
1401 }
1402 };
1403 auto endFn = [] {};
1404 return run_once(nthreads, init, fn, endFn);
1405 };
1406 return bench(name, ops, repFn);
1407 }
1408
obj_bench(std::string name,int nthreads)1409 inline uint64_t obj_bench(std::string name, int nthreads) {
1410 struct Foo : public hazptr_obj_base<Foo> {};
1411 auto repFn = [&] {
1412 auto init = [] {};
1413 auto fn = [&](int tid) {
1414 for (int j = tid; j < ops; j += nthreads) {
1415 auto p = new Foo;
1416 p->retire();
1417 }
1418 };
1419 auto endFn = [] {};
1420 return run_once(nthreads, init, fn, endFn);
1421 };
1422 return bench(name, ops, repFn);
1423 }
1424
list_hoh_bench(std::string name,int nthreads,int size,bool provided=false)1425 uint64_t list_hoh_bench(
1426 std::string name, int nthreads, int size, bool provided = false) {
1427 auto repFn = [&] {
1428 List<Node<>> l(size);
1429 auto init = [&] {};
1430 auto fn = [&](int tid) {
1431 if (provided) {
1432 hazptr_local<2> hptr;
1433 for (int j = tid; j < ops; j += nthreads) {
1434 l.hand_over_hand(size, &hptr[0], &hptr[1]);
1435 }
1436 } else {
1437 for (int j = tid; j < ops; j += nthreads) {
1438 l.hand_over_hand(size);
1439 }
1440 }
1441 };
1442 auto endFn = [] {};
1443 return run_once(nthreads, init, fn, endFn);
1444 };
1445 return bench(name, ops, repFn);
1446 }
1447
list_protect_all_bench(std::string name,int nthreads,int size,bool provided=false)1448 uint64_t list_protect_all_bench(
1449 std::string name, int nthreads, int size, bool provided = false) {
1450 auto repFn = [&] {
1451 List<NodeRC<false>> l(size);
1452 auto init = [] {};
1453 auto fn = [&](int tid) {
1454 if (provided) {
1455 hazptr_local<1> hptr;
1456 for (int j = tid; j < ops; j += nthreads) {
1457 l.protect_all(size, hptr[0]);
1458 }
1459 } else {
1460 for (int j = tid; j < ops; j += nthreads) {
1461 l.protect_all(size);
1462 }
1463 }
1464 };
1465 auto endFn = [] {};
1466 return run_once(nthreads, init, fn, endFn);
1467 };
1468 return bench(name, ops, repFn);
1469 }
1470
cleanup_bench(std::string name,int nthreads)1471 uint64_t cleanup_bench(std::string name, int nthreads) {
1472 auto repFn = [&] {
1473 auto init = [] {};
1474 auto fn = [&](int) {
1475 hazptr_holder<> hptr = make_hazard_pointer<>();
1476 for (int i = 0; i < ops / 1000; i++) {
1477 hazptr_cleanup();
1478 }
1479 };
1480 auto endFn = [] {};
1481 return run_once(nthreads, init, fn, endFn);
1482 };
1483 return bench(name, ops, repFn);
1484 }
1485
cohort_bench(std::string name,int nthreads)1486 uint64_t cohort_bench(std::string name, int nthreads) {
1487 struct Foo : public hazptr_obj_base<Foo> {};
1488 // Push unrelated objects into the domain tagged list
1489 hazptr_obj_cohort cohort;
1490 for (int i = 0; i < 999; ++i) {
1491 auto p = new Foo;
1492 p->set_cohort_tag(&cohort);
1493 p->retire();
1494 }
1495 auto repFn = [&] {
1496 auto init = [] {};
1497 auto fn = [&](int tid) {
1498 for (int j = tid; j < ops; j += nthreads) {
1499 hazptr_obj_cohort b;
1500 }
1501 };
1502 auto endFn = [] {};
1503 return run_once(nthreads, init, fn, endFn);
1504 };
1505 return bench(name, ops, repFn);
1506 }
1507
tc_miss_bench(std::string name,int nthreads)1508 uint64_t tc_miss_bench(std::string name, int nthreads) {
1509 hazptr_tc_evict();
1510 hazard_pointer_default_domain<>().delete_hazard_pointers();
1511 // Thread cache capacity
1512 constexpr int C = hazptr_tc<>::capacity();
1513 // Number of unavailable hazard pointers that will be at the head of
1514 // the main list of hazard pointers before reaching available ones.
1515 constexpr int N = 10000;
1516 // Max number of threads
1517 constexpr int P = 100;
1518 hazard_pointer<> aa[N + 2 * C * P];
1519 // The following creates N+2*C*P hazard pointers
1520 for (int i = 0; i < N + 2 * C * P; ++i) {
1521 aa[i] = make_hazard_pointer<>();
1522 }
1523 // Make the last 2*C*P in the domain's hazard pointer list available
1524 for (int i = 0; i < 2 * C * P; ++i) {
1525 aa[i] = hazard_pointer<>();
1526 }
1527 hazptr_tc_evict();
1528 // The domain now has N unavailable hazard pointers at the head of
1529 // the list following by C*P available ones.
1530 auto repFn = [&] {
1531 auto init = [] {};
1532 auto fn = [&](int tid) {
1533 for (int j = tid; j < ops; j += nthreads) {
1534 // By using twice the TC capacity, each iteration does one
1535 // filling and one eviction of the TC.
1536 hazptr_array<C> a1 = make_hazard_pointer_array<C>();
1537 hazptr_array<C> a2 = make_hazard_pointer_array<C>();
1538 }
1539 };
1540 auto endFn = [] {};
1541 return run_once(nthreads, init, fn, endFn);
1542 };
1543 return bench(name, ops, repFn);
1544 }
1545
1546 const int nthr[] = {1, 10};
1547 const int sizes[] = {10, 20};
1548
benches()1549 void benches() {
1550 for (int i : nthr) {
1551 std::cout << "================================ " << std::setw(2) << i
1552 << " threads "
1553 << "================================" << std::endl;
1554 std::cout << "10x construct/destruct hazptr_holder ";
1555 holder_bench("", i);
1556 std::cout << "10x construct/destruct hazptr_array<1> ";
1557 array_bench<1>("", i);
1558 std::cout << "10x construct/destruct hazptr_array<2> ";
1559 array_bench<2>("", i);
1560 std::cout << "10x construct/destruct hazptr_array<3> ";
1561 array_bench<3>("", i);
1562 std::cout << "10x construct/destruct hazptr_local<1> ";
1563 local_bench<1>("", i);
1564 std::cout << "10x construct/destruct hazptr_local<2> ";
1565 local_bench<2>("", i);
1566 std::cout << "10x construct/destruct hazptr_local<3> ";
1567 local_bench<3>("", i);
1568 std::cout << "10x construct/destruct hazptr_array<9> ";
1569 array_bench<9>("", i);
1570 std::cout << "TC hit + miss & overflow ";
1571 tc_miss_bench("", i);
1572 std::cout << "allocate/retire/reclaim object ";
1573 obj_bench("", i);
1574 for (int j : sizes) {
1575 std::cout << j << "-item list hand-over-hand - own hazptrs ";
1576 list_hoh_bench("", i, j, true);
1577 std::cout << j << "-item list hand-over-hand ";
1578 list_hoh_bench("", i, j);
1579 std::cout << j << "-item list protect all - own hazptr ";
1580 list_protect_all_bench("", i, j, true);
1581 std::cout << j << "-item list protect all ";
1582 list_protect_all_bench("", i, j);
1583 }
1584 std::cout << "1/1000 hazptr_cleanup ";
1585 cleanup_bench("", i);
1586 std::cout << "Life cycle of unused tagged obj cohort ";
1587 cohort_bench("", i);
1588 }
1589 }
1590
TEST(HazptrTest,bench)1591 TEST(HazptrTest, bench) {
1592 if (FLAGS_bench) {
1593 benches();
1594 }
1595 }
1596
1597 /*
1598 $ numactl -N 1 ./buck-out/gen/folly/synchronization/test/hazptr_test --bench
1599
1600 ================================ 1 threads ================================
1601 10x construct/destruct hazptr_holder 51 ns 51 ns 50 ns
1602 10x construct/destruct hazptr_array<1> 54 ns 52 ns 52 ns
1603 10x construct/destruct hazptr_array<2> 60 ns 59 ns 58 ns
1604 10x construct/destruct hazptr_array<3> 141 ns 88 ns 82 ns
1605 10x construct/destruct hazptr_local<1> 13 ns 12 ns 12 ns
1606 10x construct/destruct hazptr_local<2> 15 ns 15 ns 15 ns
1607 10x construct/destruct hazptr_local<3> 39 ns 39 ns 38 ns
1608 allocate/retire/reclaim object 70 ns 68 ns 67 ns
1609 10-item list hand-over-hand - own hazptrs 22 ns 20 ns 18 ns
1610 10-item list hand-over-hand 28 ns 25 ns 22 ns
1611 10-item list protect all - own hazptr 12 ns 11 ns 11 ns
1612 10-item list protect all 22 ns 13 ns 12 ns
1613 20-item list hand-over-hand - own hazptrs 42 ns 40 ns 38 ns
1614 20-item list hand-over-hand 48 ns 43 ns 41 ns
1615 20-item list protect all - own hazptr 28 ns 28 ns 28 ns
1616 20-item list protect all 31 ns 29 ns 29 ns
1617 1/1000 hazptr_cleanup 2 ns 1 ns 1 ns
1618 Life cycle of unused tagged obj cohort 1 ns 1 ns 1 ns
1619 ================================ 10 threads ================================
1620 10x construct/destruct hazptr_holder 11 ns 8 ns 8 ns
1621 10x construct/destruct hazptr_array<1> 8 ns 7 ns 7 ns
1622 10x construct/destruct hazptr_array<2> 9 ns 9 ns 9 ns
1623 10x construct/destruct hazptr_array<3> 19 ns 17 ns 14 ns
1624 10x construct/destruct hazptr_local<1> 8 ns 8 ns 8 ns
1625 10x construct/destruct hazptr_local<2> 8 ns 8 ns 7 ns
1626 10x construct/destruct hazptr_local<3> 11 ns 11 ns 10 ns
1627 allocate/retire/reclaim object 20 ns 17 ns 16 ns
1628 10-item list hand-over-hand - own hazptrs 3 ns 3 ns 3 ns
1629 10-item list hand-over-hand 3 ns 3 ns 3 ns
1630 10-item list protect all - own hazptr 2 ns 2 ns 2 ns
1631 10-item list protect all 2 ns 2 ns 2 ns
1632 20-item list hand-over-hand - own hazptrs 6 ns 6 ns 6 ns
1633 20-item list hand-over-hand 6 ns 6 ns 6 ns
1634 20-item list protect all - own hazptr 4 ns 4 ns 4 ns
1635 20-item list protect all 5 ns 4 ns 4 ns
1636 1/1000 hazptr_cleanup 119 ns 113 ns 97 ns
1637 Life cycle of unused tagged obj cohort 0 ns 0 ns 0 ns
1638 */
1639