]>
Commit | Line | Data |
---|---|---|
5fc9ed4c | 1 | /* Bug 23844: Test for pthread_rwlock_tryrdlock stalls. |
d614a753 | 2 | Copyright (C) 2019-2020 Free Software Foundation, Inc. |
5fc9ed4c CD |
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/>. */ |
5fc9ed4c CD |
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 attemps 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 attemps 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 becuase 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 loosing 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> |