sched,idle: need resched polling rework

Standardize the idle polling indicator to TIF_POLLING_NRFLAG such that both TIF_NEED_RESCHED and TIF_POLLING_NRFLAG are in the same word. This will allow us, using fetch_or(), to both set NEED_RESCHED and check for POLLING_NRFLAG in a single operation and avoid pointless wakeups.

Changing from the non-atomic thread_info::status flags to the atomic thread_info::flags shouldn't be a big issue since most polling state changes were followed/preceded by a full memory barrier anyway.

Cc Thomas Gleixner <[email protected]>

Cc Andy Lutomirski <[email protected]>

Cc Richard Henderson <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 arch/alpha/include/asm/thread_info.h |    4 ++--
 1 file changed, 2 inser

Standardize the idle polling indicator to TIF_POLLING_NRFLAG such that both TIF_NEED_RESCHED and TIF_POLLING_NRFLAG are in the same word. This will allow us, using fetch_or(), to both set NEED_RESCHED and check for POLLING_NRFLAG in a single operation and avoid pointless wakeups.

Changing from the non-atomic thread_info::status flags to the atomic thread_info::flags shouldn't be a big issue since most polling state changes were followed/preceded by a full memory barrier anyway.

Cc Thomas Gleixner <[email protected]>

Cc Andy Lutomirski <[email protected]>

Cc Chris Metcalf <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 arch/tile/include/asm/thread_info.h |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

It's unfortunate that you're rolling the fetch_or() unconditionally out of cmpxchg(), since some architectures (like tilegx) do have support for "fetchor" as a primitive atomic operation. Currently the tilegx fetchor is only exposed to architecture-independent code via set_bit() and test_and_set_bit(), but perhaps it's worth having an atomic_or() in atomic.h so architectures can choose to optimize it?

Because mwait_idle_with_hints() gets called from !idle context it must call current_clr_polling(). This however means that resched_task() is very likely to send an IPI even when we were polling:

CPU0 CPU1

if (current_set_polling_and_test())

    goto out;

__monitor(&ti->flags);
if (!need_resched())

    __mwait(eax, ecx);
					set_tsk_need_resched(p);
					smp_mb();
out:
  current_clr_polling();
					if (!tsk_is_polling(p))
					  smp_send_reschedule(cpu);

So while it is correct (extra IPIs aren't a problem, whereas a missed IPI would be) it is a performance problem (for some).

Avoid this issue by using fetch_or() to atomically set NEED_RESCHED and test if POLLING_NRFLAG is set.

Since a CPU stuck in mwait is unlikely to modify the flags word, contention on the cmpxchg is unlikely and thus we should mostly succeed in a single go.

Cc Thomas Gleixner <[email protected]>

Cc Andy Lutomirski <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 kernel/sched/core.c |   41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

kernel/sched/core.c +36 -5

@@ -505,6 +505,39 @@ static inline void init_hrtick(void)
 #endif	/* CONFIG_SCHED_HRTICK */
 
 /*
+ * cmpxchg based fetch_or, macro so it works for different integer types
+ */
+#define fetch_or(ptr, val)						\
+({	typeof(*(ptr)) __old, __val = *(ptr);				\
+ 	for (;;) {							\
+ 		__old = cmpxchg((ptr), __val, __val | (val));		\
+ 		if (__old == __val)					\
+ 			break;						\
+ 		__val = __old;						\
+ 	}								\
+ 	__old;								\
+})
+
+#ifdef TIF_POLLING_NRFLAG
+/*
+ * Atomically set TIF_NEED_RESCHED and test for TIF_POLLING_NRFLAG,
+ * this avoids any races wrt polling state changes and thereby avoids
+ * spurious IPIs.
+ */
+static bool set_nr_and_not_polling(struct task_struct *p)
+{
+	struct thread_info *ti = task_thread_info(p);
+	return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
+}
+#else
+static bool set_nr_and_not_polling(struct task_struct *p)
+{
+	set_tsk_need_resched(p);
+	return true;
+}
+#endif
+
+/*
  * resched_task - mark a task 'to be rescheduled now'.
  *
  * On UP this means the setting of the need_resched flag, on SMP it

@@ -520,17 +553,15 @@ void resched_task(struct task_struct *p)
 	if (test_tsk_need_resched(p))
 		return;
 
-	set_tsk_need_resched(p);
-
 	cpu = task_cpu(p);
+
 	if (cpu == smp_processor_id()) {
+		set_tsk_need_resched(p);
 		set_preempt_need_resched();
 		return;
 	}
 
-	/* NEED_RESCHED must be visible before we test polling */
-	smp_mb();
-	if (!tsk_is_polling(p))
+	if (set_nr_and_not_polling(p))
 		smp_send_reschedule(cpu);
 }
 

Because mwait_idle_with_hints() gets called from !idle context it must call current_clr_polling(). This however means that resched_task() is very likely to send an IPI even when we were polling:

CPU0 CPU1

if (current_set_polling_and_test())

    goto out;

__monitor(&ti->flags);
if (!need_resched())

    __mwait(eax, ecx);
                                        set_tsk_need_resched(p);
                                        smp_mb();
out:
  current_clr_polling();
                                        if (!tsk_is_polling(p))
                                          smp_send_reschedule(cpu);

