1 //===----------------------------------------------------------------------===// 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) 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{0}; 26 } __tickets[64]; 27 }; 28 29 ptrdiff_t& __expected; 30 unique_ptr<__state_t[]> __state; 31 32 _LIBCPP_HIDDEN 33 __barrier_algorithm_base(ptrdiff_t& __expected) 34 : __expected(__expected) 35 { 36 size_t const __count = (__expected + 1) >> 1; 37 __state = unique_ptr<__state_t[]>(new __state_t[__count]); 38 } 39 _LIBCPP_HIDDEN 40 bool __arrive(__barrier_phase_t __old_phase) 41 { 42 __barrier_phase_t const __half_step = __old_phase + 1, 43 __full_step = __old_phase + 2; 44 size_t __current_expected = __expected, 45 __current = hash<thread::id>()(this_thread::get_id()) % ((__expected + 1) >> 1); 46 for(int __round = 0;; ++__round) { 47 if(__current_expected <= 1) 48 return true; 49 size_t const __end_node = ((__current_expected + 1) >> 1), 50 __last_node = __end_node - 1; 51 for(;;++__current) { 52 if(__current == __end_node) 53 __current = 0; 54 __barrier_phase_t expect = __old_phase; 55 if(__current == __last_node && (__current_expected & 1)) 56 { 57 if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel)) 58 break; // I'm 1 in 1, go to next __round 59 } 60 else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel)) 61 { 62 return false; // I'm 1 in 2, done with arrival 63 } 64 else if(expect == __half_step) 65 { 66 if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel)) 67 break; // I'm 2 in 2, go to next __round 68 } 69 } 70 __current_expected = __last_node + 1; 71 __current >>= 1; 72 } 73 } 74 }; 75 76 _LIBCPP_EXPORTED_FROM_ABI 77 __barrier_algorithm_base * __construct_barrier_algorithm_base(ptrdiff_t& __expected) 78 { 79 return new __barrier_algorithm_base(__expected); 80 } 81 _LIBCPP_EXPORTED_FROM_ABI 82 bool __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier, 83 __barrier_phase_t __old_phase) 84 { 85 return __barrier->__arrive(__old_phase); 86 } 87 _LIBCPP_EXPORTED_FROM_ABI 88 void __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier) 89 { 90 delete __barrier; 91 } 92 93 #endif // !defined(_LIBCPP_HAS_NO_TREE_BARRIER) 94 95 _LIBCPP_END_NAMESPACE_STD 96 97 #endif //_LIBCPP_HAS_NO_THREADS 98