1/* POSIX reader--writer lock: core parts.
2 Copyright (C) 2016-2017 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 <http://www.gnu.org/licenses/>. */
18
19#include <errno.h>
20#include <sysdep.h>
21#include <pthread.h>
22#include <pthreadP.h>
23#include <sys/time.h>
24#include <stap-probe.h>
25#include <atomic.h>
26#include <futex-internal.h>
27
28
29/* A reader--writer lock that fulfills the POSIX requirements (but operations
30 on this lock are not necessarily full barriers, as one may interpret the
31 POSIX requirement about "synchronizing memory"). All critical sections are
32 in a total order, writers synchronize with prior writers and readers, and
33 readers synchronize with prior writers.
34
35 A thread is allowed to acquire a read lock recursively (i.e., have rdlock
36 critical sections that overlap in sequenced-before) unless the kind of the
37 rwlock is set to PTHREAD_RWLOCK_PREFER_WRITERS_NONRECURSIVE_NP.
38
39 This lock is built so that workloads of mostly readers can be executed with
40 low runtime overheads. This matches that the default kind of the lock is
41 PTHREAD_RWLOCK_PREFER_READER_NP. Acquiring a read lock requires a single
42 atomic addition if the lock is or was previously acquired by other
43 readers; releasing the lock is a single CAS if there are no concurrent
44 writers.
45 Workloads consisting of mostly writers are of secondary importance.
46 An uncontended write lock acquisition is as fast as for a normal
47 exclusive mutex but writer contention is somewhat more costly due to
48 keeping track of the exact number of writers. If the rwlock kind requests
49 writers to be preferred (i.e., PTHREAD_RWLOCK_PREFER_WRITERS_NP or the
50 no-recursive-readers variant of it), then writer--to--writer lock ownership
51 hand-over is fairly fast and bypasses lock acquisition attempts by readers.
52 The costs of lock ownership transfer between readers and writers vary. If
53 the program asserts that there are no recursive readers and writers are
54 preferred, then write lock acquisition attempts will block subsequent read
55 lock acquisition attempts, so that new incoming readers do not prolong a
56 phase in which readers have acquired the lock.
57
58 The main components of the rwlock are a writer-only lock that allows only
59 one of the concurrent writers to be the primary writer, and a
60 single-writer-multiple-readers lock that decides between read phases, in
61 which readers have acquired the rwlock, and write phases in which a primary
62 writer or a sequence of different primary writers have acquired the rwlock.
63
64 The single-writer-multiple-readers lock is the central piece of state
65 describing the rwlock and is encoded in the __readers field (see below for
66 a detailed explanation):
67
68 State WP WL R RW Notes
69 ---------------------------
70 #1 0 0 0 0 Lock is idle (and in a read phase).
71 #2 0 0 >0 0 Readers have acquired the lock.
72 #3 0 1 0 0 Lock is not acquired; a writer will try to start a
73 write phase.
74 #4 0 1 >0 0 Readers have acquired the lock; a writer is waiting
75 and explicit hand-over to the writer is required.
76 #4a 0 1 >0 1 Same as #4 except that there are further readers
77 waiting because the writer is to be preferred.
78 #5 1 0 0 0 Lock is idle (and in a write phase).
79 #6 1 0 >0 0 Write phase; readers will try to start a read phase
80 (requires explicit hand-over to all readers that
81 do not start the read phase).
82 #7 1 1 0 0 Lock is acquired by a writer.
83 #8 1 1 >0 0 Lock acquired by a writer and readers are waiting;
84 explicit hand-over to the readers is required.
85
86 WP (PTHREAD_RWLOCK_WRPHASE) is true if the lock is in a write phase, so
87 potentially acquired by a primary writer.
88 WL (PTHREAD_RWLOCK_WRLOCKED) is true if there is a primary writer (i.e.,
89 the thread that was able to set this bit from false to true).
90 R (all bits in __readers except the number of least-significant bits
91 denoted in PTHREAD_RWLOCK_READER_SHIFT) is the number of readers that have
92 or are trying to acquired the lock. There may be more readers waiting if
93 writers are preferred and there will be no recursive readers, in which
94 case RW (PTHREAD_RWLOCK_RWAITING) is true in state #4a.
95
96 We want to block using futexes but using __readers as a futex word directly
97 is not a good solution. First, we want to wait on different conditions
98 such as waiting for a phase change vs. waiting for the primary writer to
99 release the writer-only lock. Second, the number of readers could change
100 frequently, which would make it likely that a writer's futex_wait fails
101 frequently too because the expected value does not match the value of
102 __readers anymore.
103 Therefore, we split out the futex words into the __wrphase_futex and
104 __writers_futex fields. The former tracks the value of the WP bit and is
105 changed after changing WP by the thread that changes WP. However, because
106 of the POSIX requirements regarding mutex/rwlock destruction (i.e., that
107 destroying a rwlock is allowed as soon as no thread has acquired or will
108 acquire the lock), we have to be careful and hand over lock ownership (via
109 a phase change) carefully to those threads waiting. Specifically, we must
110 prevent a situation in which we are not quite sure whether we still have
111 to unblock another thread through a change to memory (executing a
112 futex_wake on a former futex word that is now used for something else is
113 fine).
114 The scheme we use for __wrphase_futex is that waiting threads that may
115 use the futex word to block now all have to use the futex word to block; it
116 is not allowed to take the short-cut and spin-wait on __readers because
117 then the waking thread cannot just make one final change to memory to
118 unblock all potentially waiting threads. If, for example, a reader
119 increments R in states #7 or #8, it has to then block until __wrphase_futex
120 is 0 and it can confirm that the value of 0 was stored by the primary
121 writer; in turn, the primary writer has to change to a read phase too when
122 releasing WL (i.e., to state #2), and it must change __wrphase_futex to 0
123 as the next step. This ensures that the waiting reader will not be able to
124 acquire, release, and then destroy the lock concurrently with the pending
125 futex unblock operations by the former primary writer. This scheme is
126 called explicit hand-over in what follows.
127 Note that waiting threads can cancel waiting only if explicit hand-over has
128 not yet started (e.g., if __readers is still in states #7 or #8 in the
129 example above).
130
131 Writers determine the primary writer through WL. Blocking using futexes
132 is performed using __writers_futex as a futex word; primary writers will
133 enable waiting on this futex by setting it to 1 after they acquired the WL
134 bit and will disable waiting by setting it to 0 before they release WL.
135 This leaves small windows where blocking using futexes is not possible
136 although a primary writer exists, but in turn decreases complexity of the
137 writer--writer synchronization and does not affect correctness.
138 If writers are preferred, writers can hand over WL directly to other
139 waiting writers that registered by incrementing __writers: If the primary
140 writer can CAS __writers from a non-zero value to the same value with the
141 PTHREAD_RWLOCK_WRHANDOVER bit set, it effectively transfers WL ownership
142 to one of the registered waiting writers and does not reset WL; in turn,
143 a registered writer that can clear PTHREAD_RWLOCK_WRHANDOVER using a CAS
144 then takes over WL. Note that registered waiting writers can cancel
145 waiting by decrementing __writers, but the last writer to unregister must
146 become the primary writer if PTHREAD_RWLOCK_WRHANDOVER is set.
147 Also note that adding another state/bit to signal potential writer--writer
148 contention (e.g., as done in the normal mutex algorithm) would not be
149 helpful because we would have to conservatively assume that there is in
150 fact no other writer, and wake up readers too.
151
152 To avoid having to call futex_wake when no thread uses __wrphase_futex or
153 __writers_futex, threads will set the PTHREAD_RWLOCK_FUTEX_USED bit in the
154 respective futex words before waiting on it (using a CAS so it will only be
155 set if in a state in which waiting would be possible). In the case of
156 __writers_futex, we wake only one thread but several threads may share
157 PTHREAD_RWLOCK_FUTEX_USED, so we must assume that there are still others.
158 This is similar to what we do in pthread_mutex_lock. We do not need to
159 do this for __wrphase_futex because there, we always wake all waiting
160 threads.
161
162 Blocking in the state #4a simply uses __readers as futex word. This
163 simplifies the algorithm but suffers from some of the drawbacks discussed
164 before, though not to the same extent because R can only decrease in this
165 state, so the number of potentially failing futex_wait attempts will be
166 bounded. All threads moving from state #4a to another state must wake
167 up threads blocked on the __readers futex.
168
169 The ordering invariants that we have to take care of in the implementation
170 are primarily those necessary for a reader--writer lock; this is rather
171 straightforward and happens during write/read phase switching (potentially
172 through explicit hand-over), and between writers through synchronization
173 involving the PTHREAD_RWLOCK_WRLOCKED or PTHREAD_RWLOCK_WRHANDOVER bits.
174 Additionally, we need to take care that modifications of __writers_futex
175 and __wrphase_futex (e.g., by otherwise unordered readers) take place in
176 the writer critical sections or read/write phases, respectively, and that
177 explicit hand-over observes stores from the previous phase. How this is
178 done is explained in more detail in comments in the code.
179
180 Many of the accesses to the futex words just need relaxed MO. This is
181 possible because we essentially drive both the core rwlock synchronization
182 and the futex synchronization in parallel. For example, an unlock will
183 unlock the rwlock and take part in the futex synchronization (using
184 PTHREAD_RWLOCK_FUTEX_USED, see above); even if they are not tightly
185 ordered in some way, the futex synchronization ensures that there are no
186 lost wake-ups, and woken threads will then eventually see the most recent
187 state of the rwlock. IOW, waiting threads will always be woken up, while
188 not being able to wait using futexes (which can happen) is harmless; in
189 turn, this means that waiting threads don't need special ordering wrt.
190 waking threads.
191
192 The futex synchronization consists of the three-state futex word:
193 (1) cannot block on it, (2) can block on it, and (3) there might be a
194 thread blocked on it (i.e., with PTHREAD_RWLOCK_FUTEX_USED set).
195 Relaxed-MO atomic read-modify-write operations are sufficient to maintain
196 this (e.g., using a CAS to go from (2) to (3) but not from (1) to (3)),
197 but we need ordering of the futex word modifications by the waking threads
198 so that they collectively make correct state changes between (1)-(3).
199 The futex-internal synchronization (i.e., the conceptual critical sections
200 around futex operations in the kernel) then ensures that even an
201 unconstrained load (i.e., relaxed MO) inside of futex_wait will not lead to
202 lost wake-ups because either the waiting thread will see the change from
203 (3) to (1) when a futex_wake came first, or this futex_wake will wake this
204 waiting thread because the waiting thread came first.
205
206
207 POSIX allows but does not require rwlock acquisitions to be a cancellation
208 point. We do not support cancellation.
209
210 TODO We do not try to elide any read or write lock acquisitions currently.
211 While this would be possible, it is unclear whether HTM performance is
212 currently predictable enough and our runtime tuning is good enough at
213 deciding when to use elision so that enabling it would lead to consistently
214 better performance. */
215
216
217static int
218__pthread_rwlock_get_private (pthread_rwlock_t *rwlock)
219{
220 return rwlock->__data.__shared != 0 ? FUTEX_SHARED : FUTEX_PRIVATE;
221}
222
223static __always_inline void
224__pthread_rwlock_rdunlock (pthread_rwlock_t *rwlock)
225{
226 int private = __pthread_rwlock_get_private (rwlock);
227 /* We decrease the number of readers, and if we are the last reader and
228 there is a primary writer, we start a write phase. We use a CAS to
229 make this atomic so that it is clear whether we must hand over ownership
230 explicitly. */
231 unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers);
232 unsigned int rnew;
233 for (;;)
234 {
235 rnew = r - (1 << PTHREAD_RWLOCK_READER_SHIFT);
236 /* If we are the last reader, we also need to unblock any readers
237 that are waiting for a writer to go first (PTHREAD_RWLOCK_RWAITING)
238 so that they can register while the writer is active. */
239 if ((rnew >> PTHREAD_RWLOCK_READER_SHIFT) == 0)
240 {
241 if ((rnew & PTHREAD_RWLOCK_WRLOCKED) != 0)
242 rnew |= PTHREAD_RWLOCK_WRPHASE;
243 rnew &= ~(unsigned int) PTHREAD_RWLOCK_RWAITING;
244 }
245 /* We need release MO here for three reasons. First, so that we
246 synchronize with subsequent writers. Second, we might have been the
247 first reader and set __wrphase_futex to 0, so we need to synchronize
248 with the last reader that will set it to 1 (note that we will always
249 change __readers before the last reader, or we are the last reader).
250 Third, a writer that takes part in explicit hand-over needs to see
251 the first reader's store to __wrphase_futex (or a later value) if
252 the writer observes that a write phase has been started. */
253 if (atomic_compare_exchange_weak_release (&rwlock->__data.__readers,
254 &r, rnew))
255 break;
256 /* TODO Back-off. */
257 }
258 if ((rnew & PTHREAD_RWLOCK_WRPHASE) != 0)
259 {
260 /* We need to do explicit hand-over. We need the acquire MO fence so
261 that our modification of _wrphase_futex happens after a store by
262 another reader that started a read phase. Relaxed MO is sufficient
263 for the modification of __wrphase_futex because it is just used
264 to delay acquisition by a writer until all threads are unblocked
265 irrespective of whether they are looking at __readers or
266 __wrphase_futex; any other synchronizes-with relations that are
267 necessary are established through __readers. */
268 atomic_thread_fence_acquire ();
269 if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 1)
270 & PTHREAD_RWLOCK_FUTEX_USED) != 0)
271 futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private);
272 }
273 /* Also wake up waiting readers if we did reset the RWAITING flag. */
274 if ((r & PTHREAD_RWLOCK_RWAITING) != (rnew & PTHREAD_RWLOCK_RWAITING))
275 futex_wake (&rwlock->__data.__readers, INT_MAX, private);
276}
277
278
279static __always_inline int
280__pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
281 const struct timespec *abstime)
282{
283 unsigned int r;
284
285 /* Make sure we are not holding the rwlock as a writer. This is a deadlock
286 situation we recognize and report. */
287 if (__glibc_unlikely (atomic_load_relaxed (&rwlock->__data.__cur_writer)
288 == THREAD_GETMEM (THREAD_SELF, tid)))
289 return EDEADLK;
290
291 /* If we prefer writers, recursive rdlock is disallowed, we are in a read
292 phase, and there are other readers present, we try to wait without
293 extending the read phase. We will be unblocked by either one of the
294 other active readers, or if the writer gives up WRLOCKED (e.g., on
295 timeout).
296 If there are no other readers, we simply race with any existing primary
297 writer; it would have been a race anyway, and changing the odds slightly
298 will likely not make a big difference. */
299 if (rwlock->__data.__flags == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP)
300 {
301 r = atomic_load_relaxed (&rwlock->__data.__readers);
302 while (((r & PTHREAD_RWLOCK_WRPHASE) == 0)
303 && ((r & PTHREAD_RWLOCK_WRLOCKED) != 0)
304 && ((r >> PTHREAD_RWLOCK_READER_SHIFT) > 0))
305 {
306 /* TODO Spin first. */
307 /* Try setting the flag signaling that we are waiting without having
308 incremented the number of readers. Relaxed MO is fine because
309 this is just about waiting for a state change in __readers. */
310 if (atomic_compare_exchange_weak_relaxed
311 (&rwlock->__data.__readers, &r, r | PTHREAD_RWLOCK_RWAITING))
312 {
313 /* Wait for as long as the flag is set. An ABA situation is
314 harmless because the flag is just about the state of
315 __readers, and all threads set the flag under the same
316 conditions. */
317 while ((atomic_load_relaxed (&rwlock->__data.__readers)
318 & PTHREAD_RWLOCK_RWAITING) != 0)
319 {
320 int private = __pthread_rwlock_get_private (rwlock);
321 int err = futex_abstimed_wait (&rwlock->__data.__readers,
322 r, abstime, private);
323 /* We ignore EAGAIN and EINTR. On time-outs, we can just
324 return because we don't need to clean up anything. */
325 if (err == ETIMEDOUT)
326 return err;
327 }
328 /* It makes sense to not break out of the outer loop here
329 because we might be in the same situation again. */
330 }
331 else
332 {
333 /* TODO Back-off. */
334 }
335 }
336 }
337 /* Register as a reader, using an add-and-fetch so that R can be used as
338 expected value for future operations. Acquire MO so we synchronize with
339 prior writers as well as the last reader of the previous read phase (see
340 below). */
341 r = atomic_fetch_add_acquire (&rwlock->__data.__readers,
342 (1 << PTHREAD_RWLOCK_READER_SHIFT)) + (1 << PTHREAD_RWLOCK_READER_SHIFT);
343
344 /* Check whether there is an overflow in the number of readers. We assume
345 that the total number of threads is less than half the maximum number
346 of readers that we have bits for in __readers (i.e., with 32-bit int and
347 PTHREAD_RWLOCK_READER_SHIFT of 3, we assume there are less than
348 1 << (32-3-1) concurrent threads).
349 If there is an overflow, we use a CAS to try to decrement the number of
350 readers if there still is an overflow situation. If so, we return
351 EAGAIN; if not, we are not a thread causing an overflow situation, and so
352 we just continue. Using a fetch-add instead of the CAS isn't possible
353 because other readers might release the lock concurrently, which could
354 make us the last reader and thus responsible for handing ownership over
355 to writers (which requires a CAS too to make the decrement and ownership
356 transfer indivisible). */
357 while (__glibc_unlikely (r >= PTHREAD_RWLOCK_READER_OVERFLOW))
358 {
359 /* Relaxed MO is okay because we just want to undo our registration and
360 cannot have changed the rwlock state substantially if the CAS
361 succeeds. */
362 if (atomic_compare_exchange_weak_relaxed (&rwlock->__data.__readers, &r,
363 r - (1 << PTHREAD_RWLOCK_READER_SHIFT)))
364 return EAGAIN;
365 }
366
367 /* We have registered as a reader, so if we are in a read phase, we have
368 acquired a read lock. This is also the reader--reader fast-path.
369 Even if there is a primary writer, we just return. If writers are to
370 be preferred and we are the only active reader, we could try to enter a
371 write phase to let the writer proceed. This would be okay because we
372 cannot have acquired the lock previously as a reader (which could result
373 in deadlock if we would wait for the primary writer to run). However,
374 this seems to be a corner case and handling it specially not be worth the
375 complexity. */
376 if (__glibc_likely ((r & PTHREAD_RWLOCK_WRPHASE) == 0))
377 return 0;
378 /* Otherwise, if we were in a write phase (states #6 or #8), we must wait
379 for explicit hand-over of the read phase; the only exception is if we
380 can start a read phase if there is no primary writer currently. */
381 while (((r & PTHREAD_RWLOCK_WRPHASE) != 0)
382 && ((r & PTHREAD_RWLOCK_WRLOCKED) == 0))
383 {
384 /* Try to enter a read phase: If the CAS below succeeds, we have
385 ownership; if it fails, we will simply retry and reassess the
386 situation.
387 Acquire MO so we synchronize with prior writers. */
388 if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers, &r,
389 r ^ PTHREAD_RWLOCK_WRPHASE))
390 {
391 /* We started the read phase, so we are also responsible for
392 updating the write-phase futex. Relaxed MO is sufficient.
393 We have to do the same steps as a writer would when handing
394 over the read phase to us because other readers cannot
395 distinguish between us and the writer; this includes
396 explicit hand-over and potentially having to wake other readers
397 (but we can pretend to do the setting and unsetting of WRLOCKED
398 atomically, and thus can skip this step). */
399 if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 0)
400 & PTHREAD_RWLOCK_FUTEX_USED) != 0)
401 {
402 int private = __pthread_rwlock_get_private (rwlock);
403 futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private);
404 }
405 return 0;
406 }
407 else
408 {
409 /* TODO Back off before retrying. Also see above. */
410 }
411 }
412
413 /* We were in a write phase but did not install the read phase. We cannot
414 distinguish between a writer and another reader starting the read phase,
415 so we must wait for explicit hand-over via __wrphase_futex.
416 However, __wrphase_futex might not have been set to 1 yet (either
417 because explicit hand-over to the writer is still ongoing, or because
418 the writer has started the write phase but has not yet updated
419 __wrphase_futex). The least recent value of __wrphase_futex we can
420 read from here is the modification of the last read phase (because
421 we synchronize with the last reader in this read phase through
422 __readers; see the use of acquire MO on the fetch_add above).
423 Therefore, if we observe a value of 0 for __wrphase_futex, we need
424 to subsequently check that __readers now indicates a read phase; we
425 need to use acquire MO for this so that if we observe a read phase,
426 we will also see the modification of __wrphase_futex by the previous
427 writer. We then need to load __wrphase_futex again and continue to
428 wait if it is not 0, so that we do not skip explicit hand-over.
429 Relaxed MO is sufficient for the load from __wrphase_futex because
430 we just use it as an indicator for when we can proceed; we use
431 __readers and the acquire MO accesses to it to eventually read from
432 the proper stores to __wrphase_futex. */
433 unsigned int wpf;
434 bool ready = false;
435 for (;;)
436 {
437 while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex))
438 | PTHREAD_RWLOCK_FUTEX_USED) == (1 | PTHREAD_RWLOCK_FUTEX_USED))
439 {
440 int private = __pthread_rwlock_get_private (rwlock);
441 if (((wpf & PTHREAD_RWLOCK_FUTEX_USED) == 0)
442 && !atomic_compare_exchange_weak_relaxed
443 (&rwlock->__data.__wrphase_futex,
444 &wpf, wpf | PTHREAD_RWLOCK_FUTEX_USED))
445 continue;
446 int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex,
447 1 | PTHREAD_RWLOCK_FUTEX_USED, abstime, private);
448 if (err == ETIMEDOUT)
449 {
450 /* If we timed out, we need to unregister. If no read phase
451 has been installed while we waited, we can just decrement
452 the number of readers. Otherwise, we just acquire the
453 lock, which is allowed because we give no precise timing
454 guarantees, and because the timeout is only required to
455 be in effect if we would have had to wait for other
456 threads (e.g., if futex_wait would time-out immediately
457 because the given absolute time is in the past). */
458 r = atomic_load_relaxed (&rwlock->__data.__readers);
459 while ((r & PTHREAD_RWLOCK_WRPHASE) != 0)
460 {
461 /* We don't need to make anything else visible to
462 others besides unregistering, so relaxed MO is
463 sufficient. */
464 if (atomic_compare_exchange_weak_relaxed
465 (&rwlock->__data.__readers, &r,
466 r - (1 << PTHREAD_RWLOCK_READER_SHIFT)))
467 return ETIMEDOUT;
468 /* TODO Back-off. */
469 }
470 /* Use the acquire MO fence to mirror the steps taken in the
471 non-timeout case. Note that the read can happen both
472 in the atomic_load above as well as in the failure case
473 of the CAS operation. */
474 atomic_thread_fence_acquire ();
475 /* We still need to wait for explicit hand-over, but we must
476 not use futex_wait anymore because we would just time out
477 in this case and thus make the spin-waiting we need
478 unnecessarily expensive. */
479 while ((atomic_load_relaxed (&rwlock->__data.__wrphase_futex)
480 | PTHREAD_RWLOCK_FUTEX_USED)
481 == (1 | PTHREAD_RWLOCK_FUTEX_USED))
482 {
483 /* TODO Back-off? */
484 }
485 ready = true;
486 break;
487 }
488 /* If we got interrupted (EINTR) or the futex word does not have the
489 expected value (EAGAIN), retry. */
490 }
491 if (ready)
492 /* See below. */
493 break;
494 /* We need acquire MO here so that we synchronize with the lock
495 release of the writer, and so that we observe a recent value of
496 __wrphase_futex (see below). */
497 if ((atomic_load_acquire (&rwlock->__data.__readers)
498 & PTHREAD_RWLOCK_WRPHASE) == 0)
499 /* We are in a read phase now, so the least recent modification of
500 __wrphase_futex we can read from is the store by the writer
501 with value 1. Thus, only now we can assume that if we observe
502 a value of 0, explicit hand-over is finished. Retry the loop
503 above one more time. */
504 ready = true;
505 }
506
507 return 0;
508}
509
510
511static __always_inline void
512__pthread_rwlock_wrunlock (pthread_rwlock_t *rwlock)
513{
514 int private = __pthread_rwlock_get_private (rwlock);
515
516 atomic_store_relaxed (&rwlock->__data.__cur_writer, 0);
517 /* Disable waiting by writers. We will wake up after we decided how to
518 proceed. */
519 bool wake_writers = ((atomic_exchange_relaxed
520 (&rwlock->__data.__writers_futex, 0) & PTHREAD_RWLOCK_FUTEX_USED) != 0);
521
522 if (rwlock->__data.__flags != PTHREAD_RWLOCK_PREFER_READER_NP)
523 {
524 /* First, try to hand over to another writer. */
525 unsigned int w = atomic_load_relaxed (&rwlock->__data.__writers);
526 while (w != 0)
527 {
528 /* Release MO so that another writer that gets WRLOCKED from us will
529 synchronize with us and thus can take over our view of
530 __readers (including, for example, whether we are in a write
531 phase or not). */
532 if (atomic_compare_exchange_weak_release (&rwlock->__data.__writers,
533 &w, w | PTHREAD_RWLOCK_WRHANDOVER))
534 /* Another writer will take over. */
535 goto done;
536 /* TODO Back-off. */
537 }
538 }
539
540 /* We have done everything we needed to do to prefer writers, so now we
541 either hand over explicitly to readers if there are any, or we simply
542 stay in a write phase. See pthread_rwlock_rdunlock for more details. */
543 unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers);
544 /* Release MO so that subsequent readers or writers synchronize with us. */
545 while (!atomic_compare_exchange_weak_release
546 (&rwlock->__data.__readers, &r, (r ^ PTHREAD_RWLOCK_WRLOCKED)
547 ^ ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0 ? 0
548 : PTHREAD_RWLOCK_WRPHASE)))
549 {
550 /* TODO Back-off. */
551 }
552 if ((r >> PTHREAD_RWLOCK_READER_SHIFT) != 0)
553 {
554 /* We must hand over explicitly through __wrphase_futex. Relaxed MO is
555 sufficient because it is just used to delay acquisition by a writer;
556 any other synchronizes-with relations that are necessary are
557 established through __readers. */
558 if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 0)
559 & PTHREAD_RWLOCK_FUTEX_USED) != 0)
560 futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private);
561 }
562
563 done:
564 /* We released WRLOCKED in some way, so wake a writer. */
565 if (wake_writers)
566 futex_wake (&rwlock->__data.__writers_futex, 1, private);
567}
568
569
570static __always_inline int
571__pthread_rwlock_wrlock_full (pthread_rwlock_t *rwlock,
572 const struct timespec *abstime)
573{
574 /* Make sure we are not holding the rwlock as a writer. This is a deadlock
575 situation we recognize and report. */
576 if (__glibc_unlikely (atomic_load_relaxed (&rwlock->__data.__cur_writer)
577 == THREAD_GETMEM (THREAD_SELF, tid)))
578 return EDEADLK;
579
580 /* First we try to acquire the role of primary writer by setting WRLOCKED;
581 if it was set before, there already is a primary writer. Acquire MO so
582 that we synchronize with previous primary writers.
583
584 We do not try to change to a write phase right away using a fetch_or
585 because we would have to reset it again and wake readers if there are
586 readers present (some readers could try to acquire the lock more than
587 once, so setting a write phase in the middle of this could cause
588 deadlock). Changing to a write phase eagerly would only speed up the
589 transition from a read phase to a write phase in the uncontended case,
590 but it would slow down the contended case if readers are preferred (which
591 is the default).
592 We could try to CAS from a state with no readers to a write phase, but
593 this could be less scalable if readers arrive and leave frequently. */
594 bool may_share_futex_used_flag = false;
595 unsigned int r = atomic_fetch_or_acquire (&rwlock->__data.__readers,
596 PTHREAD_RWLOCK_WRLOCKED);
597 if (__glibc_unlikely ((r & PTHREAD_RWLOCK_WRLOCKED) != 0))
598 {
599 /* There is another primary writer. */
600 bool prefer_writer =
601 (rwlock->__data.__flags != PTHREAD_RWLOCK_PREFER_READER_NP);
602 if (prefer_writer)
603 {
604 /* We register as a waiting writer, so that we can make use of
605 writer--writer hand-over. Relaxed MO is fine because we just
606 want to register. We assume that the maximum number of threads
607 is less than the capacity in __writers. */
608 atomic_fetch_add_relaxed (&rwlock->__data.__writers, 1);
609 }
610 for (;;)
611 {
612 /* TODO Spin until WRLOCKED is 0 before trying the CAS below.
613 But pay attention to not delay trying writer--writer hand-over
614 for too long (which we must try eventually anyway). */
615 if ((r & PTHREAD_RWLOCK_WRLOCKED) == 0)
616 {
617 /* Try to become the primary writer or retry. Acquire MO as in
618 the fetch_or above. */
619 if (atomic_compare_exchange_weak_acquire
620 (&rwlock->__data.__readers, &r,
621 r | PTHREAD_RWLOCK_WRLOCKED))
622 {
623 if (prefer_writer)
624 {
625 /* Unregister as a waiting writer. Note that because we
626 acquired WRLOCKED, WRHANDOVER will not be set.
627 Acquire MO on the CAS above ensures that
628 unregistering happens after the previous writer;
629 this sorts the accesses to __writers by all
630 primary writers in a useful way (e.g., any other
631 primary writer acquiring after us or getting it from
632 us through WRHANDOVER will see both our changes to
633 __writers).
634 ??? Perhaps this is not strictly necessary for
635 reasons we do not yet know of. */
636 atomic_fetch_add_relaxed (&rwlock->__data.__writers,
637 -1);
638 }
639 break;
640 }
641 /* Retry if the CAS fails (r will have been updated). */
642 continue;
643 }
644 /* If writer--writer hand-over is available, try to become the
645 primary writer this way by grabbing the WRHANDOVER token. If we
646 succeed, we own WRLOCKED. */
647 if (prefer_writer)
648 {
649 unsigned int w = atomic_load_relaxed
650 (&rwlock->__data.__writers);
651 if ((w & PTHREAD_RWLOCK_WRHANDOVER) != 0)
652 {
653 /* Acquire MO is required here so that we synchronize with
654 the writer that handed over WRLOCKED. We also need this
655 for the reload of __readers below because our view of
656 __readers must be at least as recent as the view of the
657 writer that handed over WRLOCKED; we must avoid an ABA
658 through WRHANDOVER, which could, for example, lead to us
659 assuming we are still in a write phase when in fact we
660 are not. */
661 if (atomic_compare_exchange_weak_acquire
662 (&rwlock->__data.__writers,
663 &w, (w - PTHREAD_RWLOCK_WRHANDOVER - 1)))
664 {
665 /* Reload so our view is consistent with the view of
666 the previous owner of WRLOCKED. See above. */
667 r = atomic_load_relaxed (&rwlock->__data.__readers);
668 break;
669 }
670 /* We do not need to reload __readers here. We should try
671 to perform writer--writer hand-over if possible; if it
672 is not possible anymore, we will reload __readers
673 elsewhere in this loop. */
674 continue;
675 }
676 }
677 /* We did not acquire WRLOCKED nor were able to use writer--writer
678 hand-over, so we block on __writers_futex. */
679 int private = __pthread_rwlock_get_private (rwlock);
680 unsigned int wf = atomic_load_relaxed
681 (&rwlock->__data.__writers_futex);
682 if (((wf & ~(unsigned int) PTHREAD_RWLOCK_FUTEX_USED) != 1)
683 || ((wf != (1 | PTHREAD_RWLOCK_FUTEX_USED))
684 && !atomic_compare_exchange_weak_relaxed
685 (&rwlock->__data.__writers_futex, &wf,
686 1 | PTHREAD_RWLOCK_FUTEX_USED)))
687 {
688 /* If we cannot block on __writers_futex because there is no
689 primary writer, or we cannot set PTHREAD_RWLOCK_FUTEX_USED,
690 we retry. We must reload __readers here in case we cannot
691 block on __writers_futex so that we can become the primary
692 writer and are not stuck in a loop that just continuously
693 fails to block on __writers_futex. */
694 r = atomic_load_relaxed (&rwlock->__data.__readers);
695 continue;
696 }
697 /* We set the flag that signals that the futex is used, or we could
698 have set it if we had been faster than other waiters. As a
699 result, we may share the flag with an unknown number of other
700 writers. Therefore, we must keep this flag set when we acquire
701 the lock. We do not need to do this when we do not reach this
702 point here because then we are not part of the group that may
703 share the flag, and another writer will wake one of the writers
704 in this group. */
705 may_share_futex_used_flag = true;
706 int err = futex_abstimed_wait (&rwlock->__data.__writers_futex,
707 1 | PTHREAD_RWLOCK_FUTEX_USED, abstime, private);
708 if (err == ETIMEDOUT)
709 {
710 if (prefer_writer)
711 {
712 /* We need to unregister as a waiting writer. If we are the
713 last writer and writer--writer hand-over is available,
714 we must make use of it because nobody else will reset
715 WRLOCKED otherwise. (If we use it, we simply pretend
716 that this happened before the timeout; see
717 pthread_rwlock_rdlock_full for the full reasoning.)
718 Also see the similar code above. */
719 unsigned int w = atomic_load_relaxed
720 (&rwlock->__data.__writers);
721 while (!atomic_compare_exchange_weak_acquire
722 (&rwlock->__data.__writers, &w,
723 (w == PTHREAD_RWLOCK_WRHANDOVER + 1 ? 0 : w - 1)))
724 {
725 /* TODO Back-off. */
726 }
727 if (w == PTHREAD_RWLOCK_WRHANDOVER + 1)
728 {
729 /* We must continue as primary writer. See above. */
730 r = atomic_load_relaxed (&rwlock->__data.__readers);
731 break;
732 }
733 }
734 /* We cleaned up and cannot have stolen another waiting writer's
735 futex wake-up, so just return. */
736 return ETIMEDOUT;
737 }
738 /* If we got interrupted (EINTR) or the futex word does not have the
739 expected value (EAGAIN), retry after reloading __readers. */
740 r = atomic_load_relaxed (&rwlock->__data.__readers);
741 }
742 /* Our snapshot of __readers is up-to-date at this point because we
743 either set WRLOCKED using a CAS (and update r accordingly below,
744 which was used as expected value for the CAS) or got WRLOCKED from
745 another writer whose snapshot of __readers we inherit. */
746 r |= PTHREAD_RWLOCK_WRLOCKED;
747 }
748
749 /* We are the primary writer; enable blocking on __writers_futex. Relaxed
750 MO is sufficient for futex words; acquire MO on the previous
751 modifications of __readers ensures that this store happens after the
752 store of value 0 by the previous primary writer. */
753 atomic_store_relaxed (&rwlock->__data.__writers_futex,
754 1 | (may_share_futex_used_flag ? PTHREAD_RWLOCK_FUTEX_USED : 0));
755
756 /* If we are in a write phase, we have acquired the lock. */
757 if ((r & PTHREAD_RWLOCK_WRPHASE) != 0)
758 goto done;
759
760 /* If we are in a read phase and there are no readers, try to start a write
761 phase. */
762 while (((r & PTHREAD_RWLOCK_WRPHASE) == 0)
763 && ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0))
764 {
765 /* Acquire MO so that we synchronize with prior writers and do
766 not interfere with their updates to __writers_futex, as well
767 as regarding prior readers and their updates to __wrphase_futex,
768 respectively. */
769 if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers,
770 &r, r | PTHREAD_RWLOCK_WRPHASE))
771 {
772 /* We have started a write phase, so need to enable readers to wait.
773 See the similar case in __pthread_rwlock_rdlock_full. Unlike in
774 that similar case, we are the (only) primary writer and so do
775 not need to wake another writer. */
776 atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1);
777
778 goto done;
779 }
780 /* TODO Back-off. */
781 }
782
783 /* We became the primary writer in a read phase and there were readers when
784 we did (because of the previous loop). Thus, we have to wait for
785 explicit hand-over from one of these readers.
786 We basically do the same steps as for the similar case in
787 __pthread_rwlock_rdlock_full, except that we additionally might try
788 to directly hand over to another writer and need to wake up
789 other writers or waiting readers (i.e., PTHREAD_RWLOCK_RWAITING). */
790 unsigned int wpf;
791 bool ready = false;
792 for (;;)
793 {
794 while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex))
795 | PTHREAD_RWLOCK_FUTEX_USED) == PTHREAD_RWLOCK_FUTEX_USED)
796 {
797 int private = __pthread_rwlock_get_private (rwlock);
798 if (((wpf & PTHREAD_RWLOCK_FUTEX_USED) == 0)
799 && !atomic_compare_exchange_weak_relaxed
800 (&rwlock->__data.__wrphase_futex, &wpf,
801 PTHREAD_RWLOCK_FUTEX_USED))
802 continue;
803 int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex,
804 PTHREAD_RWLOCK_FUTEX_USED, abstime, private);
805 if (err == ETIMEDOUT)
806 {
807 if (rwlock->__data.__flags
808 != PTHREAD_RWLOCK_PREFER_READER_NP)
809 {
810 /* We try writer--writer hand-over. */
811 unsigned int w = atomic_load_relaxed
812 (&rwlock->__data.__writers);
813 if (w != 0)
814 {
815 /* We are about to hand over WRLOCKED, so we must
816 release __writers_futex too; otherwise, we'd have
817 a pending store, which could at least prevent
818 other threads from waiting using the futex
819 because it could interleave with the stores
820 by subsequent writers. In turn, this means that
821 we have to clean up when we do not hand over
822 WRLOCKED.
823 Release MO so that another writer that gets
824 WRLOCKED from us can take over our view of
825 __readers. */
826 unsigned int wf = atomic_exchange_relaxed
827 (&rwlock->__data.__writers_futex, 0);
828 while (w != 0)
829 {
830 if (atomic_compare_exchange_weak_release
831 (&rwlock->__data.__writers, &w,
832 w | PTHREAD_RWLOCK_WRHANDOVER))
833 {
834 /* Wake other writers. */
835 if ((wf & PTHREAD_RWLOCK_FUTEX_USED) != 0)
836 futex_wake (&rwlock->__data.__writers_futex,
837 1, private);
838 return ETIMEDOUT;
839 }
840 /* TODO Back-off. */
841 }
842 /* We still own WRLOCKED and someone else might set
843 a write phase concurrently, so enable waiting
844 again. Make sure we don't loose the flag that
845 signals whether there are threads waiting on
846 this futex. */
847 atomic_store_relaxed
848 (&rwlock->__data.__writers_futex, wf);
849 }
850 }
851 /* If we timed out and we are not in a write phase, we can
852 just stop being a primary writer. Otherwise, we just
853 acquire the lock. */
854 r = atomic_load_relaxed (&rwlock->__data.__readers);
855 if ((r & PTHREAD_RWLOCK_WRPHASE) == 0)
856 {
857 /* We are about to release WRLOCKED, so we must release
858 __writers_futex too; see the handling of
859 writer--writer hand-over above. */
860 unsigned int wf = atomic_exchange_relaxed
861 (&rwlock->__data.__writers_futex, 0);
862 while ((r & PTHREAD_RWLOCK_WRPHASE) == 0)
863 {
864 /* While we don't need to make anything from a
865 caller's critical section visible to other
866 threads, we need to ensure that our changes to
867 __writers_futex are properly ordered.
868 Therefore, use release MO to synchronize with
869 subsequent primary writers. Also wake up any
870 waiting readers as they are waiting because of
871 us. */
872 if (atomic_compare_exchange_weak_release
873 (&rwlock->__data.__readers, &r,
874 (r ^ PTHREAD_RWLOCK_WRLOCKED)
875 & ~(unsigned int) PTHREAD_RWLOCK_RWAITING))
876 {
877 /* Wake other writers. */
878 if ((wf & PTHREAD_RWLOCK_FUTEX_USED) != 0)
879 futex_wake (&rwlock->__data.__writers_futex,
880 1, private);
881 /* Wake waiting readers. */
882 if ((r & PTHREAD_RWLOCK_RWAITING) != 0)
883 futex_wake (&rwlock->__data.__readers,
884 INT_MAX, private);
885 return ETIMEDOUT;
886 }
887 }
888 /* We still own WRLOCKED and someone else might set a
889 write phase concurrently, so enable waiting again.
890 Make sure we don't loose the flag that signals
891 whether there are threads waiting on this futex. */
892 atomic_store_relaxed (&rwlock->__data.__writers_futex, wf);
893 }
894 /* Use the acquire MO fence to mirror the steps taken in the
895 non-timeout case. Note that the read can happen both
896 in the atomic_load above as well as in the failure case
897 of the CAS operation. */
898 atomic_thread_fence_acquire ();
899 /* We still need to wait for explicit hand-over, but we must
900 not use futex_wait anymore. */
901 while ((atomic_load_relaxed
902 (&rwlock->__data.__wrphase_futex)
903 | PTHREAD_RWLOCK_FUTEX_USED)
904 == PTHREAD_RWLOCK_FUTEX_USED)
905 {
906 /* TODO Back-off. */
907 }
908 ready = true;
909 break;
910 }
911 /* If we got interrupted (EINTR) or the futex word does not have
912 the expected value (EAGAIN), retry. */
913 }
914 /* See pthread_rwlock_rdlock_full. */
915 if (ready)
916 break;
917 if ((atomic_load_acquire (&rwlock->__data.__readers)
918 & PTHREAD_RWLOCK_WRPHASE) != 0)
919 ready = true;
920 }
921
922 done:
923 atomic_store_relaxed (&rwlock->__data.__cur_writer,
924 THREAD_GETMEM (THREAD_SELF, tid));
925 return 0;
926}
927