So while it is correct (extra IPIs aren't a problem, whereas a missed IPI would be) it is a performance problem (for some).

Avoid this issue by using fetch_or() to atomically set NEED_RESCHED and test if POLLING_NRFLAG is set.

Since a CPU stuck in mwait is unlikely to modify the flags word, contention on the cmpxchg is unlikely and thus we should mostly succeed in a single go.

Cc Thomas Gleixner <[email protected]>

Cc Andy Lutomirski <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 kernel/sched/core.c |   41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

kernel/sched/core.c +13 -0

@@ -505,6 +505,39 @@ static inline void init_hrtick(void)
 #endif /* CONFIG_SCHED_HRTICK */
 
 /*
+ * cmpxchg based fetch_or, macro so it works for different integer types
+ */
+#define fetch_or(ptr, val)                                             \
+({     typeof(*(ptr)) __old, __val = *(ptr);                           \
+       for (;;) {                                                      \
+               __old = cmpxchg((ptr), __val, __val | (val));           \
+               if (__old == __val)                                     \
+                       break;                                          \
+               __val = __old;                                          \
+       }                                                               \
+       __old;                                                          \
+})
+

kernel/sched/core.c +13 -6

+}
+#else
+static bool set_nr_and_not_polling(struct task_struct *p)
+{
+       set_tsk_need_resched(p);
+       return true;
+}
+#endif
+
+/*
  * resched_task - mark a task 'to be rescheduled now'.
  *
  * On UP this means the setting of the need_resched flag, on SMP it

@@ -520,17 +553,15 @@ void resched_task(struct task_struct *p)
        if (test_tsk_need_resched(p))
                return;
 
-       set_tsk_need_resched(p);
-
        cpu = task_cpu(p);
+
        if (cpu == smp_processor_id()) {
+               set_tsk_need_resched(p);
                set_preempt_need_resched();
                return;
        }
 
-       /* NEED_RESCHED must be visible before we test polling */
-       smp_mb();
-       if (!tsk_is_polling(p))
+       if (set_nr_and_not_polling(p))
                smp_send_reschedule(cpu);
 }
 
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Hi Peter,

Quoted 1 line · Peter Zijlstra

+ return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);

This breaks the build on metag, and I suspect arm64 too:

kernel/sched/core.c In function ?set_nr_and_not_polling?:
kernel/sched/core.c +531 : error: ?_TIF_POLLING_NRFLAG? undeclared

since metag/arm64 define TIF_POLLING_NRFLAG but not _TIF_POLLING_NRFLAG. Could you please fix that prior to your patch to avoid breaking bisection?

BTW what is it that determines whether an arch needs TIF_POLLING_NRFLAG?

Quoted 4 lines · James Hogan

Quoted 1 line · Peter Zijlstra

+ return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);

This breaks the build on metag, and I suspect arm64 too:

Yep, I just got a patch for arm64.

Any SMP arch that has a polling idle function of any kind (including the default cpu_idle_poll()).

That said, even if that's true, not having TIF_POLLING_NRFLAG isn't fatal, just sub-optimal in that we'll send an unconditional IPI to wake the CPU even though its polling TIF_NEED_RESCHED and doesn't need anything other than that write to wake up.

Most archs have (x86) hlt or (arm) wfi like idle instructions, and if that is your only possible idle function, you'll require the interrupt to wake up and there's really no point to having the POLLING bit.

I wonder why we still need TIF_POLLING_NRFLAG for arm64. It was on arm until commit 16a8016372c42c7628eb (sanitize tsk_is_polling()). On arm64 we use wfi for idle or a firmware call but in both cases the assumption is that we need an interrupt for waking up.

So I think we should remove this macro for arm64.

Quoted 6 lines · Catalin Marinas

I wonder why we still need TIF_POLLING_NRFLAG for arm64. It was on arm until commit 16a8016372c42c7628eb (sanitize tsk_is_polling()). On arm64 we use wfi for idle or a firmware call but in both cases the assumption is that we need an interrupt for waking up.

So I think we should remove this macro for arm64.

Does ARM64 support idle=poll? If so, you could keep it for that, otherwise it does indeed appear to be pointless.

As to 32bit ARM, are there SMP chips which do not have WFI?

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Catalin Marinas

I wonder why we still need TIF_POLLING_NRFLAG for arm64. It was on arm until commit 16a8016372c42c7628eb (sanitize tsk_is_polling()). On arm64 we use wfi for idle or a firmware call but in both cases the assumption is that we need an interrupt for waking up.

So I think we should remove this macro for arm64.

Does ARM64 support idle=poll? If so, you could keep it for that, otherwise it does indeed appear to be pointless.

We don't support idle=poll either.

Quoted 1 line

As to 32bit ARM, are there SMP chips which do not have WFI?

No. WFI is even used for the secondary booting protocol (we need to send an IPI to get them going).

OK, so I'll queue a patch removing TIF_POLLING_NRFLAG for arm64.

Subject: arm64: Remove TIF_POLLING_NRFLAG
From: Peter Zijlstra <[email protected]>
Date: Fri May 9 19:04:00 CEST 2014

The only idle method for arm64 is WFI and it therefore unconditionally requires the reschedule interrupt when idle.

Suggested-by Catalin Marinas <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

Quoted 7 lines · Peter Zijlstra

Subject: arm64: Remove TIF_POLLING_NRFLAG
From: Peter Zijlstra <[email protected]>
Date: Fri May 9 19:04:00 CEST 2014

The only idle method for arm64 is WFI and it therefore unconditionally requires the reschedule interrupt when idle.

Quoted 2 lines

Suggested-by Catalin Marinas <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

There's a tag with my name already but just in case you need another:

Acked-by Catalin Marinas <[email protected]>

Quoted 6 lines · James Hogan

Hi Peter,

Quoted 1 line · Peter Zijlstra

+ return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);

This breaks the build on metag, and I suspect arm64 too:

Yep, I just got a patch for arm64.

Quoted 6 lines

kernel/sched/core.c In function ?set_nr_and_not_polling?:
kernel/sched/core.c +531 : error: ?_TIF_POLLING_NRFLAG? undeclared

since metag/arm64 define TIF_POLLING_NRFLAG but not _TIF_POLLING_NRFLAG. Could you please fix that prior to your patch to avoid breaking bisection?

Ingo, is there any git magic to make that happen? Can we have a tree with 2 patches (one for ARM64 and one for metag) before the sched/core tree?

Quoted 1 line

BTW what is it that determines whether an arch needs TIF_POLLING_NRFLAG?

