rwsem: fix rwsem_is_locked() bugs
Subsystems (2)
PATCH v3 1/1 rwsem: fix rwsem_is_locked() bugs
rwsem_is_locked() tests ->activity without locks, so we should always keep ->activity consistent. However, the code in __rwsem_do_wake() breaks this rule, it updates ->activity after _all_ readers waken up, this may give some reader a wrong ->activity value, thus cause rwsem_is_locked() behaves wrong.
Quote from Andrew:
"
- we have one or more processes sleeping in down_read(), waiting for access.
- we wake one or more processes up without altering ->activity
- they start to run and they do rwsem_is_locked(). This incorrectly returns "false", because the waker process is still crunching away in __rwsem_do_wake().
- the waker now alters ->activity, but it was too late.
And the patch fixes this by updating ->activity prior to waking the sleeping processes. So when they run, they'll see a non-zero value of ->activity.
"
Also, we have more problems, as pointed by David:
"... the case where the active readers run out, but there's a writer on the queue (see __up_read()), nor the case where the active writer ends, but there's a waiter on the queue (see __up_write()). In both cases, the lock is still held, though sem->activity is 0."
This patch fixes this too.
David also said we may have "the potential to cause more cacheline ping-pong under contention", but "this change shouldn't cause a significant slowdown."
With this patch applied, I can't trigger that bug any more.
---
include/linux/rwsem-spinlock.h +8 -1
@@ -71,7 +71,14 @@ extern void __downgrade_write(struct rw_semaphore *sem);static inline int rwsem_is_locked (struct rw_semaphore *sem) { -return (sem->activity !=0 ); +int ret; + +if (spin_trylock_irq (&sem->wait_lock)) { + ret = !(list_empty (&sem->wait_list) && sem->activity ==0 ); +spin_unlock_irq (&sem->wait_lock); +return ret; + } +return 1 ; }#endif /* __KERNEL__ */
lib/rwsem-spinlock.c +7 -2
@@ -78,7 +78,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)/* grant an infinite number of read locks to the front of the queue */ dont_wake_writers: - woken =0 ; +/* +* we increase ->activity just to make rwsem_is_locked() happy, +* to avoid potential cache line ping-pong, we don't do this +* within the following loop. +*/ + woken = sem->activity++;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next;
@@ -94,7 +99,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; + sem->activity = woken; out:return sem;
David, any comments on this version? :)
Thanks.
Quoted 91 lines · Amerigo Wang
rwsem_is_locked()tests ->activity without locks, so we should always keep ->activity consistent. However, the code in__rwsem_do_wake()breaks this rule, it updates ->activity after _all_ readers waken up, this may give some reader a wrong ->activity value, thus causerwsem_is_locked()behaves wrong.Quote from Andrew:
"
- we have one or more processes sleeping indown_read(), waiting for access.- we wake one or more processes up without altering ->activity
- they start to run and they do
rwsem_is_locked(). This incorrectly returns "false", because the waker process is still crunching away in__rwsem_do_wake().- the waker now alters ->activity, but it was too late.
And the patch fixes this by updating ->activity prior to waking the sleeping processes. So when they run, they'll see a non-zero value of ->activity.
"Also, we have more problems, as pointed by David:
"... the case where the active readers run out, but there's a writer on the queue (see
__up_read()), nor the case where the active writer ends, but there's a waiter on the queue (see__up_write()). In both cases, the lock is still held, thoughsem->activityis 0."This patch fixes this too.
David also said we may have "the potential to cause more cacheline ping-pong under contention", but "this change shouldn't cause a significant slowdown."
With this patch applied, I can't trigger that bug any more.
Reported-by Brian Behlendorf <[email protected]>Cc Ben Woodard <[email protected]>Cc David Howells <[email protected]>Signed-off-by WANG Cong <[email protected]>---
include/linux/rwsem-spinlock.h +8
-1@@ -71,7 +71,14 @@ extern void __downgrade_write(struct rw_semaphore *sem);static inline int rwsem_is_locked (struct rw_semaphore *sem) { -return (sem->activity !=0 ); +int ret; + +if (spin_trylock_irq (&sem->wait_lock)) { + ret = !(list_empty (&sem->wait_list) && sem->activity ==0 ); +spin_unlock_irq (&sem->wait_lock); +return ret; + } +return 1 ; }#endif /* __KERNEL__ */ lib/rwsem-spinlock.c +7
-2@@ -78,7 +78,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)/* grant an infinite number of read locks to the front of the queue */ dont_wake_writers: - woken =0 ; +/* +* we increase ->activity just to make rwsem_is_locked() happy, +* to avoid potential cache line ping-pong, we don't do this +* within the following loop. +*/ + woken = sem->activity++;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next;@@ -94,7 +99,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; + sem->activity = woken; out:return sem;
include/linux/rwsem-spinlock.h extern void __downgrade_write(struct rw_semaphore *sem); · line 82
Quoted 12 lines · Amerigo Wang
static inline int
rwsem_is_locked(struct rw_semaphore *sem){include/linux/rwsem-spinlock.h +8
-1-return (sem->activity !=0 ); +int ret; + +if (spin_trylock_irq (&sem->wait_lock)) { + ret = !(list_empty (&sem->wait_list) && sem->activity ==0 ); +spin_unlock_irq (&sem->wait_lock); +return ret; + } +return 1 ; }
Yep... This seems a reasonable approach, though I contend that if you're holding the spinlock, then sem->wait_list _must_ be empty if sem->activity is 0 - so that half of the test is redundant.
sem->activity == 0 and sem->wait_list not being empty is a transitional state that can only occur in ups and downgrades whilst they hold the spinlock.
Quoted 19 lines
lib/rwsem-spinlock.c +6
-1@@ -78,7 +78,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)/* grant an infinite number of read locks to the front of the queue */ dont_wake_writers: - woken =0 ; +/* +* we increase ->activity just to make rwsem_is_locked() happy, +* to avoid potential cache line ping-pong, we don't do this +* within the following loop. +*/ + woken = sem->activity++;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next;
lib/rwsem-spinlock.c __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) · line 105
Quoted 8 lines
lib/rwsem-spinlock.c +1
-1@@ -94,7 +99,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; + sem->activity = woken; out:return sem;
This change to __rwsem_do_wake() is all unnecessary - you're defending against the test of sem->activity by rwsem_is_locked() - but that now happens with the spinlock held.
David
Quoted 19 lines · David Howells
include/linux/rwsem-spinlock.h extern void __downgrade_write(struct rw_semaphore *sem); · line 82
Quoted 12 lines · Amerigo Wang
static inline int
rwsem_is_locked(struct rw_semaphore *sem){include/linux/rwsem-spinlock.h +8
-1-return (sem->activity !=0 ); +int ret; + +if (spin_trylock_irq (&sem->wait_lock)) { + ret = !(list_empty (&sem->wait_list) && sem->activity ==0 ); +spin_unlock_irq (&sem->wait_lock); +return ret; + } +return 1 ; }Yep... This seems a reasonable approach, though I contend that if you're holding the spinlock, then
sem->wait_list_must_ be empty ifsem->activityis 0 - so that half of the test is redundant.
Quoted 3 lines
sem->activity== 0 andsem->wait_listnot being empty is a transitional state that can only occur in ups and downgrades whilst they hold the spinlock.
Hmm, yeah...
Quoted 25 lines
Quoted 25 lines
lib/rwsem-spinlock.c +7
-2@@ -78,7 +78,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)/* grant an infinite number of read locks to the front of the queue */ dont_wake_writers: - woken =0 ; +/* +* we increase ->activity just to make rwsem_is_locked() happy, +* to avoid potential cache line ping-pong, we don't do this +* within the following loop. +*/ + woken = sem->activity++;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next;@@ -94,7 +99,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; + sem->activity = woken;
Quoted 6 lines
lib/rwsem-spinlock.c __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) · line 105
Quoted 2 lines
lib/rwsem-spinlock.c +0
-0out:return sem;This change to
__rwsem_do_wake()is all unnecessary - you're defending against the test ofsem->activitybyrwsem_is_locked()- but that now happens with the spinlock held.
Ah, yes, I knew this, I kept this just for completeness. I will remove this part then. :)
THanks!