2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #define HAZPTR_DEBUG true
17 #define HAZPTR_STATS true
18 #define HAZPTR_SCAN_THRESHOLD 10
20 #include <folly/experimental/hazptr/debug.h>
21 #include <folly/experimental/hazptr/example/LockFreeLIFO.h>
22 #include <folly/experimental/hazptr/example/MWMRSet.h>
23 #include <folly/experimental/hazptr/example/SWMRList.h>
24 #include <folly/experimental/hazptr/example/WideCAS.h>
25 #include <folly/experimental/hazptr/hazptr.h>
26 #include <folly/experimental/hazptr/test/HazptrUse1.h>
27 #include <folly/experimental/hazptr/test/HazptrUse2.h>
29 #include <folly/portability/GFlags.h>
30 #include <folly/portability/GTest.h>
34 DEFINE_int32(num_threads, 5, "Number of threads");
35 DEFINE_int64(num_reps, 1, "Number of test reps");
36 DEFINE_int64(num_ops, 10, "Number of ops or pairs of ops per rep");
38 using namespace folly::hazptr;
40 class HazptrTest : public testing::Test {
42 HazptrTest() : Test() {
43 DEBUG_PRINT("========== start of test scope");
45 ~HazptrTest() override {
46 DEBUG_PRINT("========== end of test scope");
50 TEST_F(HazptrTest, Test1) {
52 Node1* node0 = (Node1*)malloc(sizeof(Node1));
53 DEBUG_PRINT("=== new node0 " << node0 << " " << sizeof(*node0));
54 Node1* node1 = (Node1*)malloc(sizeof(Node1));
55 DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
56 Node1* node2 = (Node1*)malloc(sizeof(Node1));
57 DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
58 Node1* node3 = (Node1*)malloc(sizeof(Node1));
59 DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
63 std::atomic<Node1*> shared0 = {node0};
64 std::atomic<Node1*> shared1 = {node1};
65 std::atomic<Node1*> shared2 = {node2};
66 std::atomic<Node1*> shared3 = {node3};
68 MyMemoryResource myMr;
69 DEBUG_PRINT("=== myMr " << &myMr);
70 hazptr_domain myDomain0;
71 DEBUG_PRINT("=== myDomain0 " << &myDomain0);
72 hazptr_domain myDomain1(&myMr);
73 DEBUG_PRINT("=== myDomain1 " << &myDomain1);
77 DEBUG_PRINT("=== hptr0");
79 DEBUG_PRINT("=== hptr1");
80 hazptr_holder hptr1(myDomain0);
81 DEBUG_PRINT("=== hptr2");
82 hazptr_holder hptr2(myDomain1);
83 DEBUG_PRINT("=== hptr3");
88 Node1* n0 = shared0.load();
89 Node1* n1 = shared1.load();
90 Node1* n2 = shared2.load();
91 Node1* n3 = shared3.load();
93 if (hptr0.try_protect(n0, shared0)) {}
94 if (hptr1.try_protect(n1, shared1)) {}
98 if (hptr2.try_protect(n3, shared3)) {}
104 DEBUG_PRINT("=== retire n0 " << n0);
106 DEBUG_PRINT("=== retire n1 " << n1);
107 n1->retire(default_hazptr_domain());
108 DEBUG_PRINT("=== retire n2 " << n2);
109 n2->retire(myDomain0);
110 DEBUG_PRINT("=== retire n3 " << n3);
111 n3->retire(myDomain1);
114 TEST_F(HazptrTest, Test2) {
115 Node2* node0 = new Node2;
116 DEBUG_PRINT("=== new node0 " << node0 << " " << sizeof(*node0));
117 Node2* node1 = (Node2*)malloc(sizeof(Node2));
118 DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
119 Node2* node2 = (Node2*)malloc(sizeof(Node2));
120 DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
121 Node2* node3 = (Node2*)malloc(sizeof(Node2));
122 DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
126 std::atomic<Node2*> shared0 = {node0};
127 std::atomic<Node2*> shared1 = {node1};
128 std::atomic<Node2*> shared2 = {node2};
129 std::atomic<Node2*> shared3 = {node3};
131 MineMemoryResource mineMr;
132 DEBUG_PRINT("=== mineMr " << &mineMr);
133 hazptr_domain mineDomain0;
134 DEBUG_PRINT("=== mineDomain0 " << &mineDomain0);
135 hazptr_domain mineDomain1(&mineMr);
136 DEBUG_PRINT("=== mineDomain1 " << &mineDomain1);
140 DEBUG_PRINT("=== hptr0");
142 DEBUG_PRINT("=== hptr1");
143 hazptr_holder hptr1(mineDomain0);
144 DEBUG_PRINT("=== hptr2");
145 hazptr_holder hptr2(mineDomain1);
146 DEBUG_PRINT("=== hptr3");
151 Node2* n0 = shared0.load();
152 Node2* n1 = shared1.load();
153 Node2* n2 = shared2.load();
154 Node2* n3 = shared3.load();
156 if (hptr0.try_protect(n0, shared0)) {}
157 if (hptr1.try_protect(n1, shared1)) {}
160 if (hptr2.try_protect(n3, shared3)) {}
166 DEBUG_PRINT("=== retire n0 " << n0);
167 n0->retire(default_hazptr_domain(), &mineReclaimFnDelete);
168 DEBUG_PRINT("=== retire n1 " << n1);
169 n1->retire(default_hazptr_domain(), &mineReclaimFnFree);
170 DEBUG_PRINT("=== retire n2 " << n2);
171 n2->retire(mineDomain0, &mineReclaimFnFree);
172 DEBUG_PRINT("=== retire n3 " << n3);
173 n3->retire(mineDomain1, &mineReclaimFnFree);
176 TEST_F(HazptrTest, LIFO) {
178 CHECK_GT(FLAGS_num_threads, 0);
179 for (int i = 0; i < FLAGS_num_reps; ++i) {
180 DEBUG_PRINT("========== start of rep scope");
182 std::vector<std::thread> threads(FLAGS_num_threads);
183 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
184 threads[tid] = std::thread([&s, tid]() {
185 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
188 while (!s.pop(res)) {}
192 for (auto& t : threads) {
195 DEBUG_PRINT("========== end of rep scope");
199 TEST_F(HazptrTest, SWMRLIST) {
202 CHECK_GT(FLAGS_num_threads, 0);
203 for (int i = 0; i < FLAGS_num_reps; ++i) {
204 DEBUG_PRINT("========== start of rep scope");
206 std::vector<std::thread> threads(FLAGS_num_threads);
207 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
208 threads[tid] = std::thread([&s, tid]() {
209 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
214 for (int j = 0; j < 10; ++j) {
217 for (int j = 0; j < 10; ++j) {
220 for (auto& t : threads) {
223 DEBUG_PRINT("========== end of rep scope");
227 TEST_F(HazptrTest, MWMRSet) {
230 CHECK_GT(FLAGS_num_threads, 0);
231 for (int i = 0; i < FLAGS_num_reps; ++i) {
232 DEBUG_PRINT("========== start of rep scope");
234 std::vector<std::thread> threads(FLAGS_num_threads);
235 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
236 threads[tid] = std::thread([&s, tid]() {
237 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
244 for (int j = 0; j < 10; ++j) {
247 for (int j = 0; j < 10; ++j) {
250 for (auto& t : threads) {
253 DEBUG_PRINT("========== end of rep scope");
257 TEST_F(HazptrTest, WIDECAS) {
260 std::string v = "11112222";
261 auto ret = s.cas(u, v);
277 TEST_F(HazptrTest, VirtualTest) {
278 struct Thing : public hazptr_obj_base<Thing> {
280 DEBUG_PRINT("this: " << this << " &a: " << &a << " a: " << a);
284 for (int i = 0; i < 100; i++) {
285 auto bar = new Thing;
291 EXPECT_EQ(bar->a, i);
295 void destructionTest(hazptr_domain& domain) {
296 struct Thing : public hazptr_obj_base<Thing> {
298 hazptr_domain* domain;
300 Thing(int v, Thing* n, hazptr_domain* d) : next(n), domain(d), val(v) {}
302 DEBUG_PRINT("this: " << this << " val: " << val << " next: " << next);
304 next->retire(*domain);
308 Thing* last{nullptr};
309 for (int i = 0; i < 2000; i++) {
310 last = new Thing(i, last, &domain);
312 last->retire(domain);
315 TEST_F(HazptrTest, DestructionTest) {
317 hazptr_domain myDomain0;
318 destructionTest(myDomain0);
320 destructionTest(default_hazptr_domain());
323 TEST_F(HazptrTest, Move) {
324 struct Foo : hazptr_obj_base<Foo> {
327 for (int i = 0; i < 100; ++i) {
335 // Move constructor - still protected
336 hazptr_holder hptr1(std::move(hptr0));
337 // Self move is no-op - still protected
338 hazptr_holder* phptr1 = &hptr1;
339 CHECK_EQ(phptr1, &hptr1);
340 hptr1 = std::move(*phptr1);
342 hazptr_holder hptr2(nullptr);
343 // Move assignment - still protected
344 hptr2 = std::move(hptr1);
347 // Unprotect object - hptr2 is nonempty
352 TEST_F(HazptrTest, Array) {
353 struct Foo : hazptr_obj_base<Foo> {
356 for (int i = 0; i < 100; ++i) {
359 hazptr_array<10> hptr;
368 // Unprotect object - hptr2 is nonempty
373 hazptr_array<HAZPTR_TC_SIZE + 1> h;
377 TEST_F(HazptrTest, Local) {
378 struct Foo : hazptr_obj_base<Foo> {
381 for (int i = 0; i < 100; ++i) {
384 hazptr_local<10> hptr;
389 // Unprotect object - hptr2 is nonempty
394 hazptr_local<HAZPTR_TC_SIZE + 1> h;