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 <stdint.h>
38 #include <bits/functional_hash.h>
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 
54 namespace 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
Definition: simd.h:281
ISO C++ entities toplevel namespace is std.