Any SMP arch that has a polling idle function of any kind (including the default cpu_idle_poll()).

That said, even if that's true, not having TIF_POLLING_NRFLAG isn't fatal, just sub-optimal in that we'll send an unconditional IPI to wake the CPU even though its polling TIF_NEED_RESCHED and doesn't need anything other than that write to wake up.

Most archs have (x86) hlt or (arm) wfi like idle instructions, and if that is your only possible idle function, you'll require the interrupt to wake up and there's really no point to having the POLLING bit.

Lastly, having the POLLING bit and not needing it is similarly non-fatal.

From 15dd3f9cc18bdb1c8c4d2c395778421022250aa8 Mon Sep 17 00:00:00 2001

Most archs have (x86) hlt or (arm) wfi like idle instructions, and if that is your only possible idle function, you'll require the interrupt to wake up and there's really no point to having the POLLING bit.

Quoted 6 lines · Peter Zijlstra

Most archs have (x86) hlt or (arm) wfi like idle instructions, and if that is your only possible idle function, you'll require the interrupt to wake up and there's really no point to having the POLLING bit.

Lastly, having the POLLING bit and not needing it is similarly non-fatal.

Thanks. I think the flag can go for Metag then. I suggest the following patch.

From 15dd3f9cc18bdb1c8c4d2c395778421022250aa8 Mon Sep 17 00:00:00 2001
From: James Hogan <[email protected]>
Date: Fri, 9 May 2014 15:36:21 +0100
Subject: [PATCH] metag: Remove TIF_POLLING_NRFLAG

The Meta idle function jumps into the interrupt handler which efficiently blocks waiting for the next interrupt when it reads the interrupt status register (TXSTATI). No other (polling) idle functions can be used, therefore TIF_POLLING_NRFLAG is unnecessary, so lets remove it.

Quoted 3 lines · Peter Zijlstra

Most archs have (x86) hlt or (arm) wfi like idle instructions, and if that is your only possible idle function, you'll require the interrupt to wake up and there's really no point to having the POLLING bit.

Signed-off-by James Hogan <[email protected]>

Cc Peter Zijlstra <[email protected]>

---
 arch/metag/include/asm/thread_info.h | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

arch/metag/include/asm/thread_info.h +2 -4

index b19e9c588a16..47711336119e 100644
@@ -117,10 +117,8 @@ static inline int kstack_end(void *addr)
 #define TIF_SECCOMP		5	/* secure computing */
 #define TIF_RESTORE_SIGMASK	6	/* restore signal mask in do_signal() */
 #define TIF_NOTIFY_RESUME	7	/* callback before returning to user */
-#define TIF_POLLING_NRFLAG      8	/* true if poll_idle() is polling
-					   TIF_NEED_RESCHED */
-#define TIF_MEMDIE		9	/* is terminating due to OOM killer */
-#define TIF_SYSCALL_TRACEPOINT  10	/* syscall tracepoint instrumentation */
+#define TIF_MEMDIE		8	/* is terminating due to OOM killer */
+#define TIF_SYSCALL_TRACEPOINT	9	/* syscall tracepoint instrumentation */
 
 
 #define _TIF_SYSCALL_TRACE	(1<<TIF_SYSCALL_TRACE)

With the generic idle functions assuming !polling we should only clear the polling bit at the very last opportunity in order to avoid spurious IPIs.

Ideally we'd flip the default to polling, but that means auditing all arch idle functions.

Cc Nicolas Pitre <[email protected]>

Cc Daniel Lezcano <[email protected]>

Cc Thomas Gleixner <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 kernel/sched/idle.c |   17 ++++++++++-------
 1 file changed, 10 insertions(+), 7 deletions(-)

kernel/sched/idle.c +10 -7

@@ -78,12 +78,10 @@ static int cpuidle_idle_call(void)
 
 	/*
 	 * Check if the idle task must be rescheduled. If it is the
-	 * case, exit the function after re-enabling the local irq and
-	 * set again the polling flag
+	 * case, exit the function after re-enabling the local irq.
 	 */
