Skip to contentSkip to conversation

Q: schedule() and implied barriers on arm64

DISCUSSION Peter Zijlstra 5 participants 20 messages Oct 16, 2015 – Oct 28, 2015

lore
Share & tools
lore
#0 lore raw

Hi,

IIRC Paul relies on schedule() implying a full memory barrier with strong transitivity for RCU.

If not, ignore this email.

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

	smp_mb__before_spinlock();
	LOCK rq->lock

	clear_bit()

	UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

#1 lore raw
Quoted 6 lines · Peter Zijlstra

Hi,

IIRC Paul relies on schedule() implying a full memory barrier with strong transitivity for RCU.

If not, ignore this email.

Not so sure about schedule(), but definitely need strong transitivity for the rcu_node structure's ->lock field. And the atomic operations on the rcu_dyntick structure's fields when entering or leaving the idle loop.

With schedule, the thread later reports the quiescent state, which involves acquiring the rcu_node structure's ->lock field. So I -think- that the locks in the scheduler can be weakly transitive.

Quoted 14 lines

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

	smp_mb__before_spinlock();
	LOCK rq->lock

	clear_bit()

	UNLOCK rq->lock
Quoted 8 lines

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

Well, arm64 might well need smp_mb__after_unlock_lock() to be non-empty. But I thought that it used a dmb in the spinlock code somewhere or another...

Thanx, Paul

#2 lore raw
Quoted 8 lines · Paul E. McKenney
Quoted 6 lines · Peter Zijlstra

Hi,

IIRC Paul relies on schedule() implying a full memory barrier with strong transitivity for RCU.

If not, ignore this email.

Quoted 8 lines

Not so sure about schedule(), but definitely need strong transitivity for the rcu_node structure's ->lock field. And the atomic operations on the rcu_dyntick structure's fields when entering or leaving the idle loop.

With schedule, the thread later reports the quiescent state, which involves acquiring the rcu_node structure's ->lock field. So I -think- that the locks in the scheduler can be weakly transitive.

So I _thought_ you needed this to separate the preempt_disabled sections. Such that rcu_note_context_switch() is guaranteed to be done before a new preempt_disabled region starts.

But if you really only need program order guarantees for that, and deal with everything else from your tick, then that's fine too.

Maybe some previous RCU variant relied on this?

Quoted 19 lines
Quoted 19 lines

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

	smp_mb__before_spinlock();
	LOCK rq->lock

	clear_bit()

	UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Quoted 6 lines
Quoted 3 lines

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

But I thought that it used a dmb in the spinlock code somewhere or another...

arm does, arm64 not so much.

Quoted 1 line

Well, arm64 might well need smp_mb__after_unlock_lock() to be non-empty.

Its UNLOCK+LOCK should be RCsc, so that should be good. Its just that LOCK+UNLOCK isn't anything.

#3 lore raw
Quoted 18 lines · Peter Zijlstra
Quoted 8 lines · Paul E. McKenney
Quoted 6 lines · Peter Zijlstra

Hi,

IIRC Paul relies on schedule() implying a full memory barrier with strong transitivity for RCU.

If not, ignore this email.

Quoted 8 lines

Not so sure about schedule(), but definitely need strong transitivity for the rcu_node structure's ->lock field. And the atomic operations on the rcu_dyntick structure's fields when entering or leaving the idle loop.

With schedule, the thread later reports the quiescent state, which involves acquiring the rcu_node structure's ->lock field. So I -think- that the locks in the scheduler can be weakly transitive.

Quoted 8 lines

So I _thought_ you needed this to separate the preempt_disabled sections. Such that rcu_note_context_switch() is guaranteed to be done before a new preempt_disabled region starts.

But if you really only need program order guarantees for that, and deal with everything else from your tick, then that's fine too.

Maybe some previous RCU variant relied on this?

Yes, older versions did rely on this. Now, only the CPU itself observes RCU's state changes during context switch. I couldn't tell you exactly when this changed. :-/

With the exception of some synchronize_sched_expedited() cases, but in those cases, RCU code acquires the CPU's leaf rcu_node structure's ->lock, and with the required strong transitivity.

Quoted 26 lines
Quoted 19 lines
Quoted 19 lines

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

	smp_mb__before_spinlock();
	LOCK rq->lock

	clear_bit()

	UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Quoted 6 lines
Quoted 3 lines

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

But I thought that it used a dmb in the spinlock code somewhere or another...

Quoted 6 lines

