]>
Commit | Line | Data |
---|---|---|
b7c3f201 TR |
1 | // <barrier> -*- C++ -*- |
2 | ||
6441eb6d | 3 | // Copyright (C) 2020-2025 Free Software Foundation, Inc. |
b7c3f201 TR |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
d7f282c4 JW |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
b7c3f201 TR |
23 | // <http://www.gnu.org/licenses/>. |
24 | ||
25 | // This implementation is based on libcxx/include/barrier | |
26 | //===-- barrier.h --------------------------------------------------===// | |
27 | // | |
28 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
29 | // See https://llvm.org/LICENSE.txt for license information. | |
30 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
31 | // | |
32 | //===---------------------------------------------------------------===// | |
33 | ||
34 | /** @file include/barrier | |
35 | * This is a Standard C++ Library header. | |
36 | */ | |
37 | ||
38 | #ifndef _GLIBCXX_BARRIER | |
39 | #define _GLIBCXX_BARRIER 1 | |
40 | ||
63a598de | 41 | #ifdef _GLIBCXX_SYSHDR |
b7c3f201 | 42 | #pragma GCC system_header |
63a598de | 43 | #endif |
b7c3f201 | 44 | |
18f176d0 AA |
45 | #include <bits/requires_hosted.h> // threading primitive |
46 | ||
083b7f28 AA |
47 | #define __glibcxx_want_barrier |
48 | #include <bits/version.h> | |
49 | ||
50 | #ifdef __cpp_lib_barrier // C++ >= 20 && __cpp_aligned_new && lib_atomic_wait | |
b7c3f201 | 51 | #include <bits/atomic_base.h> |
b7c3f201 TR |
52 | #include <bits/std_thread.h> |
53 | #include <bits/unique_ptr.h> | |
54 | ||
55 | #include <array> | |
56 | ||
b7c3f201 TR |
57 | namespace std _GLIBCXX_VISIBILITY(default) |
58 | { | |
59 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
60 | ||
61 | struct __empty_completion | |
62 | { | |
63 | _GLIBCXX_ALWAYS_INLINE void | |
64 | operator()() noexcept | |
65 | { } | |
66 | }; | |
67 | ||
68 | /* | |
69 | ||
70 | The default implementation of __tree_barrier is a classic tree barrier. | |
71 | ||
72 | It looks different from literature pseudocode for two main reasons: | |
73 | 1. Threads that call into std::barrier functions do not provide indices, | |
74 | so a numbering step is added before the actual barrier algorithm, | |
75 | appearing as an N+1 round to the N rounds of the tree barrier. | |
76 | 2. A great deal of attention has been paid to avoid cache line thrashing | |
77 | by flattening the tree structure into cache-line sized arrays, that | |
78 | are indexed in an efficient way. | |
79 | ||
80 | */ | |
81 | ||
82 | enum class __barrier_phase_t : unsigned char { }; | |
83 | ||
42fc1e97 JW |
84 | struct __tree_barrier_base |
85 | { | |
86 | static constexpr ptrdiff_t | |
87 | max() noexcept | |
88 | { return __PTRDIFF_MAX__ - 1; } | |
89 | ||
90 | protected: | |
91 | using __atomic_phase_ref_t = std::__atomic_ref<__barrier_phase_t>; | |
92 | using __atomic_phase_const_ref_t = std::__atomic_ref<const __barrier_phase_t>; | |
93 | static constexpr auto __phase_alignment = | |
94 | __atomic_phase_ref_t::required_alignment; | |
95 | ||
96 | using __tickets_t = std::array<__barrier_phase_t, 64>; | |
97 | struct alignas(64) /* naturally-align the heap state */ __state_t | |
b7c3f201 | 98 | { |
42fc1e97 JW |
99 | alignas(__phase_alignment) __tickets_t __tickets; |
100 | }; | |
b7c3f201 | 101 | |
42fc1e97 JW |
102 | ptrdiff_t _M_expected; |
103 | __atomic_base<__state_t*> _M_state{nullptr}; | |
104 | __atomic_base<ptrdiff_t> _M_expected_adjustment{0}; | |
105 | alignas(__phase_alignment) __barrier_phase_t _M_phase{}; | |
b7c3f201 | 106 | |
42fc1e97 JW |
107 | explicit constexpr |
108 | __tree_barrier_base(ptrdiff_t __expected) | |
109 | : _M_expected(__expected) | |
110 | { | |
111 | __glibcxx_assert(__expected >= 0 && __expected <= max()); | |
b7c3f201 | 112 | |
42fc1e97 JW |
113 | if (!std::is_constant_evaluated()) |
114 | _M_state.store(_M_alloc_state().release(), memory_order_release); | |
115 | } | |
b7c3f201 | 116 | |
42fc1e97 JW |
117 | unique_ptr<__state_t[]> |
118 | _M_alloc_state() | |
119 | { | |
120 | size_t const __count = (_M_expected + 1) >> 1; | |
121 | return std::make_unique<__state_t[]>(__count); | |
122 | } | |
b7c3f201 | 123 | |
42fc1e97 JW |
124 | bool |
125 | _M_arrive(__barrier_phase_t __old_phase, size_t __current) | |
126 | { | |
127 | const auto __old_phase_val = static_cast<unsigned char>(__old_phase); | |
128 | const auto __half_step = | |
129 | static_cast<__barrier_phase_t>(__old_phase_val + 1); | |
130 | const auto __full_step = | |
131 | static_cast<__barrier_phase_t>(__old_phase_val + 2); | |
132 | ||
133 | size_t __current_expected = _M_expected; | |
134 | __current %= ((_M_expected + 1) >> 1); | |
135 | ||
136 | __state_t* const __state = _M_state.load(memory_order_relaxed); | |
137 | ||
138 | for (int __round = 0; ; ++__round) | |
139 | { | |
140 | if (__current_expected <= 1) | |
141 | return true; | |
142 | size_t const __end_node = ((__current_expected + 1) >> 1), | |
143 | __last_node = __end_node - 1; | |
144 | for ( ; ; ++__current) | |
145 | { | |
146 | if (__current == __end_node) | |
147 | __current = 0; | |
148 | auto __expect = __old_phase; | |
149 | __atomic_phase_ref_t __phase(__state[__current] | |
150 | .__tickets[__round]); | |
151 | if (__current == __last_node && (__current_expected & 1)) | |
152 | { | |
153 | if (__phase.compare_exchange_strong(__expect, __full_step, | |
154 | memory_order_acq_rel)) | |
155 | break; // I'm 1 in 1, go to next __round | |
156 | } | |
157 | else if (__phase.compare_exchange_strong(__expect, __half_step, | |
158 | memory_order_acq_rel)) | |
159 | { | |
160 | return false; // I'm 1 in 2, done with arrival | |
161 | } | |
162 | else if (__expect == __half_step) | |
163 | { | |
164 | if (__phase.compare_exchange_strong(__expect, __full_step, | |
165 | memory_order_acq_rel)) | |
166 | break; // I'm 2 in 2, go to next __round | |
167 | } | |
168 | } | |
169 | __current_expected = __last_node + 1; | |
170 | __current >>= 1; | |
171 | } | |
172 | } | |
173 | }; | |
ef632273 | 174 | |
42fc1e97 JW |
175 | template<typename _CompletionF> |
176 | class __tree_barrier : public __tree_barrier_base | |
177 | { | |
178 | [[no_unique_address]] _CompletionF _M_completion; | |
b7c3f201 | 179 | |
ef632273 JW |
180 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
181 | // 3898. Possibly unintended preconditions for completion functions | |
182 | void _M_invoke_completion() noexcept { _M_completion(); } | |
183 | ||
b7c3f201 TR |
184 | public: |
185 | using arrival_token = __barrier_phase_t; | |
186 | ||
ef632273 | 187 | constexpr |
b7c3f201 | 188 | __tree_barrier(ptrdiff_t __expected, _CompletionF __completion) |
42fc1e97 JW |
189 | : __tree_barrier_base(__expected), _M_completion(std::move(__completion)) |
190 | { } | |
b7c3f201 TR |
191 | |
192 | [[nodiscard]] arrival_token | |
193 | arrive(ptrdiff_t __update) | |
194 | { | |
ef632273 JW |
195 | __glibcxx_assert(__update > 0); |
196 | // FIXME: Check that update is less than or equal to the expected count | |
197 | // for the current barrier phase. | |
198 | ||
b52aef3a TR |
199 | std::hash<std::thread::id> __hasher; |
200 | size_t __current = __hasher(std::this_thread::get_id()); | |
b7c3f201 TR |
201 | __atomic_phase_ref_t __phase(_M_phase); |
202 | const auto __old_phase = __phase.load(memory_order_relaxed); | |
203 | const auto __cur = static_cast<unsigned char>(__old_phase); | |
ef632273 JW |
204 | |
205 | if (__cur == 0 && !_M_state.load(memory_order_relaxed)) [[unlikely]] | |
b7c3f201 | 206 | { |
42fc1e97 | 207 | auto __p = _M_alloc_state(); |
ef632273 JW |
208 | __state_t* __val = nullptr; |
209 | if (_M_state.compare_exchange_strong(__val, __p.get(), | |
210 | memory_order_seq_cst, | |
211 | memory_order_acquire)) | |
212 | __p.release(); | |
213 | } | |
214 | ||
215 | for (; __update; --__update) | |
216 | { | |
217 | if (_M_arrive(__old_phase, __current)) | |
b7c3f201 | 218 | { |
ef632273 | 219 | _M_invoke_completion(); |
b7c3f201 TR |
220 | _M_expected += _M_expected_adjustment.load(memory_order_relaxed); |
221 | _M_expected_adjustment.store(0, memory_order_relaxed); | |
222 | auto __new_phase = static_cast<__barrier_phase_t>(__cur + 2); | |
223 | __phase.store(__new_phase, memory_order_release); | |
224 | __phase.notify_all(); | |
225 | } | |
226 | } | |
227 | return __old_phase; | |
228 | } | |
229 | ||
230 | void | |
231 | wait(arrival_token&& __old_phase) const | |
232 | { | |
233 | __atomic_phase_const_ref_t __phase(_M_phase); | |
437c147f | 234 | __phase.wait(__old_phase, memory_order_acquire); |
b7c3f201 TR |
235 | } |
236 | ||
237 | void | |
238 | arrive_and_drop() | |
239 | { | |
240 | _M_expected_adjustment.fetch_sub(1, memory_order_relaxed); | |
241 | (void)arrive(1); | |
242 | } | |
243 | }; | |
244 | ||
245 | template<typename _CompletionF = __empty_completion> | |
246 | class barrier | |
247 | { | |
ef632273 JW |
248 | static_assert(is_invocable_v<_CompletionF&>); |
249 | ||
b7c3f201 TR |
250 | // Note, we may introduce a "central" barrier algorithm at some point |
251 | // for more space constrained targets | |
252 | using __algorithm_t = __tree_barrier<_CompletionF>; | |
253 | __algorithm_t _M_b; | |
254 | ||
255 | public: | |
5643f6f3 JW |
256 | class arrival_token final |
257 | { | |
258 | public: | |
259 | arrival_token(arrival_token&&) = default; | |
260 | arrival_token& operator=(arrival_token&&) = default; | |
261 | ~arrival_token() = default; | |
262 | ||
263 | private: | |
264 | friend class barrier; | |
265 | using __token = typename __algorithm_t::arrival_token; | |
266 | explicit arrival_token(__token __tok) noexcept : _M_tok(__tok) { } | |
267 | __token _M_tok; | |
268 | }; | |
b7c3f201 TR |
269 | |
270 | static constexpr ptrdiff_t | |
271 | max() noexcept | |
272 | { return __algorithm_t::max(); } | |
273 | ||
ef632273 | 274 | constexpr explicit |
5643f6f3 JW |
275 | barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF()) |
276 | : _M_b(__count, std::move(__completion)) | |
b7c3f201 TR |
277 | { } |
278 | ||
279 | barrier(barrier const&) = delete; | |
280 | barrier& operator=(barrier const&) = delete; | |
281 | ||
282 | [[nodiscard]] arrival_token | |
283 | arrive(ptrdiff_t __update = 1) | |
5643f6f3 | 284 | { return arrival_token{_M_b.arrive(__update)}; } |
b7c3f201 TR |
285 | |
286 | void | |
287 | wait(arrival_token&& __phase) const | |
5643f6f3 | 288 | { _M_b.wait(std::move(__phase._M_tok)); } |
b7c3f201 TR |
289 | |
290 | void | |
291 | arrive_and_wait() | |
292 | { wait(arrive()); } | |
293 | ||
294 | void | |
295 | arrive_and_drop() | |
296 | { _M_b.arrive_and_drop(); } | |
297 | }; | |
298 | ||
299 | _GLIBCXX_END_NAMESPACE_VERSION | |
300 | } // namespace | |
083b7f28 | 301 | #endif // __cpp_lib_barrier |
b7c3f201 | 302 | #endif // _GLIBCXX_BARRIER |