folly/test/SynchronizedTestLib-inl.h

   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
  17 #pragma once
  18
  19 #include <gtest/gtest.h>
  20
  21 #include <folly/Foreach.h>
  22 #include <folly/Random.h>
  23 #include <folly/Synchronized.h>
  24 #include <glog/logging.h>
  25 #include <algorithm>
  26 #include <condition_variable>
  27 #include <functional>
  28 #include <map>
  29 #include <random>
  30 #include <thread>
  31 #include <vector>
  32
  33 namespace folly {
  34 namespace sync_tests {
  35
  36 inline std::mt19937& getRNG() {
  37   static const auto seed = folly::randomNumberSeed();
  38   static std::mt19937 rng(seed);
  39   return rng;
  40 }
  41
  42 void randomSleep(std::chrono::milliseconds min, std::chrono::milliseconds max) {
  43   std::uniform_int_distribution<> range(min.count(), max.count());
  44   std::chrono::milliseconds duration(range(getRNG()));
  45   std::this_thread::sleep_for(duration);
  46 }
  47
  48 /*
  49  * Run a functon simultaneously in a number of different threads.
  50  *
  51  * The function will be passed the index number of the thread it is running in.
  52  * This function makes an attempt to synchronize the start of the threads as
  53  * best as possible.  It waits for all threads to be allocated and started
  54  * before invoking the function.
  55  */
  56 template <class Function>
  57 void runParallel(size_t numThreads, const Function& function) {
  58   std::vector<std::thread> threads;
  59   threads.reserve(numThreads);
  60
  61   // Variables used to synchronize all threads to try and start them
  62   // as close to the same time as possible
  63   folly::Synchronized<size_t, std::mutex> threadsReady(0);
  64   std::condition_variable readyCV;
  65   folly::Synchronized<bool, std::mutex> go(false);
  66   std::condition_variable goCV;
  67
  68   auto worker = [&](size_t threadIndex) {
  69     // Signal that we are ready
  70     ++(*threadsReady.lock());
  71     readyCV.notify_one();
  72
  73     // Wait until we are given the signal to start
  74     // The purpose of this is to try and make sure all threads start
  75     // as close to the same time as possible.
  76     {
  77       auto lockedGo = go.lock();
  78       goCV.wait(lockedGo.getUniqueLock(), [&] { return *lockedGo; });
  79     }
  80
  81     function(threadIndex);
  82   };
  83
  84   // Start all of the threads
  85   for (size_t threadIndex = 0; threadIndex < numThreads; ++threadIndex) {
  86     threads.emplace_back([threadIndex, &worker]() { worker(threadIndex); });
  87   }
  88
  89   // Wait for all threads to become ready
  90   {
  91     auto readyLocked = threadsReady.lock();
  92     readyCV.wait(readyLocked.getUniqueLock(), [&] {
  93       return *readyLocked == numThreads;
  94     });
  95   }
  96   // Now signal the threads that they can go
  97   go = true;
  98   goCV.notify_all();
  99
 100   // Wait for all threads to finish
 101   for (auto& thread : threads) {
 102     thread.join();
 103   }
 104 }
 105
 106 // testBasic() version for shared lock types
 107 template <class Mutex>
 108 typename std::enable_if<folly::LockTraits<Mutex>::is_shared>::type
 109 testBasicImpl() {
 110   folly::Synchronized<std::vector<int>, Mutex> obj;
 111
 112   obj.wlock()->resize(1000);
 113
 114   folly::Synchronized<std::vector<int>, Mutex> obj2{*obj.wlock()};
 115   EXPECT_EQ(1000, obj2.rlock()->size());
 116
 117   {
 118     auto lockedObj = obj.wlock();
 119     lockedObj->push_back(10);
 120     EXPECT_EQ(1001, lockedObj->size());
 121     EXPECT_EQ(10, lockedObj->back());
 122     EXPECT_EQ(1000, obj2.wlock()->size());
 123     EXPECT_EQ(1000, obj2.rlock()->size());
 124
 125     {
 126       auto unlocker = lockedObj.scopedUnlock();
 127       EXPECT_EQ(1001, obj.wlock()->size());
 128     }
 129   }
 130
 131   {
 132     auto lockedObj = obj.rlock();
 133     EXPECT_EQ(1001, lockedObj->size());
 134     EXPECT_EQ(1001, obj.rlock()->size());
 135     {
 136       auto unlocker = lockedObj.scopedUnlock();
 137       EXPECT_EQ(1001, obj.wlock()->size());
 138     }
 139   }
 140
 141   obj.wlock()->front() = 2;
 142
 143   {
 144     const auto& constObj = obj;
 145     // contextualLock() on a const reference should grab a shared lock
 146     auto lockedObj = constObj.contextualLock();
 147     EXPECT_EQ(2, lockedObj->front());
 148     EXPECT_EQ(2, constObj.rlock()->front());
 149     EXPECT_EQ(2, obj.rlock()->front());
 150   }
 151
 152   EXPECT_EQ(1001, obj.rlock()->size());
 153   EXPECT_EQ(2, obj.rlock()->front());
 154   EXPECT_EQ(10, obj.rlock()->back());
 155   EXPECT_EQ(1000, obj2.rlock()->size());
 156 }
 157
 158 // testBasic() version for non-shared lock types
 159 template <class Mutex>
 160 typename std::enable_if<!folly::LockTraits<Mutex>::is_shared>::type
 161 testBasicImpl() {
 162   folly::Synchronized<std::vector<int>, Mutex> obj;
 163
 164   obj.lock()->resize(1000);
 165
 166   folly::Synchronized<std::vector<int>, Mutex> obj2{*obj.lock()};
 167   EXPECT_EQ(1000, obj2.lock()->size());
 168
 169   {
 170     auto lockedObj = obj.lock();
 171     lockedObj->push_back(10);
 172     EXPECT_EQ(1001, lockedObj->size());
 173     EXPECT_EQ(10, lockedObj->back());
 174     EXPECT_EQ(1000, obj2.lock()->size());
 175
 176     {
 177       auto unlocker = lockedObj.scopedUnlock();
 178       EXPECT_EQ(1001, obj.lock()->size());
 179     }
 180   }
 181
 182   obj.lock()->front() = 2;
 183
 184   EXPECT_EQ(1001, obj.lock()->size());
 185   EXPECT_EQ(2, obj.lock()->front());
 186   EXPECT_EQ(2, obj.contextualLock()->front());
 187   EXPECT_EQ(10, obj.lock()->back());
 188   EXPECT_EQ(1000, obj2.lock()->size());
 189 }
 190
 191 template <class Mutex>
 192 void testBasic() {
 193   testBasicImpl<Mutex>();
 194 }
 195
 196 // Testing the deprecated SYNCHRONIZED and SYNCHRONIZED_CONST APIs
 197 template <class Mutex>
 198 void testDeprecated() {
 199   folly::Synchronized<std::vector<int>, Mutex> obj;
 200
 201   obj->resize(1000);
 202
 203   auto obj2 = obj;
 204   EXPECT_EQ(1000, obj2->size());
 205
 206   SYNCHRONIZED (obj) {
 207     obj.push_back(10);
 208     EXPECT_EQ(1001, obj.size());
 209     EXPECT_EQ(10, obj.back());
 210     EXPECT_EQ(1000, obj2->size());
 211
 212     UNSYNCHRONIZED(obj) {
 213       EXPECT_EQ(1001, obj->size());
 214     }
 215   }
 216
 217   SYNCHRONIZED_CONST (obj) {
 218     EXPECT_EQ(1001, obj.size());
 219     UNSYNCHRONIZED(obj) {
 220       EXPECT_EQ(1001, obj->size());
 221     }
 222   }
 223
 224   SYNCHRONIZED (lockedObj, *&obj) {
 225     lockedObj.front() = 2;
 226   }
 227
 228   EXPECT_EQ(1001, obj->size());
 229   EXPECT_EQ(10, obj->back());
 230   EXPECT_EQ(1000, obj2->size());
 231
 232   EXPECT_EQ(FB_ARG_2_OR_1(1, 2), 2);
 233   EXPECT_EQ(FB_ARG_2_OR_1(1), 1);
 234 }
 235
 236 template <class Mutex> void testConcurrency() {
 237   folly::Synchronized<std::vector<int>, Mutex> v;
 238   static const size_t numThreads = 100;
 239   // Note: I initially tried using itersPerThread = 1000,
 240   // which works fine for most lock types, but std::shared_timed_mutex
 241   // appears to be extraordinarily slow.  It could take around 30 seconds
 242   // to run this test with 1000 iterations per thread using shared_timed_mutex.
 243   static const size_t itersPerThread = 100;
 244
 245   auto pushNumbers = [&](size_t threadIdx) {
 246     // Test lock()
 247     for (size_t n = 0; n < itersPerThread; ++n) {
 248       v.contextualLock()->push_back((itersPerThread * threadIdx) + n);
 249       sched_yield();
 250     }
 251   };
 252   runParallel(numThreads, pushNumbers);
 253
 254   std::vector<int> result;
 255   v.swap(result);
 256
 257   EXPECT_EQ(numThreads * itersPerThread, result.size());
 258   sort(result.begin(), result.end());
 259
 260   for (size_t i = 0; i < itersPerThread * numThreads; ++i) {
 261     EXPECT_EQ(i, result[i]);
 262   }
 263 }
 264
 265 template <class Mutex>
 266 void testAcquireLocked() {
 267   folly::Synchronized<std::vector<int>, Mutex> v;
 268   folly::Synchronized<std::map<int, int>, Mutex> m;
 269
 270   auto dualLockWorker = [&](size_t threadIdx) {
 271     // Note: this will be less awkward with C++ 17's structured
 272     // binding functionality, which will make it easier to use the returned
 273     // std::tuple.
 274     if (threadIdx & 1) {
 275       auto ret = acquireLocked(v, m);
 276       std::get<0>(ret)->push_back(threadIdx);
 277       (*std::get<1>(ret))[threadIdx] = threadIdx + 1;
 278     } else {
 279       auto ret = acquireLocked(m, v);
 280       std::get<1>(ret)->push_back(threadIdx);
 281       (*std::get<0>(ret))[threadIdx] = threadIdx + 1;
 282     }
 283   };
 284   static const size_t numThreads = 100;
 285   runParallel(numThreads, dualLockWorker);
 286
 287   std::vector<int> result;
 288   v.swap(result);
 289
 290   EXPECT_EQ(numThreads, result.size());
 291   sort(result.begin(), result.end());
 292
 293   for (size_t i = 0; i < numThreads; ++i) {
 294     EXPECT_EQ(i, result[i]);
 295   }
 296 }
 297
 298 template <class Mutex>
 299 void testAcquireLockedWithConst() {
 300   folly::Synchronized<std::vector<int>, Mutex> v;
 301   folly::Synchronized<std::map<int, int>, Mutex> m;
 302
 303   auto dualLockWorker = [&](size_t threadIdx) {
 304     const auto& cm = m;
 305     if (threadIdx & 1) {
 306       auto ret = acquireLocked(v, cm);
 307       (void)std::get<1>(ret)->size();
 308       std::get<0>(ret)->push_back(threadIdx);
 309     } else {
 310       auto ret = acquireLocked(cm, v);
 311       (void)std::get<0>(ret)->size();
 312       std::get<1>(ret)->push_back(threadIdx);
 313     }
 314   };
 315   static const size_t numThreads = 100;
 316   runParallel(numThreads, dualLockWorker);
 317
 318   std::vector<int> result;
 319   v.swap(result);
 320
 321   EXPECT_EQ(numThreads, result.size());
 322   sort(result.begin(), result.end());
 323
 324   for (size_t i = 0; i < numThreads; ++i) {
 325     EXPECT_EQ(i, result[i]);
 326   }
 327 }
 328
 329 // Testing the deprecated SYNCHRONIZED_DUAL API
 330 template <class Mutex> void testDualLocking() {
 331   folly::Synchronized<std::vector<int>, Mutex> v;
 332   folly::Synchronized<std::map<int, int>, Mutex> m;
 333
 334   auto dualLockWorker = [&](size_t threadIdx) {
 335     if (threadIdx & 1) {
 336       SYNCHRONIZED_DUAL(lv, v, lm, m) {
 337         lv.push_back(threadIdx);
 338         lm[threadIdx] = threadIdx + 1;
 339       }
 340     } else {
 341       SYNCHRONIZED_DUAL(lm, m, lv, v) {
 342         lv.push_back(threadIdx);
 343         lm[threadIdx] = threadIdx + 1;
 344       }
 345     }
 346   };
 347   static const size_t numThreads = 100;
 348   runParallel(numThreads, dualLockWorker);
 349
 350   std::vector<int> result;
 351   v.swap(result);
 352
 353   EXPECT_EQ(numThreads, result.size());
 354   sort(result.begin(), result.end());
 355
 356   for (size_t i = 0; i < numThreads; ++i) {
 357     EXPECT_EQ(i, result[i]);
 358   }
 359 }
 360
 361 // Testing the deprecated SYNCHRONIZED_DUAL API
 362 template <class Mutex> void testDualLockingWithConst() {
 363   folly::Synchronized<std::vector<int>, Mutex> v;
 364   folly::Synchronized<std::map<int, int>, Mutex> m;
 365
 366   auto dualLockWorker = [&](size_t threadIdx) {
 367     const auto& cm = m;
 368     if (threadIdx & 1) {
 369       SYNCHRONIZED_DUAL(lv, v, lm, cm) {
 370         (void)lm.size();
 371         lv.push_back(threadIdx);
 372       }
 373     } else {
 374       SYNCHRONIZED_DUAL(lm, cm, lv, v) {
 375         (void)lm.size();
 376         lv.push_back(threadIdx);
 377       }
 378     }
 379   };
 380   static const size_t numThreads = 100;
 381   runParallel(numThreads, dualLockWorker);
 382
 383   std::vector<int> result;
 384   v.swap(result);
 385
 386   EXPECT_EQ(numThreads, result.size());
 387   sort(result.begin(), result.end());
 388
 389   for (size_t i = 0; i < numThreads; ++i) {
 390     EXPECT_EQ(i, result[i]);
 391   }
 392 }
 393
 394 template <class Mutex>
 395 void testTimed() {
 396   folly::Synchronized<std::vector<int>, Mutex> v;
 397   folly::Synchronized<uint64_t, Mutex> numTimeouts;
 398
 399   auto worker = [&](size_t threadIdx) {
 400     // Test directly using operator-> on the lock result
 401     v.contextualLock()->push_back(2 * threadIdx);
 402
 403     // Test using lock with a timeout
 404     for (;;) {
 405       auto lv = v.contextualLock(std::chrono::milliseconds(5));
 406       if (!lv) {
 407         ++(*numTimeouts.contextualLock());
 408         continue;
 409       }
 410
 411       // Sleep for a random time to ensure we trigger timeouts
 412       // in other threads
 413       randomSleep(std::chrono::milliseconds(5), std::chrono::milliseconds(15));
 414       lv->push_back(2 * threadIdx + 1);
 415       break;
 416     }
 417   };
 418
 419   static const size_t numThreads = 100;
 420   runParallel(numThreads, worker);
 421
 422   std::vector<int> result;
 423   v.swap(result);
 424
 425   EXPECT_EQ(2 * numThreads, result.size());
 426   sort(result.begin(), result.end());
 427
 428   for (size_t i = 0; i < 2 * numThreads; ++i) {
 429     EXPECT_EQ(i, result[i]);
 430   }
 431   // We generally expect a large number of number timeouts here.
 432   // I'm not adding a check for it since it's theoretically possible that
 433   // we might get 0 timeouts depending on the CPU scheduling if our threads
 434   // don't get to run very often.
 435   LOG(INFO) << "testTimed: " << *numTimeouts.contextualRLock() << " timeouts";
 436
 437   // Make sure we can lock with various timeout duration units
 438   {
 439     auto lv = v.contextualLock(std::chrono::milliseconds(5));
 440     EXPECT_TRUE(lv);
 441     EXPECT_FALSE(lv.isNull());
 442     auto lv2 = v.contextualLock(std::chrono::microseconds(5));
 443     // We may or may not acquire lv2 successfully, depending on whether
 444     // or not this is a recursive mutex type.
 445   }
 446   {
 447     auto lv = v.contextualLock(std::chrono::seconds(1));
 448     EXPECT_TRUE(lv);
 449   }
 450 }
 451
 452 template <class Mutex>
 453 void testTimedShared() {
 454   folly::Synchronized<std::vector<int>, Mutex> v;
 455   folly::Synchronized<uint64_t, Mutex> numTimeouts;
 456
 457   auto worker = [&](size_t threadIdx) {
 458     // Test directly using operator-> on the lock result
 459     v.wlock()->push_back(threadIdx);
 460
 461     // Test lock() with a timeout
 462     for (;;) {
 463       auto lv = v.rlock(std::chrono::milliseconds(10));
 464       if (!lv) {
 465         ++(*numTimeouts.contextualLock());
 466         continue;
 467       }
 468
 469       // Sleep while holding the lock.
 470       //
 471       // This will block other threads from acquiring the write lock to add
 472       // their thread index to v, but it won't block threads that have entered
 473       // the for loop and are trying to acquire a read lock.
 474       //
 475       // For lock types that give preference to readers rather than writers,
 476       // this will tend to serialize all threads on the wlock() above.
 477       randomSleep(std::chrono::milliseconds(5), std::chrono::milliseconds(15));
 478       auto found = std::find(lv->begin(), lv->end(), threadIdx);
 479       CHECK(found != lv->end());
 480       break;
 481     }
 482   };
 483
 484   static const size_t numThreads = 100;
 485   runParallel(numThreads, worker);
 486
 487   std::vector<int> result;
 488   v.swap(result);
 489
 490   EXPECT_EQ(numThreads, result.size());
 491   sort(result.begin(), result.end());
 492
 493   for (size_t i = 0; i < numThreads; ++i) {
 494     EXPECT_EQ(i, result[i]);
 495   }
 496   // We generally expect a small number of timeouts here.
 497   // For locks that give readers preference over writers this should usually
 498   // be 0.  With locks that give writers preference we do see a small-ish
 499   // number of read timeouts.
 500   LOG(INFO) << "testTimedShared: " << *numTimeouts.contextualRLock()
 501             << " timeouts";
 502 }
 503
 504 // Testing the deprecated TIMED_SYNCHRONIZED API
 505 template <class Mutex> void testTimedSynchronized() {
 506   folly::Synchronized<std::vector<int>, Mutex> v;
 507   folly::Synchronized<uint64_t, Mutex> numTimeouts;
 508
 509   auto worker = [&](size_t threadIdx) {
 510     // Test operator->
 511     v->push_back(2 * threadIdx);
 512
 513     // Aaand test the TIMED_SYNCHRONIZED macro
 514     for (;;)
 515       TIMED_SYNCHRONIZED(5, lv, v) {
 516         if (lv) {
 517           // Sleep for a random time to ensure we trigger timeouts
 518           // in other threads
 519           randomSleep(
 520               std::chrono::milliseconds(5), std::chrono::milliseconds(15));
 521           lv->push_back(2 * threadIdx + 1);
 522           return;
 523         }
 524
 525         ++(*numTimeouts.contextualLock());
 526       }
 527   };
 528
 529   static const size_t numThreads = 100;
 530   runParallel(numThreads, worker);
 531
 532   std::vector<int> result;
 533   v.swap(result);
 534
 535   EXPECT_EQ(2 * numThreads, result.size());
 536   sort(result.begin(), result.end());
 537
 538   for (size_t i = 0; i < 2 * numThreads; ++i) {
 539     EXPECT_EQ(i, result[i]);
 540   }
 541   // We generally expect a large number of number timeouts here.
 542   // I'm not adding a check for it since it's theoretically possible that
 543   // we might get 0 timeouts depending on the CPU scheduling if our threads
 544   // don't get to run very often.
 545   LOG(INFO) << "testTimedSynchronized: " << *numTimeouts.contextualRLock()
 546             << " timeouts";
 547 }
 548
 549 // Testing the deprecated TIMED_SYNCHRONIZED_CONST API
 550 template <class Mutex> void testTimedSynchronizedWithConst() {
 551   folly::Synchronized<std::vector<int>, Mutex> v;
 552   folly::Synchronized<uint64_t, Mutex> numTimeouts;
 553
 554   auto worker = [&](size_t threadIdx) {
 555     // Test operator->
 556     v->push_back(threadIdx);
 557
 558     // Test TIMED_SYNCHRONIZED_CONST
 559     for (;;) {
 560       TIMED_SYNCHRONIZED_CONST(10, lv, v) {
 561         if (lv) {
 562           // Sleep while holding the lock.
 563           //
 564           // This will block other threads from acquiring the write lock to add
 565           // their thread index to v, but it won't block threads that have
 566           // entered the for loop and are trying to acquire a read lock.
 567           //
 568           // For lock types that give preference to readers rather than writers,
 569           // this will tend to serialize all threads on the wlock() above.
 570           randomSleep(
 571               std::chrono::milliseconds(5), std::chrono::milliseconds(15));
 572           auto found = std::find(lv->begin(), lv->end(), threadIdx);
 573           CHECK(found != lv->end());
 574           return;
 575         } else {
 576           ++(*numTimeouts.contextualLock());
 577         }
 578       }
 579     }
 580   };
 581
 582   static const size_t numThreads = 100;
 583   runParallel(numThreads, worker);
 584
 585   std::vector<int> result;
 586   v.swap(result);
 587
 588   EXPECT_EQ(numThreads, result.size());
 589   sort(result.begin(), result.end());
 590
 591   for (size_t i = 0; i < numThreads; ++i) {
 592     EXPECT_EQ(i, result[i]);
 593   }
 594   // We generally expect a small number of timeouts here.
 595   // For locks that give readers preference over writers this should usually
 596   // be 0.  With locks that give writers preference we do see a small-ish
 597   // number of read timeouts.
 598   LOG(INFO) << "testTimedSynchronizedWithConst: "
 599             << *numTimeouts.contextualRLock() << " timeouts";
 600 }
 601
 602 template <class Mutex> void testConstCopy() {
 603   std::vector<int> input = {1, 2, 3};
 604   const folly::Synchronized<std::vector<int>, Mutex> v(input);
 605
 606   std::vector<int> result;
 607
 608   v.copy(&result);
 609   EXPECT_EQ(input, result);
 610
 611   result = v.copy();
 612   EXPECT_EQ(input, result);
 613 }
 614
 615 struct NotCopiableNotMovable {
 616   NotCopiableNotMovable(int, const char*) {}
 617   NotCopiableNotMovable(const NotCopiableNotMovable&) = delete;
 618   NotCopiableNotMovable& operator=(const NotCopiableNotMovable&) = delete;
 619   NotCopiableNotMovable(NotCopiableNotMovable&&) = delete;
 620   NotCopiableNotMovable& operator=(NotCopiableNotMovable&&) = delete;
 621 };
 622
 623 template <class Mutex> void testInPlaceConstruction() {
 624   // This won't compile without construct_in_place
 625   folly::Synchronized<NotCopiableNotMovable> a(
 626     folly::construct_in_place, 5, "a"
 627   );
 628 }
 629 }
 630 }