1 | /* Bug 23844: Test for pthread_rwlock_tryrdlock stalls. |
2 | Copyright (C) 2019-2024 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 | /* For a full analysis see comment: |
20 | https://sourceware.org/bugzilla/show_bug.cgi?id=23844#c14 |
21 | |
22 | Provided here for reference: |
23 | |
24 | --- Analysis of pthread_rwlock_tryrdlock() stall --- |
25 | A read lock begins to execute. |
26 | |
27 | In __pthread_rwlock_rdlock_full: |
28 | |
29 | We can attempt a read lock, but find that the lock is |
30 | in a write phase (PTHREAD_RWLOCK_WRPHASE, or WP-bit |
31 | is set), and the lock is held by a primary writer |
32 | (PTHREAD_RWLOCK_WRLOCKED is set). In this case we must |
33 | wait for explicit hand over from the writer to us or |
34 | one of the other waiters. The read lock threads are |
35 | about to execute: |
36 | |
37 | 341 r = (atomic_fetch_add_acquire (&rwlock->__data.__readers, |
38 | 342 (1 << PTHREAD_RWLOCK_READER_SHIFT)) |
39 | 343 + (1 << PTHREAD_RWLOCK_READER_SHIFT)); |
40 | |
41 | An unlock beings to execute. |
42 | |
43 | Then in __pthread_rwlock_wrunlock: |
44 | |
45 | 547 unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers); |
46 | ... |
47 | 549 while (!atomic_compare_exchange_weak_release |
48 | 550 (&rwlock->__data.__readers, &r, |
49 | 551 ((r ^ PTHREAD_RWLOCK_WRLOCKED) |
50 | 552 ^ ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0 ? 0 |
51 | 553 : PTHREAD_RWLOCK_WRPHASE)))) |
52 | 554 { |
53 | ... |
54 | 556 } |
55 | |
56 | We clear PTHREAD_RWLOCK_WRLOCKED, and if there are |
57 | no readers so we leave the lock in PTHRAD_RWLOCK_WRPHASE. |
58 | |
59 | Back in the read lock. |
60 | |
61 | The read lock adjusts __readres as above. |
62 | |
63 | 383 while ((r & PTHREAD_RWLOCK_WRPHASE) != 0 |
64 | 384 && (r & PTHREAD_RWLOCK_WRLOCKED) == 0) |
65 | 385 { |
66 | ... |
67 | 390 if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers, &r, |
68 | 391 r ^ PTHREAD_RWLOCK_WRPHASE)) |
69 | 392 { |
70 | |
71 | And then attempts to start the read phase. |
72 | |
73 | Assume there happens to be a tryrdlock at this point, noting |
74 | that PTHREAD_RWLOCK_WRLOCKED is clear, and PTHREAD_RWLOCK_WRPHASE |
75 | is 1. So the try lock attempts to start the read phase. |
76 | |
77 | In __pthread_rwlock_tryrdlock: |
78 | |
79 | 44 if ((r & PTHREAD_RWLOCK_WRPHASE) == 0) |
80 | 45 { |
81 | ... |
82 | 49 if (((r & PTHREAD_RWLOCK_WRLOCKED) != 0) |
83 | 50 && (rwlock->__data.__flags |
84 | 51 == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP)) |
85 | 52 return EBUSY; |
86 | 53 rnew = r + (1 << PTHREAD_RWLOCK_READER_SHIFT); |
87 | 54 } |
88 | ... |
89 | 89 while (!atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers, |
90 | 90 &r, rnew)); |
91 | |
92 | And succeeds. |
93 | |
94 | Back in the write unlock: |
95 | |
96 | 557 if ((r >> PTHREAD_RWLOCK_READER_SHIFT) != 0) |
97 | 558 { |
98 | ... |
99 | 563 if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 0) |
100 | 564 & PTHREAD_RWLOCK_FUTEX_USED) != 0) |
101 | 565 futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private); |
102 | 566 } |
103 | |
104 | We note that PTHREAD_RWLOCK_FUTEX_USED is non-zero |
105 | and don't wake anyone. This is OK because we handed |
106 | over to the trylock. It will be the trylock's responsibility |
107 | to wake any waiters. |
108 | |
109 | Back in the read lock: |
110 | |
111 | The read lock fails to install PTHRAD_REWLOCK_WRPHASE as 0 because |
112 | the __readers value was adjusted by the trylock, and so it falls through |
113 | to waiting on the lock for explicit handover from either a new writer |
114 | or a new reader. |
115 | |
116 | 448 int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex, |
117 | 449 1 | PTHREAD_RWLOCK_FUTEX_USED, |
118 | 450 abstime, private); |
119 | |
120 | We use PTHREAD_RWLOCK_FUTEX_USED to indicate the futex |
121 | is in use. |
122 | |
123 | At this point we have readers waiting on the read lock |
124 | to unlock. The wrlock is done. The trylock is finishing |
125 | the installation of the read phase. |
126 | |
127 | 92 if ((r & PTHREAD_RWLOCK_WRPHASE) != 0) |
128 | 93 { |
129 | ... |
130 | 105 atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 0); |
131 | 106 } |
132 | |
133 | The trylock does note that we were the one that |
134 | installed the read phase, but the comments are not |
135 | correct, the execution ordering above shows that |
136 | readers might indeed be waiting, and they are. |
137 | |
138 | The atomic_store_relaxed throws away PTHREAD_RWLOCK_FUTEX_USED, |
139 | and the waiting reader is never worken because as noted |
140 | above it is conditional on the futex being used. |
141 | |
142 | The solution is for the trylock thread to inspect |
143 | PTHREAD_RWLOCK_FUTEX_USED and wake the waiting readers. |
144 | |
145 | --- Analysis of pthread_rwlock_trywrlock() stall --- |
146 | |
147 | A write lock begins to execute, takes the write lock, |
148 | and then releases the lock... |
149 | |
150 | In pthread_rwlock_wrunlock(): |
151 | |
152 | 547 unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers); |
153 | ... |
154 | 549 while (!atomic_compare_exchange_weak_release |
155 | 550 (&rwlock->__data.__readers, &r, |
156 | 551 ((r ^ PTHREAD_RWLOCK_WRLOCKED) |
157 | 552 ^ ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0 ? 0 |
158 | 553 : PTHREAD_RWLOCK_WRPHASE)))) |
159 | 554 { |
160 | ... |
161 | 556 } |
162 | |
163 | ... leaving it in the write phase with zero readers |
164 | (the case where we leave the write phase in place |
165 | during a write unlock). |
166 | |
167 | A write trylock begins to execute. |
168 | |
169 | In __pthread_rwlock_trywrlock: |
170 | |
171 | 40 while (((r & PTHREAD_RWLOCK_WRLOCKED) == 0) |
172 | 41 && (((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0) |
173 | 42 || (prefer_writer && ((r & PTHREAD_RWLOCK_WRPHASE) != 0)))) |
174 | 43 { |
175 | |
176 | The lock is not locked. |
177 | |
178 | There are no readers. |
179 | |
180 | 45 if (atomic_compare_exchange_weak_acquire ( |
181 | 46 &rwlock->__data.__readers, &r, |
182 | 47 r | PTHREAD_RWLOCK_WRPHASE | PTHREAD_RWLOCK_WRLOCKED)) |
183 | |
184 | We atomically install the write phase and we take the |
185 | exclusive write lock. |
186 | |
187 | 48 { |
188 | 49 atomic_store_relaxed (&rwlock->__data.__writers_futex, 1); |
189 | |
190 | We get this far. |
191 | |
192 | A reader lock begins to execute. |
193 | |
194 | In pthread_rwlock_rdlock: |
195 | |
196 | 437 for (;;) |
197 | 438 { |
198 | 439 while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex)) |
199 | 440 | PTHREAD_RWLOCK_FUTEX_USED) == (1 | PTHREAD_RWLOCK_FUTEX_USED)) |
200 | 441 { |
201 | 442 int private = __pthread_rwlock_get_private (rwlock); |
202 | 443 if (((wpf & PTHREAD_RWLOCK_FUTEX_USED) == 0) |
203 | 444 && (!atomic_compare_exchange_weak_relaxed |
204 | 445 (&rwlock->__data.__wrphase_futex, |
205 | 446 &wpf, wpf | PTHREAD_RWLOCK_FUTEX_USED))) |
206 | 447 continue; |
207 | 448 int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex, |
208 | 449 1 | PTHREAD_RWLOCK_FUTEX_USED, |
209 | 450 abstime, private); |
210 | |
211 | We are in a write phase, so the while() on line 439 is true. |
212 | |
213 | The value of wpf does not have PTHREAD_RWLOCK_FUTEX_USED set |
214 | since this is the first reader to lock. |
215 | |
216 | The atomic operation sets wpf with PTHREAD_RELOCK_FUTEX_USED |
217 | on the expectation that this reader will be woken during |
218 | the handoff. |
219 | |
220 | Back in pthread_rwlock_trywrlock: |
221 | |
222 | 50 atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1); |
223 | 51 atomic_store_relaxed (&rwlock->__data.__cur_writer, |
224 | 52 THREAD_GETMEM (THREAD_SELF, tid)); |
225 | 53 return 0; |
226 | 54 } |
227 | ... |
228 | 57 } |
229 | |
230 | We write 1 to __wrphase_futex discarding PTHREAD_RWLOCK_FUTEX_USED, |
231 | and so in the unlock we will not awaken the waiting reader. |
232 | |
233 | The solution to this is to realize that if we did not start the write |
234 | phase we need not write 1 or any other value to __wrphase_futex. |
235 | This ensures that any readers (which saw __wrphase_futex != 0) can |
236 | set PTHREAD_RWLOCK_FUTEX_USED and this can be used at unlock to |
237 | wake them. |
238 | |
239 | If we installed the write phase then all other readers are looping |
240 | here: |
241 | |
242 | In __pthread_rwlock_rdlock_full: |
243 | |
244 | 437 for (;;) |
245 | 438 { |
246 | 439 while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex)) |
247 | 440 | PTHREAD_RWLOCK_FUTEX_USED) == (1 | PTHREAD_RWLOCK_FUTEX_USED)) |
248 | 441 { |
249 | ... |
250 | 508 } |
251 | |
252 | waiting for the write phase to be installed or removed before they |
253 | can begin waiting on __wrphase_futex (part of the algorithm), or |
254 | taking a concurrent read lock, and thus we can safely write 1 to |
255 | __wrphase_futex. |
256 | |
257 | If we did not install the write phase then the readers may already |
258 | be waiting on the futex, the original writer wrote 1 to __wrphase_futex |
259 | as part of starting the write phase, and we cannot also write 1 |
260 | without losing the PTHREAD_RWLOCK_FUTEX_USED bit. |
261 | |
262 | --- |
263 | |
264 | Summary for the pthread_rwlock_tryrdlock() stall: |
265 | |
266 | The stall is caused by pthread_rwlock_tryrdlock failing to check |
267 | that PTHREAD_RWLOCK_FUTEX_USED is set in the __wrphase_futex futex |
268 | and then waking the futex. |
269 | |
270 | The fix for bug 23844 ensures that waiters on __wrphase_futex are |
271 | correctly woken. Before the fix the test stalls as readers can |
272 | wait forever on __wrphase_futex. */ |
273 | |
274 | #include <stdio.h> |
275 | #include <stdlib.h> |
276 | #include <unistd.h> |
277 | #include <pthread.h> |
278 | #include <support/xthread.h> |
279 | #include <errno.h> |
280 | |
281 | /* We need only one lock to reproduce the issue. We will need multiple |
282 | threads to get the exact case where we have a read, try, and unlock |
283 | all interleaving to produce the case where the readers are waiting |
284 | and the try fails to wake them. */ |
285 | pthread_rwlock_t onelock; |
286 | |
287 | /* The number of threads is arbitrary but empirically chosen to have |
288 | enough threads that we see the condition where waiting readers are |
289 | not woken by a successful tryrdlock. */ |
290 | #define NTHREADS 32 |
291 | |
292 | _Atomic int do_exit; |
293 | |
294 | void * |
295 | run_loop (void *arg) |
296 | { |
297 | int i = 0, ret; |
298 | while (!do_exit) |
299 | { |
300 | /* Arbitrarily choose if we are the writer or reader. Choose a |
301 | high enough ratio of readers to writers to make it likely |
302 | that readers block (and eventually are susceptable to |
303 | stalling). |
304 | |
305 | If we are a writer, take the write lock, and then unlock. |
306 | If we are a reader, try the lock, then lock, then unlock. */ |
307 | if ((i % 8) != 0) |
308 | xpthread_rwlock_wrlock (rwlock: &onelock); |
309 | else |
310 | { |
311 | if ((ret = pthread_rwlock_tryrdlock (rwlock: &onelock)) != 0) |
312 | { |
313 | if (ret == EBUSY) |
314 | xpthread_rwlock_rdlock (rwlock: &onelock); |
315 | else |
316 | exit (EXIT_FAILURE); |
317 | } |
318 | } |
319 | /* Thread does some work and then unlocks. */ |
320 | xpthread_rwlock_unlock (rwlock: &onelock); |
321 | i++; |
322 | } |
323 | return NULL; |
324 | } |
325 | |
326 | int |
327 | do_test (void) |
328 | { |
329 | int i; |
330 | pthread_t tids[NTHREADS]; |
331 | xpthread_rwlock_init (rwlock: &onelock, NULL); |
332 | for (i = 0; i < NTHREADS; i++) |
333 | tids[i] = xpthread_create (NULL, thread_func: run_loop, NULL); |
334 | /* Run for some amount of time. Empirically speaking exercising |
335 | the stall via pthread_rwlock_tryrdlock is much harder, and on |
336 | a 3.5GHz 4 core x86_64 VM system it takes somewhere around |
337 | 20-200s to stall, approaching 100% stall past 200s. We can't |
338 | wait that long for a regression test so we just test for 20s, |
339 | and expect the stall to happen with a 5-10% chance (enough for |
340 | developers to see). */ |
341 | sleep (seconds: 20); |
342 | /* Then exit. */ |
343 | printf (format: "INFO: Exiting...\n" ); |
344 | do_exit = 1; |
345 | /* If any readers stalled then we will timeout waiting for them. */ |
346 | for (i = 0; i < NTHREADS; i++) |
347 | xpthread_join (thr: tids[i]); |
348 | printf (format: "INFO: Done.\n" ); |
349 | xpthread_rwlock_destroy (rwlock: &onelock); |
350 | printf (format: "PASS: No pthread_rwlock_tryrdlock stalls detected.\n" ); |
351 | return 0; |
352 | } |
353 | |
354 | #define TIMEOUT 30 |
355 | #include <support/test-driver.c> |
356 | |