locking/rwsem: Fix lock optimistic spinning when owner is not running

PATCH In review Jason Low 6 participants 13 messages Mar 7, 2015 – Mar 10, 2015 Locking primitives

lore

Share & tools

lore

Jason Low

author

2015-03-07 07:45 UTC #0 lore raw

PATCH 1/1 locking/rwsem: Fix lock optimistic spinning when owner is not running

Fixes tip commit b3fd4f03ca0b (locking/rwsem: Avoid deceiving lock spinners).

Ming reported soft lockups occurring when running xfstest due to commit b3fd4f03ca0b.

When doing optimistic spinning in rwsem, threads should stop spinning when the lock owner is not running. While a thread is spinning on owner, if the owner reschedules, owner->on_cpu returns false and we stop spinning.

However, commit b3fd4f03ca0b essentially caused the check to get ignored because when we break out of the spin loop due to !on_cpu, we continue spinning if sem->owner != NULL.

This patch fixes this by making sure we stop spinning if the owner is not running. Furthermore, just like with mutexes, refactor the code such that we don't have separate checks for owner_running(). This makes it more straightforward in terms of why we exit the spin on owner loop and we would also avoid needing to "guess" why we broke out of the loop to make this more readable.

Reported-and-tested-by Ming Lei <[email protected]>

Acked-by Davidlohr Bueso <[email protected]>

Signed-off-by Jason Low <[email protected]>

---
 kernel/locking/rwsem-xadd.c |   31 +++++++++++--------------------
 1 files changed, 11 insertions(+), 20 deletions(-)

kernel/locking/rwsem-xadd.c +11 ~~-20~~

index 06e2214..3417d01 100644
@@ -324,32 +324,23 @@ done:
 	return ret;
 }
 
-static inline bool owner_running(struct rw_semaphore *sem,
-				 struct task_struct *owner)
-{
-	if (sem->owner != owner)
-		return false;
-
-	/*
-	 * Ensure we emit the owner->on_cpu, dereference _after_ checking
-	 * sem->owner still matches owner, if that fails, owner might
-	 * point to free()d memory, if it still matches, the rcu_read_lock()
-	 * ensures the memory stays valid.
-	 */
-	barrier();
-
-	return owner->on_cpu;
-}
-
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
 	long count;
 
 	rcu_read_lock();
