Subject: unaligned load in branch delay slot

From: Geert Uytterhoeven <[email-masked]>
Date: Mon, 13 Jan 2003 17:13:17 +0100 (MET)

I'm seeing a crash in 2.4.20 in emulate_load_store_insn(), when accepting a TCP
connection (exact line number influenced by debug code):

Unhandled kernel unaligned access or invalid instruction in unaligned.c::emulate_load_store_insn, line 492:
$0 : 00000000 10008400 30000000 00000000 83c2a380 83d9f80e 838941c0 00000001
$8 : 00000016 c0a80002 c0a80001 00000016 83f326a4 83f326a8 83f326a0 00000000
$16: 83c2a43c 811af440 00000000 83c2a380 803da18c 00000000 00000000 00000000
$24: 00000000 2ac41330                   8039a000 8039baf8 a38415b4 8033eea4
Hi : 00000000
Lo : 00000140
epc  : 80346448    Not tainted
Status: 10008403
Cause : 00000010
Process swapper (pid: 0, stackpage=8039a000)
Stack:    00000000 00000000 00000000 00000000 00000000 00000000 00000000
 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
 00000000 00000000 00000000 00000000 00000000 00000000 00000000 8039a000
 00000001 810d0060 802dd370 00000000 00000000 8039bb70 00000000 8041a690
 803d2000 810c5de0 8041a620 810d0060 802dd370 80213fa4 810c41a0 8039bbc8
 8020ad50 ...
Call Trace:   [<802dd370>] [<802dd370>] [<80213fa4>] [<8020ad50>] [<802ea344>]
 [<802ea2fc>] [<80307e08>] [<802378f8>] [<8020a0d4>] [<8020a0d4>] [<802061d8>]
 [<802061d8>] [<8020a0d4>] [<8033eea4>] [<80346fbc>] [<80347060>] [<8034716c>]
 [<803476f4>] [<80329a50>] [<80326648>] [<8032952c>] [<80329ddc>] [<80329d98>]
 [<80329ddc>] [<8031700c>] [<80329790>] [<8031700c>] [<80316bb4>] [<803172b8>]
 [<802df95c>] [<8021bf30>] [<80317500>] [<80316ecc>] [<8021b810>] [<80379278>]
 [<8020ad50>] [<8020aeb0>] [<8020ae84>] [<80379228>] [<80204250>] ...

Code: 8cc30064  3c023000  00621824 <14600012> 8cb50010  8c840238  8c820004  90830000  00621007 
Kernel panic: Aiee, killing interrupt handler!
In interrupt handler - not syncing

803463f8 <tcp_v4_conn_request>:
803463f8:	27bdfe20 	addiu	sp,sp,-480
803463fc:	afb601d8 	sw	s6,472(sp)
80346400:	afb301cc 	sw	s3,460(sp)
80346404:	afb101c4 	sw	s1,452(sp)
80346408:	afbf01dc 	sw	ra,476(sp)
8034640c:	afb501d4 	sw	s5,468(sp)
80346410:	afb401d0 	sw	s4,464(sp)
80346414:	afb201c8 	sw	s2,456(sp)
80346418:	afb001c0 	sw	s0,448(sp)
8034641c:	00a08821 	move	s1,a1
80346420:	8ca50020 	lw	a1,32(a1)
80346424:	8e260028 	lw	a2,40(s1)
80346428:	8e320044 	lw	s2,68(s1)
8034642c:	8ca2000c 	lw	v0,12(a1)
80346430:	00809821 	move	s3,a0
80346434:	0000b021 	move	s6,zero
80346438:	afa201b8 	sw	v0,440(sp)
8034643c:	8cc30064 	lw	v1,100(a2)
80346440:	3c023000 	lui	v0,0x3000
80346444:	00621824 	and	v1,v1,v0
80346448:	14600012 	bnez	v1,80346494 <tcp_v4_conn_request+0x9c>
8034644c:	8cb50010 	lw	s5,16(a1)
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
80346450:	8c840238 	lw	a0,568(a0)
80346454:	8c820004 	lw	v0,4(a0)
80346458:	90830000 	lbu	v1,0(a0)
8034645c:	00621007 	srav	v0,v0,v1

