Clang Project

include/c++/7/bits/atomic_futex.h
1// -*- C++ -*- header.
2
3// Copyright (C) 2015-2017 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_futex.h
26 *  This is an internal header file, included by other library headers.
27 *  Do not attempt to use it directly.
28 */
29
30#ifndef _GLIBCXX_ATOMIC_FUTEX_H
31#define _GLIBCXX_ATOMIC_FUTEX_H 1
32
33#pragma GCC system_header
34
35#include <bits/c++config.h>
36#include <atomic>
37#include <chrono>
38#if ! (defined(_GLIBCXX_HAVE_LINUX_FUTEX) && ATOMIC_INT_LOCK_FREE > 1)
39#include <mutex>
40#include <condition_variable>
41#endif
42
43#ifndef _GLIBCXX_ALWAYS_INLINE
44#define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__))
45#endif
46
47namespace std _GLIBCXX_VISIBILITY(default)
48{
49_GLIBCXX_BEGIN_NAMESPACE_VERSION
50
51#if defined(_GLIBCXX_HAS_GTHREADS) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
52#if defined(_GLIBCXX_HAVE_LINUX_FUTEX) && ATOMIC_INT_LOCK_FREE > 1
53  struct __atomic_futex_unsigned_base
54  {
55    // Returns false iff a timeout occurred.
56    bool
57    _M_futex_wait_until(unsigned *__addr, unsigned __val, bool __has_timeout,
58 chrono::seconds __s, chrono::nanoseconds __ns);
59
60    // This can be executed after the object has been destroyed.
61    static void _M_futex_notify_all(unsigned* __addr);
62  };
63
64  template <unsigned _Waiter_bit = 0x80000000>
65  class __atomic_futex_unsigned : __atomic_futex_unsigned_base
66  {
67    typedef chrono::system_clock __clock_t;
68
69    // This must be lock-free and at offset 0.
70    atomic<unsigned> _M_data;
71
72  public:
73    explicit
74    __atomic_futex_unsigned(unsigned __data) : _M_data(__data)
75    { }
76
77    _GLIBCXX_ALWAYS_INLINE unsigned
78    _M_load(memory_order __mo)
79    {
80      return _M_data.load(__mo) & ~_Waiter_bit;
81    }
82
83  private:
84    // If a timeout occurs, returns a current value after the timeout;
85    // otherwise, returns the operand's value if equal is true or a different
86    // value if equal is false.
87    // The assumed value is the caller's assumption about the current value
88    // when making the call.
89    unsigned
90    _M_load_and_test_until(unsigned __assumed, unsigned __operand,
91 bool __equal, memory_order __mo, bool __has_timeout,
92 chrono::seconds __s, chrono::nanoseconds __ns)
93    {
94      for (;;)
95 {
96   // Don't bother checking the value again because we expect the caller
97   // to have done it recently.
98   // memory_order_relaxed is sufficient because we can rely on just the
99   // modification order (store_notify uses an atomic RMW operation too),
100   // and the futex syscalls synchronize between themselves.
101   _M_data.fetch_or(_Waiter_bit, memory_order_relaxed);
102   bool __ret = _M_futex_wait_until((unsigned*)(void*)&_M_data,
103    __assumed | _Waiter_bit,
104    __has_timeout, __s, __ns);
105   // Fetch the current value after waiting (clears _Waiter_bit).
106   __assumed = _M_load(__mo);
107   if (!__ret || ((__operand == __assumed) == __equal))
108     return __assumed;
109   // TODO adapt wait time
110 }
111    }
112
113    // Returns the operand's value if equal is true or a different value if
114    // equal is false.
115    // The assumed value is the caller's assumption about the current value
116    // when making the call.
117    unsigned
118    _M_load_and_test(unsigned __assumed, unsigned __operand,
119 bool __equal, memory_order __mo)
120    {
121      return _M_load_and_test_until(__assumed, __operand, __equal, __mo,
122     false, {}, {});
123    }
124
125    // If a timeout occurs, returns a current value after the timeout;
126    // otherwise, returns the operand's value if equal is true or a different
127    // value if equal is false.
128    // The assumed value is the caller's assumption about the current value
129    // when making the call.
130    template<typename _Dur>
131    unsigned
132    _M_load_and_test_until_impl(unsigned __assumed, unsigned __operand,
133 bool __equal, memory_order __mo,
134 const chrono::time_point<__clock_t, _Dur>& __atime)
135    {
136      auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
137      auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
138      // XXX correct?
139      return _M_load_and_test_until(__assumed, __operand, __equal, __mo,
140   true, __s.time_since_epoch(), __ns);
141    }
142
143  public:
144
145    _GLIBCXX_ALWAYS_INLINE unsigned
146    _M_load_when_not_equal(unsigned __val, memory_order __mo)
147    {
148      unsigned __i = _M_load(__mo);
149      if ((__i & ~_Waiter_bit) != __val)
150 return (__i & ~_Waiter_bit);
151      // TODO Spin-wait first.
152      return _M_load_and_test(__i, __val, false, __mo);
153    }
154
155    _GLIBCXX_ALWAYS_INLINE void
156    _M_load_when_equal(unsigned __val, memory_order __mo)
157    {
158      unsigned __i = _M_load(__mo);
159      if ((__i & ~_Waiter_bit) == __val)
160 return;
161      // TODO Spin-wait first.
162      _M_load_and_test(__i, __val, true, __mo);
163    }
164
165    // Returns false iff a timeout occurred.
166    template<typename _Rep, typename _Period>
167      _GLIBCXX_ALWAYS_INLINE bool
168      _M_load_when_equal_for(unsigned __val, memory_order __mo,
169   const chrono::duration<_Rep, _Period>& __rtime)
170      {
171 return _M_load_when_equal_until(__val, __mo,
172 __clock_t::now() + __rtime);
173      }
174
175    // Returns false iff a timeout occurred.
176    template<typename _Clock, typename _Duration>
177      _GLIBCXX_ALWAYS_INLINE bool
178      _M_load_when_equal_until(unsigned __val, memory_order __mo,
179   const chrono::time_point<_Clock, _Duration>& __atime)
180      {
181 // DR 887 - Sync unknown clock to known clock.
182 const typename _Clock::time_point __c_entry = _Clock::now();
183 const __clock_t::time_point __s_entry = __clock_t::now();
184 const auto __delta = __atime - __c_entry;
185 const auto __s_atime = __s_entry + __delta;
186 return _M_load_when_equal_until(__val, __mo, __s_atime);
187      }
188
189    // Returns false iff a timeout occurred.
190    template<typename _Duration>
191    _GLIBCXX_ALWAYS_INLINE bool
192    _M_load_when_equal_until(unsigned __val, memory_order __mo,
193 const chrono::time_point<__clock_t, _Duration>& __atime)
194    {
195      unsigned __i = _M_load(__mo);
196      if ((__i & ~_Waiter_bit) == __val)
197 return true;
198      // TODO Spin-wait first.  Ignore effect on timeout.
199      __i = _M_load_and_test_until_impl(__i, __val, true, __mo, __atime);
200      return (__i & ~_Waiter_bit) == __val;
201    }
202
203    _GLIBCXX_ALWAYS_INLINE void
204    _M_store_notify_all(unsigned __val, memory_order __mo)
205    {
206      unsigned* __futex = (unsigned *)(void *)&_M_data;
207      if (_M_data.exchange(__val, __mo) & _Waiter_bit)
208 _M_futex_notify_all(__futex);
209    }
210  };
211
212#else // ! (_GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1)
213
214  // If futexes are not available, use a mutex and a condvar to wait.
215  // Because we access the data only within critical sections, all accesses
216  // are sequentially consistent; thus, we satisfy any provided memory_order.
217  template <unsigned _Waiter_bit = 0x80000000>
218  class __atomic_futex_unsigned
219  {
220    typedef chrono::system_clock __clock_t;
221
222    unsigned _M_data;
223    mutex _M_mutex;
224    condition_variable _M_condvar;
225
226  public:
227    explicit
228    __atomic_futex_unsigned(unsigned __data) : _M_data(__data)
229    { }
230
231    _GLIBCXX_ALWAYS_INLINE unsigned
232    _M_load(memory_order __mo)
233    {
234      unique_lock<mutex> __lock(_M_mutex);
235      return _M_data;
236    }
237
238    _GLIBCXX_ALWAYS_INLINE unsigned
239    _M_load_when_not_equal(unsigned __val, memory_order __mo)
240    {
241      unique_lock<mutex> __lock(_M_mutex);
242      while (_M_data == __val)
243 _M_condvar.wait(__lock);
244      return _M_data;
245    }
246
247    _GLIBCXX_ALWAYS_INLINE void
248    _M_load_when_equal(unsigned __val, memory_order __mo)
249    {
250      unique_lock<mutex> __lock(_M_mutex);
251      while (_M_data != __val)
252 _M_condvar.wait(__lock);
253    }
254
255    template<typename _Rep, typename _Period>
256      _GLIBCXX_ALWAYS_INLINE bool
257      _M_load_when_equal_for(unsigned __val, memory_order __mo,
258   const chrono::duration<_Rep, _Period>& __rtime)
259      {
260 unique_lock<mutex> __lock(_M_mutex);
261 return _M_condvar.wait_for(__lock, __rtime,
262    [&] { return _M_data == __val;});
263      }
264
265    template<typename _Clock, typename _Duration>
266      _GLIBCXX_ALWAYS_INLINE bool
267      _M_load_when_equal_until(unsigned __val, memory_order __mo,
268   const chrono::time_point<_Clock, _Duration>& __atime)
269      {
270 unique_lock<mutex> __lock(_M_mutex);
271 return _M_condvar.wait_until(__lock, __atime,
272      [&] { return _M_data == __val;});
273      }
274
275    _GLIBCXX_ALWAYS_INLINE void
276    _M_store_notify_all(unsigned __val, memory_order __mo)
277    {
278      unique_lock<mutex> __lock(_M_mutex);
279      _M_data = __val;
280      _M_condvar.notify_all();
281    }
282  };
283
284#endif // _GLIBCXX_HAVE_LINUX_FUTEX && ATOMIC_INT_LOCK_FREE > 1
285#endif // _GLIBCXX_HAS_GTHREADS && _GLIBCXX_USE_C99_STDINT_TR1
286
287_GLIBCXX_END_NAMESPACE_VERSION
288} // namespace std
289
290#endif
291
std::__atomic_futex_unsigned_base::_M_futex_wait_until
std::__atomic_futex_unsigned_base::_M_futex_notify_all
std::__atomic_futex_unsigned::_M_data
std::__atomic_futex_unsigned::_M_load
std::__atomic_futex_unsigned::_M_load_and_test_until
std::__atomic_futex_unsigned::_M_load_and_test
std::__atomic_futex_unsigned::_M_load_and_test_until_impl
std::__atomic_futex_unsigned::_M_load_when_not_equal
std::__atomic_futex_unsigned::_M_load_when_equal
std::__atomic_futex_unsigned::_M_load_when_equal_for
std::__atomic_futex_unsigned::_M_load_when_equal_until
std::__atomic_futex_unsigned::_M_load_when_equal_until
std::__atomic_futex_unsigned::_M_store_notify_all
CodeThinker, Enjoy your reading code