rwsem: fix rwsem_is_locked() bug
PATCH 1/1 rwsem: fix rwsem_is_locked() bug
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.
Brian has a kernel module to reproduce this, I can include it if any of you need. Of course, with Brian's approval.
With this patch applied, I can't trigger that bug any more.
---
lib/rwsem-spinlock.c +1 -5
@@ -49,7 +49,6 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) {struct rwsem_waiter *waiter;struct task_struct *tsk; -int woken; waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
@@ -78,24 +77,21 @@ __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 ;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next; + sem->activity++;list_del (&waiter->list); tsk = waiter->task;smp_mb (); waiter->task =NULL ;wake_up_process (tsk);put_task_struct (tsk); - woken++;if (list_empty (&sem->wait_list))break ; waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; - out:return sem; }
Andrew Morton
maintainerQuoted 7 lines · On Tue, 29 Sep 2009 23:19:02 -0400 Amerigo Wang <[email protected]> wrote:
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.
Quoted 5 lines
Brian has a kernel module to reproduce this, I can include it if any of you need. Of course, with Brian's approval.
With this patch applied, I can't trigger that bug any more.
Changelog doesn't describe the bug well.
Quoted 30 lines
---
lib/rwsem-spinlock.c +1
-3@@ -49,7 +49,6 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) {struct rwsem_waiter *waiter;struct task_struct *tsk; -int woken; waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);@@ -78,24 +77,21 @@ __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 ;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next; + sem->activity++;list_del (&waiter->list); tsk = waiter->task;smp_mb (); waiter->task =NULL ;wake_up_process (tsk);put_task_struct (tsk); - woken++;
lib/rwsem-spinlock.c __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) · line 97
Quoted 10 lines
lib/rwsem-spinlock.c +0
-2if (list_empty (&sem->wait_list))break ; waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; - out:return sem; }
So if I understand this correctly
- 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.
Fair enough, I guess.
I don't know if we really need this in -stable. Do we expect that there will be any real runtime bugs arising from this?
Quoted 9 lines · Andrew Morton
Quoted 6 lines · On Tue, 29 Sep 2009 23:19:02 -0400 Amerigo Wang <[email protected]> wrote:
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.
Quoted 7 lines
Quoted 5 lines
Brian has a kernel module to reproduce this, I can include it if any of you need. Of course, with Brian's approval.
With this patch applied, I can't trigger that bug any more.
Changelog doesn't describe the bug well.
Sorry for my English. :-/
Quoted 51 lines
Quoted 30 lines
---
lib/rwsem-spinlock.c +1
-3@@ -49,7 +49,6 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) {struct rwsem_waiter *waiter;struct task_struct *tsk; -int woken; waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);@@ -78,24 +77,21 @@ __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 ;while (waiter->flags &RWSEM_WAITING_FOR_READ ) {struct list_head *next = waiter->list.next; + sem->activity++;list_del (&waiter->list); tsk = waiter->task;smp_mb (); waiter->task =NULL ;wake_up_process (tsk);put_task_struct (tsk); - woken++;lib/rwsem-spinlock.c __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite) · line 97
Quoted 10 lines
lib/rwsem-spinlock.c +0
-2if (list_empty (&sem->wait_list))break ; waiter = list_entry(next, struct rwsem_waiter, list); } - sem->activity += woken; - out:return sem; }So if I understand this correctly
- 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().
Quoted 7 lines
- 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.
Fair enough, I guess.
Yes, exactly.
But after reading David's comments, I realized that rwsem_is_locked() has more problems, this only fixes one of them.
I will try another fix.
Quoted 3 lines
I don't know if we really need this in -stable. Do we expect that there will be any real runtime bugs arising from this?
Not sure, I need an extra kernel module to trigger this bug, so probably it doesn't affect the real kernel.
Thanks!
David Howells
NAKQuoted 5 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.
NAK.
This does not fix 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.
I'm leary of endorsing the presence of rwsem_is_locked() since, unless the function calling it knows that the process it is running in has the rwsem locked, the value is obsolete the moment the test has been performed.
The other problem with this change is that it has the potential to cause more cacheline ping-pong under contention. That said, contention on an rwsem is much less likely, I think, than on, say, a spinlock, so this change shouldn't cause a significant slowdown.
Your patch would probably be better as:
- woken = 0;
+ woken = ++sem->activity;
while (waiter->flags & RWSEM_WAITING_FOR_READ) {
struct list_head *next = waiter->list.next;
list_del(&waiter->list);
tsk = waiter->task;
smp_mb();
waiter->task = NULL;
wake_up_process(tsk);
put_task_struct(tsk);
woken++;
if (list_empty(&sem->wait_list))
break;
waiter = list_entry(next, struct rwsem_waiter, list);
}- sem->activity += woken;
+ sem->activity = woken;
However, as I said above, that is not sufficient. You really do need to put spinlocks in rwsem_is_locked():
static inline int rwsem_is_locked(struct rw_semaphore *sem)
{
unsigned long flags;
__s32 activity;
spin_lock_irqsave(&sem->wait_lock, flags);
activity = sem->activity;
spin_unlock_irqrestore(&sem->wait_lock, flags);
return activity != 0;
}You also need to check over lib/rwsem.c. rwsem_is_locked() is unreliable for that algorithm.
David
Quoted 8 lines · David Howells
Quoted 5 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.
Quoted 6 lines
NAK.
This does not fix 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.
Hmm, so the algorithm used in rwsem_is_locked() is not right.:-/
Quoted 35 lines
I'm leary of endorsing the presence of
rwsem_is_locked()since, unless the function calling it knows that the process it is running in has the rwsem locked, the value is obsolete the moment the test has been performed.The other problem with this change is that it has the potential to cause more cacheline ping-pong under contention. That said, contention on an rwsem is much less likely, I think, than on, say, a spinlock, so this change shouldn't cause a significant slowdown.
Your patch would probably be better as:
(quoted diff) +1
-1- woken = 0; + woken = ++sem->activity;while (waiter->flags & RWSEM_WAITING_FOR_READ) { struct list_head *next = waiter->list.next; list_del(&waiter->list); tsk = waiter->task; smp_mb(); waiter->task = NULL; wake_up_process(tsk); put_task_struct(tsk); woken++; if (list_empty(&sem->wait_list)) break; waiter = list_entry(next, struct rwsem_waiter, list); }(quoted diff) +1
-1- sem->activity += woken; + sem->activity = woken;However, as I said above, that is not sufficient. You really do need to put spinlocks in
rwsem_is_locked():
Quoted 10 lines
static inline int rwsem_is_locked(struct rw_semaphore *sem)
{
unsigned long flags;
__s32 activity;
spin_lock_irqsave(&sem->wait_lock, flags);
activity = sem->activity;
spin_unlock_irqrestore(&sem->wait_lock, flags);
return activity != 0;
}Sure, adding spinlocks can solve this, but that would be expensive, wouldn't it?
Quoted 3 lines
You also need to check over
lib/rwsem.c.rwsem_is_locked()is unreliable for that algorithm.
Yeah, I agree, I will try another fix.
Thank you!
Quoted 20 lines · David Howells
Your patch would probably be better as:
(quoted diff) +1
-1- woken = 0; + woken = ++sem->activity;while (waiter->flags & RWSEM_WAITING_FOR_READ) { struct list_head *next = waiter->list.next; list_del(&waiter->list); tsk = waiter->task; smp_mb(); waiter->task = NULL; wake_up_process(tsk); put_task_struct(tsk); woken++; if (list_empty(&sem->wait_list)) break; waiter = list_entry(next, struct rwsem_waiter, list); }
Review
Quoted 2 lines
(quoted diff) +1
-1- sem->activity += woken; + sem->activity = woken;
FYI, this seems wrong, probably even worse than what it is now. I tried this change, it breaks portmap.
Quoted 2 lines · Amerigo Wang
FYI, this seems wrong, probably even worse than what it is now. I tried this change, it breaks portmap.
Sorry, my mistake. The following:
Quoted 2 lines
Review
Quoted 2 lines
(quoted diff) +1
-1- woken = 0; + woken = ++sem->activity;
should have been:
- woken = 0;
+ woken = sem->activity++;
David