]>
Commit | Line | Data |
---|---|---|
ed19993b | 1 | /* pthread_cond_common -- shared code for condition variable. |
dff8da6b | 2 | Copyright (C) 2016-2024 Free Software Foundation, Inc. |
ed19993b TR |
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 | |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
ed19993b TR |
18 | |
19 | #include <atomic.h> | |
8bd336a0 | 20 | #include <atomic_wide_counter.h> |
ed19993b TR |
21 | #include <stdint.h> |
22 | #include <pthread.h> | |
ed19993b | 23 | |
8bd336a0 FW |
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). */ | |
ed19993b TR |
29 | #define __PTHREAD_COND_MAX_GROUP_SIZE ((unsigned) 1 << 29) |
30 | ||
8bd336a0 | 31 | static inline uint64_t |
ed19993b TR |
32 | __condvar_load_wseq_relaxed (pthread_cond_t *cond) |
33 | { | |
8bd336a0 | 34 | return __atomic_wide_counter_load_relaxed (&cond->__data.__wseq); |
ed19993b TR |
35 | } |
36 | ||
8bd336a0 | 37 | static inline uint64_t |
ed19993b TR |
38 | __condvar_fetch_add_wseq_acquire (pthread_cond_t *cond, unsigned int val) |
39 | { | |
8bd336a0 | 40 | return __atomic_wide_counter_fetch_add_acquire (&cond->__data.__wseq, val); |
ed19993b TR |
41 | } |
42 | ||
8bd336a0 | 43 | static inline uint64_t |
ed19993b TR |
44 | __condvar_load_g1_start_relaxed (pthread_cond_t *cond) |
45 | { | |
8bd336a0 | 46 | return __atomic_wide_counter_load_relaxed (&cond->__data.__g1_start); |
ed19993b TR |
47 | } |
48 | ||
8bd336a0 | 49 | static inline void |
ed19993b TR |
50 | __condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val) |
51 | { | |
8bd336a0 | 52 | __atomic_wide_counter_add_relaxed (&cond->__data.__g1_start, val); |
ed19993b TR |
53 | } |
54 | ||
8bd336a0 | 55 | #if __HAVE_64B_ATOMICS == 1 |
ed19993b | 56 | |
8bd336a0 FW |
57 | static 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 | } | |
ed19993b | 62 | |
8bd336a0 | 63 | #else /* !__HAVE_64B_ATOMICS */ |
ed19993b | 64 | |
8bd336a0 | 65 | /* The xor operation needs to be an atomic read-modify-write. The write |
ed19993b TR |
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 | |
8bd336a0 | 73 | derived. */ |
ed19993b TR |
74 | |
75 | static uint64_t __attribute__ ((unused)) | |
76 | __condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val) | |
77 | { | |
68007900 | 78 | /* First, get the current value. See __atomic_wide_counter_load_relaxed. */ |
ed19993b TR |
79 | unsigned int h, l, h2; |
80 | do | |
81 | { | |
8bd336a0 FW |
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); | |
ed19993b TR |
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). */ | |
8bd336a0 FW |
96 | unsigned int l2 |
97 | = (atomic_fetch_xor_release (&cond->__data.__wseq.__value32.__low, val) | |
98 | & ~((unsigned int) 1 << 31)); | |
ed19993b TR |
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 | ||
8bd336a0 | 106 | #endif /* !__HAVE_64B_ATOMICS */ |
ed19993b TR |
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. */ | |
113 | static 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. */ | |
148 | static 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. */ | |
158 | static 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. */ | |
165 | static 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. */ | |
183 | static 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. */ | |
200 | static 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 | |
7f0d9e61 | 233 | serves as an advance notification of the upcoming change to __g1_start; |
ed19993b TR |
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 | |
99ea93ca MK |
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; | |
ed19993b TR |
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 | } |