folly/test/ConcurrentSkipListTest.cpp

   1 /*
   2  * Copyright 2011-present 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
  17 // @author: Xin Liu <xliux@fb.com>
  18
  19 #include <folly/ConcurrentSkipList.h>
  20
  21 #include <atomic>
  22 #include <memory>
  23 #include <set>
  24 #include <system_error>
  25 #include <thread>
  26 #include <vector>
  27
  28 #include <glog/logging.h>
  29
  30 #include <folly/Memory.h>
  31 #include <folly/String.h>
  32 #include <folly/container/Foreach.h>
  33 #include <folly/memory/Arena.h>
  34 #include <folly/portability/GFlags.h>
  35 #include <folly/portability/GTest.h>
  36
  37 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
  38
  39 namespace {
  40
  41 template <typename ParentAlloc>
  42 struct ParanoidArenaAlloc {
  43   explicit ParanoidArenaAlloc(ParentAlloc* arena) : arena_(arena) {}
  44
  45   void* allocate(size_t size) {
  46     void* result = arena_->allocate(size);
  47     allocated_.insert(result);
  48     return result;
  49   }
  50
  51   void deallocate(void* ptr) {
  52     EXPECT_EQ(1, allocated_.erase(ptr));
  53     arena_->deallocate(ptr);
  54   }
  55
  56   bool isEmpty() const { return allocated_.empty(); }
  57
  58   ParentAlloc* arena_;
  59   std::set<void*> allocated_;
  60 };
  61 } // namespace
  62
  63 namespace folly {
  64 template <>
  65 struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
  66 } // namespace folly
  67
  68 namespace {
  69
  70 using namespace folly;
  71 using std::vector;
  72
  73 typedef int ValueType;
  74 typedef detail::SkipListNode<ValueType> SkipListNodeType;
  75 typedef ConcurrentSkipList<ValueType> SkipListType;
  76 typedef SkipListType::Accessor SkipListAccessor;
  77 typedef vector<ValueType> VectorType;
  78 typedef std::set<ValueType> SetType;
  79
  80 static const int kHeadHeight = 2;
  81 static const int kMaxValue = 5000;
  82
  83 static void randomAdding(int size,
  84     SkipListAccessor skipList,
  85     SetType *verifier,
  86     int maxValue = kMaxValue) {
  87   for (int i = 0; i < size; ++i) {
  88     int32_t r = rand() % maxValue;
  89     verifier->insert(r);
  90     skipList.add(r);
  91   }
  92 }
  93
  94 static void randomRemoval(int size,
  95     SkipListAccessor skipList,
  96     SetType *verifier,
  97     int maxValue=kMaxValue) {
  98   for (int i = 0; i < size; ++i) {
  99     int32_t r = rand() % maxValue;
 100     verifier->insert(r);
 101     skipList.remove(r);
 102   }
 103 }
 104
 105 static void sumAllValues(SkipListAccessor skipList, int64_t *sum) {
 106   *sum = 0;
 107   FOR_EACH(it, skipList) {
 108     *sum += *it;
 109   }
 110   VLOG(20) << "sum = " << sum;
 111 }
 112
 113 static void concurrentSkip(const vector<ValueType> *values,
 114     SkipListAccessor skipList) {
 115   int64_t sum = 0;
 116   SkipListAccessor::Skipper skipper(skipList);
 117   FOR_EACH(it, *values) {
 118     if (skipper.to(*it)) {
 119       sum += *it;
 120     }
 121   }
 122   VLOG(20) << "sum = " << sum;
 123 }
 124
 125 bool verifyEqual(SkipListAccessor skipList,
 126     const SetType &verifier) {
 127   EXPECT_EQ(verifier.size(), skipList.size());
 128   FOR_EACH(it, verifier) {
 129     CHECK(skipList.contains(*it)) << *it;
 130     SkipListType::const_iterator iter = skipList.find(*it);
 131     CHECK(iter != skipList.end());
 132     EXPECT_EQ(*iter, *it);
 133   }
 134   EXPECT_TRUE(std::equal(verifier.begin(), verifier.end(), skipList.begin()));
 135   return true;
 136 }
 137
 138 TEST(ConcurrentSkipList, SequentialAccess) {
 139   {
 140     LOG(INFO) << "nodetype size=" << sizeof(SkipListNodeType);
 141
 142     auto skipList(SkipListType::create(kHeadHeight));
 143     EXPECT_TRUE(skipList.first() == nullptr);
 144     EXPECT_TRUE(skipList.last() == nullptr);
 145
 146     skipList.add(3);
 147     EXPECT_TRUE(skipList.contains(3));
 148     EXPECT_FALSE(skipList.contains(2));
 149     EXPECT_EQ(3, *skipList.first());
 150     EXPECT_EQ(3, *skipList.last());
 151
 152     EXPECT_EQ(3, *skipList.find(3));
 153     EXPECT_FALSE(skipList.find(3) == skipList.end());
 154     EXPECT_TRUE(skipList.find(2) == skipList.end());
 155
 156     {
 157       SkipListAccessor::Skipper skipper(skipList);
 158       skipper.to(3);
 159       CHECK_EQ(3, *skipper);
 160     }
 161
 162     skipList.add(2);
 163     EXPECT_EQ(2, *skipList.first());
 164     EXPECT_EQ(3, *skipList.last());
 165     skipList.add(5);
 166     EXPECT_EQ(5, *skipList.last());
 167     skipList.add(3);
 168     EXPECT_EQ(5, *skipList.last());
 169     auto ret = skipList.insert(9);
 170     EXPECT_EQ(9, *ret.first);
 171     EXPECT_TRUE(ret.second);
 172
 173     ret = skipList.insert(5);
 174     EXPECT_EQ(5, *ret.first);
 175     EXPECT_FALSE(ret.second);
 176
 177     EXPECT_EQ(2, *skipList.first());
 178     EXPECT_EQ(9, *skipList.last());
 179     EXPECT_TRUE(skipList.pop_back());
 180     EXPECT_EQ(5, *skipList.last());
 181     EXPECT_TRUE(skipList.pop_back());
 182     EXPECT_EQ(3, *skipList.last());
 183
 184     skipList.add(9);
 185     skipList.add(5);
 186
 187     CHECK(skipList.contains(2));
 188     CHECK(skipList.contains(3));
 189     CHECK(skipList.contains(5));
 190     CHECK(skipList.contains(9));
 191     CHECK(!skipList.contains(4));
 192
 193     // lower_bound
 194     auto it = skipList.lower_bound(5);
 195     EXPECT_EQ(5, *it);
 196     it = skipList.lower_bound(4);
 197     EXPECT_EQ(5, *it);
 198     it = skipList.lower_bound(9);
 199     EXPECT_EQ(9, *it);
 200     it = skipList.lower_bound(12);
 201     EXPECT_FALSE(it.good());
 202
 203     it = skipList.begin();
 204     EXPECT_EQ(2, *it);
 205
 206     // skipper test
 207     SkipListAccessor::Skipper skipper(skipList);
 208     skipper.to(3);
 209     EXPECT_EQ(3, skipper.data());
 210     skipper.to(5);
 211     EXPECT_EQ(5, skipper.data());
 212     CHECK(!skipper.to(7));
 213
 214     skipList.remove(5);
 215     skipList.remove(3);
 216     CHECK(skipper.to(9));
 217     EXPECT_EQ(9, skipper.data());
 218
 219     CHECK(!skipList.contains(3));
 220     skipList.add(3);
 221     CHECK(skipList.contains(3));
 222     int pos = 0;
 223     for (auto entry : skipList) {
 224       LOG(INFO) << "pos= " << pos++ << " value= " << entry;
 225     }
 226   }
 227
 228   {
 229     auto skipList(SkipListType::create(kHeadHeight));
 230
 231     SetType verifier;
 232     randomAdding(10000, skipList, &verifier);
 233     verifyEqual(skipList, verifier);
 234
 235     // test skipper
 236     SkipListAccessor::Skipper skipper(skipList);
 237     int num_skips = 1000;
 238     for (int i = 0; i < num_skips; ++i) {
 239       int n = i * kMaxValue / num_skips;
 240       bool found = skipper.to(n);
 241       EXPECT_EQ(found, (verifier.find(n) != verifier.end()));
 242     }
 243   }
 244
 245 }
 246
 247 static std::string makeRandomeString(int len) {
 248   std::string s;
 249   for (int j = 0; j < len; j++) {
 250     s.push_back((rand() % 26) + 'A');
 251   }
 252   return s;
 253 }
 254
 255 TEST(ConcurrentSkipList, TestStringType) {
 256   typedef folly::ConcurrentSkipList<std::string> SkipListT;
 257   std::shared_ptr<SkipListT> skip = SkipListT::createInstance();
 258   SkipListT::Accessor accessor(skip);
 259   {
 260     for (int i = 0; i < 100000; i++) {
 261       std::string s = makeRandomeString(7);
 262       accessor.insert(s);
 263     }
 264   }
 265   EXPECT_TRUE(std::is_sorted(accessor.begin(), accessor.end()));
 266 }
 267
 268 struct UniquePtrComp {
 269   bool operator ()(
 270       const std::unique_ptr<int> &x, const std::unique_ptr<int> &y) const {
 271     if (!x) {
 272       return false;
 273     }
 274     if (!y) {
 275       return true;
 276     }
 277     return *x < *y;
 278   }
 279 };
 280
 281 TEST(ConcurrentSkipList, TestMovableData) {
 282   typedef folly::ConcurrentSkipList<std::unique_ptr<int>, UniquePtrComp>
 283     SkipListT;
 284   auto sl = SkipListT::createInstance() ;
 285   SkipListT::Accessor accessor(sl);
 286
 287   static const int N = 10;
 288   for (int i = 0; i < N; ++i) {
 289     accessor.insert(std::make_unique<int>(i));
 290   }
 291
 292   for (int i = 0; i < N; ++i) {
 293     EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(i))) !=
 294         accessor.end());
 295   }
 296   EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(N))) ==
 297       accessor.end());
 298 }
 299
 300 void testConcurrentAdd(int numThreads) {
 301   auto skipList(SkipListType::create(kHeadHeight));
 302
 303   vector<std::thread> threads;
 304   vector<SetType> verifiers(numThreads);
 305   try {
 306     for (int i = 0; i < numThreads; ++i) {
 307       threads.push_back(std::thread(
 308             &randomAdding, 100, skipList, &verifiers[i], kMaxValue));
 309     }
 310   } catch (const std::system_error& e) {
 311     LOG(WARNING)
 312       << "Caught " << exceptionStr(e)
 313       << ": could only create " << threads.size() << " threads out of "
 314       << numThreads;
 315   }
 316   for (size_t i = 0; i < threads.size(); ++i) {
 317     threads[i].join();
 318   }
 319
 320   SetType all;
 321   FOR_EACH(s, verifiers) {
 322     all.insert(s->begin(), s->end());
 323   }
 324   verifyEqual(skipList, all);
 325 }
 326
 327 TEST(ConcurrentSkipList, ConcurrentAdd) {
 328   // test it many times
 329   for (int numThreads = 10; numThreads < 10000; numThreads += 1000) {
 330     testConcurrentAdd(numThreads);
 331   }
 332 }
 333
 334 void testConcurrentRemoval(int numThreads, int maxValue) {
 335   auto skipList = SkipListType::create(kHeadHeight);
 336   for (int i = 0; i < maxValue; ++i) {
 337     skipList.add(i);
 338   }
 339
 340   vector<std::thread> threads;
 341   vector<SetType > verifiers(numThreads);
 342   try {
 343     for (int i = 0; i < numThreads; ++i) {
 344       threads.push_back(std::thread(
 345             &randomRemoval, 100, skipList, &verifiers[i], maxValue));
 346     }
 347   } catch (const std::system_error& e) {
 348     LOG(WARNING)
 349       << "Caught " << exceptionStr(e)
 350       << ": could only create " << threads.size() << " threads out of "
 351       << numThreads;
 352   }
 353   FOR_EACH(t, threads) {
 354     (*t).join();
 355   }
 356
 357   SetType all;
 358   FOR_EACH(s, verifiers) {
 359     all.insert(s->begin(), s->end());
 360   }
 361
 362   CHECK_EQ(maxValue, all.size() + skipList.size());
 363   for (int i = 0; i < maxValue; ++i) {
 364     if (all.find(i) != all.end()) {
 365       CHECK(!skipList.contains(i)) << i;
 366     } else {
 367       CHECK(skipList.contains(i)) << i;
 368     }
 369   }
 370 }
 371
 372 TEST(ConcurrentSkipList, ConcurrentRemove) {
 373   for (int numThreads = 10; numThreads < 1000; numThreads += 100) {
 374     testConcurrentRemoval(numThreads, 100 * numThreads);
 375   }
 376 }
 377
 378 static void testConcurrentAccess(
 379     int numInsertions, int numDeletions, int maxValue) {
 380   auto skipList = SkipListType::create(kHeadHeight);
 381
 382   vector<SetType> verifiers(FLAGS_num_threads);
 383   vector<int64_t> sums(FLAGS_num_threads);
 384   vector<vector<ValueType> > skipValues(FLAGS_num_threads);
 385
 386   for (int i = 0; i < FLAGS_num_threads; ++i) {
 387     for (int j = 0; j < numInsertions; ++j) {
 388       skipValues[i].push_back(rand() % (maxValue + 1));
 389     }
 390     std::sort(skipValues[i].begin(), skipValues[i].end());
 391   }
 392
 393   vector<std::thread> threads;
 394   for (int i = 0; i < FLAGS_num_threads; ++i) {
 395     switch (i % 8) {
 396       case 0:
 397       case 1:
 398         threads.push_back(std::thread(
 399               randomAdding, numInsertions, skipList, &verifiers[i], maxValue));
 400         break;
 401       case 2:
 402         threads.push_back(std::thread(
 403               randomRemoval, numDeletions, skipList, &verifiers[i], maxValue));
 404         break;
 405       case 3:
 406         threads.push_back(std::thread(
 407               concurrentSkip, &skipValues[i], skipList));
 408         break;
 409       default:
 410         threads.push_back(std::thread(sumAllValues, skipList, &sums[i]));
 411         break;
 412     }
 413   }
 414
 415   FOR_EACH(t, threads) {
 416     (*t).join();
 417   }
 418   // just run through it, no need to verify the correctness.
 419 }
 420
 421 TEST(ConcurrentSkipList, ConcurrentAccess) {
 422   testConcurrentAccess(10000, 100, kMaxValue);
 423   testConcurrentAccess(100000, 10000, kMaxValue * 10);
 424   testConcurrentAccess(1000000, 100000, kMaxValue);
 425 }
 426
 427 struct NonTrivialValue {
 428   static std::atomic<int> InstanceCounter;
 429   static const int kBadPayLoad;
 430
 431   NonTrivialValue() : payload_(kBadPayLoad) { ++InstanceCounter; }
 432
 433   explicit NonTrivialValue(int payload) : payload_(payload) {
 434     ++InstanceCounter;
 435   }
 436
 437   NonTrivialValue(const NonTrivialValue& rhs) : payload_(rhs.payload_) {
 438     ++InstanceCounter;
 439   }
 440
 441   NonTrivialValue& operator=(const NonTrivialValue& rhs) {
 442     payload_ = rhs.payload_;
 443     return *this;
 444   }
 445
 446   ~NonTrivialValue() { --InstanceCounter; }
 447
 448   bool operator<(const NonTrivialValue& rhs) const {
 449     EXPECT_NE(kBadPayLoad, payload_);
 450     EXPECT_NE(kBadPayLoad, rhs.payload_);
 451     return payload_ < rhs.payload_;
 452   }
 453
 454  private:
 455   int payload_;
 456 };
 457
 458 std::atomic<int> NonTrivialValue::InstanceCounter(0);
 459 const int NonTrivialValue::kBadPayLoad = 0xDEADBEEF;
 460
 461 template <typename SkipListPtrType>
 462 void TestNonTrivialDeallocation(SkipListPtrType& list) {
 463   {
 464     auto accessor = typename SkipListPtrType::element_type::Accessor(list);
 465     static const size_t N = 10000;
 466     for (size_t i = 0; i < N; ++i) {
 467       accessor.add(NonTrivialValue(i));
 468     }
 469     list.reset();
 470   }
 471   EXPECT_EQ(0, NonTrivialValue::InstanceCounter);
 472 }
 473
 474 template <typename ParentAlloc>
 475 void NonTrivialDeallocationWithParanoid() {
 476   using Alloc = ParanoidArenaAlloc<ParentAlloc>;
 477   using ParanoidSkipListType =
 478       ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
 479   ParentAlloc parentAlloc;
 480   Alloc paranoidAlloc(&parentAlloc);
 481   auto list = ParanoidSkipListType::createInstance(10, paranoidAlloc);
 482   TestNonTrivialDeallocation(list);
 483   EXPECT_TRUE(paranoidAlloc.isEmpty());
 484 }
 485
 486 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
 487   NonTrivialDeallocationWithParanoid<SysAlloc>();
 488 }
 489
 490 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
 491   NonTrivialDeallocationWithParanoid<SysArena>();
 492 }
 493
 494 TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
 495   using SysArenaSkipListType =
 496       ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, SysArena>;
 497   auto list = SysArenaSkipListType::createInstance(10);
 498   TestNonTrivialDeallocation(list);
 499 }
 500
 501 } // namespace
 502
 503 int main(int argc, char* argv[]) {
 504   testing::InitGoogleTest(&argc, argv);
 505   google::InitGoogleLogging(argv[0]);
 506   gflags::ParseCommandLineFlags(&argc, &argv, true);
 507
 508   return RUN_ALL_TESTS();
 509 }