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>
41 #include <bits/functional_hash.h>
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 
55 namespace 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.