cpu_idle and cpu_wait

cpu_idle and cpu_wait

[Atsushi Nemoto]

Looking at recent change in cpu_idle(), I find an another potential
problem with cpu_wait (WAIT instruction).

    48	ATTRIB_NORET void cpu_idle(void)
    49	{
    50		/* endless idle loop with no priority at all */
    51		while (1) {
    52			while (!need_resched())
    53				if (cpu_wait)
    54					(*cpu_wait)();
    55			preempt_enable_no_resched();
    56			schedule();
    57			preempt_disable();
    58		}
    59	}

If an interrupt raised on line 53 and the interrupt handler woke a
sleeping thread up, the thread becomes runnable and current thread
(idle thread) is marked as NEED_RESCHED.

Since preemption is disabled, the interrupt handler just return to
current thread (idle thread) without rescheduling.  The idle thread
then call cpu_wait() and execute WAIT instruction (or something
similer).  The CPU will stops until next interrupt.  Then the idle
task checks need_resched() and finally calls schedule().  Therefore,
wakeup-resume latency will be nearly one TICK on worst case!

If this analysis was correct, how to fix this?

Removing above preempt_enable_no_resched/preempt_disable pair would
fix it for preemptive kernel, but no point for non-preemptive kernel.
Replacing them with local_irq_enable/local_irq_disable would fix it
for both kernel, but there is an question:

	The CPU can surely exit from the WAIT instruction by interrupt
	even if interrupts disabled?

I know the answer is yes on TX49.  Any external (or counter) interrupt
SIGNAL can break the WAIT instruction.  How about others?

---
Atsushi Nemoto

Re: cpu_idle and cpu_wait

[Ralf Baechle]

On Thu, Nov 17, 2005 at 01:19:06AM +0900, Atsushi Nemoto wrote:

> Looking at recent change in cpu_idle(), I find an another potential
> problem with cpu_wait (WAIT instruction).
> 
>     48	ATTRIB_NORET void cpu_idle(void)
>     49	{
>     50		/* endless idle loop with no priority at all */
>     51		while (1) {
>     52			while (!need_resched())
>     53				if (cpu_wait)
>     54					(*cpu_wait)();
>     55			preempt_enable_no_resched();
>     56			schedule();
>     57			preempt_disable();
>     58		}
>     59	}
> 
> If an interrupt raised on line 53 and the interrupt handler woke a
> sleeping thread up, the thread becomes runnable and current thread
> (idle thread) is marked as NEED_RESCHED.
> 
> Since preemption is disabled, the interrupt handler just return to
> current thread (idle thread) without rescheduling.  The idle thread
> then call cpu_wait() and execute WAIT instruction (or something
> similer).  The CPU will stops until next interrupt.  Then the idle
> task checks need_resched() and finally calls schedule().  Therefore,
> wakeup-resume latency will be nearly one TICK on worst case!

Pleassure.

> If this analysis was correct, how to fix this?
> 
> Removing above preempt_enable_no_resched/preempt_disable pair would
> fix it for preemptive kernel, but no point for non-preemptive kernel.
> Replacing them with local_irq_enable/local_irq_disable would fix it
> for both kernel, but there is an question:

Somebody sneaking those lines into kernel.org ...

> 	The CPU can surely exit from the WAIT instruction by interrupt
> 	even if interrupts disabled?

That's implementation dependent behaviour, unfortunately.

  Ralf

Re: cpu_idle and cpu_wait

[Atsushi Nemoto]

>>>>> On Wed, 16 Nov 2005 18:42:01 +0000, Ralf Baechle <ralf@linux-mips.org> said:
>> The CPU can surely exit from the WAIT instruction by interrupt even
>> if interrupts disabled?

ralf> That's implementation dependent behaviour, unfortunately.

I checked some MIPS32/MIPS64 datasheets and found that's really
inplementation-dependent.  The answer is YES on (perhaps) all MIPS4K?
processors but NO on 20Kc, 24K ...

