for_each_cpu() is buggy for UP kernel?

for_each_cpu() is buggy for UP kernel?

[Dexuan Cui]

In include/linux/cpumask.h, for_each_cpu is defined like this for UP kernel (CONFIG_NR_CPUS=1):

#define for_each_cpu(cpu, mask)                 \
        for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)

Here 'mask' is ignored, but what if 'mask' contains 0 CPU? -- in this case, the for loop should not
run at all, but with the current code, we run the loop once with cpu==0.

I think I'm seeing a bug in my UP kernel that is caused by the buggy for_each_cpu():

in kernel/time/tick-broadcast.c: tick_handle_oneshot_broadcast(), tick_broadcast_oneshot_mask
contains 0 CPU, but due to the buggy for_each_cpu(), the variable 'next_event' is changed from
its default value KTIME_MAX to "next_event = td->evtdev->next_event"; as a result,
tick_handle_oneshot_broadcast () -> tick_broadcast_set_event() -> clockevents_program_event()
-> pit_next_event() is programming the PIT timer by accident, causing an interrupt storm of PIT
interrupts in some way: I'm seeing that the kernel is receiving ~8000 PIT interrupts per second for
1~5 minutes when the UP kernel boots, and it looks the kernel hangs, but in 1~5 minutes, finally
somehow the kernel can recover and boot up fine. But, occasionally, the kernel just hangs there
forever, receiving ~8000 PIT timers per second. 

With the below change in kernel/time/tick-broadcast.c, the interrupt storm will go away:

+#undef for_each_cpu
+#define for_each_cpu(cpu, mask)                        \
+       for ((cpu) = 0; (((cpu) < 1) && ((mask)[0].bits[0] & 1)); (cpu)++, (void)mask)

Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?

Thanks,
-- Dexuan

Re: for_each_cpu() is buggy for UP kernel?

[Andrew Morton]

On Wed, 9 May 2018 06:24:16 +0000 Dexuan Cui <decui@microsoft.com> wrote:

> In include/linux/cpumask.h, for_each_cpu is defined like this for UP kernel (CONFIG_NR_CPUS=1):
> 
> #define for_each_cpu(cpu, mask)                 \
>         for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)
> 
> Here 'mask' is ignored, but what if 'mask' contains 0 CPU? -- in this case, the for loop should not
> run at all, but with the current code, we run the loop once with cpu==0.
> 
> I think I'm seeing a bug in my UP kernel that is caused by the buggy for_each_cpu():
> 
> in kernel/time/tick-broadcast.c: tick_handle_oneshot_broadcast(), tick_broadcast_oneshot_mask
> contains 0 CPU, but due to the buggy for_each_cpu(), the variable 'next_event' is changed from
> its default value KTIME_MAX to "next_event = td->evtdev->next_event"; as a result,
> tick_handle_oneshot_broadcast () -> tick_broadcast_set_event() -> clockevents_program_event()
> -> pit_next_event() is programming the PIT timer by accident, causing an interrupt storm of PIT
> interrupts in some way: I'm seeing that the kernel is receiving ~8000 PIT interrupts per second for
> 1~5 minutes when the UP kernel boots, and it looks the kernel hangs, but in 1~5 minutes, finally
> somehow the kernel can recover and boot up fine. But, occasionally, the kernel just hangs there
> forever, receiving ~8000 PIT timers per second. 
> 
> With the below change in kernel/time/tick-broadcast.c, the interrupt storm will go away:
> 
> +#undef for_each_cpu
> +#define for_each_cpu(cpu, mask)                        \
> +       for ((cpu) = 0; (((cpu) < 1) && ((mask)[0].bits[0] & 1)); (cpu)++, (void)mask)
> 
> Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?

I think so, yes.  That might reveal new peculiarities, but such is life.

I guess we should use bitmap_empty() rather than open-coding it.

Re: for_each_cpu() is buggy for UP kernel?

[Thomas Gleixner]

On Wed, 9 May 2018, Andrew Morton wrote:

