libstdc++
atomic_wait.h
Go to the documentation of this file.
1// -*- C++ -*- header.
2
3// Copyright (C) 2020-2025 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/atomic_wait.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{atomic}
28 */
29
30#ifndef _GLIBCXX_ATOMIC_WAIT_H
31#define _GLIBCXX_ATOMIC_WAIT_H 1
32
33#ifdef _GLIBCXX_SYSHDR
34#pragma GCC system_header
35#endif
36
37#include <bits/version.h>
38
39#if __glibcxx_atomic_wait
40#include <cstdint>
42#include <bits/gthr.h>
43#include <ext/numeric_traits.h>
44
45#ifdef _GLIBCXX_HAVE_LINUX_FUTEX
46# include <cerrno>
47# include <climits>
48# include <unistd.h>
49# include <syscall.h>
50# include <bits/functexcept.h>
51#endif
52
53# include <bits/std_mutex.h> // std::mutex, std::__condvar
54
55namespace std _GLIBCXX_VISIBILITY(default)
56{
57_GLIBCXX_BEGIN_NAMESPACE_VERSION
58 namespace __detail
59 {
60#ifdef _GLIBCXX_HAVE_LINUX_FUTEX
61#define _GLIBCXX_HAVE_PLATFORM_WAIT 1
62 using __platform_wait_t = int;
63 inline constexpr size_t __platform_wait_alignment = 4;
64#else
65// define _GLIBCX_HAVE_PLATFORM_WAIT and implement __platform_wait()
66// and __platform_notify() if there is a more efficient primitive supported
67// by the platform (e.g. __ulock_wait()/__ulock_wake()) which is better than
68// a mutex/condvar based wait.
69# if ATOMIC_LONG_LOCK_FREE == 2
70 using __platform_wait_t = unsigned long;
71# else
72 using __platform_wait_t = unsigned int;
73# endif
74 inline constexpr size_t __platform_wait_alignment
75 = __alignof__(__platform_wait_t);
76#endif
77 } // namespace __detail
78
79 template<typename _Tp>
80 inline constexpr bool __platform_wait_uses_type
81#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
82 = is_scalar_v<_Tp>
83 && ((sizeof(_Tp) == sizeof(__detail::__platform_wait_t))
84 && (alignof(_Tp*) >= __detail::__platform_wait_alignment));
85#else
86 = false;
87#endif
88
89 namespace __detail
90 {
91#ifdef _GLIBCXX_HAVE_LINUX_FUTEX
92 enum class __futex_wait_flags : int
93 {
94#ifdef _GLIBCXX_HAVE_LINUX_FUTEX_PRIVATE
95 __private_flag = 128,
96#else
97 __private_flag = 0,
98#endif
99 __wait = 0,
100 __wake = 1,
101 __wait_bitset = 9,
102 __wake_bitset = 10,
103 __wait_private = __wait | __private_flag,
104 __wake_private = __wake | __private_flag,
105 __wait_bitset_private = __wait_bitset | __private_flag,
106 __wake_bitset_private = __wake_bitset | __private_flag,
107 __bitset_match_any = -1
108 };
109
110 template<typename _Tp>
111 void
112 __platform_wait(const _Tp* __addr, __platform_wait_t __val) noexcept
113 {
114 auto __e = syscall (SYS_futex, static_cast<const void*>(__addr),
115 static_cast<int>(__futex_wait_flags::__wait_private),
116 __val, nullptr);
117 if (!__e || errno == EAGAIN)
118 return;
119 if (errno != EINTR)
120 __throw_system_error(errno);
121 }
122
123 template<typename _Tp>
124 void
125 __platform_notify(const _Tp* __addr, bool __all) noexcept
126 {
127 syscall (SYS_futex, static_cast<const void*>(__addr),
128 static_cast<int>(__futex_wait_flags::__wake_private),
129 __all ? INT_MAX : 1);
130 }
131#endif
132
133 inline void
134 __thread_yield() noexcept
135 {
136#if defined _GLIBCXX_HAS_GTHREADS && defined _GLIBCXX_USE_SCHED_YIELD
137 __gthread_yield();
138#endif
139 }
140
141 inline void
142 __thread_relax() noexcept
143 {
144#if defined __i386__ || defined __x86_64__
145 __builtin_ia32_pause();
146#else
147 __thread_yield();
148#endif
149 }
150
151 inline constexpr auto __atomic_spin_count_relax = 12;
152 inline constexpr auto __atomic_spin_count = 16;
153
154 struct __default_spin_policy
155 {
156 bool
157 operator()() const noexcept
158 { return false; }
159 };
160
161 template<typename _Pred,
162 typename _Spin = __default_spin_policy>
163 bool
164 __atomic_spin(_Pred& __pred, _Spin __spin = _Spin{ }) noexcept
165 {
166 for (auto __i = 0; __i < __atomic_spin_count; ++__i)
167 {
168 if (__pred())
169 return true;
170
171 if (__i < __atomic_spin_count_relax)
172 __detail::__thread_relax();
173 else
174 __detail::__thread_yield();
175 }
176
177 while (__spin())
178 {
179 if (__pred())
180 return true;
181 }
182
183 return false;
184 }
185
186 // return true if equal
187 template<typename _Tp>
188 bool __atomic_compare(const _Tp& __a, const _Tp& __b)
189 {
190 // TODO make this do the correct padding bit ignoring comparison
191 return __builtin_memcmp(&__a, &__b, sizeof(_Tp)) == 0;
192 }
193
194 struct __waiter_pool_base
195 {
196 // Don't use std::hardware_destructive_interference_size here because we
197 // don't want the layout of library types to depend on compiler options.
198 static constexpr auto _S_align = 64;
199
200 alignas(_S_align) __platform_wait_t _M_wait = 0;
201
202#ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
203 mutex _M_mtx;
204#endif
205
206 alignas(_S_align) __platform_wait_t _M_ver = 0;
207
208#ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
209 __condvar _M_cv;
210#endif
211 __waiter_pool_base() = default;
212
213 void
214 _M_enter_wait() noexcept
215 { __atomic_fetch_add(&_M_wait, 1, __ATOMIC_SEQ_CST); }
216
217 void
218 _M_leave_wait() noexcept
219 { __atomic_fetch_sub(&_M_wait, 1, __ATOMIC_RELEASE); }
220
221 bool
222 _M_waiting() const noexcept
223 {
224 __platform_wait_t __res;
225 __atomic_load(&_M_wait, &__res, __ATOMIC_SEQ_CST);
226 return __res != 0;
227 }
228
229 void
230 _M_notify(__platform_wait_t* __addr, [[maybe_unused]] bool __all,
231 bool __bare) noexcept
232 {
233#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
234 if (__addr == &_M_ver)
235 {
236 __atomic_fetch_add(__addr, 1, __ATOMIC_SEQ_CST);
237 __all = true;
238 }
239
240 if (__bare || _M_waiting())
241 __platform_notify(__addr, __all);
242#else
243 {
244 lock_guard<mutex> __l(_M_mtx);
245 __atomic_fetch_add(__addr, 1, __ATOMIC_RELAXED);
246 }
247 if (__bare || _M_waiting())
248 _M_cv.notify_all();
249#endif
250 }
251
252 static __waiter_pool_base&
253 _S_for(const void* __addr) noexcept
254 {
255 constexpr __UINTPTR_TYPE__ __ct = 16;
256 static __waiter_pool_base __w[__ct];
257 auto __key = ((__UINTPTR_TYPE__)__addr >> 2) % __ct;
258 return __w[__key];
259 }
260 };
261
262 struct __waiter_pool : __waiter_pool_base
263 {
264 void
265 _M_do_wait(const __platform_wait_t* __addr, __platform_wait_t __old) noexcept
266 {
267#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
268 __platform_wait(__addr, __old);
269#else
270 __platform_wait_t __val;
271 __atomic_load(__addr, &__val, __ATOMIC_SEQ_CST);
272 if (__val == __old)
273 {
274 lock_guard<mutex> __l(_M_mtx);
275 __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
276 if (__val == __old)
277 _M_cv.wait(_M_mtx);
278 }
279#endif // __GLIBCXX_HAVE_PLATFORM_WAIT
280 }
281 };
282
283 template<typename _Tp>
284 struct __waiter_base
285 {
286 using __waiter_type = _Tp;
287
288 __waiter_type& _M_w;
289 __platform_wait_t* _M_addr;
290
291 template<typename _Up>
292 static __platform_wait_t*
293 _S_wait_addr(const _Up* __a, __platform_wait_t* __b)
294 {
295 if constexpr (__platform_wait_uses_type<_Up>)
296 return reinterpret_cast<__platform_wait_t*>(const_cast<_Up*>(__a));
297 else
298 return __b;
299 }
300
301 static __waiter_type&
302 _S_for(const void* __addr) noexcept
303 {
304 static_assert(sizeof(__waiter_type) == sizeof(__waiter_pool_base));
305 auto& res = __waiter_pool_base::_S_for(__addr);
306 return reinterpret_cast<__waiter_type&>(res);
307 }
308
309 template<typename _Up>
310 explicit __waiter_base(const _Up* __addr) noexcept
311 : _M_w(_S_for(__addr))
312 , _M_addr(_S_wait_addr(__addr, &_M_w._M_ver))
313 { }
314
315 void
316 _M_notify(bool __all, bool __bare = false) noexcept
317 { _M_w._M_notify(_M_addr, __all, __bare); }
318
319 template<typename _Up, typename _ValFn,
320 typename _Spin = __default_spin_policy>
321 static bool
322 _S_do_spin_v(__platform_wait_t* __addr,
323 const _Up& __old, _ValFn __vfn,
324 __platform_wait_t& __val,
325 _Spin __spin = _Spin{ })
326 {
327 auto const __pred = [=]
328 { return !__detail::__atomic_compare(__old, __vfn()); };
329
330 if constexpr (__platform_wait_uses_type<_Up>)
331 {
332 __builtin_memcpy(&__val, &__old, sizeof(__val));
333 }
334 else
335 {
336 __atomic_load(__addr, &__val, __ATOMIC_ACQUIRE);
337 }
338 return __atomic_spin(__pred, __spin);
339 }
340
341 template<typename _Up, typename _ValFn,
342 typename _Spin = __default_spin_policy>
343 bool
344 _M_do_spin_v(const _Up& __old, _ValFn __vfn,
345 __platform_wait_t& __val,
346 _Spin __spin = _Spin{ })
347 { return _S_do_spin_v(_M_addr, __old, __vfn, __val, __spin); }
348
349 template<typename _Pred,
350 typename _Spin = __default_spin_policy>
351 static bool
352 _S_do_spin(const __platform_wait_t* __addr,
353 _Pred __pred,
354 __platform_wait_t& __val,
355 _Spin __spin = _Spin{ })
356 {
357 __atomic_load(__addr, &__val, __ATOMIC_ACQUIRE);
358 return __atomic_spin(__pred, __spin);
359 }
360
361 template<typename _Pred,
362 typename _Spin = __default_spin_policy>
363 bool
364 _M_do_spin(_Pred __pred, __platform_wait_t& __val,
365 _Spin __spin = _Spin{ })
366 { return _S_do_spin(_M_addr, __pred, __val, __spin); }
367 };
368
369 template<typename _EntersWait>
370 struct __waiter : __waiter_base<__waiter_pool>
371 {
372 using __base_type = __waiter_base<__waiter_pool>;
373
374 template<typename _Tp>
375 explicit __waiter(const _Tp* __addr) noexcept
376 : __base_type(__addr)
377 {
378 if constexpr (_EntersWait::value)
379 _M_w._M_enter_wait();
380 }
381
382 ~__waiter()
383 {
384 if constexpr (_EntersWait::value)
385 _M_w._M_leave_wait();
386 }
387
388 template<typename _Tp, typename _ValFn>
389 void
390 _M_do_wait_v(_Tp __old, _ValFn __vfn)
391 {
392 do
393 {
394 __platform_wait_t __val;
395 if (__base_type::_M_do_spin_v(__old, __vfn, __val))
396 return;
397 __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
398 }
399 while (__detail::__atomic_compare(__old, __vfn()));
400 }
401
402 template<typename _Pred>
403 void
404 _M_do_wait(_Pred __pred) noexcept
405 {
406 do
407 {
408 __platform_wait_t __val;
409 if (__base_type::_M_do_spin(__pred, __val))
410 return;
411 __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
412 }
413 while (!__pred());
414 }
415 };
416
417 using __enters_wait = __waiter<std::true_type>;
418 using __bare_wait = __waiter<std::false_type>;
419 } // namespace __detail
420
421 template<typename _Tp, typename _ValFn>
422 void
423 __atomic_wait_address_v(const _Tp* __addr, _Tp __old,
424 _ValFn __vfn) noexcept
425 {
426 __detail::__enters_wait __w(__addr);
427 __w._M_do_wait_v(__old, __vfn);
428 }
429
430 template<typename _Tp, typename _Pred>
431 void
432 __atomic_wait_address(const _Tp* __addr, _Pred __pred) noexcept
433 {
434 __detail::__enters_wait __w(__addr);
435 __w._M_do_wait(__pred);
436 }
437
438 // This call is to be used by atomic types which track contention externally
439 template<typename _Pred>
440 void
441 __atomic_wait_address_bare(const __detail::__platform_wait_t* __addr,
442 _Pred __pred) noexcept
443 {
444#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
445 do
446 {
447 __detail::__platform_wait_t __val;
448 if (__detail::__bare_wait::_S_do_spin(__addr, __pred, __val))
449 return;
450 __detail::__platform_wait(__addr, __val);
451 }
452 while (!__pred());
453#else // !_GLIBCXX_HAVE_PLATFORM_WAIT
454 __detail::__bare_wait __w(__addr);
455 __w._M_do_wait(__pred);
456#endif
457 }
458
459 template<typename _Tp>
460 void
461 __atomic_notify_address(const _Tp* __addr, bool __all) noexcept
462 {
463 __detail::__bare_wait __w(__addr);
464 __w._M_notify(__all);
465 }
466
467 // This call is to be used by atomic types which track contention externally
468 inline void
469 __atomic_notify_address_bare(const __detail::__platform_wait_t* __addr,
470 bool __all) noexcept
471 {
472#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
473 __detail::__platform_notify(__addr, __all);
474#else
475 __detail::__bare_wait __w(__addr);
476 __w._M_notify(__all, true);
477#endif
478 }
479_GLIBCXX_END_NAMESPACE_VERSION
480} // namespace std
481#endif // __glibcxx_atomic_wait
482#endif // _GLIBCXX_ATOMIC_WAIT_H
ISO C++ entities toplevel namespace is std.