2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/LifoSem.h>
18 #include <folly/test/DeterministicSchedule.h>
21 #include <semaphore.h>
22 #include <gflags/gflags.h>
23 #include <gtest/gtest.h>
25 #include <folly/Benchmark.h>
26 #include <folly/Random.h>
28 using namespace folly;
29 using namespace folly::test;
31 typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
32 typedef DeterministicSchedule DSched;
34 LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
36 TEST(LifoSem, basic) {
38 EXPECT_FALSE(sem.tryWait());
40 EXPECT_TRUE(sem.tryWait());
45 TEST(LifoSem, multi) {
48 const int opsPerThread = 10000;
49 std::thread threads[10];
50 std::atomic<int> blocks(0);
52 for (auto& thr : threads) {
53 thr = std::thread([&]{
55 for (int i = 0; i < opsPerThread; ++i) {
69 for (auto& thr : threads) {
73 LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
74 << " post/wait pairs, " << blocks << " blocked";
77 TEST(LifoSem, pingpong) {
78 DSched sched(DSched::uniform(0));
80 const int iters = 100;
82 for (int pass = 0; pass < 10; ++pass) {
86 auto thr = DSched::thread([&]{
87 for (int i = 0; i < iters; ++i) {
89 // main thread can't be running here
90 EXPECT_EQ(a.valueGuess(), 0);
91 EXPECT_EQ(b.valueGuess(), 0);
95 for (int i = 0; i < iters; ++i) {
98 // child thread can't be running here
99 EXPECT_EQ(a.valueGuess(), 0);
100 EXPECT_EQ(b.valueGuess(), 0);
106 TEST(LifoSem, mutex) {
107 DSched sched(DSched::uniform(0));
109 const int iters = 100;
111 for (int pass = 0; pass < 10; ++pass) {
114 auto thr = DSched::thread([&]{
115 for (int i = 0; i < iters; ++i) {
120 for (int i = 0; i < iters; ++i) {
130 TEST(LifoSem, no_blocking) {
131 long seed = folly::randomNumberSeed() % 10000;
132 LOG(INFO) << "seed=" << seed;
133 DSched sched(DSched::uniform(seed));
135 const int iters = 100;
136 const int numThreads = 2;
137 const int width = 10;
139 for (int pass = 0; pass < 10; ++pass) {
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) {
147 for (int w = 0; w < width; ++w) {
153 for (auto& thr : threads) {
159 TEST(LifoSem, one_way) {
160 long seed = folly::randomNumberSeed() % 10000;
161 LOG(INFO) << "seed=" << seed;
162 DSched sched(DSched::uniformSubset(seed, 1, 6));
164 const int iters = 1000;
166 for (int pass = 0; pass < 10; ++pass) {
169 auto thr = DSched::thread([&]{
170 for (int i = 0; i < iters; ++i) {
174 for (int i = 0; i < iters; ++i) {
181 TEST(LifoSem, shutdown_race) {
182 long seed = folly::randomNumberSeed() % 10000;
183 LOG(INFO) << "seed=" << seed;
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)));
192 auto thr = DSched::thread([&]{
198 } catch (ShutdownSemError& x) {
200 EXPECT_TRUE(a.isShutdown());
203 EXPECT_TRUE(!a.isShutdown());
205 EXPECT_TRUE(a.isShutdown());
208 EXPECT_EQ(1, waitCount + a.valueGuess());
209 if (waitCount == 0) {
215 EXPECT_TRUE(shutdownWon);
216 EXPECT_TRUE(shutdownLost);
219 TEST(LifoSem, shutdown_multi) {
220 DSched sched(DSched::uniform(0));
222 for (int pass = 0; pass < 10; ++pass) {
224 std::vector<std::thread> threads;
225 while (threads.size() < 20) {
226 threads.push_back(DSched::thread([&]{
230 } catch (ShutdownSemError& x) {
232 EXPECT_TRUE(a.isShutdown());
237 for (auto& thr : threads) {
243 TEST(LifoSem, multi_try_wait_simple) {
246 auto n = sem.tryWait(10); // this used to trigger an assert
250 TEST(LifoSem, multi_try_wait) {
251 long seed = folly::randomNumberSeed() % 10000;
252 LOG(INFO) << "seed=" << seed;
253 DSched sched(DSched::uniform(seed));
256 const int NPOSTS = 1000;
259 for (int i=0; i<NPOSTS; ++i) {
264 DeterministicAtomic<bool> consumer_stop(false);
270 stop = consumer_stop.load();
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);
285 ASSERT_EQ(NPOSTS, consumed);
288 BENCHMARK(lifo_sem_pingpong, iters) {
291 auto thr = std::thread([&]{
292 for (size_t i = 0; i < iters; ++i) {
297 for (size_t i = 0; i < iters; ++i) {
304 BENCHMARK(lifo_sem_oneway, iters) {
306 auto thr = std::thread([&]{
307 for (size_t i = 0; i < iters; ++i) {
311 for (size_t i = 0; i < iters; ++i) {
317 BENCHMARK(single_thread_lifo_post, iters) {
319 for (size_t n = 0; n < iters; ++n) {
321 asm volatile ("":::"memory");
325 BENCHMARK(single_thread_lifo_wait, iters) {
327 for (size_t n = 0; n < iters; ++n) {
329 asm volatile ("":::"memory");
333 BENCHMARK(single_thread_lifo_postwait, iters) {
335 for (size_t n = 0; n < iters; ++n) {
337 asm volatile ("":::"memory");
339 asm volatile ("":::"memory");
343 BENCHMARK(single_thread_lifo_trywait, iters) {
345 for (size_t n = 0; n < iters; ++n) {
346 EXPECT_FALSE(sem.tryWait());
347 asm volatile ("":::"memory");
351 BENCHMARK(single_thread_posix_postwait, iters) {
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);
358 EXPECT_EQ(sem_destroy(&sem), 0);
361 BENCHMARK(single_thread_posix_trywait, iters) {
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);
367 EXPECT_EQ(sem_destroy(&sem), 0);
370 static void contendedUse(uint n, int posters, int waiters) {
371 LifoSemImpl<std::atomic> sem;
373 std::vector<std::thread> threads;
374 std::atomic<bool> go(false);
377 for (int t = 0; t < waiters; ++t) {
378 threads.emplace_back([=,&sem] {
379 for (uint i = t; i < n; i += waiters) {
384 for (int t = 0; t < posters; ++t) {
385 threads.emplace_back([=,&sem,&go] {
387 std::this_thread::yield();
389 for (uint i = t; i < n; i += posters) {
397 for (auto& thr : threads) {
402 BENCHMARK_DRAW_LINE()
403 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_1, 1, 1)
404 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_32, 1, 32)
405 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1, 31, 1)
406 BENCHMARK_NAMED_PARAM(contendedUse, 16_to_16, 16, 16)
407 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_32, 32, 32)
408 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1000, 32, 1000)
410 // sudo nice -n -20 folly/test/LifoSemTests --benchmark --bm_min_iters=10000000
411 // ============================================================================
412 // folly/test/LifoSemTests.cpp relative time/iter iters/s
413 // ============================================================================
414 // lifo_sem_pingpong 396.84ns 2.52M
415 // lifo_sem_oneway 88.52ns 11.30M
416 // single_thread_lifo_post 14.78ns 67.67M
417 // single_thread_lifo_wait 13.53ns 73.90M
418 // single_thread_lifo_postwait 28.91ns 34.59M
419 // single_thread_lifo_trywait 670.13ps 1.49G
420 // single_thread_posix_postwait 24.12ns 41.46M
421 // single_thread_posix_trywait 6.76ns 147.88M
422 // ----------------------------------------------------------------------------
423 // contendedUse(1_to_1) 143.60ns 6.96M
424 // contendedUse(1_to_32) 244.06ns 4.10M
425 // contendedUse(32_to_1) 131.99ns 7.58M
426 // contendedUse(16_to_16) 210.64ns 4.75M
427 // contendedUse(32_to_32) 222.91ns 4.49M
428 // contendedUse(32_to_1000) 453.39ns 2.21M
429 // ============================================================================
431 int main(int argc, char ** argv) {
432 testing::InitGoogleTest(&argc, argv);
433 gflags::ParseCommandLineFlags(&argc, &argv, true);
434 int rv = RUN_ALL_TESTS();
435 folly::runBenchmarksOnFlag();