> On Wed, 9 May 2018 06:24:16 +0000 Dexuan Cui <decui@microsoft.com> wrote:
> 
> > In include/linux/cpumask.h, for_each_cpu is defined like this for UP kernel (CONFIG_NR_CPUS=1):
> > 
> > #define for_each_cpu(cpu, mask)                 \
> >         for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)
> > 
> > Here 'mask' is ignored, but what if 'mask' contains 0 CPU? -- in this case, the for loop should not
> > run at all, but with the current code, we run the loop once with cpu==0.
> > 
> > I think I'm seeing a bug in my UP kernel that is caused by the buggy for_each_cpu():
> > 
> > in kernel/time/tick-broadcast.c: tick_handle_oneshot_broadcast(), tick_broadcast_oneshot_mask
> > contains 0 CPU, but due to the buggy for_each_cpu(), the variable 'next_event' is changed from
> > its default value KTIME_MAX to "next_event = td->evtdev->next_event"; as a result,
> > tick_handle_oneshot_broadcast () -> tick_broadcast_set_event() -> clockevents_program_event()
> > -> pit_next_event() is programming the PIT timer by accident, causing an interrupt storm of PIT
> > interrupts in some way: I'm seeing that the kernel is receiving ~8000 PIT interrupts per second for
> > 1~5 minutes when the UP kernel boots, and it looks the kernel hangs, but in 1~5 minutes, finally
> > somehow the kernel can recover and boot up fine. But, occasionally, the kernel just hangs there
> > forever, receiving ~8000 PIT timers per second. 
> > 
> > With the below change in kernel/time/tick-broadcast.c, the interrupt storm will go away:
> > 
> > +#undef for_each_cpu
> > +#define for_each_cpu(cpu, mask)                        \
> > +       for ((cpu) = 0; (((cpu) < 1) && ((mask)[0].bits[0] & 1)); (cpu)++, (void)mask)
> > 
> > Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?
> 
> I think so, yes.  That might reveal new peculiarities, but such is life.
> 
> I guess we should use bitmap_empty() rather than open-coding it.

Agreed.

FWIW, this had been discussed before, but there was no real conclusion:

  https://lkml.kernel.org/r/alpine.DEB.2.20.1709161850010.2105@nanos

Thanks,

	tglx

Re: for_each_cpu() is buggy for UP kernel?

[Linus Torvalds]

On Tue, May 8, 2018 at 11:24 PM Dexuan Cui <decui@microsoft.com> wrote:

> Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?

As Thomas points out, this has come up before.

One of the issues is historical - we tried very hard to make the SMP code
not cause code generation problems for UP, and part of that was just that
all these loops were literally designed to entirely go away under UP. It
still *looks* syntactically like a loop, but an optimizing compiler will
see that there's nothing there, and "for_each_cpu(...) x" essentially just
turns into "x" on UP.  An empty mask simply generally doesn't make sense,
since opn UP you also don't have any masking of CPU ops, so the mask is
ignored, and that helps the code generation immensely.

If you have to load and test the mask, you immediately lose out badly in
code generation.

So honestly, I'd really prefer to keep our current behavior. Perhaps with a
debug option that actually tests (on SMP - because that's what every
developer is actually _using_ these days) that the mask isn't empty. But
I'm not sure that would find this case, since presumably on SMP it might
never be empty.

Now, there is likely a fairly good argument that UP is getting _so_
uninteresting that we shouldn't even worry about code generation. But the
counter-argument to that is that if people are using UP in this day and
age, they probably are using some really crappy hardware that needs all the
help it can get.

At least for now, I'd rather have this inconsistency, because it really
makes a surprisingly *big* difference in code generation.  From the little
test I just did, adding that mask testing to a *single* case of
for_each_cpu() added 20 instructions.  I didn't look at exactly why that
happened (because the code generation was so radically different), but it
was very noticeable. I used your macro replacement in kernel/taskstats.c in
case you want to try to dig into what happened, but I'm not surprised. It
really turns an unconditional trivial loop into a much more complex thing
that needs to look at and test a value that we didn't care about before.

Maybe we should introduce a "for_each_cpu_maybe_empty()" helper for cases
like this?

                    Linus

Re: for_each_cpu() is buggy for UP kernel?

