Interrupts, smp_load_acquire(), smp_store_release(), etc.

Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Paul E. McKenney]

Hello!

David Goldblatt (CCed) came up with an interesting pair of C++ litmus
tests involving POSIX signals that have Linux-kernel counterparts
involving interrupts.  These litmus tests can (in paranoid theory, anyway)
produce counter-intuitive results on architectures that use explicit
fences to enforce ordering as part of a larger primitive, which in the
specific case of smp_store_release() includes all architectures other than
arm64, ia64, s390, SPARC, x86, and of course any UP-only architecture.

David's first litmus test made use of the C11 sequentially consistent
store, which in the Linux kernel would require two separate statements
anyway (a WRITE_ONCE() either preceded or followed by smp_mb()), so
the outcome that is counter-intuitive in C11 should be expected in the
Linux kernel.  (Yes, there are similar but more complicated examples that
would have more interesting outcomes in the Linux kernel, but let's keep
it simple for the moment.)

The second (informal) litmus test has a more interesting Linux-kernel
counterpart:

	void t1_interrupt(void)
	{
		r0 = READ_ONCE(y);
		smp_store_release(&x, 1);
	}

	void t1(void)
	{
		smp_store_release(&y, 1);
	}

	void t2(void)
	{
		r1 = smp_load_acquire(&x);
		r2 = smp_load_acquire(&y);
	}

On store-reordering architectures that implement smp_store_release()
as a memory-barrier instruction followed by a store, the interrupt could
arrive betweentimes in t1(), so that there would be no ordering between
t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.

In practice, we analyzed exception paths in the sys_membarrier() review,
and ended up with this function:

static void ipi_mb(void *info)
{
	smp_mb();	/* IPIs should be serializing but paranoid. */
}

So how paranoid should we be with respect to interrupt handlers for
smp_store_release(), smp_load_acquire(), and the various RMW atomic
operations that are sometimes implemented with separate memory-barrier
instructions?  ;-)

							Thanx, Paul

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Alan Stern]

On Sat, 20 Oct 2018, Paul E. McKenney wrote:

> The second (informal) litmus test has a more interesting Linux-kernel
> counterpart:
> 
> 	void t1_interrupt(void)
> 	{
> 		r0 = READ_ONCE(y);
> 		smp_store_release(&x, 1);
> 	}
> 
> 	void t1(void)
> 	{
> 		smp_store_release(&y, 1);
> 	}
> 
> 	void t2(void)
> 	{
> 		r1 = smp_load_acquire(&x);
> 		r2 = smp_load_acquire(&y);
> 	}
> 
> On store-reordering architectures that implement smp_store_release()
> as a memory-barrier instruction followed by a store, the interrupt could
> arrive betweentimes in t1(), so that there would be no ordering between
> t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.

This is disconcerting only if we assume that t1_interrupt() has to be
executed by the same CPU as t1().  If the interrupt could be fielded by
a different CPU then the paranoid outcome is perfectly understandable,
even in an SC context.

So the question really should be limited to situations where a handler 
is forced to execute in the context of a particular thread.  While 
POSIX does allow such restrictions for user programs, I'm not aware of 
any similar mechanism in the kernel.

Alan

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Alan Stern]

On Sat, 20 Oct 2018, Paul E. McKenney wrote:

> The second (informal) litmus test has a more interesting Linux-kernel
> counterpart:
> 
> 	void t1_interrupt(void)
> 	{
> 		r0 = READ_ONCE(y);
> 		smp_store_release(&x, 1);
> 	}
> 
> 	void t1(void)
> 	{
> 		smp_store_release(&y, 1);
> 	}
> 
> 	void t2(void)
> 	{
> 		r1 = smp_load_acquire(&x);
> 		r2 = smp_load_acquire(&y);
> 	}
> 
> On store-reordering architectures that implement smp_store_release()
> as a memory-barrier instruction followed by a store, the interrupt could
> arrive betweentimes in t1(), so that there would be no ordering between
> t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.

