1 /* Bug 23844: Test for pthread_rwlock_tryrdlock stalls.
2 Copyright (C) 2019-2023 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 (&onelock);
309 else
310 {
311 if ((ret = pthread_rwlock_tryrdlock (&onelock)) != 0)
312 {
313 if (ret == EBUSY)
314 xpthread_rwlock_rdlock (&onelock);
315 else
316 exit (EXIT_FAILURE);
317 }
318 }
319 /* Thread does some work and then unlocks. */
320 xpthread_rwlock_unlock (&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 (&onelock, NULL);
332 for (i = 0; i < NTHREADS; i++)
333 tids[i] = xpthread_create (NULL, 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 (20);
342 /* Then exit. */
343 printf ("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 (tids[i]);
348 printf ("INFO: Done.\n");
349 xpthread_rwlock_destroy (&onelock);
350 printf ("PASS: No pthread_rwlock_tryrdlock stalls detected.\n");
351 return 0;
352 }
353
354 #define TIMEOUT 30
355 #include <support/test-driver.c>