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_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_WAIT_H
31 #define _GLIBCXX_ATOMIC_WAIT_H 1
32
33 #pragma GCC system_header
34
35 #include <bits/c++config.h>
36 #if defined _GLIBCXX_HAS_GTHREADS || defined _GLIBCXX_HAVE_LINUX_FUTEX
37 #include <bits/functional_hash.h>
38 #include <bits/gthr.h>
39 #include <ext/numeric_traits.h>
40
41 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
42 # include <cerrno>
43 # include <climits>
44 # include <unistd.h>
45 # include <syscall.h>
46 # include <bits/functexcept.h>
47 #endif
48
49 # include <bits/std_mutex.h> // std::mutex, std::__condvar
50
51 #define __cpp_lib_atomic_wait 201907L
52
_GLIBCXX_VISIBILITY(default)53 namespace std _GLIBCXX_VISIBILITY(default)
54 {
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
56 namespace __detail
57 {
58 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
59 using __platform_wait_t = int;
60 static constexpr size_t __platform_wait_alignment = 4;
61 #else
62 using __platform_wait_t = uint64_t;
63 static constexpr size_t __platform_wait_alignment
64 = __alignof__(__platform_wait_t);
65 #endif
66 } // namespace __detail
67
68 template<typename _Tp>
69 inline constexpr bool __platform_wait_uses_type
70 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
71 = is_scalar_v<_Tp>
72 && ((sizeof(_Tp) == sizeof(__detail::__platform_wait_t))
73 && (alignof(_Tp*) >= __platform_wait_alignment));
74 #else
75 = false;
76 #endif
77
78 namespace __detail
79 {
80 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
81 #define _GLIBCXX_HAVE_PLATFORM_WAIT 1
82 enum class __futex_wait_flags : int
83 {
84 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX_PRIVATE
85 __private_flag = 128,
86 #else
87 __private_flag = 0,
88 #endif
89 __wait = 0,
90 __wake = 1,
91 __wait_bitset = 9,
92 __wake_bitset = 10,
93 __wait_private = __wait | __private_flag,
94 __wake_private = __wake | __private_flag,
95 __wait_bitset_private = __wait_bitset | __private_flag,
96 __wake_bitset_private = __wake_bitset | __private_flag,
97 __bitset_match_any = -1
98 };
99
100 template<typename _Tp>
101 void
102 __platform_wait(const _Tp* __addr, __platform_wait_t __val) noexcept
103 {
104 auto __e = syscall (SYS_futex, static_cast<const void*>(__addr),
105 static_cast<int>(__futex_wait_flags::__wait_private),
106 __val, nullptr);
107 if (!__e || errno == EAGAIN)
108 return;
109 if (errno != EINTR)
110 __throw_system_error(errno);
111 }
112
113 template<typename _Tp>
114 void
115 __platform_notify(const _Tp* __addr, bool __all) noexcept
116 {
117 syscall (SYS_futex, static_cast<const void*>(__addr),
118 static_cast<int>(__futex_wait_flags::__wake_private),
119 __all ? INT_MAX : 1);
120 }
121 #else
122 // define _GLIBCX_HAVE_PLATFORM_WAIT and implement __platform_wait()
123 // and __platform_notify() if there is a more efficient primitive supported
124 // by the platform (e.g. __ulock_wait()/__ulock_wake()) which is better than
125 // a mutex/condvar based wait
126 #endif
127
128 inline void
129 __thread_yield() noexcept
130 {
131 #if defined _GLIBCXX_HAS_GTHREADS && defined _GLIBCXX_USE_SCHED_YIELD
132 __gthread_yield();
133 #endif
134 }
135
136 inline void
137 __thread_relax() noexcept
138 {
139 #if defined __i386__ || defined __x86_64__
140 __builtin_ia32_pause();
141 #else
142 __thread_yield();
143 #endif
144 }
145
146 constexpr auto __atomic_spin_count_1 = 12;
147 constexpr auto __atomic_spin_count_2 = 4;
148
149 struct __default_spin_policy
150 {
151 bool
152 operator()() const noexcept
153 { return false; }
154 };
155
156 template<typename _Pred,
157 typename _Spin = __default_spin_policy>
158 bool
159 __atomic_spin(_Pred& __pred, _Spin __spin = _Spin{ }) noexcept
160 {
161 for (auto __i = 0; __i < __atomic_spin_count_1; ++__i)
162 {
163 if (__pred())
164 return true;
165 __detail::__thread_relax();
166 }
167
168 for (auto __i = 0; __i < __atomic_spin_count_2; ++__i)
169 {
170 if (__pred())
171 return true;
172 __detail::__thread_yield();
173 }
174
175 while (__spin())
176 {
177 if (__pred())
178 return true;
179 }
180
181 return false;
182 }
183
184 // return true if equal
185 template<typename _Tp>
186 bool __atomic_compare(const _Tp& __a, const _Tp& __b)
187 {
188 // TODO make this do the correct padding bit ignoring comparison
189 return __builtin_memcmp(&__a, &__b, sizeof(_Tp)) == 0;
190 }
191
192 struct __waiter_pool_base
193 {
194 #ifdef __cpp_lib_hardware_interference_size
195 static constexpr auto _S_align = hardware_destructive_interference_size;
196 #else
197 static constexpr auto _S_align = 64;
198 #endif
199
200 alignas(_S_align) __platform_wait_t _M_wait = 0;
201
202 #ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
203 mutex _M_mtx;
204 #endif
205
206 alignas(_S_align) __platform_wait_t _M_ver = 0;
207
208 #ifndef _GLIBCXX_HAVE_PLATFORM_WAIT
209 __condvar _M_cv;
210 #endif
211 __waiter_pool_base() = default;
212
213 void
214 _M_enter_wait() noexcept
215 { __atomic_fetch_add(&_M_wait, 1, __ATOMIC_ACQ_REL); }
216
217 void
218 _M_leave_wait() noexcept
219 { __atomic_fetch_sub(&_M_wait, 1, __ATOMIC_ACQ_REL); }
220
221 bool
222 _M_waiting() const noexcept
223 {
224 __platform_wait_t __res;
225 __atomic_load(&_M_wait, &__res, __ATOMIC_ACQUIRE);
226 return __res > 0;
227 }
228
229 void
230 _M_notify(const __platform_wait_t* __addr, bool __all, bool __bare) noexcept
231 {
232 if (!(__bare || _M_waiting()))
233 return;
234
235 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
236 __platform_notify(__addr, __all);
237 #else
238 if (__all)
239 _M_cv.notify_all();
240 else
241 _M_cv.notify_one();
242 #endif
243 }
244
245 static __waiter_pool_base&
246 _S_for(const void* __addr) noexcept
247 {
248 constexpr uintptr_t __ct = 16;
249 static __waiter_pool_base __w[__ct];
250 auto __key = (uintptr_t(__addr) >> 2) % __ct;
251 return __w[__key];
252 }
253 };
254
255 struct __waiter_pool : __waiter_pool_base
256 {
257 void
258 _M_do_wait(const __platform_wait_t* __addr, __platform_wait_t __old) noexcept
259 {
260 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
261 __platform_wait(__addr, __old);
262 #else
263 __platform_wait_t __val;
264 __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
265 if (__val == __old)
266 {
267 lock_guard<mutex> __l(_M_mtx);
268 _M_cv.wait(_M_mtx);
269 }
270 #endif // __GLIBCXX_HAVE_PLATFORM_WAIT
271 }
272 };
273
274 template<typename _Tp>
275 struct __waiter_base
276 {
277 using __waiter_type = _Tp;
278
279 __waiter_type& _M_w;
280 __platform_wait_t* _M_addr;
281
282 template<typename _Up>
283 static __platform_wait_t*
284 _S_wait_addr(const _Up* __a, __platform_wait_t* __b)
285 {
286 if constexpr (__platform_wait_uses_type<_Up>)
287 return reinterpret_cast<__platform_wait_t*>(const_cast<_Up*>(__a));
288 else
289 return __b;
290 }
291
292 static __waiter_type&
293 _S_for(const void* __addr) noexcept
294 {
295 static_assert(sizeof(__waiter_type) == sizeof(__waiter_pool_base));
296 auto& res = __waiter_pool_base::_S_for(__addr);
297 return reinterpret_cast<__waiter_type&>(res);
298 }
299
300 template<typename _Up>
301 explicit __waiter_base(const _Up* __addr) noexcept
302 : _M_w(_S_for(__addr))
303 , _M_addr(_S_wait_addr(__addr, &_M_w._M_ver))
304 { }
305
306 bool
307 _M_laundered() const
308 { return _M_addr == &_M_w._M_ver; }
309
310 void
311 _M_notify(bool __all, bool __bare = false)
312 {
313 if (_M_laundered())
314 {
315 __atomic_fetch_add(_M_addr, 1, __ATOMIC_ACQ_REL);
316 __all = true;
317 }
318 _M_w._M_notify(_M_addr, __all, __bare);
319 }
320
321 template<typename _Up, typename _ValFn,
322 typename _Spin = __default_spin_policy>
323 static bool
324 _S_do_spin_v(__platform_wait_t* __addr,
325 const _Up& __old, _ValFn __vfn,
326 __platform_wait_t& __val,
327 _Spin __spin = _Spin{ })
328 {
329 auto const __pred = [=]
330 { return !__detail::__atomic_compare(__old, __vfn()); };
331
332 if constexpr (__platform_wait_uses_type<_Up>)
333 {
334 __val == __old;
335 }
336 else
337 {
338 __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
339 }
340 return __atomic_spin(__pred, __spin);
341 }
342
343 template<typename _Up, typename _ValFn,
344 typename _Spin = __default_spin_policy>
345 bool
346 _M_do_spin_v(const _Up& __old, _ValFn __vfn,
347 __platform_wait_t& __val,
348 _Spin __spin = _Spin{ })
349 { return _S_do_spin_v(_M_addr, __old, __vfn, __val, __spin); }
350
351 template<typename _Pred,
352 typename _Spin = __default_spin_policy>
353 static bool
354 _S_do_spin(const __platform_wait_t* __addr,
355 _Pred __pred,
356 __platform_wait_t& __val,
357 _Spin __spin = _Spin{ })
358 {
359 __atomic_load(__addr, &__val, __ATOMIC_RELAXED);
360 return __atomic_spin(__pred, __spin);
361 }
362
363 template<typename _Pred,
364 typename _Spin = __default_spin_policy>
365 bool
366 _M_do_spin(_Pred __pred, __platform_wait_t& __val,
367 _Spin __spin = _Spin{ })
368 { return _S_do_spin(_M_addr, __pred, __val, __spin); }
369 };
370
371 template<typename _EntersWait>
372 struct __waiter : __waiter_base<__waiter_pool>
373 {
374 using __base_type = __waiter_base<__waiter_pool>;
375
376 template<typename _Tp>
377 explicit __waiter(const _Tp* __addr) noexcept
378 : __base_type(__addr)
379 {
380 if constexpr (_EntersWait::value)
381 _M_w._M_enter_wait();
382 }
383
384 ~__waiter()
385 {
386 if constexpr (_EntersWait::value)
387 _M_w._M_leave_wait();
388 }
389
390 template<typename _Tp, typename _ValFn>
391 void
392 _M_do_wait_v(_Tp __old, _ValFn __vfn)
393 {
394 __platform_wait_t __val;
395 if (__base_type::_M_do_spin_v(__old, __vfn, __val))
396 return;
397
398 do
399 {
400 __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
401 }
402 while (__detail::__atomic_compare(__old, __vfn()));
403 }
404
405 template<typename _Pred>
406 void
407 _M_do_wait(_Pred __pred) noexcept
408 {
409 do
410 {
411 __platform_wait_t __val;
412 if (__base_type::_M_do_spin(__pred, __val))
413 return;
414 __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
415 }
416 while (!__pred());
417 }
418 };
419
420 using __enters_wait = __waiter<std::true_type>;
421 using __bare_wait = __waiter<std::false_type>;
422 } // namespace __detail
423
424 template<typename _Tp, typename _ValFn>
425 void
426 __atomic_wait_address_v(const _Tp* __addr, _Tp __old,
427 _ValFn __vfn) noexcept
428 {
429 __detail::__enters_wait __w(__addr);
430 __w._M_do_wait_v(__old, __vfn);
431 }
432
433 template<typename _Tp, typename _Pred>
434 void
435 __atomic_wait_address(const _Tp* __addr, _Pred __pred) noexcept
436 {
437 __detail::__enters_wait __w(__addr);
438 __w._M_do_wait(__pred);
439 }
440
441 // This call is to be used by atomic types which track contention externally
442 template<typename _Pred>
443 void
444 __atomic_wait_address_bare(const __detail::__platform_wait_t* __addr,
445 _Pred __pred) noexcept
446 {
447 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
448 do
449 {
450 __detail::__platform_wait_t __val;
451 if (__detail::__bare_wait::_S_do_spin(__addr, __pred, __val))
452 return;
453 __detail::__platform_wait(__addr, __val);
454 }
455 while (!__pred());
456 #else // !_GLIBCXX_HAVE_PLATFORM_WAIT
457 __detail::__bare_wait __w(__addr);
458 __w._M_do_wait(__pred);
459 #endif
460 }
461
462 template<typename _Tp>
463 void
464 __atomic_notify_address(const _Tp* __addr, bool __all) noexcept
465 {
466 __detail::__bare_wait __w(__addr);
467 __w._M_notify(__all);
468 }
469
470 // This call is to be used by atomic types which track contention externally
471 inline void
472 __atomic_notify_address_bare(const __detail::__platform_wait_t* __addr,
473 bool __all) noexcept
474 {
475 #ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
476 __detail::__platform_notify(__addr, __all);
477 #else
478 __detail::__bare_wait __w(__addr);
479 __w._M_notify(__all, true);
480 #endif
481 }
482 _GLIBCXX_END_NAMESPACE_VERSION
483 } // namespace std
484 #endif // GTHREADS || LINUX_FUTEX
485 #endif // _GLIBCXX_ATOMIC_WAIT_H
486