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