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