3 // Copyright (C) 2020-2022 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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}
30 #ifndef _GLIBCXX_ATOMIC_WAIT_H
31 #define _GLIBCXX_ATOMIC_WAIT_H 1
33 #pragma GCC system_header
35 #include <bits/c++config.h>
36 #if defined _GLIBCXX_HAS_GTHREADS || defined _GLIBCXX_HAVE_LINUX_FUTEX
37 #include <bits/functional_hash.h>
38 #include <bits/gthr.h>
39 #include <ext/numeric_traits.h>
41 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
46 # include <bits/functexcept.h>
49 # include <bits/std_mutex.h> // std::mutex, std::__condvar
51 #define __cpp_lib_atomic_wait 201907L
53 namespace std
_GLIBCXX_VISIBILITY(default)
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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;
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
);
71 } // namespace __detail
73 template<typename _Tp
>
74 inline constexpr bool __platform_wait_uses_type
75 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
77 && ((sizeof(_Tp
) == sizeof(__detail::__platform_wait_t
))
78 && (alignof(_Tp
*) >= __detail::__platform_wait_alignment
));
85 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
86 enum class __futex_wait_flags
: int
88 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX_PRIVATE
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
104 template<typename _Tp
>
106 __platform_wait(const _Tp
* __addr
, __platform_wait_t __val
) noexcept
108 auto __e
= syscall (SYS_futex
, static_cast<const void*>(__addr
),
109 static_cast<int>(__futex_wait_flags::__wait_private
),
111 if (!__e
|| errno
== EAGAIN
)
114 __throw_system_error(errno
);
117 template<typename _Tp
>
119 __platform_notify(const _Tp
* __addr
, bool __all
) noexcept
121 syscall (SYS_futex
, static_cast<const void*>(__addr
),
122 static_cast<int>(__futex_wait_flags::__wake_private
),
123 __all
? INT_MAX
: 1);
128 __thread_yield() noexcept
130 #if defined _GLIBCXX_HAS_GTHREADS && defined _GLIBCXX_USE_SCHED_YIELD
136 __thread_relax() noexcept
138 #if defined __i386__ || defined __x86_64__
139 __builtin_ia32_pause();
145 constexpr auto __atomic_spin_count_relax
= 12;
146 constexpr auto __atomic_spin_count
= 16;
148 struct __default_spin_policy
151 operator()() const noexcept
155 template<typename _Pred
,
156 typename _Spin
= __default_spin_policy
>
158 __atomic_spin(_Pred
& __pred
, _Spin __spin
= _Spin
{ }) noexcept
160 for (auto __i
= 0; __i
< __atomic_spin_count
; ++__i
)
165 if (__i
< __atomic_spin_count_relax
)
166 __detail::__thread_relax();
168 __detail::__thread_yield();
180 // return true if equal
181 template<typename _Tp
>
182 bool __atomic_compare(const _Tp
& __a
, const _Tp
& __b
)
184 // TODO make this do the correct padding bit ignoring comparison
185 return __builtin_memcmp(&__a
, &__b
, sizeof(_Tp
)) == 0;
188 struct __waiter_pool_base
190 // Don't use std::hardware_destructive_interference_size here because we
191 // don't want the layout of library types to depend on compiler options.
192 static constexpr auto _S_align
= 64;
194 alignas(_S_align
) __platform_wait_t _M_wait
= 0;
196 #ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
200 alignas(_S_align
) __platform_wait_t _M_ver
= 0;
202 #ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
205 __waiter_pool_base() = default;
208 _M_enter_wait() noexcept
209 { __atomic_fetch_add(&_M_wait
, 1, __ATOMIC_SEQ_CST
); }
212 _M_leave_wait() noexcept
213 { __atomic_fetch_sub(&_M_wait
, 1, __ATOMIC_RELEASE
); }
216 _M_waiting() const noexcept
218 __platform_wait_t __res
;
219 __atomic_load(&_M_wait
, &__res
, __ATOMIC_SEQ_CST
);
224 _M_notify(__platform_wait_t
* __addr
, [[maybe_unused
]] bool __all
,
225 bool __bare
) noexcept
227 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
228 if (__addr
== &_M_ver
)
230 __atomic_fetch_add(__addr
, 1, __ATOMIC_SEQ_CST
);
234 if (__bare
|| _M_waiting())
235 __platform_notify(__addr
, __all
);
238 lock_guard
<mutex
> __l(_M_mtx
);
239 __atomic_fetch_add(__addr
, 1, __ATOMIC_RELAXED
);
241 if (__bare
|| _M_waiting())
246 static __waiter_pool_base
&
247 _S_for(const void* __addr
) noexcept
249 constexpr uintptr_t __ct
= 16;
250 static __waiter_pool_base __w
[__ct
];
251 auto __key
= (uintptr_t(__addr
) >> 2) % __ct
;
256 struct __waiter_pool
: __waiter_pool_base
259 _M_do_wait(const __platform_wait_t
* __addr
, __platform_wait_t __old
) noexcept
261 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
262 __platform_wait(__addr
, __old
);
264 __platform_wait_t __val
;
265 __atomic_load(__addr
, &__val
, __ATOMIC_SEQ_CST
);
268 lock_guard
<mutex
> __l(_M_mtx
);
269 __atomic_load(__addr
, &__val
, __ATOMIC_RELAXED
);
273 #endif // __GLIBCXX_HAVE_PLATFORM_WAIT
277 template<typename _Tp
>
280 using __waiter_type
= _Tp
;
283 __platform_wait_t
* _M_addr
;
285 template<typename _Up
>
286 static __platform_wait_t
*
287 _S_wait_addr(const _Up
* __a
, __platform_wait_t
* __b
)
289 if constexpr (__platform_wait_uses_type
<_Up
>)
290 return reinterpret_cast<__platform_wait_t
*>(const_cast<_Up
*>(__a
));
295 static __waiter_type
&
296 _S_for(const void* __addr
) noexcept
298 static_assert(sizeof(__waiter_type
) == sizeof(__waiter_pool_base
));
299 auto& res
= __waiter_pool_base::_S_for(__addr
);
300 return reinterpret_cast<__waiter_type
&>(res
);
303 template<typename _Up
>
304 explicit __waiter_base(const _Up
* __addr
) noexcept
305 : _M_w(_S_for(__addr
))
306 , _M_addr(_S_wait_addr(__addr
, &_M_w
._M_ver
))
310 _M_notify(bool __all
, bool __bare
= false) noexcept
311 { _M_w
._M_notify(_M_addr
, __all
, __bare
); }
313 template<typename _Up
, typename _ValFn
,
314 typename _Spin
= __default_spin_policy
>
316 _S_do_spin_v(__platform_wait_t
* __addr
,
317 const _Up
& __old
, _ValFn __vfn
,
318 __platform_wait_t
& __val
,
319 _Spin __spin
= _Spin
{ })
321 auto const __pred
= [=]
322 { return !__detail::__atomic_compare(__old
, __vfn()); };
324 if constexpr (__platform_wait_uses_type
<_Up
>)
326 __builtin_memcpy(&__val
, &__old
, sizeof(__val
));
330 __atomic_load(__addr
, &__val
, __ATOMIC_ACQUIRE
);
332 return __atomic_spin(__pred
, __spin
);
335 template<typename _Up
, typename _ValFn
,
336 typename _Spin
= __default_spin_policy
>
338 _M_do_spin_v(const _Up
& __old
, _ValFn __vfn
,
339 __platform_wait_t
& __val
,
340 _Spin __spin
= _Spin
{ })
341 { return _S_do_spin_v(_M_addr
, __old
, __vfn
, __val
, __spin
); }
343 template<typename _Pred
,
344 typename _Spin
= __default_spin_policy
>
346 _S_do_spin(const __platform_wait_t
* __addr
,
348 __platform_wait_t
& __val
,
349 _Spin __spin
= _Spin
{ })
351 __atomic_load(__addr
, &__val
, __ATOMIC_ACQUIRE
);
352 return __atomic_spin(__pred
, __spin
);
355 template<typename _Pred
,
356 typename _Spin
= __default_spin_policy
>
358 _M_do_spin(_Pred __pred
, __platform_wait_t
& __val
,
359 _Spin __spin
= _Spin
{ })
360 { return _S_do_spin(_M_addr
, __pred
, __val
, __spin
); }
363 template<typename _EntersWait
>
364 struct __waiter
: __waiter_base
<__waiter_pool
>
366 using __base_type
= __waiter_base
<__waiter_pool
>;
368 template<typename _Tp
>
369 explicit __waiter(const _Tp
* __addr
) noexcept
370 : __base_type(__addr
)
372 if constexpr (_EntersWait::value
)
373 _M_w
._M_enter_wait();
378 if constexpr (_EntersWait::value
)
379 _M_w
._M_leave_wait();
382 template<typename _Tp
, typename _ValFn
>
384 _M_do_wait_v(_Tp __old
, _ValFn __vfn
)
388 __platform_wait_t __val
;
389 if (__base_type::_M_do_spin_v(__old
, __vfn
, __val
))
391 __base_type::_M_w
._M_do_wait(__base_type::_M_addr
, __val
);
393 while (__detail::__atomic_compare(__old
, __vfn()));
396 template<typename _Pred
>
398 _M_do_wait(_Pred __pred
) noexcept
402 __platform_wait_t __val
;
403 if (__base_type::_M_do_spin(__pred
, __val
))
405 __base_type::_M_w
._M_do_wait(__base_type::_M_addr
, __val
);
411 using __enters_wait
= __waiter
<std::true_type
>;
412 using __bare_wait
= __waiter
<std::false_type
>;
413 } // namespace __detail
415 template<typename _Tp
, typename _ValFn
>
417 __atomic_wait_address_v(const _Tp
* __addr
, _Tp __old
,
418 _ValFn __vfn
) noexcept
420 __detail::__enters_wait
__w(__addr
);
421 __w
._M_do_wait_v(__old
, __vfn
);
424 template<typename _Tp
, typename _Pred
>
426 __atomic_wait_address(const _Tp
* __addr
, _Pred __pred
) noexcept
428 __detail::__enters_wait
__w(__addr
);
429 __w
._M_do_wait(__pred
);
432 // This call is to be used by atomic types which track contention externally
433 template<typename _Pred
>
435 __atomic_wait_address_bare(const __detail::__platform_wait_t
* __addr
,
436 _Pred __pred
) noexcept
438 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
441 __detail::__platform_wait_t __val
;
442 if (__detail::__bare_wait::_S_do_spin(__addr
, __pred
, __val
))
444 __detail::__platform_wait(__addr
, __val
);
447 #else // !_GLIBCXX_HAVE_PLATFORM_WAIT
448 __detail::__bare_wait
__w(__addr
);
449 __w
._M_do_wait(__pred
);
453 template<typename _Tp
>
455 __atomic_notify_address(const _Tp
* __addr
, bool __all
) noexcept
457 __detail::__bare_wait
__w(__addr
);
458 __w
._M_notify(__all
);
461 // This call is to be used by atomic types which track contention externally
463 __atomic_notify_address_bare(const __detail::__platform_wait_t
* __addr
,
466 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
467 __detail::__platform_notify(__addr
, __all
);
469 __detail::__bare_wait
__w(__addr
);
470 __w
._M_notify(__all
, true);
473 _GLIBCXX_END_NAMESPACE_VERSION
475 #endif // GTHREADS || LINUX_FUTEX
476 #endif // _GLIBCXX_ATOMIC_WAIT_H