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/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>
  28
  29 #include <folly/portability/GFlags.h>
  30 #include <folly/portability/GTest.h>
  31
  32 #include <thread>
  33
  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");
  37
  38 using namespace folly::hazptr;
  39
  40 class HazptrTest : public testing::Test {
  41  public:
  42   HazptrTest() : Test() {
  43     DEBUG_PRINT("========== start of test scope");
  44   }
  45   ~HazptrTest() override {
  46     DEBUG_PRINT("========== end of test scope");
  47   }
  48 };
  49
  50 TEST_F(HazptrTest, Test1) {
  51   DEBUG_PRINT("");
  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));
  60
  61   DEBUG_PRINT("");
  62
  63   std::atomic<Node1*> shared0 = {node0};
  64   std::atomic<Node1*> shared1 = {node1};
  65   std::atomic<Node1*> shared2 = {node2};
  66   std::atomic<Node1*> shared3 = {node3};
  67
  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);
  74
  75   DEBUG_PRINT("");
  76
  77   DEBUG_PRINT("=== hptr0");
  78   hazptr_holder hptr0;
  79   DEBUG_PRINT("=== hptr1");
  80   hazptr_holder hptr1(myDomain0);
  81   DEBUG_PRINT("=== hptr2");
  82   hazptr_holder hptr2(myDomain1);
  83   DEBUG_PRINT("=== hptr3");
  84   hazptr_holder hptr3;
  85
  86   DEBUG_PRINT("");
  87
  88   Node1* n0 = shared0.load();
  89   Node1* n1 = shared1.load();
  90   Node1* n2 = shared2.load();
  91   Node1* n3 = shared3.load();
  92
  93   if (hptr0.try_protect(n0, shared0)) {}
  94   if (hptr1.try_protect(n1, shared1)) {}
  95   hptr1.reset();
  96   hptr1.reset(nullptr);
  97   hptr1.reset(n2);
  98   if (hptr2.try_protect(n3, shared3)) {}
  99   swap(hptr1, hptr2);
 100   hptr3.reset();
 101
 102   DEBUG_PRINT("");
 103
 104   DEBUG_PRINT("=== retire n0 " << n0);
 105   n0->retire();
 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);
 112 }
 113
 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));
 123
 124   DEBUG_PRINT("");
 125
 126   std::atomic<Node2*> shared0 = {node0};
 127   std::atomic<Node2*> shared1 = {node1};
 128   std::atomic<Node2*> shared2 = {node2};
 129   std::atomic<Node2*> shared3 = {node3};
 130
 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);
 137
 138   DEBUG_PRINT("");
 139
 140   DEBUG_PRINT("=== hptr0");
 141   hazptr_holder hptr0;
 142   DEBUG_PRINT("=== hptr1");
 143   hazptr_holder hptr1(mineDomain0);
 144   DEBUG_PRINT("=== hptr2");
 145   hazptr_holder hptr2(mineDomain1);
 146   DEBUG_PRINT("=== hptr3");
 147   hazptr_holder hptr3;
 148
 149   DEBUG_PRINT("");
 150
 151   Node2* n0 = shared0.load();
 152   Node2* n1 = shared1.load();
 153   Node2* n2 = shared2.load();
 154   Node2* n3 = shared3.load();
 155
 156   if (hptr0.try_protect(n0, shared0)) {}
 157   if (hptr1.try_protect(n1, shared1)) {}
 158   hptr1.reset();
 159   hptr1.reset(n2);
 160   if (hptr2.try_protect(n3, shared3)) {}
 161   swap(hptr1, hptr2);
 162   hptr3.reset();
 163
 164   DEBUG_PRINT("");
 165
 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);
 174 }
 175
 176 TEST_F(HazptrTest, LIFO) {
 177   using T = uint32_t;
 178   CHECK_GT(FLAGS_num_threads, 0);
 179   for (int i = 0; i < FLAGS_num_reps; ++i) {
 180     DEBUG_PRINT("========== start of rep scope");
 181     LockFreeLIFO<T> s;
 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) {
 186           s.push(j);
 187           T res;
 188           while (!s.pop(res)) {}
 189         }
 190       });
 191     }
 192     for (auto& t : threads) {
 193       t.join();
 194     }
 195     DEBUG_PRINT("========== end of rep scope");
 196   }
 197 }
 198
 199 TEST_F(HazptrTest, SWMRLIST) {
 200   using T = uint64_t;
 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;
 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, MWMRSet) {
 228   using T = uint64_t;
 229
 230   CHECK_GT(FLAGS_num_threads, 0);
 231   for (int i = 0; i < FLAGS_num_reps; ++i) {
 232     DEBUG_PRINT("========== start of rep scope");
 233     MWMRListSet<T> s;
 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) {
 238           s.contains(j);
 239           s.add(j);
 240           s.remove(j);
 241         }
 242       });
 243     }
 244     for (int j = 0; j < 10; ++j) {
 245       s.add(j);
 246     }
 247     for (int j = 0; j < 10; ++j) {
 248       s.remove(j);
 249     }
 250     for (auto& t : threads) {
 251       t.join();
 252     }
 253     DEBUG_PRINT("========== end of rep scope");
 254   }
 255 }
 256
 257 TEST_F(HazptrTest, WIDECAS) {
 258   WideCAS s;
 259   std::string u = "";
 260   std::string v = "11112222";
 261   auto ret = s.cas(u, v);
 262   CHECK(ret);
 263   u = "";
 264   v = "11112222";
 265   ret = s.cas(u, v);
 266   CHECK(!ret);
 267   u = "11112222";
 268   v = "22223333";
 269   ret = s.cas(u, v);
 270   CHECK(ret);
 271   u = "22223333";
 272   v = "333344445555";
 273   ret = s.cas(u, v);
 274   CHECK(ret);
 275 }
 276
 277 TEST_F(HazptrTest, VirtualTest) {
 278   struct Thing : public hazptr_obj_base<Thing> {
 279     virtual ~Thing() {
 280       DEBUG_PRINT("this: " << this << " &a: " << &a << " a: " << a);
 281     }
 282     int a;
 283   };
 284   for (int i = 0; i < 100; i++) {
 285     auto bar = new Thing;
 286     bar->a = i;
 287
 288     hazptr_holder hptr;
 289     hptr.reset(bar);
 290     bar->retire();
 291     EXPECT_EQ(bar->a, i);
 292   }
 293 }
 294
 295 void destructionTest(hazptr_domain& domain) {
 296   struct Thing : public hazptr_obj_base<Thing> {
 297     Thing* next;
 298     hazptr_domain* domain;
 299     int val;
 300     Thing(int v, Thing* n, hazptr_domain* d) : next(n), domain(d), val(v) {}
 301     ~Thing() {
 302       DEBUG_PRINT("this: " << this << " val: " << val << " next: " << next);
 303       if (next) {
 304         next->retire(*domain);
 305       }
 306     }
 307   };
 308   Thing* last{nullptr};
 309   for (int i = 0; i < 2000; i++) {
 310     last = new Thing(i, last, &domain);
 311   }
 312   last->retire(domain);
 313 }
 314
 315 TEST_F(HazptrTest, DestructionTest) {
 316   {
 317     hazptr_domain myDomain0;
 318     destructionTest(myDomain0);
 319   }
 320   destructionTest(default_hazptr_domain());
 321 }
 322
 323 TEST_F(HazptrTest, Move) {
 324   struct Foo : hazptr_obj_base<Foo> {
 325     int a;
 326   };
 327   for (int i = 0; i < 100; ++i) {
 328     Foo* x = new Foo;
 329     x->a = i;
 330     hazptr_holder hptr0;
 331     // Protect object
 332     hptr0.reset(x);
 333     // Retire object
 334     x->retire();
 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);
 341     // Empty constructor
 342     hazptr_holder hptr2(nullptr);
 343     // Move assignment - still protected
 344     hptr2 = std::move(hptr1);
 345     // Access object
 346     CHECK_EQ(x->a, i);
 347     // Unprotect object - hptr2 is nonempty
 348     hptr2.reset();
 349   }
 350 }
 351
 352 TEST_F(HazptrTest, Array) {
 353   struct Foo : hazptr_obj_base<Foo> {
 354     int a;
 355   };
 356   for (int i = 0; i < 100; ++i) {
 357     Foo* x = new Foo;
 358     x->a = i;
 359     hazptr_array<10> hptr;
 360     // Protect object
 361     hptr[9].reset(x);
 362     // Empty array
 363     hazptr_array<10> h(nullptr);
 364     // Move assignment
 365     h = std::move(hptr);
 366     // Retire object
 367     x->retire();
 368     // Unprotect object - hptr2 is nonempty
 369     h[9].reset();
 370   }
 371   {
 372     // Abnormal case
 373     hazptr_array<HAZPTR_TC_SIZE + 1> h;
 374   }
 375 }
 376
 377 TEST_F(HazptrTest, Local) {
 378   struct Foo : hazptr_obj_base<Foo> {
 379     int a;
 380   };
 381   for (int i = 0; i < 100; ++i) {
 382     Foo* x = new Foo;
 383     x->a = i;
 384     hazptr_local<10> hptr;
 385     // Protect object
 386     hptr[9].reset(x);
 387     // Retire object
 388     x->retire();
 389     // Unprotect object - hptr2 is nonempty
 390     hptr[9].reset();
 391   }
 392   {
 393     // Abnormal case
 394     hazptr_local<HAZPTR_TC_SIZE + 1> h;
 395   }
 396 }