And I checked x86 implemetation and found that HLT or MWAIT
instruction also must be used with interrupts enabled.  So IIUC it
seems x86 have same latency problem too.

---
Atsushi Nemoto

Re: cpu_idle and cpu_wait

[Atsushi Nemoto]

>>>>> On Thu, 17 Nov 2005 11:21:45 +0900 (JST), Atsushi Nemoto <anemo@mba.ocn.ne.jp> said:
anemo> And I checked x86 implemetation and found that HLT or MWAIT
anemo> instruction also must be used with interrupts enabled.  So IIUC
anemo> it seems x86 have same latency problem too.

No, I was wrong.  MWAIT (and MONITOR) instruction provides something
like "test and wait" mechanism.  mwait_idle() is using them for
thread_flag, so there is no latency problem on processors which have
MWAIT/MONITOR.

---
Atsushi Nemoto

Re: cpu_idle and cpu_wait

[Atsushi Nemoto]

>>>>> On Wed, 16 Nov 2005 18:42:01 +0000, Ralf Baechle <ralf@linux-mips.org> said:
>> The CPU can surely exit from the WAIT instruction by interrupt even
>> if interrupts disabled?

ralf> That's implementation dependent behaviour, unfortunately.

Then how about this patch?

By datasheets, MIPS4K?, MIPS5Kc, TX49 (and TX39 using HALT bit instead
of WAIT insn) allow us entering WAIT with interrupt disabled.

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

diff --git a/arch/mips/kernel/cpu-probe.c b/arch/mips/kernel/cpu-probe.c
index d2ae111..4bdd8c1 100644
--- a/arch/mips/kernel/cpu-probe.c
+++ b/arch/mips/kernel/cpu-probe.c
@@ -39,16 +39,33 @@ static void r3081_wait(void)
 
 static void r39xx_wait(void)
 {
-	unsigned long cfg = read_c0_conf();
-	write_c0_conf(cfg | TX39_CONF_HALT);
+	local_irq_disable();
+	if (!need_resched())
+		write_c0_conf(read_c0_conf() | TX39_CONF_HALT);
+	local_irq_enable();
 }
 
+/*
+ * There is a race when WAIT instruction executed with interrupt
+ * enabled.
+ * But it is implementation-dependent wheter the pipelie restarts when
+ * a non-enabled interrupt is requested.
+ */
 static void r4k_wait(void)
 {
 	__asm__(".set\tmips3\n\t"
 		"wait\n\t"
 		".set\tmips0");
 }
+static void r4k_wait_irqoff(void)
+{
+	local_irq_disable();
+	if (!need_resched())
+		__asm__(".set\tmips3\n\t"
+			"wait\n\t"
+			".set\tmips0");
+	local_irq_enable();
+}
 
 /* The Au1xxx wait is available only if using 32khz counter or
  * external timer source, but specifically not CP0 Counter. */
@@ -112,11 +129,6 @@ static inline void check_wait(void)
 	case CPU_NEVADA:
 	case CPU_RM7000:
 	case CPU_RM9000:
-	case CPU_TX49XX:
-	case CPU_4KC:
-	case CPU_4KEC:
-	case CPU_4KSC:
-	case CPU_5KC:
 /*	case CPU_20KC:*/
 	case CPU_24K:
 	case CPU_25KF:
@@ -125,6 +137,14 @@ static inline void check_wait(void)
 		cpu_wait = r4k_wait;
 		printk(" available.\n");
 		break;
+	case CPU_TX49XX:
+	case CPU_4KC:
+	case CPU_4KEC:
+	case CPU_4KSC:
+	case CPU_5KC:
+		cpu_wait = r4k_wait_irqoff;
+		printk(" available.\n");
+		break;
 	case CPU_AU1000:
 	case CPU_AU1100:
 	case CPU_AU1500:

Re: cpu_idle and cpu_wait

[Atsushi Nemoto]

On Fri, 18 Nov 2005 12:22:42 +0900 (JST), Atsushi Nemoto <anemo@mba.ocn.ne.jp> wrote:
> By datasheets, MIPS4K?, MIPS5Kc, TX49 (and TX39 using HALT bit instead
> of WAIT insn) allow us entering WAIT with interrupt disabled.

