slow_work_thread() should do the exclusive wait
Subsystems (2)
PATCH 1/1 slow_work_thread() should do the exclusive wait
slow_work_thread() sleeps on slow_work_thread_wq without WQ_FLAG_EXCLUSIVE, this means that slow_work_enqueue()->__wake_up(nr_exclusive => 1) wakes up all kslowd threads. Afaics this is not what we want, change slow_work_thread() to use prepare_to_wait_exclusive().
kernel/slow-work.c renamed from kernel/slow-work.c~1_SW_EXCLUSIVE +2 -2
@@ -372,8 +372,8 @@ static int slow_work_thread(void *_data) vsmax *=atomic_read (&slow_work_thread_count); vsmax /=100 ; -prepare_to_wait (&slow_work_thread_wq, &wait, -TASK_INTERRUPTIBLE ); +prepare_to_wait_exclusive (&slow_work_thread_wq, &wait, +TASK_INTERRUPTIBLE ); if (!freezing(current) && !slow_work_threads_should_exit && !slow_work_available(vsmax) &&
Quoted 11 lines · Oleg Nesterov
slow_work_thread()sleeps onslow_work_thread_wqwithoutWQ_FLAG_EXCLUSIVE, this means that slow_work_enqueue()->__wake_up(nr_exclusive => 1) wakes up all kslowd threads. Afaics this is not what we want, changeslow_work_thread()to useprepare_to_wait_exclusive().Signed-off-by Oleg Nesterov <[email protected]>
kernel/slow-work.c static int slow_work_thread(void *_data) · line 379
Quoted 10 lines
kernel/slow-work.c renamed from kernel/slow-work.c~1_SW_EXCLUSIVE +2
-2@@ -372,8 +372,8 @@ static int slow_work_thread(void *_data) vsmax *=atomic_read (&slow_work_thread_count); vsmax /=100 ; -prepare_to_wait (&slow_work_thread_wq, &wait, -TASK_INTERRUPTIBLE ); +prepare_to_wait_exclusive (&slow_work_thread_wq, &wait, +TASK_INTERRUPTIBLE ); if (!freezing(current) && !slow_work_threads_should_exit && !slow_work_available(vsmax) &&
Should that really be TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...
Cheers
Trond
Signature · 6 lines
Trond Myklebust Linux NFS client maintainer NetApp [email protected] www.netapp.com
Quoted 15 lines · Trond Myklebust
Quoted 13 lines · Oleg Nesterov
slow_work_thread()sleeps onslow_work_thread_wqwithoutWQ_FLAG_EXCLUSIVE, this means that slow_work_enqueue()->__wake_up(nr_exclusive => 1) wakes up all kslowd threads. Afaics this is not what we want, changeslow_work_thread()to useprepare_to_wait_exclusive().Signed-off-by Oleg Nesterov <[email protected]>kernel/slow-work.c renamed from kernel/slow-work.c~1_SW_EXCLUSIVE +0
-0@@ -372,8 +372,8 @@ static int slow_work_thread(void *_data) vsmax *=atomic_read (&slow_work_thread_count); vsmax /=100 ;
Quoted 11 lines
kernel/slow-work.c static int slow_work_thread(void *_data) · line 379
Quoted 8 lines
kernel/slow-work.c renamed from kernel/slow-work.c~1_SW_EXCLUSIVE +2
-2-prepare_to_wait (&slow_work_thread_wq, &wait, -TASK_INTERRUPTIBLE ); +prepare_to_wait_exclusive (&slow_work_thread_wq, &wait, +TASK_INTERRUPTIBLE ); if (!freezing(current) && !slow_work_threads_should_exit && !slow_work_available(vsmax) &&Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...
I guess TASK_INTERRUPTIBLE was chosen to not contribute to calc_load(), nr_active() returns nr_running + nr_uninterruptible.
Oleg.
David Howells
maintainerQuoted 2 lines · Trond Myklebust
Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...
If it were TASK_UNINTERRUPTIBLE, it would sit there in the D-state when not doing anything. I must admit, I thought I was calling daemonize(), but that seems to have got lost somewhere.
David
Quoted 9 lines · David Howells
Quoted 2 lines · Trond Myklebust
Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...If it were
TASK_UNINTERRUPTIBLE, it would sit there in the D-state when not doing anything. I must admit, I thought I was callingdaemonize(), but that seems to have got lost somewhere.
daemonize() is not needed, kthread_create() creates the kernel thread which ignores all signals. So it doesn't matter which state we use to sleep, TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE.
Oleg.
Quoted 7 lines · Oleg Nesterov
Quoted 6 lines · David Howells
Quoted 2 lines · Trond Myklebust
Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...
Quoted 7 lines
Quoted 3 lines
If it were
TASK_UNINTERRUPTIBLE, it would sit there in the D-state when not doing anything. I must admit, I thought I was callingdaemonize(), but that seems to have got lost somewhere.
daemonize()is not needed,kthread_create()creates the kernel thread which ignores all signals. So it doesn't matter which state we use to sleep,TASK_INTERRUPTIBLEorTASK_UNINTERRUPTIBLE.
Yes, but that is precisely why it is cleaner to use TASK_UNINTERRUPTIBLE. It documents the fact that signal handling isn't needed (whether or not the thread is blocking them).
Trond
Signature · 6 lines
Trond Myklebust Linux NFS client maintainer NetApp [email protected] www.netapp.com
Quoted 13 lines · Trond Myklebust
Quoted 11 lines · Oleg Nesterov
Quoted 9 lines · David Howells
Quoted 2 lines · Trond Myklebust
Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...If it were
TASK_UNINTERRUPTIBLE, it would sit there in the D-state when not doing anything. I must admit, I thought I was callingdaemonize(), but that seems to have got lost somewhere.
Quoted 7 lines
Quoted 3 lines
daemonize()is not needed,kthread_create()creates the kernel thread which ignores all signals. So it doesn't matter which state we use to sleep,TASK_INTERRUPTIBLEorTASK_UNINTERRUPTIBLE.Yes, but that is precisely why it is cleaner to use
TASK_UNINTERRUPTIBLE. It documents the fact that signal handling isn't needed (whether or not the thread is blocking them).
Agreed. But TASK_UNINTERRUPTIBLE can confuse a user which does "cat /proc/loadavg" on the idle machine...
Note that, for example, worker_thread() uses TASK_INTERRUPTIBLE too, and I think for the same reason.
I dunno.
Oleg.
Quoted 22 lines · On Tue, 14 Apr 2009 00:24:51 +0200 Oleg Nesterov <[email protected]> wrote:
Quoted 13 lines · Trond Myklebust
Quoted 11 lines · Oleg Nesterov
Quoted 9 lines · David Howells
Quoted 2 lines · Trond Myklebust
Should that really be
TASK_INTERRUPTIBLE? I don't see anything obvious in the enclosing for(;;) loop that checks for or handles signals...If it were
TASK_UNINTERRUPTIBLE, it would sit there in the D-state when not doing anything. I must admit, I thought I was callingdaemonize(), but that seems to have got lost somewhere.Quoted 7 lines
Quoted 3 lines
daemonize()is not needed,kthread_create()creates the kernel thread which ignores all signals. So it doesn't matter which state we use to sleep,TASK_INTERRUPTIBLEorTASK_UNINTERRUPTIBLE.Yes, but that is precisely why it is cleaner to use
TASK_UNINTERRUPTIBLE. It documents the fact that signal handling isn't needed (whether or not the thread is blocking them).
Quoted 6 lines
Agreed. But
TASK_UNINTERRUPTIBLEcan confuse a user which does "cat/proc/loadavg" on the idle machine...Note that, for example,
worker_thread()usesTASK_INTERRUPTIBLEtoo, and I think for the same reason.
Yup. It's a very common pattern for kernel threads to sleep in state TASK_INTERRUPTIBLE. It is "well known" (lol) that kernel threads don't accept signals, and having a kernel thread sleep in state TASK_UNINTERRUPTIBLE will indeed contribute to load average and we get distressed emails quite promptly when we do that.
The patch itself is a little worrisome. The wake-all semantics are very good at covering up little race bugs. And switching to wake-once is a great way of exposing hitherto-unsuspected races.
<looks for races>
Nothing immediately leaps out, but you know how these things are.
I wonder if slow_work_cull_timeout() should have some sort of barrier, so the write is suitably visible to the woken thread. Bearing in mind that the thread might _already_ have been woken by someone else?
off-topic: afacit the code will cull a maximum of one thread per five seconds. But the rate of thread _creation_ is, afacit, unbound. Are there scenarios in which we can get a runaway thread count?
David Howells
maintainerQuoted 3 lines · Andrew Morton
The patch itself is a little worrisome. The wake-all semantics are very good at covering up little race bugs. And switching to wake-once is a great way of exposing hitherto-unsuspected races.
It's something I'm intending to test, once I get MN10300 working again (which for some reason it isn't).
Quoted 2 lines
I wonder if
slow_work_cull_timeout()should have some sort of barrier, so the write is suitably visible to the woken thread.
That's an interesting question. Should wake_up() imply a barrier of any sort, I wonder. Well, __wake_up() does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
Quoted 2 lines
Bearing in mind that the thread might _already_ have been woken by someone else?
If the thread is woken by someone else, there must be work for it to do, in which case it wouldn't be culled anyway.
Quoted 3 lines
off-topic: afacit the code will cull a maximum of one thread per five seconds. But the rate of thread _creation_ is, afacit, unbound. Are there scenarios in which we can get a runaway thread count?
The maximum number of threads is limited (slow_work_max_threads).
David
Quoted 9 lines · David Howells
Quoted 2 lines · Andrew Morton
I wonder if
slow_work_cull_timeout()should have some sort of barrier, so the write is suitably visible to the woken thread.That's an interesting question. Should
wake_up()imply a barrier of any sort, I wonder. Well,__wake_up()does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
wake_up() does imply the barrier. Note the smp_wmb() in try_to_wake_up(). And in fact this wmb() implies mb(), because spin_lock() itself is STORE, and the futher LOADs can't leak up before spin_lock().
But afaics, this doesn't matter? prepare_to_wait() sets task->state under wait_queue_head_t->lock and wake_up() takes this look too, so we can't miss the event.
Or I completely misunderstood the issue...
Oleg.
David Howells
maintainerPATCH 1/1 Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 8 lines · Oleg Nesterov
Quoted 3 lines
That's an interesting question. Should
wake_up()imply a barrier of any sort, I wonder. Well,__wake_up()does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
wake_up()does imply the barrier. Note thesmp_wmb()intry_to_wake_up(). And in fact thiswmb()impliesmb(), becausespin_lock()itself is STORE, and the futher LOADs can't leak up beforespin_lock().
Quoted 5 lines
But afaics, this doesn't matter?
prepare_to_wait()setstask->stateunderwait_queue_head_t->lockandwake_up()takes this look too, so we can't miss the event.Or I completely misunderstood the issue...
The problem is not what wake_up() and co. do, it's what you are allowed to assume that they do.
However, I think you're right, and that we can assume they imply a full memory barrier. To this end, I've attached a patch to document this.
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Add to the memory barriers document to note that wake_up(), complete() and co. all imply a full memory barrier.
---
Documentation/memory-barriers.txt | 4 ++++ kernel/sched.c | 10 ++++++++++ 2 files changed, 14 insertions(+), 0 deletions(-)
Documentation/memory-barriers.txt +4 -0
@@ -1224,6 +1224,10 @@ Other functions that imply barriers: (*) schedule() and similar imply full memory barriers. + (*) wake_up(), try_to_wake_up() and co. imply a full memory barrier. + + (*) complete() and co. imply a full memory barrier. + ================================= INTER-CPU LOCKING BARRIER EFFECTS
kernel/sched.c +10 -0
@@ -2337,6 +2337,8 @@ static int sched_balance_self(int cpu, int flag)* runnable without the overhead of this. * * returns failure only if the task is already active. +* +* It may be assumed that this function implies a full memory barrier. */ static int try_to_wake_up (struct task_struct *p,unsigned int state,int sync) {
@@ -5241,6 +5243,8 @@ void __wake_up_common(wait_queue_head_t *q, unsigned int mode,* @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function +* +* It may be assumed that this function implies a full memory barrier. */ void __wake_up (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5279,6 +5283,8 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)* with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. +* +* It may be assumed that this function implies a full memory barrier. */ void __wake_up_sync_key (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5315,6 +5321,8 @@ EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */* awakened in the same order in which they were queued. * * See also complete_all(), wait_for_completion() and related routines. +* +* It may be assumed that this function implies a full memory barrier. */ void complete (struct completion *x) {
@@ -5332,6 +5340,8 @@ EXPORT_SYMBOL(complete);* @x: holds the state of this particular completion * * This will wake up all threads waiting on this particular completion event. +* +* It may be assumed that this function implies a full memory barrier. */ void complete_all (struct completion *x) {
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 23 lines · David Howells
Quoted 8 lines · Oleg Nesterov
Quoted 3 lines
That's an interesting question. Should
wake_up()imply a barrier of any sort, I wonder. Well,__wake_up()does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
wake_up()does imply the barrier. Note thesmp_wmb()intry_to_wake_up(). And in fact thiswmb()impliesmb(), becausespin_lock()itself is STORE, and the futher LOADs can't leak up beforespin_lock().Quoted 5 lines
But afaics, this doesn't matter?
prepare_to_wait()setstask->stateunderwait_queue_head_t->lockandwake_up()takes this look too, so we can't miss the event.Or I completely misunderstood the issue...
The problem is not what
wake_up()and co. do, it's what you are allowed to assume that they do.However, I think you're right, and that we can assume they imply a full memory barrier. To this end, I've attached a patch to document this.
Quoted 7 lines
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document thatwake_up(),complete()and co. imply a full memory barrierAdd to the memory barriers document to note that
wake_up(),complete()and co. all imply a full memory barrier.
No. They dont generally imply a full memory barrier versus any arbitrary prior (or following) memory access.
try_to_wake_up() has an smp_wmb() so it is a write memory barrier (but not necessarily a read memory barrier). Otherwise there are spinlocks there but spinlocks are not explicit 'full memory barriers'.
Also, there's a sub-detail wrt. the wake_up() variants in that they have a fastpath for the !q case - then they dont have any atomics at all - they just return straight away.
Another sub-detail: wakeups using a special wakeup handler might not even call try_to_wake_up() - so in their case not even a write barrier can be assumed.
So your patch is misleading in a number of areas here.
Ingo
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 34 lines · Ingo Molnar
Quoted 23 lines · David Howells
Quoted 8 lines · Oleg Nesterov
Quoted 3 lines
That's an interesting question. Should
wake_up()imply a barrier of any sort, I wonder. Well,__wake_up()does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
wake_up()does imply the barrier. Note thesmp_wmb()intry_to_wake_up(). And in fact thiswmb()impliesmb(), becausespin_lock()itself is STORE, and the futher LOADs can't leak up beforespin_lock().Quoted 5 lines
But afaics, this doesn't matter?
prepare_to_wait()setstask->stateunderwait_queue_head_t->lockandwake_up()takes this look too, so we can't miss the event.Or I completely misunderstood the issue...
The problem is not what
wake_up()and co. do, it's what you are allowed to assume that they do.However, I think you're right, and that we can assume they imply a full memory barrier. To this end, I've attached a patch to document this.
Quoted 7 lines
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document thatwake_up(),complete()and co. imply a full memory barrierAdd to the memory barriers document to note that
wake_up(),complete()and co. all imply a full memory barrier.
Quoted 7 lines
No. They dont generally imply a full memory barrier versus any arbitrary prior (or following) memory access.
try_to_wake_up()has ansmp_wmb()so it is a write memory barrier (but not necessarily a read memory barrier). Otherwise there are spinlocks there but spinlocks are not explicit 'full memory barriers'.
Yes. But please look at the changelog in
"Add memory barrier semantics to wake_up() & co" 04e2f1741d235ba599037734878d72e57cb302b5
However, I must admit, I don't understand how to document the semantics correctly. This wmb() before spin_lock() ensures we don't read task->state before previous STOREs. This is what we care about, and this is what I meant when I said "this wmb() implies mb()".
So, I think that try_to_wake_up() implies that the LOADS after it can't be reordered with STOREs before it (and wmb() of course).
Oleg.
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 43 lines · Oleg Nesterov
Quoted 34 lines · Ingo Molnar
Quoted 23 lines · David Howells
Quoted 8 lines · Oleg Nesterov
Quoted 3 lines
That's an interesting question. Should
wake_up()imply a barrier of any sort, I wonder. Well,__wake_up()does impose a barrier as it uses a spinlock, but I wonder if that's sufficient.
wake_up()does imply the barrier. Note thesmp_wmb()intry_to_wake_up(). And in fact thiswmb()impliesmb(), becausespin_lock()itself is STORE, and the futher LOADs can't leak up beforespin_lock().Quoted 5 lines
But afaics, this doesn't matter?
prepare_to_wait()setstask->stateunderwait_queue_head_t->lockandwake_up()takes this look too, so we can't miss the event.Or I completely misunderstood the issue...
The problem is not what
wake_up()and co. do, it's what you are allowed to assume that they do.However, I think you're right, and that we can assume they imply a full memory barrier. To this end, I've attached a patch to document this.
Quoted 7 lines
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document thatwake_up(),complete()and co. imply a full memory barrierAdd to the memory barriers document to note that
wake_up(),complete()and co. all imply a full memory barrier.Quoted 7 lines
No. They dont generally imply a full memory barrier versus any arbitrary prior (or following) memory access.
try_to_wake_up()has ansmp_wmb()so it is a write memory barrier (but not necessarily a read memory barrier). Otherwise there are spinlocks there but spinlocks are not explicit 'full memory barriers'.
Quoted 4 lines
Yes. But please look at the changelog in
"Add memory barrier semantics to wake_up() & co" 04e2f1741d235ba599037734878d72e57cb302b5
yes - but still that commit is only wrt. the ->state check.
Quoted 8 lines
However, I must admit, I don't understand how to document the semantics correctly. This
wmb()beforespin_lock()ensures we don't readtask->statebefore previous STOREs. This is what we care about, and this is what I meant when I said "thiswmb()impliesmb()".So, I think that
try_to_wake_up()implies that the LOADS after it can't be reordered with STOREs before it (andwmb()of course).
Note that the patch David sent says "full memory barrier", not "full memory barrier wrt. task->state":
+ (*) wake_up(), try_to_wake_up() and co. imply a full memory barrier. +
+ (*) complete() and co. imply a full memory barrier.
These statements are not true in that form, as this code does not imply a full memory barrier. It does imply one on task->state _alone_ (and a couple of other wq-internal variables it happens to read for sure).
But even that one isnt entirely true in the two sub-cases i noted:
the !wq case (which can happen in object state teardown) and the special ->func handler (which can happen in custom wakeup code a'la eventpoll).
So adding a comment that says "this is a full memory barrier" is simply not true to that extent, and is easily misunderstood. Adding "this is a fully memory barrier for task->state dependent data flow" would be more correct. (with a 'as long as wq is not NULL, and as long as the code using this isnt overriding ->func)
Agreed?
Ingo
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 23 lines · Ingo Molnar
Quoted 2 lines · Oleg Nesterov
So, I think that
try_to_wake_up()implies that the LOADS after it can't be reordered with STOREs before it (andwmb()of course).Note that the patch David sent says "full memory barrier", not "full memory barrier wrt.
task->state":+ (*)
wake_up(),try_to_wake_up()and co. imply a full memory barrier. +
+ (*)complete()and co. imply a full memory barrier.These statements are not true in that form, as this code does not imply a full memory barrier. It does imply one on
task->state_alone_ (and a couple of other wq-internal variables it happens to read for sure).But even that one isnt entirely true in the two sub-cases i noted:
the !wq case (which can happen in object state teardown) and the special ->func handler (which can happen in custom wakeup code a'la eventpoll).
Quoted 7 lines
So adding a comment that says "this is a full memory barrier" is simply not true to that extent, and is easily misunderstood. Adding "this is a fully memory barrier for
task->statedependent data flow" would be more correct. (with a 'as long as wq is not NULL, and as long as the code using this isnt overriding ->func)Agreed?
Yes sure.
Except... not that it really matters, but the reading of ->state is not "special". I mean,
STORE; try_to_wake_up(); LOAD;
in this case try_to_wake_up() acts as a barrier for STORE/LOAD. But probably we should not rely on this. So personally I agree with "for task->state dependent data flow" above.
Oleg.
David Howells
maintainerRe: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
In reply to Ingo MolnarQuoted 7 lines · Ingo Molnar
No. They dont generally imply a full memory barrier versus any arbitrary prior (or following) memory access.
try_to_wake_up()has ansmp_wmb()so it is a write memory barrier (but not necessarily a read memory barrier). Otherwise there are spinlocks there but spinlocks are not explicit 'full memory barriers'.
Blech. That's a good point LOCK...UNLOCK does not imply a full barrier.
So we can't assume that complete(), wake_up() and co. imply any barriers.
All we can assume is that try_to_wake_up() implies a write barrier, but we can't assume that that will be called via __wake_up_common().
David
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 13 lines · David Howells
Quoted 7 lines · Ingo Molnar
No. They dont generally imply a full memory barrier versus any arbitrary prior (or following) memory access.
try_to_wake_up()has ansmp_wmb()so it is a write memory barrier (but not necessarily a read memory barrier). Otherwise there are spinlocks there but spinlocks are not explicit 'full memory barriers'.Blech. That's a good point LOCK...UNLOCK does not imply a full barrier.
Quoted 6 lines
So we can't assume that
complete(),wake_up()and co. imply any barriers.All we can assume is that
try_to_wake_up()implies a write barrier, but we can't assume that that will be called via__wake_up_common().
Yeah, it's all too special-case. We might rely on it in special, well-argued cases but we should not document it as a general barrier property.
Ingo
David Howells
maintainerRe: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
In reply to David HowellsQuoted 4 lines · David Howells
So we can't assume that
complete(),wake_up()and co. imply any barriers.All we can assume is that
try_to_wake_up()implies a write barrier, but we can't assume that that will be called via__wake_up_common().
So how about this, then?
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document that wake_up(), complete() and co. may not imply a memory barrier
Add to the memory barriers document to note that wake_up(), complete() and co. may not be assumed to imply any sort of memory barrier, with the exception of try_to_wake_up() and things derived from that.
---
Documentation/memory-barriers.txt | 34 +++++++++++++++++++++++++++++++++- kernel/sched.c | 10 ++++++++++ 2 files changed, 43 insertions(+), 1 deletions(-)
Documentation/memory-barriers.txt +33 -1
@@ -42,6 +42,7 @@ Contents: - Interprocessor interaction. - Atomic operations. + - Wake up of processes - Accessing devices. - Interrupts.
@@ -1224,6 +1225,9 @@ Other functions that imply barriers: (*) schedule() and similar imply full memory barriers. + (*) try_to_wake_up() and things derived from that imply a write memory + barrier. + ================================= INTER-CPU LOCKING BARRIER EFFECTS
@@ -1366,13 +1370,15 @@ WHERE ARE MEMORY BARRIERS NEEDED? Under normal operation, memory operation reordering is generally not going to be a problem as a single-threaded linear piece of code will still appear to -work correctly, even if it's in an SMP kernel. There are, however, three +work correctly, even if it's in an SMP kernel. There are, however, five circumstances in which reordering definitely _could_ be a problem: (*) Interprocessor interaction. (*) Atomic operations. + (*) Wake up of processes. + (*) Accessing devices. (*) Interrupts.
@@ -1568,6 +1574,32 @@ and in such cases the special barrier primitives will be no-ops. See Documentation/atomic_ops.txt for more information. +WAKE UP OF PROCESSES +-------------------- + +An unlock, write memory barrier or a full memory barrier may be needed before a +call to wake up another processes if the waker sets some state that the sleeper +will need to see. + + complete(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr(); + wake_up_interruptible_poll(); + wake_up_interruptible_sync(); + wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + +The sleeper may then need to interpolate a lock, read or full memory barrier +before accessing that state. + + ACCESSING DEVICES -----------------
kernel/sched.c +10 -0
@@ -2337,6 +2337,8 @@ static int sched_balance_self(int cpu, int flag)* runnable without the overhead of this. * * returns failure only if the task is already active. +* +* It may be assumed that this function implies a full memory barrier. */ static int try_to_wake_up (struct task_struct *p,unsigned int state,int sync) {
@@ -5241,6 +5243,8 @@ void __wake_up_common(wait_queue_head_t *q, unsigned int mode,* @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function +* +* It may not be assumed that this function implies any sort of memory barrier. */ void __wake_up (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5279,6 +5283,8 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)* with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void __wake_up_sync_key (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5315,6 +5321,8 @@ EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */* awakened in the same order in which they were queued. * * See also complete_all(), wait_for_completion() and related routines. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void complete (struct completion *x) {
@@ -5332,6 +5340,8 @@ EXPORT_SYMBOL(complete);* @x: holds the state of this particular completion * * This will wake up all threads waiting on this particular completion event. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void complete_all (struct completion *x) {
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 14 lines · David Howells
Documentation/memory-barriers.txt +14
-0+WAKE UP OF PROCESSES +-------------------- + +An unlock, write memory barrier or a full memory barrier may be needed before a +call to wake up another processes if the waker sets some state that the sleeper +will need to see. + + complete(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr();
Documentation/memory-barriers.txt and in such cases the special barrier primitives will be no-ops. · line 1600
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+ wake_up_interruptible_poll(); + wake_up_interruptible_sync(); + wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + +The sleeper may then need to interpolate a lock, read or full memory barrier +before accessing that state.
Why would an unlock be needed before a call to wake_up() variants?
If a piece of code does:
wake_up*(&object->wq); ... spin_unlock(&object->lock);
that's perfectly race-free, as long as the wakee always starts with something like:
spin_lock(&object->lock); ...
I.e. waking up sooner than dropping the lock always OK (and it's a frequent operation). Your text seems to imply that a barrier is needed (or the unlock needs to happen first) but that's wrong i think.
The dangerous pattern is lockless code doing wakeups. But lockless code always has to use proper barriers or atomics anyway, and has to be aware of the fact that kernel primitives they call are not necessarily full memory barriers.
In fact i'd encourage to _not_ document try_to_lock() as a write barrier either - but rather have explicit barriers where they are needed. Then we could remove that barrier from try_to_wake_up() too ;-)
Hm?
Ingo
David Howells
maintainerPATCH 1/1 It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 1 line · Ingo Molnar
Why would an unlock be needed before a call to
wake_up()variants?
Good point. I've amended my patch again (see attached).
Quoted 2 lines
In fact i'd encourage to _not_ document
try_to_lock()as a write barrier either
Did you mean try_to_wake_up()? Or did you mean things like spin_lock_trylock()? If the latter, it *has* to be a LOCK-class barrier if it succeeds - otherwise what's the point?
Quoted 2 lines
- but rather have explicit barriers where they are needed. Then we could remove that barrier from
try_to_wake_up()too ;-)
I was wondering if wake_up() and friends should in fact imply smp_wmb(), but I guess that they're often used in conjunction with spinlocks - and in such a situation a barrier is unnecessary overhead.
David
---
From: David Howells <[email protected]>
Subject: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Add to the memory barriers document to note that try_to_wake_up(), wake_up(), complete(), finish_wait() and co. should not be assumed to imply any sort of memory barrier.
This is because:
(1) A lot of the time, memory barriers in the wake-up and sleeper paths would be superfluous due to the use of locks.
(2) It is possible to pass right through wake_up() and co. without hitting anything at all or anything other than a spin_lock/spin_unlock (if try_to_wake_up() isn't invoked).
(3) The smp_wmb() should probably move out of try_to_wake_up() and into suitable places in its callers.
---
Documentation/memory-barriers.txt | 34 +++++++++++++++++++++++++++++++++- kernel/sched.c | 11 +++++++++++ 2 files changed, 44 insertions(+), 1 deletions(-)
Documentation/memory-barriers.txt +33 -1
@@ -42,6 +42,7 @@ Contents: - Interprocessor interaction. - Atomic operations. + - Wake up of processes - Accessing devices. - Interrupts.
@@ -1366,13 +1367,15 @@ WHERE ARE MEMORY BARRIERS NEEDED? Under normal operation, memory operation reordering is generally not going to be a problem as a single-threaded linear piece of code will still appear to -work correctly, even if it's in an SMP kernel. There are, however, three +work correctly, even if it's in an SMP kernel. There are, however, five circumstances in which reordering definitely _could_ be a problem: (*) Interprocessor interaction. (*) Atomic operations. + (*) Wake up of processes. + (*) Accessing devices. (*) Interrupts.
@@ -1568,6 +1571,35 @@ and in such cases the special barrier primitives will be no-ops. See Documentation/atomic_ops.txt for more information. +WAKE UP OF PROCESSES +-------------------- + +If locking is not used, and if the waker sets some state that the sleeper will +need to see, a write memory barrier or a full memory barrier may be needed +before one of the following calls is used to wake up another process: + + complete(); + try_to_wake_up(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr(); + wake_up_interruptible_poll(); + wake_up_interruptible_sync(); + wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + +After waking, and assuming it doesn't take a matching lock, the sleeper may +need to interpolate a read or full memory barrier before accessing that state +as finish_wait() does not imply a barrier either, and schedule() only implies a +barrier on entry. + + ACCESSING DEVICES -----------------
kernel/sched.c +11 -0
@@ -2337,6 +2337,9 @@ static int sched_balance_self(int cpu, int flag)* runnable without the overhead of this. * * returns failure only if the task is already active. +* +* It should not be assumed that this function implies any sort of memory +* barrier. */ static int try_to_wake_up (struct task_struct *p,unsigned int state,int sync) {
@@ -5241,6 +5244,8 @@ void __wake_up_common(wait_queue_head_t *q, unsigned int mode,* @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function +* +* It may not be assumed that this function implies any sort of memory barrier. */ void __wake_up (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5279,6 +5284,8 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)* with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void __wake_up_sync_key (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5315,6 +5322,8 @@ EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */* awakened in the same order in which they were queued. * * See also complete_all(), wait_for_completion() and related routines. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void complete (struct completion *x) {
@@ -5332,6 +5341,8 @@ EXPORT_SYMBOL(complete);* @x: holds the state of this particular completion * * This will wake up all threads waiting on this particular completion event. +* +* It may not be assumed that this function implies any sort of memory barrier. */ void complete_all (struct completion *x) {
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 11 lines · David Howells
Documentation/memory-barriers.txt +10
-0+ complete(); + try_to_wake_up(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr(); + wake_up_interruptible_poll(); + wake_up_interruptible_sync();
Documentation/memory-barriers.txt and in such cases the special barrier primitives will be no-ops. · line 1600
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+ wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + +After waking, and assuming it doesn't take a matching lock, the sleeper may +need to interpolate a read or full memory barrier before accessing that state +as finish_wait() does not imply a barrier either, and schedule() only implies a +barrier on entry.
Well. I am starting to suspect I missed something, but I disagree. Or I just (this is very possible) misunderstand the above.
finish_wait() doesn't imply a barrier, but why this matters?
And if we don't use prepare_to_wait() and just do
for (;;) {
set_current_state(WHATEVER);
if (!CONDITION)
schedule();
break;
}we do have mb(), but
Quoted 5 lines
+ *
+ * It should not be assumed that this function implies any sort of memory
+ * barrier.
*/
static inttry_to_wake_up(struct task_struct *p, unsigned int state, int sync)
unless try_to_wake_up() has a barrier semantics too, this code
CONDITION = 1; wake_up_process(waiter);
is not right, and that mb above can't help.
Could you please give the code example which shows we need a barrier after finish_wait() ?
I am just trying to understand what I missed.
Oleg.
David Howells
maintainerRe: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 2 lines · Oleg Nesterov
Well. I am starting to suspect I missed something, but I disagree. Or I just (this is very possible) misunderstand the above.
No, it's me getting myself confused. After thinking about it for a while, I see that you're right: the potential misordering, I think, is between the setting of the task state and reading the data value in the sleeper, and between the writing of the data value and the clearing of the task state in the waker.
That means that provided that:
(1) set_current_state() interpolates a full memory barrier after setting the task state then there's no problem in the sleeper, and
(2) wake_up() interpolates a write memory barrier before clearing the task state - _if_ it wakes anything up - then there's no problem in the waker either.
How about the attached doc patch?
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document memory barriers implied by sleep/wake-up primitives
Add a section to the memory barriers document to note the implied memory barriers of sleep primitives (set_current_state() and wrappers) and wake-up primitives (wake_up() and co.).
Also extend the in-code comments on the wake_up() functions to note these implied barriers.
---
Documentation/memory-barriers.txt | 93 +++++++++++++++++++++++++++++++++++++ kernel/sched.c | 23 +++++++++ 2 files changed, 115 insertions(+), 1 deletions(-)
Documentation/memory-barriers.txt +92 -1
@@ -31,6 +31,7 @@ Contents: - Locking functions. - Interrupt disabling functions. + - Sleep and wake-up functions. - Miscellaneous functions. (*) Inter-CPU locking barrier effects.
@@ -1217,6 +1218,96 @@ barriers are required in such a situation, they must be provided from some other means. +SLEEP AND WAKE-UP FUNCTIONS +--------------------------- + +Sleeping and waking on an event flagged in global data can be viewed as an +interaction between two pieces of data: the task state of the task waiting for +the event and the global data used to indicate the event. To make sure that +these appear to happen in the right order, the primitives to begin the process +of going to sleep, and the primitives to initiate a wake up imply certain +barriers. + +Firstly, the sleeper normally follows something like this sequence of events: + + for (;;) { + set_current_state(TASK_UNINTERRUPTIBLE); + if (event_indicated) + break; + schedule(); + } + +A general memory barrier is interpolated automatically by set_current_state() +after it has altered the task state: + + CPU 1 + =============================== + set_current_state(); + set_mb(); + STORE current->state + <general barrier> + LOAD event_indicated + +set_current_state() may be wrapped by: + + prepare_to_wait(); + prepare_to_wait_exclusive(); + +which therefore also imply a general memory barrier after setting the state. +The whole sequence above is available in various canned forms, all of which +interpolate the memory barrier in the right place: + + wait_event(); + wait_event_interruptible(); + wait_event_interruptible_exclusive(); + wait_event_interruptible_timeout(); + wait_event_killable(); + wait_event_timeout(); + wait_on_bit(); + wait_on_bit_lock(); + + +Secondly, code that performs a wake up normally follows something like this: + + event_indicated = 1; + wake_up(&event_wait_queue); + +or: + + event_indicated = 1; + wake_up_process(event_daemon); + +A write memory barrier is implied by wake_up() and co. if and only if they wake +something up. The barrier occurs before the task state is cleared, and so sits +between the STORE to indicate the event and the STORE to set TASK_RUNNING: + + CPU 1 CPU 2 + =============================== =============================== + set_current_state(); STORE event_indicated + set_mb(); wake_up(); + STORE current->state <write barrier> + <general barrier> STORE current->state + LOAD event_indicated + +The available waker functions include: + + complete(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr(); + wake_up_interruptible_poll(); + wake_up_interruptible_sync(); + wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + wake_up_process(); + + MISCELLANEOUS FUNCTIONS -----------------------
@@ -1366,7 +1457,7 @@ WHERE ARE MEMORY BARRIERS NEEDED? Under normal operation, memory operation reordering is generally not going to be a problem as a single-threaded linear piece of code will still appear to -work correctly, even if it's in an SMP kernel. There are, however, three +work correctly, even if it's in an SMP kernel. There are, however, four circumstances in which reordering definitely _could_ be a problem: (*) Interprocessor interaction.
kernel/sched.c +23 -0
@@ -2458,6 +2458,17 @@ out:return success; } +/** +* wake_up_process - Wake up a specific process +* @p: The process to be woken up. +* +* Attempt to wake up the nominated process and move it to the set of runnable +* processes. Returns 1 if the process was woken up, 0 if it was already +* running. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. +*/ int wake_up_process (struct task_struct *p) {return try_to_wake_up (p,TASK_ALL ,0 );
@@ -5241,6 +5252,9 @@ void __wake_up_common(wait_queue_head_t *q, unsigned int mode,* @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void __wake_up (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5279,6 +5293,9 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)* with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void __wake_up_sync_key (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)
@@ -5315,6 +5332,9 @@ EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */* awakened in the same order in which they were queued. * * See also complete_all(), wait_for_completion() and related routines. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void complete (struct completion *x) {
@@ -5332,6 +5352,9 @@ EXPORT_SYMBOL(complete);* @x: holds the state of this particular completion * * This will wake up all threads waiting on this particular completion event. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void complete_all (struct completion *x) {
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 13 lines · David Howells
Quoted 2 lines · Oleg Nesterov
Well. I am starting to suspect I missed something, but I disagree. Or I just (this is very possible) misunderstand the above.
No, it's me getting myself confused. After thinking about it for a while, I see that you're right: the potential misordering, I think, is between the setting of the task state and reading the data value in the sleeper, and between the writing of the data value and the clearing of the task state in the waker.
That means that provided that:
Quoted 8 lines
(1)
set_current_state()interpolates a full memory barrier after setting the task state then there's no problem in the sleeper, and(2)
wake_up()interpolates a write memory barrier before clearing the task state - _if_ it wakes anything up - then there's no problem in the waker either.How about the attached doc patch?
One question, assuming that this documentation intends to guide the reader on where to put the locking and/or memory-barrier primitives...
Suppose we have the following sequence of events:
1. The waiter does "set_current_state(TASK_UNINTERRUPTIBLE);".
This implies a full memory barrier.
2. The awakener updates some shared state.
3. The awakener does "event_indicated = 1;".
4. The waiter does "if (event_indicated)", and, finding that
the event has in fact been indicated, does "break".
5. The waiter accesses the shared state set in #2 above.
6. Some time later, the awakener does "wake_up(&event_wait_queue);"
This does not awaken anyone, so no memory barrier.
Because there is no memory barrier between #2 and #3, reordering by either the compiler or the CPU might cause the awakener to update the event_indicated flag in #3 -before- completing its update of shared state in #2. Less likely (but still possible) optimizations might cause the waiter to access the shared state in #5 before checking the event_indicated flag in #4.
So, for this to work correctly, don't we need at least an smp_wmb() between #2 and #3 and at least an smp_rmb() between #4 and #5? And if #2 does reads (but not writes) at least one variable in the shared state that #5 writes to, don't both barriers need to be smp_mb()?
Or should I have waited until fully waking up before replying to this email? ;-)
For everyone's amusement, I have placed these memory barriers in the code samples below.
And, yes, if these primitives are used with appropriate locks, then no memory barriers are required. So, again, for everyone's amusement, I have indicated where the locking primitives would go -- not necessarily where the memory barriers go due to the semipermeable nature of the barriers implied by the locking primitives.
If I understand the purpose of this documentation, it would be good to tell the reader where the required locks and/or memory barriers must go.
Thanx, Paul
Quoted 44 lines
David
---
From: David Howells <[email protected]>
Subject: [PATCH] Document memory barriers implied by sleep/wake-up primitivesAdd a section to the memory barriers document to note the implied memory barriers of sleep primitives (
set_current_state()and wrappers) and wake-up primitives (wake_up()and co.).Also extend the in-code comments on the
wake_up()functions to note these implied barriers.Signed-off-by David Howells <[email protected]>---
Documentation/memory-barriers.txt | 93 +++++++++++++++++++++++++++++++++++++ kernel/sched.c | 23 +++++++++ 2 files changed, 115 insertions(+), 1 deletions(-)Documentation/memory-barriers.txt +9
-0@@ -31,6 +31,7 @@ Contents: - Locking functions. - Interrupt disabling functions. + - Sleep and wake-up functions. - Miscellaneous functions. (*) Inter-CPU locking barrier effects.@@ -1217,6 +1218,96 @@ barriers are required in such a situation, they must be provided from some other means. +SLEEP AND WAKE-UP FUNCTIONS +--------------------------- + +Sleeping and waking on an event flagged in global data can be viewed as an +interaction between two pieces of data: the task state of the task waiting for +the event and the global data used to indicate the event. To make sure that +these appear to happen in the right order, the primitives to begin the process +of going to sleep, and the primitives to initiate a wake up imply certain
Documentation/memory-barriers.txt barriers are required in such a situation, they must be provided from some · line 1238
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+barriers. + +Firstly, the sleeper normally follows something like this sequence of events: + + for (;;) { + set_current_state(TASK_UNINTERRUPTIBLE); + if (event_indicated) + break; + schedule(); + }
smp_rmb(); /* or smp_mb() if writing later, or spin_lock(). */
Quoted 23 lines
Documentation/memory-barriers.txt +23
-0+ +A general memory barrier is interpolated automatically by set_current_state() +after it has altered the task state: + + CPU 1 + =============================== + set_current_state(); + set_mb(); + STORE current->state + <general barrier> + LOAD event_indicated + +set_current_state() may be wrapped by: + + prepare_to_wait(); + prepare_to_wait_exclusive(); + +which therefore also imply a general memory barrier after setting the state. +The whole sequence above is available in various canned forms, all of which +interpolate the memory barrier in the right place: + + wait_event(); + wait_event_interruptible();
Documentation/memory-barriers.txt barriers are required in such a situation, they must be provided from some · line 1271
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+ wait_event_interruptible_exclusive(); + wait_event_interruptible_timeout(); + wait_event_killable(); + wait_event_timeout(); + wait_on_bit(); + wait_on_bit_lock(); + + +Secondly, code that performs a wake up normally follows something like this: +
smp_wmb(); /* or smp_mb() if trailing prior read to a variable. */
Documentation/memory-barriers.txt barriers are required in such a situation, they must be provided from some · line 1276
Quoted 5 lines
Documentation/memory-barriers.txt +5
-0+ event_indicated = 1; + wake_up(&event_wait_queue); + +or: +
smp_wmb(); /* or smp_mb() if trailing prior read to a variable. */
Documentation/memory-barriers.txt barriers are required in such a situation, they must be provided from some · line 1277
Quoted 1 line
Documentation/memory-barriers.txt +1
-0+ event_indicated = 1;
/* Or spin_unlock() here instead. */
Quoted 107 lines
Documentation/memory-barriers.txt +34
-1+ wake_up_process(event_daemon); + +A write memory barrier is implied by wake_up() and co. if and only if they wake +something up. The barrier occurs before the task state is cleared, and so sits +between the STORE to indicate the event and the STORE to set TASK_RUNNING: + + CPU 1 CPU 2 + =============================== =============================== + set_current_state(); STORE event_indicated + set_mb(); wake_up(); + STORE current->state <write barrier> + <general barrier> STORE current->state + LOAD event_indicated + +The available waker functions include: + + complete(); + wake_up(); + wake_up_all(); + wake_up_bit(); + wake_up_interruptible(); + wake_up_interruptible_all(); + wake_up_interruptible_nr(); + wake_up_interruptible_poll(); + wake_up_interruptible_sync(); + wake_up_interruptible_sync_poll(); + wake_up_locked(); + wake_up_locked_poll(); + wake_up_nr(); + wake_up_poll(); + wake_up_process(); + + MISCELLANEOUS FUNCTIONS -----------------------@@ -1366,7 +1457,7 @@ WHERE ARE MEMORY BARRIERS NEEDED? Under normal operation, memory operation reordering is generally not going to be a problem as a single-threaded linear piece of code will still appear to -work correctly, even if it's in an SMP kernel. There are, however, three +work correctly, even if it's in an SMP kernel. There are, however, four circumstances in which reordering definitely _could_ be a problem: (*) Interprocessor interaction.kernel/sched.c +23
-0@@ -2458,6 +2458,17 @@ out:return success; } +/** +* wake_up_process - Wake up a specific process +* @p: The process to be woken up. +* +* Attempt to wake up the nominated process and move it to the set of runnable +* processes. Returns 1 if the process was woken up, 0 if it was already +* running. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. +*/ int wake_up_process (struct task_struct *p) {return try_to_wake_up (p,TASK_ALL ,0 );@@ -5241,6 +5252,9 @@ void __wake_up_common(wait_queue_head_t *q, unsigned int mode,* @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void __wake_up (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)@@ -5279,6 +5293,9 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)* with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void __wake_up_sync_key (wait_queue_head_t *q,unsigned int mode,int nr_exclusive,void *key)@@ -5315,6 +5332,9 @@ EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */* awakened in the same order in which they were queued. * * See also complete_all(), wait_for_completion() and related routines. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void complete (struct completion *x) {@@ -5332,6 +5352,9 @@ EXPORT_SYMBOL(complete);* @x: holds the state of this particular completion * * This will wake up all threads waiting on this particular completion event. +* +* It may be assumed that this function implies a write memory barrier before +* changing the task state if and only if any tasks are woken up. */ void complete_all (struct completion *x) {
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 21 lines · Paul E. McKenney
One question, assuming that this documentation intends to guide the reader on where to put the locking and/or memory-barrier primitives...
Suppose we have the following sequence of events:
1. The waiter does "
set_current_state(TASK_UNINTERRUPTIBLE);".
This implies a full memory barrier.2. The awakener updates some shared state.
3. The awakener does "
event_indicated= 1;".4. The waiter does "if (
event_indicated)", and, finding that
the event has in fact been indicated, does "break".5. The waiter accesses the shared state set in #2 above.
6. Some time later, the awakener does "
wake_up(&event_wait_queue);"
This does not awaken anyone, so no memory barrier.
Quoted 6 lines
Because there is no memory barrier between #2 and #3, reordering by either the compiler or the CPU might cause the awakener to update the
event_indicatedflag in #3 -before- completing its update of shared state in #2. Less likely (but still possible) optimizations might cause the waiter to access the shared state in #5 before checking theevent_indicatedflag in #4.
Do you mean something like
awakener: DATA = value; DATA_IS_READY = true; wake_up(wq); waiter: set_current_state(UNINTERRUPTIBLE); if (DATA_IS_READY) do_something(DATA);
?
Imho, the code above is just buggy and should be ignored by documentation ;)
Or do I miss your point?
Oleg.
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 44 lines · Oleg Nesterov
Quoted 21 lines · Paul E. McKenney
One question, assuming that this documentation intends to guide the reader on where to put the locking and/or memory-barrier primitives...
Suppose we have the following sequence of events:
1. The waiter does "
set_current_state(TASK_UNINTERRUPTIBLE);".
This implies a full memory barrier.2. The awakener updates some shared state.
3. The awakener does "
event_indicated= 1;".4. The waiter does "if (
event_indicated)", and, finding that
the event has in fact been indicated, does "break".5. The waiter accesses the shared state set in #2 above.
6. Some time later, the awakener does "
wake_up(&event_wait_queue);"
This does not awaken anyone, so no memory barrier.Quoted 6 lines
Because there is no memory barrier between #2 and #3, reordering by either the compiler or the CPU might cause the awakener to update the
event_indicatedflag in #3 -before- completing its update of shared state in #2. Less likely (but still possible) optimizations might cause the waiter to access the shared state in #5 before checking theevent_indicatedflag in #4.Do you mean something like
awakener: DATA = value; DATA_IS_READY = true; wake_up(wq); waiter: set_current_state(UNINTERRUPTIBLE); if (DATA_IS_READY) do_something(DATA);
Quoted 5 lines
?
Imho, the code above is just buggy and should be ignored by documentation ;)
Or do I miss your point?
I was hoping that this sort of code might be actively discouraged by the documentation. ;-)
Thanx, Paul
David Howells
maintainerRe: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
In reply to Paul E. McKenneyQuoted 4 lines · Paul E. McKenney
Because there is no memory barrier between #2 and #3, reordering by either the compiler or the CPU might cause the awakener to update the
event_indicatedflag in #3 -before- completing its update of shared state in #2.
If the ordering of #2 and #3 is important with respect to each other, then the awakener must manually interpolate a barrier of some sort between the two _before_ calling wake_up() (or it should wrap them in a lock).
As I've tried to make clear in my documentation:
Sleeping and waking on an event flagged in global data can be viewed as an interaction between two pieces of data: ===> the task state of the task waiting for the event and the global data used to indicate the event <===.
the barrier in wake_up() is only concerned with the ordering of #3 vs #6. That is all it _can_ impose an order upon, since #2 and #3 both happen before wake_up() is called, and #3 is what causes the sleeper to break out of the sleep loop.
Quoted 4 lines
So, for this to work correctly, don't we need at least an
smp_wmb()between #2 and #3 and at least ansmp_rmb()between #4 and #5? And if #2 does reads (but not writes) at least one variable in the shared state that #5 writes to, don't both barriers need to besmp_mb()?
Yes, but that's beyond the scope of this section. set_current_state() imposes the partial ordering { #1, #4 } and wake_up() the partial ordering { #3, #6 } because those are the controlling features of the loop.
Managing the data beyond that is up to the caller of set_current_state() and the caller of wake_up().
David
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 28 lines · David Howells
Quoted 4 lines · Paul E. McKenney
Because there is no memory barrier between #2 and #3, reordering by either the compiler or the CPU might cause the awakener to update the
event_indicatedflag in #3 -before- completing its update of shared state in #2.If the ordering of #2 and #3 is important with respect to each other, then the awakener must manually interpolate a barrier of some sort between the two _before_ calling
wake_up()(or it should wrap them in a lock).As I've tried to make clear in my documentation:
Sleeping and waking on an event flagged in global data can be viewed as an interaction between two pieces of data: ===> the task state of the task waiting for the event and the global data used to indicate the event <===.the barrier in
wake_up()is only concerned with the ordering of #3 vs #6. That is all it _can_ impose an order upon, since #2 and #3 both happen beforewake_up()is called, and #3 is what causes the sleeper to break out of the sleep loop.Quoted 4 lines
So, for this to work correctly, don't we need at least an
smp_wmb()between #2 and #3 and at least ansmp_rmb()between #4 and #5? And if #2 does reads (but not writes) at least one variable in the shared state that #5 writes to, don't both barriers need to besmp_mb()?
Quoted 6 lines
Yes, but that's beyond the scope of this section.
set_current_state()imposes the partial ordering { #1, #4 } andwake_up()the partial ordering { #3, #6 } because those are the controlling features of the loop.Managing the data beyond that is up to the caller of
set_current_state()and the caller ofwake_up().
Fair enough!
But I would strongly suggest at least a note calling this out, preferably a "don't do this" example.
Thanx, Paul
David Howells
maintainerRe: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 2 lines · Paul E. McKenney
But I would strongly suggest at least a note calling this out, preferably a "don't do this" example.
How about I add this to the bottom of the new section:
[!] Note that the memory barriers implied by the sleeper and the waker do _not_ order multiple stores before the wake-up with respect to loads of those stored values after the sleeper has called set_current_state(). For instance, if the sleeper does:
set_current_state(TASK_INTERRUPTIBLE); if (event_indicated) break; __set_current_state(TASK_RUNNING); do_something(my_data);
and the waker does:
my_data = value; event_indicated = 1; wake_up(&event_wait_queue);
there's no guarantee that the change to event_indicated will be perceived by the sleeper as coming after the change to my_data. In such a circumstance, the code on both sides must interpolate its own memory barriers between the separate data accesses. Thus the above sleeper ought to do:
set_current_state(TASK_INTERRUPTIBLE);
if (event_indicated) {
smp_rmb();
do_something(my_data);
}and the waker should do:
my_data = value; smp_wmb(); event_indicated = 1; wake_up(&event_wait_queue);
David
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 35 lines · David Howells
Quoted 2 lines · Paul E. McKenney
But I would strongly suggest at least a note calling this out, preferably a "don't do this" example.
How about I add this to the bottom of the new section:
[!] Note that the memory barriers implied by the sleeper and the waker do _not_ order multiple stores before the wake-up with respect to loads of those stored values after the sleeper has called
set_current_state(). For instance, if the sleeper does:set_current_state(TASK_INTERRUPTIBLE); if (event_indicated) break; __set_current_state(TASK_RUNNING); do_something(my_data);and the waker does:
my_data = value; event_indicated = 1; wake_up(&event_wait_queue);there's no guarantee that the change to
event_indicatedwill be perceived by the sleeper as coming after the change tomy_data. In such a circumstance, the code on both sides must interpolate its own memory barriers between the separate data accesses. Thus the above sleeper ought to do:set_current_state(TASK_INTERRUPTIBLE); if (event_indicated) { smp_rmb(); do_something(my_data); }
Quoted 6 lines
and the waker should do:
my_data = value; smp_wmb(); event_indicated = 1; wake_up(&event_wait_queue);
Looks good to me!
Thanx, Paul
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
In reply to David HowellsQuoted 5 lines · David Howells
(2)
wake_up()interpolates a write memory barrier before clearing the task state - _if_ it wakes anything up - then there's no problem in the waker either.
[...snip...]
Documentation/memory-barriers.txt barriers are required in such a situation, they must be provided from some · line 1282
Quoted 4 lines
Documentation/memory-barriers.txt +3
-0+A write memory barrier is implied by wake_up() and co. if and only if they wake +something up. The barrier occurs before the task state is cleared, and so sits +between the STORE to indicate the event and the STORE to set TASK_RUNNING:
Very minor nit. Perhaps it makes sense to mention that we also need the barrier before _reading_ the task->state as well. Or not, I am not sure ;) Just in case...
event_indicated = 1; wake_up_process(event_daemon);
Suppose that "event_indicated = 1" leaks into try_to_wake_up() after we read p->state. In this case we have
try_to_wake_up: if (!(p->state & state)) goto out; // do nothing // WINDOW event_indicated = 1; // leaked
In that case the whole
set_current_state(TASK_UNINTERRUPTIBLE); if (event_indicated) break; schedule();
can happen in the WINDOW above.
But again, this is the real nitpick, and probably just the "implementation details" which should not be documented.
Oleg.
David Howells
maintainerRe: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 2 lines · Oleg Nesterov
Suppose that "
event_indicated= 1" leaks intotry_to_wake_up()after we readp->state.
In that case, it's entirely possible that the smp_wmb() in try_to_wake_up() should actually be an smp_mb(), but that on whichever arch patch:
commit 04e2f1741d235ba599037734878d72e57cb302b5 Author: Linus Torvalds <[email protected]> Date: Sat Feb 23 18:05:03 2008 -0800 Subject: Add memory barrier semantics to wake_up() & co
was tested on, it made no difference.
David
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 9 lines · David Howells
Quoted 2 lines · Oleg Nesterov
Suppose that "
event_indicated= 1" leaks intotry_to_wake_up()after we readp->state.In that case, it's entirely possible that the
smp_wmb()intry_to_wake_up()should actually be ansmp_mb(), but that on whichever arch patch:
Quoted 6 lines
commit 04e2f1741d235ba599037734878d72e57cb302b5 Author: Linus Torvalds <[email protected]> Date: Sat Feb 23 18:05:03 2008 -0800 Subject: Add memory barrier semantics to wake_up() & cowas tested on, it made no difference.
I think that, from the correctness pov, this patch does not depend on arch.
Quoted 1 line
From the changelog:
However, adding a smp_wmb() to before the spinlock should now order the writing of CONDITION wrt the lock itself, which in turn is ordered wrt the accesses within the spinlock (which includes the reading of the old state).
IOW, spin_lock() itself is STORE, and has the acquire semantics. This means that "wmb() + spin_lock()" must correctly serialize "STOREs bfore" and "STOREs/LOADs after". At least this is my understanding.
But does it really "equal" to mb() on all arches ? I don't know, but I guess it is not possible to derive from documentation. So, at least in theory, try_to_wake_up() doesn't provide rmb() afaics, and
LOAD_1; try_to_wake_up(); LOAD_2;
this can be re-ordered.
But I know nothing about how mb/lock _actually_ play with hardware, even on x86.
Oleg.
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
In reply to David HowellsQuoted 4 lines · David Howells
I was wondering if
wake_up()and friends should in fact implysmp_wmb(), but I guess that they're often used in conjunction with spinlocks - and in such a situation a barrier is unnecessary overhead.
I think we _have_ to imply a smp_wmb() in the wakup semantics, because otherwise sleepers can't do anything sane (no amount of barriers on the sleeping side will help). IOW, there basically has to be an implied write barrier between the thing that causes an event to become true, and the thing that turns 'task->state' back to RUNNING.
This is similar to the issue of doing cross-CPU IPI's: sending an IPI _must_ imply a memory barrier with the IPI mechanism, because otherwise the receiver could never do anything sane.
Linus
David Howells
maintainerRe: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 5 lines · Linus Torvalds
I think we _have_ to imply a
smp_wmb()in the wakup semantics, because otherwise sleepers can't do anything sane (no amount of barriers on the sleeping side will help). IOW, there basically has to be an implied write barrier between the thing that causes an event to become true, and the thing that turns 'task->state' back to RUNNING.
Well, Ingo's point is it could be left up to the caller of wake_up() to supply the barrier:
*my_variable = 1234; smp_wmb(); wake_up(&my_queue);
or:
spin_lock(&my_lock); *my_variable = 1234; wake_up(&my_queue); spin_unlock(&my_lock);
on the condition that the sleeper also gets the lock.
Also, he points out that wake_up() and co. may not insert useful memory barrier at all, for three reasons:
(1) If there's no-one to wake up, then certain wake functions will return immediately.
(2) If there's no-one to wake up, then other wake functions will only impose LOCK and UNLOCK barriers.
(3) If someone supplies a special awakener instead of default_wake_function(), then they can bypass try_to_wake_up() and whatever barrier that implies.
Though as far as I can see, if you want to wake someone up, you *have* to go through try_to_wake_up().
What I'd like to say is that wake_up() and friends _will_ interpose at least a write barrier _if_ they wake anything up (which is more or less what you said above). If they don't wake anything up, then there's no need for a memory barrier between the assignment to my_variable and the non-existent alterations to the state of the task not being awoken.
David
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 7 lines · David Howells
Well, Ingo's point is it could be left up to the caller of
wake_up()to supply the barrier:*my_variable = 1234; smp_wmb(); wake_up(&my_queue);
That's bogus.
EVERY SINGLE wake_up() would need it.
There is _always_ a reason for the wakeup. And yes, you can re-order things, but we normally don't. Just make the rule be that there's an implied smp_wmb() instead.
It's not like it's going to cost anything on any sane architecture anyway. So asking people to add "smp_wmb()" calls before their wakups just makes the source code unreadable and fragile, for no actual advantage.
Linus
Re: [PATCH] It may not be assumed that wake_up(), finish_wait() and co. imply a memory barrier
Quoted 4 lines · Linus Torvalds
Quoted 3 lines · David Howells
Well, Ingo's point is it could be left up to the caller of
wake_up()to supply the barrier:
Well, i mainly reacted to your documentation patch which was incorrect as it said wake-up implies a _FULL_ memory barrier.
I also suggested that lockless code should have its barriers clearly documented and they should not really rely on kernel facilities acting as memory barriers.
Then i also suggested that maybe in the future we could remove the smp_wmb() from try_to_wake_up(). That was just an afterthought, and a rather stupid one at that, as Linus quickly noted :-)
Ingo
Re: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
In reply to Ingo MolnarQuoted 8 lines · Ingo Molnar
* David Howells <[email protected]> wrote:
The dangerous pattern is lockless code doing wakeups. But lockless code always has to use proper barriers or atomics anyway, and has to be aware of the fact that kernel primitives they call are not necessarily full memory barriers.
Quoted 4 lines
In fact i'd encourage to _not_ document
try_to_lock()as a write barrier either - but rather have explicit barriers where they are needed. Then we could remove that barrier fromtry_to_wake_up()too ;-)
Well. I think in that case almost every try_to_wake_up/wake_up_process needs mb().
For example:
do_nanosleep:
for (;;) {
set_current_state(TASK_INTERRUPTIBLE);
if (likely(t->task))
schedule();
break;
}
hrtimer_wakeup:
task = t->task
t->task = NULL;
wake_up_process(task);If try_to_wake_up() has no the barrier semantics, we can miss the event. "t->task = NULL" and the reading of task->state must not be reordered.
Oleg.
David Howells
maintainerRe: [PATCH] Document that wake_up(), complete() and co. imply a full memory barrier
Quoted 2 lines · Oleg Nesterov
Well. I think in that case almost every try_to_wake_up/wake_up_process needs
mb().
Not exactly. They need smp_wmb() in the wake_up() path - unless they use locks, which a lot of cases do.
David
David Howells
maintainerQuoted 3 lines · Andrew Morton
I wonder if
slow_work_cull_timeout()should have some sort of barrier, so the write is suitably visible to the woken thread. Bearing in mind that the thread might _already_ have been woken by someone else?
Perhaps the attached patch?
David
---
From: David Howells <[email protected]>
Subject: [PATCH] slow_work_cull_timeout() should have a memory barrier
slow_work_cull_timeout() should have a write memory barrier so that the setting of the cull flag is seen before the wakeup takes place. This is required because wake_up() does not guarantee any memory barriership at all.
Concomitant to this, slow_work_thread() should have a read memory barrier between its return from schedule() and its testing of slow_work_cull() as finish_wait() isn't a guaranteed barrier either.
---
kernel/slow-work.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-)
kernel/slow-work.c +2 -0
@@ -382,6 +382,7 @@ static int slow_work_thread(void *_data)finish_wait (&slow_work_thread_wq, &wait);try_to_freeze (); +smp_rmb (); vsmax = vslow_work_proportion; vsmax *=atomic_read (&slow_work_thread_count);
@@ -416,6 +417,7 @@ static int slow_work_thread(void *_data)static void slow_work_cull_timeout (unsigned long data) { slow_work_cull = true; +smp_wmb ();wake_up (&slow_work_thread_wq); }
(add Ingo)
Quoted 42 lines · David Howells
Quoted 3 lines · Andrew Morton
I wonder if
slow_work_cull_timeout()should have some sort of barrier, so the write is suitably visible to the woken thread. Bearing in mind that the thread might _already_ have been woken by someone else?Perhaps the attached patch?
David
---
From: David Howells <[email protected]>
Subject: [PATCH]slow_work_cull_timeout()should have a memory barrier
slow_work_cull_timeout()should have a write memory barrier so that the setting of the cull flag is seen before the wakeup takes place. This is required becausewake_up()does not guarantee any memory barriership at all.Concomitant to this,
slow_work_thread()should have a read memory barrier between its return fromschedule()and its testing ofslow_work_cull()asfinish_wait()isn't a guaranteed barrier either.Signed-off-by David Howells <[email protected]>---
kernel/slow-work.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-)kernel/slow-work.c +1
-0@@ -382,6 +382,7 @@ static int slow_work_thread(void *_data)finish_wait (&slow_work_thread_wq, &wait);try_to_freeze (); +smp_rmb (); vsmax = vslow_work_proportion; vsmax *=atomic_read (&slow_work_thread_count);
kernel/slow-work.c static int slow_work_thread(void *_data) · line 422
Quoted 6 lines
kernel/slow-work.c +1
-0@@ -416,6 +417,7 @@ static int slow_work_thread(void *_data)static void slow_work_cull_timeout (unsigned long data) { slow_work_cull = true; +smp_wmb ();wake_up (&slow_work_thread_wq); }
Confused. If we need this barrier, a lot of similar code is broken.
slow_work_cull_timeout: slow_work_cull = true; wake_up(&slow_work_thread_wq); slow_work_thread: prepare_to_wait(&slow_work_thread_wq); if (!slow_work_cull) schedule(); finish_wait(&slow_work_thread_wq); if (slow_work_cull) .....
Both wake_up() and prepare_to_wait() take the same wait_queue_head_t->lock, and prepare_to_wait() does set_current_state() under this lock.
How can we miss the event? If wake_up() happens before prepare_to_wait(), slow_work_thread() must see slow_work_cull = T, otherwise the subsequent wake_up() must see the result of list_add() + set_current_state() and wake up the sleeping thread.
Could you please clarify?
Oleg.
David Howells
maintainerQuoted 4 lines · Oleg Nesterov
slow_work_thread()sleeps onslow_work_thread_wqwithoutWQ_FLAG_EXCLUSIVE, this means that slow_work_enqueue()->__wake_up(nr_exclusive => 1) wakes up all kslowd threads. Afaics this is not what we want, changeslow_work_thread()to useprepare_to_wait_exclusive().
Hmmm... I think you may be right. I think I was assuming that wake_up() would only wake up the first item on the queue, but that's not strictly what it does...
David