Fix a lockup in wait_for_completion() and friends
PATCH v2 1/1 Fix a lockup in wait_for_completion() and friends
From: Corey Minyard <[email protected]>
The function call do_wait_for_common() has a race condition that can result in lockups waiting for completions. Adding the thread to (and removing the thread from) the wait queue for the completion is done outside the do loop in that function. However, if the thread is woken up, the swake_up_locked() function will delete the entry from the wait queue. If that happens and another thread sneaks in and decrements the done count in the completion to zero, the loop will go around again, but the thread will no longer be in the wait queue, so there is no way to wake it up.
Fix it by adding/removing the thread to/from the wait queue inside the do loop.
---
I sent the wrong version of this, I had spotted this before but didn't fix it here. Adding the thread to the wait queue needs to come after the signal check. Sorry about the noise.
kernel/sched/completion.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/sched/completion.c +4 -4
@@ -70,20 +70,20 @@ do_wait_for_common(struct completion *x, long (*action)(long), long timeout, int state) { if (!x->done) { -DECLARE_SWAITQUEUE (wait ); - -__prepare_to_swait (&x->wait, &wait); do { +DECLARE_SWAITQUEUE (wait ); +if (signal_pending_state (state, current)) { timeout = -ERESTARTSYS ;break ; } +__prepare_to_swait (&x->wait, &wait);__set_current_state (state);raw_spin_unlock_irq (&x->wait.lock); timeout =action (timeout);raw_spin_lock_irq (&x->wait.lock); +__finish_swait (&x->wait, &wait); }while (!x->done && timeout); -__finish_swait (&x->wait, &wait);if (!x->done)return timeout; }
Signature · 1 line
2.17.1
Please:
- add some RT developers on Cc:
- add lkml
- use [PATCH RT] instead just [PATCH] so it is visible that you target the RT tree.
Quoted 12 lines · On 2019-05-08 15:57:28 [-0500], [email protected] wrote:
From: Corey Minyard <[email protected]>
The function call
do_wait_for_common()has a race condition that can result in lockups waiting for completions. Adding the thread to (and removing the thread from) the wait queue for the completion is done outside the do loop in that function. However, if the thread is woken up, theswake_up_locked()function will delete the entry from the wait queue. If that happens and another thread sneaks in and decrements the done count in the completion to zero, the loop will go around again, but the thread will no longer be in the wait queue, so there is no way to wake it up.
Quoted 2 lines
Fix it by adding/removing the thread to/from the wait queue inside the do loop.
So you are saying:
T0 T1 T2 wait_for_completion() do_wait_for_common() __prepare_to_swait() schedule() complete() x->done++ (0 -> 1) raw_spin_lock_irqsave() swake_up_locked() wait_for_completion() wake_up_process(T0) list_del_init() raw_spin_unlock_irqrestore() raw_spin_lock_irq(&x->wait.lock) raw_spin_lock_irq(&x->wait.lock) x->done != UINT_MAX, 1 -> 0 return 1 raw_spin_unlock_irq(&x->wait.lock) while (!x->done && timeout), continue loop, not enqueued on &x->wait
The difference compared to the non-swait based implementation is that swake_up_locked() removes woken up tasks from the list while the other implementation (wait_queue_entry based, default_wake_function()) does not. Buh
One question for the upstream completion implementation:completion_done() returns true if there are no waiters. It acquires the wait.lock to ensure that complete()/complete_all() is done. However, once complete releases the lock it is guaranteed that the wake_up() (for the waiter) occurred. The waiter task still needs to be remove itself from the wait-queue before the completion can be removed.
Do I miss something?
Quoted 15 lines
Fixes a04ff6b4ec4ee7e ("completion: Use simple wait queues")Signed-off-by Corey Minyard <[email protected]>---
I sent the wrong version of this, I had spotted this before but didn't fix it here. Adding the thread to the wait queue needs to come after the signal check. Sorry about the noise.kernel/sched/completion.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)kernel/sched/completion.c +0
-0
kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 75
Quoted 6 lines
kernel/sched/completion.c +0
-3@@ -70,20 +70,20 @@ do_wait_for_common(struct completion *x, long (*action)(long), long timeout, int state) { if (!x->done) { -DECLARE_SWAITQUEUE (wait ); - -__prepare_to_swait (&x->wait, &wait);
you can keep DECLARE_SWAITQUEUE remove just __prepare_to_swait()
kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 80
Quoted 8 lines
kernel/sched/completion.c +3
-0do { + DECLARE_SWAITQUEUE(wait); + if (signal_pending_state(state, current)) { timeout = -ERESTARTSYS; break; } + __prepare_to_swait(&x->wait, &wait);
add this, yes and you are done.
kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 89
Quoted 10 lines
kernel/sched/completion.c +1
-1__set_current_state (state);raw_spin_unlock_irq (&x->wait.lock); timeout =action (timeout);raw_spin_lock_irq (&x->wait.lock); +__finish_swait (&x->wait, &wait); }while (!x->done && timeout); -__finish_swait (&x->wait, &wait);if (!x->done)return timeout; }
Sebastian
Quoted 5 lines · Sebastian Andrzej Siewior
Please:
- add some RT developers on Cc:
- add lkml
- use [PATCH RT] instead just [PATCH] so it is visible that you target the RT tree.
Will do. I'll add your diagram below, too.
Quoted 38 lines · On 2019-05-08 15:57:28 [-0500], [email protected] wrote:
Quoted 12 lines
From: Corey Minyard <[email protected]>
The function call
do_wait_for_common()has a race condition that can result in lockups waiting for completions. Adding the thread to (and removing the thread from) the wait queue for the completion is done outside the do loop in that function. However, if the thread is woken up, theswake_up_locked()function will delete the entry from the wait queue. If that happens and another thread sneaks in and decrements the done count in the completion to zero, the loop will go around again, but the thread will no longer be in the wait queue, so there is no way to wake it up.Quoted 2 lines
Fix it by adding/removing the thread to/from the wait queue inside the do loop.
So you are saying:
T0 T1 T2 wait_for_completion() do_wait_for_common() __prepare_to_swait() schedule() complete() x->done++ (0 -> 1) raw_spin_lock_irqsave() swake_up_locked() wait_for_completion() wake_up_process(T0) list_del_init() raw_spin_unlock_irqrestore() raw_spin_lock_irq(&x->wait.lock) raw_spin_lock_irq(&x->wait.lock) x->done != UINT_MAX, 1 -> 0 return 1 raw_spin_unlock_irq(&x->wait.lock) while (!x->done && timeout), continue loop, not enqueued on &x->wait
Quoted 4 lines
The difference compared to the non-swait based implementation is that
swake_up_locked()removes woken up tasks from the list while the other implementation (wait_queue_entrybased,default_wake_function()) does not. Buh
Yes, exactly. I was wondering if swait could be changed to not remove the waiter, but that seemed like a bad idea. It is an unusual semantic, though.
I thought some more about this, wondering why everything isn't keeling over because of this. I'm guessing that just about everything using completions has a single waiter, so it doesn't matter. I just wrote some code that has a bunch of waiters, so I hit it.
-corey
Quoted 56 lines
One question for the upstream completion implementation:
completion_done()returns true if there are no waiters. It acquires the wait.lock to ensure that complete()/complete_all() is done. However, once complete releases the lock it is guaranteed that thewake_up()(for the waiter) occurred. The waiter task still needs to be remove itself from the wait-queue before the completion can be removed.
Do I miss something?Quoted 15 lines
Fixes a04ff6b4ec4ee7e ("completion: Use simple wait queues")Signed-off-by Corey Minyard <[email protected]>---
I sent the wrong version of this, I had spotted this before but didn't fix it here. Adding the thread to the wait queue needs to come after the signal check. Sorry about the noise.kernel/sched/completion.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)kernel/sched/completion.c +0
-0kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 75
Quoted 6 lines
kernel/sched/completion.c +0
-3@@ -70,20 +70,20 @@ do_wait_for_common(struct completion *x, long (*action)(long), long timeout, int state) { if (!x->done) { -DECLARE_SWAITQUEUE (wait ); - -__prepare_to_swait (&x->wait, &wait);you can keep
DECLARE_SWAITQUEUEremove just__prepare_to_swait()kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 80
Quoted 8 lines
kernel/sched/completion.c +3
-0do { + DECLARE_SWAITQUEUE(wait); + if (signal_pending_state(state, current)) { timeout = -ERESTARTSYS; break; } + __prepare_to_swait(&x->wait, &wait);add this, yes and you are done.
kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 89
Quoted 10 lines
kernel/sched/completion.c +1
-1__set_current_state (state);raw_spin_unlock_irq (&x->wait.lock); timeout =action (timeout);raw_spin_lock_irq (&x->wait.lock); +__finish_swait (&x->wait, &wait); }while (!x->done && timeout); -__finish_swait (&x->wait, &wait);if (!x->done)return timeout; }Sebastian
Peter Zijlstra
maintainerQuoted 30 lines · Sebastian Andrzej Siewior
Quoted 8 lines · On 2019-05-08 15:57:28 [-0500], [email protected] wrote:
kernel/sched/completion.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)kernel/sched/completion.c +0
-0kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 75
Quoted 6 lines
kernel/sched/completion.c +0
-3@@ -70,20 +70,20 @@ do_wait_for_common(struct completion *x, long (*action)(long), long timeout, int state) { if (!x->done) { -DECLARE_SWAITQUEUE (wait ); - -__prepare_to_swait (&x->wait, &wait);you can keep
DECLARE_SWAITQUEUEremove just__prepare_to_swait()kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 80
Quoted 8 lines
kernel/sched/completion.c +3
-0do { + DECLARE_SWAITQUEUE(wait); + if (signal_pending_state(state, current)) { timeout = -ERESTARTSYS; break; } + __prepare_to_swait(&x->wait, &wait);add this, yes and you are done.
Quoted 10 lines
kernel/sched/completion.c do_wait_for_common(struct completion *x, · line 89
Quoted 10 lines
kernel/sched/completion.c +1
-1__set_current_state (state);raw_spin_unlock_irq (&x->wait.lock); timeout =action (timeout);raw_spin_lock_irq (&x->wait.lock); +__finish_swait (&x->wait, &wait); }while (!x->done && timeout); -__finish_swait (&x->wait, &wait);if (!x->done)return timeout; }
Now.. that will fix it, but I think it is also wrong.
The problem being that it violates FIFO, something that might be more important on -RT than elsewhere.
The regular wait API seems confused/inconsistent when it uses autoremove_wake_function and default_wake_function, which doesn't help, but we can easily support this with swait -- the problematic thing is the custom wake functions, we musn't do that.
(also, mingo went and renamed a whole bunch of wait_* crap and didn't do the same to swait_ so now its named all different :/)
Something like the below perhaps.
---
include/linux/swait.h +2 -0
@@ -61,11 +61,13 @@ struct swait_queue_head {struct swait_queue {struct task_struct *task;struct list_head task_list; +unsigned int remove; };#define __SWAITQUEUE_INITIALIZER (name) { \ .task = current, \ .task_list = LIST_HEAD_INIT((name).task_list), \ + .remove = 1, \ }#define DECLARE_SWAITQUEUE (name) \
kernel/sched/swait.c +4 -2
@@ -28,7 +28,8 @@ void swake_up_locked(struct swait_queue_head *q) curr =list_first_entry (&q->task_list,typeof (*curr), task_list);wake_up_process (curr->task); -list_del_init (&curr->task_list); +if (curr->remove) +list_del_init (&curr->task_list); }EXPORT_SYMBOL (swake_up_locked);
@@ -57,7 +58,8 @@ void swake_up_all(struct swait_queue_head *q) curr =list_first_entry (&tmp,typeof (*curr), task_list);wake_up_state (curr->task,TASK_NORMAL ); -list_del_init (&curr->task_list); +if (curr->remove) +list_del_init (&curr->task_list);if (list_empty (&tmp))break ;
Quoted 4 lines · Peter Zijlstra
Now.. that will fix it, but I think it is also wrong.
The problem being that it violates FIFO, something that might be more important on -RT than elsewhere.
Wouldn't -RT be more about waking the task with the highest priority instead the one that waited the longest?
Quoted 9 lines
The regular wait API seems confused/inconsistent when it uses
autoremove_wake_functionanddefault_wake_function, which doesn't help, but we can easily support this with swait -- the problematic thing is the custom wake functions, we musn't do that.(also, mingo went and renamed a whole bunch of wait_* crap and didn't do the same to
swait_so now its named all different :/)Something like the below perhaps.
This still violates FIFO because a task can do wait_for_completion(), not enqueue itself on the list because it noticed a pending wake and leave. The list order is preserved, we have that.
But this a completion list. We have probably multiple worker waiting for something to do so all of those should be of equal priority, maybe one for each core or so. So it shouldn't matter which one we wake up.
Corey, would it make any change which waiter is going to be woken up?
Sebastian
Peter Zijlstra
maintainerQuoted 8 lines · Sebastian Andrzej Siewior
Quoted 4 lines · Peter Zijlstra
Now.. that will fix it, but I think it is also wrong.
The problem being that it violates FIFO, something that might be more important on -RT than elsewhere.
Wouldn't -RT be more about waking the task with the highest priority instead the one that waited the longest?
Possibly, but that's a far larger patch. Also, even with that completions do not avoid inversions and thus don't really make nice RT primitives anyway.
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 4 lines · Peter Zijlstra
Now.. that will fix it, but I think it is also wrong.
The problem being that it violates FIFO, something that might be more important on -RT than elsewhere.
Quoted 6 lines
Quoted 2 lines
Wouldn't -RT be more about waking the task with the highest priority instead the one that waited the longest?
Possibly, but that's a far larger patch. Also, even with that completions do not avoid inversions and thus don't really make nice RT primitives anyway.
See. So it does not really matter if a particular waiter ends up at the end of the queue.
Anyway, I don't really think we need this but if you want it, let me add it.
What about the other question I had regarding completion_done()?
Sebastian
Quoted 19 lines · Sebastian Andrzej Siewior
Quoted 4 lines · Peter Zijlstra
Now.. that will fix it, but I think it is also wrong.
The problem being that it violates FIFO, something that might be more important on -RT than elsewhere.
Wouldn't -RT be more about waking the task with the highest priority instead the one that waited the longest?
Quoted 9 lines
The regular wait API seems confused/inconsistent when it uses
autoremove_wake_functionanddefault_wake_function, which doesn't help, but we can easily support this with swait -- the problematic thing is the custom wake functions, we musn't do that.(also, mingo went and renamed a whole bunch of wait_* crap and didn't do the same to
swait_so now its named all different :/)Something like the below perhaps.
Quoted 8 lines
This still violates FIFO because a task can do
wait_for_completion(), not enqueue itself on the list because it noticed a pending wake and leave. The list order is preserved, we have that.
But this a completion list. We have probably multiple worker waiting for something to do so all of those should be of equal priority, maybe one for each core or so. So it shouldn't matter which one we wake up.Corey, would it make any change which waiter is going to be woken up?
In the application that found this, the wake order probably isn't relevant.
For other applications, I really doubt that very many are using multiple waiters. If so, this bug would have been reported sooner, I think.
As you mention, for RT you would want waiter woken by priority and FIFO within priority. I don't think POSIX says anything about FIFO within priority, but that's probably a good idea. That's no longer a simple wait queue The way it is now is probably closer to that than what Peter suggested, but not really that close.
This is heavily used in drivers and fs code, where it probably doesn't matter. I looked through a few users in mm and kernel, and they had one waiter or were init/shutdown type things where order is not important.
So I'm not sure it's important.
-corey
Quoted 2 lines
Sebastian
Quoted 4 lines · Corey Minyard
Quoted 1 line
Corey, would it make any change which waiter is going to be woken up?
In the application that found this, the wake order probably isn't relevant.
what I expected.
Quoted 2 lines
For other applications, I really doubt that very many are using multiple waiters. If so, this bug would have been reported sooner, I think.
most other do either one waiter/waker pair or one waker and multiple waiter. And then reinit_completion() is used for the next round.
Quoted 11 lines
As you mention, for RT you would want waiter woken by priority and FIFO within priority. I don't think POSIX says anything about FIFO within priority, but that's probably a good idea. That's no longer a simple wait queue The way it is now is probably closer to that than what Peter suggested, but not really that close.
This is heavily used in drivers and fs code, where it probably doesn't matter. I looked through a few users in mm and kernel, and they had one waiter or were init/shutdown type things where order is not important.
So I'm not sure it's important.
Why did you bring POSIX into this? This isn't an API exported to userland which would fall into that category.
Peter's suggestion for FIFO is that we probably don't want to starve one thread/waiter if it is always enqueued at the end of the list. As you said, in your case it does not matter because (I assume) each waiter is equal and the outcome would be the same.
Quoted 1 line
-corey
Sebastian
Quoted 20 lines · Sebastian Andrzej Siewior
Quoted 4 lines · Corey Minyard
Quoted 1 line
Corey, would it make any change which waiter is going to be woken up?
In the application that found this, the wake order probably isn't relevant.
what I expected.
Quoted 2 lines
For other applications, I really doubt that very many are using multiple waiters. If so, this bug would have been reported sooner, I think.
most other do either one waiter/waker pair or one waker and multiple waiter. And then
reinit_completion()is used for the next round.Quoted 6 lines
As you mention, for RT you would want waiter woken by priority and FIFO within priority. I don't think POSIX says anything about FIFO within priority, but that's probably a good idea. That's no longer a simple wait queue The way it is now is probably closer to that than what Peter suggested, but not really that close.
Quoted 8 lines
Quoted 5 lines
This is heavily used in drivers and fs code, where it probably doesn't matter. I looked through a few users in mm and kernel, and they had one waiter or were init/shutdown type things where order is not important.
So I'm not sure it's important.
Why did you bring POSIX into this? This isn't an API exported to userland which would fall into that category.
My understanding is that POSIX.1b scheduling classes affect everything. So if you have two processes blocked on the same things for any reason, you need to wake up the higher priority one first. In reality, it probably doesn't matter unless something more critical uses completions.
Quoted 5 lines
Peter's suggestion for FIFO is that we probably don't want to starve one thread/waiter if it is always enqueued at the end of the list. As you said, in your case it does not matter because (I assume) each waiter is equal and the outcome would be the same.
Yeah, my case is not relevant to this, I'm more concerned with the cases that are.
-corey
Quoted 4 lines
Quoted 2 lines
-corey
Sebastian
Peter Zijlstra
maintainerQuoted 7 lines · Sebastian Andrzej Siewior
One question for the upstream completion implementation:
completion_done()returns true if there are no waiters. It acquires the wait.lock to ensure that complete()/complete_all() is done. However, once complete releases the lock it is guaranteed that thewake_up()(for the waiter) occurred. The waiter task still needs to be remove itself from the wait-queue before the completion can be removed.
Do I miss something?
So you mean:
init_completion(&done); wait_for_copmletion(&done) spin_lock() __add_wait_queue() spin_unlock() schedule() complete() completion_done() spin_lock() __remove_wait_queue() spin_unlock()
Right?
I think that boils down to that whenever you have multiple waiters, someone needs to be in charge of @done's lifetime.
The case that matters is:
DECLARE_COMPLETION_ONSTACK(done) while (!completion_done(&done)) cpu_relax();
Where there is but a single waiter, and that waiter is completion_done(). In that case it must not return early.
Now, I've also seen a ton of code do:
if (!completion_done(done)) complete(done);
And that makes me itch... but I've not bothered to look into it hard enough.