1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___STOP_TOKEN_STOP_STATE_H
11#define _LIBCPP___STOP_TOKEN_STOP_STATE_H
12
13#include <__assert>
14#include <__atomic/atomic.h>
15#include <__atomic/memory_order.h>
16#include <__config>
17#include <__stop_token/atomic_unique_lock.h>
18#include <__stop_token/intrusive_list_view.h>
19#include <__thread/id.h>
20#include <cstdint>
21
22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23# pragma GCC system_header
24#endif
25
26#if _LIBCPP_STD_VER >= 20 && _LIBCPP_HAS_THREADS
27
28_LIBCPP_BEGIN_NAMESPACE_STD
29
30struct __stop_callback_base : __intrusive_node_base<__stop_callback_base> {
31 using __callback_fn_t _LIBCPP_NODEBUG = void(__stop_callback_base*) noexcept;
32 _LIBCPP_HIDE_FROM_ABI explicit __stop_callback_base(__callback_fn_t* __callback_fn) : __callback_fn_(__callback_fn) {}
33
34 _LIBCPP_HIDE_FROM_ABI void __invoke() noexcept { __callback_fn_(this); }
35
36 __callback_fn_t* __callback_fn_;
37 atomic<bool> __completed_ = false;
38 bool* __destroyed_ = nullptr;
39};
40
41class __stop_state {
42 static constexpr uint32_t __stop_requested_bit = 1;
43 static constexpr uint32_t __callback_list_locked_bit = 1 << 1;
44 static constexpr uint32_t __stop_source_counter_shift = 2;
45
46 // The "stop_source counter" is not used for lifetime reference counting.
47 // When the number of stop_source reaches 0, the remaining stop_tokens's
48 // stop_possible will return false. We need this counter to track this.
49 //
50 // The "callback list locked" bit implements the atomic_unique_lock to
51 // guard the operations on the callback list
52 //
53 // 31 - 2 | 1 | 0 |
54 // stop_source counter | callback list locked | stop_requested |
55 atomic<uint32_t> __state_ = 0;
56
57 // Reference count for stop_token + stop_callback + stop_source
58 // When the counter reaches zero, the state is destroyed
59 // It is used by __intrusive_shared_ptr, but it is stored here for better layout
60 atomic<uint32_t> __ref_count_ = 0;
61
62 using __state_t _LIBCPP_NODEBUG = uint32_t;
63 using __callback_list_lock _LIBCPP_NODEBUG = __atomic_unique_lock<__state_t, __callback_list_locked_bit>;
64 using __callback_list _LIBCPP_NODEBUG = __intrusive_list_view<__stop_callback_base>;
65
66 __callback_list __callback_list_;
67 __thread_id __requesting_thread_;
68
69public:
70 _LIBCPP_HIDE_FROM_ABI __stop_state() noexcept = default;
71
72 _LIBCPP_HIDE_FROM_ABI void __increment_stop_source_counter() noexcept {
73 _LIBCPP_ASSERT_UNCATEGORIZED(
74 __state_.load(std::memory_order_relaxed) <= static_cast<__state_t>(~(1 << __stop_source_counter_shift)),
75 "stop_source's counter reaches the maximum. Incrementing the counter will overflow");
76 __state_.fetch_add(op: 1 << __stop_source_counter_shift, m: std::memory_order_relaxed);
77 }
78
79 // We are not destroying the object after counter decrements to zero, nor do we have
80 // operations depend on the ordering of decrementing the counter. relaxed is enough.
81 _LIBCPP_HIDE_FROM_ABI void __decrement_stop_source_counter() noexcept {
82 _LIBCPP_ASSERT_UNCATEGORIZED(
83 __state_.load(std::memory_order_relaxed) >= static_cast<__state_t>(1 << __stop_source_counter_shift),
84 "stop_source's counter is 0. Decrementing the counter will underflow");
85 __state_.fetch_sub(op: 1 << __stop_source_counter_shift, m: std::memory_order_relaxed);
86 }
87
88 _LIBCPP_HIDE_FROM_ABI bool __stop_requested() const noexcept {
89 // acquire because [thread.stoptoken.intro] A call to request_stop that returns true
90 // synchronizes with a call to stop_requested on an associated stop_token or stop_source
91 // object that returns true.
92 // request_stop's compare_exchange_weak has release which syncs with this acquire
93 return (__state_.load(m: std::memory_order_acquire) & __stop_requested_bit) != 0;
94 }
95
96 _LIBCPP_HIDE_FROM_ABI bool __stop_possible_for_stop_token() const noexcept {
97 // [stoptoken.mem] false if "a stop request was not made and there are no associated stop_source objects"
98 // Todo: Can this be std::memory_order_relaxed as the standard does not say anything except not to introduce data
99 // race?
100 __state_t __curent_state = __state_.load(m: std::memory_order_acquire);
101 return ((__curent_state & __stop_requested_bit) != 0) || ((__curent_state >> __stop_source_counter_shift) != 0);
102 }
103
104 _LIBCPP_HIDE_FROM_ABI bool __request_stop() noexcept {
105 auto __cb_list_lock = __try_lock_for_request_stop();
106 if (!__cb_list_lock.__owns_lock()) {
107 return false;
108 }
109 __requesting_thread_ = this_thread::get_id();
110
111 while (!__callback_list_.__empty()) {
112 auto __cb = __callback_list_.__pop_front();
113
114 // allow other callbacks to be removed while invoking the current callback
115 __cb_list_lock.__unlock();
116
117 bool __destroyed = false;
118 __cb->__destroyed_ = &__destroyed;
119
120 __cb->__invoke();
121
122 // __cb's invoke function could potentially delete itself. We need to check before accessing __cb's member
123 if (!__destroyed) {
124 // needs to set __destroyed_ pointer to nullptr, otherwise it points to a local variable
125 // which is to be destroyed at the end of the loop
126 __cb->__destroyed_ = nullptr;
127
128 // [stopcallback.cons] If callback is concurrently executing on another thread, then the return
129 // from the invocation of callback strongly happens before ([intro.races]) callback is destroyed.
130 // this release syncs with the acquire in the remove_callback
131 __cb->__completed_.store(d: true, m: std::memory_order_release);
132 __cb->__completed_.notify_all();
133 }
134
135 __cb_list_lock.__lock();
136 }
137
138 return true;
139 }
140
141 _LIBCPP_HIDE_FROM_ABI bool __add_callback(__stop_callback_base* __cb) noexcept {
142 // If it is already stop_requested. Do not try to request it again.
143 const auto __give_up_trying_to_lock_condition = [__cb](__state_t __state) {
144 if ((__state & __stop_requested_bit) != 0) {
145 // already stop requested, synchronously run the callback and no need to lock the list again
146 __cb->__invoke();
147 return true;
148 }
149 // no stop source. no need to lock the list to add the callback as it can never be invoked
150 return (__state >> __stop_source_counter_shift) == 0;
151 };
152
153 __callback_list_lock __cb_list_lock(__state_, __give_up_trying_to_lock_condition);
154
155 if (!__cb_list_lock.__owns_lock()) {
156 return false;
157 }
158
159 __callback_list_.__push_front(node: __cb);
160
161 return true;
162 // unlock here: [thread.stoptoken.intro] Registration of a callback synchronizes with the invocation of
163 // that callback.
164 // Note: this release sync with the acquire in the request_stop' __try_lock_for_request_stop
165 }
166
167 // called by the destructor of stop_callback
168 _LIBCPP_HIDE_FROM_ABI void __remove_callback(__stop_callback_base* __cb) noexcept {
169 __callback_list_lock __cb_list_lock(__state_);
170
171 // under below condition, the request_stop call just popped __cb from the list and could execute it now
172 bool __potentially_executing_now = __cb->__prev_ == nullptr && !__callback_list_.__is_head(node: __cb);
173
174 if (__potentially_executing_now) {
175 auto __requested_thread = __requesting_thread_;
176 __cb_list_lock.__unlock();
177
178 if (std::this_thread::get_id() != __requested_thread) {
179 // [stopcallback.cons] If callback is concurrently executing on another thread, then the return
180 // from the invocation of callback strongly happens before ([intro.races]) callback is destroyed.
181 __cb->__completed_.wait(v: false, m: std::memory_order_acquire);
182 } else {
183 // The destructor of stop_callback runs on the same thread of the thread that invokes the callback.
184 // The callback is potentially invoking its own destuctor. Set the flag to avoid accessing destroyed
185 // members on the invoking side
186 if (__cb->__destroyed_) {
187 *__cb->__destroyed_ = true;
188 }
189 }
190 } else {
191 __callback_list_.__remove(node: __cb);
192 }
193 }
194
195private:
196 _LIBCPP_HIDE_FROM_ABI __callback_list_lock __try_lock_for_request_stop() noexcept {
197 // If it is already stop_requested, do not try to request stop or lock the list again.
198 const auto __lock_fail_condition = [](__state_t __state) { return (__state & __stop_requested_bit) != 0; };
199
200 // set locked and requested bit at the same time
201 const auto __after_lock_state = [](__state_t __state) {
202 return __state | __callback_list_locked_bit | __stop_requested_bit;
203 };
204
205 // acq because [thread.stoptoken.intro] Registration of a callback synchronizes with the invocation of that
206 // callback. We are going to invoke the callback after getting the lock, acquire so that we can see the
207 // registration of a callback (and other writes that happens-before the add_callback)
208 // Note: the rel (unlock) in the add_callback syncs with this acq
209 // rel because [thread.stoptoken.intro] A call to request_stop that returns true synchronizes with a call
210 // to stop_requested on an associated stop_token or stop_source object that returns true.
211 // We need to make sure that all writes (including user code) before request_stop will be made visible
212 // to the threads that waiting for `stop_requested == true`
213 // Note: this rel syncs with the acq in `stop_requested`
214 const auto __locked_ordering = std::memory_order_acq_rel;
215
216 return __callback_list_lock(__state_, __lock_fail_condition, __after_lock_state, __locked_ordering);
217 }
218
219 template <class _Tp>
220 friend struct __intrusive_shared_ptr_traits;
221};
222
223template <class _Tp>
224struct __intrusive_shared_ptr_traits;
225
226template <>
227struct __intrusive_shared_ptr_traits<__stop_state> {
228 _LIBCPP_HIDE_FROM_ABI static atomic<uint32_t>& __get_atomic_ref_count(__stop_state& __state) {
229 return __state.__ref_count_;
230 }
231};
232
233_LIBCPP_END_NAMESPACE_STD
234
235#endif // _LIBCPP_STD_VER >= 20 && _LIBCPP_HAS_THREADS
236
237#endif // _LIBCPP___STOP_TOKEN_STOP_STATE_H
238