If I print the parameters at label `sigill' in emulate_load_store_insn(), I
get:

    pc 0x80346448 addr 0x83d9f81e ins 0x14600012

And emulate_load_store_insn() gets confused because 0x14600012 is not a
load/store. 0x14600012 is the branch instruction before the load, not the load
after the branch instruction! Note that bit 31 of cause (CAUSEF_BD) is not set.
Some more investigations showed that the branch is indeed not taken.

Apparently if an unaligned access happens right after a branch which is not
taking, epc points to the branch instruction, and CAUSEF_BD is not set
(technically speaking, this is not a branch delay, since the branch is not
taken :-). Is this expected behavior? The CPU is a VR4120A core.

As a workaround, I assume I can just test whether pc points to a branch
instruction, and increment pc if that's the case?

Thanks!

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email-masked]

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

---

From: "Mike Uhler" <[email-masked]>
Date: Mon, 13 Jan 2003 09:19:45 -0800

> instruction, and increment pc if that's the case?

Prior to the MIPS32/MIPS64 architecture definition, which requires that EPC
point at the branch and the Cause[BD] bit be set on any exception in the
branch delay slot, there were a few CPUs which interpreted the rules in the
manner that you describe.  I don't happen to have a VR4120A manual in front
of me, but the behavior you describe could easily be the case of this differnt
interpretation.

/gmu

-- 

  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Michael Uhler, VP, Systems, Architecture, and Software Products 
  MIPS Technologies, Inc.   Email: [email-masked]   Pager: [email-masked]
  1225 Charleston Road      Voice:  (650)567-5025   FAX:   (650)567-5225
  Mountain View, CA 94043   Mobile: (650)868-6870   Admin: (650)567-5085

---

From: Geert Uytterhoeven <[email-masked]>
Date: Mon, 13 Jan 2003 19:04:36 +0100 (MET)

Thanks!

The following patch (against linux-mips-2.4.x CVS) cures my crash.

I don't know on which CPUs this may happen (need #ifdef CONFIG_CPU_VR41XX?),
nor whether all branch and jump instructions are affected (I included
everything that starts with a `b' or `j').

Index: arch/mips/kernel/unaligned.c
===================================================================
RCS file: /home/cvs/linux/arch/mips/kernel/unaligned.c,v
retrieving revision 1.15.2.14
diff -u -r1.15.2.14 unaligned.c
--- arch/mips/kernel/unaligned.c	6 Jan 2003 22:05:25 -0000	1.15.2.14
+++ arch/mips/kernel/unaligned.c	13 Jan 2003 18:01:26 -0000
@@ -103,6 +103,7 @@
 	/*
 	 * This load never faults.
 	 */
