Preventing IPI sending races in arch code

Preventing IPI sending races in arch code

[Vineet Gupta]

Hi,

I've been looking into cleaning up bitrot in ARC SMP support. Unlike some other
arches/platforms, we don't have per-msg-type IRQ, so the actual msg (say cross
function call) corresponding to IPI needs to be encoded in a per-cpu word (1 bit
per msg type) before kicking the IPI.

The current code (indicative below) is completely bonkers as it calls set_bit w/o
any protection whatsoever, clearly racy in case of multiple senders, where
receiver could end up NOT seeing one of the writes.

ipi_send_msg(cpu, msg-type)
{
   struct ipi_data *ipi_data = &per_cpu(ipi_data, cpu);

   local_irq_save();
   set_bit(msg-type, &ipi_data->bits)
   plat_smp_ops.ipi_send(cpumask)
   local_irq_restore();
}

Adding a spinlock here would serialize the sending part, but I still see issue in
receiver. Upon receipt of First IPI, the msg holding word will be atomically
exchanged with 0, so 2nd IPI will not see any msg in the word. Augmenting with an
atomic counter would only help detect the issue - but I don't see how it will help
elide the issue.

Does that mean w/o proper hardware assist (i.e. IRQ providing the msg id
indication), the race, however small, remains ?

Comments much appreciated !

-Vineet

Re: Preventing IPI sending races in arch code

[Peter Zijlstra]

On Mon, Nov 25, 2013 at 04:22:18PM +0530, Vineet Gupta wrote:
> Hi,
> 
> I've been looking into cleaning up bitrot in ARC SMP support. Unlike some other
> arches/platforms, we don't have per-msg-type IRQ, so the actual msg (say cross
> function call) corresponding to IPI needs to be encoded in a per-cpu word (1 bit
> per msg type) before kicking the IPI.
> 
> The current code (indicative below) is completely bonkers as it calls set_bit w/o
> any protection whatsoever, clearly racy in case of multiple senders, where
> receiver could end up NOT seeing one of the writes.
> 
> ipi_send_msg(cpu, msg-type)
> {
>    struct ipi_data *ipi_data = &per_cpu(ipi_data, cpu);
> 
>    local_irq_save();
>    set_bit(msg-type, &ipi_data->bits)
>    plat_smp_ops.ipi_send(cpumask)
>    local_irq_restore();
> }
> 
> Adding a spinlock here would serialize the sending part, but I still see issue in
> receiver. Upon receipt of First IPI, the msg holding word will be atomically
> exchanged with 0, so 2nd IPI will not see any msg in the word. Augmenting with an
> atomic counter would only help detect the issue - but I don't see how it will help
> elide the issue.
> 
> Does that mean w/o proper hardware assist (i.e. IRQ providing the msg id
> indication), the race, however small, remains ?

You can use cmpxchg to set the bit, and in case the previous value
wasn't 0 not send a second IPI.

Re: Preventing IPI sending races in arch code

[Vineet Gupta]

On 11/25/2013 04:30 PM, Peter Zijlstra wrote:
> On Mon, Nov 25, 2013 at 04:22:18PM +0530, Vineet Gupta wrote:
>> Hi,
>>
>> I've been looking into cleaning up bitrot in ARC SMP support. Unlike some other
>> arches/platforms, we don't have per-msg-type IRQ, so the actual msg (say cross
>> function call) corresponding to IPI needs to be encoded in a per-cpu word (1 bit
>> per msg type) before kicking the IPI.
>>
>> The current code (indicative below) is completely bonkers as it calls set_bit w/o
>> any protection whatsoever, clearly racy in case of multiple senders, where
>> receiver could end up NOT seeing one of the writes.
>>
>> ipi_send_msg(cpu, msg-type)
>> {
>>    struct ipi_data *ipi_data = &per_cpu(ipi_data, cpu);
>>
>>    local_irq_save();
>>    set_bit(msg-type, &ipi_data->bits)
>>    plat_smp_ops.ipi_send(cpumask)
>>    local_irq_restore();
>> }
>>
>> Adding a spinlock here would serialize the sending part, but I still see issue in
>> receiver. Upon receipt of First IPI, the msg holding word will be atomically
>> exchanged with 0, so 2nd IPI will not see any msg in the word. Augmenting with an
>> atomic counter would only help detect the issue - but I don't see how it will help
>> elide the issue.
>>
>> Does that mean w/o proper hardware assist (i.e. IRQ providing the msg id
>> indication), the race, however small, remains ?
> 
> You can use cmpxchg to set the bit, and in case the previous value
> wasn't 0 not send a second IPI.
> 

