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