+retry:
 	__get_user(insn.word, (unsigned int *)pc);
 
 	switch (insn.i_format.opcode) {
@@ -134,6 +135,26 @@
 	case lbu_op:
 	case sb_op:
 		goto sigbus;
+
+	/*
+	 * On some CPUs, if an unaligned access happens in a branch delay slot
+	 * and the branch is not taken, EPC points at the branch instruction,
+	 * but the BD bit in the cause register is not set.
+	 */
+	case bcond_op:
+	case j_op:
+	case jal_op:
+	case beq_op:
+	case bne_op:
+	case blez_op:
+	case bgtz_op:
+	case beql_op:
+	case bnel_op:
+	case blezl_op:
+	case bgtzl_op:
+	case jalx_op:
+		pc += 4;
+		goto retry;
 
 	/*
 	 * The remaining opcodes are the ones that are really of interest.

Gr{oetje,eeting}s,

						Geert

---

From: "Mike Uhler" <[email-masked]>
Date: Mon, 13 Jan 2003 12:12:28 -0800

> everything that starts with a `b' or `j').

Since all MIPS jumps are unconditional, one can never have a non-taken
jump, so you can eliminate those from the patch.

/gmu

--

---

From: Ralf Baechle <[email-masked]>
Date: Tue, 28 Jan 2003 03:39:01 +0100

> everything that starts with a `b' or `j').

I'm suggesting this alternative patch below.  Comments?

  Ralf

diff -u -r1.4.2.1 branch.h
--- include/asm-mips/branch.h 7 May 2002 03:48:08 -0000
+++ include/asm-mips/branch.h 28 Jan 2003 02:34:12 -0000
@@ -8,11 +8,52 @@
 #ifndef _ASM_BRANCH_H
 #define _ASM_BRANCH_H
 
+#include <asm/inst.h>
 #include <asm/ptrace.h>
+#include <asm/uaccess.h>
+#include <asm/war.h>
 
 static inline int delay_slot(struct pt_regs *regs)
 {
-	return regs->cp0_cause & CAUSEF_BD;
+#ifdef BDSLOT_WAR
+	union mips_instruction insn;
+	mm_segment_t seg;
+#endif
+	int ds;
+
+	ds = regs->cp0_cause & CAUSEF_BD;
+	if (ds)
+		return ds;
+
+#ifdef BDSLOT_WAR
+	if (!user_mode(regs))
+		set_fs(KERNEL_DS);
+	__get_user(insn.word, (unsigned int *)regs->cp0_epc);
+	set_fs(seg);
+
+	switch (insn.i_format.opcode) {
+	/*
+	 * On some CPUs, if an unaligned access happens in a branch delay slot
+	 * and the branch is not taken, EPC points at the branch instruction,
+	 * but the BD bit in the cause register is not set.
+	 */
+	case bcond_op:
+	case j_op:
+	case jal_op:
+	case beq_op:
+	case bne_op:
+	case blez_op:
+	case bgtz_op:
+	case beql_op:
+	case bnel_op:
+	case blezl_op:
+	case bgtzl_op:
+	case jalx_op:
+		return 1;	
+	}
+#endif
+
+	return 0;
 }
 
 static inline unsigned long exception_epc(struct pt_regs *regs)
diff -u -r1.1.2.4 war.h
--- include/asm-mips/war.h 2 Oct 2002 19:42:04 -0000
+++ include/asm-mips/war.h 28 Jan 2003 02:34:13 -0000
@@ -84,4 +84,17 @@
 
 #endif
 
+#if !defined(CONFIG_CPU_MIPS32) && !defined(CONFIG_CPU_MIPS64)
+
+/*
+ * A bunch of CPUs predating the MIPS32 and MIPS64 specs do not always set
+ * the BD bit in c0_cause on an exception.  For those we need to look at
+ * the faulting instruction to deciede if we were faulting in a delay slot.
+ * There might be further CPUs where BD works as expected but for now we're
+ * paranoid.
+ */
+#define BDSLOT_WAR
+
+#endif
+
 #endif /* _ASM_WAR_H */

---

From: Geert Uytterhoeven <[email-masked]>
Date: Tue, 28 Jan 2003 10:30:20 +0100 (MET)

> I'm suggesting this alternative patch below.  Comments?

I tried to write a simple user space test to identify which CPUs suffer from
this, but I wasn't able to trigger it from user space. Perhaps it happens in
kernel space only?

Or perhaps I made a silly mistake, here's the code I used:
--snip--------------------------------------------------------------------------
        .text
        .align  2
        .globl  probe
probe:
        .set    noreorder
        .set    nomacro
        beq     $4,$0,$L2
        lw      $2,0($5)
        j       $31
        nop
$L2:
        li      $2,-559087616                   # 0xffffffffdead0000
        ori     $2,$2,0xbeef
        j       $31
        nop
        .set    macro
        .set    reorder
--snip--------------------------------------------------------------------------
#include <stdio.h>

extern int probe(int a, char *p);

static int data[2] = { 0x01234567, 0x89abcdef };

int main(int argc, char *argv[])
{
    char *p = (char *)data;

    printf("Should print 0x01234567:               0x%08x\n", probe(1, p));
    printf("Should print 0xdeadbeef:               0x%08x\n", probe(0, p));
    printf("Should print 0x23456789 or 0xef012345: 0x%08x\n", probe(1, p+1));
    printf("Should print 0xdeadbeef:               0x%08x\n", probe(0, p+1));
    return 0;
}
--snip--------------------------------------------------------------------------

