Miscellaneous fixes for v4.15

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.

RCU 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.

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree_plugin.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

kernel/rcu/tree_plugin.h +0 -0

index fed95fa941e6..60bfb16c9a1a 100644

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.

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.

[ isn't B blocked (off rq)? How does it migrate? ]

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 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.

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

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 via complete().

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 the synchronize_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.

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 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 on wait_for_completion(), but per the very last point, we'll observe the complete() before we block.

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 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.

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 section

The point is that rcu_read_unlock() doesn't have memory ordering.

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 via complete().

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 the synchronize_rcu() without any ordering against the end of Task A's RCU read-side critical section.

B runs

Quoted 1 line

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.

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.

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 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.

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 by complete(), no?

And is not CPU0's QS reporting ordered against that complete()?

Quoted 14 lines · Paul E. McKenney

RCU 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.

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?

Quoted 9 lines

---
 kernel/rcu/tree_plugin.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

kernel/rcu/tree_plugin.h +0 -0

index fed95fa941e6..60bfb16c9a1a 100644

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).

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 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.

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 by complete(), 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?

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 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.

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 by complete(), 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.)

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().

Yes, the ordering does need to be visible to uninvolved CPUs, so release-acquire is not necessarily strong enough.

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)

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

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 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().

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.

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 the smp_load_acquire() correspond to? I see just plain locking in wait_for_completion() and complete().

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() and complete(): Each unconditionally acquires the lock. So the smp_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

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().

They reflect the concept of complete() / wait_for_completion(). Fundamentally all it needs to do is pass the message of 'completion'.

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.

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() and complete(): Each unconditionally acquires the lock. So the smp_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.

Quoted 4 lines · Paul E. McKenney

Quoted 4 lines

Quoted 3 lines

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 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

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.

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() and complete(): Each unconditionally acquires the lock. So the smp_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 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.

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?

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 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.

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 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. ;-)

Quoted 11 lines · Paul E. McKenney

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 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 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.

Quoted 4 lines

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. ;-)

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..

Quoted 9 lines · Paul E. McKenney

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 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 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.

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 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.

Quoted 4 lines

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. ;-)

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..