Thx Peter, that'll do it.

While we are at it, I wanted to confirm another potential race (ARC/blackfin..)
The IPI handler clears the interrupt before atomically-read-n-clear the msg word.

do_IPI
   plat_smp_ops.ipi_clear(irq);
   while ((pending = xchg(&ipi_data->bits, 0) != 0)
      find_next_bit(....)
      switch(next-msg)

Depending on arch this could lead to an immediate IPI interrupt, and again
ipi_data->bits could get out of syn with IPI senders. IMO the while loop is
completely useless specially if IPIs are not coalesced in h/w. And we need to move
the xchg ahead of ACK'ing the IPI

do_IPI
   pending = xchg(&ipi_data->bits, 0);
   plat_smp_ops.ipi_clear(irq);
   while (ffs....)
      switch(next-msg)
      ...

Does that look sane to you.

Thx,
-Vineet

Re: Preventing IPI sending races in arch code

[Peter Zijlstra]

On Mon, Nov 25, 2013 at 05:00:18PM +0530, Vineet Gupta wrote:
> While we are at it, I wanted to confirm another potential race (ARC/blackfin..)
> The IPI handler clears the interrupt before atomically-read-n-clear the msg word.
> 
> do_IPI
>    plat_smp_ops.ipi_clear(irq);
>    while ((pending = xchg(&ipi_data->bits, 0) != 0)
>       find_next_bit(....)
>       switch(next-msg)
> 
> Depending on arch this could lead to an immediate IPI interrupt, and again
> ipi_data->bits could get out of syn with IPI senders. 

I'm obviously lacking in platform knowledge here, what does that
ipi_clear() actually do? Tell the platform the interrupt has arrived and
it can stop asserting the line?

So sure, then someone can again assert the interrupt, but given we just
established a protocol for raising the thing; namely something like
this:

void arch_send_ipi(int cpu, int type)
{
  u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
  u32 new, old;

  do {
  	new = old = *pending_ptr;
	new |= 1U << type;
  } while (cmpxchg(pending_ptr, old, new) != old)

  if (!old) /* only raise the actual IPI if we set the first bit */
  	raise_ipi(cpu);
}

Who would re-assert it if we have !0 pending?

Also, the above can be thought of as a memory ordering issue:

  STORE pending
  MB /* implied by cmpxchg */
  STORE ipi /* raise the actual thing */

In that case the other end must be:

  LOAD ipi
  MB /* implied by xchg */
  LOAD pending

Which is what your code seems to do.

> IMO the while loop is
> completely useless specially if IPIs are not coalesced in h/w. 

Agreed, the while loops seems superfluous.

> And we need to move
> the xchg ahead of ACK'ing the IPI
> 
> do_IPI
>    pending = xchg(&ipi_data->bits, 0);
>    plat_smp_ops.ipi_clear(irq);
>    while (ffs....)
>       switch(next-msg)
>       ...
> 
> Does that look sane to you.

This I'm not at all certain of; continuing with the memory order analogy
this would allow for the case where we see 0 pending, set a bit, try and
raise the interrupt but then do not because its already assert.

And since you just removed the while() loop, we'll be left with a !0
pending vector and nobody processing it.

Re: Preventing IPI sending races in arch code

[Vineet Gupta]

On 11/25/2013 05:57 PM, Peter Zijlstra wrote:
> On Mon, Nov 25, 2013 at 05:00:18PM +0530, Vineet Gupta wrote:
>> While we are at it, I wanted to confirm another potential race (ARC/blackfin..)
>> The IPI handler clears the interrupt before atomically-read-n-clear the msg word.
>>
>> do_IPI
>>    plat_smp_ops.ipi_clear(irq);
>>    while ((pending = xchg(&ipi_data->bits, 0) != 0)
>>       find_next_bit(....)
>>       switch(next-msg)
>>
>> Depending on arch this could lead to an immediate IPI interrupt, and again
>> ipi_data->bits could get out of syn with IPI senders. 
> I'm obviously lacking in platform knowledge here, what does that
> ipi_clear() actually do? Tell the platform the interrupt has arrived and
> it can stop asserting the line?

Correct.

> So sure, then someone can again assert the interrupt, but given we just
> established a protocol for raising the thing; namely something like
> this:
>
> void arch_send_ipi(int cpu, int type)
> {
>   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
>   u32 new, old;
>
>   do {
>   	new = old = *pending_ptr;
> 	new |= 1U << type;
>   } while (cmpxchg(pending_ptr, old, new) != old)
>
>   if (!old) /* only raise the actual IPI if we set the first bit */
>   	raise_ipi(cpu);
> }
>
> Who would re-assert it if we have !0 pending?

I see your point. So in receiver, it is OK to de-assert the IPI before processing
the msg itself.

Actually your code seems to be optimizing away asserting an IPI, if sender already
had a pending msg (assuming we retain the xchg loop in receiver). Was that an
intended optimization - or just a side effect of your code ;-)

Before reading ur email I was coding something like below:

void arch_send_ipi(int cpu, int type)
{
  u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);

  while (cmpxchg(pending_ptr, 0, 1 << type) != 0)
	cpu_relax();

  raise_ipi(cpu);
}

But obviously your version is nicer due to optimization, unless I'm over-analyzing it.


> Also, the above can be thought of as a memory ordering issue:
>
>   STORE pending
>   MB /* implied by cmpxchg */
>   STORE ipi /* raise the actual thing */
>
> In that case the other end must be:
>
>   LOAD ipi
>   MB /* implied by xchg */
>   LOAD pending
>
> Which is what your code seems to do.

...

>
>> IMO the while loop is
>> completely useless specially if IPIs are not coalesced in h/w. 
> Agreed, the while loops seems superfluous.

Not with your version of sender, since we need it as described above.

>> And we need to move
>> the xchg ahead of ACK'ing the IPI
>>
>> do_IPI
>>    pending = xchg(&ipi_data->bits, 0);
>>    plat_smp_ops.ipi_clear(irq);
>>    while (ffs....)
>>       switch(next-msg)
>>       ...
>>
>> Does that look sane to you.
> This I'm not at all certain of; continuing with the memory order analogy
> this would allow for the case where we see 0 pending, set a bit, try and
> raise the interrupt but then do not because its already assert.
>
> And since you just removed the while() loop, we'll be left with a !0
> pending vector and nobody processing it.

Right we need it with ur version of sender. Bit don't with my simplistic one.

-Vineet

Re: Preventing IPI sending races in arch code

[Peter Zijlstra]

On Mon, Nov 25, 2013 at 01:35:38PM +0000, Vineet Gupta wrote:
> On 11/25/2013 05:57 PM, Peter Zijlstra wrote:

> > So sure, then someone can again assert the interrupt, but given we just
> > established a protocol for raising the thing; namely something like
> > this:
> >
> > void arch_send_ipi(int cpu, int type)
> > {
> >   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
> >   u32 new, old;
> >
> >   do {
> >   	new = old = *pending_ptr;
> > 	new |= 1U << type;
> >   } while (cmpxchg(pending_ptr, old, new) != old)
> >
> >   if (!old) /* only raise the actual IPI if we set the first bit */
> >   	raise_ipi(cpu);
> > }
> >
> > Who would re-assert it if we have !0 pending?
> 
> I see your point. So in receiver, it is OK to de-assert the IPI before processing
> the msg itself.
> 
> Actually your code seems to be optimizing away asserting an IPI, if sender already
> had a pending msg (assuming we retain the xchg loop in receiver). Was that an
> intended optimization - or just a side effect of your code ;-)

