1 /*******************************************************************************
2  * tlx/thread_barrier_spin.hpp
3  *
4  * Part of tlx - http://panthema.net/tlx
5  *
6  * Copyright (C) 2015-2019 Timo Bingmann <tb@panthema.net>
7  *
8  * All rights reserved. Published under the Boost Software License, Version 1.0
9  ******************************************************************************/
10 
11 #ifndef TLX_THREAD_BARRIER_SPIN_HEADER
12 #define TLX_THREAD_BARRIER_SPIN_HEADER
13 
14 #include <tlx/meta/no_operation.hpp>
15 
16 #include <atomic>
17 #include <thread>
18 
19 namespace tlx {
20 
21 /*!
22  * Implements a thread barrier using atomics and a spin lock that can be used to
23  * synchronize threads.
24  *
25  * This ThreadBarrier implementation was a lot faster in tests than
26  * ThreadBarrierMutex, but ThreadSanitizer shows data races (probably due to the
27  * generation counter).
28  */
29 class ThreadBarrierSpin
30 {
31 public:
32     /*!
33      * Creates a new barrier that waits for n threads.
34      */
ThreadBarrierSpin(size_t thread_count)35     explicit ThreadBarrierSpin(size_t thread_count)
36         : thread_count_(thread_count - 1) { }
37 
38     /*!
39      * Waits for n threads to arrive. When they have arrive, execute lambda on
40      * the one thread, which arrived last. After lambda, step the generation
41      * counter.
42      *
43      * This method blocks and returns as soon as n threads are waiting inside
44      * the method.
45      */
46     template <typename Lambda = NoOperation<void> >
wait(Lambda lambda=Lambda ())47     void wait(Lambda lambda = Lambda()) {
48         // get synchronization generation step counter.
49         size_t this_step = step_.load(std::memory_order_acquire);
50 
51         if (waiting_.fetch_add(1, std::memory_order_acq_rel) == thread_count_) {
52             // we are the last thread to wait() -> reset and increment step.
53             waiting_.store(0, std::memory_order_release);
54             // step other generation counters.
55             lambda();
56             // the following statement releases all threads from busy waiting.
57             step_.fetch_add(1, std::memory_order_acq_rel);
58         }
59         else {
60             // spin lock awaiting the last thread to increment the step counter.
61             while (step_.load(std::memory_order_acquire) == this_step) {
62                 // busy spinning loop
63             }
64         }
65     }
66 
67     /*!
68      * Waits for n threads to arrive, yield thread while spinning. When they
69      * have arrive, execute lambda on the one thread, which arrived last. After
70      * lambda, step the generation counter.
71      *
72      * This method blocks and returns as soon as n threads are waiting inside
73      * the method.
74      */
75     template <typename Lambda = NoOperation<void> >
wait_yield(Lambda lambda=Lambda ())76     void wait_yield(Lambda lambda = Lambda()) {
77         // get synchronization generation step counter.
78         size_t this_step = step_.load(std::memory_order_acquire);
79 
80         if (waiting_.fetch_add(1, std::memory_order_acq_rel) == thread_count_) {
81             // we are the last thread to wait() -> reset and increment step.
82             waiting_.store(0, std::memory_order_release);
83             // step other generation counters.
84             lambda();
85             // the following statement releases all threads from busy waiting.
86             step_.fetch_add(1, std::memory_order_acq_rel);
87         }
88         else {
89             // spin lock awaiting the last thread to increment the step counter.
90             while (step_.load(std::memory_order_acquire) == this_step) {
91                 std::this_thread::yield();
92             }
93         }
94     }
95 
96     //! Return generation step counter
step() const97     size_t step() const {
98         return step_.load(std::memory_order_acquire);
99     }
100 
101 protected:
102     //! number of threads, minus one due to comparison needed in loop
103     const size_t thread_count_;
104 
105     //! number of threads in spin lock
106     std::atomic<size_t> waiting_ { 0 };
107 
108     //! barrier synchronization generation
109     std::atomic<size_t> step_ { 0 };
110 };
111 
112 } // namespace tlx
113 
114 #endif // !TLX_THREAD_BARRIER_SPIN_HEADER
115 
116 /******************************************************************************/
117