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 #ifdef _GLIBCXX_HAS_GTHREADS
143  // Returns true if wait ended before timeout.
144  // _Clock must be either steady_clock or system_clock.
145  template<typename _Clock, typename _Dur>
146  bool
147  __cond_wait_until_impl(__condvar& __cv, mutex& __mx,
148  const chrono::time_point<_Clock, _Dur>& __atime)
149  {
150  static_assert(std::__is_one_of<_Clock, chrono::steady_clock,
151  chrono::system_clock>::value);
152 
153  auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
154  auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
155 
156  __gthread_time_t __ts =
157  {
158  static_cast<std::time_t>(__s.time_since_epoch().count()),
159  static_cast<long>(__ns.count())
160  };
161 
162 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
163  if constexpr (is_same_v<chrono::steady_clock, _Clock>)
164  __cv.wait_until(__mx, CLOCK_MONOTONIC, __ts);
165  else
166 #endif
167  __cv.wait_until(__mx, __ts);
168  return _Clock::now() < __atime;
169  }
170 
171  // returns true if wait ended before timeout
172  template<typename _Clock, typename _Dur>
173  bool
174  __cond_wait_until(__condvar& __cv, mutex& __mx,
175  const chrono::time_point<_Clock, _Dur>& __atime)
176  {
177 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
178  if constexpr (is_same_v<_Clock, chrono::steady_clock>)
179  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
180  else
181 #endif
182  if constexpr (is_same_v<_Clock, chrono::system_clock>)
183  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
184  else
185  {
186  if (__cond_wait_until_impl(__cv, __mx,
187  __to_wait_clock(__atime)))
188  {
189  // We got a timeout when measured against __clock_t but
190  // we need to check against the caller-supplied clock
191  // to tell whether we should return a timeout.
192  if (_Clock::now() < __atime)
193  return true;
194  }
195  return false;
196  }
197  }
198 #endif // _GLIBCXX_HAS_GTHREADS
199 
200  struct __timed_waiter_pool : __waiter_pool_base
201  {
202  // returns true if wait ended before timeout
203  template<typename _Clock, typename _Dur>
204  bool
205  _M_do_wait_until(__platform_wait_t* __addr, __platform_wait_t __old,
206  const chrono::time_point<_Clock, _Dur>& __atime)
207  {
208 #ifdef _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
209  return __platform_wait_until(__addr, __old, __atime);
210 #else
211  __platform_wait_t __val;
212  __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
213  if (__val == __old)
214  {
215  lock_guard<mutex> __l(_M_mtx);
216  return __cond_wait_until(_M_cv, _M_mtx, __atime);
217  }
218  else
219  return true;
220 #endif // _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
221  }
222  };
223 
224  struct __timed_backoff_spin_policy
225  {
226  __wait_clock_t::time_point _M_deadline;
227  __wait_clock_t::time_point _M_t0;
228 
229  template<typename _Clock, typename _Dur>
230  __timed_backoff_spin_policy(chrono::time_point<_Clock, _Dur>
231  __deadline = _Clock::time_point::max(),
232  chrono::time_point<_Clock, _Dur>
233  __t0 = _Clock::now()) noexcept
234  : _M_deadline(__to_wait_clock(__deadline))
235  , _M_t0(__to_wait_clock(__t0))
236  { }
237 
238  bool
239  operator()() const noexcept
240  {
241  using namespace literals::chrono_literals;
242  auto __now = __wait_clock_t::now();
243  if (_M_deadline <= __now)
244  return false;
245 
246  // FIXME: this_thread::sleep_for not available #ifdef _GLIBCXX_NO_SLEEP
247 
248  auto __elapsed = __now - _M_t0;
249  if (__elapsed > 128ms)
250  {
252  }
253  else if (__elapsed > 64us)
254  {
255  this_thread::sleep_for(__elapsed / 2);
256  }
257  else if (__elapsed > 4us)
258  {
259  __thread_yield();
260  }
261  else
262  return false;
263  return true;
264  }
265  };
266 
267  template<typename _EntersWait>
268  struct __timed_waiter : __waiter_base<__timed_waiter_pool>
269  {
270  using __base_type = __waiter_base<__timed_waiter_pool>;
271 
272  template<typename _Tp>
273  __timed_waiter(const _Tp* __addr) noexcept
274  : __base_type(__addr)
275  {
276  if constexpr (_EntersWait::value)
277  _M_w._M_enter_wait();
278  }
279 
280  ~__timed_waiter()
281  {
282  if constexpr (_EntersWait::value)
283  _M_w._M_leave_wait();
284  }
285 
286  // returns true if wait ended before timeout
287  template<typename _Tp, typename _ValFn,
288  typename _Clock, typename _Dur>
289  bool
290  _M_do_wait_until_v(_Tp __old, _ValFn __vfn,
291  const chrono::time_point<_Clock, _Dur>&
292  __atime) noexcept
293  {
294  __platform_wait_t __val;
295  if (_M_do_spin(__old, std::move(__vfn), __val,
296  __timed_backoff_spin_policy(__atime)))
297  return true;
298  return __base_type::_M_w._M_do_wait_until(__base_type::_M_addr, __val, __atime);
299  }
300 
301  // returns true if wait ended before timeout
302  template<typename _Pred,
303  typename _Clock, typename _Dur>
304  bool
305  _M_do_wait_until(_Pred __pred, __platform_wait_t __val,
306  const chrono::time_point<_Clock, _Dur>&
307  __atime) noexcept
308  {
309  for (auto __now = _Clock::now(); __now < __atime;
310  __now = _Clock::now())
311  {
312  if (__base_type::_M_w._M_do_wait_until(
313  __base_type::_M_addr, __val, __atime)
314  && __pred())
315  return true;
316 
317  if (__base_type::_M_do_spin(__pred, __val,
318  __timed_backoff_spin_policy(__atime, __now)))
319  return true;
320  }
321  return false;
322  }
323 
324  // returns true if wait ended before timeout
325  template<typename _Pred,
326  typename _Clock, typename _Dur>
327  bool
328  _M_do_wait_until(_Pred __pred,
329  const chrono::time_point<_Clock, _Dur>&
330  __atime) noexcept
331  {
332  __platform_wait_t __val;
333  if (__base_type::_M_do_spin(__pred, __val,
334  __timed_backoff_spin_policy(__atime)))
335  return true;
336  return _M_do_wait_until(__pred, __val, __atime);
337  }
338 
339  template<typename _Tp, typename _ValFn,
340  typename _Rep, typename _Period>
341  bool
342  _M_do_wait_for_v(_Tp __old, _ValFn __vfn,
343  const chrono::duration<_Rep, _Period>&
344  __rtime) noexcept
345  {
346  __platform_wait_t __val;
347  if (_M_do_spin_v(__old, std::move(__vfn), __val))
348  return true;
349 
350  if (!__rtime.count())
351  return false; // no rtime supplied, and spin did not acquire
352 
353  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
354 
355  return __base_type::_M_w._M_do_wait_until(
356  __base_type::_M_addr,
357  __val,
358  chrono::steady_clock::now() + __reltime);
359  }
360 
361  template<typename _Pred,
362  typename _Rep, typename _Period>
363  bool
364  _M_do_wait_for(_Pred __pred,
365  const chrono::duration<_Rep, _Period>& __rtime) noexcept
366  {
367  __platform_wait_t __val;
368  if (__base_type::_M_do_spin(__pred, __val))
369  return true;
370 
371  if (!__rtime.count())
372  return false; // no rtime supplied, and spin did not acquire
373 
374  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
375 
376  return _M_do_wait_until(__pred, __val,
377  chrono::steady_clock::now() + __reltime);
378  }
379  };
380 
381  using __enters_timed_wait = __timed_waiter<std::true_type>;
382  using __bare_timed_wait = __timed_waiter<std::false_type>;
383  } // namespace __detail
384 
385  // returns true if wait ended before timeout
386  template<typename _Tp, typename _ValFn,
387  typename _Clock, typename _Dur>
388  bool
389  __atomic_wait_address_until_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
390  const chrono::time_point<_Clock, _Dur>&
391  __atime) noexcept
392  {
393  __detail::__enters_timed_wait __w{__addr};
394  return __w._M_do_wait_until_v(__old, __vfn, __atime);
395  }
396 
397  template<typename _Tp, typename _Pred,
398  typename _Clock, typename _Dur>
399  bool
400  __atomic_wait_address_until(const _Tp* __addr, _Pred __pred,
401  const chrono::time_point<_Clock, _Dur>&
402  __atime) noexcept
403  {
404  __detail::__enters_timed_wait __w{__addr};
405  return __w._M_do_wait_until(__pred, __atime);
406  }
407 
408  template<typename _Pred,
409  typename _Clock, typename _Dur>
410  bool
411  __atomic_wait_address_until_bare(const __detail::__platform_wait_t* __addr,
412  _Pred __pred,
413  const chrono::time_point<_Clock, _Dur>&
414  __atime) noexcept
415  {
416  __detail::__bare_timed_wait __w{__addr};
417  return __w._M_do_wait_until(__pred, __atime);
418  }
419 
420  template<typename _Tp, typename _ValFn,
421  typename _Rep, typename _Period>
422  bool
423  __atomic_wait_address_for_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
424  const chrono::duration<_Rep, _Period>& __rtime) noexcept
425  {
426  __detail::__enters_timed_wait __w{__addr};
427  return __w._M_do_wait_for_v(__old, __vfn, __rtime);
428  }
429 
430  template<typename _Tp, typename _Pred,
431  typename _Rep, typename _Period>
432  bool
433  __atomic_wait_address_for(const _Tp* __addr, _Pred __pred,
434  const chrono::duration<_Rep, _Period>& __rtime) noexcept
435  {
436 
437  __detail::__enters_timed_wait __w{__addr};
438  return __w._M_do_wait_for(__pred, __rtime);
439  }
440 
441  template<typename _Pred,
442  typename _Rep, typename _Period>
443  bool
444  __atomic_wait_address_for_bare(const __detail::__platform_wait_t* __addr,
445  _Pred __pred,
446  const chrono::duration<_Rep, _Period>& __rtime) noexcept
447  {
448  __detail::__bare_timed_wait __w{__addr};
449  return __w._M_do_wait_for(__pred, __rtime);
450  }
451 _GLIBCXX_END_NAMESPACE_VERSION
452 } // namespace std
453 #endif // __cpp_lib_atomic_wait
454 #endif // _GLIBCXX_ATOMIC_TIMED_WAIT_H
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