No, full intention. As you mentioned you wanted to avoid sending IPIs
where none were needed.

> >> IMO the while loop is
> >> completely useless specially if IPIs are not coalesced in h/w. 
> > Agreed, the while loops seems superfluous.
> 
> Not with your version of sender, since we need it as described above.

No, even with my code; the receiving end should look like:

void handle_ipi(struct pt_regs *regs)
{
	u32 pending;

	ipi_clear(irq);

	pending = xchg(this_cpu_ptr(ipi_bits), 0);

	while (pending) {
		bit = ffs(pending);

		/* handle bit */

		pending &= ~(1U << bit);
	}
}

So while it does have a while() loop, it only does a single xchg().

The version you showed before had the xchg() in the loop, that is not
required.

Re: Preventing IPI sending races in arch code

[Peter Zijlstra]

On Mon, Nov 25, 2013 at 01:35:38PM +0000, Vineet Gupta wrote:
> On 11/25/2013 05:57 PM, Peter Zijlstra wrote:

> > So sure, then someone can again assert the interrupt, but given we just
> > established a protocol for raising the thing; namely something like
> > this:
> >
> > void arch_send_ipi(int cpu, int type)
> > {
> >   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
> >   u32 new, old;
> >
> >   do {
> >   	new = old = *pending_ptr;
> > 	new |= 1U << type;
> >   } while (cmpxchg(pending_ptr, old, new) != old)
> >
> >   if (!old) /* only raise the actual IPI if we set the first bit */
> >   	raise_ipi(cpu);
> > }
> >
> > Who would re-assert it if we have !0 pending?
> 
> I see your point. So in receiver, it is OK to de-assert the IPI before processing
> the msg itself.
> 
> Actually your code seems to be optimizing away asserting an IPI, if sender already
> had a pending msg (assuming we retain the xchg loop in receiver). Was that an
> intended optimization - or just a side effect of your code ;-)

