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 to
00097           // 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;
00103           __ret = _M_futex_wait_until((unsigned*)(void*)&_M_data,
00104               __assumed | _Waiter_bit, __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, chrono::seconds(0), chrono::nanoseconds(0));
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) return;
00150       // TODO Spin-wait first.
00151       return _M_load_and_test(__i, __val, false, __mo);
00152     }
00153 
00154     _GLIBCXX_ALWAYS_INLINE void
00155     _M_load_when_equal(unsigned __val, memory_order __mo)
00156     {
00157       unsigned __i = _M_load(__mo);
00158       if ((__i & ~_Waiter_bit) == __val)
00159         return;
00160       // TODO Spin-wait first.
00161       _M_load_and_test(__i, __val, true, __mo);
00162     }
00163 
00164     // Returns false iff a timeout occurred.
00165     template<typename _Rep, typename _Period>
00166       _GLIBCXX_ALWAYS_INLINE bool
00167       _M_load_when_equal_for(unsigned __val, memory_order __mo,
00168           const chrono::duration<_Rep, _Period>& __rtime)
00169       {
00170         return _M_load_when_equal_until(__val, __mo,
00171                                         __clock_t::now() + __rtime);
00172       }
00173 
00174     // Returns false iff a timeout occurred.
00175     template<typename _Clock, typename _Duration>
00176       _GLIBCXX_ALWAYS_INLINE bool
00177       _M_load_when_equal_until(unsigned __val, memory_order __mo,
00178           const chrono::time_point<_Clock, _Duration>& __atime)
00179       {
00180         // DR 887 - Sync unknown clock to known clock.
00181         const typename _Clock::time_point __c_entry = _Clock::now();
00182         const __clock_t::time_point __s_entry = __clock_t::now();
00183         const auto __delta = __atime - __c_entry;
00184         const auto __s_atime = __s_entry + __delta;
00185         return _M_load_when_equal_until(__val, __mo, __s_atime);
00186       }
00187 
00188     // Returns false iff a timeout occurred.
00189     template<typename _Duration>
00190     _GLIBCXX_ALWAYS_INLINE bool
00191     _M_load_when_equal_until(unsigned __val, memory_order __mo,
00192         const chrono::time_point<__clock_t, _Duration>& __atime)
00193     {
00194       unsigned __i = _M_load(__mo);
00195       if ((__i & ~_Waiter_bit) == __val)
00196         return true;
00197       // TODO Spin-wait first.  Ignore effect on timeout.
00198       __i = _M_load_and_test_until_impl(__i, __val, true, __mo, __atime);
00199       return (__i & ~_Waiter_bit) == __val;
00200     }
00201 
00202     _GLIBCXX_ALWAYS_INLINE void
00203     _M_store_notify_all(unsigned __val, memory_order __mo)
00204     {
00205       unsigned* __futex = (unsigned *)(void *)&_M_data;
00206       if (_M_data.exchange(__val, __mo) & _Waiter_bit)
00207         _M_futex_notify_all(__futex);
00208     }
00209   };
00210 
00211 #else // ! (_GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1)
00212 
00213   // If futexes are not available, use a mutex and a condvar to wait.
00214   // Because we access the data only within critical sections, all accesses
00215   // are sequentially consistent; thus, we satisfy any provided memory_order.
00216   template <unsigned _Waiter_bit = 0x80000000>
00217   class __atomic_futex_unsigned
00218   {
00219     typedef chrono::system_clock __clock_t;
00220 
00221     unsigned _M_data;
00222     mutex _M_mutex;
00223     condition_variable _M_condvar;
00224 
00225   public:
00226     explicit
00227     __atomic_futex_unsigned(unsigned __data) : _M_data(__data)
00228     { }
00229 
00230     _GLIBCXX_ALWAYS_INLINE unsigned
00231     _M_load(memory_order __mo)
00232     {
00233       unique_lock<mutex> __lock(_M_mutex);
00234       return _M_data;
00235     }
00236 
00237     _GLIBCXX_ALWAYS_INLINE unsigned
00238     _M_load_when_not_equal(unsigned __val, memory_order __mo)
00239     {
00240       unique_lock<mutex> __lock(_M_mutex);
00241       while (_M_data == __val)
00242         _M_condvar.wait(__lock);
00243       return _M_data;
00244     }
00245 
00246     _GLIBCXX_ALWAYS_INLINE void
00247     _M_load_when_equal(unsigned __val, memory_order __mo)
00248     {
00249       unique_lock<mutex> __lock(_M_mutex);
00250       while (_M_data != __val)
00251         _M_condvar.wait(__lock);
00252     }
00253 
00254     template<typename _Rep, typename _Period>
00255       _GLIBCXX_ALWAYS_INLINE bool
00256       _M_load_when_equal_for(unsigned __val, memory_order __mo,
00257           const chrono::duration<_Rep, _Period>& __rtime)
00258       {
00259         unique_lock<mutex> __lock(_M_mutex);
00260         return _M_condvar.wait_for(__lock, __rtime,
00261                                    [&] { return _M_data == __val;});
00262       }
00263 
00264     template<typename _Clock, typename _Duration>
00265       _GLIBCXX_ALWAYS_INLINE bool
00266       _M_load_when_equal_until(unsigned __val, memory_order __mo,
00267           const chrono::time_point<_Clock, _Duration>& __atime)
00268       {
00269         unique_lock<mutex> __lock(_M_mutex);
00270         return _M_condvar.wait_until(__lock, __atime,
00271                                      [&] { return _M_data == __val;});
00272       }
00273 
00274     _GLIBCXX_ALWAYS_INLINE void
00275     _M_store_notify_all(unsigned __val, memory_order __mo)
00276     {
00277       unique_lock<mutex> __lock(_M_mutex);
00278       _M_data = __val;
00279       _M_condvar.notify_all();
00280     }
00281   };
00282 
00283 #endif // _GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1
00284 #endif // _GLIBCXX_HAS_GTHREADS && _GLIBCXX_USE_C99_STDINT_TR1
00285 
00286 _GLIBCXX_END_NAMESPACE_VERSION
00287 } // namespace std
00288 
00289 #endif