[Dmitry Vyukov]

On Sun, May 13, 2018 at 8:21 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Tue, May 8, 2018 at 11:24 PM Dexuan Cui <decui@microsoft.com> wrote:
>
>> Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?
>
> As Thomas points out, this has come up before.
>
> One of the issues is historical - we tried very hard to make the SMP code
> not cause code generation problems for UP, and part of that was just that
> all these loops were literally designed to entirely go away under UP. It
> still *looks* syntactically like a loop, but an optimizing compiler will
> see that there's nothing there, and "for_each_cpu(...) x" essentially just
> turns into "x" on UP.  An empty mask simply generally doesn't make sense,
> since opn UP you also don't have any masking of CPU ops, so the mask is
> ignored, and that helps the code generation immensely.
>
> If you have to load and test the mask, you immediately lose out badly in
> code generation.
>
> So honestly, I'd really prefer to keep our current behavior. Perhaps with a
> debug option that actually tests (on SMP - because that's what every
> developer is actually _using_ these days) that the mask isn't empty. But
> I'm not sure that would find this case, since presumably on SMP it might
> never be empty.

This looks like the problem automated testing traditionally and
effectively solves. If UP is an important config, there must be
automated pre/post commit checks for this.

RE: for_each_cpu() is buggy for UP kernel?

[Dexuan Cui]

> From: Linus Torvalds <torvalds@linux-foundation.org>
> Sent: Sunday, May 13, 2018 11:22
> On Tue, May 8, 2018 at 11:24 PM Dexuan Cui <decui@microsoft.com> wrote:
> 
> > Should we fix the for_each_cpu() in include/linux/cpumask.h for UP?
> 
> As Thomas points out, this has come up before.
> 
> One of the issues is historical - we tried very hard to make the SMP code
> not cause code generation problems for UP, and part of that was just that
> all these loops were literally designed to entirely go away under UP. It
> still *looks* syntactically like a loop, but an optimizing compiler will
> see that there's nothing there, and "for_each_cpu(...) x" essentially just
> turns into "x" on UP.  An empty mask simply generally doesn't make sense,
> since opn UP you also don't have any masking of CPU ops, so the mask is
> ignored, and that helps the code generation immensely.
> 
> If you have to load and test the mask, you immediately lose out badly in
> code generation.
Thank you all for the insights and the detailed background introduction!
 
> So honestly, I'd really prefer to keep our current behavior. Perhaps with a
> debug option that actually tests (on SMP - because that's what every
> developer is actually _using_ these days) that the mask isn't empty. But
> I'm not sure that would find this case, since presumably on SMP it might
> never be empty.
I agree.

> Now, there is likely a fairly good argument that UP is getting _so_
> uninteresting that we shouldn't even worry about code generation. But the
> counter-argument to that is that if people are using UP in this day and
> age, they probably are using some really crappy hardware that needs all the
> help it can get.
FWIW, I happened to find this issue in a SMP virtual machine, but the kernel
from a customer was built with CONFIG_SMP disabled. After spending 1 day
debugging the strange boot-up delay, which was caused by the unexpected
PIT interrupt storm, I finally tracked it down to the UP version of for_each_cpu().

The function exposing the issue is kernel/time/tick-broadcast.c:
tick_handle_oneshot_broadcast().

If you're OK with the below fix (not tested yet), I'll submit a patch for it:

