Bad MIPS address arithmetic

Bad MIPS address arithmetic

[Paul Koning]

I spotted this in binutils 2.18.

Given the source file:

foo:	ld	$v0,40000($sp)
	jr	$ra

The resulting code is:

	lui	v0, 1
	addu	v0, v0, sp
	jr	ra
	ld	v0, -25536(sp) 

The problem is that this produces wrong addresses in machines with 64
bit registers, if the current sp is 0x7fff0000 or higher.  If so, the
addu produces 0xffffffff8000nnnn in v0, and the ld then references
0xffffffff7fffnnnn which is not likely to be a valid address.

It seems that daddu rather than addu should be used here, for O64 (and
probably N32) ABIs.

	paul

Re: Bad MIPS address arithmetic

[David Daney]

On 05/10/2010 02:17 PM, Paul Koning wrote:
> I spotted this in binutils 2.18.
>
> Given the source file:
>
> foo:	ld	$v0,40000($sp)
> 	jr	$ra
>
> The resulting code is:
>
> 	lui	v0, 1
> 	addu	v0, v0, sp
> 	jr	ra
> 	ld	v0, -25536(sp)
>
> The problem is that this produces wrong addresses in machines with 64
> bit registers, if the current sp is 0x7fff0000 or higher.  If so, the
> addu produces 0xffffffff8000nnnn in v0, and the ld then references
> 0xffffffff7fffnnnn which is not likely to be a valid address.
>

Well things get tricky up there near the top of USEG.  That is why the 
Linux kernel never places the stack in that region.

> It seems that daddu rather than addu should be used here, for O64 (and
> probably N32) ABIs.
>

This is what I get:

$ cat koning.s
foo:	ld	$v0,40000($sp)
	jr	$ra

$ mips64-linux-as --version
GNU assembler (GNU Binutils) 2.20
Copyright 2009 Free Software Foundation, Inc.
This program is free software; you may redistribute it under the terms of
the GNU General Public License version 3 or later.
This program has absolutely no warranty.
This assembler was configured for a target of `mips64-linux'.
$ mips64-linux-as -o koning.o koning.s
$ mips64-linux-objdump -d -r koning.o

koning.o:     file format elf32-ntradbigmips


Disassembly of section .text:

00000000 <foo>:
    0:	3c020001 	lui	v0,0x1
    4:	005d1021 	addu	v0,v0,sp
    8:	03e00008 	jr	ra
    c:	dc429c40 	ld	v0,-25536(v0)

$ mips64-linux-as -mabi=32 -o koning.o koning.s
$ mips64-linux-objdump -d -r koning.o

koning.o:     file format elf32-tradbigmips


Disassembly of section .text:

00000000 <foo>:
    0:	3c010001 	lui	at,0x1
    4:	03a10821 	addu	at,sp,at
    8:	8c229c40 	lw	v0,-25536(at)
    c:	8c239c44 	lw	v1,-25532(at)
   10:	03e00008 	jr	ra
   14:	00000000 	nop
	...

$ mips64-linux-as -mabi=64 -o koning.o koning.s
$ mips64-linux-objdump -d -r koning.o

koning.o:     file format elf64-tradbigmips


Disassembly of section .text:

0000000000000000 <foo>:
    0:	3c020001 	lui	v0,0x1
    4:	005d102d 	daddu	v0,v0,sp
    8:	03e00008 	jr	ra
    c:	dc429c40 	ld	v0,-25536(v0)


So I think it is working as it was intended.  For the default n32 ABI, 
the ADDU is the proper instruction to use for pointer arithmetic.  Other 
ABIs do different things.  If you want code for n64, you should specify 
that when invoking the assembler.  You can also add '.set nomacro' if 
you don't want it to do these weird things.

In MIPS assembly, what you think is an instruction often isn't, the ABI 
and other things have a big influence.

David Daney

RE: Bad MIPS address arithmetic

[Paul Koning]

> Well things get tricky up there near the top of USEG.  That is why the
> Linux kernel never places the stack in that region.

Sure, I suppose it's possible to have the kernel work around the
assembler bug that way.  That's an interesting possibility.
 
> > It seems that daddu rather than addu should be used here, for O64
> (and
> > probably N32) ABIs.
> >
> 
> This is what I get:
> 
> $ cat koning.s
> foo:	ld	$v0,40000($sp)
> 	jr	$ra
> 
> $ mips64-linux-as --version
> GNU assembler (GNU Binutils) 2.20
> Copyright 2009 Free Software Foundation, Inc.
> This program is free software; you may redistribute it under the terms
> of
> the GNU General Public License version 3 or later.
> This program has absolutely no warranty.
> This assembler was configured for a target of `mips64-linux'.
> $ mips64-linux-as -o koning.o koning.s
> $ mips64-linux-objdump -d -r koning.o
> 
> koning.o:     file format elf32-ntradbigmips
> 
> 
> Disassembly of section .text:
> 
> 00000000 <foo>:
>     0:	3c020001 	lui	v0,0x1
>     4:	005d1021 	addu	v0,v0,sp
>     8:	03e00008 	jr	ra
>     c:	dc429c40 	ld	v0,-25536(v0)
> 
> $ mips64-linux-as -mabi=32 -o koning.o koning.s
> $ mips64-linux-objdump -d -r koning.o
> 
> koning.o:     file format elf32-tradbigmips
> 
> 
> Disassembly of section .text:
> 
> 00000000 <foo>:
>     0:	3c010001 	lui	at,0x1
>     4:	03a10821 	addu	at,sp,at
>     8:	8c229c40 	lw	v0,-25536(at)
>     c:	8c239c44 	lw	v1,-25532(at)
>    10:	03e00008 	jr	ra
>    14:	00000000 	nop
> 	...
> 
> $ mips64-linux-as -mabi=64 -o koning.o koning.s
> $ mips64-linux-objdump -d -r koning.o
> 
> koning.o:     file format elf64-tradbigmips
> 
> 
> Disassembly of section .text:
> 
> 0000000000000000 <foo>:
>     0:	3c020001 	lui	v0,0x1
>     4:	005d102d 	daddu	v0,v0,sp
>     8:	03e00008 	jr	ra
>     c:	dc429c40 	ld	v0,-25536(v0)
> 
> 
> So I think it is working as it was intended.  For the default n32 ABI,
> the ADDU is the proper instruction to use for pointer arithmetic.

