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