1*4d6fc14bSjoerg //===------------------------- barrier.cpp ---------------------------------===//
2*4d6fc14bSjoerg //
3*4d6fc14bSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*4d6fc14bSjoerg // See https://llvm.org/LICENSE.txt for license information.
5*4d6fc14bSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*4d6fc14bSjoerg //
7*4d6fc14bSjoerg //===----------------------------------------------------------------------===//
8*4d6fc14bSjoerg
9*4d6fc14bSjoerg #include <__config>
10*4d6fc14bSjoerg
11*4d6fc14bSjoerg #ifndef _LIBCPP_HAS_NO_THREADS
12*4d6fc14bSjoerg
13*4d6fc14bSjoerg #include <barrier>
14*4d6fc14bSjoerg #include <thread>
15*4d6fc14bSjoerg
16*4d6fc14bSjoerg _LIBCPP_BEGIN_NAMESPACE_STD
17*4d6fc14bSjoerg
18*4d6fc14bSjoerg #if !defined(_LIBCPP_HAS_NO_TREE_BARRIER) && (_LIBCPP_STD_VER > 11)
19*4d6fc14bSjoerg
20*4d6fc14bSjoerg class __barrier_algorithm_base {
21*4d6fc14bSjoerg public:
22*4d6fc14bSjoerg struct alignas(64) /* naturally-align the heap state */ __state_t
23*4d6fc14bSjoerg {
24*4d6fc14bSjoerg struct {
25*4d6fc14bSjoerg __atomic_base<__barrier_phase_t> __phase = ATOMIC_VAR_INIT(0);
26*4d6fc14bSjoerg } __tickets[64];
27*4d6fc14bSjoerg };
28*4d6fc14bSjoerg
29*4d6fc14bSjoerg ptrdiff_t& __expected;
30*4d6fc14bSjoerg unique_ptr<__state_t[]> __state;
31*4d6fc14bSjoerg
32*4d6fc14bSjoerg _LIBCPP_HIDDEN
__barrier_algorithm_base(ptrdiff_t & __expected)33*4d6fc14bSjoerg __barrier_algorithm_base(ptrdiff_t& __expected)
34*4d6fc14bSjoerg : __expected(__expected)
35*4d6fc14bSjoerg {
36*4d6fc14bSjoerg size_t const __count = (__expected + 1) >> 1;
37*4d6fc14bSjoerg __state = unique_ptr<__state_t[]>(new __state_t[__count]);
38*4d6fc14bSjoerg }
39*4d6fc14bSjoerg _LIBCPP_HIDDEN
__arrive(__barrier_phase_t __old_phase)40*4d6fc14bSjoerg bool __arrive(__barrier_phase_t __old_phase)
41*4d6fc14bSjoerg {
42*4d6fc14bSjoerg __barrier_phase_t const __half_step = __old_phase + 1,
43*4d6fc14bSjoerg __full_step = __old_phase + 2;
44*4d6fc14bSjoerg size_t __current_expected = __expected,
45*4d6fc14bSjoerg __current = hash<thread::id>()(this_thread::get_id()) % ((__expected + 1) >> 1);
46*4d6fc14bSjoerg for(int __round = 0;; ++__round) {
47*4d6fc14bSjoerg if(__current_expected <= 1)
48*4d6fc14bSjoerg return true;
49*4d6fc14bSjoerg size_t const __end_node = ((__current_expected + 1) >> 1),
50*4d6fc14bSjoerg __last_node = __end_node - 1;
51*4d6fc14bSjoerg for(;;++__current) {
52*4d6fc14bSjoerg if(__current == __end_node)
53*4d6fc14bSjoerg __current = 0;
54*4d6fc14bSjoerg __barrier_phase_t expect = __old_phase;
55*4d6fc14bSjoerg if(__current == __last_node && (__current_expected & 1))
56*4d6fc14bSjoerg {
57*4d6fc14bSjoerg if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
58*4d6fc14bSjoerg break; // I'm 1 in 1, go to next __round
59*4d6fc14bSjoerg }
60*4d6fc14bSjoerg else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel))
61*4d6fc14bSjoerg {
62*4d6fc14bSjoerg return false; // I'm 1 in 2, done with arrival
63*4d6fc14bSjoerg }
64*4d6fc14bSjoerg else if(expect == __half_step)
65*4d6fc14bSjoerg {
66*4d6fc14bSjoerg if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
67*4d6fc14bSjoerg break; // I'm 2 in 2, go to next __round
68*4d6fc14bSjoerg }
69*4d6fc14bSjoerg }
70*4d6fc14bSjoerg __current_expected = __last_node + 1;
71*4d6fc14bSjoerg __current >>= 1;
72*4d6fc14bSjoerg }
73*4d6fc14bSjoerg }
74*4d6fc14bSjoerg };
75*4d6fc14bSjoerg
76*4d6fc14bSjoerg _LIBCPP_EXPORTED_FROM_ABI
__construct_barrier_algorithm_base(ptrdiff_t & __expected)77*4d6fc14bSjoerg __barrier_algorithm_base * __construct_barrier_algorithm_base(ptrdiff_t& __expected)
78*4d6fc14bSjoerg {
79*4d6fc14bSjoerg return new __barrier_algorithm_base(__expected);
80*4d6fc14bSjoerg }
81*4d6fc14bSjoerg _LIBCPP_EXPORTED_FROM_ABI
__arrive_barrier_algorithm_base(__barrier_algorithm_base * __barrier,__barrier_phase_t __old_phase)82*4d6fc14bSjoerg bool __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier,
83*4d6fc14bSjoerg __barrier_phase_t __old_phase)
84*4d6fc14bSjoerg {
85*4d6fc14bSjoerg return __barrier->__arrive(__old_phase);
86*4d6fc14bSjoerg }
87*4d6fc14bSjoerg _LIBCPP_EXPORTED_FROM_ABI
__destroy_barrier_algorithm_base(__barrier_algorithm_base * __barrier)88*4d6fc14bSjoerg void __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier)
89*4d6fc14bSjoerg {
90*4d6fc14bSjoerg delete __barrier;
91*4d6fc14bSjoerg }
92*4d6fc14bSjoerg
93*4d6fc14bSjoerg #endif //!defined(_LIBCPP_HAS_NO_TREE_BARRIER) && (_LIBCPP_STD_VER >= 11)
94*4d6fc14bSjoerg
95*4d6fc14bSjoerg _LIBCPP_END_NAMESPACE_STD
96*4d6fc14bSjoerg
97*4d6fc14bSjoerg #endif //_LIBCPP_HAS_NO_THREADS
98