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
37 #include <bits/functional_hash.h>
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 
53 namespace 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_ACQ_REL); }
215 
216  void
217  _M_leave_wait() noexcept
218  { __atomic_fetch_sub(&_M_wait, 1, __ATOMIC_ACQ_REL); }
219 
220  bool
221  _M_waiting() const noexcept
222  {
223  __platform_wait_t __res;
224  __atomic_load(&_M_wait, &__res, __ATOMIC_ACQUIRE);
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_RELAXED);
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_ACQ_REL);
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_RELAXED);
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_RELAXED);
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  __platform_wait_t __val;
394  if (__base_type::_M_do_spin_v(__old, __vfn, __val))
395  return;
396 
397  do
398  {
399  __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
400  }
401  while (__detail::__atomic_compare(__old, __vfn()));
402  }
403 
404  template<typename _Pred>
405  void
406  _M_do_wait(_Pred __pred) noexcept
407  {
408  do
409  {
410  __platform_wait_t __val;
411  if (__base_type::_M_do_spin(__pred, __val))
412  return;
413  __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
414  }
415  while (!__pred());
416  }
417  };
418 
419  using __enters_wait = __waiter<std::true_type>;
420  using __bare_wait = __waiter<std::false_type>;
421  } // namespace __detail
422 
423  template<typename _Tp, typename _ValFn>
424  void
425  __atomic_wait_address_v(const _Tp* __addr, _Tp __old,
426  _ValFn __vfn) noexcept
427  {
428  __detail::__enters_wait __w(__addr);
429  __w._M_do_wait_v(__old, __vfn);
430  }
431 
432  template<typename _Tp, typename _Pred>
433  void
434  __atomic_wait_address(const _Tp* __addr, _Pred __pred) noexcept
435  {
436  __detail::__enters_wait __w(__addr);
437  __w._M_do_wait(__pred);
438  }
439 
440  // This call is to be used by atomic types which track contention externally
441  template<typename _Pred>
442  void
443  __atomic_wait_address_bare(const __detail::__platform_wait_t* __addr,
444  _Pred __pred) noexcept
445  {
446 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
447  do
448  {
449  __detail::__platform_wait_t __val;
450  if (__detail::__bare_wait::_S_do_spin(__addr, __pred, __val))
451  return;
452  __detail::__platform_wait(__addr, __val);
453  }
454  while (!__pred());
455 #else // !_GLIBCXX_HAVE_PLATFORM_WAIT
456  __detail::__bare_wait __w(__addr);
457  __w._M_do_wait(__pred);
458 #endif
459  }
460 
461  template<typename _Tp>
462  void
463  __atomic_notify_address(const _Tp* __addr, bool __all) noexcept
464  {
465  __detail::__bare_wait __w(__addr);
466  __w._M_notify(__all);
467  }
468 
469  // This call is to be used by atomic types which track contention externally
470  inline void
471  __atomic_notify_address_bare(const __detail::__platform_wait_t* __addr,
472  bool __all) noexcept
473  {
474 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
475  __detail::__platform_notify(__addr, __all);
476 #else
477  __detail::__bare_wait __w(__addr);
478  __w._M_notify(__all, true);
479 #endif
480  }
481 _GLIBCXX_END_NAMESPACE_VERSION
482 } // namespace std
483 #endif // GTHREADS || LINUX_FUTEX
484 #endif // _GLIBCXX_ATOMIC_WAIT_H
Definition: simd.h:210
ISO C++ entities toplevel namespace is std.