arm does, arm64 not so much.

Quoted 1 line

Well, arm64 might well need smp_mb__after_unlock_lock() to be non-empty.

Its UNLOCK+LOCK should be RCsc, so that should be good. Its just that LOCK+UNLOCK isn't anything.

Ah! If RCU relies on LOCK+UNLOCK being a barrier of any sort, that is a bug in RCU that needs fixing.

Thanx, Paul

#4 lore raw
Quoted 9 lines · Paul E. McKenney
Quoted 1 line

Maybe some previous RCU variant relied on this?

Yes, older versions did rely on this. Now, only the CPU itself observes RCU's state changes during context switch. I couldn't tell you exactly when this changed. :-/

With the exception of some synchronize_sched_expedited() cases, but in those cases, RCU code acquires the CPU's leaf rcu_node structure's ->lock, and with the required strong transitivity.

OK, so I can scrap this 'requirement' from my list. All sorted, thanks!

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

Well, arm64 might well need smp_mb__after_unlock_lock() to be non-empty.

Its UNLOCK+LOCK should be RCsc, so that should be good. Its just that LOCK+UNLOCK isn't anything.

Ah! If RCU relies on LOCK+UNLOCK being a barrier of any sort, that is a bug in RCU that needs fixing.

Don't think RCU does that, But its what schedule() provides in the weakest case. Hence my question here.

#5 lore raw
In reply to Peter Zijlstra

I'll try to reply in Will's absence, though I gave up trying to understand these threads long time ago ;).

Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Peter Zijlstra

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

    smp_mb__before_spinlock();
    LOCK rq->lock

    clear_bit()

    UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

But I thought that it used a dmb in the spinlock code somewhere or another...

arm does, arm64 not so much.

arm64 indeed does not have a dmb after spin_lock, it only has a load-acquire. So with the default smp_mb__before_spinlock() + spin_lock we have:

smp_wmb()
loop
load-acquire
store

So (I think) this guarantees that any writes before wmb+lock would be visible before any reads _and_ writes after wmb+lock. However, the ordering with reads before wmb+lock is not guaranteed.

Signature · 1 line
Catalin
#6 lore raw
Quoted 38 lines · Catalin Marinas

I'll try to reply in Will's absence, though I gave up trying to understand these threads long time ago ;).

Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Peter Zijlstra

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

    smp_mb__before_spinlock();
    LOCK rq->lock

    clear_bit()

    UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

But I thought that it used a dmb in the spinlock code somewhere or another...

arm does, arm64 not so much.

arm64 indeed does not have a dmb after spin_lock, it only has a load-acquire. So with the default smp_mb__before_spinlock() + spin_lock we have:

Quoted 8 lines

smp_wmb()
loop
load-acquire
store

So (I think) this guarantees that any writes before wmb+lock would be visible before any reads _and_ writes after wmb+lock. However, the ordering with reads before wmb+lock is not guaranteed.

So RCU needs the following sort of guarantee:

	void task1(unsigned long flags)
	{
		WRITE_ONCE(x, 1);
		WRITE_ONCE(z, 1);
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
	}

	void task2(unsigned long *flags)
	{
		raw_spin_lock_irqsave(&rnp->lock, *flags);
		smp_mb__after_unlock_lock();
		r1 = READ_ONCE(y);
		r2 = READ_ONCE(z);
	}

	void task3(void)
	{
		WRITE_ONCE(y, 1);
		smp_mb();
		r3 = READ_ONCE(x);
	}

	BUG_ON(!r1 && r2 && !r3); /* After the dust settles. */

In other words, if task2() acquires the lock after task1() releases it, all CPUs must agree on the order of the operations in the two critical sections, even if these other CPUs don't acquire the lock.

This same guarantee is needed if task1() and then task2() run in succession on the same CPU with no additional synchronization of any sort.

Does this work on arm64?

Thanx, Paul

#7 lore raw
Quoted 8 lines · Paul E. McKenney

In other words, if task2() acquires the lock after task1() releases it, all CPUs must agree on the order of the operations in the two critical sections, even if these other CPUs don't acquire the lock.

This same guarantee is needed if task1() and then task2() run in succession on the same CPU with no additional synchronization of any sort.

Does this work on arm64?

Yes, their load-acquire and store-release are RCsc.

#8 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Paul E. McKenney

In other words, if task2() acquires the lock after task1() releases it, all CPUs must agree on the order of the operations in the two critical sections, even if these other CPUs don't acquire the lock.

