folly/experimental/hazptr/test/HazptrTest.cpp

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