--- a/kernel/time/tick-broadcast.c
+++ b/kernel/time/tick-broadcast.c
@@ -616,6 +616,10 @@ static void tick_handle_oneshot_broadcast(struct clock_event_device *dev)
        now = ktime_get();
        /* Find all expired events */
        for_each_cpu(cpu, tick_broadcast_oneshot_mask) {
+#ifndef CONFIG_SMP
+               if (cpumask_empty(tick_broadcast_oneshot_mask))
+                       break;
+#endif
                td = &per_cpu(tick_cpu_device, cpu);
                if (td->evtdev->next_event <= now) {
                        cpumask_set_cpu(cpu, tmpmask); 

> At least for now, I'd rather have this inconsistency, because it really
> makes a surprisingly *big* difference in code generation.  From the little
> test I just did, adding that mask testing to a *single* case of
> for_each_cpu() added 20 instructions.  I didn't look at exactly why that
> happened (because the code generation was so radically different), but it
> was very noticeable. I used your macro replacement in kernel/taskstats.c in
> case you want to try to dig into what happened, but I'm not surprised. It
> really turns an unconditional trivial loop into a much more complex thing
> that needs to look at and test a value that we didn't care about before.
I agree.

 
> Maybe we should introduce a "for_each_cpu_maybe_empty()" helper for
> cases  like this?
>                     Linus
Sounds like a good idea.

Thanks,
-- Dexuan

Re: for_each_cpu() is buggy for UP kernel?

[Linus Torvalds]

On Mon, May 14, 2018 at 8:02 PM Dexuan Cui <decui@microsoft.com> wrote:

> If you're OK with the below fix (not tested yet), I'll submit a patch for
it:

> --- a/kernel/time/tick-broadcast.c
> +++ b/kernel/time/tick-broadcast.c
> @@ -616,6 +616,10 @@ static void tick_handle_oneshot_broadcast(struct
clock_event_device *dev)
>          now = ktime_get();
>          /* Find all expired events */
>          for_each_cpu(cpu, tick_broadcast_oneshot_mask) {
> +#ifndef CONFIG_SMP
> +               if (cpumask_empty(tick_broadcast_oneshot_mask))
> +                       break;
> +#endif

I'm certainly ok with this. It's hacky, but maybe being explicitly hacky is
good to "document" this gotcha.

And I really do agree that this special UP case is nasty nasty and much too
subtle, and I hope that some day we won't care about UP at all, and maybe
kill it, or maybe just make for_each_cpu() generate the extra code to have
the actual same semantics as the SMP case.

                  Linus

[PATCH] tick/broadcast: Use for_each_cpu() specially on UP kernels

[Dexuan Cui]

for_each_cpu() unintuitively reports CPU0 as set independent of the actual
cpumask content on UP kernels. This causes an unexpected PIT interrupt
storm on a UP kernel running in an SMP virtual machine on Hyper-V, and as
a result, the virtual machine can suffer from a strange random delay of 1~20
minutes during boot-up, and sometimes it can hang forever.

Link: https://lkml.org/lkml/2018/5/9/63
Link: https://lkml.org/lkml/2018/5/15/747
Signed-off-by: Dexuan Cui <decui@microsoft.com>
Cc: stable@vger.kernel.org
---

Some part of the changelog and comments are copied from 
Thomas Gleixner's 115ef3b7e61a ("watchdog/hardlockup/perf: Cure UP damage") :-)

 kernel/time/tick-broadcast.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/kernel/time/tick-broadcast.c b/kernel/time/tick-broadcast.c
index b398c2e..2fc59ad 100644
--- a/kernel/time/tick-broadcast.c
+++ b/kernel/time/tick-broadcast.c
@@ -612,6 +612,14 @@ static void tick_handle_oneshot_broadcast(struct clock_event_device *dev)
 	now = ktime_get();
 	/* Find all expired events */
 	for_each_cpu(cpu, tick_broadcast_oneshot_mask) {
+#ifndef CONFIG_SMP
+		/*
+		 * Required because for_each_cpu() reports unconditionally
+		 * CPU0 as set on UP kernels.
+		 */
+		if (cpumask_empty(tick_broadcast_oneshot_mask))
+			break;
+#endif
 		td = &per_cpu(tick_cpu_device, cpu);
 		if (td->evtdev->next_event <= now) {
 			cpumask_set_cpu(cpu, tmpmask);
-- 
2.7.4

RE: for_each_cpu() is buggy for UP kernel?

[Dexuan Cui]

> From: Linus Torvalds <torvalds@linux-foundation.org>
> Sent: Tuesday, May 15, 2018 10:22
> To: Dexuan Cui <decui@microsoft.com>
> 
> On Mon, May 14, 2018 at 8:02 PM Dexuan Cui <decui@microsoft.com> wrote:
> 
> > If you're OK with the below fix (not tested yet), I'll submit a patch for it:
> 
> > --- a/kernel/time/tick-broadcast.c
> > +++ b/kernel/time/tick-broadcast.c
> > @@ -616,6 +616,10 @@ static void tick_handle_oneshot_broadcast(struct
> clock_event_device *dev)
> >          now = ktime_get();
> >          /* Find all expired events */
> >          for_each_cpu(cpu, tick_broadcast_oneshot_mask) {
> > +#ifndef CONFIG_SMP
> > +               if (cpumask_empty(tick_broadcast_oneshot_mask))
> > +                       break;
> > +#endif
> 
> I'm certainly ok with this. It's hacky, but maybe being explicitly hacky is
> good to "document" this gotcha.
> 
> And I really do agree that this special UP case is nasty nasty and much too
> subtle, and I hope that some day we won't care about UP at all, and maybe
> kill it, or maybe just make for_each_cpu() generate the extra code to have
> the actual same semantics as the SMP case.
> 
>                   Linus

Thanks! I submitted the patch just now: https://lkml.org/lkml/2018/5/15/866 

Thanks,
-- Dexuan

[tip:timers/urgent] tick/broadcast: Use for_each_cpu() specially on UP kernels

[tip-bot for Dexuan Cui]

Commit-ID:  5596fe34495cf0f645f417eb928ef224df3e3cb4
Gitweb:     https://git.kernel.org/tip/5596fe34495cf0f645f417eb928ef224df3e3cb4
Author:     Dexuan Cui <decui@microsoft.com>
AuthorDate: Tue, 15 May 2018 19:52:50 +0000
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Tue, 15 May 2018 22:45:54 +0200

tick/broadcast: Use for_each_cpu() specially on UP kernels

for_each_cpu() unintuitively reports CPU0 as set independent of the actual
cpumask content on UP kernels. This causes an unexpected PIT interrupt
storm on a UP kernel running in an SMP virtual machine on Hyper-V, and as
a result, the virtual machine can suffer from a strange random delay of 1~20
minutes during boot-up, and sometimes it can hang forever.

Protect if by checking whether the cpumask is empty before entering the
for_each_cpu() loop.

[ tglx: Use !IS_ENABLED(CONFIG_SMP) instead of #ifdeffery ]

Signed-off-by: Dexuan Cui <decui@microsoft.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Josh Poulson <jopoulso@microsoft.com>
Cc: "Michael Kelley (EOSG)" <Michael.H.Kelley@microsoft.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: stable@vger.kernel.org
Cc: Rakib Mullick <rakib.mullick@gmail.com>
Cc: Jork Loeser <Jork.Loeser@microsoft.com>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: KY Srinivasan <kys@microsoft.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Alexey Dobriyan <adobriyan@gmail.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Link: https://lkml.kernel.org/r/KL1P15301MB000678289FE55BA365B3279ABF990@KL1P15301MB0006.APCP153.PROD.OUTLOOK.COM
Link: https://lkml.kernel.org/r/KL1P15301MB0006FA63BC22BEB64902EAA0BF930@KL1P15301MB0006.APCP153.PROD.OUTLOOK.COM
---
 kernel/time/tick-broadcast.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/kernel/time/tick-broadcast.c b/kernel/time/tick-broadcast.c
index b398c2ea69b2..aa2094d5dd27 100644
--- a/kernel/time/tick-broadcast.c
+++ b/kernel/time/tick-broadcast.c
@@ -612,6 +612,14 @@ static void tick_handle_oneshot_broadcast(struct clock_event_device *dev)
 	now = ktime_get();
 	/* Find all expired events */
 	for_each_cpu(cpu, tick_broadcast_oneshot_mask) {
+		/*
+		 * Required for !SMP because for_each_cpu() reports
+		 * unconditionally CPU0 as set on UP kernels.
+		 */
+		if (!IS_ENABLED(CONFIG_SMP) &&
+		    cpumask_empty(tick_broadcast_oneshot_mask))
+			break;
+
 		td = &per_cpu(tick_cpu_device, cpu);
 		if (td->evtdev->next_event <= now) {
 			cpumask_set_cpu(cpu, tmpmask);