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

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