Warning, /include/c++/v1/__cxx03/barrier is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03_BARRIER
0011 #define _LIBCPP___CXX03_BARRIER
0012
0013 /*
0014 barrier synopsis
0015
0016 namespace std
0017 {
0018
0019 template<class CompletionFunction = see below>
0020 class barrier
0021 {
0022 public:
0023 using arrival_token = see below;
0024
0025 static constexpr ptrdiff_t max() noexcept;
0026
0027 constexpr explicit barrier(ptrdiff_t phase_count,
0028 CompletionFunction f = CompletionFunction());
0029 ~barrier();
0030
0031 barrier(const barrier&) = delete;
0032 barrier& operator=(const barrier&) = delete;
0033
0034 [[nodiscard]] arrival_token arrive(ptrdiff_t update = 1);
0035 void wait(arrival_token&& arrival) const;
0036
0037 void arrive_and_wait();
0038 void arrive_and_drop();
0039
0040 private:
0041 CompletionFunction completion; // exposition only
0042 };
0043
0044 }
0045
0046 */
0047
0048 #include <__cxx03/__config>
0049
0050 #if !defined(_LIBCPP_HAS_NO_THREADS)
0051
0052 # include <__cxx03/__assert>
0053 # include <__cxx03/__atomic/atomic_base.h>
0054 # include <__cxx03/__atomic/memory_order.h>
0055 # include <__cxx03/__memory/unique_ptr.h>
0056 # include <__cxx03/__thread/poll_with_backoff.h>
0057 # include <__cxx03/__thread/timed_backoff_policy.h>
0058 # include <__cxx03/__utility/move.h>
0059 # include <__cxx03/cstddef>
0060 # include <__cxx03/cstdint>
0061 # include <__cxx03/limits>
0062 # include <__cxx03/version>
0063
0064 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0065 # pragma GCC system_header
0066 # endif
0067
0068 _LIBCPP_PUSH_MACROS
0069 # include <__cxx03/__undef_macros>
0070
0071 # if _LIBCPP_STD_VER >= 14
0072
0073 _LIBCPP_BEGIN_NAMESPACE_STD
0074
0075 struct __empty_completion {
0076 inline _LIBCPP_HIDE_FROM_ABI void operator()() noexcept {}
0077 };
0078
0079 # ifndef _LIBCPP_HAS_NO_TREE_BARRIER
0080
0081 /*
0082
0083 The default implementation of __barrier_base is a classic tree barrier.
0084
0085 It looks different from literature pseudocode for two main reasons:
0086 1. Threads that call into std::barrier functions do not provide indices,
0087 so a numbering step is added before the actual barrier algorithm,
0088 appearing as an N+1 round to the N rounds of the tree barrier.
0089 2. A great deal of attention has been paid to avoid cache line thrashing
0090 by flattening the tree structure into cache-line sized arrays, that
0091 are indexed in an efficient way.
0092
0093 */
0094
0095 using __barrier_phase_t = uint8_t;
0096
0097 class __barrier_algorithm_base;
0098
0099 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base*
0100 __construct_barrier_algorithm_base(ptrdiff_t& __expected);
0101
0102 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI bool
0103 __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier, __barrier_phase_t __old_phase) noexcept;
0104
0105 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI void
0106 __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier) noexcept;
0107
0108 template <class _CompletionF>
0109 class __barrier_base {
0110 ptrdiff_t __expected_;
0111 unique_ptr<__barrier_algorithm_base, void (*)(__barrier_algorithm_base*)> __base_;
0112 __atomic_base<ptrdiff_t> __expected_adjustment_;
0113 _CompletionF __completion_;
0114 __atomic_base<__barrier_phase_t> __phase_;
0115
0116 public:
0117 using arrival_token = __barrier_phase_t;
0118
0119 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
0120
0121 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI
0122 __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
0123 : __expected_(__expected),
0124 __base_(std::__construct_barrier_algorithm_base(this->__expected_), &__destroy_barrier_algorithm_base),
0125 __expected_adjustment_(0),
0126 __completion_(std::move(__completion)),
0127 __phase_(0) {}
0128 _LIBCPP_NODISCARD _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update) {
0129 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
0130 __update <= __expected_, "update is greater than the expected count for the current barrier phase");
0131
0132 auto const __old_phase = __phase_.load(memory_order_relaxed);
0133 for (; __update; --__update)
0134 if (__arrive_barrier_algorithm_base(__base_.get(), __old_phase)) {
0135 __completion_();
0136 __expected_ += __expected_adjustment_.load(memory_order_relaxed);
0137 __expected_adjustment_.store(0, memory_order_relaxed);
0138 __phase_.store(__old_phase + 2, memory_order_release);
0139 __phase_.notify_all();
0140 }
0141 return __old_phase;
0142 }
0143 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __old_phase) const {
0144 auto const __test_fn = [this, __old_phase]() -> bool { return __phase_.load(memory_order_acquire) != __old_phase; };
0145 std::__libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());
0146 }
0147 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
0148 __expected_adjustment_.fetch_sub(1, memory_order_relaxed);
0149 (void)arrive(1);
0150 }
0151 };
0152
0153 # else
0154
0155 /*
0156
0157 The alternative implementation of __barrier_base is a central barrier.
0158
0159 Two versions of this algorithm are provided:
0160 1. A fairly straightforward implementation of the litterature for the
0161 general case where the completion function is not empty.
0162 2. An optimized implementation that exploits 2's complement arithmetic
0163 and well-defined overflow in atomic arithmetic, to handle the phase
0164 roll-over for free.
0165
0166 */
0167
0168 template <class _CompletionF>
0169 class __barrier_base {
0170 __atomic_base<ptrdiff_t> __expected;
0171 __atomic_base<ptrdiff_t> __arrived;
0172 _CompletionF __completion;
0173 __atomic_base<bool> __phase;
0174
0175 public:
0176 using arrival_token = bool;
0177
0178 static constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
0179
0180 _LIBCPP_HIDE_FROM_ABI __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF())
0181 : __expected(__expected), __arrived(__expected), __completion(std::move(__completion)), __phase(false) {}
0182 [[nodiscard]] _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t update) {
0183 auto const __old_phase = __phase.load(memory_order_relaxed);
0184 auto const __result = __arrived.fetch_sub(update, memory_order_acq_rel) - update;
0185 auto const new_expected = __expected.load(memory_order_relaxed);
0186
0187 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
0188 update <= new_expected, "update is greater than the expected count for the current barrier phase");
0189
0190 if (0 == __result) {
0191 __completion();
0192 __arrived.store(new_expected, memory_order_relaxed);
0193 __phase.store(!__old_phase, memory_order_release);
0194 __phase.notify_all();
0195 }
0196 return __old_phase;
0197 }
0198 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __old_phase) const {
0199 __phase.wait(__old_phase, memory_order_acquire);
0200 }
0201 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
0202 __expected.fetch_sub(1, memory_order_relaxed);
0203 (void)arrive(1);
0204 }
0205 };
0206
0207 template <>
0208 class __barrier_base<__empty_completion> {
0209 static constexpr uint64_t __expected_unit = 1ull;
0210 static constexpr uint64_t __arrived_unit = 1ull << 32;
0211 static constexpr uint64_t __expected_mask = __arrived_unit - 1;
0212 static constexpr uint64_t __phase_bit = 1ull << 63;
0213 static constexpr uint64_t __arrived_mask = (__phase_bit - 1) & ~__expected_mask;
0214
0215 __atomic_base<uint64_t> __phase_arrived_expected;
0216
0217 static _LIBCPP_HIDE_FROM_ABI constexpr uint64_t __init(ptrdiff_t __count) _NOEXCEPT {
0218 return ((uint64_t(1u << 31) - __count) << 32) | (uint64_t(1u << 31) - __count);
0219 }
0220
0221 public:
0222 using arrival_token = uint64_t;
0223
0224 static constexpr ptrdiff_t max() noexcept { return ptrdiff_t(1u << 31) - 1; }
0225
0226 _LIBCPP_HIDE_FROM_ABI explicit inline __barrier_base(ptrdiff_t __count, __empty_completion = __empty_completion())
0227 : __phase_arrived_expected(__init(__count)) {}
0228 [[nodiscard]] inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t update) {
0229 auto const __inc = __arrived_unit * update;
0230 auto const __old = __phase_arrived_expected.fetch_add(__inc, memory_order_acq_rel);
0231
0232 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
0233 update <= __old, "update is greater than the expected count for the current barrier phase");
0234
0235 if ((__old ^ (__old + __inc)) & __phase_bit) {
0236 __phase_arrived_expected.fetch_add((__old & __expected_mask) << 32, memory_order_relaxed);
0237 __phase_arrived_expected.notify_all();
0238 }
0239 return __old & __phase_bit;
0240 }
0241 inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const {
0242 auto const __test_fn = [=]() -> bool {
0243 uint64_t const __current = __phase_arrived_expected.load(memory_order_acquire);
0244 return ((__current & __phase_bit) != __phase);
0245 };
0246 __libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());
0247 }
0248 inline _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
0249 __phase_arrived_expected.fetch_add(__expected_unit, memory_order_relaxed);
0250 (void)arrive(1);
0251 }
0252 };
0253
0254 # endif // !_LIBCPP_HAS_NO_TREE_BARRIER
0255
0256 template <class _CompletionF = __empty_completion>
0257 class _LIBCPP_DEPRECATED_ATOMIC_SYNC barrier {
0258 __barrier_base<_CompletionF> __b_;
0259
0260 public:
0261 using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
0262
0263 static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return __barrier_base<_CompletionF>::max(); }
0264
0265 _LIBCPP_AVAILABILITY_SYNC
0266 _LIBCPP_HIDE_FROM_ABI explicit barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
0267 : __b_(__count, std::move(__completion)) {
0268 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
0269 __count >= 0,
0270 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with a negative value");
0271 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
0272 __count <= max(),
0273 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with "
0274 "a value greater than max()");
0275 }
0276
0277 barrier(barrier const&) = delete;
0278 barrier& operator=(barrier const&) = delete;
0279
0280 _LIBCPP_NODISCARD _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update = 1) {
0281 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__update > 0, "barrier:arrive must be called with a value greater than 0");
0282 return __b_.arrive(__update);
0283 }
0284 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const {
0285 __b_.wait(std::move(__phase));
0286 }
0287 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(arrive()); }
0288 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }
0289 };
0290
0291 _LIBCPP_END_NAMESPACE_STD
0292
0293 # endif // _LIBCPP_STD_VER >= 14
0294
0295 _LIBCPP_POP_MACROS
0296
0297 #endif // !defined(_LIBCPP_HAS_NO_THREADS)
0298
0299 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0300 # include <__cxx03/atomic>
0301 # include <__cxx03/concepts>
0302 # include <__cxx03/iterator>
0303 # include <__cxx03/memory>
0304 # include <__cxx03/stdexcept>
0305 # include <__cxx03/variant>
0306 #endif
0307
0308 #endif //_LIBCPP___CXX03_BARRIER