This is disconcerting only if we assume that t1_interrupt() has to be
executed by the same CPU as t1().  If the interrupt could be fielded by
a different CPU then the paranoid outcome is perfectly understandable,
even in an SC context.

So the question really should be limited to situations where a handler 
is forced to execute in the context of a particular thread.  While 
POSIX does allow such restrictions for user programs, I'm not aware of 
any similar mechanism in the kernel.

Alan

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Andrea Parri]

[...]

> The second (informal) litmus test has a more interesting Linux-kernel
> counterpart:
> 
> 	void t1_interrupt(void)
> 	{
> 		r0 = READ_ONCE(y);
> 		smp_store_release(&x, 1);
> 	}
> 
> 	void t1(void)
> 	{
> 		smp_store_release(&y, 1);
> 	}
> 
> 	void t2(void)
> 	{
> 		r1 = smp_load_acquire(&x);
> 		r2 = smp_load_acquire(&y);
> 	}
> 
> On store-reordering architectures that implement smp_store_release()
> as a memory-barrier instruction followed by a store, the interrupt could
> arrive betweentimes in t1(), so that there would be no ordering between
> t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.

FWIW, I'd rather call "paranoid" the act of excluding such outcome ;-)
but I admit that I've only run this test in *my mind*: in an SC world,

  CPU1				CPU2

  t1()
    t1_interrupt()
      r0 = READ_ONCE(y); // =0
				t2()
				  r1 = smp_load_acquire(&x); // =0
      smp_store_release(&x, 1);
    smp_store_release(&y, 1);
				  r2 = smp_load_acquire(&y); // =1


> So how paranoid should we be with respect to interrupt handlers for
> smp_store_release(), smp_load_acquire(), and the various RMW atomic
> operations that are sometimes implemented with separate memory-barrier
> instructions?  ;-)

Good question! ;-)

  Andrea


> 
> 							Thanx, Paul
> 

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Paul E. McKenney]

On Sat, Oct 20, 2018 at 04:18:37PM -0400, Alan Stern wrote:
> On Sat, 20 Oct 2018, Paul E. McKenney wrote:
> 
> > The second (informal) litmus test has a more interesting Linux-kernel
> > counterpart:
> > 
> > 	void t1_interrupt(void)
> > 	{
> > 		r0 = READ_ONCE(y);
> > 		smp_store_release(&x, 1);
> > 	}
> > 
> > 	void t1(void)
> > 	{
> > 		smp_store_release(&y, 1);
> > 	}
> > 
> > 	void t2(void)
> > 	{
> > 		r1 = smp_load_acquire(&x);
> > 		r2 = smp_load_acquire(&y);
> > 	}
> > 
> > On store-reordering architectures that implement smp_store_release()
> > as a memory-barrier instruction followed by a store, the interrupt could
> > arrive betweentimes in t1(), so that there would be no ordering between
> > t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> > in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.
> 
> This is disconcerting only if we assume that t1_interrupt() has to be
> executed by the same CPU as t1().  If the interrupt could be fielded by
> a different CPU then the paranoid outcome is perfectly understandable,
> even in an SC context.
> 
> So the question really should be limited to situations where a handler 
> is forced to execute in the context of a particular thread.  While 
> POSIX does allow such restrictions for user programs, I'm not aware of 
> any similar mechanism in the kernel.

Good point, and I was in fact assuming that t1() and t1_interrupt()
were executing on the same CPU.

This sort of thing happens naturally in the kernel when both t1()
and t1_interrupt() are accessing per-CPU variables.

							Thanx, Paul

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Paul E. McKenney]