This same guarantee is needed if task1() and then task2() run in succession on the same CPU with no additional synchronization of any sort.

Does this work on arm64?

Yes, their load-acquire and store-release are RCsc.

Whew!!!

Thanx, Paul

#9 lore raw
In reply to Paul E. McKenney
Quoted 26 lines · Paul E. McKenney

So RCU needs the following sort of guarantee:

	void task1(unsigned long flags)
	{
		WRITE_ONCE(x, 1);
		WRITE_ONCE(z, 1);
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
	}

	void task2(unsigned long *flags)
	{
		raw_spin_lock_irqsave(&rnp->lock, *flags);
		smp_mb__after_unlock_lock();
		r1 = READ_ONCE(y);
		r2 = READ_ONCE(z);
	}

	void task3(void)
	{
		WRITE_ONCE(y, 1);
		smp_mb();
		r3 = READ_ONCE(x);
	}

	BUG_ON(!r1 && r2 && !r3); /* After the dust settles. */
Quoted 8 lines

In other words, if task2() acquires the lock after task1() releases it, all CPUs must agree on the order of the operations in the two critical sections, even if these other CPUs don't acquire the lock.

This same guarantee is needed if task1() and then task2() run in succession on the same CPU with no additional synchronization of any sort.

Does this work on arm64?

I think it does. If r3 == 0, it means that READ_ONCE(x) in task3 is "observed" (in ARM ARM terms) by task1 before WRITE_ONCE(x, 1). The smp_mb() in task3 implies that WRITEONCE(y, 1) is also observed by task1.

A store-release is multi-copy atomic when "observed" with a load-acquire (from task2). When on the same CPU, they are always observed in program order. The store-release on ARM has the property that writes observed by task1 before store-release (that is WRITE_ONCE(y, 1) in task3) will be observed by other observers (task2) before the store-release is observed (the unlock).

The above rules guarantee that, when r3 == 0, WRITE_ONCE(y, 1) in task3 is observed by task2 (and task1), hence r1 == 1.

(a more formal proof would have to wait for Will to come back from holiday ;))

Signature · 1 line
Catalin
#10 lore raw
In reply to Catalin Marinas
Quoted 4 lines · Catalin Marinas

arm64 indeed does not have a dmb after spin_lock, it only has a load-acquire. So with the default smp_mb__before_spinlock() + spin_lock we have:

Quoted 8 lines

smp_wmb()
loop
load-acquire
store

So (I think) this guarantees that any writes before wmb+lock would be visible before any reads _and_ writes after wmb+lock. However, the ordering with reads before wmb+lock is not guaranteed.

That is my understanding as well, and stores could creep up from below the unlock and then the reads and those stores can cross and you've lost.

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

#11 lore raw
Quoted 4 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

[...]

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

Just like system calls are assumed to be barriers in general - and system calls are more lightweight than schedule() ...

Thanks,

Ingo

#12 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 3 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

Quoted 8 lines
Quoted 1 line

[...]

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

Just like system calls are assumed to be barriers in general -

Are they? I know they are on some platforms, but I'm not sure we've audited them all and established this.

Quoted 1 line

and system calls are more lightweight than schedule() ...

Hopefully, although if you enable nohz_full there's a fair chance to reverse that :-)

#13 lore raw
In reply to Ingo Molnar
Quoted 11 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

[...]

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

FWIW, the arm64 __switch_to() has a heavy barrier (DSB) but the reason for this was to cope with potentially interrupted cache or TLB maintenance (which require a DSB on the same CPU) and thread migration to another CPU.

Signature · 1 line
Catalin
#14 lore raw
Quoted 13 lines · Catalin Marinas
Quoted 11 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

[...]

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

Quoted 4 lines

FWIW, the arm64 __switch_to() has a heavy barrier (DSB) but the reason for this was to cope with potentially interrupted cache or TLB maintenance (which require a DSB on the same CPU) and thread migration to another CPU.

Right, but there's a path through schedule() that does not pass through __switch_to(); when we pick the current task as the most eligible task and next == prev.

In that case there really only is the wmb, a spin lock, an atomic op and a spin unlock (and a whole bunch of 'normal' code of course).

#15 lore raw
Quoted 18 lines · Peter Zijlstra
Quoted 8 lines · Catalin Marinas
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

[...]

Quoted 8 lines
Quoted 4 lines

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

