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