I don't agree.  Clearly it is flat out wrong in the test case.  

> Other
> ABIs do different things.  If you want code for n64, you should
specify
> that when invoking the assembler.  You can also add '.set nomacro' if
> you don't want it to do these weird things.
> 
> In MIPS assembly, what you think is an instruction often isn't, the
ABI
> and other things have a big influence.

Well, yes, that's an unfortunate and very serious design error dating
back to day 1 of the MIPS assemblers.

The big problem for me is that the code sequence in question comes out
of gcc (V3.3, which we're stuck with for now).  Essentially, what it
means is that a program with a stack frame bigger than 32k may crash in
bizarre ways.

Clearly addu is wrong here.  I believe the right answer is that daddu is
correct for address arithmetic whenever 64 bit registers are used, i.e.,
O64, N32, N64.  In other words, not only for N64 as appears to be the
current assumption.

I need to do some analysis to see if that theory is correct for ksegx
addresses.

	paul

Re: Bad MIPS address arithmetic

[David Daney]

On 05/10/2010 06:11 PM, Paul Koning wrote:
[...]
>> So I think it is working as it was intended.  For the default n32 ABI,
>> the ADDU is the proper instruction to use for pointer arithmetic.
>
> I don't agree.  Clearly it is flat out wrong in the test case.
>

You never said what your criteria for correctness were.  For your two 
line assembly file you are not getting the results you want for some 
specific values of $sp.

If you expand your horizons a little so that they include the code gcc 
will emit for all different types of n32 pointer arithmetic, then I 
think it is not so black and white.

>> Other
>> ABIs do different things.  If you want code for n64, you should
> specify
>> that when invoking the assembler.  You can also add '.set nomacro' if
>> you don't want it to do these weird things.
>>
>> In MIPS assembly, what you think is an instruction often isn't, the
> ABI
>> and other things have a big influence.
>
> Well, yes, that's an unfortunate and very serious design error dating
> back to day 1 of the MIPS assemblers.

They are what they are.  Knowing their limitations, it is possible to 
create a working system.

>
> The big problem for me is that the code sequence in question comes out
> of gcc (V3.3, which we're stuck with for now).  Essentially, what it
> means is that a program with a stack frame bigger than 32k may crash in
> bizarre ways.

... unless you restrict the virtual address range of valid pointers as I 
suggested that the Linux kernel does.

>
> Clearly addu is wrong here.  I believe the right answer is that daddu is
> correct for address arithmetic whenever 64 bit registers are used, i.e.,
> O64, N32, N64.  In other words, not only for N64 as appears to be the
> current assumption.
>

I dissagree, it has nothing to do with the width of the registers.  It 
is the width of the data type that is important.  If your pointers are 
32-bits wide, you should use the corresponding 32-bit instructions to 
manipulate them.  Doing otherwise can result in undefined behavior. 
This is what gcc and binutils are doing.  If you use daddu, you can 
generate register values where the upper 32-bits are non-uniform (not 
all 0 or all 1).  Once you do that, you enter into the world of truly 
undefined behavior.


> I need to do some analysis to see if that theory is correct for ksegx
> addresses.
>
> 	paul
>

RE: Bad MIPS address arithmetic

[Paul Koning]

> >> So I think it is working as it was intended.  For the default n32
> ABI,
> >> the ADDU is the proper instruction to use for pointer arithmetic.
> >
> > I don't agree.  Clearly it is flat out wrong in the test case.
> >
> 
> You never said what your criteria for correctness were.  For your two
> line assembly file you are not getting the results you want for some
> specific values of $sp.

That's true.
 
> If you expand your horizons a little so that they include the code gcc
> will emit for all different types of n32 pointer arithmetic, then I
> think it is not so black and white.

Maybe so.  Maybe not.  I think the issue has to do with instruction
sequences that mix 32 bit sign extended operations with 64 bit
operations.  If you're all one or all the other, the results are always
correct; if you mix then the results can be wrong near the boundaries,
as in this case.

> >
> > Clearly addu is wrong here.  I believe the right answer is that
daddu
> is
> > correct for address arithmetic whenever 64 bit registers are used,
> i.e.,
> > O64, N32, N64.  In other words, not only for N64 as appears to be
the
> > current assumption.
> >
> 
> I dissagree, it has nothing to do with the width of the registers.  It
> is the width of the data type that is important.  If your pointers are
> 32-bits wide, you should use the corresponding 32-bit instructions to
> manipulate them.  Doing otherwise can result in undefined behavior.
> This is what gcc and binutils are doing.  If you use daddu, you can
> generate register values where the upper 32-bits are non-uniform (not
> all 0 or all 1).  Once you do that, you enter into the world of truly
> undefined behavior.

Undefined if you mix 32 and 64 bit operations, yes; that's what the MIPS
book says.

In fact, that is the problem right now.  The current code is the one
that mixes operation sizes.  Specifically, on a machine with 64 bit
registers, effective address arithmetic in load and store (base register
content plus offset) is done in 64 bits, NOT in 32 bits.  So on such
machines, if you add something to a pointer register with an addu, and
then subtract from it with a register offset in a load or store, you
have a mixed operation: 32 bits in the first, 64 in the second.

So I still believe daddu is the right instruction for any 64 bit
register machine.  But changing the address space is probably the
easiest solution so I'll look at that first.

	paul

Re: Bad MIPS address arithmetic

[Maciej W. Rozycki]

On Mon, 10 May 2010, Paul Koning wrote:

> I spotted this in binutils 2.18.
> 
> Given the source file:
> 
> foo:	ld	$v0,40000($sp)
> 	jr	$ra
> 
> The resulting code is:
> 
> 	lui	v0, 1
> 	addu	v0, v0, sp
> 	jr	ra
> 	ld	v0, -25536(sp) 
> 
> The problem is that this produces wrong addresses in machines with 64
> bit registers, if the current sp is 0x7fff0000 or higher.  If so, the
> addu produces 0xffffffff8000nnnn in v0, and the ld then references
> 0xffffffff7fffnnnn which is not likely to be a valid address.
> 
> It seems that daddu rather than addu should be used here, for O64 (and
> probably N32) ABIs.

 I dare not speak of the o64 ABI as its details have always been a mystery 
to me.  But with n32 the code generated is correct.  You can't just offset 
an address of "0x7fff0000 or higher" by 40000, because you are crossing 
from KUSEG to KSEG0 this way.  This is undefined behaviour -- the n32's 
31-bit KUSEG space ends at 0x7fffffff.

 Now I agree there is a problem, namely with legacy 64-bit MIPS hardware 
that did not properly support address space truncation that would 
correctly support the 31-bit user address space suitable for n32 
processes.  The only controlling bit for the 64-bit mode was CP0.Status.UX 
that enabled both 64-bit operations and 64-bit addresses at the same time.  
This was corrected in the MIPS64 ISA with the addition of the 
CP0.Status.PX that only enables 64-bit operations, but keeps addresses 
truncated to 32-bit segments.  With CP0.Status.PX set the LD instruction 
above correctly refers to 0xffffffff8000nnnn.

 The difference is however somewhat academic -- at the kernel level with 
legacy processors you get an unhandled TLBL exception rather than the 
expected AdEL one.  A properly written OS kernel will kill the offender 
with a signal in both cases.

 Even if you're advanced enough to handle the signal sent, then you don't 
really need to take any special precautions -- the faulting address passed 
to the handler has to be properly sign-extended from 32 bits by user 
software (typically by using LW to retrieve) and (at least with Linux) you 
won't notice a difference as a SIGSEGV is sent in response to both 
exceptions under these circumstances.

 Have I made it clear enough?

  Maciej

RE: Bad MIPS address arithmetic

[Paul Koning]

> On Mon, 10 May 2010, Paul Koning wrote:
> 
> > I spotted this in binutils 2.18.
> >
> > Given the source file:
> >
> > foo:	ld	$v0,40000($sp)
> > 	jr	$ra
> >
> > The resulting code is:
> >
> > 	lui	v0, 1
> > 	addu	v0, v0, sp
> > 	jr	ra
> > 	ld	v0, -25536(v0)

(v0) not (sp) -- I transcribed this wrong when I first wrote the note.

> > The problem is that this produces wrong addresses in machines with
64
> > bit registers, if the current sp is 0x7fff0000 or higher.  If so,
the
> > addu produces 0xffffffff8000nnnn in v0, and the ld then references
> > 0xffffffff7fffnnnn which is not likely to be a valid address.
> >
> > It seems that daddu rather than addu should be used here, for O64
> (and
> > probably N32) ABIs.
> 
>  I dare not speak of the o64 ABI as its details have always been a
> mystery
> to me.  But with n32 the code generated is correct.  You can't just
> offset
> an address of "0x7fff0000 or higher" by 40000, because you are
crossing
> from KUSEG to KSEG0 this way.  This is undefined behaviour -- the
n32's
> 31-bit KUSEG space ends at 0x7fffffff.

N32 and O64 are the same from the point of view of address handling.  

The "undefined behavior" is exactly the point I'm complaining about.
The assembler is generating code that fails (exercises undefined
behavior) for some values of SP that are perfectly legal.
 
>  Now I agree there is a problem, namely with legacy 64-bit MIPS
> hardware
> that did not properly support address space truncation that would
> correctly support the 31-bit user address space suitable for n32
> processes.  The only controlling bit for the 64-bit mode was
> CP0.Status.UX
> that enabled both 64-bit operations and 64-bit addresses at the same
> time.
> This was corrected in the MIPS64 ISA with the addition of the
> CP0.Status.PX that only enables 64-bit operations, but keeps addresses
> truncated to 32-bit segments.  With CP0.Status.PX set the LD
> instruction
> above correctly refers to 0xffffffff8000nnnn.
> ...
>  Have I made it clear enough?

I think so.  It looks like N32 and O64 require the kernel to do one of
two things:

1. Set PX in the status register and leave UX clear, or
2. Leave the upper 64k of useg unmapped (so, for example, the stack
would start at 0x7fff0000 or below).

The code produces ffffffff8000nnnn in v0.  With 64 bit address
arithmetic, the memory reference to -25536(v0) produces an address of
the form ffffffff7fffnnnn which is what causes the trouble.  I take it
from what you're saying that setting PX and clearing UX will cause the
processor to ignore the upper 32 bits in that address calculation and
instead use the sign extended lower 32 bits, so I get 000000007fffnnnn
which is the right answer.  Section 4.9 in the MIPS64 spec volume 3
describes this reasonably clearly.

My kernel is currently setting UX (it doesn't have a symbolic name for
PX at all) but my platform does support PX so that seems like the
simplest solution.  Alternatively, I can move the initial SP, that isn't
all that hard either.

Thanks for the help.

	paul 

RE: Bad MIPS address arithmetic

[Maciej W. Rozycki]

On Wed, 12 May 2010, Paul Koning wrote:

> The code produces ffffffff8000nnnn in v0.  With 64 bit address
> arithmetic, the memory reference to -25536(v0) produces an address of
> the form ffffffff7fffnnnn which is what causes the trouble.  I take it
> from what you're saying that setting PX and clearing UX will cause the
> processor to ignore the upper 32 bits in that address calculation and
> instead use the sign extended lower 32 bits, so I get 000000007fffnnnn
> which is the right answer.  Section 4.9 in the MIPS64 spec volume 3
> describes this reasonably clearly.

 I believe this is the case although I haven't verified it empirically 
(technically, this should be the equivalent of what ADDIU does on a 64-bit 
processor, even though a separate adder will be used in the address 
generation path; likewise I wouldn't blame a CPU implementation if it did 
something unpredictable if the base contained in the register was not a 
properly sign-extended 32-bit number before offsetting).

> My kernel is currently setting UX (it doesn't have a symbolic name for
> PX at all) but my platform does support PX so that seems like the
> simplest solution.  Alternatively, I can move the initial SP, that isn't
> all that hard either.

 Please note that clearing UX has a side effect of using the TLB Refill 
exception vector rather than the XTLB Refill one.  The MMU register state 
prepared for the handler remains the same so it's up to the kernel to take 
advantage of this distinction or not, but anyway it has to take it into 
account somehow.

> Thanks for the help.

 You are welcome.

  Maciej