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