If it happens, I should get a SIGILL, right?

> +++ include/asm-mips/branch.h 28 Jan 2003 02:34:12 -0000

`seg' is never initialized?

> +	 * but the BD bit in the cause register is not set.

I think you can remove the unconditional jumps, cfr. Mike's comments.

> + * There might be further CPUs where BD works as expected but for now we're

Isn't the Vr4120A core MIPS32?

Gr{oetje,eeting}s,

						Geert

---

From: Ralf Baechle <[email-masked]>
Date: Tue, 28 Jan 2003 12:47:50 +0100

> If it happens, I should get a SIGILL, right?

Right.

Hmm...  If you can't reproduce this anymore I guess we should pull this
patch again?  Despite Mike basically acknowledging that such behaviour
exists I don't feel to well about applying patches for non-reproducable
processor behaviour and would rather prefer to wait until we believe to
know the full details.

?

> `seg' is never initialized?

Yep ...

> I think you can remove the unconditional jumps, cfr. Mike's comments.

That's one of the points where I felt a bit unsafe about the extend of
the issue so I left the jumps in.  Anyway, why should it make a difference
if an instruction is conditional or not?

> Isn't the Vr4120A core MIPS32?

Vr4120 is MIPS III.

  Ralf

---

From: Geert Uytterhoeven <[email-masked]>
Date: Tue, 28 Jan 2003 13:27:42 +0100 (MET)

> patch again?  Despite Mike basically acknowledging that such behaviour

I cannot reproduce it in user space. I can still reproduce it in kernel space
when an incoming TCP connection is accepted:

| 8034d568 <tcp_v4_conn_request>:
| 8034d568:       27bdfe20        addiu   sp,sp,-480
| 8034d56c:       afb601d8        sw      s6,472(sp)
| 8034d570:       afb301cc        sw      s3,460(sp)
| 8034d574:       afb101c4        sw      s1,452(sp)
| 8034d578:       afbf01dc        sw      ra,476(sp)
| 8034d57c:       afb501d4        sw      s5,468(sp)
| 8034d580:       afb401d0        sw      s4,464(sp)
| 8034d584:       afb201c8        sw      s2,456(sp)
| 8034d588:       afb001c0        sw      s0,448(sp)
| 8034d58c:       00a08821        move    s1,a1
| 8034d590:       8ca50020        lw      a1,32(a1)
| 8034d594:       8e260028        lw      a2,40(s1)
| 8034d598:       8e320044        lw      s2,68(s1)
| 8034d59c:       8ca2000c        lw      v0,12(a1)
| 8034d5a0:       00809821        move    s3,a0
| 8034d5a4:       0000b021        move    s6,zero
| 8034d5a8:       afa201b8        sw      v0,440(sp)
| 8034d5ac:       8cc30064        lw      v1,100(a2)
| 8034d5b0:       3c023000        lui     v0,0x3000
| 8034d5b4:       00621824        and     v1,v1,v0
| 8034d5b8:       14600012        bnez    v1,8034d604 <tcp_v4_conn_request+0x9c>
| 8034d5bc:       8cb50010        lw      s5,16(a1)
                                  ^^^^^^^^^^^^^^^^^
This load may cause an unaligned address exception. Sometimes pc (after
correction based on the branch delay flag) points to 8034d5bc, sometimes it
points to 8034d5b8. In the latter case I found out that the branch was not
taken.

> if an instruction is conditional or not?

Jumps are always taken, and the behavior I saw happened when the branch was
untaken (cfr. above).

Gr{oetje,eeting}s,

						Geert

---

From: "Maciej W. Rozycki" <[email-masked]>
Date: Tue, 28 Jan 2003 13:30:03 +0100 (MET)

> processor behaviour and would rather prefer to wait until we believe to

 Agreed, and I believe a run-time check would be better (and trivial as
well).  The (!MIPS32 && !MIPS64) approximation is too rough.

