libstdc++-v3/include/bits/atomic_wait.h

   1 // -*- C++ -*- header.
   2
   3 // Copyright (C) 2020 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 || _GLIBCXX_HAVE_LINUX_FUTEX
  37 #include <bits/functional_hash.h>
  38 #include <bits/gthr.h>
  39 #include <bits/std_mutex.h>
  40 #include <bits/unique_lock.h>
  41 #include <ext/numeric_traits.h>
  42
  43 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
  44 #include <climits>
  45 #include <unistd.h>
  46 #include <syscall.h>
  47 #endif
  48
  49
  50 // TODO get this from Autoconf
  51 #define _GLIBCXX_HAVE_LINUX_FUTEX_PRIVATE 1
  52
  53 namespace std _GLIBCXX_VISIBILITY(default)
  54 {
  55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  56   namespace __detail
  57   {
  58     using __platform_wait_t = int;
  59
  60     constexpr auto __atomic_spin_count_1 = 16;
  61     constexpr auto __atomic_spin_count_2 = 12;
  62
  63     inline constexpr
  64     auto __platform_wait_max_value =
  65                 __gnu_cxx::__int_traits<__platform_wait_t>::__max;
  66
  67     template<typename _Tp>
  68       inline constexpr bool __platform_wait_uses_type
  69 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
  70         = is_same_v<remove_cv_t<_Tp>, __platform_wait_t>;
  71 #else
  72         = false;
  73 #endif
  74
  75 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
  76     enum class __futex_wait_flags : int
  77     {
  78 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX_PRIVATE
  79       __private_flag = 128,
  80 #else
  81       __private_flag = 0,
  82 #endif
  83       __wait = 0,
  84       __wake = 1,
  85       __wait_bitset = 9,
  86       __wake_bitset = 10,
  87       __wait_private = __wait | __private_flag,
  88       __wake_private = __wake | __private_flag,
  89       __wait_bitset_private = __wait_bitset | __private_flag,
  90       __wake_bitset_private = __wake_bitset | __private_flag,
  91       __bitset_match_any = -1
  92     };
  93
  94     template<typename _Tp>
  95       void
  96       __platform_wait(const _Tp* __addr, __platform_wait_t __val) noexcept
  97       {
  98         for(;;)
  99           {
 100             auto __e = syscall (SYS_futex, static_cast<const void*>(__addr),
 101                                   static_cast<int>(__futex_wait_flags::__wait_private),
 102                                     __val, nullptr);
 103             if (!__e)
 104               break;
 105             else if (!(errno == EINTR || errno == EAGAIN))
 106               __throw_system_error(__e);
 107           }
 108       }
 109
 110     template<typename _Tp>
 111       void
 112       __platform_notify(const _Tp* __addr, bool __all) noexcept
 113       {
 114         syscall (SYS_futex, static_cast<const void*>(__addr),
 115                   static_cast<int>(__futex_wait_flags::__wake_private),
 116                     __all ? INT_MAX : 1);
 117       }
 118 #endif
 119
 120     struct __waiters
 121     {
 122        alignas(64) __platform_wait_t _M_ver = 0;
 123        alignas(64) __platform_wait_t _M_wait = 0;
 124
 125 #ifndef _GLIBCXX_HAVE_LINUX_FUTEX
 126       using __lock_t = std::unique_lock<std::mutex>;
 127       mutable __lock_t::mutex_type _M_mtx;
 128
 129 #  ifdef __GTHREAD_COND_INIT
 130       mutable __gthread_cond_t _M_cv = __GTHREAD_COND_INIT;
 131       __waiters() noexcept = default;
 132 #  else
 133       mutable __gthread_cond_t _M_cv;
 134       __waiters() noexcept
 135       {
 136         __GTHREAD_COND_INIT_FUNCTION(&_M_cond);
 137       }
 138 #  endif
 139 #endif
 140
 141       __platform_wait_t
 142       _M_enter_wait() noexcept
 143       {
 144         __platform_wait_t __res;
 145         __atomic_load(&_M_ver, &__res, __ATOMIC_ACQUIRE);
 146         __atomic_fetch_add(&_M_wait, 1, __ATOMIC_ACQ_REL);
 147         return __res;
 148       }
 149
 150       void
 151       _M_leave_wait() noexcept
 152       {
 153         __atomic_fetch_sub(&_M_wait, 1, __ATOMIC_ACQ_REL);
 154       }
 155
 156       void
 157       _M_do_wait(__platform_wait_t __version) noexcept
 158       {
 159 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
 160         __platform_wait(&_M_ver, __version);
 161 #else
 162         __platform_wait_t __cur = 0;
 163         while (__cur <= __version)
 164           {
 165             __waiters::__lock_t __l(_M_mtx);
 166             auto __e = __gthread_cond_wait(&_M_cv, __l.mutex()->native_handle());
 167             if (__e)
 168               __throw_system_error(__e);
 169             __platform_wait_t __last = __cur;
 170             __atomic_load(&_M_ver, &__cur, __ATOMIC_ACQUIRE);
 171             if (__cur < __last)
 172               break; // break the loop if version overflows
 173           }
 174 #endif
 175       }
 176
 177       bool
 178       _M_waiting() const noexcept
 179       {
 180         __platform_wait_t __res;
 181         __atomic_load(&_M_wait, &__res, __ATOMIC_ACQUIRE);
 182         return __res;
 183       }
 184
 185       void
 186       _M_notify(bool __all) noexcept
 187       {
 188         __atomic_fetch_add(&_M_ver, 1, __ATOMIC_ACQ_REL);
 189 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
 190         __platform_notify(&_M_ver, __all);
 191 #else
 192         auto __e = __gthread_cond_broadcast(&_M_cv);
 193         if (__e)
 194           __throw_system_error(__e);
 195 #endif
 196       }
 197
 198       static __waiters&
 199       _S_for(const void* __t)
 200       {
 201         const unsigned char __mask = 0xf;
 202         static __waiters __w[__mask + 1];
 203
 204         auto __key = _Hash_impl::hash(__t) & __mask;
 205         return __w[__key];
 206       }
 207     };
 208
 209     struct __waiter
 210     {
 211       __waiters& _M_w;
 212       __platform_wait_t _M_version;
 213
 214       template<typename _Tp>
 215         __waiter(const _Tp* __addr) noexcept
 216           : _M_w(__waiters::_S_for(static_cast<const void*>(__addr)))
 217           , _M_version(_M_w._M_enter_wait())
 218         { }
 219
 220       ~__waiter()
 221       { _M_w._M_leave_wait(); }
 222
 223       void _M_do_wait() noexcept
 224       { _M_w._M_do_wait(_M_version); }
 225     };
 226
 227     void
 228     __thread_relax() noexcept
 229     {
 230 #if defined __i386__ || defined __x86_64__
 231       __builtin_ia32_pause();
 232 #elif defined _GLIBCXX_USE_SCHED_YIELD
 233       __gthread_yield();
 234 #endif
 235     }
 236
 237     void
 238     __thread_yield() noexcept
 239    {
 240 #if defined _GLIBCXX_USE_SCHED_YIELD
 241      __gthread_yield();
 242 #endif
 243     }
 244
 245   } // namespace __detail
 246
 247   template<typename _Pred>
 248     bool
 249     __atomic_spin(_Pred& __pred) noexcept
 250     {
 251       for (auto __i = 0; __i < __detail::__atomic_spin_count_1; ++__i)
 252         {
 253           if (__pred())
 254             return true;
 255
 256           if (__i < __detail::__atomic_spin_count_2)
 257             __detail::__thread_relax();
 258           else
 259             __detail::__thread_yield();
 260         }
 261       return false;
 262     }
 263
 264   template<typename _Tp, typename _Pred>
 265     void
 266     __atomic_wait(const _Tp* __addr, _Tp __old, _Pred __pred) noexcept
 267     {
 268       using namespace __detail;
 269       if (std::__atomic_spin(__pred))
 270         return;
 271
 272       __waiter __w(__addr);
 273       while (!__pred())
 274         {
 275           if constexpr (__platform_wait_uses_type<_Tp>)
 276             {
 277               __platform_wait(__addr, __old);
 278             }
 279           else
 280             {
 281               // TODO support timed backoff when this can be moved into the lib
 282               __w._M_do_wait();
 283             }
 284         }
 285     }
 286
 287   template<typename _Tp>
 288     void
 289     __atomic_notify(const _Tp* __addr, bool __all) noexcept
 290     {
 291       using namespace __detail;
 292       auto& __w = __waiters::_S_for((void*)__addr);
 293       if (!__w._M_waiting())
 294         return;
 295
 296 #ifdef _GLIBCXX_HAVE_LINUX_FUTEX
 297       if constexpr (__platform_wait_uses_type<_Tp>)
 298         {
 299           __platform_notify((__platform_wait_t*)(void*) __addr, __all);
 300         }
 301       else
 302 #endif
 303         {
 304           __w._M_notify(__all);
 305         }
 306     }
 307 _GLIBCXX_END_NAMESPACE_VERSION
 308 } // namespace std
 309 #endif // GTHREADS || LINUX_FUTEX
 310 #endif // _GLIBCXX_ATOMIC_WAIT_H