-	if (current_clr_polling_and_test()) {
+	if (need_resched()) {
 		local_irq_enable();
-		__current_set_polling();
 		return 0;
 	}
 

@@ -127,7 +125,7 @@ static int cpuidle_idle_call(void)
 			broadcast = !!(drv->states[next_state].flags &
 				       CPUIDLE_FLAG_TIMER_STOP);
 
-			if (broadcast)
+			if (broadcast) {
 				/*
 				 * Tell the time framework to switch
 				 * to a broadcast timer because our

@@ -139,6 +137,7 @@ static int cpuidle_idle_call(void)
 				ret = clockevents_notify(
 					CLOCK_EVT_NOTIFY_BROADCAST_ENTER,
 					&dev->cpu);
+			}
 
 			if (!ret) {
 				trace_cpu_idle_rcuidle(next_state, dev->cpu);

@@ -175,8 +174,12 @@ static int cpuidle_idle_call(void)
 	 * We can't use the cpuidle framework, let's use the default
 	 * idle routine
 	 */
-	if (ret)
-		arch_cpu_idle();
+	if (ret) {
+		if (!current_clr_polling_and_test())
+			arch_cpu_idle();
+		else
+			local_irq_enable();
+	}
 
 	__current_set_polling();
 

Apply goto to reduce lines and nesting levels.

Cc Daniel Lezcano <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Nicolas Pitre <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 kernel/sched/idle.c |  138 +++++++++++++++++++++++-----------------------------
 1 file changed, 62 insertions(+), 76 deletions(-)

kernel/sched/idle.c +1 -1

@@ -73,7 +73,7 @@ static int cpuidle_idle_call(void)
 {
 	struct cpuidle_device *dev = __this_cpu_read(cpuidle_devices);
 	struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);
-	int next_state, entered_state, ret;
+	int next_state, entered_state;
 	bool broadcast;
 
 	/*

kernel/sched/idle.c +59 -74

-	if (!ret) {
-		/*
-		 * Ask the governor to choose an idle state it thinks
-		 * it is convenient to go to. There is *always* a
-		 * convenient idle state
-		 */
-		next_state = cpuidle_select(drv, dev);
-
-		/*
-		 * The idle task must be scheduled, it is pointless to
-		 * go to idle, just update no idle residency and get
-		 * out of this function
-		 */
-		if (current_clr_polling_and_test()) {
-			dev->last_residency = 0;
-			entered_state = next_state;
-			local_irq_enable();
-		} else {
-			broadcast = !!(drv->states[next_state].flags &
-				       CPUIDLE_FLAG_TIMER_STOP);
-
-			if (broadcast) {
-				/*
-				 * Tell the time framework to switch
-				 * to a broadcast timer because our
-				 * local timer will be shutdown. If a
-				 * local timer is used from another
-				 * cpu as a broadcast timer, this call
-				 * may fail if it is not available
-				 */
-				ret = clockevents_notify(
-					CLOCK_EVT_NOTIFY_BROADCAST_ENTER,
-					&dev->cpu);
-			}
-
-			if (!ret) {
-				trace_cpu_idle_rcuidle(next_state, dev->cpu);
-
-				/*
-				 * Enter the idle state previously
-				 * returned by the governor
-				 * decision. This function will block
-				 * until an interrupt occurs and will
-				 * take care of re-enabling the local
-				 * interrupts
-				 */
-				entered_state = cpuidle_enter(drv, dev,
-							      next_state);
-
-				trace_cpu_idle_rcuidle(PWR_EVENT_EXIT,
-						       dev->cpu);
-
-				if (broadcast)
-					clockevents_notify(
-						CLOCK_EVT_NOTIFY_BROADCAST_EXIT,
-						&dev->cpu);
-
-				/*
-				 * Give the governor an opportunity to reflect on the
-				 * outcome
-				 */
-				cpuidle_reflect(dev, entered_state);
-			}
-		}
-	}
+	/*
+	 * Ask the governor to choose an idle state it thinks
+	 * it is convenient to go to. There is *always* a
+	 * convenient idle state
+	 */
+	next_state = cpuidle_select(drv, dev);
 
 	/*
-	 * We can't use the cpuidle framework, let's use the default
-	 * idle routine
+	 * The idle task must be scheduled, it is pointless to
+	 * go to idle, just update no idle residency and get
+	 * out of this function
 	 */
-	if (ret) {
-		if (!current_clr_polling_and_test())
-			arch_cpu_idle();
-		else
-			local_irq_enable();
+	if (current_clr_polling_and_test()) {
+		dev->last_residency = 0;
+		entered_state = next_state;
+		local_irq_enable();
+		goto exit_idle;
 	}
 
+	broadcast = !!(drv->states[next_state].flags & CPUIDLE_FLAG_TIMER_STOP);
+
+	/*
+	 * Tell the time framework to switch to a broadcast timer
+	 * because our local timer will be shutdown. If a local timer
+	 * is used from another cpu as a broadcast timer, this call may
+	 * fail if it is not available
+	 */
+	if (broadcast &&
+	    clockevents_notify(CLOCK_EVT_NOTIFY_BROADCAST_ENTER, &dev->cpu))
+		goto use_default;
+
+	trace_cpu_idle_rcuidle(next_state, dev->cpu);
+
+	/*
+	 * Enter the idle state previously returned by the governor decision.
+	 * This function will block until an interrupt occurs and will take
+	 * care of re-enabling the local interrupts
+	 */
+	entered_state = cpuidle_enter(drv, dev, next_state);
+
+	trace_cpu_idle_rcuidle(PWR_EVENT_EXIT, dev->cpu);
+
+	if (broadcast)
+		clockevents_notify(CLOCK_EVT_NOTIFY_BROADCAST_EXIT, &dev->cpu);
+
+	/*
+	 * Give the governor an opportunity to reflect on the outcome
+	 */
+	cpuidle_reflect(dev, entered_state);
+
+exit_idle:
 	__current_set_polling();
 
 	/*
-	 * It is up to the idle functions to enable back the local
-	 * interrupt
+	 * It is up to the idle functions to reenable local interrupts
 	 */
 	if (WARN_ON_ONCE(irqs_disabled()))
 		local_irq_enable();

@@ -194,6 +168,18 @@ static int cpuidle_idle_call(void)
 	start_critical_timings();
 
 	return 0;
+
+	/*
+	 * We can't use the cpuidle framework, let's use the default idle
+	 * routine
+	 */
+use_default:
+	if (current_clr_polling_and_test())
+		local_irq_enable();
+	else
+		arch_cpu_idle();
+
+	goto exit_idle;
 }
 
 /*

kernel/sched/idle.c static int cpuidle_idle_call(void) · line 106

Quoted 7 lines

kernel/sched/idle.c +2 -1

@@ -102,90 +102,64 @@ static int cpuidle_idle_call(void)
 	 * Check if the cpuidle framework is ready, otherwise fallback
 	 * to the default arch specific idle method
 	 */
-	ret = cpuidle_enabled(drv, dev);
+	if (cpuidle_enabled(drv, dev))
+		goto use_default;

Why not using braces here and moving the use_default code block inside it instead?

Quoted 2 lines

Why not using braces here and moving the use_default code block inside it instead?

I didn't because there's two goto use_default sites, but sure, I can do that.

Quoted 5 lines · Peter Zijlstra

Quoted 2 lines

Why not using braces here and moving the use_default code block inside it instead?

I didn't because there's two goto use_default sites, but sure, I can do that.

---
Subject: sched,idle: Reflow cpuidle_idle_call()
From: Peter Zijlstra <[email protected]>
Date: Fri Apr 11 13:55:48 CEST 2014

Apply goto to reduce lines and nesting levels.

Cc Nicolas Pitre <[email protected]>

Cc Daniel Lezcano <[email protected]>

Cc Thomas Gleixner <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

Link http://lkml.kernel.org/n/[email protected] open here

---
 kernel/sched/idle.c |  131 +++++++++++++++++++++++-----------------------------
 1 file changed, 58 insertions(+), 73 deletions(-)

kernel/sched/idle.c +58 -73

@@ -73,7 +73,7 @@ static int cpuidle_idle_call(void)
 {
 	struct cpuidle_device *dev = __this_cpu_read(cpuidle_devices);
 	struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);
-	int next_state, entered_state, ret;
+	int next_state, entered_state;
 	bool broadcast;
 
 	/*

@@ -102,90 +102,75 @@ static int cpuidle_idle_call(void)
 	 * Check if the cpuidle framework is ready, otherwise fallback
 	 * to the default arch specific idle method
 	 */
-	ret = cpuidle_enabled(drv, dev);
-
-	if (!ret) {
-		/*
-		 * Ask the governor to choose an idle state it thinks
-		 * it is convenient to go to. There is *always* a
-		 * convenient idle state
-		 */
-		next_state = cpuidle_select(drv, dev);
-
+	if (cpuidle_enabled(drv, dev)) {
+use_default:
 		/*
-		 * The idle task must be scheduled, it is pointless to
-		 * go to idle, just update no idle residency and get
-		 * out of this function
+		 * We can't use the cpuidle framework, let's use the default
+		 * idle routine.
 		 */
-		if (current_clr_polling_and_test()) {
-			dev->last_residency = 0;
-			entered_state = next_state;
+		if (current_clr_polling_and_test())
 			local_irq_enable();
-		} else {
-			broadcast = !!(drv->states[next_state].flags &
-				       CPUIDLE_FLAG_TIMER_STOP);
-
-			if (broadcast) {
-				/*
-				 * Tell the time framework to switch
-				 * to a broadcast timer because our
-				 * local timer will be shutdown. If a
-				 * local timer is used from another
-				 * cpu as a broadcast timer, this call
-				 * may fail if it is not available
-				 */
-				ret = clockevents_notify(
-					CLOCK_EVT_NOTIFY_BROADCAST_ENTER,
-					&dev->cpu);
-			}
-
-			if (!ret) {
-				trace_cpu_idle_rcuidle(next_state, dev->cpu);
-
-				/*
-				 * Enter the idle state previously
-				 * returned by the governor
-				 * decision. This function will block
-				 * until an interrupt occurs and will
-				 * take care of re-enabling the local
-				 * interrupts
-				 */
-				entered_state = cpuidle_enter(drv, dev,
-							      next_state);
-
-				trace_cpu_idle_rcuidle(PWR_EVENT_EXIT,
-						       dev->cpu);
-
-				if (broadcast)
-					clockevents_notify(
-						CLOCK_EVT_NOTIFY_BROADCAST_EXIT,
-						&dev->cpu);
-
-				/*
-				 * Give the governor an opportunity to reflect on the
-				 * outcome
-				 */
-				cpuidle_reflect(dev, entered_state);
-			}
-		}
+		else
+			arch_cpu_idle();
+
+		goto exit_idle;
 	}
 
 	/*
-	 * We can't use the cpuidle framework, let's use the default
-	 * idle routine
+	 * Ask the governor to choose an idle state it thinks
+	 * it is convenient to go to. There is *always* a
+	 * convenient idle state
 	 */
-	if (ret) {
-		if (!current_clr_polling_and_test())
-			arch_cpu_idle();
-		else
-			local_irq_enable();
+	next_state = cpuidle_select(drv, dev);
+
+	/*
+	 * The idle task must be scheduled, it is pointless to
+	 * go to idle, just update no idle residency and get
+	 * out of this function
+	 */
+	if (current_clr_polling_and_test()) {
+		dev->last_residency = 0;
+		entered_state = next_state;
+		local_irq_enable();
+		goto exit_idle;
 	}
 
+	broadcast = !!(drv->states[next_state].flags & CPUIDLE_FLAG_TIMER_STOP);
+
+	/*
+	 * Tell the time framework to switch to a broadcast timer
+	 * because our local timer will be shutdown. If a local timer
+	 * is used from another cpu as a broadcast timer, this call may
+	 * fail if it is not available
+	 */
+	if (broadcast &&
+	    clockevents_notify(CLOCK_EVT_NOTIFY_BROADCAST_ENTER, &dev->cpu))
+		goto use_default;
+
+	trace_cpu_idle_rcuidle(next_state, dev->cpu);
+
+	/*
+	 * Enter the idle state previously returned by the governor decision.
+	 * This function will block until an interrupt occurs and will take
+	 * care of re-enabling the local interrupts
+	 */
+	entered_state = cpuidle_enter(drv, dev, next_state);
+
+	trace_cpu_idle_rcuidle(PWR_EVENT_EXIT, dev->cpu);
+
+	if (broadcast)
+		clockevents_notify(CLOCK_EVT_NOTIFY_BROADCAST_EXIT, &dev->cpu);
+
+	/*
+	 * Give the governor an opportunity to reflect on the outcome
+	 */
+	cpuidle_reflect(dev, entered_state);
+
+exit_idle:
 	__current_set_polling();
 
 	/*
-	 * It is up to the idle functions to enable back the local
-	 * interrupt
+	 * It is up to the idle functions to reenable local interrupts
 	 */
 	if (WARN_ON_ONCE(irqs_disabled()))
 		local_irq_enable();

A while ago both Mike and Andy complained that we still get pointless wakeup IPIs, we had a few patches back and forth but eventually more or less agreed and then nothing... :-)

So here's a number of patches that implement something near what we left off with.

Its only been compile/boot tested on x86_64, I've no actually looked at the IPI numbers yet.

That being said, I think that this addresses once one of the two major issues. While the race you're fixing is more interesting, I think its impact is dwarfed by the fact that ttwu_queue_remote completely ignores polling. (NB: I haven't actually tested this patch set, but I did try to instrument this stuff awhile ago.)

To fix this, presumably the wake-from-idle path needs a sched_ttwu_pending call, and ttwu_queue_remote could use resched_task.
sched_ttwu_pending could benefit from a straightforward optimization:
it doesn't need rq->lock if llist is empty.

If you're not planning on trying to fix that, I can try to write up a patch in the next day or two.

Even with all of this fixed, what happens when ttwu_queue_remote is called with a task that has lower priority than whatever is currently running on the targeted cpu? I think the result is an IPI that serves very little purpose other than avoiding taking a spinlock in the waking thread. This may be a bad tradeoff. I doubt that this matters for my particular workload, though.

That being said, I think that this addresses once one of the two major issues. While the race you're fixing is more interesting, I think its impact is dwarfed by the fact that ttwu_queue_remote completely ignores polling. (NB: I haven't actually tested this patch set, but I did try to instrument this stuff awhile ago.)

