Preventing IPI sending races in arch code

DISCUSSION Vineet Gupta 3 participants 10 messages Nov 25, 2013 – Nov 26, 2013 Generic include/asm header files

Share & tools

Vineet Gupta

author

2013-11-25 10:52 UTC #0 lore raw

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

Peter Zijlstra

2013-11-25 11:00 UTC #1 lore raw

Quoted 21 lines · 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();
}

Quoted 8 lines

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.

Vineet Gupta

author

2013-11-25 11:30 UTC #2 lore raw

Quoted 28 lines · Peter Zijlstra

Quoted 27 lines · 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.

Quoted 6 lines

Quoted 2 lines
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

Peter Zijlstra

2013-11-25 12:27 UTC #3 lore raw

Quoted 11 lines · Vineet Gupta

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.

Quoted 2 lines

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

Agreed, the while loops seems superfluous.

Quoted 11 lines

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.

Vineet Gupta

author

2013-11-25 13:35 UTC #4 lore raw

Quoted 10 lines · Peter Zijlstra

Quoted 9 lines · Vineet Gupta
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)

Quoted 5 lines

Quoted 2 lines
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.

Quoted 12 lines

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;

Quoted 7 lines

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

Quoted 13 lines

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.

...

Quoted 4 lines

Quoted 3 lines
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.

Quoted 10 lines

Quoted 10 lines
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)
      ...

Quoted 7 lines

Quoted 1 line
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

Peter Zijlstra

2013-11-25 13:57 UTC #5 lore raw

Quoted 20 lines · Vineet Gupta

Quoted 18 lines · Peter Zijlstra
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);
}

Quoted 8 lines

Quoted 1 line
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.

Quoted 5 lines

Quoted 3 lines
Quoted 2 lines
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.

Benjamin Herrenschmidt

2013-11-25 19:53 UTC #6 lore raw

In reply to Vineet Gupta

Quoted 11 lines · Vineet Gupta

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.

Quoted 51 lines

But obviously your version is nicer due to optimization, unless I'm over-analyzing it.
Quoted 13 lines
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.
...
Quoted 4 lines
Quoted 3 lines
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.
Quoted 10 lines
Quoted 10 lines
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)
      ...
Quoted 7 lines
Quoted 1 line
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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Vineet Gupta

author

2013-11-26 04:48 UTC #7 lore raw

Quoted 8 lines · Benjamin Herrenschmidt

Quoted 6 lines · Vineet Gupta
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);

Quoted 8 lines

Quoted 5 lines
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.

Quoted 2 lines

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.

Quoted 1 line

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

Benjamin Herrenschmidt

2013-11-26 05:12 UTC #8 lore raw

Quoted 15 lines · Vineet Gupta

Quoted 14 lines · Benjamin Herrenschmidt
Quoted 11 lines · Vineet Gupta
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);
}

Quoted 6 lines

Quoted 2 lines
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...

Quoted 9 lines

Quoted 2 lines
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.
Quoted 1 line
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.

Quoted 15 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Vineet Gupta

author

2013-11-26 06:35 UTC #9 lore raw

Quoted 4 lines · Benjamin Herrenschmidt

Quoted 2 lines
Right, but the issue per-se is not clobbering of msg holder, but from POV of
Quoted 1 line
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