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