No, full intention. As you mentioned you wanted to avoid sending IPIs
where none were needed.

> >> IMO the while loop is
> >> completely useless specially if IPIs are not coalesced in h/w. 
> > Agreed, the while loops seems superfluous.
> 
> Not with your version of sender, since we need it as described above.

No, even with my code; the receiving end should look like:

void handle_ipi(struct pt_regs *regs)
{
	u32 pending;

	ipi_clear(irq);

	pending = xchg(this_cpu_ptr(ipi_bits), 0);

	while (pending) {
		bit = ffs(pending);

		/* handle bit */

		pending &= ~(1U << bit);
	}
}

So while it does have a while() loop, it only does a single xchg().

The version you showed before had the xchg() in the loop, that is not
required.

Re: Preventing IPI sending races in arch code

[Benjamin Herrenschmidt]

On Mon, 2013-11-25 at 13:35 +0000, Vineet Gupta wrote:

> Before reading ur email I was coding something like below:
> 
> void arch_send_ipi(int cpu, int type)
> {
>   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
> 
>   while (cmpxchg(pending_ptr, 0, 1 << type) != 0)
> 	cpu_relax();
> 
>   raise_ipi(cpu);
> }

So you would have blocked the sender while there was already
a pending IPI on the target ? Why ?

The optimization proposed by Peter is actually the only interesting
change here, without it the existing set_bit was perfectly fine.
Remember that set_bit is atomic.

Ben.

> But obviously your version is nicer due to optimization, unless I'm over-analyzing it.
> 
> 
> > Also, the above can be thought of as a memory ordering issue:
> >
> >   STORE pending
> >   MB /* implied by cmpxchg */
> >   STORE ipi /* raise the actual thing */
> >
> > In that case the other end must be:
> >
> >   LOAD ipi
> >   MB /* implied by xchg */
> >   LOAD pending
> >
> > Which is what your code seems to do.
> 
> ...
> 
> >
> >> IMO the while loop is
> >> completely useless specially if IPIs are not coalesced in h/w. 
> > Agreed, the while loops seems superfluous.
> 
> Not with your version of sender, since we need it as described above.
> 
> >> And we need to move
> >> the xchg ahead of ACK'ing the IPI
> >>
> >> do_IPI
> >>    pending = xchg(&ipi_data->bits, 0);
> >>    plat_smp_ops.ipi_clear(irq);
> >>    while (ffs....)
> >>       switch(next-msg)
> >>       ...
> >>
> >> Does that look sane to you.
> > This I'm not at all certain of; continuing with the memory order analogy
> > this would allow for the case where we see 0 pending, set a bit, try and
> > raise the interrupt but then do not because its already assert.
> >
> > And since you just removed the while() loop, we'll be left with a !0
> > pending vector and nobody processing it.
> 
> Right we need it with ur version of sender. Bit don't with my simplistic one.
> 
> -Vineet
> --
> To unsubscribe from this list: send the line "unsubscribe linux-arch" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Preventing IPI sending races in arch code

