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