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