libstdc++
atomic_futex.h
Go to the documentation of this file.
00001 // -*- C++ -*- header.
00002 
00003 // Copyright (C) 2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/atomic_futex.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly.
00028  */
00029 
00030 #ifndef _GLIBCXX_ATOMIC_FUTEX_H
00031 #define _GLIBCXX_ATOMIC_FUTEX_H 1
00032 
00033 #pragma GCC system_header
00034 
00035 #include <bits/c++config.h>
00036 #include <atomic>
00037 #include <chrono>
00038 #if ! (defined(_GLIBCXX_HAVE_LINUX_FUTEX) && ATOMIC_INT_LOCK_FREE > 1)
00039 #include <mutex>
00040 #include <condition_variable>
00041 #endif
00042 
00043 #ifndef _GLIBCXX_ALWAYS_INLINE
00044 #define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__))
00045 #endif
00046 
00047 namespace std _GLIBCXX_VISIBILITY(default)
00048 {
00049 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00050 
00051 #if defined(_GLIBCXX_HAS_GTHREADS) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
00052 #if defined(_GLIBCXX_HAVE_LINUX_FUTEX) && ATOMIC_INT_LOCK_FREE > 1
00053   struct __atomic_futex_unsigned_base
00054   {
00055     // Returns false iff a timeout occurred.
00056     bool
00057     _M_futex_wait_until(unsigned *__addr, unsigned __val, bool __has_timeout,
00058         chrono::seconds __s, chrono::nanoseconds __ns);
00059 
00060     // This can be executed after the object has been destroyed.
00061     static void _M_futex_notify_all(unsigned* __addr);
00062   };
00063 
00064   template <unsigned _Waiter_bit = 0x80000000>
00065   class __atomic_futex_unsigned : __atomic_futex_unsigned_base
00066   {
00067     typedef chrono::system_clock __clock_t;
00068 
00069     // This must be lock-free and at offset 0.
00070     atomic<unsigned> _M_data;
00071 
00072   public:
00073     explicit
00074     __atomic_futex_unsigned(unsigned __data) : _M_data(__data)
00075     { }
00076 
00077     _GLIBCXX_ALWAYS_INLINE unsigned
00078     _M_load(memory_order __mo)
00079     {
00080       return _M_data.load(__mo) & ~_Waiter_bit;
00081     }
00082 
00083   private:
00084     // If a timeout occurs, returns a current value after the timeout;
00085     // otherwise, returns the operand's value if equal is true or a different
00086     // value if equal is false.
00087     // The assumed value is the caller's assumption about the current value
00088     // when making the call.
00089     unsigned
00090     _M_load_and_test_until(unsigned __assumed, unsigned __operand,
00091         bool __equal, memory_order __mo, bool __has_timeout,
00092         chrono::seconds __s, chrono::nanoseconds __ns)
00093     {
00094       for (;;)
00095         {
00096           // Don't bother checking the value again because we expect the caller
00097           // to have done it recently.
00098           // memory_order_relaxed is sufficient because we can rely on just the
00099           // modification order (store_notify uses an atomic RMW operation too),
00100           // and the futex syscalls synchronize between themselves.
00101           _M_data.fetch_or(_Waiter_bit, memory_order_relaxed);
00102           bool __ret = _M_futex_wait_until((unsigned*)(void*)&_M_data,
00103                                            __assumed | _Waiter_bit,
00104                                            __has_timeout, __s, __ns);
00105           // Fetch the current value after waiting (clears _Waiter_bit).
00106           __assumed = _M_load(__mo);
00107           if (!__ret || ((__operand == __assumed) == __equal))
00108             return __assumed;
00109           // TODO adapt wait time
00110         }
00111     }
00112 
00113     // Returns the operand's value if equal is true or a different value if
00114     // equal is false.
00115     // The assumed value is the caller's assumption about the current value
00116     // when making the call.
00117     unsigned
00118     _M_load_and_test(unsigned __assumed, unsigned __operand,
00119         bool __equal, memory_order __mo)
00120     {
00121       return _M_load_and_test_until(__assumed, __operand, __equal, __mo,
00122                                     false, {}, {});
00123     }
00124 
00125     // If a timeout occurs, returns a current value after the timeout;
00126     // otherwise, returns the operand's value if equal is true or a different
00127     // value if equal is false.
00128     // The assumed value is the caller's assumption about the current value
00129     // when making the call.
00130     template<typename _Dur>
00131     unsigned
00132     _M_load_and_test_until_impl(unsigned __assumed, unsigned __operand,
00133         bool __equal, memory_order __mo,
00134         const chrono::time_point<__clock_t, _Dur>& __atime)
00135     {
00136       auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
00137       auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
00138       // XXX correct?
00139       return _M_load_and_test_until(__assumed, __operand, __equal, __mo,
00140           true, __s.time_since_epoch(), __ns);
00141     }
00142 
00143   public:
00144 
00145     _GLIBCXX_ALWAYS_INLINE unsigned
00146     _M_load_when_not_equal(unsigned __val, memory_order __mo)
00147     {
00148       unsigned __i = _M_load(__mo);
00149       if ((__i & ~_Waiter_bit) != __val)
00150         return (__i & ~_Waiter_bit);
00151       // TODO Spin-wait first.
00152       return _M_load_and_test(__i, __val, false, __mo);
00153     }
00154 
00155     _GLIBCXX_ALWAYS_INLINE void
00156     _M_load_when_equal(unsigned __val, memory_order __mo)
00157     {
00158       unsigned __i = _M_load(__mo);
00159       if ((__i & ~_Waiter_bit) == __val)
00160         return;
00161       // TODO Spin-wait first.
00162       _M_load_and_test(__i, __val, true, __mo);
00163     }
00164 
00165     // Returns false iff a timeout occurred.
00166     template<typename _Rep, typename _Period>
00167       _GLIBCXX_ALWAYS_INLINE bool
00168       _M_load_when_equal_for(unsigned __val, memory_order __mo,
00169           const chrono::duration<_Rep, _Period>& __rtime)
00170       {
00171         return _M_load_when_equal_until(__val, __mo,
00172                                         __clock_t::now() + __rtime);
00173       }
00174 
00175     // Returns false iff a timeout occurred.
00176     template<typename _Clock, typename _Duration>
00177       _GLIBCXX_ALWAYS_INLINE bool
00178       _M_load_when_equal_until(unsigned __val, memory_order __mo,
00179           const chrono::time_point<_Clock, _Duration>& __atime)
00180       {
00181         // DR 887 - Sync unknown clock to known clock.
00182         const typename _Clock::time_point __c_entry = _Clock::now();
00183         const __clock_t::time_point __s_entry = __clock_t::now();
00184         const auto __delta = __atime - __c_entry;
00185         const auto __s_atime = __s_entry + __delta;
00186         return _M_load_when_equal_until(__val, __mo, __s_atime);
00187       }
00188 
00189     // Returns false iff a timeout occurred.
00190     template<typename _Duration>
00191     _GLIBCXX_ALWAYS_INLINE bool
00192     _M_load_when_equal_until(unsigned __val, memory_order __mo,
00193         const chrono::time_point<__clock_t, _Duration>& __atime)
00194     {
00195       unsigned __i = _M_load(__mo);
00196       if ((__i & ~_Waiter_bit) == __val)
00197         return true;
00198       // TODO Spin-wait first.  Ignore effect on timeout.
00199       __i = _M_load_and_test_until_impl(__i, __val, true, __mo, __atime);
00200       return (__i & ~_Waiter_bit) == __val;
00201     }
00202 
00203     _GLIBCXX_ALWAYS_INLINE void
00204     _M_store_notify_all(unsigned __val, memory_order __mo)
00205     {
00206       unsigned* __futex = (unsigned *)(void *)&_M_data;
00207       if (_M_data.exchange(__val, __mo) & _Waiter_bit)
00208         _M_futex_notify_all(__futex);
00209     }
00210   };
00211 
00212 #else // ! (_GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1)
00213 
00214   // If futexes are not available, use a mutex and a condvar to wait.
00215   // Because we access the data only within critical sections, all accesses
00216   // are sequentially consistent; thus, we satisfy any provided memory_order.
00217   template <unsigned _Waiter_bit = 0x80000000>
00218   class __atomic_futex_unsigned
00219   {
00220     typedef chrono::system_clock __clock_t;
00221 
00222     unsigned _M_data;
00223     mutex _M_mutex;
00224     condition_variable _M_condvar;
00225 
00226   public:
00227     explicit
00228     __atomic_futex_unsigned(unsigned __data) : _M_data(__data)
00229     { }
00230 
00231     _GLIBCXX_ALWAYS_INLINE unsigned
00232     _M_load(memory_order __mo)
00233     {
00234       unique_lock<mutex> __lock(_M_mutex);
00235       return _M_data;
00236     }
00237 
00238     _GLIBCXX_ALWAYS_INLINE unsigned
00239     _M_load_when_not_equal(unsigned __val, memory_order __mo)
00240     {
00241       unique_lock<mutex> __lock(_M_mutex);
00242       while (_M_data == __val)
00243         _M_condvar.wait(__lock);
00244       return _M_data;
00245     }
00246 
00247     _GLIBCXX_ALWAYS_INLINE void
00248     _M_load_when_equal(unsigned __val, memory_order __mo)
00249     {
00250       unique_lock<mutex> __lock(_M_mutex);
00251       while (_M_data != __val)
00252         _M_condvar.wait(__lock);
00253     }
00254 
00255     template<typename _Rep, typename _Period>
00256       _GLIBCXX_ALWAYS_INLINE bool
00257       _M_load_when_equal_for(unsigned __val, memory_order __mo,
00258           const chrono::duration<_Rep, _Period>& __rtime)
00259       {
00260         unique_lock<mutex> __lock(_M_mutex);
00261         return _M_condvar.wait_for(__lock, __rtime,
00262                                    [&] { return _M_data == __val;});
00263       }
00264 
00265     template<typename _Clock, typename _Duration>
00266       _GLIBCXX_ALWAYS_INLINE bool
00267       _M_load_when_equal_until(unsigned __val, memory_order __mo,
00268           const chrono::time_point<_Clock, _Duration>& __atime)
00269       {
00270         unique_lock<mutex> __lock(_M_mutex);
00271         return _M_condvar.wait_until(__lock, __atime,
00272                                      [&] { return _M_data == __val;});
00273       }
00274 
00275     _GLIBCXX_ALWAYS_INLINE void
00276     _M_store_notify_all(unsigned __val, memory_order __mo)
00277     {
00278       unique_lock<mutex> __lock(_M_mutex);
00279       _M_data = __val;
00280       _M_condvar.notify_all();
00281     }
00282   };
00283 
00284 #endif // _GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1
00285 #endif // _GLIBCXX_HAS_GTHREADS && _GLIBCXX_USE_C99_STDINT_TR1
00286 
00287 _GLIBCXX_END_NAMESPACE_VERSION
00288 } // namespace std
00289 
00290 #endif