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) && (errno != EINTR)
105  && (errno != EAGAIN))
106  __throw_system_error(errno);
107  return true;
108  }
109  return false;
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 #endif // _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
217  }
218  };
219 
220  struct __timed_backoff_spin_policy
221  {
222  __wait_clock_t::time_point _M_deadline;
223  __wait_clock_t::time_point _M_t0;
224 
225  template<typename _Clock, typename _Dur>
226  __timed_backoff_spin_policy(chrono::time_point<_Clock, _Dur>
227  __deadline = _Clock::time_point::max(),
228  chrono::time_point<_Clock, _Dur>
229  __t0 = _Clock::now()) noexcept
230  : _M_deadline(__to_wait_clock(__deadline))
231  , _M_t0(__to_wait_clock(__t0))
232  { }
233 
234  bool
235  operator()() const noexcept
236  {
237  using namespace literals::chrono_literals;
238  auto __now = __wait_clock_t::now();
239  if (_M_deadline <= __now)
240  return false;
241 
242  auto __elapsed = __now - _M_t0;
243  if (__elapsed > 128ms)
244  {
246  }
247  else if (__elapsed > 64us)
248  {
249  this_thread::sleep_for(__elapsed / 2);
250  }
251  else if (__elapsed > 4us)
252  {
253  __thread_yield();
254  }
255  else
256  return false;
257  return true;
258  }
259  };
260 
261  template<typename _EntersWait>
262  struct __timed_waiter : __waiter_base<__timed_waiter_pool>
263  {
264  using __base_type = __waiter_base<__timed_waiter_pool>;
265 
266  template<typename _Tp>
267  __timed_waiter(const _Tp* __addr) noexcept
268  : __base_type(__addr)
269  {
270  if constexpr (_EntersWait::value)
271  _M_w._M_enter_wait();
272  }
273 
274  ~__timed_waiter()
275  {
276  if constexpr (_EntersWait::value)
277  _M_w._M_leave_wait();
278  }
279 
280  // returns true if wait ended before timeout
281  template<typename _Tp, typename _ValFn,
282  typename _Clock, typename _Dur>
283  bool
284  _M_do_wait_until_v(_Tp __old, _ValFn __vfn,
285  const chrono::time_point<_Clock, _Dur>&
286  __atime) noexcept
287  {
288  __platform_wait_t __val;
289  if (_M_do_spin(__old, std::move(__vfn), __val,
290  __timed_backoff_spin_policy(__atime)))
291  return true;
292  return __base_type::_M_w._M_do_wait_until(__base_type::_M_addr, __val, __atime);
293  }
294 
295  // returns true if wait ended before timeout
296  template<typename _Pred,
297  typename _Clock, typename _Dur>
298  bool
299  _M_do_wait_until(_Pred __pred, __platform_wait_t __val,
300  const chrono::time_point<_Clock, _Dur>&
301  __atime) noexcept
302  {
303  for (auto __now = _Clock::now(); __now < __atime;
304  __now = _Clock::now())
305  {
306  if (__base_type::_M_w._M_do_wait_until(
307  __base_type::_M_addr, __val, __atime)
308  && __pred())
309  return true;
310 
311  if (__base_type::_M_do_spin(__pred, __val,
312  __timed_backoff_spin_policy(__atime, __now)))
313  return true;
314  }
315  return false;
316  }
317 
318  // returns true if wait ended before timeout
319  template<typename _Pred,
320  typename _Clock, typename _Dur>
321  bool
322  _M_do_wait_until(_Pred __pred,
323  const chrono::time_point<_Clock, _Dur>&
324  __atime) noexcept
325  {
326  __platform_wait_t __val;
327  if (__base_type::_M_do_spin(__pred, __val,
328  __timed_backoff_spin_policy(__atime)))
329  return true;
330  return _M_do_wait_until(__pred, __val, __atime);
331  }
332 
333  template<typename _Tp, typename _ValFn,
334  typename _Rep, typename _Period>
335  bool
336  _M_do_wait_for_v(_Tp __old, _ValFn __vfn,
337  const chrono::duration<_Rep, _Period>&
338  __rtime) noexcept
339  {
340  __platform_wait_t __val;
341  if (_M_do_spin_v(__old, std::move(__vfn), __val))
342  return true;
343 
344  if (!__rtime.count())
345  return false; // no rtime supplied, and spin did not acquire
346 
347  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
348 
349  return __base_type::_M_w._M_do_wait_until(
350  __base_type::_M_addr,
351  __val,
352  chrono::steady_clock::now() + __reltime);
353  }
354 
355  template<typename _Pred,
356  typename _Rep, typename _Period>
357  bool
358  _M_do_wait_for(_Pred __pred,
359  const chrono::duration<_Rep, _Period>& __rtime) noexcept
360  {
361  __platform_wait_t __val;
362  if (__base_type::_M_do_spin(__pred, __val))
363  return true;
364 
365  if (!__rtime.count())
366  return false; // no rtime supplied, and spin did not acquire
367 
368  auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
369 
370  return _M_do_wait_until(__pred, __val,
371  chrono::steady_clock::now() + __reltime);
372  }
373  };
374 
375  using __enters_timed_wait = __timed_waiter<std::true_type>;
376  using __bare_timed_wait = __timed_waiter<std::false_type>;
377  } // namespace __detail
378 
379  // returns true if wait ended before timeout
380  template<typename _Tp, typename _ValFn,
381  typename _Clock, typename _Dur>
382  bool
383  __atomic_wait_address_until_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
384  const chrono::time_point<_Clock, _Dur>&
385  __atime) noexcept
386  {
387  __detail::__enters_timed_wait __w{__addr};
388  return __w._M_do_wait_until_v(__old, __vfn, __atime);
389  }
390 
391  template<typename _Tp, typename _Pred,
392  typename _Clock, typename _Dur>
393  bool
394  __atomic_wait_address_until(const _Tp* __addr, _Pred __pred,
395  const chrono::time_point<_Clock, _Dur>&
396  __atime) noexcept
397  {
398  __detail::__enters_timed_wait __w{__addr};
399  return __w._M_do_wait_until(__pred, __atime);
400  }
401 
402  template<typename _Pred,
403  typename _Clock, typename _Dur>
404  bool
405  __atomic_wait_address_until_bare(const __detail::__platform_wait_t* __addr,
406  _Pred __pred,
407  const chrono::time_point<_Clock, _Dur>&
408  __atime) noexcept
409  {
410  __detail::__bare_timed_wait __w{__addr};
411  return __w._M_do_wait_until(__pred, __atime);
412  }
413 
414  template<typename _Tp, typename _ValFn,
415  typename _Rep, typename _Period>
416  bool
417  __atomic_wait_address_for_v(const _Tp* __addr, _Tp&& __old, _ValFn&& __vfn,
418  const chrono::duration<_Rep, _Period>& __rtime) noexcept
419  {
420  __detail::__enters_timed_wait __w{__addr};
421  return __w._M_do_wait_for_v(__old, __vfn, __rtime);
422  }
423 
424  template<typename _Tp, typename _Pred,
425  typename _Rep, typename _Period>
426  bool
427  __atomic_wait_address_for(const _Tp* __addr, _Pred __pred,
428  const chrono::duration<_Rep, _Period>& __rtime) noexcept
429  {
430 
431  __detail::__enters_timed_wait __w{__addr};
432  return __w._M_do_wait_for(__pred, __rtime);
433  }
434 
435  template<typename _Pred,
436  typename _Rep, typename _Period>
437  bool
438  __atomic_wait_address_for_bare(const __detail::__platform_wait_t* __addr,
439  _Pred __pred,
440  const chrono::duration<_Rep, _Period>& __rtime) noexcept
441  {
442  __detail::__bare_timed_wait __w{__addr};
443  return __w._M_do_wait_for(__pred, __rtime);
444  }
445 _GLIBCXX_END_NAMESPACE_VERSION
446 } // namespace std
447 #endif // __cpp_lib_atomic_wait
448 #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