207 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_BARRIER11#define _LIBCPP_BARRIER12 13/*14 barrier synopsis15 16namespace std17{18 19 template<class CompletionFunction = see below>20 class barrier // since C++2021 {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 only42 };43 44}45 46*/47 48#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)49# include <__cxx03/__config>50#else51# include <__config>52 53# if _LIBCPP_HAS_THREADS54 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_header69# endif70 71_LIBCPP_PUSH_MACROS72# include <__undef_macros>73 74# if _LIBCPP_STD_VER >= 2075 76_LIBCPP_BEGIN_NAMESPACE_STD77 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 thrashing91 by flattening the tree structure into cache-line sized arrays, that92 are indexed in an efficient way.93 94*/95 96using __barrier_phase_t _LIBCPP_NODEBUG = uint8_t;97 98class __barrier_algorithm_base;99 100[[__gnu__::__returns_nonnull__, __gnu__::__malloc__]]101_LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base* __construct_barrier_algorithm_base(ptrdiff_t& __expected);102 103_LIBCPP_EXPORTED_FROM_ABI bool104__arrive_barrier_algorithm_base([[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier,105 __barrier_phase_t __old_phase) noexcept;106 107_LIBCPP_EXPORTED_FROM_ABI void __destroy_barrier_algorithm_base(108 [[__gnu__::__nonnull__]] _LIBCPP_NOESCAPE __barrier_algorithm_base* __barrier) noexcept;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(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(memory_order_relaxed);134 for (; __update; --__update)135 if (__arrive_barrier_algorithm_base(__base_.get(), __old_phase)) {136 __completion_();137 __expected_ += __expected_adjustment_.load(memory_order_relaxed);138 __expected_adjustment_.store(0, memory_order_relaxed);139 __phase_.store(__old_phase + 2, 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 auto const __test_fn = [this, __old_phase]() -> bool { return __phase_.load(memory_order_acquire) != __old_phase; };146 std::__libcpp_thread_poll_with_backoff(__test_fn, __libcpp_timed_backoff_policy());147 }148 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {149 __expected_adjustment_.fetch_sub(1, memory_order_relaxed);150 (void)arrive(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 [[nodiscard]] static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept {162 return __barrier_base<_CompletionF>::max();163 }164 165 _LIBCPP_HIDE_FROM_ABI explicit barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())166 : __b_(__count, std::move(__completion)) {167 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(168 __count >= 0,169 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with a negative value");170 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(171 __count <= max(),172 "barrier::barrier(ptrdiff_t, CompletionFunction): barrier cannot be initialized with "173 "a value greater than max()");174 }175 176 barrier(barrier const&) = delete;177 barrier& operator=(barrier const&) = delete;178 179 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI arrival_token arrive(ptrdiff_t __update = 1) {180 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__update > 0, "barrier:arrive must be called with a value greater than 0");181 return __b_.arrive(__update);182 }183 _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const { __b_.wait(std::move(__phase)); }184 _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(arrive()); }185 _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }186};187 188_LIBCPP_END_NAMESPACE_STD189 190# endif // _LIBCPP_STD_VER >= 20191 192_LIBCPP_POP_MACROS193 194# endif // _LIBCPP_HAS_THREADS195 196# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20197# include <atomic>198# include <concepts>199# include <iterator>200# include <memory>201# include <stdexcept>202# include <variant>203# endif204#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)205 206#endif // _LIBCPP_BARRIER207