1// -*- C++ -*- header.
2
3// Copyright (C) 2015-2018 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