FWIW, the arm64 __switch_to() has a heavy barrier (DSB) but the reason for this was to cope with potentially interrupted cache or TLB maintenance (which require a DSB on the same CPU) and thread migration to another CPU.

Quoted 6 lines

Right, but there's a path through schedule() that does not pass through __switch_to(); when we pick the current task as the most eligible task and next == prev.

In that case there really only is the wmb, a spin lock, an atomic op and a spin unlock (and a whole bunch of 'normal' code of course).

Yeah, so my concern is that this is a rare race that might be 'surprising' for developers relying on various schedule() constructs. Especially as it's a full barrier on x86 (the most prominent SMP platform at the moment) there's a real danger of hard to debug bugs creeping to other architectures.

So I think we should just do the small step of making it a full barrier everywhere
- it's very close to it in any case, and it shouldn't really matter for performance. Agreed?

Thanks,

Ingo

#16 lore raw
In reply to Peter Zijlstra
Quoted 19 lines · Peter Zijlstra
Quoted 13 lines · Catalin Marinas
Quoted 11 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra

In any case, its all moot now, since Paul no longer requires schedule() to imply a full barrier.

[...]

Nevertheless from a least-surprise POV it might be worth guaranteeing it, because I bet there's tons of code that assumes that schedule() is a heavy operation and it's such an easy mistake to make. Since we are so close to having that guarantee, we might as well codify it?

Quoted 4 lines

FWIW, the arm64 __switch_to() has a heavy barrier (DSB) but the reason for this was to cope with potentially interrupted cache or TLB maintenance (which require a DSB on the same CPU) and thread migration to another CPU.

Quoted 6 lines

Right, but there's a path through schedule() that does not pass through __switch_to(); when we pick the current task as the most eligible task and next == prev.

In that case there really only is the wmb, a spin lock, an atomic op and a spin unlock (and a whole bunch of 'normal' code of course).

... and the 'normal' code will have a control hazard somewhere, followed by the implicit ISB in exception return, so there's a barrier of sorts there too.

The problem is that people say "full barrier" without defining what it really means, and we end up going round the houses on things like transitivity (which ctrl + isb doesn't always give you).

Will

#17 lore raw
Quoted 3 lines · Will Deacon

... and the 'normal' code will have a control hazard somewhere, followed by the implicit ISB in exception return, so there's a barrier of sorts there too.

Which exception return?

Quoted 3 lines

The problem is that people say "full barrier" without defining what it really means, and we end up going round the houses on things like transitivity (which ctrl + isb doesn't always give you).

I pretty much meant smp_mb() here :-)

#18 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Will Deacon

... and the 'normal' code will have a control hazard somewhere, followed by the implicit ISB in exception return, so there's a barrier of sorts there too.

Which exception return?

The return to userspace after the interrupt/fault/system call that got us into the kernel.

Quoted 5 lines
Quoted 3 lines

The problem is that people say "full barrier" without defining what it really means, and we end up going round the houses on things like transitivity (which ctrl + isb doesn't always give you).

I pretty much meant smp_mb() here :-)

In which case, we don't provide the transitivity guarantees that you would get from an smp_mb().

Will

#19 lore raw
In reply to Paul E. McKenney
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Peter Zijlstra

If so, however, I suspect AARGH64 is borken and would need (just like PPC):

#define smp_mb__before_spinlock() smp_mb()

The problem is that schedule() (when a NO-OP) does:

      smp_mb__before_spinlock();
      LOCK rq->lock

      clear_bit()

      UNLOCK rq->lock

And nothing there implies a full barrier on AARGH64, since smp_mb__before_spinlock() defaults to WMB, LOCK is an "ldaxr" or load-acquire, UNLOCK is "stlrh" or store-release and clear_bit() isn't anything.

Quoted 7 lines
Quoted 3 lines

Pretty much every other arch has LOCK implying a full barrier, either because its strongly ordered or because it needs one for the ACQUIRE semantics.

Well, arm64 might well need smp_mb__after_unlock_lock() to be non-empty. But I thought that it used a dmb in the spinlock code somewhere or another...

unlock+lock on arm64 is a full barrier, so, IIUC the semantics of smp_mb__after_unlock_lock(), I don't think we need this to be non-empty. Maybe redefining smp_mb__before_spinlock() to be smp_mb() (rather than wmb) on arm64 if we need smp_mb__before_spinlock+lock to act as a barrier for both reads and writes (see my other reply to Peter).

Signature · 1 line
Catalin