1/* pthread_cond_common -- shared code for condition variable.
2 Copyright (C) 2016-2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19#include <atomic.h>
20#include <atomic_wide_counter.h>
21#include <stdint.h>
22#include <pthread.h>
23
24/* We need 3 least-significant bits on __wrefs for something else.
25 This also matches __atomic_wide_counter requirements: The highest
26 value we add is __PTHREAD_COND_MAX_GROUP_SIZE << 2 to __g1_start
27 (the two extra bits are for the lock in the two LSBs of
28 __g1_start). */
29#define __PTHREAD_COND_MAX_GROUP_SIZE ((unsigned) 1 << 29)
30
31static inline uint64_t
32__condvar_load_wseq_relaxed (pthread_cond_t *cond)
33{
34 return __atomic_wide_counter_load_relaxed (&cond->__data.__wseq);
35}
36
37static inline uint64_t
38__condvar_fetch_add_wseq_acquire (pthread_cond_t *cond, unsigned int val)
39{
40 return __atomic_wide_counter_fetch_add_acquire (&cond->__data.__wseq, val);
41}
42
43static inline uint64_t
44__condvar_load_g1_start_relaxed (pthread_cond_t *cond)
45{
46 return __atomic_wide_counter_load_relaxed (&cond->__data.__g1_start);
47}
48
49static inline void
50__condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val)
51{
52 __atomic_wide_counter_add_relaxed (&cond->__data.__g1_start, val);
53}
54
55#if __HAVE_64B_ATOMICS == 1
56
57static inline uint64_t
58__condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val)
59{
60 return atomic_fetch_xor_release (&cond->__data.__wseq.__value64, val);
61}
62
63#else /* !__HAVE_64B_ATOMICS */
64
65/* The xor operation needs to be an atomic read-modify-write. The write
66 itself is not an issue as it affects just the lower-order half but not bits
67 used in the add operation. To make the full fetch-and-xor atomic, we
68 exploit that concurrently, the value can increase by at most 1<<31 (*): The
69 xor operation is only called while having acquired the lock, so not more
70 than __PTHREAD_COND_MAX_GROUP_SIZE waiters can enter concurrently and thus
71 increment __wseq. Therefore, if the xor operation observes a value of
72 __wseq, then the value it applies the modification to later on can be
73 derived. */
74
75static uint64_t __attribute__ ((unused))
76__condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val)
77{
78 /* First, get the current value. See __atomic_wide_counter_load_relaxed. */
79 unsigned int h, l, h2;
80 do
81 {
82 h = atomic_load_acquire (&cond->__data.__wseq.__value32.__high);
83 l = atomic_load_acquire (&cond->__data.__wseq.__value32.__low);
84 h2 = atomic_load_relaxed (&cond->__data.__wseq.__value32.__high);
85 }
86 while (h != h2);
87 if (((l >> 31) > 0) && ((h >> 31) == 0))
88 h++;
89 h &= ~((unsigned int) 1 << 31);
90 l &= ~((unsigned int) 1 << 31);
91
92 /* Now modify. Due to the coherence rules, the prior load will read a value
93 earlier in modification order than the following fetch-xor.
94 This uses release MO to make the full operation have release semantics
95 (all other operations access the lower-order half). */
96 unsigned int l2
97 = (atomic_fetch_xor_release (&cond->__data.__wseq.__value32.__low, val)
98 & ~((unsigned int) 1 << 31));
99 if (l2 < l)
100 /* The lower-order half overflowed in the meantime. This happened exactly
101 once due to the limit on concurrent waiters (see above). */
102 h++;
103 return ((uint64_t) h << 31) + l2;
104}
105
106#endif /* !__HAVE_64B_ATOMICS */
107
108/* The lock that signalers use. See pthread_cond_wait_common for uses.
109 The lock is our normal three-state lock: not acquired (0) / acquired (1) /
110 acquired-with-futex_wake-request (2). However, we need to preserve the
111 other bits in the unsigned int used for the lock, and therefore it is a
112 little more complex. */
113static void __attribute__ ((unused))
114__condvar_acquire_lock (pthread_cond_t *cond, int private)
115{
116 unsigned int s = atomic_load_relaxed (&cond->__data.__g1_orig_size);
117 while ((s & 3) == 0)
118 {
119 if (atomic_compare_exchange_weak_acquire (&cond->__data.__g1_orig_size,
120 &s, s | 1))
121 return;
122 /* TODO Spinning and back-off. */
123 }
124 /* We can't change from not acquired to acquired, so try to change to
125 acquired-with-futex-wake-request and do a futex wait if we cannot change
126 from not acquired. */
127 while (1)
128 {
129 while ((s & 3) != 2)
130 {
131 if (atomic_compare_exchange_weak_acquire
132 (&cond->__data.__g1_orig_size, &s, (s & ~(unsigned int) 3) | 2))
133 {
134 if ((s & 3) == 0)
135 return;
136 break;
137 }
138 /* TODO Back off. */
139 }
140 futex_wait_simple (&cond->__data.__g1_orig_size,
141 (s & ~(unsigned int) 3) | 2, private);
142 /* Reload so we see a recent value. */
143 s = atomic_load_relaxed (&cond->__data.__g1_orig_size);
144 }
145}
146
147/* See __condvar_acquire_lock. */
148static void __attribute__ ((unused))
149__condvar_release_lock (pthread_cond_t *cond, int private)
150{
151 if ((atomic_fetch_and_release (&cond->__data.__g1_orig_size,
152 ~(unsigned int) 3) & 3)
153 == 2)
154 futex_wake (&cond->__data.__g1_orig_size, 1, private);
155}
156
157/* Only use this when having acquired the lock. */
158static unsigned int __attribute__ ((unused))
159__condvar_get_orig_size (pthread_cond_t *cond)
160{
161 return atomic_load_relaxed (&cond->__data.__g1_orig_size) >> 2;
162}
163
164/* Only use this when having acquired the lock. */
165static void __attribute__ ((unused))
166__condvar_set_orig_size (pthread_cond_t *cond, unsigned int size)
167{
168 /* We have acquired the lock, but might get one concurrent update due to a
169 lock state change from acquired to acquired-with-futex_wake-request.
170 The store with relaxed MO is fine because there will be no further
171 changes to the lock bits nor the size, and we will subsequently release
172 the lock with release MO. */
173 unsigned int s;
174 s = (atomic_load_relaxed (&cond->__data.__g1_orig_size) & 3)
175 | (size << 2);
176 if ((atomic_exchange_relaxed (&cond->__data.__g1_orig_size, s) & 3)
177 != (s & 3))
178 atomic_store_relaxed (&cond->__data.__g1_orig_size, (size << 2) | 2);
179}
180
181/* Returns FUTEX_SHARED or FUTEX_PRIVATE based on the provided __wrefs
182 value. */
183static int __attribute__ ((unused))
184__condvar_get_private (int flags)
185{
186 if ((flags & __PTHREAD_COND_SHARED_MASK) == 0)
187 return FUTEX_PRIVATE;
188 else
189 return FUTEX_SHARED;
190}
191
192/* This closes G1 (whose index is in G1INDEX), waits for all futex waiters to
193 leave G1, converts G1 into a fresh G2, and then switches group roles so that
194 the former G2 becomes the new G1 ending at the current __wseq value when we
195 eventually make the switch (WSEQ is just an observation of __wseq by the
196 signaler).
197 If G2 is empty, it will not switch groups because then it would create an
198 empty G1 which would require switching groups again on the next signal.
199 Returns false iff groups were not switched because G2 was empty. */
200static bool __attribute__ ((unused))
201__condvar_quiesce_and_switch_g1 (pthread_cond_t *cond, uint64_t wseq,
202 unsigned int *g1index, int private)
203{
204 const unsigned int maxspin = 0;
205 unsigned int g1 = *g1index;
206
207 /* If there is no waiter in G2, we don't do anything. The expression may
208 look odd but remember that __g_size might hold a negative value, so
209 putting the expression this way avoids relying on implementation-defined
210 behavior.
211 Note that this works correctly for a zero-initialized condvar too. */
212 unsigned int old_orig_size = __condvar_get_orig_size (cond);
213 uint64_t old_g1_start = __condvar_load_g1_start_relaxed (cond) >> 1;
214 if (((unsigned) (wseq - old_g1_start - old_orig_size)
215 + cond->__data.__g_size[g1 ^ 1]) == 0)
216 return false;
217
218 /* Now try to close and quiesce G1. We have to consider the following kinds
219 of waiters:
220 * Waiters from less recent groups than G1 are not affected because
221 nothing will change for them apart from __g1_start getting larger.
222 * New waiters arriving concurrently with the group switching will all go
223 into G2 until we atomically make the switch. Waiters existing in G2
224 are not affected.
225 * Waiters in G1 will be closed out immediately by setting a flag in
226 __g_signals, which will prevent waiters from blocking using a futex on
227 __g_signals and also notifies them that the group is closed. As a
228 result, they will eventually remove their group reference, allowing us
229 to close switch group roles. */
230
231 /* First, set the closed flag on __g_signals. This tells waiters that are
232 about to wait that they shouldn't do that anymore. This basically
233 serves as an advance notificaton of the upcoming change to __g1_start;
234 waiters interpret it as if __g1_start was larger than their waiter
235 sequence position. This allows us to change __g1_start after waiting
236 for all existing waiters with group references to leave, which in turn
237 makes recovery after stealing a signal simpler because it then can be
238 skipped if __g1_start indicates that the group is closed (otherwise,
239 we would have to recover always because waiters don't know how big their
240 groups are). Relaxed MO is fine. */
241 atomic_fetch_or_relaxed (cond->__data.__g_signals + g1, 1);
242
243 /* Wait until there are no group references anymore. The fetch-or operation
244 injects us into the modification order of __g_refs; release MO ensures
245 that waiters incrementing __g_refs after our fetch-or see the previous
246 changes to __g_signals and to __g1_start that had to happen before we can
247 switch this G1 and alias with an older group (we have two groups, so
248 aliasing requires switching group roles twice). Note that nobody else
249 can have set the wake-request flag, so we do not have to act upon it.
250
251 Also note that it is harmless if older waiters or waiters from this G1
252 get a group reference after we have quiesced the group because it will
253 remain closed for them either because of the closed flag in __g_signals
254 or the later update to __g1_start. New waiters will never arrive here
255 but instead continue to go into the still current G2. */
256 unsigned r = atomic_fetch_or_release (cond->__data.__g_refs + g1, 0);
257 while ((r >> 1) > 0)
258 {
259 for (unsigned int spin = maxspin; ((r >> 1) > 0) && (spin > 0); spin--)
260 {
261 /* TODO Back off. */
262 r = atomic_load_relaxed (cond->__data.__g_refs + g1);
263 }
264 if ((r >> 1) > 0)
265 {
266 /* There is still a waiter after spinning. Set the wake-request
267 flag and block. Relaxed MO is fine because this is just about
268 this futex word.
269
270 Update r to include the set wake-request flag so that the upcoming
271 futex_wait only blocks if the flag is still set (otherwise, we'd
272 violate the basic client-side futex protocol). */
273 r = atomic_fetch_or_relaxed (cond->__data.__g_refs + g1, 1) | 1;
274
275 if ((r >> 1) > 0)
276 futex_wait_simple (cond->__data.__g_refs + g1, r, private);
277 /* Reload here so we eventually see the most recent value even if we
278 do not spin. */
279 r = atomic_load_relaxed (cond->__data.__g_refs + g1);
280 }
281 }
282 /* Acquire MO so that we synchronize with the release operation that waiters
283 use to decrement __g_refs and thus happen after the waiters we waited
284 for. */
285 atomic_thread_fence_acquire ();
286
287 /* Update __g1_start, which finishes closing this group. The value we add
288 will never be negative because old_orig_size can only be zero when we
289 switch groups the first time after a condvar was initialized, in which
290 case G1 will be at index 1 and we will add a value of 1. See above for
291 why this takes place after waiting for quiescence of the group.
292 Relaxed MO is fine because the change comes with no additional
293 constraints that others would have to observe. */
294 __condvar_add_g1_start_relaxed (cond,
295 (old_orig_size << 1) + (g1 == 1 ? 1 : - 1));
296
297 /* Now reopen the group, thus enabling waiters to again block using the
298 futex controlled by __g_signals. Release MO so that observers that see
299 no signals (and thus can block) also see the write __g1_start and thus
300 that this is now a new group (see __pthread_cond_wait_common for the
301 matching acquire MO loads). */
302 atomic_store_release (cond->__data.__g_signals + g1, 0);
303
304 /* At this point, the old G1 is now a valid new G2 (but not in use yet).
305 No old waiter can neither grab a signal nor acquire a reference without
306 noticing that __g1_start is larger.
307 We can now publish the group switch by flipping the G2 index in __wseq.
308 Release MO so that this synchronizes with the acquire MO operation
309 waiters use to obtain a position in the waiter sequence. */
310 wseq = __condvar_fetch_xor_wseq_release (cond, 1) >> 1;
311 g1 ^= 1;
312 *g1index ^= 1;
313
314 /* These values are just observed by signalers, and thus protected by the
315 lock. */
316 unsigned int orig_size = wseq - (old_g1_start + old_orig_size);
317 __condvar_set_orig_size (cond, orig_size);
318 /* Use and addition to not loose track of cancellations in what was
319 previously G2. */
320 cond->__data.__g_size[g1] += orig_size;
321
322 /* The new G1's size may be zero because of cancellations during its time
323 as G2. If this happens, there are no waiters that have to receive a
324 signal, so we do not need to add any and return false. */
325 if (cond->__data.__g_size[g1] == 0)
326 return false;
327
328 return true;
329}
330