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