libcxx/include/barrier

   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
  16 namespace 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/barrier>
  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 <__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_header
  69 #    endif
  70
  71 _LIBCPP_PUSH_MACROS
  72 #    include <__undef_macros>
  73
  74 #    if _LIBCPP_STD_VER >= 20
  75
  76 _LIBCPP_BEGIN_NAMESPACE_STD
  77
  78 struct __empty_completion {
  79   inline _LIBCPP_HIDE_FROM_ABI void operator()() noexcept {}
  80 };
  81
  82 /*
  83
  84 The default implementation of __barrier_base is a classic tree barrier.
  85
  86 It 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 thrashing
  91     by flattening the tree structure into cache-line sized arrays, that
  92     are indexed in an efficient way.
  93
  94 */
  95
  96 using __barrier_phase_t _LIBCPP_NODEBUG = uint8_t;
  97
  98 class __barrier_algorithm_base;
  99
 100 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI __barrier_algorithm_base*
 101 __construct_barrier_algorithm_base(ptrdiff_t& __expected);
 102
 103 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI bool
 104 __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier, __barrier_phase_t __old_phase) noexcept;
 105
 106 _LIBCPP_AVAILABILITY_SYNC _LIBCPP_EXPORTED_FROM_ABI void
 107 __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier) noexcept;
 108
 109 template <class _CompletionF>
 110 class __barrier_base {
 111   ptrdiff_t __expected_;
 112   unique_ptr<__barrier_algorithm_base, void (*)(__barrier_algorithm_base*)> __base_;
 113   atomic<ptrdiff_t> __expected_adjustment_;
 114   _CompletionF __completion_;
 115   atomic<__barrier_phase_t> __phase_;
 116
 117 public:
 118   using arrival_token = __barrier_phase_t;
 119
 120   static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return numeric_limits<ptrdiff_t>::max(); }
 121
 122   _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI
 123   __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_AVAILABILITY_SYNC _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_AVAILABILITY_SYNC _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_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() {
 149     __expected_adjustment_.fetch_sub(1, memory_order_relaxed);
 150     (void)arrive(1);
 151   }
 152 };
 153
 154 template <class _CompletionF = __empty_completion>
 155 class barrier {
 156   __barrier_base<_CompletionF> __b_;
 157
 158 public:
 159   using arrival_token = typename __barrier_base<_CompletionF>::arrival_token;
 160
 161   static _LIBCPP_HIDE_FROM_ABI constexpr ptrdiff_t max() noexcept { return __barrier_base<_CompletionF>::max(); }
 162
 163   _LIBCPP_AVAILABILITY_SYNC
 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_AVAILABILITY_SYNC _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_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void wait(arrival_token&& __phase) const {
 183     __b_.wait(std::move(__phase));
 184   }
 185   _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_wait() { wait(arrive()); }
 186   _LIBCPP_AVAILABILITY_SYNC _LIBCPP_HIDE_FROM_ABI void arrive_and_drop() { __b_.arrive_and_drop(); }
 187 };
 188
 189 _LIBCPP_END_NAMESPACE_STD
 190
 191 #    endif // _LIBCPP_STD_VER >= 20
 192
 193 _LIBCPP_POP_MACROS
 194
 195 #  endif // _LIBCPP_HAS_THREADS
 196
 197 #  if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 198 #    include <atomic>
 199 #    include <concepts>
 200 #    include <iterator>
 201 #    include <memory>
 202 #    include <stdexcept>
 203 #    include <variant>
 204 #  endif
 205 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
 206
 207 #endif // _LIBCPP_BARRIER