To fix this, presumably the wake-from-idle path needs a sched_ttwu_pending call, and ttwu_queue_remote could use resched_task.
sched_ttwu_pending could benefit from a straightforward optimization:
it doesn't need rq->lock if llist is empty.

If you're not planning on trying to fix that, I can try to write up a patch in the next day or two.

Even with all of this fixed, what happens when ttwu_queue_remote is called with a task that has lower priority than whatever is currently running on the targeted cpu? I think the result is an IPI that serves very little purpose other than avoiding taking a spinlock in the waking thread. This may be a bad tradeoff. I doubt that this matters for my particular workload, though.

---

kernel/sched/core.c +4 -0

index 4ea7b3f1a087..a5da85fb3570 100644
@@ -546,12 +546,38 @@ static bool set_nr_and_not_polling(struct task_struct *p)
 	struct thread_info *ti = task_thread_info(p);
 	return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
+
+/*
+ * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
+ */

kernel/sched/core.c +6 -0

+		old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
+		if (old == val)
+			return true;
+		val = old;
+	}
+}

Quoted 19 lines · Peter Zijlstra

---

kernel/sched/core.c +10 -0

index 4ea7b3f1a087..a5da85fb3570 100644
@@ -546,12 +546,38 @@ static bool set_nr_and_not_polling(struct task_struct *p)
      struct thread_info *ti = task_thread_info(p);
      return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
