Skip to contentSkip to conversation

rwsem: fix rwsem_is_locked() bug

PATCH Superseded Amerigo Wang 3 participants 7 messages Sep 30, 2009 – Oct 5, 2009 Library code

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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
index 9df3ca5..44e4484 100644
@@ -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;
 }
maintainer
#1 lore raw
Quoted 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 cause rwsem_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
index 9df3ca5..44e4484 100644
@@ -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 -2
 		if (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?

#2 lore raw
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 cause rwsem_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
index 9df3ca5..44e4484 100644
@@ -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 -2
 		if (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!

#3 lore raw
In reply to Amerigo Wang
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 cause rwsem_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

#4 lore raw
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 cause rwsem_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, though sem->activity is 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!

#5 lore raw
In reply to David Howells
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.

#6 lore raw
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