-	while (owner_running(sem, owner)) {
-		/* abort spinning when need_resched */
-		if (need_resched()) {
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,
+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.
+		 */
+		barrier();
+
+		/* abort spinning when need_resched or owner is not running */
+		if (!owner->on_cpu || need_resched()) {
 			rcu_read_unlock();
 			return false;
 		}

Signature · 1 line

1.7.2.5

Peter Zijlstra

maintainer

2015-03-07 09:40 UTC #1 lore raw

Quoted 10 lines · Jason Low

static noinline
bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner) {
kernel/locking/rwsem-xadd.c +4 -0
 	long count;
 
 	rcu_read_lock();
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,

kernel/locking/rwsem-xadd.c done: · line 346

Quoted 10 lines

kernel/locking/rwsem-xadd.c +7 -0

+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.
+		 */
+		barrier();
+
+		/* abort spinning when need_resched or owner is not running */
+		if (!owner->on_cpu || need_resched()) {
 			rcu_read_unlock();
 			return false;
 		}

Thanks, looks good; do we want to change the mutex code (again) to more closely resemble this too? It still has the while (true) instead of the while(lock->owner != owner).

tip-bot for Jason Low

merge bot

2015-03-07 16:44 UTC #3 lore raw

In reply to Jason Low

locking/rwsem: Fix lock optimistic spinning when owner is not running

Commit-ID:  9198f6edfd9ced74fd90b238d5a354aeac89bdfa
Gitweb:     http://git.kernel.org/tip/9198f6edfd9ced74fd90b238d5a354aeac89bdfa
Author:     Jason Low <[email protected]>
AuthorDate: Fri, 6 Mar 2015 23:45:31 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Sat, 7 Mar 2015 09:50:49 +0100

locking/rwsem: Fix lock optimistic spinning when owner is not running

Ming reported soft lockups occurring when running xfstest due to the following tip:locking/core commit:

b3fd4f03ca0b ("locking/rwsem: Avoid deceiving lock spinners")

However, this commit essentially caused the check to get ignored because when we break out of the spin loop due to !on_cpu, we continue spinning if sem->owner != NULL.

Reported-and-tested-by Ming Lei <[email protected]>

Signed-off-by Jason Low <[email protected]>

Acked-by Davidlohr Bueso <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Dave Jones <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Michel Lespinasse <[email protected]>

Cc Oleg Nesterov <[email protected]>

Cc Paul E. McKenney <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Sasha Levin <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Tim Chen <[email protected]>

Link http://lkml.kernel.org/r/1425714331.2475.388.camel@j-VirtualBox open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/locking/rwsem-xadd.c | 31 +++++++++++--------------------
 1 file changed, 11 insertions(+), 20 deletions(-)

kernel/locking/rwsem-xadd.c +11 ~~-20~~

index 06e2214..3417d01 100644
@@ -324,32 +324,23 @@ done:
 	return ret;
 }
 
-static inline bool owner_running(struct rw_semaphore *sem,
-				 struct task_struct *owner)
-{
-	if (sem->owner != owner)
-		return false;
-
-	/*
-	 * Ensure we emit the owner->on_cpu, dereference _after_ checking
-	 * sem->owner still matches owner, if that fails, owner might
-	 * point to free()d memory, if it still matches, the rcu_read_lock()
-	 * ensures the memory stays valid.
-	 */
-	barrier();
-
-	return owner->on_cpu;
-}
-
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
 	long count;
 
 	rcu_read_lock();
-	while (owner_running(sem, owner)) {
-		/* abort spinning when need_resched */
-		if (need_resched()) {
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,
+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.
+		 */
+		barrier();
+
+		/* abort spinning when need_resched or owner is not running */
+		if (!owner->on_cpu || need_resched()) {
 			rcu_read_unlock();
 			return false;
 		}

Oleg Nesterov

2015-03-07 17:16 UTC #4 lore raw

I think the patch is fine, but this reminds me...

Quoted 5 lines · tip-bot for Jason Low

bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner) {
kernel/locking/rwsem-xadd.c +0 -0
 	long count;
 

kernel/locking/rwsem-xadd.c done: · line 338

Quoted 10 lines

kernel/locking/rwsem-xadd.c +6 -3

 	rcu_read_lock();
-	while (owner_running(sem, owner)) {
-		/* abort spinning when need_resched */
-		if (need_resched()) {
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,
+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.

                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Yes, this is another case when we wrongly assume this.

Peter, should I resend

	[PATCH 3/3] introduce task_rcu_dereference()
	http://marc.info/?l=linux-kernel&m=141443631413914

? or should we add another call_rcu() in finish_task_switch() (like -rt does) to make this true?

Oleg.

Sasha Levin

2015-03-07 18:18 UTC #11 lore raw

In reply to Jason Low

Quoted 13 lines · Jason Low

Fixes tip commit b3fd4f03ca0b (locking/rwsem: Avoid deceiving lock spinners).
Ming reported soft lockups occurring when running xfstest due to commit b3fd4f03ca0b.
When doing optimistic spinning in rwsem, threads should stop spinning when the lock owner is not running. While a thread is spinning on owner, if the owner reschedules, owner->on_cpu returns false and we stop spinning.
However, commit b3fd4f03ca0b essentially caused the check to get ignored because when we break out of the spin loop due to !on_cpu, we continue spinning if sem->owner != NULL.

Quoted 6 lines

This patch fixes this by making sure we stop spinning if the owner is not running. Furthermore, just like with mutexes, refactor the code such that we don't have separate checks for owner_running(). This makes it more straightforward in terms of why we exit the spin on owner loop and we would also avoid needing to "guess" why we broke out of the loop to make this more readable.

That seems to solve the hangs I'm seeing as well.

Thanks,
Sasha

Jason Low

author

2015-03-09 17:37 UTC #12 lore raw

Quoted 14 lines · Sasha Levin

Quoted 13 lines · Jason Low
Fixes tip commit b3fd4f03ca0b (locking/rwsem: Avoid deceiving lock spinners).
Ming reported soft lockups occurring when running xfstest due to commit b3fd4f03ca0b.
When doing optimistic spinning in rwsem, threads should stop spinning when the lock owner is not running. While a thread is spinning on owner, if the owner reschedules, owner->on_cpu returns false and we stop spinning.
However, commit b3fd4f03ca0b essentially caused the check to get ignored because when we break out of the spin loop due to !on_cpu, we continue spinning if sem->owner != NULL.

Quoted 8 lines

Quoted 6 lines
This patch fixes this by making sure we stop spinning if the owner is not running. Furthermore, just like with mutexes, refactor the code such that we don't have separate checks for owner_running(). This makes it more straightforward in terms of why we exit the spin on owner loop and we would also avoid needing to "guess" why we broke out of the loop to make this more readable.
That seems to solve the hangs I'm seeing as well.

Great, thanks for confirming this.

Jason Low

author

2015-03-09 17:42 UTC #2 lore raw

In reply to Peter Zijlstra

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Jason Low

static noinline
bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner) {

kernel/locking/rwsem-xadd.c +10 -0

 	long count;
 
 	rcu_read_lock();
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,
+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.
+		 */
+		barrier();
+
+		/* abort spinning when need_resched or owner is not running */

Quoted 8 lines

kernel/locking/rwsem-xadd.c done: · line 346
Quoted 4 lines
kernel/locking/rwsem-xadd.c +1 -0
+		if (!owner->on_cpu || need_resched()) {
 			rcu_read_unlock();
 			return false;
 		}
Thanks, looks good; do we want to change the mutex code (again) to more closely resemble this too? It still has the while (true) instead of the while(lock->owner != owner).

Yeah, I wondered about the same thing, though I wasn't sure if you wanted an additional patch just for that change.

Guess you answered it for me :)

Peter Zijlstra

maintainer

2015-03-10 11:00 UTC #5 lore raw

In reply to Oleg Nesterov

Quoted 22 lines · Oleg Nesterov

I think the patch is fine, but this reminds me...
Quoted 5 lines · tip-bot for Jason Low
bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner) {
kernel/locking/rwsem-xadd.c +0 -0
 	long count;
 
kernel/locking/rwsem-xadd.c done: · line 338
Quoted 10 lines
kernel/locking/rwsem-xadd.c +6 -3
 	rcu_read_lock();
-	while (owner_running(sem, owner)) {
-		/* abort spinning when need_resched */
-		if (need_resched()) {
+	while (sem->owner == owner) {
+		/*
+		 * Ensure we emit the owner->on_cpu, dereference _after_
+		 * checking sem->owner still matches owner, if that fails,
+		 * owner might point to free()d memory, if it still matches,
+		 * the rcu_read_lock() ensures the memory stays valid.
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Yes, this is another case when we wrongly assume this.

Quoted 7 lines

Peter, should I resend
	[PATCH 3/3] introduce task_rcu_dereference()
	http://marc.info/?l=linux-kernel&m=141443631413914
? or should we add another call_rcu() in finish_task_switch() (like -rt does) to make this true?

Yeah, I think the extra call_rcu() makes most sense.

Linus Torvalds

2015-03-10 16:04 UTC #6 lore raw

In reply to Oleg Nesterov

Quoted 9 lines · Oleg Nesterov

kernel/locking/rwsem-xadd.c done: · line 338

Quoted 5 lines

kernel/locking/rwsem-xadd.c +5 -0

+             /*
+              * Ensure we emit the owner->on_cpu, dereference _after_
+              * checking sem->owner still matches owner, if that fails,
+              * owner might point to free()d memory, if it still matches,
+              * the rcu_read_lock() ensures the memory stays valid.

                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Yes, this is another case when we wrongly assume this.

Quoted 7 lines

Peter, should I resend
[PATCH 3/3] introduce task_rcu_dereference()
http://marc.info/?l=linux-kernel&m=141443631413914
? or should we add another call_rcu() in finish_task_switch() (like -rt does) to make this true?

I think we should just make 'task_struct_cachep' have SLAB_DESTROY_BY_RCU.

It has almost no overhead - since it only affects the final page freeing, not the actual slab alloc/free paths - and it means that you can do the "access for reading under rcu lock" without worrying.

Of course, with SLAB_DESTROY_BY_RCU, a task may be re-allocated (to *another* task) even under RCU, so the results from unlocked RCU read accesses aren't "guaranteed" in that sense, but it's fine for optimistic spinning where the code also ends up re-checking that the task pointer itself matches. Getting the occasional race with "oops, task went away" is fine, as long as we don't keep looping over a dead task.

Linus

Peter Zijlstra

maintainer

2015-03-10 16:17 UTC #7 lore raw

Quoted 2 lines · Linus Torvalds

I think we should just make 'task_struct_cachep' have SLAB_DESTROY_BY_RCU.

Yes, that'll work. Also for the other cases Oleg found previously I think.

Oleg Nesterov

2015-03-10 17:31 UTC #8 lore raw

In reply to Linus Torvalds

Quoted 13 lines · Linus Torvalds

Quoted 11 lines · Oleg Nesterov

kernel/locking/rwsem-xadd.c done: · line 338

Quoted 5 lines

kernel/locking/rwsem-xadd.c +5 -0

+             /*
+              * Ensure we emit the owner->on_cpu, dereference _after_
+              * checking sem->owner still matches owner, if that fails,
+              * owner might point to free()d memory, if it still matches,
+              * the rcu_read_lock() ensures the memory stays valid.

                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Yes, this is another case when we wrongly assume this.

Peter, should I resend

Quoted 7 lines

Quoted 5 lines
[PATCH 3/3] introduce task_rcu_dereference()
http://marc.info/?l=linux-kernel&m=141443631413914
? or should we add another call_rcu() in finish_task_switch() (like -rt does) to make this true?
I think we should just make 'task_struct_cachep' have SLAB_DESTROY_BY_RCU.

This is what I initially suggested too, but then tried to argue with. But it seems that I lost if you too prefer SLAB_DESTROY_BY_RCU.

Yes, SLAB_DESTROY_BY_RCU will work in this case because we recheck ->owner in a loop. And because task->on_cpu is just a word we can safely read.

But this won't fix other problems we might have. For example, suppose that we will need get_task_struct(owner) in this code, this won't work.

Or, as Kirill pointed out, lets look at "tsk = ACCESS_ONCE(cpu_rq(cpu)->curr)" in task_numa_group(). Even if this will be "fixed" by SLAB_DESTROY_BY_RCU, this code won't be correct anyway. Even if (I think) it will be safe to dereference ->numa_group as well.

But OK, I won't argue.

Oleg.

Linus Torvalds

2015-03-10 17:45 UTC #9 lore raw

Quoted 3 lines · Oleg Nesterov

But this won't fix other problems we might have. For example, suppose that we will need get_task_struct(owner) in this code, this won't work.

I agree that SLAB_DESTROY_BY_RCU in general is fairly fragile, and leads to subtle issues. If speculatively taking locks, for example, they might need to be initialized in the constructor function, and not ever touched at actual allocation time. Etc etc.

So I'm not a huge fan of SLAB_DESTROY_BY_RCU in general, but for really core data structures like this, I think it's worth it. The overhead of "call_rcu()" can be quite noticeable, and the other alternative solutions (like that suggested task_rcu_dereference()) are even *more* complex and subtle and generally perform worse.

I'm not claiming it's perfect, but I think the "access the task pointer without locking" is kind of special and worth making work in reasonable ways.

Linus

Oleg Nesterov

2015-03-10 18:35 UTC #10 lore raw

Quoted 3 lines · Linus Torvalds

So I'm not a huge fan of SLAB_DESTROY_BY_RCU in general, but for really core data structures like this, I think it's worth it.

I agree, but we have other users which can't be fixed if we just add SLAB_DESTROY_BY_RCU to task_struct_cachep. So we need something else anyway.

Quoted 2 lines

The
overhead of "call_rcu()" can be quite noticeable,

Yes, this was my concern too,

Quoted 3 lines

and the other
alternative solutions (like that suggested task_rcu_dereference()) are even *more* complex and subtle

Yes, but at least the ugliness is hidden inside task_rcu_dereference(). The usage is simple.

Quoted 1 line

and generally perform worse.

Well, task_rcu_dereference() should be cheap enough. probe_slab_address() is a plain LOAD unless CONFIG_DEBUG_PAGEALLOC.

But!

Quoted 1 line

I'm not claiming it's perfect,

Same here, it is not that I think task_rcu_dereference() is very nice.

So I leave this to you and Peter ;)

Oleg.