folly/test/LifoSemTests.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
  17 #include <folly/LifoSem.h>
  18 #include <folly/test/DeterministicSchedule.h>
  19
  20 #include <thread>
  21 #include <semaphore.h>
  22 #include <gflags/gflags.h>
  23 #include <gtest/gtest.h>
  24
  25 #include <folly/Benchmark.h>
  26 #include <folly/Random.h>
  27
  28 using namespace folly;
  29 using namespace folly::test;
  30
  31 typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
  32 typedef DeterministicSchedule DSched;
  33
  34 LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
  35
  36 TEST(LifoSem, basic) {
  37   LifoSem sem;
  38   EXPECT_FALSE(sem.tryWait());
  39   sem.post();
  40   EXPECT_TRUE(sem.tryWait());
  41   sem.post();
  42   sem.wait();
  43 }
  44
  45 TEST(LifoSem, multi) {
  46   LifoSem sem;
  47
  48   const int opsPerThread = 10000;
  49   std::thread threads[10];
  50   std::atomic<int> blocks(0);
  51
  52   for (auto& thr : threads) {
  53     thr = std::thread([&]{
  54       int b = 0;
  55       for (int i = 0; i < opsPerThread; ++i) {
  56         if (!sem.tryWait()) {
  57           sem.wait();
  58           ++b;
  59         }
  60         sem.post();
  61       }
  62       blocks += b;
  63     });
  64   }
  65
  66   // start the flood
  67   sem.post();
  68
  69   for (auto& thr : threads) {
  70     thr.join();
  71   }
  72
  73   LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
  74             << " post/wait pairs, " << blocks << " blocked";
  75 }
  76
  77 TEST(LifoSem, pingpong) {
  78   DSched sched(DSched::uniform(0));
  79
  80   const int iters = 100;
  81
  82   for (int pass = 0; pass < 10; ++pass) {
  83     DLifoSem a;
  84     DLifoSem b;
  85
  86     auto thr = DSched::thread([&]{
  87       for (int i = 0; i < iters; ++i) {
  88         a.wait();
  89         // main thread can't be running here
  90         EXPECT_EQ(a.valueGuess(), 0);
  91         EXPECT_EQ(b.valueGuess(), 0);
  92         b.post();
  93       }
  94     });
  95     for (int i = 0; i < iters; ++i) {
  96       a.post();
  97       b.wait();
  98       // child thread can't be running here
  99       EXPECT_EQ(a.valueGuess(), 0);
 100       EXPECT_EQ(b.valueGuess(), 0);
 101     }
 102     DSched::join(thr);
 103   }
 104 }
 105
 106 TEST(LifoSem, mutex) {
 107   DSched sched(DSched::uniform(0));
 108
 109   const int iters = 100;
 110
 111   for (int pass = 0; pass < 10; ++pass) {
 112     DLifoSem a;
 113
 114     auto thr = DSched::thread([&]{
 115       for (int i = 0; i < iters; ++i) {
 116         a.wait();
 117         a.post();
 118       }
 119     });
 120     for (int i = 0; i < iters; ++i) {
 121       a.post();
 122       a.wait();
 123     }
 124     a.post();
 125     DSched::join(thr);
 126     a.wait();
 127   }
 128 }
 129
 130 TEST(LifoSem, no_blocking) {
 131   long seed = folly::randomNumberSeed() % 10000;
 132   LOG(INFO) << "seed=" << seed;
 133   DSched sched(DSched::uniform(seed));
 134
 135   const int iters = 100;
 136   const int numThreads = 2;
 137   const int width = 10;
 138
 139   for (int pass = 0; pass < 10; ++pass) {
 140     DLifoSem a;
 141
 142     std::vector<std::thread> threads;
 143     while (threads.size() < numThreads) {
 144       threads.emplace_back(DSched::thread([&]{
 145         for (int i = 0; i < iters; ++i) {
 146           a.post(width);
 147           for (int w = 0; w < width; ++w) {
 148             a.wait();
 149           }
 150         }
 151       }));
 152     }
 153     for (auto& thr : threads) {
 154       DSched::join(thr);
 155     }
 156   }
 157 }
 158
 159 TEST(LifoSem, one_way) {
 160   long seed = folly::randomNumberSeed() % 10000;
 161   LOG(INFO) << "seed=" << seed;
 162   DSched sched(DSched::uniformSubset(seed, 1, 6));
 163
 164   const int iters = 1000;
 165
 166   for (int pass = 0; pass < 10; ++pass) {
 167     DLifoSem a;
 168
 169     auto thr = DSched::thread([&]{
 170       for (int i = 0; i < iters; ++i) {
 171         a.wait();
 172       }
 173     });
 174     for (int i = 0; i < iters; ++i) {
 175       a.post();
 176     }
 177     DSched::join(thr);
 178   }
 179 }
 180
 181 TEST(LifoSem, shutdown_race) {
 182   long seed = folly::randomNumberSeed() % 10000;
 183   LOG(INFO) << "seed=" << seed;
 184
 185   bool shutdownWon = false;
 186   bool shutdownLost = false;
 187   for (int pass = 0; pass < 1000; ++pass) {
 188     DSched sched(DSched::uniformSubset(seed + pass, 1, 1 + (pass % 50)));
 189
 190     DLifoSem a;
 191     int waitCount = 0;
 192     auto thr = DSched::thread([&]{
 193       try {
 194         while (true) {
 195           a.wait();
 196           ++waitCount;
 197         }
 198       } catch (ShutdownSemError& x) {
 199         // expected
 200         EXPECT_TRUE(a.isShutdown());
 201       }
 202     });
 203     EXPECT_TRUE(!a.isShutdown());
 204     a.shutdown();
 205     EXPECT_TRUE(a.isShutdown());
 206     a.post();
 207     DSched::join(thr);
 208     EXPECT_EQ(1, waitCount + a.valueGuess());
 209     if (waitCount == 0) {
 210       shutdownWon = true;
 211     } else {
 212       shutdownLost = true;
 213     }
 214   }
 215   EXPECT_TRUE(shutdownWon);
 216   EXPECT_TRUE(shutdownLost);
 217 }
 218
 219 TEST(LifoSem, shutdown_multi) {
 220   DSched sched(DSched::uniform(0));
 221
 222   for (int pass = 0; pass < 10; ++pass) {
 223     DLifoSem a;
 224     std::vector<std::thread> threads;
 225     while (threads.size() < 20) {
 226       threads.push_back(DSched::thread([&]{
 227         try {
 228           a.wait();
 229           EXPECT_TRUE(false);
 230         } catch (ShutdownSemError& x) {
 231           // expected
 232           EXPECT_TRUE(a.isShutdown());
 233         }
 234       }));
 235     }
 236     a.shutdown();
 237     for (auto& thr : threads) {
 238       DSched::join(thr);
 239     }
 240   }
 241 }
 242
 243 TEST(LifoSem, multi_try_wait_simple) {
 244   LifoSem sem;
 245   sem.post(5);
 246   auto n = sem.tryWait(10);     // this used to trigger an assert
 247   ASSERT_EQ(5, n);
 248 }
 249
 250 TEST(LifoSem, multi_try_wait) {
 251   long seed = folly::randomNumberSeed() % 10000;
 252   LOG(INFO) << "seed=" << seed;
 253   DSched sched(DSched::uniform(seed));
 254   DLifoSem sem;
 255
 256   const int NPOSTS = 1000;
 257
 258   auto producer = [&]{
 259     for (int i=0; i<NPOSTS; ++i) {
 260       sem.post();
 261     }
 262   };
 263
 264   DeterministicAtomic<bool> consumer_stop(false);
 265   int consumed = 0;
 266
 267   auto consumer = [&]{
 268     bool stop;
 269     do {
 270       stop = consumer_stop.load();
 271       int n;
 272       do {
 273         n = sem.tryWait(10);
 274         consumed += n;
 275       } while (n > 0);
 276     } while (!stop);
 277   };
 278
 279   std::thread producer_thread(DSched::thread(producer));
 280   std::thread consumer_thread(DSched::thread(consumer));
 281   DSched::join(producer_thread);
 282   consumer_stop.store(true);
 283   DSched::join(consumer_thread);
 284
 285   ASSERT_EQ(NPOSTS, consumed);
 286 }
 287
 288 BENCHMARK(lifo_sem_pingpong, iters) {
 289   LifoSem a;
 290   LifoSem b;
 291   auto thr = std::thread([&]{
 292     for (size_t i = 0; i < iters; ++i) {
 293       a.wait();
 294       b.post();
 295     }
 296   });
 297   for (size_t i = 0; i < iters; ++i) {
 298     a.post();
 299     b.wait();
 300   }
 301   thr.join();
 302 }
 303
 304 BENCHMARK(lifo_sem_oneway, iters) {
 305   LifoSem a;
 306   auto thr = std::thread([&]{
 307     for (size_t i = 0; i < iters; ++i) {
 308       a.wait();
 309     }
 310   });
 311   for (size_t i = 0; i < iters; ++i) {
 312     a.post();
 313   }
 314   thr.join();
 315 }
 316
 317 BENCHMARK(single_thread_lifo_post, iters) {
 318   LifoSem sem;
 319   for (size_t n = 0; n < iters; ++n) {
 320     sem.post();
 321     asm volatile ("":::"memory");
 322   }
 323 }
 324
 325 BENCHMARK(single_thread_lifo_wait, iters) {
 326   LifoSem sem(iters);
 327   for (size_t n = 0; n < iters; ++n) {
 328     sem.wait();
 329     asm volatile ("":::"memory");
 330   }
 331 }
 332
 333 BENCHMARK(single_thread_lifo_postwait, iters) {
 334   LifoSem sem;
 335   for (size_t n = 0; n < iters; ++n) {
 336     sem.post();
 337     asm volatile ("":::"memory");
 338     sem.wait();
 339     asm volatile ("":::"memory");
 340   }
 341 }
 342
 343 BENCHMARK(single_thread_lifo_trywait, iters) {
 344   LifoSem sem;
 345   for (size_t n = 0; n < iters; ++n) {
 346     EXPECT_FALSE(sem.tryWait());
 347     asm volatile ("":::"memory");
 348   }
 349 }
 350
 351 BENCHMARK(single_thread_posix_postwait, iters) {
 352   sem_t sem;
 353   EXPECT_EQ(sem_init(&sem, 0, 0), 0);
 354   for (size_t n = 0; n < iters; ++n) {
 355     EXPECT_EQ(sem_post(&sem), 0);
 356     EXPECT_EQ(sem_wait(&sem), 0);
 357   }
 358   EXPECT_EQ(sem_destroy(&sem), 0);
 359 }
 360
 361 BENCHMARK(single_thread_posix_trywait, iters) {
 362   sem_t sem;
 363   EXPECT_EQ(sem_init(&sem, 0, 0), 0);
 364   for (size_t n = 0; n < iters; ++n) {
 365     EXPECT_EQ(sem_trywait(&sem), -1);
 366   }
 367   EXPECT_EQ(sem_destroy(&sem), 0);
 368 }
 369
 370 static void contendedUse(uint n, int posters, int waiters) {
 371   LifoSemImpl<std::atomic> sem;
 372
 373   std::vector<std::thread> threads;
 374   std::atomic<bool> go(false);
 375
 376   BENCHMARK_SUSPEND {
 377     for (int t = 0; t < waiters; ++t) {
 378       threads.emplace_back([=,&sem] {
 379         for (uint i = t; i < n; i += waiters) {
 380           sem.wait();
 381         }
 382       });
 383     }
 384     for (int t = 0; t < posters; ++t) {
 385       threads.emplace_back([=,&sem,&go] {
 386         while (!go.load()) {
 387           std::this_thread::yield();
 388         }
 389         for (uint i = t; i < n; i += posters) {
 390           sem.post();
 391         }
 392       });
 393     }
 394   }
 395
 396   go.store(true);
 397   for (auto& thr : threads) {
 398     thr.join();
 399   }
 400 }
 401
 402 BENCHMARK_DRAW_LINE()
 403 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_1, 1, 1)
 404 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_4, 1, 4)
 405 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_32, 1, 32)
 406 BENCHMARK_NAMED_PARAM(contendedUse, 4_to_1, 4, 1)
 407 BENCHMARK_NAMED_PARAM(contendedUse, 4_to_24, 4, 24)
 408 BENCHMARK_NAMED_PARAM(contendedUse, 8_to_100, 8, 100)
 409 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1, 31, 1)
 410 BENCHMARK_NAMED_PARAM(contendedUse, 16_to_16, 16, 16)
 411 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_32, 32, 32)
 412 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1000, 32, 1000)
 413
 414 // sudo nice -n -20 _build/opt/folly/test/LifoSemTests
 415 //     --benchmark --bm_min_iters=10000000 --gtest_filter=-\*
 416 // ============================================================================
 417 // folly/test/LifoSemTests.cpp                     relative  time/iter  iters/s
 418 // ============================================================================
 419 // lifo_sem_pingpong                                            1.31us  762.40K
 420 // lifo_sem_oneway                                            193.89ns    5.16M
 421 // single_thread_lifo_post                                     15.37ns   65.08M
 422 // single_thread_lifo_wait                                     13.60ns   73.53M
 423 // single_thread_lifo_postwait                                 29.43ns   33.98M
 424 // single_thread_lifo_trywait                                 677.69ps    1.48G
 425 // single_thread_posix_postwait                                25.03ns   39.95M
 426 // single_thread_posix_trywait                                  7.30ns  136.98M
 427 // ----------------------------------------------------------------------------
 428 // contendedUse(1_to_1)                                       158.22ns    6.32M
 429 // contendedUse(1_to_4)                                       574.73ns    1.74M
 430 // contendedUse(1_to_32)                                      592.94ns    1.69M
 431 // contendedUse(4_to_1)                                       118.28ns    8.45M
 432 // contendedUse(4_to_24)                                      667.62ns    1.50M
 433 // contendedUse(8_to_100)                                     701.46ns    1.43M
 434 // contendedUse(32_to_1)                                      165.06ns    6.06M
 435 // contendedUse(16_to_16)                                     238.57ns    4.19M
 436 // contendedUse(32_to_32)                                     219.82ns    4.55M
 437 // contendedUse(32_to_1000)                                   777.42ns    1.29M
 438 // ============================================================================
 439
 440 int main(int argc, char ** argv) {
 441   testing::InitGoogleTest(&argc, argv);
 442   gflags::ParseCommandLineFlags(&argc, &argv, true);
 443   int rv = RUN_ALL_TESTS();
 444   folly::runBenchmarksOnFlag();
 445   return rv;
 446 }