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