folly/experimental/hazptr/test/HazptrTest.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   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 #define HAZPTR_DEBUG true
  17 #define HAZPTR_STATS true
  18 #define HAZPTR_SCAN_THRESHOLD 10
  19
  20 #include <folly/experimental/hazptr/test/HazptrUse1.h>
  21 #include <folly/experimental/hazptr/test/HazptrUse2.h>
  22 #include <folly/experimental/hazptr/example/LockFreeLIFO.h>
  23 #include <folly/experimental/hazptr/example/SWMRList.h>
  24 #include <folly/experimental/hazptr/example/WideCAS.h>
  25 #include <folly/experimental/hazptr/debug.h>
  26 #include <folly/experimental/hazptr/hazptr.h>
  27
  28 #include <folly/portability/GFlags.h>
  29 #include <folly/portability/GTest.h>
  30
  31 #include <thread>
  32
  33 DEFINE_int32(num_threads, 5, "Number of threads");
  34 DEFINE_int64(num_reps, 1, "Number of test reps");
  35 DEFINE_int64(num_ops, 10, "Number of ops or pairs of ops per rep");
  36
  37 using namespace folly::hazptr;
  38
  39 class HazptrTest : public testing::Test {
  40  public:
  41   HazptrTest() : Test() {
  42     DEBUG_PRINT("========== start of test scope");
  43   }
  44   ~HazptrTest() override {
  45     DEBUG_PRINT("========== end of test scope");
  46   }
  47 };
  48
  49 TEST_F(HazptrTest, Test1) {
  50   DEBUG_PRINT("");
  51   Node1* node0 = (Node1*)malloc(sizeof(Node1));
  52   DEBUG_PRINT("=== new    node0 " << node0 << " " << sizeof(*node0));
  53   Node1* node1 = (Node1*)malloc(sizeof(Node1));
  54   DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
  55   Node1* node2 = (Node1*)malloc(sizeof(Node1));
  56   DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
  57   Node1* node3 = (Node1*)malloc(sizeof(Node1));
  58   DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
  59
  60   DEBUG_PRINT("");
  61
  62   std::atomic<Node1*> shared0 = {node0};
  63   std::atomic<Node1*> shared1 = {node1};
  64   std::atomic<Node1*> shared2 = {node2};
  65   std::atomic<Node1*> shared3 = {node3};
  66
  67   MyMemoryResource myMr;
  68   DEBUG_PRINT("=== myMr " << &myMr);
  69   hazptr_domain myDomain0;
  70   DEBUG_PRINT("=== myDomain0 " << &myDomain0);
  71   hazptr_domain myDomain1(&myMr);
  72   DEBUG_PRINT("=== myDomain1 " << &myDomain1);
  73
  74   DEBUG_PRINT("");
  75
  76   DEBUG_PRINT("=== hptr0");
  77   hazptr_holder hptr0;
  78   DEBUG_PRINT("=== hptr1");
  79   hazptr_holder hptr1(myDomain0);
  80   DEBUG_PRINT("=== hptr2");
  81   hazptr_holder hptr2(myDomain1);
  82   DEBUG_PRINT("=== hptr3");
  83   hazptr_holder hptr3;
  84
  85   DEBUG_PRINT("");
  86
  87   Node1* n0 = shared0.load();
  88   Node1* n1 = shared1.load();
  89   Node1* n2 = shared2.load();
  90   Node1* n3 = shared3.load();
  91
  92   if (hptr0.try_protect(n0, shared0)) {}
  93   if (hptr1.try_protect(n1, shared1)) {}
  94   hptr1.reset();
  95   hptr1.reset(nullptr);
  96   hptr1.reset(n2);
  97   if (hptr2.try_protect(n3, shared3)) {}
  98   swap(hptr1, hptr2);
  99   hptr3.reset();
 100
 101   DEBUG_PRINT("");
 102
 103   DEBUG_PRINT("=== retire n0 " << n0);
 104   n0->retire();
 105   DEBUG_PRINT("=== retire n1 " << n1);
 106   n1->retire(default_hazptr_domain());
 107   DEBUG_PRINT("=== retire n2 " << n2);
 108   n2->retire(myDomain0);
 109   DEBUG_PRINT("=== retire n3 " << n3);
 110   n3->retire(myDomain1);
 111 }
 112
 113 TEST_F(HazptrTest, Test2) {
 114   Node2* node0 = new Node2;
 115   DEBUG_PRINT("=== new    node0 " << node0 << " " << sizeof(*node0));
 116   Node2* node1 = (Node2*)malloc(sizeof(Node2));
 117   DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
 118   Node2* node2 = (Node2*)malloc(sizeof(Node2));
 119   DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
 120   Node2* node3 = (Node2*)malloc(sizeof(Node2));
 121   DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
 122
 123   DEBUG_PRINT("");
 124
 125   std::atomic<Node2*> shared0 = {node0};
 126   std::atomic<Node2*> shared1 = {node1};
 127   std::atomic<Node2*> shared2 = {node2};
 128   std::atomic<Node2*> shared3 = {node3};
 129
 130   MineMemoryResource mineMr;
 131   DEBUG_PRINT("=== mineMr " << &mineMr);
 132   hazptr_domain mineDomain0;
 133   DEBUG_PRINT("=== mineDomain0 " << &mineDomain0);
 134   hazptr_domain mineDomain1(&mineMr);
 135   DEBUG_PRINT("=== mineDomain1 " << &mineDomain1);
 136
 137   DEBUG_PRINT("");
 138
 139   DEBUG_PRINT("=== hptr0");
 140   hazptr_holder hptr0;
 141   DEBUG_PRINT("=== hptr1");
 142   hazptr_holder hptr1(mineDomain0);
 143   DEBUG_PRINT("=== hptr2");
 144   hazptr_holder hptr2(mineDomain1);
 145   DEBUG_PRINT("=== hptr3");
 146   hazptr_holder hptr3;
 147
 148   DEBUG_PRINT("");
 149
 150   Node2* n0 = shared0.load();
 151   Node2* n1 = shared1.load();
 152   Node2* n2 = shared2.load();
 153   Node2* n3 = shared3.load();
 154
 155   if (hptr0.try_protect(n0, shared0)) {}
 156   if (hptr1.try_protect(n1, shared1)) {}
 157   hptr1.reset();
 158   hptr1.reset(n2);
 159   if (hptr2.try_protect(n3, shared3)) {}
 160   swap(hptr1, hptr2);
 161   hptr3.reset();
 162
 163   DEBUG_PRINT("");
 164
 165   DEBUG_PRINT("=== retire n0 " << n0);
 166   n0->retire(default_hazptr_domain(), &mineReclaimFnDelete);
 167   DEBUG_PRINT("=== retire n1 " << n1);
 168   n1->retire(default_hazptr_domain(), &mineReclaimFnFree);
 169   DEBUG_PRINT("=== retire n2 " << n2);
 170   n2->retire(mineDomain0, &mineReclaimFnFree);
 171   DEBUG_PRINT("=== retire n3 " << n3);
 172   n3->retire(mineDomain1, &mineReclaimFnFree);
 173 }
 174
 175 TEST_F(HazptrTest, LIFO) {
 176   using T = uint32_t;
 177   CHECK_GT(FLAGS_num_threads, 0);
 178   for (int i = 0; i < FLAGS_num_reps; ++i) {
 179     DEBUG_PRINT("========== start of rep scope");
 180     LockFreeLIFO<T> s;
 181     std::vector<std::thread> threads(FLAGS_num_threads);
 182     for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
 183       threads[tid] = std::thread([&s, tid]() {
 184         for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
 185           s.push(j);
 186           T res;
 187           while (!s.pop(res)) {}
 188         }
 189       });
 190     }
 191     for (auto& t : threads) {
 192       t.join();
 193     }
 194     DEBUG_PRINT("========== end of rep scope");
 195   }
 196 }
 197
 198 TEST_F(HazptrTest, SWMRLIST) {
 199   using T = uint64_t;
 200   hazptr_domain custom_domain;
 201
 202   CHECK_GT(FLAGS_num_threads, 0);
 203   for (int i = 0; i < FLAGS_num_reps; ++i) {
 204     DEBUG_PRINT("========== start of rep scope");
 205     SWMRListSet<T> s(custom_domain);
 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) {
 210           s.contains(j);
 211         }
 212       });
 213     }
 214     for (int j = 0; j < 10; ++j) {
 215       s.add(j);
 216     }
 217     for (int j = 0; j < 10; ++j) {
 218       s.remove(j);
 219     }
 220     for (auto& t : threads) {
 221       t.join();
 222     }
 223     DEBUG_PRINT("========== end of rep scope");
 224   }
 225 }
 226
 227 TEST_F(HazptrTest, WIDECAS) {
 228   WideCAS s;
 229   std::string u = "";
 230   std::string v = "11112222";
 231   auto ret = s.cas(u, v);
 232   CHECK(ret);
 233   u = "";
 234   v = "11112222";
 235   ret = s.cas(u, v);
 236   CHECK(!ret);
 237   u = "11112222";
 238   v = "22223333";
 239   ret = s.cas(u, v);
 240   CHECK(ret);
 241   u = "22223333";
 242   v = "333344445555";
 243   ret = s.cas(u, v);
 244   CHECK(ret);
 245 }
 246
 247 TEST_F(HazptrTest, VirtualTest) {
 248   struct Thing : public hazptr_obj_base<Thing> {
 249     virtual ~Thing() {
 250       DEBUG_PRINT("this: " << this << " &a: " << &a << " a: " << a);
 251     }
 252     int a;
 253   };
 254   for (int i = 0; i < 100; i++) {
 255     auto bar = new Thing;
 256     bar->a = i;
 257
 258     hazptr_holder hptr;
 259     hptr.reset(bar);
 260     bar->retire();
 261     EXPECT_EQ(bar->a, i);
 262   }
 263 }
 264
 265 void destructionTest(hazptr_domain& domain) {
 266   struct Thing : public hazptr_obj_base<Thing> {
 267     Thing* next;
 268     hazptr_domain* domain;
 269     int val;
 270     Thing(int v, Thing* n, hazptr_domain* d) : next(n), domain(d), val(v) {}
 271     ~Thing() {
 272       DEBUG_PRINT("this: " << this << " val: " << val << " next: " << next);
 273       if (next) {
 274         next->retire(*domain);
 275       }
 276     }
 277   };
 278   Thing* last{nullptr};
 279   for (int i = 0; i < 2000; i++) {
 280     last = new Thing(i, last, &domain);
 281   }
 282   last->retire(domain);
 283 }
 284
 285 TEST_F(HazptrTest, DestructionTest) {
 286   {
 287     hazptr_domain myDomain0;
 288     destructionTest(myDomain0);
 289   }
 290   destructionTest(default_hazptr_domain());
 291 }
 292
 293 TEST_F(HazptrTest, Move) {
 294   struct Foo : hazptr_obj_base<Foo> {
 295     int a;
 296   };
 297   for (int i = 0; i < 100; ++i) {
 298     Foo* x = new Foo;
 299     x->a = i;
 300     hazptr_holder hptr0;
 301     // Protect object
 302     hptr0.reset(x);
 303     // Retire object
 304     x->retire();
 305     // Move constructor - still protected
 306     hazptr_holder hptr1(std::move(hptr0));
 307     // Self move is no-op - still protected
 308     hazptr_holder* phptr1 = &hptr1;
 309     CHECK_EQ(phptr1, &hptr1);
 310     hptr1 = std::move(*phptr1);
 311     // Empty constructor
 312     hazptr_holder hptr2(nullptr);
 313     // Move assignment - still protected
 314     hptr2 = std::move(hptr1);
 315     // Access object
 316     CHECK_EQ(x->a, i);
 317     // Unprotect object - hptr2 is nonempty
 318     hptr2.reset();
 319   }
 320 }