kthread: (possibly) a missing memory barrier in kthread_stop()
RFC PATCH 1/1 kthread: (possibly) a missing memory barrier in kthread_stop()
Hi,
[ description ]
Subject: kthread: add a memory barrier to kthread_stop()
'kthread' threads do a check in the following order:
- set_current_state(TASK_INTERRUPTIBLE);
- kthread_should_stop();
and set_current_state() implies an smp_mb().
on another side (kthread_stop), wake_up_process() does not seem to guarantee a full mb.
And 'kthread_stop_info.k' must be visible before wake_up_process() checks for/modifies a state of the 'kthread' task.
(the patch is at the end of the message)
[ more detailed description ]
the current code might well be safe in case a to-be-stopped 'kthread' task is _not_ running on another CPU at the moment when kthread_stop() is called (in this case, 'rq->lock' will act as a kind of synch. point/barrier).
Another case is as follows:
CPU#0:
...
while (kthread_should_stop()) {
if (condition)
schedule();
/* ... do something useful ... */ <--- EIP
set_current_state(TASK_INTERRUPTIBLE);
}so a 'kthread' task is about to callset_current_state(TASK_INTERRUPTIBLE) ...
(in the mean time)
CPU#1:
kthread_stop()
-> kthread_stop_info.k = k (*)
-> wake_up_process()
wake_up_process() looks like:
(try_to_wake_up)
IRQ_OFF
LOCK
old_state = p->state;
if (!(old_state & state)) (**)
goto out;
...
UNLOCKIRQ_ON
let's suppose (*) and (**) are reordered
(according to Documentation/memory-barriers.txt, neither IRQ_OFF nor LOCK may prevent it from happening).
- the state is TASK_RUNNING, so we are about to return.
- CPU#1 is about to execute (*) (it's guaranteed to be done before spin_unlock(&rq->lock) at the end of try_to_wake_up())
(in the mean time)
CPU#0:
- set_current_state(TASK_INTERRUPTIBLE);
- kthread_should_stop();
here, kthread_stop_info.k is not yet visible
- schedule()
...
we missed a 'kthread_stop' event.
hum?
TIA,
---
From: Dmitry Adamushko <[email protected]>
Subject: kthread: add a memory barrier to kthread_stop()
'kthread' threads do a check in the following order:
- set_current_state(TASK_INTERRUPTIBLE);
- kthread_should_stop();
and set_current_state() implies an smp_mb().
on another side (kthread_stop), wake_up_process() is not guaranteed to act as a full mb.
'kthread_stop_info.k' must be visible before wake_up_process() checks for/modifies a state of the 'kthread' task.
kernel/kthread.c +4 -0
@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb (); +wake_up_process (k);put_task_struct (k);
Quoted 93 lines · Dmitry Adamushko
Hi,
[ description ]
Subject: kthread: add a memory barrier to
kthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()does not seem to guarantee a full mb.And 'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.(the patch is at the end of the message)
[ more detailed description ]
the current code might well be safe in case a to-be-stopped 'kthread' task is _not_ running on another CPU at the moment when
kthread_stop()is called (in this case, 'rq->lock' will act as a kind of synch. point/barrier).Another case is as follows:
CPU#0:
...
while (kthread_should_stop()) {if (condition) schedule(); /* ... do something useful ... */ <--- EIP set_current_state(TASK_INTERRUPTIBLE); }so a 'kthread' task is about to call
set_current_state(TASK_INTERRUPTIBLE)...(in the mean time)
CPU#1:
kthread_stop()-> kthread_stop_info.k = k (*)
->wake_up_process()
wake_up_process()looks like:(
try_to_wake_up)
IRQ_OFF
LOCK
old_state=p->state;
if (!(old_state & state)) (**)goto out;...
UNLOCK
IRQ_ONlet's suppose (*) and (**) are reordered
(according toDocumentation/memory-barriers.txt, neitherIRQ_OFFnor LOCK may prevent it from happening).- the state is
TASK_RUNNING, so we are about to return.- CPU#1 is about to execute (*) (it's guaranteed to be done before
spin_unlock(&rq->lock)at the end oftry_to_wake_up())(in the mean time)
CPU#0:
-
set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();here, kthread_stop_info.k is not yet visible
Quoted 7 lines
-
schedule()...
we missed a '
kthread_stop' event.hum?
Looks like you are correct to me.
Quoted 41 lines
TIA,
---
From: Dmitry Adamushko <[email protected]>
Subject: kthread: add a memory barrier tokthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()is not guaranteed to act as a full mb.'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.Signed-off-by Dmitry Adamushko <[email protected]>kernel/kthread.c +4
-1@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb (); +wake_up_process (k);put_task_struct (k); --
Quoted 134 lines · Nick Piggin
Quoted 93 lines · Dmitry Adamushko
Hi,
[ description ]
Subject: kthread: add a memory barrier to
kthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()does not seem to guarantee a full mb.And 'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.(the patch is at the end of the message)
[ more detailed description ]
the current code might well be safe in case a to-be-stopped 'kthread' task is _not_ running on another CPU at the moment when
kthread_stop()is called (in this case, 'rq->lock' will act as a kind of synch. point/barrier).Another case is as follows:
CPU#0:
...
while (kthread_should_stop()) {if (condition) schedule(); /* ... do something useful ... */ <--- EIP set_current_state(TASK_INTERRUPTIBLE); }so a 'kthread' task is about to call
set_current_state(TASK_INTERRUPTIBLE)...(in the mean time)
CPU#1:
kthread_stop()-> kthread_stop_info.k = k (*)
->wake_up_process()
wake_up_process()looks like:(
try_to_wake_up)
IRQ_OFF
LOCK
old_state=p->state;
if (!(old_state & state)) (**)goto out;...
UNLOCK
IRQ_ONlet's suppose (*) and (**) are reordered
(according toDocumentation/memory-barriers.txt, neitherIRQ_OFFnor LOCK may prevent it from happening).- the state is
TASK_RUNNING, so we are about to return.- CPU#1 is about to execute (*) (it's guaranteed to be done before
spin_unlock(&rq->lock)at the end oftry_to_wake_up())(in the mean time)
CPU#0:
-
set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();here, kthread_stop_info.k is not yet visible
Quoted 7 lines
-
schedule()...
we missed a '
kthread_stop' event.hum?
Looks like you are correct to me.
Quoted 29 lines
TIA,
---
From: Dmitry Adamushko <[email protected]>
Subject: kthread: add a memory barrier tokthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()is not guaranteed to act as a full mb.'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.Signed-off-by Dmitry Adamushko <[email protected]>kernel/kthread.c +0
-0@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)
Quoted 5 lines
kernel/kthread.c int kthread_stop(struct task_struct *k) · line 216
Quoted 5 lines
kernel/kthread.c +3
-0/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb ();
Does this not also imply you need a matching barrier in kthread_should_stop() ?
Quoted 7 lines
Quoted 6 lines
kernel/kthread.c +0
-1wake_up_process (k);put_task_struct (k); --
Quoted 27 lines · Peter Zijlstra
[ ... ]
Quoted 26 lines
Quoted 26 lines
From: Dmitry Adamushko <[email protected]>
Subject: kthread: add a memory barrier tokthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()is not guaranteed to act as a full mb.'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.Signed-off-by Dmitry Adamushko <[email protected]>kernel/kthread.c +0
-0@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)
Quoted 8 lines
Quoted 5 lines
kernel/kthread.c int kthread_stop(struct task_struct *k) · line 216
Quoted 5 lines
kernel/kthread.c +3
-0/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb ();Does this not also imply you need a matching barrier in
kthread_should_stop()?
Yes, but only when it's used in combination with something that alters a state of the task.
So it's rather a question of the interface-design.
We currently impose a requirement on how a main loop of 'kthread' threads (ok, so it seems to dictate a policy :-) has to be orginized. Namely, the following sequence must be kept in order:
(1) set_current_task(TASK_INTERRUPTIBLE);
(2) kthread_should_stop()
...
- schedule()
and (1) already provides a mb which becomes a "matching barrier" on the kthread_should_stop() side.
Signature · 2 lines
Best regards, Dmitry Adamushko
Quoted 131 lines · Dmitry Adamushko
Hi,
[ description ]
Subject: kthread: add a memory barrier to
kthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()does not seem to guarantee a full mb.And 'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.(the patch is at the end of the message)
[ more detailed description ]
the current code might well be safe in case a to-be-stopped 'kthread' task is _not_ running on another CPU at the moment when
kthread_stop()is called (in this case, 'rq->lock' will act as a kind of synch. point/barrier).Another case is as follows:
CPU#0:
...
while (kthread_should_stop()) {if (condition) schedule(); /* ... do something useful ... */ <--- EIP set_current_state(TASK_INTERRUPTIBLE); }so a 'kthread' task is about to call
set_current_state(TASK_INTERRUPTIBLE)...(in the mean time)
CPU#1:
kthread_stop()-> kthread_stop_info.k = k (*)
->wake_up_process()
wake_up_process()looks like:(
try_to_wake_up)
IRQ_OFF
LOCK
old_state=p->state;
if (!(old_state & state)) (**)goto out;...
UNLOCK
IRQ_ONlet's suppose (*) and (**) are reordered
(according toDocumentation/memory-barriers.txt, neitherIRQ_OFFnor LOCK may prevent it from happening).- the state is
TASK_RUNNING, so we are about to return.- CPU#1 is about to execute (*) (it's guaranteed to be done before
spin_unlock(&rq->lock)at the end oftry_to_wake_up())(in the mean time)
CPU#0:
-
set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();here, kthread_stop_info.k is not yet visible
-
schedule()...
we missed a '
kthread_stop' event.hum?
TIA,
---
From: Dmitry Adamushko <[email protected]>
Subject: kthread: add a memory barrier tokthread_stop()'kthread' threads do a check in the following order:
-set_current_state(TASK_INTERRUPTIBLE);
-kthread_should_stop();and
set_current_state()implies ansmp_mb().on another side (
kthread_stop),wake_up_process()is not guaranteed to act as a full mb.'kthread_stop_info.k' must be visible before
wake_up_process()checks for/modifies a state of the 'kthread' task.Signed-off-by Dmitry Adamushko <[email protected]>kernel/kthread.c +0
-0
kernel/kthread.c int kthread_stop(struct task_struct *k) · line 219
Quoted 9 lines
kernel/kthread.c +4
-0@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb (); +wake_up_process (k);put_task_struct (k);
The rules as written do seem to support your theory. The CPU has every right to delay the .k = k as late as the UNLOCK operation.
On the read-side there is a full barrier implied by the set_current_state(TASK_INTERRUPTIBLE), however this synchronises us with the current global state, which may well not have the updated version of .k.
That seems to imply that a write memory barrier would be sufficient to cover this.
So three comments. First, should this not be an smp_wmb. Second, this memory barrier is paired with the barrier in set_current_state(TASK_INTERRUPTIBLE) and that probabally should be documented as part of this patch. Finally, I think the comment as is is hard to understand I got the sense of it backwards on first reading; perhaps something like this:
/* * Ensure kthread_stop_info.k is visible before wakeup, paired * with barrier in set_current_state(). */
-apw
Quoted 20 lines · Andy Whitcroft
[ ... ]
Quoted 5 lines
kernel/kthread.c +0
-0kernel/kthread.c int kthread_stop(struct task_struct *k) · line 219
Quoted 9 lines
kernel/kthread.c +4
-0@@ -211,6 +211,10 @@ int kthread_stop(struct task_struct *k)/* Now set kthread_should_stop() to true, and wake it up. */ kthread_stop_info.k = k; + +/* The previous store operation must not get ahead of the wakeup. */ +smp_mb (); +wake_up_process (k);put_task_struct (k);The rules as written do seem to support your theory. The CPU has every right to delay the .k = k as late as the UNLOCK operation.
Quoted 4 lines
On the read-side there is a full barrier implied by the
set_current_state(TASK_INTERRUPTIBLE), however this synchronises us with the current global state, which may well not have the updated version of .k.
yes.
Quoted 5 lines
That seems to imply that a write memory barrier would be sufficient to cover this.
So three comments. First, should this not be an
smp_wmb.
No. We also need to be sure that ".k = k" is updated by the moment we check for a state of the task in try_to_wake_up(), so that's write vs. read ops.
The point is that a 'kthread' loop does :
(1) set TASK_INTERRUPTIBLE
(2) check for .k == k
and kthread_stop() must do it in the _reverse_ order:
(1) .k = k
(2) check for a task state and wakeup if necessary.
Only this way we ensure that a wakeup is not lost.
Quoted 11 lines
Second, this
memory barrier is paired with the barrier inset_current_state(TASK_INTERRUPTIBLE)and that probabally should be documented as part of this patch. Finally, I think the comment as is is hard to understand I got the sense of it backwards on first reading; perhaps something like this:/*
* Ensure kthread_stop_info.k is visible before wakeup, paired
* with barrier inset_current_state().
*/
Yes, I'll try to come up with a better description.
Quoted 3 lines
-apw
Signature · 2 lines
Best regards, Dmitry Adamushko
btw.,
(a bit more of 'nit-picking' :-)
to work properly, kthread_stop() should also impose one of the following requirements on a 'kthread' loop:
- a loop can be interrupted _only_ as a result of 'kthread_should_stop() == true'
and no concurrent kthread_stop() calls are possible;
or
- if it can exit due to another reason, a user has to use additional synchronization means to make sure than kthread_stop() is never called/running after a main loop has finished (makes sense as 'struct task_struct *' can be 'obsolete')
otherwise,
note, the comment in kthread() that says "It might have exited on its own, w/o kthread_stop. Check."
so let's suppose a 'kthread' is really "exiting on its own" and at the same time, kthread_stop() is running on another CPU... as a result, we may end up with kthread_stop() being blocked on wait_for_completion(&kthread_stop_info.done) without anybody to call complete().
Although, the requirements above don't seem to be so insane in this case.
static int kthread(void *_create)
{
...
if (!kthread_should_stop())
ret = threadfn(data); <---- our main loop is
inside this function
/* It might have exited on its own, w/o kthread_stop. Check. */
if (kthread_should_stop()) {
kthread_stop_info.err = ret;
complete(&kthread_stop_info.done);
}
return 0;
}Signature · 2 lines
Best regards, Dmitry Adamushko
humm... following the same logic, there is also a problem in kthread.c.
(1) the main loop of kthreadd() :
set_current_state(TASK_INTERRUPTIBLE);
if (list_empty(&kthread_create_list))
schedule();and
(2) kthread_create() does:
spin_lock(&kthread_create_lock); list_add_tail(&create.list, &kthread_create_list); wake_up_process(kthreadd_task); spin_unlock(&kthread_create_lock);
provided,
- (1) doesn't want to take the 'kthread_create_lock' in order to do a check for list_empty(&kthread_create_list)
[ which can be possible if list_empty() results in a single word-size aligned read op. -- which is guaranteed to be atomic on any arch, iirc ]
and
- (1) and (2) can run in parallel.
then it's crucial that a modification of the list (i.e. list_add_tail()) is completed by the moment a state of the task (kthreadd_task->state) is checked in try_to_wake_up(). i.e. they must not be re-ordered.
which makes me think that try_to_wake_up() could be better off just acting as a full mb.
otherwise, a possible fix would be:
this way we get a pair of UNLOCK/LOCK which is guaranteed to be a full mb (the LOCK is in try_to_wake_up())
[ moreover, there seems to be no need to call wake_up_process() with 'kthread_create_lock' being held ]
kernel/kthread.c +0 -0
@@ -145,8 +145,8 @@ struct task_struct *kthread_create(int
(*threadfn)(void *data),
spin_lock(&kthread_create_lock);
list_add_tail(&create.list, &kthread_create_list);
- wake_up_process(kthreadd_task);
spin_unlock(&kthread_create_lock);+ wake_up_process(kthreadd_task);
wait_for_completion(&create.done);
Signature · 2 lines
Best regards, Dmitry Adamushko