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[[__gnu__::__returns_nonnull__, __gnu__::__malloc__]]
99_LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base* __construct_barrier_algorithm_base(ptrdiff_t& __expected);
100
101_LIBCPP_EXPORTED_FROM_ABI bool
102__arrive_barrier_algorithm_base([[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier,
103 __barrier_phase_t __old_phase) noexcept;
104
105_LIBCPP_EXPORTED_FROM_ABI void __destroy_barrier_algorithm_base(
106 [[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier) noexcept;
107
108template <class _CompletionF>
109class __barrier_base {
110 ptrdiff_t __expected_;
111 unique_ptr<__barrier_algorithm_base, void (*)(_LIBCPP_NOESCAPE __barrier_algorithm_base*)> __base_;
112 atomic<ptrdiff_t> __expected_adjustment_;
113 _CompletionF __completion_;
114 atomic<__barrier_phase_t> __phase_;
115
116public:
117 using arrival_token = __barrier_phase_t;
118
119 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
120
121 _LIBCPP_HIDE_FROM_ABI __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
122 : __expected_(__expected),
123 __base_(std::__construct_barrier_algorithm_base(expected&: this->__expected_), &__destroy_barrier_algorithm_base),
124 __expected_adjustment_(0),
125 __completion_(std::move(__completion)),
126 __phase_(0) {}
127 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update) {
128 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
129 __update <= __expected_, "update is greater than the expected count for the current barrier phase");
130
131 auto const __old_phase = __phase_.load(m: memory_order_relaxed);
132 for (; __update; --__update)
133 if (__arrive_barrier_algorithm_base(barrier: __base_.get(), __old_phase)) {
134 __completion_();
135 __expected_ += __expected_adjustment_.load(m: memory_order_relaxed);
136 __expected_adjustment_.store(d: 0, m: memory_order_relaxed);
137 __phase_.store(d: __old_phase + 2, m: memory_order_release);
138 __phase_.notify_all();
139 }
140 return __old_phase;
141 }
142 _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __old_phase) const {
143 __phase_.wait(v: __old_phase, m: std::memory_order_acquire);
144 }
145 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
146 __expected_adjustment_.fetch_sub(op: 1, m: memory_order_relaxed);
147 (void)arrive(update: 1);
148 }
149};
150
151template <class _CompletionF = __empty_completion>
152class barrier {
153 __barrier_base<_CompletionF> __b_;
154
155public:
156 using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
157
158 [[nodiscard]] static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept {
159 return __barrier_base<_CompletionF>::max();
160 }
161
162 _LIBCPP_HIDE_FROM_ABI explicit barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
163 : __b_(__count, std::move(__completion)) {
164 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
165 __count >= 0,
166 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with a negative value");
167 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
168 __count <= max(),
169 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with "
170 "a value greater than max()");
171 }
172
173 barrier(barrier const&) = delete;
174 barrier& operator=(barrier const&) = delete;
175
176 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update = 1) {
177 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__update > 0, "barrier:arrive must be called with a value greater than 0");
178 return __b_.arrive(__update);
179 }
180 _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const { __b_.wait(std::move(__phase)); }
181 _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(phase: arrive()); }
182 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }
183};
184
185_LIBCPP_END_NAMESPACE_STD
186
187# endif // _LIBCPP_STD_VER >= 20
188
189_LIBCPP_POP_MACROS
190
191# endif // _LIBCPP_HAS_THREADS
192
193# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
194# include <atomic>
195# include <concepts>
196# include <iterator>
197# include <memory>
198# include <stdexcept>
199# include <variant>
200# endif
201#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
202
203#endif // _LIBCPP_BARRIER
204