On Sat, Oct 20, 2018 at 10:22:29PM +0200, Andrea Parri wrote:
> [...]
> 
> > The second (informal) litmus test has a more interesting Linux-kernel
> > counterpart:
> > 
> > 	void t1_interrupt(void)
> > 	{
> > 		r0 = READ_ONCE(y);
> > 		smp_store_release(&x, 1);
> > 	}
> > 
> > 	void t1(void)
> > 	{
> > 		smp_store_release(&y, 1);
> > 	}
> > 
> > 	void t2(void)
> > 	{
> > 		r1 = smp_load_acquire(&x);
> > 		r2 = smp_load_acquire(&y);
> > 	}
> > 
> > On store-reordering architectures that implement smp_store_release()
> > as a memory-barrier instruction followed by a store, the interrupt could
> > arrive betweentimes in t1(), so that there would be no ordering between
> > t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> > in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.
> 
> FWIW, I'd rather call "paranoid" the act of excluding such outcome ;-)
> but I admit that I've only run this test in *my mind*: in an SC world,
> 
>   CPU1				CPU2
> 
>   t1()
>     t1_interrupt()
>       r0 = READ_ONCE(y); // =0
> 				t2()
> 				  r1 = smp_load_acquire(&x); // =0
>       smp_store_release(&x, 1);
>     smp_store_release(&y, 1);
> 				  r2 = smp_load_acquire(&y); // =1

OK, so did I get the outcome messed up again?  :-/

							Thanx, Paul

> > So how paranoid should we be with respect to interrupt handlers for
> > smp_store_release(), smp_load_acquire(), and the various RMW atomic
> > operations that are sometimes implemented with separate memory-barrier
> > instructions?  ;-)
> 
> Good question! ;-)
> 
>   Andrea
> 
> 
> > 
> > 							Thanx, Paul
> > 
> 

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Alan Stern]

On Sat, 20 Oct 2018, Paul E. McKenney wrote:

> On Sat, Oct 20, 2018 at 10:22:29PM +0200, Andrea Parri wrote:
> > [...]
> > 
> > > The second (informal) litmus test has a more interesting Linux-kernel
> > > counterpart:
> > > 
> > > 	void t1_interrupt(void)
> > > 	{
> > > 		r0 = READ_ONCE(y);
> > > 		smp_store_release(&x, 1);
> > > 	}
> > > 
> > > 	void t1(void)
> > > 	{
> > > 		smp_store_release(&y, 1);
> > > 	}
> > > 
> > > 	void t2(void)
> > > 	{
> > > 		r1 = smp_load_acquire(&x);
> > > 		r2 = smp_load_acquire(&y);
> > > 	}
> > > 
> > > On store-reordering architectures that implement smp_store_release()
> > > as a memory-barrier instruction followed by a store, the interrupt could
> > > arrive betweentimes in t1(), so that there would be no ordering between
> > > t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> > > in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.
> > 
> > FWIW, I'd rather call "paranoid" the act of excluding such outcome ;-)
> > but I admit that I've only run this test in *my mind*: in an SC world,
> > 
> >   CPU1				CPU2
> > 
> >   t1()
> >     t1_interrupt()
> >       r0 = READ_ONCE(y); // =0
> > 				t2()
> > 				  r1 = smp_load_acquire(&x); // =0
> >       smp_store_release(&x, 1);
> >     smp_store_release(&y, 1);
> > 				  r2 = smp_load_acquire(&y); // =1
> 
> OK, so did I get the outcome messed up again?  :-/

Did you mean to say r0==1?  If so, the litmus test would be a little
clearer if you wrote t1() above t1_interrupt().  That would help to
cement the WRC pattern in the reader's mind.

In any case, perhaps this indicates the kernel should ensure that a
full memory barrier is executed when an interrupt occurs.  (Of course, 
the hardware may already do this for us, depending on the 
architecture.)

Alan

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Alan Stern]

On Sat, 20 Oct 2018, Paul E. McKenney wrote:

