Miscellaneous fixes for v4.15
Subsystems (4)
cover Miscellaneous fixes for v4.15
Hello!
This series contains the following miscellaneous fixes:
1. Provide GP ordering in face of migrations and delays.
2. Fix up pending cbs check in rcu_prepare_for_idle(), courtesy
of Neeraj Upadhyay.
3. Create call_rcu_tasks() kthread at boot time.
4. Map irq_work_on_queue() to irq_work_on() in !SMP.
5. Add parameters to SRCU docbook comments.
6. Make resched_cpu() unconditional.
7. Pretend ->boost_mtx acquired legitimately for lockdep's benefit.
8. Add extended-quiescent-state testing advice.
9. Include rcupdate.h into kernel/rcu/segcblist, courtesy of
Sebastian Andrzej Siewior.
Thanx, Paul
------------------------------------------------------------------------
include/linux/irq_work.h | 3 --- include/linux/srcu.h | 1 + kernel/irq_work.c | 9 ++++++--- kernel/rcu/rcu_segcblist.c | 1 + kernel/rcu/srcutree.c | 2 +- kernel/rcu/tree.c | 30 ++++++++++++++++++++++++++++++ kernel/rcu/tree_plugin.h | 7 +++++-- kernel/rcu/update.c | 34 +++++++++++++++------------------- kernel/sched/core.c | 3 +-- 9 files changed, 60 insertions(+), 30 deletions(-)
PATCH 1/9 rcu: Provide GP ordering in face of migrations and delays
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes rcu_read_lock().
o Task B on CPU 1 executes synchronize_rcu(), which must
wait on Task A:
o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.
o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.
o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invoke RCU_SOFTIRQ, both thus learning of the new grace period.
o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.
o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.
o Task A executes rcu_read_unlock(), exiting its RCU read-side
critical section.
o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.
o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B via complete().
o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from the synchronize_rcu() without any ordering against the end of Task A's RCU read-side critical section.
It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
However, if CPU hotplug ever gets rid of stop_machine(), there will be more straightforward ways for this sort of thing to happen, so this commit adds a memory barrier in order to enforce the needed ordering.
--- kernel/rcu/update.c | 10 ++++++++++ 1 file changed, 10 insertions(+)
kernel/rcu/update.c +10 -0
@@ -413,6 +413,16 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } + +/* +* If we migrated after we registered a callback, but before the +* corresponding wait_for_completion(), we might now be running +* on a CPU that has not yet noticed that the corresponding grace +* period has ended. That CPU might not yet be fully ordered +* against the completion of the grace period, so the full memory +* barrier below enforces that ordering via the completion's state. +*/ +smp_mb ();/* ^^^ */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);
Signature · 1 line
2.5.2
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 39 lines · Paul E. McKenney
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().
Quoted 8 lines
o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
I'm not sure I follow, at the very least the wait_for_completion() does an ACQUIRE such that it observes the state prior to the RELEASE as done by complete(), no?
And is not CPU0's QS reporting ordered against that complete()?
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 46 lines · Peter Zijlstra
Quoted 45 lines · Paul E. McKenney
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.
Quoted 6 lines
Quoted 2 lines
It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
I'm not sure I follow, at the very least the
wait_for_completion()does an ACQUIRE such that it observes the state prior to the RELEASE as done bycomplete(), no?
Your point being that both wait_for_completion() and complete() acquire and release the same lock? (Yes, I suspect that I was confusing this with wait_event() and wake_up(), just so you know.)
Quoted 1 line
And is not CPU0's QS reporting ordered against that
complete()?
Mumble mumble mumble powerpc mumble mumble mumble...
OK, I will make this new memory barrier only execute for powerpc.
Or am I missing something else here?
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 50 lines · Paul E. McKenney
Quoted 49 lines · Peter Zijlstra
Quoted 47 lines · Paul E. McKenney
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
Quoted 7 lines
Quoted 3 lines
I'm not sure I follow, at the very least the
wait_for_completion()does an ACQUIRE such that it observes the state prior to the RELEASE as done bycomplete(), no?Your point being that both
wait_for_completion()andcomplete()acquire and release the same lock? (Yes, I suspect that I was confusing this withwait_event()andwake_up(), just so you know.)
Well, fundamentally complete()/wait_for_completion() is a message-pass and they include a RELEASE/ACQUIRE pair for causal reasons.
Per the implementation they use a spinlock, but any implementation needs to provide at least that RELEASE/ACQUIRE pair.
Quoted 7 lines
Quoted 1 line
And is not CPU0's QS reporting ordered against that
complete()?Mumble mumble mumble powerpc mumble mumble mumble...
OK, I will make this new memory barrier only execute for powerpc.
Or am I missing something else here?
So I'm not entirely clear on the required semantics here; why do we need a full mb? I'm thinking CPU0's QS propagating through the tree and arriving at the root node is a multi-copy-atomic / transitive thing and all CPUs will agree the system QS has ended, right?
Whichever CPU establishes the system QS does complete() and the wait_for_completion() then has the weak-transitive causal relation to that, ensuring that -- in the above example -- CPU3 must be _after_ CPU0's rcu_read_unlock().
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 78 lines · Peter Zijlstra
Quoted 50 lines · Paul E. McKenney
Quoted 49 lines · Peter Zijlstra
Quoted 47 lines · Paul E. McKenney
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
Quoted 7 lines
Quoted 3 lines
I'm not sure I follow, at the very least the
wait_for_completion()does an ACQUIRE such that it observes the state prior to the RELEASE as done bycomplete(), no?Your point being that both
wait_for_completion()andcomplete()acquire and release the same lock? (Yes, I suspect that I was confusing this withwait_event()andwake_up(), just so you know.)Well, fundamentally complete()/wait_for_completion() is a message-pass and they include a RELEASE/ACQUIRE pair for causal reasons.
Per the implementation they use a spinlock, but any implementation needs to provide at least that RELEASE/ACQUIRE pair.
Quoted 7 lines
Quoted 1 line
And is not CPU0's QS reporting ordered against that
complete()?Mumble mumble mumble powerpc mumble mumble mumble...
OK, I will make this new memory barrier only execute for powerpc.
Or am I missing something else here?
So I'm not entirely clear on the required semantics here; why do we need a full mb? I'm thinking CPU0's QS propagating through the tree and arriving at the root node is a multi-copy-atomic / transitive thing and all CPUs will agree the system QS has ended, right?
Quoted 4 lines
Whichever CPU establishes the system QS does
complete()and thewait_for_completion()then has the weak-transitive causal relation to that, ensuring that -- in the above example -- CPU3 must be _after_ CPU0'srcu_read_unlock().
Yes, the ordering does need to be visible to uninvolved CPUs, so release-acquire is not necessarily strong enough.
My current thought is like this:
if (IS_ENABLED(CONFIG_ARCH_WEAK_RELEASE_ACQUIRE)) smp_mb();
Thoughts?
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 3 lines · Paul E. McKenney
Yes, the ordering does need to be visible to uninvolved CPUs, so release-acquire is not necessarily strong enough.
Why? Because I'm not at all seeing why it needs more. Your Changelog doesn't provide enough hints.
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney
Yes, the ordering does need to be visible to uninvolved CPUs, so release-acquire is not necessarily strong enough.
Why? Because I'm not at all seeing why it needs more. Your Changelog doesn't provide enough hints.
Hmmm... Here is what I was worried about:
C C-PaulEMcKenney-W+RWC4+2017-10-05
{
}
P0(int *a, int *x)
{
WRITE_ONCE(*a, 1);
smp_mb(); /* Lock acquisition for rcu_node ->lock. */
WRITE_ONCE(*x, 1);
}
P1(int *x, int *y, spinlock_t *l)
{
r3 = READ_ONCE(*x);
smp_mb(); /* Lock acquisition for rcu_node ->lock. */
spin_lock(l); /* Locking in complete(). */
WRITE_ONCE(*y, 1);
spin_unlock(l);
}
P2(int *y, int *b, spinlock_t *l)
{
spin_lock(l); /* Locking in wait_for_completion. */
r4 = READ_ONCE(*y);
spin_unlock(l);
r1 = READ_ONCE(*b);
}
P3(int *b, int *a)
{
WRITE_ONCE(*b, 1);
smp_mb();
r2 = READ_ONCE(*a);
}
exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)My concern was that P2()'s read from b could be pulled into the lock's critical section and reordered with the read from y. But even if you physically rearrange the code, the cycle is forbidden. Removing P2()'s lock acquisition and release does allow the cycle. I get the same result when replacing spin_lock() with xchg_acquire() and spin_unlock() with smp_store_release(). I can drop P1()'s smp_mb() (but otherwise like the original above) and the cycle is forbidden. Removing P1()'s lock acquisition and release, but leaving the smp_mb(), does allow the cycle.
So it looks like I can drop this patch entirely. Though somewhat nervously, despite the evidence that I have ample redundancy in ordering. ;-)
So, thank you for persisting on this one!
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 31 lines · Paul E. McKenney
Hmmm... Here is what I was worried about:
C C-PaulEMcKenney-W+RWC4+2017-10-05 { } P0(int *a, int *x) { WRITE_ONCE(*a, 1); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ WRITE_ONCE(*x, 1); } P1(int *x, int *y, spinlock_t *l) { r3 = READ_ONCE(*x); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ spin_lock(l); /* Locking in complete(). */ WRITE_ONCE(*y, 1); spin_unlock(l); } P2(int *y, int *b, spinlock_t *l) { spin_lock(l); /* Locking in wait_for_completion. */ r4 = READ_ONCE(*y); spin_unlock(l); r1 = READ_ONCE(*b); }
Quoted 8 lines
P3(int *b, int *a)
{
WRITE_ONCE(*b, 1);
smp_mb();
r2 = READ_ONCE(*a);
}
exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)/me goes and install this herd thing again.. I'm sure I had it running _somewhere_.. A well.
C C-PaulEMcKenney-W+RWC4+2017-10-05
{
}
P0(int *a, int *x)
{
WRITE_ONCE(*a, 1);
smp_mb(); /* Lock acquisition for rcu_node ->lock. */
WRITE_ONCE(*x, 1);
}
P1(int *x, int *y)
{
r3 = READ_ONCE(*x);
smp_mb(); /* Lock acquisition for rcu_node ->lock. */
smp_store_release(y, 1);
}
P2(int *y, int *b)
{
r4 = smp_load_acquire(y);
r1 = READ_ONCE(*b);
}
P3(int *b, int *a)
{
WRITE_ONCE(*b, 1);
smp_mb();
r2 = READ_ONCE(*a);
}
exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)Is what I was thinking of, I think that is the minimal ordering complete()/wait_for_completion() need to provide.
(also, that r# numbering confuses the hell out of me, its not related to P nor to the variables)
Test C-PaulEMcKenney-W+RWC4+2017-10-05 Allowed States 15
1:r3=0; 2:r1=0; 2:r4=0; 3:r2=0;
1:r3=0; 2:r1=0; 2:r4=0; 3:r2=1;
1:r3=0; 2:r1=0; 2:r4=1; 3:r2=0;
1:r3=0; 2:r1=0; 2:r4=1; 3:r2=1;
1:r3=0; 2:r1=1; 2:r4=0; 3:r2=0;
1:r3=0; 2:r1=1; 2:r4=0; 3:r2=1;
1:r3=0; 2:r1=1; 2:r4=1; 3:r2=0;
1:r3=0; 2:r1=1; 2:r4=1; 3:r2=1;
1:r3=1; 2:r1=0; 2:r4=0; 3:r2=0;
1:r3=1; 2:r1=0; 2:r4=0; 3:r2=1;
1:r3=1; 2:r1=0; 2:r4=1; 3:r2=1;
1:r3=1; 2:r1=1; 2:r4=0; 3:r2=0;
1:r3=1; 2:r1=1; 2:r4=0; 3:r2=1;
1:r3=1; 2:r1=1; 2:r4=1; 3:r2=0;
1:r3=1; 2:r1=1; 2:r4=1; 3:r2=1;
No
Witnesses
Positive: 0 Negative: 15
Condition exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0) Observation C-PaulEMcKenney-W+RWC4+2017-10-05 Never 0 15 Time C-PaulEMcKenney-W+RWC4+2017-10-05 0.04 Hash=f7f8ad6eab33e90718a394bcb021557d
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 79 lines · Peter Zijlstra
Quoted 31 lines · Paul E. McKenney
Hmmm... Here is what I was worried about:
C C-PaulEMcKenney-W+RWC4+2017-10-05 { } P0(int *a, int *x) { WRITE_ONCE(*a, 1); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ WRITE_ONCE(*x, 1); } P1(int *x, int *y, spinlock_t *l) { r3 = READ_ONCE(*x); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ spin_lock(l); /* Locking in complete(). */ WRITE_ONCE(*y, 1); spin_unlock(l); } P2(int *y, int *b, spinlock_t *l) { spin_lock(l); /* Locking in wait_for_completion. */ r4 = READ_ONCE(*y); spin_unlock(l); r1 = READ_ONCE(*b); }Quoted 8 lines
P3(int *b, int *a) { WRITE_ONCE(*b, 1); smp_mb(); r2 = READ_ONCE(*a); } exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)/me goes and install this herd thing again.. I'm sure I had it running _somewhere_.. A well.
C C-PaulEMcKenney-W+RWC4+2017-10-05 { } P0(int *a, int *x) { WRITE_ONCE(*a, 1); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ WRITE_ONCE(*x, 1); } P1(int *x, int *y) { r3 = READ_ONCE(*x); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ smp_store_release(y, 1); } P2(int *y, int *b) { r4 = smp_load_acquire(y); r1 = READ_ONCE(*b); } P3(int *b, int *a) { WRITE_ONCE(*b, 1); smp_mb(); r2 = READ_ONCE(*a); } exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)
Quoted 2 lines
Is what I was thinking of, I think that is the minimal ordering complete()/wait_for_completion() need to provide.
OK, I will bite... What do the smp_store_release() and the smp_load_acquire() correspond to? I see just plain locking in wait_for_completion() and complete().
Quoted 2 lines
(also, that r# numbering confuses the hell out of me, its not related to P nor to the variables)
Yeah, it is random, sorry!!!
Quoted 16 lines
Test C-PaulEMcKenney-W+RWC4+2017-10-05 Allowed
States 15
1:r3=0; 2:r1=0; 2:r4=0; 3:r2=0;
1:r3=0; 2:r1=0; 2:r4=0; 3:r2=1;
1:r3=0; 2:r1=0; 2:r4=1; 3:r2=0;
1:r3=0; 2:r1=0; 2:r4=1; 3:r2=1;
1:r3=0; 2:r1=1; 2:r4=0; 3:r2=0;
1:r3=0; 2:r1=1; 2:r4=0; 3:r2=1;
1:r3=0; 2:r1=1; 2:r4=1; 3:r2=0;
1:r3=0; 2:r1=1; 2:r4=1; 3:r2=1;
1:r3=1; 2:r1=0; 2:r4=0; 3:r2=0;
1:r3=1; 2:r1=0; 2:r4=0; 3:r2=1;
1:r3=1; 2:r1=0; 2:r4=1; 3:r2=1;
1:r3=1; 2:r1=1; 2:r4=0; 3:r2=0;
1:r3=1; 2:r1=1; 2:r4=0; 3:r2=1;
1:r3=1; 2:r1=1; 2:r4=1; 3:r2=0;
Quoted 8 lines
1:r3=1; 2:r1=1; 2:r4=1; 3:r2=1;
No
Witnesses
Positive: 0 Negative: 15
Condition exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0) Observation C-PaulEMcKenney-W+RWC4+2017-10-05 Never 0 15 Time C-PaulEMcKenney-W+RWC4+2017-10-05 0.04 Hash=f7f8ad6eab33e90718a394bcb021557d
But yes, looking closer, this corresponds to the rule of thumb about non-rf relations and full memory barriers. We have two non-rf relations (P2->P3 and P3->P0), so we need two full barriers, one each between the non-rf relations.
So I dropped that patch yesterday. The main thing I was missing was that there is no ordering-free fastpath in wait_for_completion() and complete(): Each unconditionally acquires the lock. So the smp_mb() that I was trying to add doesn't need to be there.
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 38 lines · Paul E. McKenney
Quoted 38 lines
/me goes and install this herd thing again.. I'm sure I had it running _somewhere_.. A well.
C C-PaulEMcKenney-W+RWC4+2017-10-05 { } P0(int *a, int *x) { WRITE_ONCE(*a, 1); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ WRITE_ONCE(*x, 1); } P1(int *x, int *y) { r3 = READ_ONCE(*x); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ smp_store_release(y, 1); } P2(int *y, int *b) { r4 = smp_load_acquire(y); r1 = READ_ONCE(*b); } P3(int *b, int *a) { WRITE_ONCE(*b, 1); smp_mb(); r2 = READ_ONCE(*a); } exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)
Quoted 6 lines
Quoted 2 lines
Is what I was thinking of, I think that is the minimal ordering complete()/wait_for_completion() need to provide.
OK, I will bite... What do the
smp_store_release()and thesmp_load_acquire()correspond to? I see just plain locking inwait_for_completion()andcomplete().
They reflect the concept of complete() / wait_for_completion(). Fundamentally all it needs to do is pass the message of 'completion'.
That is, if we were to go optimize our completion implementation, it would be impossible to be weaker than this and still correct.
Quoted 4 lines
So I dropped that patch yesterday. The main thing I was missing was that there is no ordering-free fastpath in
wait_for_completion()andcomplete(): Each unconditionally acquires the lock. So thesmp_mb()that I was trying to add doesn't need to be there.
Going by the above, it never needs to be there, even if there was a lock-free fast-path.
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 46 lines · Peter Zijlstra
Quoted 38 lines · Paul E. McKenney
Quoted 38 lines
/me goes and install this herd thing again.. I'm sure I had it running _somewhere_.. A well.
C C-PaulEMcKenney-W+RWC4+2017-10-05 { } P0(int *a, int *x) { WRITE_ONCE(*a, 1); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ WRITE_ONCE(*x, 1); } P1(int *x, int *y) { r3 = READ_ONCE(*x); smp_mb(); /* Lock acquisition for rcu_node ->lock. */ smp_store_release(y, 1); } P2(int *y, int *b) { r4 = smp_load_acquire(y); r1 = READ_ONCE(*b); } P3(int *b, int *a) { WRITE_ONCE(*b, 1); smp_mb(); r2 = READ_ONCE(*a); } exists (1:r3=1 /\ 2:r4=1 /\ 2:r1=0 /\ 3:r2=0)Quoted 6 lines
Quoted 2 lines
Is what I was thinking of, I think that is the minimal ordering complete()/wait_for_completion() need to provide.
OK, I will bite... What do the
smp_store_release()and thesmp_load_acquire()correspond to? I see just plain locking inwait_for_completion()andcomplete().
Quoted 5 lines
They reflect the concept of
complete()/wait_for_completion(). Fundamentally all it needs to do is pass the message of 'completion'.That is, if we were to go optimize our completion implementation, it would be impossible to be weaker than this and still correct.
OK, though the model does not provide spinlocks, and there can be differences in behavior between spinlocks and release-acquire. But yes, in this case, it works.
Quoted 7 lines
Quoted 4 lines
So I dropped that patch yesterday. The main thing I was missing was that there is no ordering-free fastpath in
wait_for_completion()andcomplete(): Each unconditionally acquires the lock. So thesmp_mb()that I was trying to add doesn't need to be there.Going by the above, it never needs to be there, even if there was a lock-free fast-path.
Given that wait_for_completion()/complete() both acquire the same lock, yes, and agreed, if it were lockless but provided the release and acquire ordering, then yes. But if it was instead structured like wait_event()/wake_up(), there would be ordering only if the caller supplied it.
All that aside, paring the ordering down to the bare minimum is not always the right approach. Nevertheless, in this particular case, there is plenty of ordering, so yet again, I have dropped this commit. Like yesterday. ;-)
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 7 lines · Paul E. McKenney
Quoted 7 lines
Quoted 3 lines
OK, I will bite... What do the
smp_store_release()and thesmp_load_acquire()correspond to? I see just plain locking inwait_for_completion()andcomplete().They reflect the concept of
complete()/wait_for_completion(). Fundamentally all it needs to do is pass the message of 'completion'.
Quoted 6 lines
Quoted 2 lines
That is, if we were to go optimize our completion implementation, it would be impossible to be weaker than this and still correct.
OK, though the model does not provide spinlocks, and there can be differences in behavior between spinlocks and release-acquire. But yes, in this case, it works.
Sure; but the fundamental property here is that if we observe the complete() we must also observe everything that went before. The exact means of implementing that is irrelevant.
Quoted 11 lines
Quoted 7 lines
Quoted 4 lines
So I dropped that patch yesterday. The main thing I was missing was that there is no ordering-free fastpath in
wait_for_completion()andcomplete(): Each unconditionally acquires the lock. So thesmp_mb()that I was trying to add doesn't need to be there.Going by the above, it never needs to be there, even if there was a lock-free fast-path.
Given that wait_for_completion()/complete() both acquire the same lock, yes, and agreed, if it were lockless but provided the release and acquire ordering, then yes.
I'm not sure I got the point across; so I'll try once more. Without providing this ordering the completion would be fundamentally broken. It _must_ provide this ordering.
Quoted 3 lines
But if it was instead structured like wait_event()/wake_up(), there would be ordering only if the caller supplied it.
Right, wait_event()/wake_up() are different in that the 'condition' variable is external to the abstraction and thus it cannot help.
All wait_event()/wake_up() can guarantee is that IFF it does a wakeup, the woken thread will observe the prior state of the waker. But given the actual condition is external and we might not hit the actual sleep case, there is no guarantees.
Quoted 2 lines
All that aside, paring the ordering down to the bare minimum is not always the right approach.
Why not? In what sort of cases does it go wobbly?
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 6 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney
Quoted 4 lines
Quoted 3 lines
OK, I will bite... What do the
smp_store_release()and thesmp_load_acquire()correspond to? I see just plain locking inwait_for_completion()andcomplete().
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
They reflect the concept of
complete()/wait_for_completion(). Fundamentally all it needs to do is pass the message of 'completion'.That is, if we were to go optimize our completion implementation, it would be impossible to be weaker than this and still correct.
OK, though the model does not provide spinlocks, and there can be
Sigh. s/not//. The current model -does- provide spinlocks, though they are a bit new. I don't know of any breakage, but I am paranoid enough so that where feasible I double-check against xchg_acquire() and store_release().
Quoted 6 lines
Quoted 2 lines
differences in behavior between spinlocks and release-acquire. But yes, in this case, it works.
Sure; but the fundamental property here is that if we observe the
complete()we must also observe everything that went before. The exact means of implementing that is irrelevant.
Agreed, and that also tends to speed up the running of the model on the litmus test, so this sort of abstraction is a very good thing for multiple reasons.
So why did I use spinlocks? Because the model was small and fast enough, and using the spinlocks meant that I didn't need to take time to worry about the code's intent.
But if you are saying that it would be good to have wait_for_completion() and complete() directly modeled at some point, no argument. In addition, I hope that the memory model is applied to other tools that analyze kernel code.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines
So I dropped that patch yesterday. The main thing I was missing was that there is no ordering-free fastpath in
wait_for_completion()andcomplete(): Each unconditionally acquires the lock. So thesmp_mb()that I was trying to add doesn't need to be there.Going by the above, it never needs to be there, even if there was a lock-free fast-path.
Quoted 7 lines
Quoted 3 lines
Given that wait_for_completion()/complete() both acquire the same lock, yes, and agreed, if it were lockless but provided the release and acquire ordering, then yes.
I'm not sure I got the point across; so I'll try once more. Without providing this ordering the completion would be fundamentally broken. It _must_ provide this ordering.
OK, I now understand what you are getting at, and I do very much like that guarantee.
Quoted 11 lines
Quoted 3 lines
But if it was instead structured like wait_event()/wake_up(), there would be ordering only if the caller supplied it.
Right, wait_event()/wake_up() are different in that the 'condition' variable is external to the abstraction and thus it cannot help.
All wait_event()/wake_up() can guarantee is that IFF it does a wakeup, the woken thread will observe the prior state of the waker. But given the actual condition is external and we might not hit the actual sleep case, there is no guarantees.
Agreed.
Quoted 4 lines
Quoted 2 lines
All that aside, paring the ordering down to the bare minimum is not always the right approach.
Why not? In what sort of cases does it go wobbly?
For one, when it conflicts with maintainability. For example, it would probably be OK for some of RCU's rcu_node ->lock acquisitions to skip the smp_mb__after_unlock_lock() invocations. But those are slowpaths, and the small speedup on only one architecture is just not worth the added pain. Especially given the nice wrapper functions that you provided.
But of course if this were instead (say) rcu_read_lock() or common-case rcu_read_unlock(), I would be willing to undergo much more pain. On the other hand, for that exact reason, that common-case code path doesn't acquire locks in the first place. ;-)
Thanx, Paul
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 11 lines · Paul E. McKenney
But if you are saying that it would be good to have
wait_for_completion()andcomplete()directly modeled at some point, no argument. In addition, I hope that the memory model is applied to other tools that analyze kernel code.Quoted 3 lines
I'm not sure I got the point across; so I'll try once more. Without providing this ordering the completion would be fundamentally broken. It _must_ provide this ordering.
OK, I now understand what you are getting at, and I do very much like that guarantee.
Right, so maybe we should update the completion comments a bit to call out this property, because I'm not sure its there.
Also, with this, I think the smp_store_release() / smp_load_acquire() is a perfectly fine abstraction of it, I don't think the model needs to be taught about the completion interface.
Quoted 8 lines
Quoted 1 line
Why not? In what sort of cases does it go wobbly?
For one, when it conflicts with maintainability. For example, it would probably be OK for some of RCU's
rcu_node->lock acquisitions to skip thesmp_mb__after_unlock_lock()invocations. But those are slowpaths, and the small speedup on only one architecture is just not worth the added pain. Especially given the nice wrapper functions that you provided.
Quoted 4 lines
But of course if this were instead (say)
rcu_read_lock()or common-casercu_read_unlock(), I would be willing to undergo much more pain. On the other hand, for that exact reason, that common-case code path doesn't acquire locks in the first place. ;-)
Ah, so for models I would go absolutely minimal; it helps understand what the strict requirements are and where we over-provide etc..
For actual code you're entirely right, there's no point in trying to be cute with the rcu-node locks. Simplicity rules etc..
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 28 lines · Peter Zijlstra
Quoted 11 lines · Paul E. McKenney
But if you are saying that it would be good to have
wait_for_completion()andcomplete()directly modeled at some point, no argument. In addition, I hope that the memory model is applied to other tools that analyze kernel code.Quoted 3 lines
I'm not sure I got the point across; so I'll try once more. Without providing this ordering the completion would be fundamentally broken. It _must_ provide this ordering.
OK, I now understand what you are getting at, and I do very much like that guarantee.
Right, so maybe we should update the completion comments a bit to call out this property, because I'm not sure its there.
Also, with this, I think the
smp_store_release()/smp_load_acquire()is a perfectly fine abstraction of it, I don't think the model needs to be taught about the completion interface.Quoted 8 lines
Quoted 1 line
Why not? In what sort of cases does it go wobbly?
For one, when it conflicts with maintainability. For example, it would probably be OK for some of RCU's
rcu_node->lock acquisitions to skip thesmp_mb__after_unlock_lock()invocations. But those are slowpaths, and the small speedup on only one architecture is just not worth the added pain. Especially given the nice wrapper functions that you provided.
Quoted 7 lines
Quoted 4 lines
But of course if this were instead (say)
rcu_read_lock()or common-casercu_read_unlock(), I would be willing to undergo much more pain. On the other hand, for that exact reason, that common-case code path doesn't acquire locks in the first place. ;-)Ah, so for models I would go absolutely minimal; it helps understand what the strict requirements are and where we over-provide etc..
Except, maybe, that simplicity and maintainability do apply to "models" (design) as well... ;-)
As Ingo once put it [1] (referring to the "Linux-kernel memory model"):
"it's not true that Linux has to offer a barrier and locking model
that panders to the weakest (and craziest!) memory ordering model amongst all the possible Linux platforms - theoretical or real metal.
Instead what we want to do is to consciously, intelligently _pick_ a sane, maintainable memory model and offer primitives for that - at least as far as generic code is concerned. Each architecture can map those primitives to the best of its abilities."
Andrea
[1] https://marc.info/?l=linux-mm&m=138513336717990&w=2
Quoted 3 lines
For actual code you're entirely right, there's no point in trying to be cute with the rcu-node locks. Simplicity rules etc..
Re: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
But if you are saying that it would be good to have
wait_for_completion()andcomplete()directly modeled at some point, no argument. In addition, I hope that the memory model is applied to other tools that analyze kernel code.Quoted 3 lines
I'm not sure I got the point across; so I'll try once more. Without providing this ordering the completion would be fundamentally broken. It _must_ provide this ordering.
Quoted 5 lines
Quoted 2 lines
OK, I now understand what you are getting at, and I do very much like that guarantee.
Right, so maybe we should update the completion comments a bit to call out this property, because I'm not sure its there.
That would be very good!
Quoted 3 lines
Also, with this, I think the
smp_store_release()/smp_load_acquire()is a perfectly fine abstraction of it, I don't think the model needs to be taught about the completion interface.
Agreed, if we pull too much stuff into the model it might well become difficult to maintain in and of itself. So we do need to choose carefully based on model performance and ease of use.
For a performance example, note that locking can be easily modeled with xchg_acquire() for lock acquisition and smp_store_release() for lock release. But here is the resulting performance compared to directly modeling locking within the cat code:
xchg_acquire() and # Processes smp_store_release() Direct modeling 2 0.061 s 0.007 s 3 3.542 s 0.039 s 4 569.189 s 0.397 s 5 > 113,853.000 s 5.187 s
Combinatorial explosion is a real pain... The problem is that the xchg_acquire() / smp_store_release() approach requires the herd7 tool to consider and then reject all the scenarios where the lock critical sections overlap. In contrast, when direct modeling, those overlapping critical-section scenarios are implicitly rejected by the cat-code that models locking. Don't get me wrong, there is still combinatorial explosion, as you can see from the rightmost column of numbers. After all, the herd7 tool still needs to consider all possible lock-acquisition orders. But the explosion is much less explosive. ;-)
Given that we expect locking to be very heavily used, it makes a lot of sense to directly model it, which we (mostly Alan, Andrea, and Luc) have done. Direct modeling of RCU gets similar speedups over emulation, plus the fact that accurate emulation of RCU requires some surprisingly unnatural acts. ("Ghost" accesses unaffected by normal memory-ordering primitives, and "ghost-buster memory barriers" that affect both "ghost" and normal accesses. Plus the transformation is complex, so much so that I broke down and wrote a script, which was used to validate the early versions of the RCU model.)
In constrast, I have no reason to believe that direct modeling could make wait_for_completion() / complete() go any faster than the equivalent setup using smp_store_release() / smp_load_acquire(), that is, I don't see anything that could be optimized away byt cat-code. So the only reason to directly model wait_for_completion() / complete() would be to get rid of the need to add the extra term to the "exists" clause. And agreed, we should wait until people are actually being significantly inconvenienced by this, which I do not expect any time soon.
Quoted 8 lines
Quoted 8 lines
Quoted 1 line
Why not? In what sort of cases does it go wobbly?
For one, when it conflicts with maintainability. For example, it would probably be OK for some of RCU's
rcu_node->lock acquisitions to skip thesmp_mb__after_unlock_lock()invocations. But those are slowpaths, and the small speedup on only one architecture is just not worth the added pain. Especially given the nice wrapper functions that you provided.
Quoted 7 lines
Quoted 4 lines
But of course if this were instead (say)
rcu_read_lock()or common-casercu_read_unlock(), I would be willing to undergo much more pain. On the other hand, for that exact reason, that common-case code path doesn't acquire locks in the first place. ;-)Ah, so for models I would go absolutely minimal; it helps understand what the strict requirements are and where we over-provide etc..
Agreed, we should be careful how much we promise lest we get locked into needlessly heavyweight implementations.
Quoted 2 lines
For actual code you're entirely right, there's no point in trying to be cute with the rcu-node locks. Simplicity rules etc..
Hear, hear! ;-)
Thanx, Paul
Steven Rostedt
reviewerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
In reply to Paul E. McKenneyQuoted 5 lines · On Wed, 4 Oct 2017 14:29:27 -0700 "Paul E. McKenney"…
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().
A starts rcu_read_lock() critical section.
Quoted 3 lines
o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:
B waits for A.
Quoted 4 lines
o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.
[ isn't B blocked (off rq)? How does it migrate? ]
Quoted 10 lines
o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
Quoted 8 lines
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.
A calls rcu_read_unlock() ending the critical section
Quoted 9 lines
o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().
Quoted 5 lines
o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.
B runs
Quoted 3 lines
It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
I don't see how B ran during A's critical section.
-- Steve
Quoted 5 lines
However, if CPU hotplug ever gets rid of
stop_machine(), there will be more straightforward ways for this sort of thing to happen, so this commit adds a memory barrier in order to enforce the needed ordering.
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 15 lines · Steven Rostedt
Quoted 5 lines · On Wed, 4 Oct 2017 14:29:27 -0700 "Paul E. McKenney"…
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().A starts
rcu_read_lock()critical section.Quoted 3 lines
o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:
Quoted 8 lines
B waits for A.
Quoted 4 lines
o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.[ isn't B blocked (off rq)? How does it migrate? ]
No, its running synchronize_rcu() but hasn't blocked yet. It would block on wait_for_completion(), but per the very last point, we'll observe the complete() before we block.
Quoted 12 lines
Quoted 12 lines
o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.
Quoted 7 lines
Quoted 5 lines
o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.A calls
rcu_read_unlock()ending the critical section
The point is that rcu_read_unlock() doesn't have memory ordering.
Quoted 15 lines
Quoted 9 lines
o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().Quoted 5 lines
o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.
Quoted 8 lines
B runs
Quoted 3 lines
It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
I don't see how B ran during A's critical section.
It didn't but that doesn't mean the memory ordering agrees. What we require is B observes (per the memory ordering) everything up to and including the rcu_read_unlock(). This is not 'time' related.
That said, I don't think it can actually happen, because CPU0's QS state is ordered against the complete and the wait_for_completion is ordered against the complete.
Steven Rostedt
reviewerRe: [PATCH tip/core/rcu 1/9] rcu: Provide GP ordering in face of migrations and delays
Quoted 23 lines · On Thu, 5 Oct 2017 15:40:42 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 22 lines · Steven Rostedt
Quoted 5 lines · On Wed, 4 Oct 2017 14:29:27 -0700 "Paul E. McKenney"…
Consider the following admittedly improbable sequence of events:
o RCU is initially idle.
o Task A on CPU 0 executes
rcu_read_lock().A starts
rcu_read_lock()critical section.Quoted 3 lines
o Task B on CPU 1 executes
synchronize_rcu(), which must
wait on Task A:B waits for A.
Quoted 4 lines
o Task B registers the callback, which starts a new
grace period, awakening the grace-period kthread on CPU 3, which immediately starts a new grace period.
Quoted 5 lines
Quoted 1 line
[ isn't B blocked (off rq)? How does it migrate? ]
No, its running
synchronize_rcu()but hasn't blocked yet. It would block onwait_for_completion(), but per the very last point, we'll observe thecomplete()before we block.
Hmm, maybe this should be stated as well, as it looked confusing.
Quoted 16 lines
Quoted 16 lines
Quoted 16 lines
o Task B migrates to CPU 2, which provides a quiescent
state for both CPUs 1 and 2.o Both CPUs 1 and 2 take scheduling-clock interrupts,
and both invokeRCU_SOFTIRQ, both thus learning of the new grace period.o Task B is delayed, perhaps by vCPU preemption on CPU 2.
o CPUs 2 and 3 pass through quiescent states, which are reported
to core RCU.o Task B is resumed just long enough to be migrated to CPU 3,
and then is once again delayed.
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
o Task A executes
rcu_read_unlock(), exiting its RCU read-side
critical section.A calls
rcu_read_unlock()ending the critical sectionThe point is that
rcu_read_unlock()doesn't have memory ordering.
Ah, that makes a difference. Can we state that in the change log too.
Quoted 20 lines
Quoted 20 lines
Quoted 10 lines
o CPU 0 passes through a quiescent sate, which is reported to
core RCU. Only CPU 1 continues to block the grace period.o CPU 1 passes through a quiescent state, which is reported to
core RCU. This ends the grace period, and CPU 1 therefore invokes its callbacks, one of which awakens Task B viacomplete().Quoted 5 lines
o Task B resumes (still on CPU 3) and starts executing
wait_for_completion(), which sees that the completion has already completed, and thus does not block. It returns from thesynchronize_rcu()without any ordering against the end of Task A's RCU read-side critical section.B runs
Quoted 1 line
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
It can therefore mess up Task A's RCU read-side critical section, in theory, anyway.
I don't see how B ran during A's critical section.
It didn't but that doesn't mean the memory ordering agrees. What we require is B observes (per the memory ordering) everything up to and including the
rcu_read_unlock(). This is not 'time' related.
OK, that makes sense. It was just missing from the change log, so mere mortals like myself can keep up. (This is why I'm Batman. I'm only human but I can still compete with superheros ;-)
Quoted 5 lines
That said, I don't think it can actually happen, because CPU0's QS state is ordered against the complete and the
wait_for_completionis ordered against the complete.
OK, but this doesn't hurt to have. Just a paranoid check, which when it comes to RCU, leaning toward paranoid is good.
-- Steve
PATCH 2/9 rcu: Fix up pending cbs check in rcu_prepare_for_idle
In reply to Paul E. McKenneyFrom: Neeraj Upadhyay <[email protected]>
The pending-callbacks check in rcu_prepare_for_idle() is backwards. It should accelerate if there are pending callbacks, but the check rather uselessly accelerates only if there are no callbacks. This commit therefore inverts this check.
--- kernel/rcu/tree_plugin.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/rcu/tree_plugin.h +1 -1
@@ -1507,7 +1507,7 @@ static void rcu_prepare_for_idle(void) rdtp->last_accelerate = jiffies;for_each_rcu_flavor (rsp) { rdp =this_cpu_ptr (rsp->rda); -if (rcu_segcblist_pend_cbs (&rdp->cblist)) +if (!rcu_segcblist_pend_cbs (&rdp->cblist))continue ; rnp = rdp->mynode;raw_spin_lock_rcu_node (rnp);/* irqs already disabled. */
Signature · 1 line
2.5.2
PATCH 3/9 rcu: Create call_rcu_tasks() kthread at boot time
In reply to Paul E. McKenneyCurrently the call_rcu_tasks() kthread is created upon first invocation of call_rcu_tasks(). This has the advantage of avoiding creation if there are never any invocations of call_rcu_tasks() and of synchronize_rcu_tasks(), but it requires an unreliable heuristic to determine when it is safe to create the kthread. For example, it is not safe to create the kthread when call_rcu_tasks() is invoked with a spinlock held, but there is no good way to detect this in !PREEMPT kernels.
This commit therefore creates this kthread unconditionally at core_initcall() time. If you don't want this kthread created, then build with CONFIG_TASKS_RCU=n.
--- kernel/rcu/update.c | 24 +++++------------------- 1 file changed, 5 insertions(+), 19 deletions(-)
kernel/rcu/update.c +5 -19
@@ -585,7 +585,6 @@ DEFINE_STATIC_SRCU(tasks_rcu_exit_srcu);static int rcu_task_stall_timeout__read_mostly =RCU_TASK_STALL_TIMEOUT ;module_param (rcu_task_stall_timeout, int,0644 ); -static void rcu_spawn_tasks_kthread (void );static struct task_struct *rcu_tasks_kthread_ptr;/**
@@ -610,7 +609,6 @@ void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func) {unsigned long flags;bool needwake; -bool havetask =READ_ONCE (rcu_tasks_kthread_ptr); rhp->next =NULL ; rhp->func = func;
@@ -620,11 +618,8 @@ void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func) rcu_tasks_cbs_tail = &rhp->next;raw_spin_unlock_irqrestore (&rcu_tasks_cbs_lock, flags);/* We can't create the thread unless interrupts are enabled. */ -if ((needwake && havetask) || - (!havetask && !irqs_disabled_flags (flags))) { -rcu_spawn_tasks_kthread (); +if (needwake &&READ_ONCE (rcu_tasks_kthread_ptr))wake_up (&rcu_tasks_cbs_wq); - } }EXPORT_SYMBOL_GPL (call_rcu_tasks);
@@ -863,27 +858,18 @@ static int __noreturn rcu_tasks_kthread(void *arg) } } -/* Spawn rcu_tasks_kthread() at first call to call_rcu_tasks(). */ -static void rcu_spawn_tasks_kthread (void ) +/* Spawn rcu_tasks_kthread() at core_initcall() time. */ +static int __init rcu_spawn_tasks_kthread (void ) { -static DEFINE_MUTEX (rcu_tasks_kthread_mutex);struct task_struct *t; -if (READ_ONCE (rcu_tasks_kthread_ptr)) { -smp_mb ();/* Ensure caller sees full kthread. */ -return ; - } -mutex_lock (&rcu_tasks_kthread_mutex); -if (rcu_tasks_kthread_ptr) { -mutex_unlock (&rcu_tasks_kthread_mutex); -return ; - } t =kthread_run (rcu_tasks_kthread,NULL ,"rcu_tasks_kthread" );BUG_ON (IS_ERR (t));smp_mb ();/* Ensure others see full kthread. */ WRITE_ONCE (rcu_tasks_kthread_ptr, t); -mutex_unlock (&rcu_tasks_kthread_mutex); +return 0 ; } +core_initcall (rcu_spawn_tasks_kthread);/* Do the srcu_read_lock() for the above synchronize_srcu(). */ void exit_tasks_rcu_start (void )
Signature · 1 line
2.5.2
PATCH 4/9 irq_work: Map irq_work_on_queue() to irq_work_on() in !SMP
In reply to Paul E. McKenneyCommit 478850160636 ("irq_work: Implement remote queueing") provides irq_work_on_queue() only for SMP builds. However, providing it simplifies code that submits irq_work to lists of CPUs, eliminating the !SMP special cases. This commit therefore maps irq_work_on_queue() to irq_work_on() in !SMP builds, but validating the specified CPU.
--- include/linux/irq_work.h | 3 --- kernel/irq_work.c | 9 ++++++--- 2 files changed, 6 insertions(+), 6 deletions(-)
include/linux/irq_work.h +0 -3
@@ -33,10 +33,7 @@ void init_irq_work(struct irq_work *work, void (*func)(struct irq_work *))#define DEFINE_IRQ_WORK (name, _f) struct irq_work name = { .func = (_f), }bool irq_work_queue (struct irq_work *work); - -#ifdef CONFIG_SMP bool irq_work_queue_on (struct irq_work *work,int cpu); -#endif void irq_work_tick (void );void irq_work_sync (struct irq_work *work);
kernel/irq_work.c +6 -3
@@ -56,7 +56,6 @@ void __weak arch_irq_work_raise(void)*/ } -#ifdef CONFIG_SMP /* * Enqueue the irq_work @work on @cpu unless it's already pending * somewhere.
@@ -68,6 +67,8 @@ bool irq_work_queue_on(struct irq_work *work, int cpu)/* All work should have been flushed before going offline */ WARN_ON_ONCE (cpu_is_offline (cpu)); +#ifdef CONFIG_SMP +/* Arch remote IPI send/receive backend aren't NMI safe */ WARN_ON_ONCE (in_nmi ());
@@ -78,10 +79,12 @@ bool irq_work_queue_on(struct irq_work *work, int cpu)if (llist_add (&work->llnode, &per_cpu (raised_list, cpu)))arch_send_call_function_single_ipi (cpu); +#else /* #ifdef CONFIG_SMP */ +irq_work_queue (work); +#endif /* #else #ifdef CONFIG_SMP */ +return true; } -EXPORT_SYMBOL_GPL (irq_work_queue_on); -#endif /* Enqueue the irq work @work on the current CPU */ bool irq_work_queue (struct irq_work *work)
Signature · 1 line
2.5.2
PATCH 5/9 srcu: Add parameters to SRCU docbook comments
In reply to Paul E. McKenney--- include/linux/srcu.h | 1 + kernel/rcu/srcutree.c | 2 +- 2 files changed, 2 insertions(+), 1 deletion(-)
include/linux/srcu.h +1 -0
@@ -78,6 +78,7 @@ void synchronize_srcu(struct srcu_struct *sp);/** * srcu_read_lock_held - might we be in SRCU read-side critical section? +* @sp: The srcu_struct structure to check * * If CONFIG_DEBUG_LOCK_ALLOC is selected, returns nonzero iff in an SRCU * read-side critical section. In absence of CONFIG_DEBUG_LOCK_ALLOC,
kernel/rcu/srcutree.c +1 -1
@@ -854,7 +854,7 @@ void __call_srcu(struct srcu_struct *sp, struct rcu_head *rhp,/** * call_srcu() - Queue a callback for invocation after an SRCU grace period * @sp: srcu_struct in queue the callback -* @head: structure to be used for queueing the SRCU callback. +* @rhp: structure to be used for queueing the SRCU callback. * @func: function to be invoked after the SRCU grace period * * The callback function will be invoked some time after a full SRCU
Signature · 1 line
2.5.2
PATCH 6/9 sched: Make resched_cpu() unconditional
In reply to Paul E. McKenneyThe current implementation of synchronize_sched_expedited() incorrectly assumes that resched_cpu() is unconditional, which it is not. This means that synchronize_sched_expedited() can hang when resched_cpu()'s trylock fails as follows (analysis by Neeraj Upadhyay):
o CPU1 is waiting for expedited wait to complete:
sync_rcu_exp_select_cpus rdp->exp_dynticks_snap & 0x1 // returns 1 for CPU5 IPI sent to CPU5 synchronize_sched_expedited_wait ret = swait_event_timeout(rsp->expedited_wq, sync_rcu_preempt_exp_done(rnp_root), jiffies_stall); expmask = 0x20, CPU 5 in idle path (in cpuidle_enter())
o CPU5 handles IPI and fails to acquire rq lock.
Handles IPI sync_sched_exp_handler resched_cpu returns while failing to try lock acquire rq->lock need_resched is not set
o CPU5 calls rcu_idle_enter() and as need_resched is not set, goes to
idle (schedule() is not called).
o CPU 1 reports RCU stall.
Given that resched_cpu() is now used only by RCU, this commit fixes the assumption by making resched_cpu() unconditional.
--- kernel/sched/core.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/sched/core.c +1 -2
@@ -505,8 +505,7 @@ void resched_cpu(int cpu)struct rq *rq =cpu_rq (cpu);unsigned long flags; -if (!raw_spin_trylock_irqsave (&rq->lock, flags)) -return ; +raw_spin_lock_irqsave (&rq->lock, flags);resched_curr (rq);raw_spin_unlock_irqrestore (&rq->lock, flags); }
Signature · 1 line
2.5.2
PATCH 7/9 rcu: Pretend ->boost_mtx acquired legitimately
In reply to Paul E. McKenneyRCU priority boosting uses rt_mutex_init_proxy_locked() to initialize an rt_mutex structure in locked state held by some other task. When that other task releases it, lockdep complains (quite accurately, but a bit uselessly) that the other task never acquired it. This complaint can suppress other, more helpful, lockdep complaints, and in any case it is a false positive.
This commit therefore uses the mutex_acquire() macro to make it look like that other process legitimately acquired the lock, thus suppressing this lockdep false-positive complaint.
Of course, if lockdep ever learns about rt_mutex_init_proxy_locked(), this commit will need to be reverted.
--- kernel/rcu/tree_plugin.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)
kernel/rcu/tree_plugin.h +4 -1
@@ -529,8 +529,11 @@ void rcu_read_unlock_special(struct task_struct *t) }/* Unboost if we were boosted. */ -if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) +if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) { +/* For lockdep, pretend we acquired lock honestly. */ +mutex_acquire (&rnp->boost_mtx.dep_map,0 ,0 , _RET_IP_);rt_mutex_unlock (&rnp->boost_mtx); + }/* * If this was the last task on the expedited lists,
Signature · 1 line
2.5.2
Peter Zijlstra
maintainerRe: [PATCH tip/core/rcu 7/9] rcu: Pretend ->boost_mtx acquired legitimately
Quoted 7 lines · Paul E. McKenney
RCU priority boosting uses
rt_mutex_init_proxy_locked()to initialize anrt_mutexstructure in locked state held by some other task. When that other task releases it, lockdep complains (quite accurately, but a bit uselessly) that the other task never acquired it. This complaint can suppress other, more helpful, lockdep complaints, and in any case it is a false positive.
Quoted 8 lines
This commit therefore uses the
mutex_acquire()macro to make it look like that other process legitimately acquired the lock, thus suppressing this lockdep false-positive complaint.Of course, if lockdep ever learns about
rt_mutex_init_proxy_locked(), this commit will need to be reverted.Signed-off-by Paul E. McKenney <[email protected]>
This is a consequence of me doing:
f5694788ad8d ("rt_mutex: Add lockdep annotations")
Right?
Quoted 9 lines
--- kernel/rcu/tree_plugin.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)kernel/rcu/tree_plugin.h +0
-0
kernel/rcu/tree_plugin.h void rcu_read_unlock_special(struct task_struct *t) · line 536
Quoted 9 lines
kernel/rcu/tree_plugin.h +4
-1@@ -529,8 +529,11 @@ void rcu_read_unlock_special(struct task_struct *t) }/* Unboost if we were boosted. */ -if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) +if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) { +/* For lockdep, pretend we acquired lock honestly. */ +mutex_acquire (&rnp->boost_mtx.dep_map,0 ,0 , _RET_IP_);rt_mutex_unlock (&rnp->boost_mtx); + }
So I'm thinking the problem is that you're mixing rt_mutex and PI-futex primitives here. As per commit:
5293c2efda37 ("futex,rt_mutex: Provide futex specific rt_mutex API")
these are two separate APIs, that should, ideally, not be mixed.
The 'right' counterpart to rt_mutex_init_proxy_locked() is rt_mutex_futex_unlock() (which very much does not include lockdep bits).
Re: [PATCH tip/core/rcu 7/9] rcu: Pretend ->boost_mtx acquired legitimately
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Paul E. McKenney
RCU priority boosting uses
rt_mutex_init_proxy_locked()to initialize anrt_mutexstructure in locked state held by some other task. When that other task releases it, lockdep complains (quite accurately, but a bit uselessly) that the other task never acquired it. This complaint can suppress other, more helpful, lockdep complaints, and in any case it is a false positive.This commit therefore uses the
mutex_acquire()macro to make it look like that other process legitimately acquired the lock, thus suppressing this lockdep false-positive complaint.Of course, if lockdep ever learns about
rt_mutex_init_proxy_locked(), this commit will need to be reverted.
Quoted 7 lines
Quoted 1 line
Signed-off-by Paul E. McKenney <[email protected]>This is a consequence of me doing:
f5694788ad8d("rt_mutex: Add lockdep annotations")Right?
The timing matches, so I do believe this is the case.
Quoted 22 lines
Quoted 9 lines
--- kernel/rcu/tree_plugin.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)kernel/rcu/tree_plugin.h +0
-0kernel/rcu/tree_plugin.h void rcu_read_unlock_special(struct task_struct *t) · line 536
Quoted 9 lines
kernel/rcu/tree_plugin.h +4
-1@@ -529,8 +529,11 @@ void rcu_read_unlock_special(struct task_struct *t) }/* Unboost if we were boosted. */ -if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) +if (IS_ENABLED (CONFIG_RCU_BOOST ) && drop_boost_mutex) { +/* For lockdep, pretend we acquired lock honestly. */ +mutex_acquire (&rnp->boost_mtx.dep_map,0 ,0 , _RET_IP_);rt_mutex_unlock (&rnp->boost_mtx); + }So I'm thinking the problem is that you're mixing
rt_mutexand PI-futex primitives here. As per commit:
Quoted 6 lines
5293c2efda37("futex,rt_mutex: Provide futex specificrt_mutexAPI")these are two separate APIs, that should, ideally, not be mixed.
The 'right' counterpart to
rt_mutex_init_proxy_locked()isrt_mutex_futex_unlock()(which very much does not include lockdep bits).
OK, will give this a try. It does at least seem to build, so I guess that is a good start. ;-)
Thanx, Paul
PATCH 8/9 rcu: Add extended-quiescent-state testing advice
In reply to Paul E. McKenneyIf you add or remove calls to rcu_idle_enter(), rcu_user_enter(), rcu_irq_exit(), rcu_irq_exit_irqson(), rcu_idle_exit(), rcu_user_exit(), rcu_irq_enter(), rcu_irq_enter_irqson(), rcu_nmi_enter(), or rcu_nmi_exit(), you should run a full set of tests on a kernel built with CONFIG_RCU_EQS_DEBUG=y.
--- kernel/rcu/tree.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+)
kernel/rcu/tree.c +30 -0
@@ -837,6 +837,9 @@ static void rcu_eqs_enter(bool user)* We crowbar the ->dynticks_nesting field to zero to allow for * the possibility of usermode upcalls having messed up our count * of interrupt nesting level during the prior busy period. +* +* If you add or remove a call to rcu_idle_enter(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_idle_enter (void ) {
@@ -852,6 +855,9 @@ void rcu_idle_enter(void)* is permitted between this call and rcu_user_exit(). This way the * CPU doesn't need to maintain the tick for RCU maintenance purposes * when the CPU runs in userspace. +* +* If you add or remove a call to rcu_user_enter(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_user_enter (void ) {
@@ -875,6 +881,9 @@ void rcu_user_enter(void)* Use things like work queues to work around this limitation. * * You have been warned. +* +* If you add or remove a call to rcu_irq_exit(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_irq_exit (void ) {
@@ -899,6 +908,9 @@ void rcu_irq_exit(void)/* * Wrapper for rcu_irq_exit() where interrupts are enabled. +* +* If you add or remove a call to rcu_irq_exit_irqson(), be sure to test +* with CONFIG_RCU_EQS_DEBUG=y. */ void rcu_irq_exit_irqson (void ) {
@@ -971,6 +983,9 @@ static void rcu_eqs_exit(bool user)* allow for the possibility of usermode upcalls messing up our count * of interrupt nesting level during the busy period that is just * now starting. +* +* If you add or remove a call to rcu_idle_exit(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_idle_exit (void ) {
@@ -987,6 +1002,9 @@ void rcu_idle_exit(void)* * Exit RCU idle mode while entering the kernel because it can * run a RCU read side critical section anytime. +* +* If you add or remove a call to rcu_user_exit(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_user_exit (void ) {
@@ -1012,6 +1030,9 @@ void rcu_user_exit(void)* Use things like work queues to work around this limitation. * * You have been warned. +* +* If you add or remove a call to rcu_irq_enter(), be sure to test with +* CONFIG_RCU_EQS_DEBUG=y. */ void rcu_irq_enter (void ) {
@@ -1037,6 +1058,9 @@ void rcu_irq_enter(void)/* * Wrapper for rcu_irq_enter() where interrupts are enabled. +* +* If you add or remove a call to rcu_irq_enter_irqson(), be sure to test +* with CONFIG_RCU_EQS_DEBUG=y. */ void rcu_irq_enter_irqson (void ) {
@@ -1055,6 +1079,9 @@ void rcu_irq_enter_irqson(void)* that the CPU is active. This implementation permits nested NMIs, as * long as the nesting level does not overflow an int. (You will probably * run out of stack space first.) +* +* If you add or remove a call to rcu_nmi_enter(), be sure to test +* with CONFIG_RCU_EQS_DEBUG=y. */ void rcu_nmi_enter (void ) {
@@ -1087,6 +1114,9 @@ void rcu_nmi_enter(void)* RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting * to let the RCU grace-period handling know that the CPU is back to * being RCU-idle. +* +* If you add or remove a call to rcu_nmi_exit(), be sure to test +* with CONFIG_RCU_EQS_DEBUG=y. */ void rcu_nmi_exit (void ) {
Signature · 1 line
2.5.2
PATCH 9/9 rcu/segcblist: Include rcupdate.h
In reply to Paul E. McKenneyFrom: Sebastian Andrzej Siewior <[email protected]>
The RT build on ARM complains about non-existing ULONG_CMP_LT. This commit therefore includes rcupdate.h into rcu_segcblist.c.
--- kernel/rcu/rcu_segcblist.c | 1 + 1 file changed, 1 insertion(+)
kernel/rcu/rcu_segcblist.c +1 -0
@@ -23,6 +23,7 @@#include <linux/types.h> #include <linux/kernel.h> #include <linux/interrupt.h> +#include <linux/rcupdate.h> #include "rcu_segcblist.h"
Signature · 1 line
2.5.2