1// -*- C++ -*-
2//===--------------------------- barrier ----------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_BARRIER
11#define _LIBCPP_BARRIER
12
13/*
14    barrier synopsis
15
16namespace std
17{
18
19  template<class CompletionFunction = see below>
20  class barrier
21  {
22  public:
23    using arrival_token = see below;
24
25    constexpr explicit barrier(ptrdiff_t phase_count,
26                               CompletionFunction f = CompletionFunction());
27    ~barrier();
28
29    barrier(const barrier&) = delete;
30    barrier& operator=(const barrier&) = delete;
31
32    [[nodiscard]] arrival_token arrive(ptrdiff_t update = 1);
33    void wait(arrival_token&& arrival) const;
34
35    void arrive_and_wait();
36    void arrive_and_drop();
37
38  private:
39    CompletionFunction completion; // exposition only
40  };
41
42}
43
44*/
45
46#include <__config>
47#include <__availability>
48#include <atomic>
49#ifndef _LIBCPP_HAS_NO_TREE_BARRIER
50# include <memory>
51#endif
52
53#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
54#pragma GCC system_header
55#endif
56
57#ifdef _LIBCPP_HAS_NO_THREADS
58# error <barrier> is not supported on this single threaded system
59#endif
60
61#if _LIBCPP_STD_VER >= 14
62
63_LIBCPP_BEGIN_NAMESPACE_STD
64
65struct __empty_completion
66{
67    inline _LIBCPP_INLINE_VISIBILITY
68    void operator()() noexcept
69    {
70    }
71};
72
73#ifndef _LIBCPP_HAS_NO_TREE_BARRIER
74
75/*
76
77The default implementation of __barrier_base is a classic tree barrier.
78
79It looks different from literature pseudocode for two main reasons:
80 1. Threads that call into std::barrier functions do not provide indices,
81    so a numbering step is added before the actual barrier algorithm,
82    appearing as an N+1 round to the N rounds of the tree barrier.
83 2. A great deal of attention has been paid to avoid cache line thrashing
84    by flattening the tree structure into cache-line sized arrays, that
85    are indexed in an efficient way.
86
87*/
88
89using __barrier_phase_t = uint8_t;
90
91class __barrier_algorithm_base;
92
93_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI
94__barrier_algorithm_base* __construct_barrier_algorithm_base(ptrdiff_t& __expected);
95
96_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI
97bool __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier,
98                                     __barrier_phase_t __old_phase);
99
100_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI
101void __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier);
102
103template<class _CompletionF>
104class __barrier_base {
105
106    ptrdiff_t                                               __expected;
107    unique_ptr<__barrier_algorithm_base,
108               void (*)(__barrier_algorithm_base*)>         __base;
109    __atomic_base<ptrdiff_t>                                __expected_adjustment;
110    _CompletionF                                            __completion;
111    __atomic_base<__barrier_phase_t>                        __phase;
112
113public:
114    using arrival_token = __barrier_phase_t;
115
116    static constexpr ptrdiff_t max() noexcept {
117        return numeric_limits<ptrdiff_t>::max();
118    }
119
120    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
121    __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
122            : __expected(__expected), __base(__construct_barrier_algorithm_base(this->__expected),
123                                             &__destroy_barrier_algorithm_base),
124              __expected_adjustment(0), __completion(move(__completion)), __phase(0)
125    {
126    }
127    [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
128    arrival_token arrive(ptrdiff_t update)
129    {
130        auto const __old_phase = __phase.load(memory_order_relaxed);
131        for(; update; --update)
132            if(__arrive_barrier_algorithm_base(__base.get(), __old_phase)) {
133                __completion();
134                __expected += __expected_adjustment.load(memory_order_relaxed);
135                __expected_adjustment.store(0, memory_order_relaxed);
136                __phase.store(__old_phase + 2, memory_order_release);
137                __phase.notify_all();
138            }
139        return __old_phase;
140    }
141    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
142    void wait(arrival_token&& __old_phase) const
143    {
144        auto const __test_fn = [=]() -> bool {
145            return __phase.load(memory_order_acquire) != __old_phase;
146        };
147        __libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());
148    }
149    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
150    void arrive_and_drop()
151    {
152        __expected_adjustment.fetch_sub(1, memory_order_relaxed);
153        (void)arrive(1);
154    }
155};
156
157#else
158
159/*
160
161The alternative implementation of __barrier_base is a central barrier.
162
163Two versions of this algorithm are provided:
164 1. A fairly straightforward implementation of the litterature for the
165    general case where the completion function is not empty.
166 2. An optimized implementation that exploits 2's complement arithmetic
167    and well-defined overflow in atomic arithmetic, to handle the phase
168    roll-over for free.
169
170*/
171
172template<class _CompletionF>
173class __barrier_base {
174
175    __atomic_base<ptrdiff_t> __expected;
176    __atomic_base<ptrdiff_t> __arrived;
177    _CompletionF             __completion;
178    __atomic_base<bool>      __phase;
179public:
180    using arrival_token = bool;
181
182    static constexpr ptrdiff_t max() noexcept {
183        return numeric_limits<ptrdiff_t>::max();
184    }
185
186    _LIBCPP_INLINE_VISIBILITY
187    __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
188        : __expected(__expected), __arrived(__expected), __completion(move(__completion)), __phase(false)
189    {
190    }
191    [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
192    arrival_token arrive(ptrdiff_t update)
193    {
194        auto const __old_phase = __phase.load(memory_order_relaxed);
195        auto const __result = __arrived.fetch_sub(update, memory_order_acq_rel) - update;
196        auto const new_expected = __expected.load(memory_order_relaxed);
197        if(0 == __result) {
198            __completion();
199            __arrived.store(new_expected, memory_order_relaxed);
200            __phase.store(!__old_phase, memory_order_release);
201            __phase.notify_all();
202        }
203        return __old_phase;
204    }
205    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
206    void wait(arrival_token&& __old_phase) const
207    {
208        __phase.wait(__old_phase, memory_order_acquire);
209    }
210    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
211    void arrive_and_drop()
212    {
213        __expected.fetch_sub(1, memory_order_relaxed);
214        (void)arrive(1);
215    }
216};
217
218template<>
219class __barrier_base<__empty_completion> {
220
221    static constexpr uint64_t __expected_unit = 1ull;
222    static constexpr uint64_t __arrived_unit = 1ull << 32;
223    static constexpr uint64_t __expected_mask = __arrived_unit - 1;
224    static constexpr uint64_t __phase_bit = 1ull << 63;
225    static constexpr uint64_t __arrived_mask = (__phase_bit - 1) & ~__expected_mask;
226
227    __atomic_base<uint64_t>   __phase_arrived_expected;
228
229    static _LIBCPP_INLINE_VISIBILITY
230    constexpr uint64_t __init(ptrdiff_t __count) _NOEXCEPT
231    {
232        return ((uint64_t(1u << 31) - __count) << 32)
233              | (uint64_t(1u << 31) - __count);
234    }
235
236public:
237    using arrival_token = uint64_t;
238
239    static constexpr ptrdiff_t max() noexcept {
240        return ptrdiff_t(1u << 31) - 1;
241    }
242
243    _LIBCPP_INLINE_VISIBILITY
244    explicit inline __barrier_base(ptrdiff_t __count, __empty_completion = __empty_completion())
245        : __phase_arrived_expected(__init(__count))
246    {
247    }
248    [[nodiscard]] inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
249    arrival_token arrive(ptrdiff_t update)
250    {
251        auto const __inc = __arrived_unit * update;
252        auto const __old = __phase_arrived_expected.fetch_add(__inc, memory_order_acq_rel);
253        if((__old ^ (__old + __inc)) & __phase_bit) {
254            __phase_arrived_expected.fetch_add((__old & __expected_mask) << 32, memory_order_relaxed);
255            __phase_arrived_expected.notify_all();
256        }
257        return __old & __phase_bit;
258    }
259    inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
260    void wait(arrival_token&& __phase) const
261    {
262        auto const __test_fn = [=]() -> bool {
263            uint64_t const __current = __phase_arrived_expected.load(memory_order_acquire);
264            return ((__current & __phase_bit) != __phase);
265        };
266        __libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());
267    }
268    inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
269    void arrive_and_drop()
270    {
271        __phase_arrived_expected.fetch_add(__expected_unit, memory_order_relaxed);
272        (void)arrive(1);
273    }
274};
275
276#endif //_LIBCPP_HAS_NO_TREE_BARRIER
277
278template<class _CompletionF = __empty_completion>
279class barrier {
280
281    __barrier_base<_CompletionF> __b;
282public:
283    using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
284
285    static constexpr ptrdiff_t max() noexcept {
286        return __barrier_base<_CompletionF>::max();
287    }
288
289    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
290    barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
291        : __b(__count, std::move(__completion)) {
292    }
293
294    barrier(barrier const&) = delete;
295    barrier& operator=(barrier const&) = delete;
296
297    [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
298    arrival_token arrive(ptrdiff_t update = 1)
299    {
300        return __b.arrive(update);
301    }
302    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
303    void wait(arrival_token&& __phase) const
304    {
305        __b.wait(std::move(__phase));
306    }
307	_LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
308    void arrive_and_wait()
309    {
310        wait(arrive());
311	}
312    _LIBCPP_AVAILABILITY_SYNC _LIBCPP_INLINE_VISIBILITY
313    void arrive_and_drop()
314    {
315        __b.arrive_and_drop();
316    }
317};
318
319_LIBCPP_END_NAMESPACE_STD
320
321#endif // _LIBCPP_STD_VER >= 14
322
323#endif //_LIBCPP_BARRIER
324