PATCH? hrtimer_wakeup: fix a theoretical race wrt rt_mutex_slowlock()
When task->array != NULL, try_to_wake_up() just goes to "out_running" and sets task->state = TASK_RUNNING.
In that case hrtimer_wakeup() does:
timeout->task = NULL; <----- [1] spin_lock(runqueues->lock); task->state = TASK_RUNNING; <----- [2]
from Documentation/memory-barriers.txt
Memory operations that occur before a LOCK operation may appear to happen after it completes.
This means that [2] may be completed before [1], and
CPU_0 CPU_1rt_mutex_slowlock:
for (;;) {
...
if (timeout && !timeout->task)
return -ETIMEDOUT;
...
schedule();
hrtimer_wakeup() sets
... task->state = TASK_RUNNING,
but "timeout->task = NULL"
is not completed
set_current_state(TASK_INTERRUPTIBLE);
}we can miss a timeout.
Of course, this all is scholasticism, this can't happen in practice, but may be this patch makes sense as a documentation update.
kernel/hrtimer.c renamed from kernel/hrtimer.c~1_hrtw +5 -2
@@ -662,9 +662,12 @@ static int hrtimer_wakeup(struct hrtimer container_of(timer, struct hrtimer_sleeper, timer);struct task_struct *task = t->task; - t->task =NULL ; -if (task) +if (task) { + t->task =NULL ; +/* must be visible before task->state = TASK_RUNNING */ +smp_wmb ();wake_up_process (task); + }return HRTIMER_NORESTART ; }
Quoted 12 lines · Oleg Nesterov
When
task->array!= NULL,try_to_wake_up()just goes to "out_running" and setstask->state=TASK_RUNNING.In that case
hrtimer_wakeup()does:timeout->task = NULL; <----- [1] spin_lock(runqueues->lock); task->state = TASK_RUNNING; <----- [2]
Quoted 6 lines
from
Documentation/memory-barriers.txtMemory operations that occur before a LOCK operation may appear to happen after it completes.
This means that [2] may be completed before [1], and
Yes. On x86 (and x86-64) you'll never see this, because writes are always seen in order regardless, and in addition, the spin_lock is actually totally serializing anyway. On most other architectures, the spin_lock will serialize all the writes too, but it's not guaranteed, so in theory you're right. I suspect no actual architecture will do this, but hey, when talking memory ordering, safe is a lot better than sorry.
That said, since "task->state" in only tested _inside_ the runqueue lock, there is no race that I can see. Since we've gotten the runqueue lock in order to even check task-state, the processor that _sets_ task state must not only have done the "spin_lock()", it must also have done the "spin_unlock()", and _that_ will not allow either the timeout or the task state to haev leaked out from under it (because that would imply that the critical region leaked out too).
So I don't think the race exists anyway - the schedule() will return immediately (because it will see TASK_RUNNING), and we'll just retry.
Linus
Quoted 9 lines · Linus Torvalds
That said, since "
task->state" in only tested _inside_ the runqueue lock, there is no race that I can see. Since we've gotten the runqueue lock in order to even check task-state, the processor that _sets_ task state must not only have done the "spin_lock()", it must also have done the "spin_unlock()", and _that_ will not allow either the timeout or the task state to haev leaked out from under it (because that would imply that the critical region leaked out too).
Quoted 3 lines
So I don't think the race exists anyway - the
schedule()will return immediately (because it will seeTASK_RUNNING), and we'll just retry.
This whole situation is very theoretical, but I think this actually can happen *theoretically*.
OK, the spin_lock doesn't do any serialization, but the unlock does. But the problem can happen before the unlock. Because of the loop.
CPU 1 CPU 2
task_rq_lock()
p->state = TASK_RUNNING;
(from bottom of for loop)
set_current_state(TASK_INTERRUPTIBLE);
for (;;) { (looping)
if (timeout && !timeout->task) (now CPU implements)
t->task = NULL
task_rq_unlock();
schedule() (with state == TASK_INTERRUPTIBLE)
Again, this is very theoretical, and I don't even think that this can happen if you tried to make it. But I guess if hardware were to change in the future with the same rules that we have today with barriers, that this can be a race.
-- Steve
Quoted 37 lines · Linus Torvalds
Quoted 12 lines · Oleg Nesterov
When
task->array!= NULL,try_to_wake_up()just goes to "out_running" and setstask->state=TASK_RUNNING.In that case
hrtimer_wakeup()does:timeout->task = NULL; <----- [1] spin_lock(runqueues->lock); task->state = TASK_RUNNING; <----- [2]Quoted 6 lines
from
Documentation/memory-barriers.txtMemory operations that occur before a LOCK operation may appear to happen after it completes.
This means that [2] may be completed before [1], and
Yes. On x86 (and x86-64) you'll never see this, because writes are always seen in order regardless, and in addition, the
spin_lockis actually totally serializing anyway. On most other architectures, thespin_lockwill serialize all the writes too, but it's not guaranteed, so in theory you're right. I suspect no actual architecture will do this, but hey, when talking memory ordering, safe is a lot better than sorry.That said, since "
task->state" in only tested _inside_ the runqueue lock, there is no race that I can see. Since we've gotten the runqueue lock in order to even check task-state, the processor that _sets_ task state must not only have done the "spin_lock()", it must also have done the "spin_unlock()", and _that_ will not allow either the timeout or the task state to haev leaked out from under it (because that would imply that the critical region leaked out too).
Quoted 2 lines
So I don't think the race exists anyway - the
schedule()will return immediately (because it will seeTASK_RUNNING), and we'll just retry.
schedule() will see TASK_INTERRUPTIBLE. hrtimer_wakeup() sets TASK_RUNNING, rt_mutex_slowlock() does set_current_state(TASK_INTERRUPTIBLE) after that. schedule() takes runqueue lock, yes, but we are testing timeout->task before.
Oleg.
Quoted 16 lines · Steven Rostedt
Quoted 9 lines · Linus Torvalds
That said, since "
task->state" in only tested _inside_ the runqueue lock, there is no race that I can see. Since we've gotten the runqueue lock in order to even check task-state, the processor that _sets_ task state must not only have done the "spin_lock()", it must also have done the "spin_unlock()", and _that_ will not allow either the timeout or the task state to haev leaked out from under it (because that would imply that the critical region leaked out too).Quoted 3 lines
So I don't think the race exists anyway - the
schedule()will return immediately (because it will seeTASK_RUNNING), and we'll just retry.
Quoted 6 lines
This whole situation is very theoretical, but I think this actually can happen *theoretically*.
OK, the
spin_lockdoesn't do any serialization, but the unlock does. But the problem can happen before the unlock. Because of the loop.
Yes, yes, thanks.
( Actually, this was more "is my understanding correct?" than a patch )
Thanks!
Quoted 31 lines
CPU 1 CPU 2
task_rq_lock() p->state = TASK_RUNNING; (from bottom of for loop) set_current_state(TASK_INTERRUPTIBLE); for (;;) { (looping) if (timeout && !timeout->task)(now CPU implements) t->task = NULL task_rq_unlock(); schedule() (with state == TASK_INTERRUPTIBLE)Again, this is very theoretical, and I don't even think that this can happen if you tried to make it. But I guess if hardware were to change in the future with the same rules that we have today with barriers, that this can be a race.
-- Steve
Quoted 22 lines · Steven Rostedt
This whole situation is very theoretical, but I think this actually can happen *theoretically*.
OK, the
spin_lockdoesn't do any serialization, but the unlock does. But the problem can happen before the unlock. Because of the loop.CPU 1 CPU 2
task_rq_lock() p->state = TASK_RUNNING; (from bottom of for loop) set_current_state(TASK_INTERRUPTIBLE); for (;;) { (looping) if (timeout && !timeout->task)
Quoted 6 lines
(now CPU implements)
t->task = NULL
task_rq_unlock();
schedule() (with state == TASK_INTERRUPTIBLE)Yeah, that seems a real bug. You _always_ need to actually do the thing that you wait for _before_ you want it up. That's what all the scheduling primitives depend on - you can't wake people up first, and then set the condition variable.
So if a rt_mutex depeds on something that is set inside the rq-lock, it needs to get the task rw-lock in order to check it.
Linus
Quoted 7 lines
Yes. On x86 (and x86-64) you'll never see this, because writes are always seen in order regardless, and in addition, the
spin_lockis actually totally serializing anyway. On most other architectures, thespin_lockwill serialize all the writes too, but it's not guaranteed, so in theory you're right. I suspect no actual architecture will do this, but hey, when talking memory ordering, safe is a lot better than sorry.
PowerPC doesn't serialize the writes on spin_lock, only on spin_unlock.
(That is, previous writes can "leak" into the lock, but writes done before the unlock can't leak out of the spinlock).
Now, I've just glanced at the thread, so I don't know if that's relevant to the problems you guys are talking about :-)
Ben.
Quoted 31 lines · Linus Torvalds
Quoted 22 lines · Steven Rostedt
This whole situation is very theoretical, but I think this actually can happen *theoretically*.
OK, the
spin_lockdoesn't do any serialization, but the unlock does. But the problem can happen before the unlock. Because of the loop.CPU 1 CPU 2
task_rq_lock() p->state = TASK_RUNNING; (from bottom of for loop) set_current_state(TASK_INTERRUPTIBLE); for (;;) { (looping) if (timeout && !timeout->task)Quoted 6 lines
(now CPU implements) t->task = NULL task_rq_unlock(); schedule() (with state == TASK_INTERRUPTIBLE)
Quoted 7 lines
Yeah, that seems a real bug. You _always_ need to actually do the thing that you wait for _before_ you want it up. That's what all the scheduling primitives depend on - you can't wake people up first, and then set the condition variable.
So if a
rt_mutexdepeds on something that is set inside the rq-lock, it needs to get the task rw-lock in order to check it.
No, rt_mutex is fine (I think).
My changelog was very unclean and confusing, I'll try again. What we are doing is:
rt_mutex_slowlock: task->state = TASK_INTERRUPTIBLE; mb(); if (CONDITION) return -ETIMEDOUT; schedule();
This is common and correct.
hrtimer_wakeup: CONDITION = 1; // [1] spin_lock(rq->lock); task->state = TASK_RUNNING; // [2]
This needs 'wmb()' between [1] and [2] unless spin_lock() garantees memory ordering. Of course, rt_mutex can take rq->lock to solve this, but I don't think it would be right.
Oleg.
Quoted 11 lines · Oleg Nesterov
Quoted 8 lines · Linus Torvalds
Yeah, that seems a real bug. You _always_ need to actually do the thing that you wait for _before_ you want it up. That's what all the scheduling primitives depend on - you can't wake people up first, and then set the condition variable.
So if a
rt_mutexdepeds on something that is set inside the rq-lock, it needs to get the task rw-lock in order to check it.No,
rt_mutexis fine (I think).
I agree. The problem isn't with rt_mutex. It rt_mutex doesn't depend on that condition to break out of the loop. That condition is an extra condition that's there to stop in the case we timed out before the owner released the lock. The real condition to break out of the loop is the owner releasing the lock, and there's no known races there.
So the time out is what needs to make sure that rt_mutex sees the event.
Quoted 15 lines
My changelog was very unclean and confusing, I'll try again. What we are doing is:
rt_mutex_slowlock: task->state = TASK_INTERRUPTIBLE; mb(); if (CONDITION) return -ETIMEDOUT; schedule();
Quoted 5 lines
This is common and correct.
hrtimer_wakeup: CONDITION = 1; // [1]
Right! The changing of the condition isn't even in any spin lock. But that condition needs be be completed before the changes done within the spin lock, but unfortunately, the spin lock itself doesn't guarantee anything.
Quoted 8 lines
spin_lock(rq->lock); task->state = TASK_RUNNING; // [2]This needs '
wmb()' between [1] and [2] unlessspin_lock()garantees memory ordering. Of course,rt_mutexcan takerq->lockto solve this, but I don't think it would be right.
Correct, the solution should NOT change rt_mutex. Your original patch is the correct approach.
-- Steve
Quoted 4 lines
Oleg.
Steven Rostedt
Acked-byQuoted 51 lines · Oleg Nesterov
When
task->array!= NULL,try_to_wake_up()just goes to "out_running" and setstask->state=TASK_RUNNING.In that case
hrtimer_wakeup()does:timeout->task = NULL; <----- [1] spin_lock(runqueues->lock); task->state = TASK_RUNNING; <----- [2]from
Documentation/memory-barriers.txtMemory operations that occur before a LOCK operation may appear to happen after it completes.
This means that [2] may be completed before [1], and
CPU_0CPU_1rt_mutex_slowlock:for (;;) { ... if (timeout && !timeout->task) return -ETIMEDOUT; ... schedule(); hrtimer_wakeup() sets ... task->state = TASK_RUNNING, but "timeout->task = NULL" is not completed set_current_state(TASK_INTERRUPTIBLE); }we can miss a timeout.
Of course, this all is scholasticism, this can't happen in practice, but may be this patch makes sense as a documentation update.
Signed-off-by Oleg Nesterov <[email protected]>kernel/hrtimer.c renamed from kernel/hrtimer.c~1_hrtw +0
-1@@ -662,9 +662,12 @@ static int hrtimer_wakeup(struct hrtimer container_of(timer, struct hrtimer_sleeper, timer);struct task_struct *task = t->task; - t->task =NULL ;
kernel/hrtimer.c static int hrtimer_wakeup(struct hrtimer · line 673
Quoted 10 lines
kernel/hrtimer.c renamed from kernel/hrtimer.c~1_hrtw +5
-1-if (task) +if (task) { + t->task =NULL ; +/* must be visible before task->state = TASK_RUNNING */ +smp_wmb ();wake_up_process (task); + }return HRTIMER_NORESTART ; }
Ingo, Thomas, could you ack this too, or Nack it with an explaination.
Ingo, you might want to read the whole thread here.
-- Steve
Quoted 8 lines · Benjamin Herrenschmidt
Quoted 7 lines
Yes. On x86 (and x86-64) you'll never see this, because writes are always seen in order regardless, and in addition, the
spin_lockis actually totally serializing anyway. On most other architectures, thespin_lockwill serialize all the writes too, but it's not guaranteed, so in theory you're right. I suspect no actual architecture will do this, but hey, when talking memory ordering, safe is a lot better than sorry.
Quoted 8 lines
PowerPC doesn't serialize the writes on
spin_lock, only onspin_unlock.(That is, previous writes can "leak" into the lock, but writes done before the unlock can't leak out of the spinlock).
Now, I've just glanced at the thread, so I don't know if that's relevant to the problems you guys are talking about :-)
It is relevant. In powerpc, can one write happen before another write?
x = 1; barrier(); (only compiler barrier) b = 2;
And have CPU 2 see b=2 before seeing x=1?
If so, then I guess this is indeed a bug on powerpc.
-- Steve
Quoted 2 lines · Steven Rostedt
Acked-by Steven Rostedt <[email protected]>
Thanks.
But on the other hand we probably have a similar code (set condition + wake_up_process()) in other places too, and __wake_up(wait_queue_head_t) has (in theory) the same problem. Probably we can add something like
smp_wmb_unless_spin_lock_implies_memory_barrier_on_this_arch()
somewhere in try_to_wake_up(). I dunno.
Oleg.
Quoted 11 lines · Oleg Nesterov
Quoted 2 lines · Steven Rostedt
Acked-by Steven Rostedt <[email protected]>Thanks.
But on the other hand we probably have a similar code (set condition +
wake_up_process()) in other places too, and__wake_up(wait_queue_head_t)has (in theory) the same problem. Probably we can add something like
smp_wmb_unless_spin_lock_implies_memory_barrier_on_this_arch()
Probably smp_wmb_before_spin_lock would be a good name.
Quoted 3 lines
somewhere in
try_to_wake_up(). I dunno.
But I don't think it belongs in try_to_wake_up. That's just assuming too much in that function. The event to wake up could simply be an interrupt took place, where the smb_wmb would not be needed.
As Linus has stated. Most cases where a process is going to sleep on an event, it had better check to make sure that the event didn't happen between the time it set itself to something other than TASK_RUNNING and when it calls schedule.
I guess what this points out is that in such a case, the event maker must make sure that the event is visible before it wakes up the process that's waiting on the event. But putting that logic into try_to_wake_up, IMHO is an overkill.
But...
Doing a quick search on wake_up, I came across loop.c (also my first hit).
Here we have: (some funcs pulled in).
loop_make_request:
lo->lo_bio = lo->lo_biotail = bio;
wake_up(&lo->lo_event);
And with wait_event_interruptible(lo->lo_event, lo->lo_bio) we have:
prepare_to_wait(..., TASK_INTERRUPTIBLE);
if (lo->bio)
break;
schedule_timeout();So this probably also has the same bug!
There's nothing to prevent the CPU from showing lo->bio has changed *after* setting wake_up to TASK_RUNNING.
So maybe this *is* a race condition that is all over the kernel for other architectures!
-- Steve
Quoted 19 lines · Steven Rostedt
But...
Doing a quick search on
wake_up, I came acrossloop.c(also my first hit).Here we have: (some funcs pulled in).
loop_make_request:
lo->lo_bio=lo->lo_biotail= bio;
wake_up(&lo->lo_event);And with
wait_event_interruptible(lo->lo_event, lo->lo_bio)we have:prepare_to_wait(..., TASK_INTERRUPTIBLE); if (lo->bio) break; schedule_timeout();
Quoted 7 lines
So this probably also has the same bug!
There's nothing to prevent the CPU from showing
lo->biohas changed *after* settingwake_uptoTASK_RUNNING.So maybe this *is* a race condition that is all over the kernel for other architectures!
Talking this over with Stephen Tweedie, he pointed out to me that the setting of the task state is done within the wait queue locks, and thus, the above is not a problem.
But the old paradigm of:
add_wait_queue();
for (;;) {
task->state = TASK_INTERRUPTIBLE;
if (condition)
break;
schedule();}
Can still be a bug, since the other CPU might hold off the condition to after it set the state to TASK_RUNNING.
-- Steve
Quoted 9 lines · Steven Rostedt
It is relevant. In powerpc, can one write happen before another write?
x = 1; barrier(); (only compiler barrier) b = 2;And have CPU 2 see b=2 before seeing x=1?
Yes. Definitely.
Quoted 1 line
If so, then I guess this is indeed a bug on powerpc.
Ben.
Quoted 5 lines · Benjamin Herrenschmidt
Quoted 3 lines · Steven Rostedt
It is relevant. In powerpc, can one write happen before another write?
Quoted 8 lines
Quoted 6 lines
x = 1; barrier(); (only compiler barrier) b = 2;And have CPU 2 see b=2 before seeing x=1?
Yes. Definitely.
OK, I see in powerpc, that spin lock calls isync. This just clears the pipeline. It doesn't touch the loads and stores, right?
So basically saying this:
x=1;
asm ("isync");
b=2;Would that have the same problem too? Where another CPU can see x=1 before seeing b=2?
Thanks!
-- Steve
Quoted 12 lines · Steven Rostedt
Quoted 10 lines · Benjamin Herrenschmidt
Quoted 8 lines · Steven Rostedt
It is relevant. In powerpc, can one write happen before another write?
x = 1; barrier(); (only compiler barrier) b = 2;
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
And have CPU 2 see b=2 before seeing x=1?
Yes. Definitely.
OK, I see in powerpc, that spin lock calls isync. This just clears the pipeline. It doesn't touch the loads and stores, right?
Yes. That isync is to prevent loads to be speculated accross spin_lock, thus leaking out of the lock by the top. In fact, it doesn't act on the load per-se but it prevent speculative execution accross the conditional branch in the spin_lock.
Quoted 8 lines
So basically saying this:
x=1; asm ("isync"); b=2;Would that have the same problem too? Where another CPU can see x=1 before seeing b=2?
Yes.
What isync provides is
a = *foospin_lock_loop_with_conditional_branch
isync
b = *bar
It prevents the read of b from being speculated by the CPU ahead of a
Ben.