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 // since C++20
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#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
49# include <__cxx03/__config>
50#else
51# include <__config>
52
53# if _LIBCPP_HAS_THREADS
54
55# include <__assert>
56# include <__atomic/atomic.h>
57# include <__atomic/memory_order.h>
58# include <__cstddef/ptrdiff_t.h>
59# include <__memory/unique_ptr.h>
60# include <__thread/poll_with_backoff.h>
61# include <__thread/timed_backoff_policy.h>
62# include <__utility/move.h>
63# include <cstdint>
64# include <limits>
65# include <version>
66
67# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
68# pragma GCC system_header
69# endif
70
71_LIBCPP_PUSH_MACROS
72# include <__undef_macros>
73
74# if _LIBCPP_STD_VER >= 20
75
76_LIBCPP_BEGIN_NAMESPACE_STD
77
78struct __empty_completion {
79 inline _LIBCPP_HIDE_FROM_ABI void operator()() noexcept {}
80};
81
82/*
83
84The default implementation of __barrier_base is a classic tree barrier.
85
86It looks different from literature pseudocode for two main reasons:
87 1. Threads that call into std::barrier functions do not provide indices,
88 so a numbering step is added before the actual barrier algorithm,
89 appearing as an N+1 round to the N rounds of the tree barrier.
90 2. A great deal of attention has been paid to avoid cache line thrashing
91 by flattening the tree structure into cache-line sized arrays, that
92 are indexed in an efficient way.
93
94*/
95
96using __barrier_phase_t _LIBCPP_NODEBUG = uint8_t;
97
98class __barrier_algorithm_base;
99
100_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base*
101__construct_barrier_algorithm_base(ptrdiff_t& __expected);
102
103_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI bool
104__arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier, __barrier_phase_t __old_phase) noexcept;
105
106_LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI void
107__destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier) noexcept;
108
109template <class _CompletionF>
110class __barrier_base {
111 ptrdiff_t __expected_;
112 unique_ptr<__barrier_algorithm_base, void (*)(__barrier_algorithm_base*)> __base_;
113 atomic<ptrdiff_t> __expected_adjustment_;
114 _CompletionF __completion_;
115 atomic<__barrier_phase_t> __phase_;
116
117public:
118 using arrival_token = __barrier_phase_t;
119
120 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
121
122 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI
123 __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
124 : __expected_(__expected),
125 __base_(std::__construct_barrier_algorithm_base(expected&: this->__expected_), &__destroy_barrier_algorithm_base),
126 __expected_adjustment_(0),
127 __completion_(std::move(__completion)),
128 __phase_(0) {}
129 [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update) {
130 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
131 __update <= __expected_, "update is greater than the expected count for the current barrier phase");
132
133 auto const __old_phase = __phase_.load(m: memory_order_relaxed);
134 for (; __update; --__update)
135 if (__arrive_barrier_algorithm_base(barrier: __base_.get(), __old_phase)) {
136 __completion_();
137 __expected_ += __expected_adjustment_.load(m: memory_order_relaxed);
138 __expected_adjustment_.store(d: 0, m: memory_order_relaxed);
139 __phase_.store(d: __old_phase + 2, m: memory_order_release);
140 __phase_.notify_all();
141 }
142 return __old_phase;
143 }
144 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __old_phase) const {
145 auto const __test_fn = [this, __old_phase]() -> bool { return __phase_.load(m: memory_order_acquire) != __old_phase; };
146 std::__libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());
147 }
148 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
149 __expected_adjustment_.fetch_sub(op: 1, m: memory_order_relaxed);
150 (void)arrive(update: 1);
151 }
152};
153
154template <class _CompletionF = __empty_completion>
155class barrier {
156 __barrier_base<_CompletionF> __b_;
157
158public:
159 using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
160
161 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return __barrier_base<_CompletionF>::max(); }
162
163 _LIBCPP_AVAILABILITY_SYNC
164 _LIBCPP_HIDE_FROM_ABI explicit barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
165 : __b_(__count, std::move(__completion)) {
166 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
167 __count >= 0,
168 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with a negative value");
169 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
170 __count <= max(),
171 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with "
172 "a value greater than max()");
173 }
174
175 barrier(barrier const&) = delete;
176 barrier& operator=(barrier const&) = delete;
177
178 [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update = 1) {
179 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__update > 0, "barrier:arrive must be called with a value greater than 0");
180 return __b_.arrive(__update);
181 }
182 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const {
183 __b_.wait(std::move(__phase));
184 }
185 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(phase: arrive()); }
186 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }
187};
188
189_LIBCPP_END_NAMESPACE_STD
190
191# endif // _LIBCPP_STD_VER >= 20
192
193_LIBCPP_POP_MACROS
194
195# endif // _LIBCPP_HAS_THREADS
196
197# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
198# include <atomic>
199# include <concepts>
200# include <iterator>
201# include <memory>
202# include <stdexcept>
203# include <variant>
204# endif
205#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
206
207#endif // _LIBCPP_BARRIER
208