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