[Vineet Gupta]

On 11/26/2013 01:21 AM, Benjamin Herrenschmidt wrote:
> On Mon, 2013-11-25 at 13:35 +0000, Vineet Gupta wrote:
> 
>> Before reading ur email I was coding something like below:
>>
>> void arch_send_ipi(int cpu, int type)
>> {
>>   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
>>
>>   while (cmpxchg(pending_ptr, 0, 1 << type) != 0)
>> 	cpu_relax();
>>
>>   raise_ipi(cpu);
>> }
> 
> So you would have blocked the sender while there was already
> a pending IPI on the target ? Why ?

A simplistic (but non optimal) way to cater to the race where 2 senders try to
send the exact same msg to same receiver. Upon first IPI, receiver "consumes" the
msg (using xchg with 0) so the 2nd IPI seems "empty" i.e. no msg.


> The optimization proposed by Peter is actually the only interesting
> change here, without it the existing set_bit was perfectly fine.

I'm not sure, see below.

> Remember that set_bit is atomic.

Right, but the issue per-se is not clobbering of msg holder, but from POV of
receiver, seeming coalescing of 2 set_bit writes to msg holder.

core0		core1		core2

set_bit 1	
kick IPI-2	set_bit 1	IPI-0 received
		kick IPI-2	read+clear bit
				IPI-1 received
				no msg

-Vineet

Re: Preventing IPI sending races in arch code

[Benjamin Herrenschmidt]

On Tue, 2013-11-26 at 10:17 +0530, Vineet Gupta wrote:
> On 11/26/2013 01:21 AM, Benjamin Herrenschmidt wrote:
> > On Mon, 2013-11-25 at 13:35 +0000, Vineet Gupta wrote:
> > 
> >> Before reading ur email I was coding something like below:
> >>
> >> void arch_send_ipi(int cpu, int type)
> >> {
> >>   u32 *pending_ptr = per_cpu_ptr(ipi_bits, cpu);
> >>
> >>   while (cmpxchg(pending_ptr, 0, 1 << type) != 0)
> >> 	cpu_relax();
> >>
> >>   raise_ipi(cpu);
> >> }
> > 
> > So you would have blocked the sender while there was already
> > a pending IPI on the target ? Why ?
> 
> A simplistic (but non optimal) way to cater to the race where 2 senders try to
> send the exact same msg to same receiver. Upon first IPI, receiver "consumes" the
> msg (using xchg with 0) so the 2nd IPI seems "empty" i.e. no msg.

But there is no race...

> > The optimization proposed by Peter is actually the only interesting
> > change here, without it the existing set_bit was perfectly fine.
> 
> I'm not sure, see below.
> 
> > Remember that set_bit is atomic.
> 
> Right, but the issue per-se is not clobbering of msg holder, but from POV of
> receiver, seeming coalescing of 2 set_bit writes to msg holder.

That's fine. There's no expectation that N ipi_send_msg turn into N
messages received... it turns into at least one.

Just like MSIs or other edge interrupts

Cheers,
Ben.

> core0		core1		core2
> 
> set_bit 1	
> kick IPI-2	set_bit 1	IPI-0 received
> 		kick IPI-2	read+clear bit
> 				IPI-1 received
> 				no msg
> 
> -Vineet
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Preventing IPI sending races in arch code

[Vineet Gupta]

On 11/26/2013 10:41 AM, Benjamin Herrenschmidt wrote:
>> Right, but the issue per-se is not clobbering of msg holder, but from POV of
>> > receiver, seeming coalescing of 2 set_bit writes to msg holder.
> That's fine. There's no expectation that N ipi_send_msg turn into N
> messages received... it turns into at least one.

OK, I was not aware of that relaxation in semantics.

Thx,
-Vineet