xref: /llvm-project/libcxx/include/barrier (revision fbb4697c3f08dc3ef69e718b3c43dde494018de3) 
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/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
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 thrashing
91    by flattening the tree structure into cache-line sized arrays, that
92    are indexed in an efficient way.
93
94*/
95
96using __barrier_phase_t _LIBCPP_NODEBUG = uint8_t;
97
98class __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
109template <class _CompletionF>
110class __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
117public:
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
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  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
208