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