+
+/*
+ * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
+ */
+static bool set_nr_if_polling(struct task_struct *p)
+{
+     struct thread_info *ti = task_thread_info(p);
+     typeof(ti->flags) old, val = ti->flags;
+
+     for (;;) {

kernel/sched/core.c static bool set_nr_and_not_polling(struct task_struct *p) · line 562

Quoted 4 lines

kernel/sched/core.c +4 -0

+             if (!(val & _TIF_POLLING_NRFLAG))
+                     return false;
+             if (val & _TIF_NEED_RESCHED)
+                     return true;

Hmm, I think this is racy, false would be safer. If its already set we might already be past the sched_ttwu_pending() invocation, while if its clear and we're the one to set it, we're guaranteed not.

Quoted 6 lines

kernel/sched/core.c +6 -0

+             old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
+             if (old == val)
+                     return true;
+             val = old;
+     }
+}

Quoted 20 lines · Peter Zijlstra

Quoted 19 lines · Peter Zijlstra

---

kernel/sched/core.c +10 -0

index 4ea7b3f1a087..a5da85fb3570 100644
@@ -546,12 +546,38 @@ static bool set_nr_and_not_polling(struct task_struct *p)
      struct thread_info *ti = task_thread_info(p);
      return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
+
+/*
+ * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
+ */
+static bool set_nr_if_polling(struct task_struct *p)
+{
+     struct thread_info *ti = task_thread_info(p);
+     typeof(ti->flags) old, val = ti->flags;
+
+     for (;;) {

Quoted 15 lines

kernel/sched/core.c static bool set_nr_and_not_polling(struct task_struct *p) · line 562

Quoted 4 lines

kernel/sched/core.c +4 -0

+             if (!(val & _TIF_POLLING_NRFLAG))
+                     return false;
+             if (val & _TIF_NEED_RESCHED)
+                     return true;

Hmm, I think this is racy, false would be safer. If its already set we might already be past the sched_ttwu_pending() invocation, while if its clear and we're the one to set it, we're guaranteed not.

Quoted 6 lines

kernel/sched/core.c +6 -0

+             old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
+             if (old == val)
+                     return true;
+             val = old;
+     }
+}

Do you have an updated patch? After fixing the MIME flow damage (sigh), it doesn't apply to sched/core, which is my best guess for what it's based on.

Quoted 37 lines · Andy Lutomirski

Quoted 35 lines · Peter Zijlstra

Quoted 13 lines · Peter Zijlstra

---

kernel/sched/core.c +4 -0

index 4ea7b3f1a087..a5da85fb3570 100644
@@ -546,12 +546,38 @@ static bool set_nr_and_not_polling(struct task_struct *p)
      struct thread_info *ti = task_thread_info(p);
      return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
+
+/*
+ * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
+ */

kernel/sched/core.c static bool set_nr_and_not_polling(struct task_struct *p) · line 562

Quoted 10 lines

kernel/sched/core.c +10 -0

+static bool set_nr_if_polling(struct task_struct *p)
+{
+     struct thread_info *ti = task_thread_info(p);
+     typeof(ti->flags) old, val = ti->flags;
+
+     for (;;) {
+             if (!(val & _TIF_POLLING_NRFLAG))
+                     return false;
+             if (val & _TIF_NEED_RESCHED)
+                     return true;

Hmm, I think this is racy, false would be safer. If its already set we might already be past the sched_ttwu_pending() invocation, while if its clear and we're the one to set it, we're guaranteed not.

Quoted 6 lines

kernel/sched/core.c +6 -0

+             old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
+             if (old == val)
+                     return true;
+             val = old;
+     }
+}

