xref: /netbsd-src/external/apache2/llvm/dist/libcxx/src/barrier.cpp (revision 4d6fc14bc9b0c5bf3e30be318c143ee82cadd108)
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