diff options
Diffstat (limited to 'nptl/pthread_rwlock_common.c')
| -rw-r--r-- | nptl/pthread_rwlock_common.c | 924 |
1 files changed, 0 insertions, 924 deletions
diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c deleted file mode 100644 index 256508ca2a..0000000000 --- a/nptl/pthread_rwlock_common.c +++ /dev/null @@ -1,924 +0,0 @@ -/* POSIX reader--writer lock: core parts. - Copyright (C) 2016-2017 Free Software Foundation, Inc. - This file is part of the GNU C Library. - - The GNU C Library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - The GNU C Library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with the GNU C Library; if not, see - <http://www.gnu.org/licenses/>. */ - -#include <errno.h> -#include <sysdep.h> -#include <pthread.h> -#include <pthreadP.h> -#include <sys/time.h> -#include <stap-probe.h> -#include <atomic.h> -#include <futex-internal.h> - - -/* A reader--writer lock that fulfills the POSIX requirements (but operations - on this lock are not necessarily full barriers, as one may interpret the - POSIX requirement about "synchronizing memory"). All critical sections are - in a total order, writers synchronize with prior writers and readers, and - readers synchronize with prior writers. - - A thread is allowed to acquire a read lock recursively (i.e., have rdlock - critical sections that overlap in sequenced-before) unless the kind of the - rwlock is set to PTHREAD_RWLOCK_PREFER_WRITERS_NONRECURSIVE_NP. - - This lock is built so that workloads of mostly readers can be executed with - low runtime overheads. This matches that the default kind of the lock is - PTHREAD_RWLOCK_PREFER_READER_NP. Acquiring a read lock requires a single - atomic addition if the lock is or was previously acquired by other - readers; releasing the lock is a single CAS if there are no concurrent - writers. - Workloads consisting of mostly writers are of secondary importance. - An uncontended write lock acquisition is as fast as for a normal - exclusive mutex but writer contention is somewhat more costly due to - keeping track of the exact number of writers. If the rwlock kind requests - writers to be preferred (i.e., PTHREAD_RWLOCK_PREFER_WRITERS_NP or the - no-recursive-readers variant of it), then writer--to--writer lock ownership - hand-over is fairly fast and bypasses lock acquisition attempts by readers. - The costs of lock ownership transfer between readers and writers vary. If - the program asserts that there are no recursive readers and writers are - preferred, then write lock acquisition attempts will block subsequent read - lock acquisition attempts, so that new incoming readers do not prolong a - phase in which readers have acquired the lock. - - - The main components of the rwlock are a writer-only lock that allows only - one of the concurrent writers to be the primary writer, and a - single-writer-multiple-readers lock that decides between read phases, in - which readers have acquired the rwlock, and write phases in which a primary - writer or a sequence of different primary writers have acquired the rwlock. - - The single-writer-multiple-readers lock is the central piece of state - describing the rwlock and is encoded in the __readers field (see below for - a detailed explanation): - - State WP WL R RW Notes - --------------------------- - #1 0 0 0 0 Lock is idle (and in a read phase). - #2 0 0 >0 0 Readers have acquired the lock. - #3 0 1 0 0 Lock is not acquired; a writer is waiting for a write - phase to start or will try to start one. - #4 0 1 >0 0 Readers have acquired the lock; a writer is waiting - and explicit hand-over to the writer is required. - #4a 0 1 >0 1 Same as #4 except that there are further readers - waiting because the writer is to be preferred. - #5 1 0 0 0 Lock is idle (and in a write phase). - #6 1 0 >0 0 Write phase; readers are waiting for a read phase to - start or will try to start one. - #7 1 1 0 0 Lock is acquired by a writer. - #8 1 1 >0 0 Lock acquired by a writer and readers are waiting; - explicit hand-over to the readers is required. - - WP (PTHREAD_RWLOCK_WRPHASE) is true if the lock is in a write phase, so - potentially acquired by a primary writer. - WL (PTHREAD_RWLOCK_WRLOCKED) is true if there is a primary writer (i.e., - the thread that was able to set this bit from false to true). - R (all bits in __readers except the number of least-significant bits - denoted in PTHREAD_RWLOCK_READER_SHIFT) is the number of readers that have - or are trying to acquired the lock. There may be more readers waiting if - writers are preferred and there will be no recursive readers, in which - case RW (PTHREAD_RWLOCK_RWAITING) is true in state #4a. - - We want to block using futexes but using __readers as a futex word directly - is not a good solution. First, we want to wait on different conditions - such as waiting for a phase change vs. waiting for the primary writer to - release the writer-only lock. Second, the number of readers could change - frequently, which would make it likely that a writer's futex_wait fails - frequently too because the expected value does not match the value of - __readers anymore. - Therefore, we split out the futex words into the __wrphase_futex and - __writers_futex fields. The former tracks the value of the WP bit and is - changed after changing WP by the thread that changes WP. However, because - of the POSIX requirements regarding mutex/rwlock destruction (i.e., that - destroying a rwlock is allowed as soon as no thread has acquired or will - acquire the lock), we have to be careful and hand over lock ownership (via - a phase change) carefully to those threads waiting. Specifically, we must - prevent a situation in which we are not quite sure whether we still have - to unblock another thread through a change to memory (executing a - futex_wake on a former futex word that is now used for something else is - fine). - The scheme we use for __wrphase_futex is that waiting threads that may - use the futex word to block now all have to use the futex word to block; it - is not allowed to take the short-cut and spin-wait on __readers because - then the waking thread cannot just make one final change to memory to - unblock all potentially waiting threads. If, for example, a reader - increments R in states #7 or #8, it has to then block until __wrphase_futex - is 0 and it can confirm that the value of 0 was stored by the primary - writer; in turn, the primary writer has to change to a read phase too when - releasing WL (i.e., to state #2), and it must change __wrphase_futex to 0 - as the next step. This ensures that the waiting reader will not be able to - acquire, release, and then destroy the lock concurrently with the pending - futex unblock operations by the former primary writer. This scheme is - called explicit hand-over in what follows. - Note that waiting threads can cancel waiting only if explicit hand-over has - not yet started (e.g., if __readers is still in states #7 or #8 in the - example above). - - Writers determine the primary writer through WL. Blocking using futexes - is performed using __writers_futex as a futex word; primary writers will - enable waiting on this futex by setting it to 1 after they acquired the WL - bit and will disable waiting by setting it to 0 before they release WL. - This leaves small windows where blocking using futexes is not possible - although a primary writer exists, but in turn decreases complexity of the - writer--writer synchronization and does not affect correctness. - If writers are preferred, writers can hand over WL directly to other - waiting writers that registered by incrementing __writers: If the primary - writer can CAS __writers from a non-zero value to the same value with the - PTHREAD_RWLOCK_WRHANDOVER bit set, it effectively transfers WL ownership - to one of the registered waiting writers and does not reset WL; in turn, - a registered writer that can clear PTHREAD_RWLOCK_WRHANDOVER using a CAS - then takes over WL. Note that registered waiting writers can cancel - waiting by decrementing __writers, but the last writer to unregister must - become the primary writer if PTHREAD_RWLOCK_WRHANDOVER is set. - Also note that adding another state/bit to signal potential writer--writer - contention (e.g., as done in the normal mutex algorithm) would not be - helpful because we would have to conservatively assume that there is in - fact no other writer, and wake up readers too. - - To avoid having to call futex_wake when no thread uses __wrphase_futex or - __writers_futex, threads will set the PTHREAD_RWLOCK_FUTEX_USED bit in the - respective futex words before waiting on it (using a CAS so it will only be - set if in a state in which waiting would be possible). In the case of - __writers_futex, we wake only one thread but several threads may share - PTHREAD_RWLOCK_FUTEX_USED, so we must assume that there are still others. - This is similar to what we do in pthread_mutex_lock. We do not need to - do this for __wrphase_futex because there, we always wake all waiting - threads. - - Blocking in the state #4a simply uses __readers as futex word. This - simplifies the algorithm but suffers from some of the drawbacks discussed - before, though not to the same extent because R can only decrease in this - state, so the number of potentially failing futex_wait attempts will be - bounded. All threads moving from state #4a to another state must wake - up threads blocked on the __readers futex. - - The ordering invariants that we have to take care of in the implementation - are primarily those necessary for a reader--writer lock; this is rather - straightforward and happens during write/read phase switching (potentially - through explicit hand-over), and between writers through synchronization - involving the PTHREAD_RWLOCK_WRLOCKED or PTHREAD_RWLOCK_WRHANDOVER bits. - Additionally, we need to take care that modifications of __writers_futex - and __wrphase_futex (e.g., by otherwise unordered readers) take place in - the writer critical sections or read/write phases, respectively, and that - explicit hand-over observes stores from the previous phase. How this is - done is explained in more detail in comments in the code. - - Many of the accesses to the futex words just need relaxed MO. This is - possible because we essentially drive both the core rwlock synchronization - and the futex synchronization in parallel. For example, an unlock will - unlock the rwlock and take part in the futex synchronization (using - PTHREAD_RWLOCK_FUTEX_USED, see above); even if they are not tightly - ordered in some way, the futex synchronization ensures that there are no - lost wake-ups, and woken threads will then eventually see the most recent - state of the rwlock. IOW, waiting threads will always be woken up, while - not being able to wait using futexes (which can happen) is harmless; in - turn, this means that waiting threads don't need special ordering wrt. - waking threads. - - The futex synchronization consists of the three-state futex word: - (1) cannot block on it, (2) can block on it, and (3) there might be a - thread blocked on it (i.e., with PTHREAD_RWLOCK_FUTEX_USED set). - Relaxed-MO atomic read-modify-write operations are sufficient to maintain - this (e.g., using a CAS to go from (2) to (3) but not from (1) to (3)), - but we need ordering of the futex word modifications by the waking threads - so that they collectively make correct state changes between (1)-(3). - The futex-internal synchronization (i.e., the conceptual critical sections - around futex operations in the kernel) then ensures that even an - unconstrained load (i.e., relaxed MO) inside of futex_wait will not lead to - lost wake-ups because either the waiting thread will see the change from - (3) to (1) when a futex_wake came first, or this futex_wake will wake this - waiting thread because the waiting thread came first. - - - POSIX allows but does not require rwlock acquisitions to be a cancellation - point. We do not support cancellation. - - TODO We do not try to elide any read or write lock acquisitions currently. - While this would be possible, it is unclear whether HTM performance is - currently predictable enough and our runtime tuning is good enough at - deciding when to use elision so that enabling it would lead to consistently - better performance. */ - - -static int -__pthread_rwlock_get_private (pthread_rwlock_t *rwlock) -{ - return rwlock->__data.__shared != 0 ? FUTEX_SHARED : FUTEX_PRIVATE; -} - -static __always_inline void -__pthread_rwlock_rdunlock (pthread_rwlock_t *rwlock) -{ - int private = __pthread_rwlock_get_private (rwlock); - /* We decrease the number of readers, and if we are the last reader and - there is a primary writer, we start a write phase. We use a CAS to - make this atomic so that it is clear whether we must hand over ownership - explicitly. */ - unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers); - unsigned int rnew; - for (;;) - { - rnew = r - (1 << PTHREAD_RWLOCK_READER_SHIFT); - /* If we are the last reader, we also need to unblock any readers - that are waiting for a writer to go first (PTHREAD_RWLOCK_RWAITING) - so that they can register while the writer is active. */ - if ((rnew >> PTHREAD_RWLOCK_READER_SHIFT) == 0) - { - if ((rnew & PTHREAD_RWLOCK_WRLOCKED) != 0) - rnew |= PTHREAD_RWLOCK_WRPHASE; - rnew &= ~(unsigned int) PTHREAD_RWLOCK_RWAITING; - } - /* We need release MO here for three reasons. First, so that we - synchronize with subsequent writers. Second, we might have been the - first reader and set __wrphase_futex to 0, so we need to synchronize - with the last reader that will set it to 1 (note that we will always - change __readers before the last reader, or we are the last reader). - Third, a writer that takes part in explicit hand-over needs to see - the first reader's store to __wrphase_futex (or a later value) if - the writer observes that a write phase has been started. */ - if (atomic_compare_exchange_weak_release (&rwlock->__data.__readers, - &r, rnew)) - break; - /* TODO Back-off. */ - } - if ((rnew & PTHREAD_RWLOCK_WRPHASE) != 0) - { - /* We need to do explicit hand-over. We need the acquire MO fence so - that our modification of _wrphase_futex happens after a store by - another reader that started a read phase. Relaxed MO is sufficient - for the modification of __wrphase_futex because it is just used - to delay acquisition by a writer until all threads are unblocked - irrespective of whether they are looking at __readers or - __wrphase_futex; any other synchronizes-with relations that are - necessary are established through __readers. */ - atomic_thread_fence_acquire (); - if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 1) - & PTHREAD_RWLOCK_FUTEX_USED) != 0) - futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private); - } - /* Also wake up waiting readers if we did reset the RWAITING flag. */ - if ((r & PTHREAD_RWLOCK_RWAITING) != (rnew & PTHREAD_RWLOCK_RWAITING)) - futex_wake (&rwlock->__data.__readers, INT_MAX, private); -} - - -static __always_inline int -__pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock, - const struct timespec *abstime) -{ - unsigned int r; - - /* Make sure we are not holding the rwlock as a writer. This is a deadlock - situation we recognize and report. */ - if (__glibc_unlikely (atomic_load_relaxed (&rwlock->__data.__cur_writer) - == THREAD_GETMEM (THREAD_SELF, tid))) - return EDEADLK; - - /* If we prefer writers, recursive rdlock is disallowed, we are in a read - phase, and there are other readers present, we try to wait without - extending the read phase. We will be unblocked by either one of the - other active readers, or if the writer gives up WRLOCKED (e.g., on - timeout). - If there are no other readers, we simply race with any existing primary - writer; it would have been a race anyway, and changing the odds slightly - will likely not make a big difference. */ - if (rwlock->__data.__flags == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP) - { - r = atomic_load_relaxed (&rwlock->__data.__readers); - while (((r & PTHREAD_RWLOCK_WRPHASE) == 0) - && ((r & PTHREAD_RWLOCK_WRLOCKED) != 0) - && ((r >> PTHREAD_RWLOCK_READER_SHIFT) > 0)) - { - /* TODO Spin first. */ - /* Try setting the flag signaling that we are waiting without having - incremented the number of readers. Relaxed MO is fine because - this is just about waiting for a state change in __readers. */ - if (atomic_compare_exchange_weak_relaxed - (&rwlock->__data.__readers, &r, r | PTHREAD_RWLOCK_RWAITING)) - { - /* Wait for as long as the flag is set. An ABA situation is - harmless because the flag is just about the state of - __readers, and all threads set the flag under the same - conditions. */ - while ((atomic_load_relaxed (&rwlock->__data.__readers) - & PTHREAD_RWLOCK_RWAITING) != 0) - { - int private = __pthread_rwlock_get_private (rwlock); - int err = futex_abstimed_wait (&rwlock->__data.__readers, - r, abstime, private); - /* We ignore EAGAIN and EINTR. On time-outs, we can just - return because we don't need to clean up anything. */ - if (err == ETIMEDOUT) - return err; - } - /* It makes sense to not break out of the outer loop here - because we might be in the same situation again. */ - } - else - { - /* TODO Back-off. */ - } - } - } - /* Register as a reader, using an add-and-fetch so that R can be used as - expected value for future operations. Acquire MO so we synchronize with - prior writers as well as the last reader of the previous read phase (see - below). */ - r = atomic_fetch_add_acquire (&rwlock->__data.__readers, - (1 << PTHREAD_RWLOCK_READER_SHIFT)) + (1 << PTHREAD_RWLOCK_READER_SHIFT); - - /* Check whether there is an overflow in the number of readers. We assume - that the total number of threads is less than half the maximum number - of readers that we have bits for in __readers (i.e., with 32-bit int and - PTHREAD_RWLOCK_READER_SHIFT of 3, we assume there are less than - 1 << (32-3-1) concurrent threads). - If there is an overflow, we use a CAS to try to decrement the number of - readers if there still is an overflow situation. If so, we return - EAGAIN; if not, we are not a thread causing an overflow situation, and so - we just continue. Using a fetch-add instead of the CAS isn't possible - because other readers might release the lock concurrently, which could - make us the last reader and thus responsible for handing ownership over - to writers (which requires a CAS too to make the decrement and ownership - transfer indivisible). */ - while (__glibc_unlikely (r >= PTHREAD_RWLOCK_READER_OVERFLOW)) - { - /* Relaxed MO is okay because we just want to undo our registration and - cannot have changed the rwlock state substantially if the CAS - succeeds. */ - if (atomic_compare_exchange_weak_relaxed (&rwlock->__data.__readers, &r, - r - (1 << PTHREAD_RWLOCK_READER_SHIFT))) - return EAGAIN; - } - - /* We have registered as a reader, so if we are in a read phase, we have - acquired a read lock. This is also the reader--reader fast-path. - Even if there is a primary writer, we just return. If writers are to - be preferred and we are the only active reader, we could try to enter a - write phase to let the writer proceed. This would be okay because we - cannot have acquired the lock previously as a reader (which could result - in deadlock if we would wait for the primary writer to run). However, - this seems to be a corner case and handling it specially not be worth the - complexity. */ - if (__glibc_likely ((r & PTHREAD_RWLOCK_WRPHASE) == 0)) - return 0; - - /* If there is no primary writer but we are in a write phase, we can try - to install a read phase ourself. */ - while (((r & PTHREAD_RWLOCK_WRPHASE) != 0) - && ((r & PTHREAD_RWLOCK_WRLOCKED) == 0)) - { - /* Try to enter a read phase: If the CAS below succeeds, we have - ownership; if it fails, we will simply retry and reassess the - situation. - Acquire MO so we synchronize with prior writers. */ - if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers, &r, - r ^ PTHREAD_RWLOCK_WRPHASE)) - { - /* We started the read phase, so we are also responsible for - updating the write-phase futex. Relaxed MO is sufficient. - Note that there can be no other reader that we have to wake - because all other readers will see the read phase started by us - (or they will try to start it themselves); if a writer started - the read phase, we cannot have started it. Furthermore, we - cannot discard a PTHREAD_RWLOCK_FUTEX_USED flag because we will - overwrite the value set by the most recent writer (or the readers - before it in case of explicit hand-over) and we know that there - are no waiting readers. */ - atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 0); - return 0; - } - else - { - /* TODO Back off before retrying. Also see above. */ - } - } - - if ((r & PTHREAD_RWLOCK_WRPHASE) != 0) - { - /* We are in a write phase, and there must be a primary writer because - of the previous loop. Block until the primary writer gives up the - write phase. This case requires explicit hand-over using - __wrphase_futex. - However, __wrphase_futex might not have been set to 1 yet (either - because explicit hand-over to the writer is still ongoing, or because - the writer has started the write phase but does not yet have updated - __wrphase_futex). The least recent value of __wrphase_futex we can - read from here is the modification of the last read phase (because - we synchronize with the last reader in this read phase through - __readers; see the use of acquire MO on the fetch_add above). - Therefore, if we observe a value of 0 for __wrphase_futex, we need - to subsequently check that __readers now indicates a read phase; we - need to use acquire MO for this so that if we observe a read phase, - we will also see the modification of __wrphase_futex by the previous - writer. We then need to load __wrphase_futex again and continue to - wait if it is not 0, so that we do not skip explicit hand-over. - Relaxed MO is sufficient for the load from __wrphase_futex because - we just use it as an indicator for when we can proceed; we use - __readers and the acquire MO accesses to it to eventually read from - the proper stores to __wrphase_futex. */ - unsigned int wpf; - bool ready = false; - for (;;) - { - while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex)) - | PTHREAD_RWLOCK_FUTEX_USED) == (1 | PTHREAD_RWLOCK_FUTEX_USED)) - { - int private = __pthread_rwlock_get_private (rwlock); - if (((wpf & PTHREAD_RWLOCK_FUTEX_USED) == 0) - && !atomic_compare_exchange_weak_relaxed - (&rwlock->__data.__wrphase_futex, - &wpf, wpf | PTHREAD_RWLOCK_FUTEX_USED)) - continue; - int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex, - 1 | PTHREAD_RWLOCK_FUTEX_USED, abstime, private); - if (err == ETIMEDOUT) - { - /* If we timed out, we need to unregister. If no read phase - has been installed while we waited, we can just decrement - the number of readers. Otherwise, we just acquire the - lock, which is allowed because we give no precise timing - guarantees, and because the timeout is only required to - be in effect if we would have had to wait for other - threads (e.g., if futex_wait would time-out immediately - because the given absolute time is in the past). */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - while ((r & PTHREAD_RWLOCK_WRPHASE) != 0) - { - /* We don't need to make anything else visible to - others besides unregistering, so relaxed MO is - sufficient. */ - if (atomic_compare_exchange_weak_relaxed - (&rwlock->__data.__readers, &r, - r - (1 << PTHREAD_RWLOCK_READER_SHIFT))) - return ETIMEDOUT; - /* TODO Back-off. */ - } - /* Use the acquire MO fence to mirror the steps taken in the - non-timeout case. Note that the read can happen both - in the atomic_load above as well as in the failure case - of the CAS operation. */ - atomic_thread_fence_acquire (); - /* We still need to wait for explicit hand-over, but we must - not use futex_wait anymore because we would just time out - in this case and thus make the spin-waiting we need - unnecessarily expensive. */ - while ((atomic_load_relaxed (&rwlock->__data.__wrphase_futex) - | PTHREAD_RWLOCK_FUTEX_USED) - == (1 | PTHREAD_RWLOCK_FUTEX_USED)) - { - /* TODO Back-off? */ - } - ready = true; - break; - } - /* If we got interrupted (EINTR) or the futex word does not have the - expected value (EAGAIN), retry. */ - } - if (ready) - /* See below. */ - break; - /* We need acquire MO here so that we synchronize with the lock - release of the writer, and so that we observe a recent value of - __wrphase_futex (see below). */ - if ((atomic_load_acquire (&rwlock->__data.__readers) - & PTHREAD_RWLOCK_WRPHASE) == 0) - /* We are in a read phase now, so the least recent modification of - __wrphase_futex we can read from is the store by the writer - with value 1. Thus, only now we can assume that if we observe - a value of 0, explicit hand-over is finished. Retry the loop - above one more time. */ - ready = true; - } - } - - return 0; -} - - -static __always_inline void -__pthread_rwlock_wrunlock (pthread_rwlock_t *rwlock) -{ - int private = __pthread_rwlock_get_private (rwlock); - - atomic_store_relaxed (&rwlock->__data.__cur_writer, 0); - /* Disable waiting by writers. We will wake up after we decided how to - proceed. */ - bool wake_writers = ((atomic_exchange_relaxed - (&rwlock->__data.__writers_futex, 0) & PTHREAD_RWLOCK_FUTEX_USED) != 0); - - if (rwlock->__data.__flags != PTHREAD_RWLOCK_PREFER_READER_NP) - { - /* First, try to hand over to another writer. */ - unsigned int w = atomic_load_relaxed (&rwlock->__data.__writers); - while (w != 0) - { - /* Release MO so that another writer that gets WRLOCKED from us will - synchronize with us and thus can take over our view of - __readers (including, for example, whether we are in a write - phase or not). */ - if (atomic_compare_exchange_weak_release (&rwlock->__data.__writers, - &w, w | PTHREAD_RWLOCK_WRHANDOVER)) - /* Another writer will take over. */ - goto done; - /* TODO Back-off. */ - } - } - - /* We have done everything we needed to do to prefer writers, so now we - either hand over explicitly to readers if there are any, or we simply - stay in a write phase. See pthread_rwlock_rdunlock for more details. */ - unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers); - /* Release MO so that subsequent readers or writers synchronize with us. */ - while (!atomic_compare_exchange_weak_release - (&rwlock->__data.__readers, &r, (r ^ PTHREAD_RWLOCK_WRLOCKED) - ^ ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0 ? 0 - : PTHREAD_RWLOCK_WRPHASE))) - { - /* TODO Back-off. */ - } - if ((r >> PTHREAD_RWLOCK_READER_SHIFT) != 0) - { - /* We must hand over explicitly through __wrphase_futex. Relaxed MO is - sufficient because it is just used to delay acquisition by a writer; - any other synchronizes-with relations that are necessary are - established through __readers. */ - if ((atomic_exchange_relaxed (&rwlock->__data.__wrphase_futex, 0) - & PTHREAD_RWLOCK_FUTEX_USED) != 0) - futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private); - } - - done: - /* We released WRLOCKED in some way, so wake a writer. */ - if (wake_writers) - futex_wake (&rwlock->__data.__writers_futex, 1, private); -} - - -static __always_inline int -__pthread_rwlock_wrlock_full (pthread_rwlock_t *rwlock, - const struct timespec *abstime) -{ - /* Make sure we are not holding the rwlock as a writer. This is a deadlock - situation we recognize and report. */ - if (__glibc_unlikely (atomic_load_relaxed (&rwlock->__data.__cur_writer) - == THREAD_GETMEM (THREAD_SELF, tid))) - return EDEADLK; - - /* First we try to acquire the role of primary writer by setting WRLOCKED; - if it was set before, there already is a primary writer. Acquire MO so - that we synchronize with previous primary writers. - - We do not try to change to a write phase right away using a fetch_or - because we would have to reset it again and wake readers if there are - readers present (some readers could try to acquire the lock more than - once, so setting a write phase in the middle of this could cause - deadlock). Changing to a write phase eagerly would only speed up the - transition from a read phase to a write phase in the uncontended case, - but it would slow down the contended case if readers are preferred (which - is the default). - We could try to CAS from a state with no readers to a write phase, but - this could be less scalable if readers arrive and leave frequently. */ - bool may_share_futex_used_flag = false; - unsigned int r = atomic_fetch_or_acquire (&rwlock->__data.__readers, - PTHREAD_RWLOCK_WRLOCKED); - if (__glibc_unlikely ((r & PTHREAD_RWLOCK_WRLOCKED) != 0)) - { - /* There is another primary writer. */ - bool prefer_writer = - (rwlock->__data.__flags != PTHREAD_RWLOCK_PREFER_READER_NP); - if (prefer_writer) - { - /* We register as a waiting writer, so that we can make use of - writer--writer hand-over. Relaxed MO is fine because we just - want to register. We assume that the maximum number of threads - is less than the capacity in __writers. */ - atomic_fetch_add_relaxed (&rwlock->__data.__writers, 1); - } - for (;;) - { - /* TODO Spin until WRLOCKED is 0 before trying the CAS below. - But pay attention to not delay trying writer--writer hand-over - for too long (which we must try eventually anyway). */ - if ((r & PTHREAD_RWLOCK_WRLOCKED) == 0) - { - /* Try to become the primary writer or retry. Acquire MO as in - the fetch_or above. */ - if (atomic_compare_exchange_weak_acquire - (&rwlock->__data.__readers, &r, - r | PTHREAD_RWLOCK_WRLOCKED)) - { - if (prefer_writer) - { - /* Unregister as a waiting writer. Note that because we - acquired WRLOCKED, WRHANDOVER will not be set. - Acquire MO on the CAS above ensures that - unregistering happens after the previous writer; - this sorts the accesses to __writers by all - primary writers in a useful way (e.g., any other - primary writer acquiring after us or getting it from - us through WRHANDOVER will see both our changes to - __writers). - ??? Perhaps this is not strictly necessary for - reasons we do not yet know of. */ - atomic_fetch_add_relaxed (&rwlock->__data.__writers, - -1); - } - break; - } - /* Retry if the CAS fails (r will have been updated). */ - continue; - } - /* If writer--writer hand-over is available, try to become the - primary writer this way by grabbing the WRHANDOVER token. If we - succeed, we own WRLOCKED. */ - if (prefer_writer) - { - unsigned int w = atomic_load_relaxed - (&rwlock->__data.__writers); - if ((w & PTHREAD_RWLOCK_WRHANDOVER) != 0) - { - /* Acquire MO is required here so that we synchronize with - the writer that handed over WRLOCKED. We also need this - for the reload of __readers below because our view of - __readers must be at least as recent as the view of the - writer that handed over WRLOCKED; we must avoid an ABA - through WRHANDOVER, which could, for example, lead to us - assuming we are still in a write phase when in fact we - are not. */ - if (atomic_compare_exchange_weak_acquire - (&rwlock->__data.__writers, - &w, (w - PTHREAD_RWLOCK_WRHANDOVER - 1))) - { - /* Reload so our view is consistent with the view of - the previous owner of WRLOCKED. See above. */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - break; - } - /* We do not need to reload __readers here. We should try - to perform writer--writer hand-over if possible; if it - is not possible anymore, we will reload __readers - elsewhere in this loop. */ - continue; - } - } - /* We did not acquire WRLOCKED nor were able to use writer--writer - hand-over, so we block on __writers_futex. */ - int private = __pthread_rwlock_get_private (rwlock); - unsigned int wf = atomic_load_relaxed - (&rwlock->__data.__writers_futex); - if (((wf & ~(unsigned int) PTHREAD_RWLOCK_FUTEX_USED) != 1) - || ((wf != (1 | PTHREAD_RWLOCK_FUTEX_USED)) - && !atomic_compare_exchange_weak_relaxed - (&rwlock->__data.__writers_futex, &wf, - 1 | PTHREAD_RWLOCK_FUTEX_USED))) - { - /* If we cannot block on __writers_futex because there is no - primary writer, or we cannot set PTHREAD_RWLOCK_FUTEX_USED, - we retry. We must reload __readers here in case we cannot - block on __writers_futex so that we can become the primary - writer and are not stuck in a loop that just continuously - fails to block on __writers_futex. */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - continue; - } - /* We set the flag that signals that the futex is used, or we could - have set it if we had been faster than other waiters. As a - result, we may share the flag with an unknown number of other - writers. Therefore, we must keep this flag set when we acquire - the lock. We do not need to do this when we do not reach this - point here because then we are not part of the group that may - share the flag, and another writer will wake one of the writers - in this group. */ - may_share_futex_used_flag = true; - int err = futex_abstimed_wait (&rwlock->__data.__writers_futex, - 1 | PTHREAD_RWLOCK_FUTEX_USED, abstime, private); - if (err == ETIMEDOUT) - { - if (prefer_writer) - { - /* We need to unregister as a waiting writer. If we are the - last writer and writer--writer hand-over is available, - we must make use of it because nobody else will reset - WRLOCKED otherwise. (If we use it, we simply pretend - that this happened before the timeout; see - pthread_rwlock_rdlock_full for the full reasoning.) - Also see the similar code above. */ - unsigned int w = atomic_load_relaxed - (&rwlock->__data.__writers); - while (!atomic_compare_exchange_weak_acquire - (&rwlock->__data.__writers, &w, - (w == PTHREAD_RWLOCK_WRHANDOVER + 1 ? 0 : w - 1))) - { - /* TODO Back-off. */ - } - if (w == PTHREAD_RWLOCK_WRHANDOVER + 1) - { - /* We must continue as primary writer. See above. */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - break; - } - } - /* We cleaned up and cannot have stolen another waiting writer's - futex wake-up, so just return. */ - return ETIMEDOUT; - } - /* If we got interrupted (EINTR) or the futex word does not have the - expected value (EAGAIN), retry after reloading __readers. */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - } - /* Our snapshot of __readers is up-to-date at this point because we - either set WRLOCKED using a CAS or were handed over WRLOCKED from - another writer whose snapshot of __readers we inherit. */ - } - - /* If we are in a read phase and there are no readers, try to start a write - phase. */ - while (((r & PTHREAD_RWLOCK_WRPHASE) == 0) - && ((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0)) - { - /* Acquire MO so that we synchronize with prior writers and do - not interfere with their updates to __writers_futex, as well - as regarding prior readers and their updates to __wrphase_futex, - respectively. */ - if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers, - &r, r | PTHREAD_RWLOCK_WRPHASE)) - { - /* We have started a write phase, so need to enable readers to wait. - See the similar case in__pthread_rwlock_rdlock_full. */ - atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1); - /* Make sure we fall through to the end of the function. */ - r |= PTHREAD_RWLOCK_WRPHASE; - break; - } - /* TODO Back-off. */ - } - - /* We are the primary writer; enable blocking on __writers_futex. Relaxed - MO is sufficient for futex words; acquire MO on the previous - modifications of __readers ensures that this store happens after the - store of value 0 by the previous primary writer. */ - atomic_store_relaxed (&rwlock->__data.__writers_futex, - 1 | (may_share_futex_used_flag ? PTHREAD_RWLOCK_FUTEX_USED : 0)); - - if (__glibc_unlikely ((r & PTHREAD_RWLOCK_WRPHASE) == 0)) - { - /* We are not in a read phase and there are readers (because of the - previous loop). Thus, we have to wait for explicit hand-over from - one of these readers. - We basically do the same steps as for the similar case in - __pthread_rwlock_rdlock_full, except that we additionally might try - to directly hand over to another writer and need to wake up - other writers or waiting readers (i.e., PTHREAD_RWLOCK_RWAITING). */ - unsigned int wpf; - bool ready = false; - for (;;) - { - while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex)) - | PTHREAD_RWLOCK_FUTEX_USED) == PTHREAD_RWLOCK_FUTEX_USED) - { - int private = __pthread_rwlock_get_private (rwlock); - if (((wpf & PTHREAD_RWLOCK_FUTEX_USED) == 0) - && !atomic_compare_exchange_weak_relaxed - (&rwlock->__data.__wrphase_futex, &wpf, - PTHREAD_RWLOCK_FUTEX_USED)) - continue; - int err = futex_abstimed_wait (&rwlock->__data.__wrphase_futex, - PTHREAD_RWLOCK_FUTEX_USED, abstime, private); - if (err == ETIMEDOUT) - { - if (rwlock->__data.__flags - != PTHREAD_RWLOCK_PREFER_READER_NP) - { - /* We try writer--writer hand-over. */ - unsigned int w = atomic_load_relaxed - (&rwlock->__data.__writers); - if (w != 0) - { - /* We are about to hand over WRLOCKED, so we must - release __writers_futex too; otherwise, we'd have - a pending store, which could at least prevent - other threads from waiting using the futex - because it could interleave with the stores - by subsequent writers. In turn, this means that - we have to clean up when we do not hand over - WRLOCKED. - Release MO so that another writer that gets - WRLOCKED from us can take over our view of - __readers. */ - unsigned int wf = atomic_exchange_relaxed - (&rwlock->__data.__writers_futex, 0); - while (w != 0) - { - if (atomic_compare_exchange_weak_release - (&rwlock->__data.__writers, &w, - w | PTHREAD_RWLOCK_WRHANDOVER)) - { - /* Wake other writers. */ - if ((wf & PTHREAD_RWLOCK_FUTEX_USED) != 0) - futex_wake - (&rwlock->__data.__writers_futex, 1, - private); - return ETIMEDOUT; - } - /* TODO Back-off. */ - } - /* We still own WRLOCKED and someone else might set - a write phase concurrently, so enable waiting - again. Make sure we don't loose the flag that - signals whether there are threads waiting on - this futex. */ - atomic_store_relaxed - (&rwlock->__data.__writers_futex, wf); - } - } - /* If we timed out and we are not in a write phase, we can - just stop being a primary writer. Otherwise, we just - acquire the lock. */ - r = atomic_load_relaxed (&rwlock->__data.__readers); - if ((r & PTHREAD_RWLOCK_WRPHASE) == 0) - { - /* We are about to release WRLOCKED, so we must release - __writers_futex too; see the handling of - writer--writer hand-over above. */ - unsigned int wf = atomic_exchange_relaxed - (&rwlock->__data.__writers_futex, 0); - while ((r & PTHREAD_RWLOCK_WRPHASE) == 0) - { - /* While we don't need to make anything from a - caller's critical section visible to other - threads, we need to ensure that our changes to - __writers_futex are properly ordered. - Therefore, use release MO to synchronize with - subsequent primary writers. Also wake up any - waiting readers as they are waiting because of - us. */ - if (atomic_compare_exchange_weak_release - (&rwlock->__data.__readers, &r, - (r ^ PTHREAD_RWLOCK_WRLOCKED) - & ~(unsigned int) PTHREAD_RWLOCK_RWAITING)) - { - /* Wake other writers. */ - if ((wf & PTHREAD_RWLOCK_FUTEX_USED) != 0) - futex_wake (&rwlock->__data.__writers_futex, - 1, private); - /* Wake waiting readers. */ - if ((r & PTHREAD_RWLOCK_RWAITING) != 0) - futex_wake (&rwlock->__data.__readers, - INT_MAX, private); - return ETIMEDOUT; - } - } - /* We still own WRLOCKED and someone else might set a - write phase concurrently, so enable waiting again. - Make sure we don't loose the flag that signals - whether there are threads waiting on this futex. */ - atomic_store_relaxed (&rwlock->__data.__writers_futex, - wf); - } - /* Use the acquire MO fence to mirror the steps taken in the - non-timeout case. Note that the read can happen both - in the atomic_load above as well as in the failure case - of the CAS operation. */ - atomic_thread_fence_acquire (); - /* We still need to wait for explicit hand-over, but we must - not use futex_wait anymore. */ - while ((atomic_load_relaxed - (&rwlock->__data.__wrphase_futex) - | PTHREAD_RWLOCK_FUTEX_USED) - == PTHREAD_RWLOCK_FUTEX_USED) - { - /* TODO Back-off. */ - } - ready = true; - break; - } - /* If we got interrupted (EINTR) or the futex word does not have - the expected value (EAGAIN), retry. */ - } - /* See pthread_rwlock_rdlock_full. */ - if (ready) - break; - if ((atomic_load_acquire (&rwlock->__data.__readers) - & PTHREAD_RWLOCK_WRPHASE) != 0) - ready = true; - } - } - - atomic_store_relaxed (&rwlock->__data.__cur_writer, - THREAD_GETMEM (THREAD_SELF, tid)); - return 0; -} |