Quoted 3 lines

Do you have an updated patch? After fixing the MIME flow damage (sigh), it doesn't apply to sched/core, which is my best guess for what it's based on.

https://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/commit/?h=sched/core&id=c224d4fee677ecc72209903d330b643bcf0793d7

Bugs found so far:

defined(SMP) should be defined(CONFIG_SMP)

You're testing polling on the task being woken, which cannot possibly
succeed: the only tasks that have any business polling are the idle tasks. Something like this seems to help:

You're testing polling on the task being woken, which cannot possibly
succeed: the only tasks that have any business polling are the idle tasks. Something like this seems to help:

static void ttwu_queue_remote(struct task_struct *p, int cpu) {

(quoted diff) +5 -1

+       struct rq *rq = cpu_rq(cpu);
+
        if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list)) {
-               if (!set_nr_if_polling(p))
+               if (!set_nr_if_polling(rq->idle))
                        smp_send_reschedule(cpu);
+               else
+                       trace_sched_wake_polling_cpu(cpu);
        }
 }

If you don't beat me to it, I'll send real patches in the morning. I'll also send some followup patches to make it even better. Fully fixed up, this gets rid of almost all of my rescheduling interrupts except for interrupts from the timer tick.

Also, grr, I still think this would be clearer if polling and need_resched were per cpu instead of per task -- they only make sense on a running task. I guess that need_resched being in thread_info->flags is helpful because it streamlines the interrupt exit code. Oh, well.

We need rq->curr, rq->idle 'sleeps' with polling set and nr clear, but it obviously has no effect setting that if its not actually the current task.

Touching rq->curr needs holding rcu_read_lock() though, to make sure the task stays around, still shouldn't be a problem.

kernel/sched/core.c +0 -1

@@ -1581,8 +1604,14 @@ void scheduler_ipi(void)
 
 static void ttwu_queue_remote(struct task_struct *p, int cpu)
 {
-	if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list))

Quoted 12 lines · Peter Zijlstra

We need rq->curr, rq->idle 'sleeps' with polling set and nr clear, but it obviously has no effect setting that if its not actually the current task.

Touching rq->curr needs holding rcu_read_lock() though, to make sure the task stays around, still shouldn't be a problem.

kernel/sched/core.c +0 -1

@@ -1581,8 +1604,14 @@ void scheduler_ipi(void)
 
 static void ttwu_queue_remote(struct task_struct *p, int cpu)
 {
-     if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list))

kernel/sched/core.c void scheduler_ipi(void) · line 1615

Quoted 10 lines

kernel/sched/core.c +8 -1

-             smp_send_reschedule(cpu);
+     struct rq *rq = cpu_rq(cpu);
+
+     if (llist_add(&p->wake_entry, &rq->wake_list)) {
+             rcu_read_lock();
+             if (!set_nr_if_polling(rq->curr))
+                     smp_send_reschedule(cpu);
+             rcu_read_unlock();
+     }
 }

Hrmm, I think that is still broken, see how in schedule() we clear NR before setting the new ->curr.

So I think I had a loop on rq->curr the last time we talked about this, but alternatively we could look at clearing NR after setting a new curr.

I think I once looked at why it was done before, of course I can't actually remember the details :/

Quoted 27 lines · Peter Zijlstra

Quoted 12 lines · Peter Zijlstra

We need rq->curr, rq->idle 'sleeps' with polling set and nr clear, but it obviously has no effect setting that if its not actually the current task.

Touching rq->curr needs holding rcu_read_lock() though, to make sure the task stays around, still shouldn't be a problem.

kernel/sched/core.c +0 -1

@@ -1581,8 +1604,14 @@ void scheduler_ipi(void)
 
 static void ttwu_queue_remote(struct task_struct *p, int cpu)
 {
-     if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list))

kernel/sched/core.c void scheduler_ipi(void) · line 1615

Quoted 10 lines

kernel/sched/core.c +8 -1

-             smp_send_reschedule(cpu);
+     struct rq *rq = cpu_rq(cpu);
+
+     if (llist_add(&p->wake_entry, &rq->wake_list)) {
+             rcu_read_lock();
+             if (!set_nr_if_polling(rq->curr))
+                     smp_send_reschedule(cpu);
+             rcu_read_unlock();
+     }
 }

Hrmm, I think that is still broken, see how in schedule() we clear NR before setting the new ->curr.

Quoted 5 lines

So I think I had a loop on rq->curr the last time we talked about this, but alternatively we could look at clearing NR after setting a new curr.

I think I once looked at why it was done before, of course I can't actually remember the details :/

Wouldn't this be a little simpler and maybe even faster if we just changed the idle loop to make TIF_POLLING_NRFLAG be a real indication that the idle task is running and actively polling? That is, change the end of cpuidle_idle_loop to:

                preempt_set_need_resched();
                tick_nohz_idle_exit();
                clear_tsk_need_resched(current);
                __current_clr_polling();
                smp_mb__after_clear_bit();
                WARN_ON_ONCE(test_thread_flag(TIF_POLLING_NRFLAG));
                sched_ttwu_pending();
                schedule_preempt_disabled();
                __current_set_polling();

This has the added benefit that the optimistic version of the cmpxchg loop would be safe again. I'm about to test this with this variant. I'll try and send a comprehensible set of patches in a few hours.

Can you remind me what the benefit was of letting polling be set when the idle thread schedules?

It seems racy to me: it probably prevents
any safe use of the polling bit without holding the rq lock. I guess there's some benefit to having polling be set for as long as possible, but it only helps if there are wakeups in very rapid succession, and it costs a couple of extra bit ops per idle entry.

Quoted 49 lines · Andy Lutomirski

Quoted 27 lines · Peter Zijlstra

Quoted 12 lines · Peter Zijlstra