> if an instruction is conditional or not?

 I think jumps cannot be non-taken... 

> > Isn't the Vr4120A core MIPS32?

 Actually I have a datasheet for the Vr4121 (which is a Vr4120 plus some
glue logic for specific peripherals) and it explicitly states whenever
cp0.EPC points to a preceding branch/jump of a faulting instruction, the
cp0.Cause.BD bit is set.  Maybe there is an errata sheet available.

 Additionally the processor is "nice" enough to implement the MIPS III ISA
(with the MIPS16 extension) except ll/sc, lld/scd, sigh...  So the
emulation would need to be ported to the 64-bit kernel if we were to
support this processor in the 64-bit mode. 

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: [email-masked], PGP key available        +

---

From: Ralf Baechle <[email-masked]>
Date: Tue, 28 Jan 2003 13:54:53 +0100

> cp0.Cause.BD bit is set.  Maybe there is an errata sheet available.

Honestly I'd not expect this to be documented in a NEC manual - they
basically look like the description of the processor core is the same for
basically all the Vr4xxx processors and SOCs.

> support this processor in the 64-bit mode. 

Maximum agreement on the "sigh" part ...

  Ralf

---

From: Jun Sun <[email-masked]>
Date: Tue, 28 Jan 2003 09:53:47 -0800

Geert,

I had exactly the same problem with Vr4120A chip!

I have narrowed it down to be a hardware bug.  Basically under
certain conditions, BD flag won't get set.

You can verify that by inserting various number of "nop" just
before the faulting places and observe certain address alignment
would show/hide this bug.

Further more I wrote a standalone kernel code and could not
reproduce it, which means it requires more conditions than just
address alignment.

NEC Europe knows about this problem.  Not sure if they passed
it to Japan where the chip is designed.  Their engineers
even had difficulty to understand what I was talking about. 

(more sighs)

Jun

---

From: "Mike Uhler" <[email-masked]>
Date: Tue, 28 Jan 2003 11:48:56 -0800

> even had difficulty to understand what I was talking about. 

Let me give the list some background on this to aid in understanding.

When the MIPS I Architecture was originally defined (back in
1984), it included the architecturally-visible branch delay slot
that exists in the architecture today.  The Coprocessor 0
EPC register was defined to be the PC at which to restart after
an exception or an interrupt.  However, because an exception or
interrupt could occur while attempting to execute the instruction
in a branch delay slot, EPC could not simply point at that
instruction, because if the branch or jump was taken, restarting
at the delay slot PC doesn't account for the taken branch/jump.
As such, the architecture was specified such that if an exception
or interrupt was detected while attempting to execution the
instruction in a branch delay slot, EPC was defined to receive
the PC of the branch, and the BD bit was set in the Coprocessor 0
Cause register.  Most implementations of the MIPS Architecture did
exactly this.

In a few implementations of the MIPS Architecture (and I can't confirm
nor deny that this is the case with the NEC VR 41xx chips - I simply don't
know), the implementors observed that the restart PC could, in fact,
be the PC of the instruction in the delay slot, but only if the preceding
branch was known to be not-taken.  Restarting a not-taken branch
at the branch is equivalent to restarting at the delay slot in
terms of PC flow.  Note that this assumes that restarting at the
branch would not cause a different decision on the restart as
on the original execution, and this is required by the architecture.

Since the MIPS architecture has no not-taken jump instructions, there
should never be a case in which EPC points at the delay slot of a
jump, nor should there ever be a case in which EPC points at the
delay slot of a taken branch.

In the MIPS32 and MIPS64 Architecture, we explicitly require that the
value in EPC point at the branch/jump and that the BD bit be set in
the Cause register if an exception is detected in the delay slot.
Our compliance testing tests for this, and there are no compliant
implementations of the MIPS32 or MIPS64 Architecture which will
cause EPC to point to the delay slot of the branch (subject, of coure,
to an obscure bug).

As I mentioned earlier, there are some number of implementations of
earlier versions of the MIPS Architecture which apparently have
decided to point EPC at the delay slot instruction in the case of
a not-taken branch.  I can't give you a list of such implementations
because they pre-date our formal MIPS32/MIPS64 compliance testing.
I would hope that the users manual and/or errata sheets for chips
that do this would mention this as an issue.

