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 <__utility/move.h>
61# include <cstdint>
62# include <limits>
63# include <version>
64
65# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
66# pragma GCC system_header
67# endif
68
69_LIBCPP_PUSH_MACROS
70# include <__undef_macros>
71
72# if _LIBCPP_STD_VER >= 20
73
74_LIBCPP_BEGIN_NAMESPACE_STD
75
76struct __empty_completion {
77 inline _LIBCPP_HIDE_FROM_ABI void operator()() noexcept {}
78};
79
80/*
81
82The default implementation of __barrier_base is a classic tree barrier.
83
84It looks different from literature pseudocode for two main reasons:
85 1. Threads that call into std::barrier functions do not provide indices,
86 so a numbering step is added before the actual barrier algorithm,
87 appearing as an N+1 round to the N rounds of the tree barrier.
88 2. A great deal of attention has been paid to avoid cache line thrashing
89 by flattening the tree structure into cache-line sized arrays, that
90 are indexed in an efficient way.
91
92*/
93
94using __barrier_phase_t _LIBCPP_NODEBUG = uint8_t;
95
96class __barrier_algorithm_base;
97
98_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
99[[__gnu__::__returns_nonnull__, __gnu__::__malloc__]]
100_LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base* __construct_barrier_algorithm_base(ptrdiff_t& __expected);
101
102_LIBCPP_EXPORTED_FROM_ABI bool
103__arrive_barrier_algorithm_base([[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier,
104 __barrier_phase_t __old_phase) noexcept;
105
106_LIBCPP_EXPORTED_FROM_ABI void __destroy_barrier_algorithm_base(
107 [[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier) noexcept;
108_LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS
109
110template <class _CompletionF>
111class __barrier_base {
112 ptrdiff_t __expected_;
113 unique_ptr<__barrier_algorithm_base, void (*)(_LIBCPP_NOESCAPE __barrier_algorithm_base*)> __base_;
114 atomic<ptrdiff_t> __expected_adjustment_;
115 _CompletionF __completion_;
116 atomic<__barrier_phase_t> __phase_;
117
118public:
119 using arrival_token = __barrier_phase_t;
120
121 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
122
123 _LIBCPP_HIDE_FROM_ABI __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_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_HIDE_FROM_ABI void wait(arrival_token&& __old_phase) const {
145 __phase_.wait(v: __old_phase, m: std::memory_order_acquire);
146 }
147 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
148 __expected_adjustment_.fetch_sub(op: 1, m: memory_order_relaxed);
149 (void)arrive(update: 1);
150 }
151};
152
153template <class _CompletionF = __empty_completion>
154class barrier {
155 __barrier_base<_CompletionF> __b_;
156
157public:
158 using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
159
160 [[nodiscard]] static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept {
161 return __barrier_base<_CompletionF>::max();
162 }
163
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_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_HIDE_FROM_ABI void wait(arrival_token&& __phase) const { __b_.wait(std::move(__phase)); }
183 _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(phase: arrive()); }
184 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }
185};
186
187_LIBCPP_END_NAMESPACE_STD
188
189# endif // _LIBCPP_STD_VER >= 20
190
191_LIBCPP_POP_MACROS
192
193# endif // _LIBCPP_HAS_THREADS
194
195# if defined(_LIBCPP_KEEP_TRANSITIVE_INCLUDES_LLVM23) && _LIBCPP_STD_VER <= 20
196# include <atomic>
197# include <concepts>
198# include <iterator>
199# include <memory>
200# include <stdexcept>
201# include <variant>
202# endif
203#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
204
205#endif // _LIBCPP_BARRIER
206