> On Sat, Oct 20, 2018 at 10:22:29PM +0200, Andrea Parri wrote:
> > [...]
> > 
> > > The second (informal) litmus test has a more interesting Linux-kernel
> > > counterpart:
> > > 
> > > 	void t1_interrupt(void)
> > > 	{
> > > 		r0 = READ_ONCE(y);
> > > 		smp_store_release(&x, 1);
> > > 	}
> > > 
> > > 	void t1(void)
> > > 	{
> > > 		smp_store_release(&y, 1);
> > > 	}
> > > 
> > > 	void t2(void)
> > > 	{
> > > 		r1 = smp_load_acquire(&x);
> > > 		r2 = smp_load_acquire(&y);
> > > 	}
> > > 
> > > On store-reordering architectures that implement smp_store_release()
> > > as a memory-barrier instruction followed by a store, the interrupt could
> > > arrive betweentimes in t1(), so that there would be no ordering between
> > > t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
> > > in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.
> > 
> > FWIW, I'd rather call "paranoid" the act of excluding such outcome ;-)
> > but I admit that I've only run this test in *my mind*: in an SC world,
> > 
> >   CPU1				CPU2
> > 
> >   t1()
> >     t1_interrupt()
> >       r0 = READ_ONCE(y); // =0
> > 				t2()
> > 				  r1 = smp_load_acquire(&x); // =0
> >       smp_store_release(&x, 1);
> >     smp_store_release(&y, 1);
> > 				  r2 = smp_load_acquire(&y); // =1
> 
> OK, so did I get the outcome messed up again?  :-/

Did you mean to say r0==1?  If so, the litmus test would be a little
clearer if you wrote t1() above t1_interrupt().  That would help to
cement the WRC pattern in the reader's mind.

In any case, perhaps this indicates the kernel should ensure that a
full memory barrier is executed when an interrupt occurs.  (Of course, 
the hardware may already do this for us, depending on the 
architecture.)

Alan

Re: Interrupts, smp_load_acquire(), smp_store_release(), etc.

[Eric W. Biederman]

"Paul E. McKenney" <paulmck@linux.ibm.com> writes:

> On Sat, Oct 20, 2018 at 04:18:37PM -0400, Alan Stern wrote:
>> On Sat, 20 Oct 2018, Paul E. McKenney wrote:
>> 
>> > The second (informal) litmus test has a more interesting Linux-kernel
>> > counterpart:
>> > 
>> > 	void t1_interrupt(void)
>> > 	{
>> > 		r0 = READ_ONCE(y);
>> > 		smp_store_release(&x, 1);
>> > 	}
>> > 
>> > 	void t1(void)
>> > 	{
>> > 		smp_store_release(&y, 1);
>> > 	}
>> > 
>> > 	void t2(void)
>> > 	{
>> > 		r1 = smp_load_acquire(&x);
>> > 		r2 = smp_load_acquire(&y);
>> > 	}
>> > 
>> > On store-reordering architectures that implement smp_store_release()
>> > as a memory-barrier instruction followed by a store, the interrupt could
>> > arrive betweentimes in t1(), so that there would be no ordering between
>> > t1_interrupt()'s store to x and t1()'s store to y.  This could (again,
>> > in paranoid theory) result in the outcome r0==0 && r1==0 && r2==1.
>> 
>> This is disconcerting only if we assume that t1_interrupt() has to be
>> executed by the same CPU as t1().  If the interrupt could be fielded by
>> a different CPU then the paranoid outcome is perfectly understandable,
>> even in an SC context.
>> 
>> So the question really should be limited to situations where a handler 
>> is forced to execute in the context of a particular thread.  While 
>> POSIX does allow such restrictions for user programs, I'm not aware of 
>> any similar mechanism in the kernel.

> Good point, and I was in fact assuming that t1() and t1_interrupt()
> were executing on the same CPU.
>
> This sort of thing happens naturally in the kernel when both t1()
> and t1_interrupt() are accessing per-CPU variables.

Interrupts have a cpumask of the cpus they may be dlievered on.

I believe networking does in fact have places where percpu actions
happen as well as interrupts pinned to a single cpu.  And yes I agree
percpu variables mean that you do not need to pin an interrupt to a
single cpu to cause this to happen.

Eric