So, the proposed code that went by on this list earlier can almost
certainly remove the jumps (they are always taken), and only adjust
PC if the previous instruction was a branch.

One word of warning, however:  Note that branch delay slots are
defined as DYNAMIC, not STATIC instructions.  Consider the following
example:

	...
5:	b	20f
	nop
	...
10:	b	someplace
20:	instruction-that-causes-exception

If the PC flow goes executions the branch at label 10 and detects
an exception on the instruction at label 20, EPC should point at
label 10, and the BD bit in Cause should be set.  However, if the branch
at label 5, with the nop in its delay slot, goes directly to the
excepting instruction at label 20, that instruction IS NOT in a
branch delay slot (remember, it's a dynamic relationship, not a
static one), so EPC would point at label 20 and the BD bit in cause
would not be set.

If the patch assumes that one can look backward by one instruction
in the STATIC code to determine if the instruction is in a
delay slot, one can not have code that jumps directly to the
instruction following another branch, as this would cause the
code to assume that it was in the delay slot of the branch.

This is exactly the reason why the architecture is defined in the
way that it is.

If anyone has any other questions, let me know.

/gmu

--

---

From: [email-masked]
Date: 28 Jan 2003 16:30:09 -0500

> code to assume that it was in the delay slot of the branch.

A while back, when working on a different architecture that also had
branch delay slots, it took me a while to get my head around the
branch-in-a-delay-slot case, e.g.

10:  b 100
20:  b 30
30:  foo
...
100: bar

where the actual program flow would be

10
20
100
30

and instruction 100 would be considered to be in the delay slot of 20.

I was *very* happy when I first looked at MIPS to see that this was 
specified as unpredictable, even if it was pretty cool to be able to
make the CPU execute a single instruction in the middle of nowhere. 
Pointless, but cool.  :)

-Justin

---

From: "Mike Uhler" <[email-masked]>
Date: Tue, 28 Jan 2003 13:39:48 -0800

> make the CPU execute a single instruction in the middle of nowhere. 

I presume that you're talking about Sparc, where such a construct is
used to execute a single instruction out of a table.  This is, in
fact, very, very unpredictable on a MIPS implementation, ranging from
reserved instruction, to branching to one of the two branch targets,
to wandering off into hyperspace.  So please do not assume that because
a particular implementation does something that all implementations
do the same thing. In this particular case, I can guarantee you that
you won't like the answer you get.

/gmu

--

---

From: Brad Parker <[email-masked]>
Date: Tue, 28 Jan 2003 20:39:03 -0500

>| 8034d568 <tcp_v4_conn_request>:

I had a problem in tcp_rcv_established() where this "if" would trigger
even though "th->syn" was zero:

...
	if (th->syn && !before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
...

It turned out the tcp header was 'misaligned' after coming across a
usb link.  I never figured out why it was failing, but it was clearly
the emulation code which was doing the wrong thing.  This was on an
alchemy au1000 (MIPS32).

also in the kernel...

-brad

---

From: Ralf Baechle <[email-masked]>
Date: Wed, 29 Jan 2003 07:40:10 +0100

> the emulation code which was doing the wrong thing.  This was on an

A few days ago I fixed a special case in cvs where the unaligned handler
was misshandling the special case where

	bxx	$r1, dest
	load	$r1, offset($r2)

both instruction are using the same register $r1 and the effective address
offset + $r2 was missaligned.  In that case the emulation code was
executing the load instruction first then using the loaded value to deciede
if the branch was taken.

I know the bug was hitting in the netfilter code but chances are there are
other places in the network code affected as well.

  Ralf

---

From: Ralf Baechle <[email-masked]>
Date: Wed, 29 Jan 2003 15:25:43 +0100

Mike,

> Let me give the list some background on this to aid in understanding.

Thanks for elaborating on this problem.

My workaround was trying so deal with a different problem so I'm going to
pull that patch again until the nature of Geert's problem is fully
understood.

  Ralf