Updated against current git tree.


[MIPS] reduce race between cpu_wait() and need_resched() checking

If a thread became runnable between need_resched() and the WAIT
instruction, switching to the thread will delay until a next interrupt.
Some CPUs can execute the WAIT instruction with interrupt disabled, so
we can get rid of this race on them (at least UP case).

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

diff --git a/arch/mips/kernel/cpu-probe.c b/arch/mips/kernel/cpu-probe.c
index 66e47e7..bc79c5b 100644
--- a/arch/mips/kernel/cpu-probe.c
+++ b/arch/mips/kernel/cpu-probe.c
@@ -39,16 +39,33 @@ static void r3081_wait(void)
 
 static void r39xx_wait(void)
 {
-	unsigned long cfg = read_c0_conf();
-	write_c0_conf(cfg | TX39_CONF_HALT);
+	local_irq_disable();
+	if (!need_resched())
+		write_c0_conf(read_c0_conf() | TX39_CONF_HALT);
+	local_irq_enable();
 }
 
+/*
+ * There is a race when WAIT instruction executed with interrupt
+ * enabled.
+ * But it is implementation-dependent wheter the pipelie restarts when
+ * a non-enabled interrupt is requested.
+ */
 static void r4k_wait(void)
 {
 	__asm__(".set\tmips3\n\t"
 		"wait\n\t"
 		".set\tmips0");
 }
+static void r4k_wait_irqoff(void)
+{
+	local_irq_disable();
+	if (!need_resched())
+		__asm__(".set\tmips3\n\t"
+			"wait\n\t"
+			".set\tmips0");
+	local_irq_enable();
+}
 
 /* The Au1xxx wait is available only if using 32khz counter or
  * external timer source, but specifically not CP0 Counter. */
@@ -111,11 +128,6 @@ static inline void check_wait(void)
 	case CPU_R5000:
 	case CPU_NEVADA:
 	case CPU_RM7000:
-	case CPU_TX49XX:
-	case CPU_4KC:
-	case CPU_4KEC:
-	case CPU_4KSC:
-	case CPU_5KC:
 /*	case CPU_20KC:*/
 	case CPU_24K:
 	case CPU_25KF:
@@ -125,6 +137,14 @@ static inline void check_wait(void)
 		cpu_wait = r4k_wait;
 		printk(" available.\n");
 		break;
+	case CPU_TX49XX:
+	case CPU_4KC:
+	case CPU_4KEC:
+	case CPU_4KSC:
+	case CPU_5KC:
+		cpu_wait = r4k_wait_irqoff;
+		printk(" available.\n");
+		break;
 	case CPU_AU1000:
 	case CPU_AU1100:
 	case CPU_AU1500:

Re: cpu_idle and cpu_wait

[Ralf Baechle]

On Thu, Jun 08, 2006 at 01:09:01AM +0900, Atsushi Nemoto wrote:

> [MIPS] reduce race between cpu_wait() and need_resched() checking
> 
> If a thread became runnable between need_resched() and the WAIT
> instruction, switching to the thread will delay until a next interrupt.
> Some CPUs can execute the WAIT instruction with interrupt disabled, so
> we can get rid of this race on them (at least UP case).

Applied but based on feedback from the 4K and 5K CPU designers I modified
your patch to continue using the old code.

  Ralf

Re: cpu_idle and cpu_wait

[Atsushi Nemoto]

On Sun, 10 Sep 2006 02:18:03 +0200, Ralf Baechle <ralf@linux-mips.org> wrote:
> Applied but based on feedback from the 4K and 5K CPU designers I modified
> your patch to continue using the old code.

Thanks!  IIRC MIPS4K? and MIPS5Kc datasheets state that any masked
interrupts can break WAIT instruction, but I could not test by myself
since I do not have any of them.  I believe feedback from CPU
designers of course :-)

---
Atsushi Nemoto