We need rq->curr, rq->idle 'sleeps' with polling set and nr clear, but it obviously has no effect setting that if its not actually the current task.

Touching rq->curr needs holding rcu_read_lock() though, to make sure the task stays around, still shouldn't be a problem.

kernel/sched/core.c +0 -1

@@ -1581,8 +1604,14 @@ void scheduler_ipi(void)
 
 static void ttwu_queue_remote(struct task_struct *p, int cpu)
 {
-     if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list))

kernel/sched/core.c void scheduler_ipi(void) · line 1615

Quoted 10 lines

kernel/sched/core.c +8 -1

-             smp_send_reschedule(cpu);
+     struct rq *rq = cpu_rq(cpu);
+
+     if (llist_add(&p->wake_entry, &rq->wake_list)) {
+             rcu_read_lock();
+             if (!set_nr_if_polling(rq->curr))
+                     smp_send_reschedule(cpu);
+             rcu_read_unlock();
+     }
 }

Hrmm, I think that is still broken, see how in schedule() we clear NR before setting the new ->curr.

Quoted 5 lines

So I think I had a loop on rq->curr the last time we talked about this, but alternatively we could look at clearing NR after setting a new curr.

I think I once looked at why it was done before, of course I can't actually remember the details :/

Wouldn't this be a little simpler and maybe even faster if we just changed the idle loop to make TIF_POLLING_NRFLAG be a real indication that the idle task is running and actively polling? That is, change the end of cpuidle_idle_loop to:

                preempt_set_need_resched();
                tick_nohz_idle_exit();
                clear_tsk_need_resched(current);
                __current_clr_polling();
                smp_mb__after_clear_bit();
                WARN_ON_ONCE(test_thread_flag(TIF_POLLING_NRFLAG));
                sched_ttwu_pending();
                schedule_preempt_disabled();
                __current_set_polling();

Quoted 6 lines

This has the added benefit that the optimistic version of the cmpxchg loop would be safe again. I'm about to test this with this variant. I'll try and send a comprehensible set of patches in a few hours.

Can you remind me what the benefit was of letting polling be set when the idle thread schedules?

Hysterical raisins, I don't think there's an actual reason, so yes, that might be the best option indeed.

Quoted 5 lines

It seems racy to me: it probably prevents
any safe use of the polling bit without holding the rq lock. I guess there's some benefit to having polling be set for as long as possible, but it only helps if there are wakeups in very rapid succession, and it costs a couple of extra bit ops per idle entry.

So you could cheat and set it in pick_next_task_idle() and clear in put_prev_task_idle(), that way the entire idle loop, when running has it set.

And then there was the idle injection loop crap trainwreck, which I should send patches for..

Quoted 4 lines

So you could cheat and set it in pick_next_task_idle() and clear in put_prev_task_idle(), that way the entire idle loop, when running has it set.

Isn't that a little late for sched_ttwu_pending? I guess it could be okay, but I'm hesitant to muck around with the scheduler innards that much. I don't see anything that'll break, though.

I'm seriously confused by the polling situation, though. TIF_NRFLAG_POLLING is defined for a whole bunch of architectures, but I can't find any actual polling idle code outside cpuidle and x86.

For example, arm defines TIF_POLLING_NRFLAG, but I can't find anything that clears the polling bit in the arm code. Am I missing something obvious here?

Is the whole point of this so that a wakeup that
happens right after the idle task is scheduled but before it goes idle cancels idle and avoids an IPI? This seems like a lot of complexity to avoid IPIs in a hopefully extremely narrow window.

This is totally backwards for x86, but it seems to do the right thing for other architectures. I'm not convinced it does any good, though.

Quoted 8 lines · Andy Lutomirski

Quoted 4 lines

So you could cheat and set it in pick_next_task_idle() and clear in put_prev_task_idle(), that way the entire idle loop, when running has it set.

Isn't that a little late for sched_ttwu_pending? I guess it could be okay, but I'm hesitant to muck around with the scheduler innards that much. I don't see anything that'll break, though.

Yeah, only later did I see you clear much earlier, which makes sense.

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Andy Lutomirski

Quoted 4 lines

So you could cheat and set it in pick_next_task_idle() and clear in put_prev_task_idle(), that way the entire idle loop, when running has it set.

Isn't that a little late for sched_ttwu_pending? I guess it could be okay, but I'm hesitant to muck around with the scheduler innards that much. I don't see anything that'll break, though.

Quoted 1 line

Yeah, only later did I see you clear much earlier, which makes sense.

Could we clear it from set_nr_and_not_polling()/set_nr_if_polling()? That's the only two functions that'll kick a cpu out of its polling loop, and we're already writing to the word anyhow.

Quoted 11 lines · Peter Zijlstra

Quoted 10 lines · Peter Zijlstra

Quoted 8 lines · Andy Lutomirski

Quoted 4 lines

So you could cheat and set it in pick_next_task_idle() and clear in put_prev_task_idle(), that way the entire idle loop, when running has it set.

Isn't that a little late for sched_ttwu_pending? I guess it could be okay, but I'm hesitant to muck around with the scheduler innards that much. I don't see anything that'll break, though.

Quoted 5 lines

Quoted 1 line

Yeah, only later did I see you clear much earlier, which makes sense.

Could we clear it from set_nr_and_not_polling()/set_nr_if_polling()? That's the only two functions that'll kick a cpu out of its polling loop, and we're already writing to the word anyhow.

I'd be nervous about this. I think it could break if cpuidle_idle_call decides not to idle for any reason, and there is plenty of complicated code in there.

I'm currently working on some patches that might make this clearer. Give me a bit.

A while ago both Mike and Andy complained that we still get pointless wakeup IPIs, we had a few patches back and forth but eventually more or less agreed and then nothing... :-)

So here's a number of patches that implement something near what we left off with.

Its only been compile/boot tested on x86_64, I've no actually looked at the IPI numbers yet.