libstdc++
atomic_timed_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_timed_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_TIMED_WAIT_H
31 #define _GLIBCXX_ATOMIC_TIMED_WAIT_H 1
32 
33 #pragma GCC system_header
34 
35 #include <bits/atomic_wait.h>
36 
37 #if __cpp_lib_atomic_wait
38 #include <bits/functional_hash.h>
39 #include <bits/this_thread_sleep.h>
40 
41 #include <chrono>
42 
43 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
44 #include <exception> // std::terminate
45 #include <sys/time.h>
46 #endif
47 
48 namespace std _GLIBCXX_VISIBILITY(default)
49 {
50 _GLIBCXX_BEGIN_NAMESPACE_VERSION
51 
52  namespace __detail
53  {
54  using __wait_clock_t = chrono::steady_clock;
55 
56  template<typename _Clock, typename _Dur>
57  __wait_clock_t::time_point
58  __to_wait_clock(const chrono::time_point<_Clock, _Dur>& __atime) noexcept
59  {
60  const typename _Clock::time_point __c_entry = _Clock::now();
61  const __wait_clock_t::time_point __w_entry = __wait_clock_t::now();
62  const auto __delta = __atime - __c_entry;
63  using __w_dur = typename __wait_clock_t::duration;
64  return __w_entry + chrono::ceil<__w_dur>(__delta);
65  }
66 
67  template<typename _Dur>
68  __wait_clock_t::time_point
69  __to_wait_clock(const chrono::time_point<__wait_clock_t,
70  _Dur>& __atime) noexcept
71  {
72  using __w_dur = typename __wait_clock_t::duration;
73  return chrono::ceil<__w_dur>(__atime);
74  }
75 
76 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
77 #define _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
78  // returns true if wait ended before timeout
79  template<typename _Dur>
80  bool
81  __platform_wait_until_impl(const __platform_wait_t* __addr,
82  __platform_wait_t __old,
83  const chrono::time_point<__wait_clock_t, _Dur>&
84  __atime) noexcept
85  {
86  auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
87  auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
88 
89  struct timespec __rt =
90  {
91  static_cast<std::time_t>(__s.time_since_epoch().count()),
92  static_cast<long>(__ns.count())
93  };
94 
95  auto __e = syscall (SYS_futex, __addr,
96  static_cast<int>(__futex_wait_flags::
97  __wait_bitset_private),
98  __old, &__rt, nullptr,
99  static_cast<int>(__futex_wait_flags::
100  __bitset_match_any));
101 
102  if (__e)
103  {
104  if (errno == ETIMEDOUT)
105  return false;
106  if (errno != EINTR && errno != EAGAIN)
107  __throw_system_error(errno);
108  }
109  return true;
110  }
111 
112  // returns true if wait ended before timeout
113  template<typename _Clock, typename _Dur>
114  bool
115  __platform_wait_until(const __platform_wait_t* __addr, __platform_wait_t __old,
116  const chrono::time_point<_Clock, _Dur>& __atime)
117  {
118  if constexpr (is_same_v<__wait_clock_t, _Clock>)
119  {
120  return __platform_wait_until_impl(__addr, __old, __atime);
121  }
122  else
123  {
124  if (!__platform_wait_until_impl(__addr, __old,
125  __to_wait_clock(__atime)))
126  {
127  // We got a timeout when measured against __clock_t but
128  // we need to check against the caller-supplied clock
129  // to tell whether we should return a timeout.
130  if (_Clock::now() < __atime)
131  return true;
132  }
133  return false;
134  }
135  }
136 #else
137 // define _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT and implement __platform_wait_until()
138 // if there is a more efficient primitive supported by the platform
139 // (e.g. __ulock_wait())which is better than pthread_cond_clockwait
140 #endif // ! PLATFORM_TIMED_WAIT
141 
142  // Returns true if wait ended before timeout.
143  // _Clock must be either steady_clock or system_clock.
144  template<typename _Clock, typename _Dur>
145  bool
146  __cond_wait_until_impl(__condvar& __cv, mutex& __mx,
147  const chrono::time_point<_Clock, _Dur>& __atime)
148  {
149  static_assert(std::__is_one_of<_Clock, chrono::steady_clock,
150  chrono::system_clock>::value);
151 
152  auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
153  auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
154 
155  __gthread_time_t __ts =
156  {
157  static_cast<std::time_t>(__s.time_since_epoch().count()),
158  static_cast<long>(__ns.count())
159  };
160 
161 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
162  if constexpr (is_same_v<chrono::steady_clock, _Clock>)
163  __cv.wait_until(__mx, CLOCK_MONOTONIC, __ts);
164  else
165 #endif
166  __cv.wait_until(__mx, __ts);
167  return _Clock::now() < __atime;
168  }
169 
170  // returns true if wait ended before timeout
171  template<typename _Clock, typename _Dur>
172  bool
173  __cond_wait_until(__condvar& __cv, mutex& __mx,
174  const chrono::time_point<_Clock, _Dur>& __atime)
175  {
176 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
177  if constexpr (is_same_v<_Clock, chrono::steady_clock>)
178  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
179  else
180 #endif
181  if constexpr (is_same_v<_Clock, chrono::system_clock>)
182  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
183  else
184  {
185  if (__cond_wait_until_impl(__cv, __mx,
186  __to_wait_clock(__atime)))
187  {
188  // We got a timeout when measured against __clock_t but
189  // we need to check against the caller-supplied clock
190  // to tell whether we should return a timeout.
191  if (_Clock::now() < __atime)
192  return true;
193  }
194  return false;
195  }
196  }
197 
198  struct __timed_waiter_pool : __waiter_pool_base
199  {
200  // returns true if wait ended before timeout
201  template<typename _Clock, typename _Dur>
202  bool
203  _M_do_wait_until(__platform_wait_t* __addr, __platform_wait_t __old,
204  const chrono::time_point<_Clock, _Dur>& __atime)
205  {
206 #ifdef _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
207  return __platform_wait_until(__addr, __old, __atime);
208 #else
209  __platform_wait_t __val;
210  __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
211  if (__val == __old)
212  {
213  lock_guard<mutex> __l(_M_mtx);
214  return __cond_wait_until(_M_cv, _M_mtx, __atime);
215  }
216  else
217  return true;
218 #endif // _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
219  }
220  };
221 
222  struct __timed_backoff_spin_policy
223  {
224  __wait_clock_t::time_point _M_deadline;
225  __wait_clock_t::time_point _M_t0;
226 
227  template<typename _Clock, typename _Dur>
228  __timed_backoff_spin_policy(chrono::time_point<_Clock, _Dur>
229  __deadline = _Clock::time_point::max(),
230  chrono::time_point<_Clock, _Dur>
231  __t0 = _Clock::now()) noexcept
232  : _M_deadline(__to_wait_clock(__deadline))
233  , _M_t0(__to_wait_clock(__t0))
234  { }
235 
236  bool
237  operator()() const noexcept
238  {
239  using namespace literals::chrono_literals;
240  auto __now = __wait_clock_t::now();
241  if (_M_deadline <= __now)
242  return false;
243 
244  auto __elapsed = __now - _M_t0;
245  if (__elapsed > 128ms)
246  {
248  }
249  else if (__elapsed > 64us)
250  {
251  this_thread::sleep_for(__elapsed / 2);
252  }
253  else if (__elapsed > 4us)
254  {
255  __thread_yield();
256  }
257  else
258  return false;
259  return true;
260  }
261  };
262 
263  template<typename _EntersWait>
264  struct __timed_waiter : __waiter_base<__timed_waiter_pool>
265  {
266  using __base_type = __waiter_base<__timed_waiter_pool>;
267 
268  template<typename _Tp>
269  __timed_waiter(const _Tp* __addr) noexcept
270  : __base_type(__addr)
271  {
272  if constexpr (_EntersWait::value)
273  _M_w._M_enter_wait();
274  }
275 
276  ~__timed_waiter()
277  {
278  if constexpr (_EntersWait::value)
279  _M_w._M_leave_wait();
280  }
281 
282  // returns true if wait ended before timeout
283  template<typename _Tp, typename _ValFn,
284  typename _Clock, typename _Dur>
285  bool
286  _M_do_wait_until_v(_Tp __old, _ValFn __vfn,
287  const chrono::time_point<_Clock, _Dur>&
288  __atime) noexcept
289  {
290  __platform_wait_t __val;
291  if (_M_do_spin(__old, std::move(__vfn), __val,
292  __timed_backoff_spin_policy(__atime)))
293  return true;
294  return __base_type::_M_w._M_do_wait_until(__base_type::_M_addr, __val, __atime);
295  }
296 
297  // returns true if wait ended before timeout
298  template<typename _Pred,
299  typename _Clock, typename _Dur>
300  bool
301  _M_do_wait_until(_Pred __pred, __platform_wait_t __val,
302  const chrono::time_point<_Clock, _Dur>&
303  __atime) noexcept
304  {
305  for (auto __now = _Clock::now(); __now < __atime;
306  __now = _Clock::now())
307  {
308  if (__base_type::_M_w._M_do_wait_until(
309  __base_type::_M_addr, __val, __atime)
310  && __pred())
311  return true;
312 
313  if (__base_type::_M_do_spin(__pred, __val,
314  __timed_backoff_spin_policy(__atime, __now)))
315  return true;
316  }
317  return false;
318  }
319 
320  // returns true if wait ended before timeout
321  template<typename _Pred,
322  typename _Clock, typename _Dur>
323  bool
324  _M_do_wait_until(_Pred __pred,
325  const chrono::time_point<_Clock, _Dur>&
326  __atime) noexcept
327  {
328  __platform_wait_t __val;
329  if (__base_type::_M_do_spin(__pred, __val,
330  __timed_backoff_spin_policy(__atime)))
331  return true;
332  return _M_do_wait_until(__pred, __val, __atime);
333  }
334 
335  template<typename _Tp, typename _ValFn,
336  typename _Rep, typename _Period>
337  bool
338  _M_do_wait_for_v(_Tp __old, _ValFn __vfn,
339  const chrono::duration<_Rep, _Period>&
340  __rtime) noexcept
341  {
342  __platform_wait_t __val;
343  if (_M_do_spin_v(__old, std::move(__vfn), __val))
344  return true;
345 
346  if (!__rtime.count())
347  return false; // no rtime supplied, and spin did not acquire
348 
349  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
350 
351  return __base_type::_M_w._M_do_wait_until(
352  __base_type::_M_addr,
353  __val,
354  chrono::steady_clock::now() + __reltime);
355  }
356 
357  template<typename _Pred,
358  typename _Rep, typename _Period>
359  bool
360  _M_do_wait_for(_Pred __pred,
361  const chrono::duration<_Rep, _Period>& __rtime) noexcept
362  {
363  __platform_wait_t __val;
364  if (__base_type::_M_do_spin(__pred, __val))
365  return true;
366 
367  if (!__rtime.count())
368  return false; // no rtime supplied, and spin did not acquire
369 
370  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
371 
372  return _M_do_wait_until(__pred, __val,
373  chrono::steady_clock::now() + __reltime);
374  }
375  };
376 
377  using __enters_timed_wait = __timed_waiter<std::true_type>;
378  using __bare_timed_wait = __timed_waiter<std::false_type>;
379  } // namespace __detail
380 
381  // returns true if wait ended before timeout
382  template<typename _Tp, typename _ValFn,
383  typename _Clock, typename _Dur>
384  bool
385  __atomic_wait_address_until_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
386  const chrono::time_point<_Clock, _Dur>&
387  __atime) noexcept
388  {
389  __detail::__enters_timed_wait __w{__addr};
390  return __w._M_do_wait_until_v(__old, __vfn, __atime);
391  }
392 
393  template<typename _Tp, typename _Pred,
394  typename _Clock, typename _Dur>
395  bool
396  __atomic_wait_address_until(const _Tp* __addr, _Pred __pred,
397  const chrono::time_point<_Clock, _Dur>&
398  __atime) noexcept
399  {
400  __detail::__enters_timed_wait __w{__addr};
401  return __w._M_do_wait_until(__pred, __atime);
402  }
403 
404  template<typename _Pred,
405  typename _Clock, typename _Dur>
406  bool
407  __atomic_wait_address_until_bare(const __detail::__platform_wait_t* __addr,
408  _Pred __pred,
409  const chrono::time_point<_Clock, _Dur>&
410  __atime) noexcept
411  {
412  __detail::__bare_timed_wait __w{__addr};
413  return __w._M_do_wait_until(__pred, __atime);
414  }
415 
416  template<typename _Tp, typename _ValFn,
417  typename _Rep, typename _Period>
418  bool
419  __atomic_wait_address_for_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
420  const chrono::duration<_Rep, _Period>& __rtime) noexcept
421  {
422  __detail::__enters_timed_wait __w{__addr};
423  return __w._M_do_wait_for_v(__old, __vfn, __rtime);
424  }
425 
426  template<typename _Tp, typename _Pred,
427  typename _Rep, typename _Period>
428  bool
429  __atomic_wait_address_for(const _Tp* __addr, _Pred __pred,
430  const chrono::duration<_Rep, _Period>& __rtime) noexcept
431  {
432 
433  __detail::__enters_timed_wait __w{__addr};
434  return __w._M_do_wait_for(__pred, __rtime);
435  }
436 
437  template<typename _Pred,
438  typename _Rep, typename _Period>
439  bool
440  __atomic_wait_address_for_bare(const __detail::__platform_wait_t* __addr,
441  _Pred __pred,
442  const chrono::duration<_Rep, _Period>& __rtime) noexcept
443  {
444  __detail::__bare_timed_wait __w{__addr};
445  return __w._M_do_wait_for(__pred, __rtime);
446  }
447 _GLIBCXX_END_NAMESPACE_VERSION
448 } // namespace std
449 #endif // __cpp_lib_atomic_wait
450 #endif // _GLIBCXX_ATOMIC_TIMED_WAIT_H
duration< int64_t > seconds
seconds
Definition: chrono:847
constexpr enable_if< __is_duration< _ToDur >::value, time_point< _Clock, _ToDur > >::type time_point_cast(const time_point< _Clock, _Dur > &__t)
time_point_cast
Definition: chrono:957
Definition: simd.h:210
duration< int64_t, nano > nanoseconds
nanoseconds
Definition: chrono:838
constexpr __enable_if_is_duration< _ToDur > duration_cast(const duration< _Rep, _Period > &__d)
duration_cast
Definition: chrono:267
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:254
ISO C++ entities toplevel namespace is std.
void sleep_for(const chrono::duration< _Rep, _Period > &__rtime)
this_thread::sleep_for