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 #include <bits/chrono.h>
41 
42 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
43 #include <sys/time.h>
44 #endif
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49 
50  namespace __detail
51  {
52  using __wait_clock_t = chrono::steady_clock;
53 
54  template<typename _Clock, typename _Dur>
55  __wait_clock_t::time_point
56  __to_wait_clock(const chrono::time_point<_Clock, _Dur>& __atime) noexcept
57  {
58  const typename _Clock::time_point __c_entry = _Clock::now();
59  const __wait_clock_t::time_point __w_entry = __wait_clock_t::now();
60  const auto __delta = __atime - __c_entry;
61  using __w_dur = typename __wait_clock_t::duration;
62  return __w_entry + chrono::ceil<__w_dur>(__delta);
63  }
64 
65  template<typename _Dur>
66  __wait_clock_t::time_point
67  __to_wait_clock(const chrono::time_point<__wait_clock_t,
68  _Dur>& __atime) noexcept
69  {
70  using __w_dur = typename __wait_clock_t::duration;
71  return chrono::ceil<__w_dur>(__atime);
72  }
73 
74 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
75 #define _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
76  // returns true if wait ended before timeout
77  template<typename _Dur>
78  bool
79  __platform_wait_until_impl(const __platform_wait_t* __addr,
80  __platform_wait_t __old,
81  const chrono::time_point<__wait_clock_t, _Dur>&
82  __atime) noexcept
83  {
84  auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
85  auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
86 
87  struct timespec __rt =
88  {
89  static_cast<std::time_t>(__s.time_since_epoch().count()),
90  static_cast<long>(__ns.count())
91  };
92 
93  auto __e = syscall (SYS_futex, __addr,
94  static_cast<int>(__futex_wait_flags::
95  __wait_bitset_private),
96  __old, &__rt, nullptr,
97  static_cast<int>(__futex_wait_flags::
98  __bitset_match_any));
99 
100  if (__e)
101  {
102  if (errno == ETIMEDOUT)
103  return false;
104  if (errno != EINTR && errno != EAGAIN)
105  __throw_system_error(errno);
106  }
107  return true;
108  }
109 
110  // returns true if wait ended before timeout
111  template<typename _Clock, typename _Dur>
112  bool
113  __platform_wait_until(const __platform_wait_t* __addr, __platform_wait_t __old,
114  const chrono::time_point<_Clock, _Dur>& __atime)
115  {
116  if constexpr (is_same_v<__wait_clock_t, _Clock>)
117  {
118  return __platform_wait_until_impl(__addr, __old, __atime);
119  }
120  else
121  {
122  if (!__platform_wait_until_impl(__addr, __old,
123  __to_wait_clock(__atime)))
124  {
125  // We got a timeout when measured against __clock_t but
126  // we need to check against the caller-supplied clock
127  // to tell whether we should return a timeout.
128  if (_Clock::now() < __atime)
129  return true;
130  }
131  return false;
132  }
133  }
134 #else
135 // define _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT and implement __platform_wait_until()
136 // if there is a more efficient primitive supported by the platform
137 // (e.g. __ulock_wait())which is better than pthread_cond_clockwait
138 #endif // ! PLATFORM_TIMED_WAIT
139 
140  // Returns true if wait ended before timeout.
141  // _Clock must be either steady_clock or system_clock.
142  template<typename _Clock, typename _Dur>
143  bool
144  __cond_wait_until_impl(__condvar& __cv, mutex& __mx,
145  const chrono::time_point<_Clock, _Dur>& __atime)
146  {
147  static_assert(std::__is_one_of<_Clock, chrono::steady_clock,
148  chrono::system_clock>::value);
149 
150  auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
151  auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
152 
153  __gthread_time_t __ts =
154  {
155  static_cast<std::time_t>(__s.time_since_epoch().count()),
156  static_cast<long>(__ns.count())
157  };
158 
159 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
160  if constexpr (is_same_v<chrono::steady_clock, _Clock>)
161  __cv.wait_until(__mx, CLOCK_MONOTONIC, __ts);
162  else
163 #endif
164  __cv.wait_until(__mx, __ts);
165  return _Clock::now() < __atime;
166  }
167 
168  // returns true if wait ended before timeout
169  template<typename _Clock, typename _Dur>
170  bool
171  __cond_wait_until(__condvar& __cv, mutex& __mx,
172  const chrono::time_point<_Clock, _Dur>& __atime)
173  {
174 #ifdef _GLIBCXX_USE_PTHREAD_COND_CLOCKWAIT
175  if constexpr (is_same_v<_Clock, chrono::steady_clock>)
176  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
177  else
178 #endif
179  if constexpr (is_same_v<_Clock, chrono::system_clock>)
180  return __detail::__cond_wait_until_impl(__cv, __mx, __atime);
181  else
182  {
183  if (__cond_wait_until_impl(__cv, __mx,
184  __to_wait_clock(__atime)))
185  {
186  // We got a timeout when measured against __clock_t but
187  // we need to check against the caller-supplied clock
188  // to tell whether we should return a timeout.
189  if (_Clock::now() < __atime)
190  return true;
191  }
192  return false;
193  }
194  }
195 
196  struct __timed_waiter_pool : __waiter_pool_base
197  {
198  // returns true if wait ended before timeout
199  template<typename _Clock, typename _Dur>
200  bool
201  _M_do_wait_until(__platform_wait_t* __addr, __platform_wait_t __old,
202  const chrono::time_point<_Clock, _Dur>& __atime)
203  {
204 #ifdef _GLIBCXX_HAVE_PLATFORM_TIMED_WAIT
205  return __platform_wait_until(__addr, __old, __atime);
206 #else
207  __platform_wait_t __val;
208  __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
209  if (__val == __old)
210  {
211  lock_guard<mutex> __l(_M_mtx);
212  return __cond_wait_until(_M_cv, _M_mtx, __atime);
213  }
214  else
215  return true;
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
ISO C++ entities toplevel namespace is std.
void sleep_for(const chrono::duration< _Rep, _Period > &__rtime)
this_thread::sleep_for