GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Project Revolution]

Hi GCC folks,

We were working on a decompilation project for a Nintendo 64 title and attempting to enable support for using GCC instead of the emulated IRIX compiler and we ran into a big problem with how GCC generates relocations for the MIPS target which appears to show that GCC is generating non-compliant relocation data for MIPS target.

In summary: the Nintendo 64 title has a limited amount of RAM (4MB, 8MB if you add Expansion Pak, which our ROM target uses for debug reasons); in order to accomplish this, the codebase packs actors/objects into overlays which the game determines need to be loaded per room/system transition. Once loaded into RAM, the game applies the overlay's relocations generated at compile time to the code to move the data and code correctly and make sure the jumps and loads get recalculated correctly.

Unfortunately.. there's a problem. Here's the function that applies the relocs to MIPS: https://github.com/zeldaret/oot/blob/master/src/code/relocation.c

While enabling overlays to be recompiled with GCC instead of the IDO compiler, we have found the relocs generated did not guarantee 0x45/0x46 (Hi/lo pairs) pairs to be 1:1, and GCC would share any possible hi/lo in O2 mode. While O0 and O1 gcc overlays will work, or even Og, this is not a solution for an N64 ROM due to limited RAM and space will quickly run out since memory is so tight. While investigating why gcc will optimize relocs, we have found the following:

The MIPS ABI specified at https://refspecs.linuxfoundation.org/elf/mipsabi.pdf on pages 79-80 (page 82 regarding the GP caveat) demands that hi/los be in pairs). Thus, we have found that the reloc data generated erroneously applies the relocation twice. Several LOs following a HI seems to be in a spec, but several HIs following a LO does not. This is causing issues for our relocation due to the relocs being applied incorrectly as a result of non-compliant relocation data. It turned out this reloc optimization is caused by an unmentioned, undocumented GNU extension.

We have found the GNU extension was ONLY ever mentioned here: https://people.freebsd.org/~adrian/mips/20160819-mips-elf-reloc-gcc-5.3-3.diff

Here is the file we compiled: https://github.com/zeldaret/oot/blob/master/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c

This is the line we used to compile it:

mips-linux-gnu-gcc -c -O2 -c -G 0 -nostdinc -Iinclude -Isrc -Iassets -Ibuild -I. -DNON_MATCHING=1 -DNON_EQUIVALENT=1 -DAVOID_UB=1 -mno-shared -march=vr4300 -mfix4300 -mabi=32 -mhard-float -mdivide-breaks -fno-stack-protector -fno-common -fno-zero-initialized-in-bss -mno-abicalls -fno-strict-aliasing -fno-inline-functions -fno-inline-small-functions -fno-toplevel-reorder -ffreestanding -fwrapv -Wall -Wextra -g -fno-gcse -fno-cse-follow-jumps -mno-load-store-pairs -mno-explicit-relocs -fno-peephole2 -mips3 -o build/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.o src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c

To note, we have tried with and without explicit relocs and with and without peephole2 and with and without mips2/3 and it didnt make a difference: the relocs were still noncompliant per the PDF posted earlier. We need a way to turn this undocumented GNU extension off because it is causing relocs when optimized to not be processed correctly. To note, our use case is attempting to compile this repo with GCC (this file is a test case) but if you were to compile the ROM with the Heishi4 file being compiled as GCC using the above call (make any Makefile alterations to force the object to be GCC), spawn on the SPOT00 map at the start of the game and go inside the castle town area and observe the crash which takes like 60 seconds. This is ultimately what we're trying to fix which following this rabbit hole leads us to this GNU extension in a haystack hunt. Can you guys help us resolve this?

v/r,
Revo

Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Andrew Pinski]

On Thu, Feb 18, 2021 at 12:15 PM Project Revolution via Gcc
<gcc@gcc.gnu.org> wrote:
>
> Hi GCC folks,
>
> We were working on a decompilation project for a Nintendo 64 title and attempting to enable support for using GCC instead of the emulated IRIX compiler and we ran into a big problem with how GCC generates relocations for the MIPS target which appears to show that GCC is generating non-compliant relocation data for MIPS target.

Try compiling with -fno-section-anchors .
https://gcc.gnu.org/legacy-ml/gcc-help/2009-07/msg00455.html

Thanks,
Andrew

>
> In summary: the Nintendo 64 title has a limited amount of RAM (4MB, 8MB if you add Expansion Pak, which our ROM target uses for debug reasons); in order to accomplish this, the codebase packs actors/objects into overlays which the game determines need to be loaded per room/system transition. Once loaded into RAM, the game applies the overlay's relocations generated at compile time to the code to move the data and code correctly and make sure the jumps and loads get recalculated correctly.
>
> Unfortunately.. there's a problem. Here's the function that applies the relocs to MIPS: https://github.com/zeldaret/oot/blob/master/src/code/relocation.c
>
> While enabling overlays to be recompiled with GCC instead of the IDO compiler, we have found the relocs generated did not guarantee 0x45/0x46 (Hi/lo pairs) pairs to be 1:1, and GCC would share any possible hi/lo in O2 mode. While O0 and O1 gcc overlays will work, or even Og, this is not a solution for an N64 ROM due to limited RAM and space will quickly run out since memory is so tight. While investigating why gcc will optimize relocs, we have found the following:
>
> The MIPS ABI specified at https://refspecs.linuxfoundation.org/elf/mipsabi.pdf on pages 79-80 (page 82 regarding the GP caveat) demands that hi/los be in pairs). Thus, we have found that the reloc data generated erroneously applies the relocation twice. Several LOs following a HI seems to be in a spec, but several HIs following a LO does not. This is causing issues for our relocation due to the relocs being applied incorrectly as a result of non-compliant relocation data. It turned out this reloc optimization is caused by an unmentioned, undocumented GNU extension.
>
> We have found the GNU extension was ONLY ever mentioned here: https://people.freebsd.org/~adrian/mips/20160819-mips-elf-reloc-gcc-5.3-3.diff
>
> Here is the file we compiled: https://github.com/zeldaret/oot/blob/master/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> This is the line we used to compile it:
>
> mips-linux-gnu-gcc -c -O2 -c -G 0 -nostdinc -Iinclude -Isrc -Iassets -Ibuild -I. -DNON_MATCHING=1 -DNON_EQUIVALENT=1 -DAVOID_UB=1 -mno-shared -march=vr4300 -mfix4300 -mabi=32 -mhard-float -mdivide-breaks -fno-stack-protector -fno-common -fno-zero-initialized-in-bss -mno-abicalls -fno-strict-aliasing -fno-inline-functions -fno-inline-small-functions -fno-toplevel-reorder -ffreestanding -fwrapv -Wall -Wextra -g -fno-gcse -fno-cse-follow-jumps -mno-load-store-pairs -mno-explicit-relocs -fno-peephole2 -mips3 -o build/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.o src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> To note, we have tried with and without explicit relocs and with and without peephole2 and with and without mips2/3 and it didnt make a difference: the relocs were still noncompliant per the PDF posted earlier. We need a way to turn this undocumented GNU extension off because it is causing relocs when optimized to not be processed correctly. To note, our use case is attempting to compile this repo with GCC (this file is a test case) but if you were to compile the ROM with the Heishi4 file being compiled as GCC using the above call (make any Makefile alterations to force the object to be GCC), spawn on the SPOT00 map at the start of the game and go inside the castle town area and observe the crash which takes like 60 seconds. This is ultimately what we're trying to fix which following this rabbit hole leads us to this GNU extension in a haystack hunt. Can you guys help us resolve this?
>
> v/r,
> Revo
>

Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Project Revolution]

[-- Attachment #1: Type: text/plain, Size: 5299 bytes --]

We do -fno-toplevel-reorders, which implies section anchors are off. We recompiled, but:

...
0000052c  00004505 R_MIPS_HI16       00000000   gSaveContext
00000530  00004506 R_MIPS_LO16       00000000   gSaveContext
00000538  00004705 R_MIPS_HI16       0000057c   func_80A56614
00000b60  00004705 R_MIPS_HI16       0000057c   func_80A56614
0000053c  00004706 R_MIPS_LO16       0000057c   func_80A56614
0000055c  00003304 R_MIPS_26         00000000   osSyncPrintf
00000558  00001305 R_MIPS_HI16       00000160   $LC17
...

...
.word 0x45000538
.word 0x45000B60
...

As seen above, there is still a double HI here, which was present before. Finishing compiling the ROM still results in the same crash due to the bad reloc data.

Sorry, didnt do Reply All last time.

________________________________
From: Andrew Pinski <pinskia@gmail.com>
Sent: Thursday, February 18, 2021 3:28 PM
To: Project Revolution <projectrevotpp@hotmail.com>
Cc: gcc@gcc.gnu.org <gcc@gcc.gnu.org>; kenixwhisperwind@gmail.com <kenixwhisperwind@gmail.com>
Subject: Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

On Thu, Feb 18, 2021 at 12:15 PM Project Revolution via Gcc
<gcc@gcc.gnu.org> wrote:
>
> Hi GCC folks,
>
> We were working on a decompilation project for a Nintendo 64 title and attempting to enable support for using GCC instead of the emulated IRIX compiler and we ran into a big problem with how GCC generates relocations for the MIPS target which appears to show that GCC is generating non-compliant relocation data for MIPS target.

Try compiling with -fno-section-anchors .
https://gcc.gnu.org/legacy-ml/gcc-help/2009-07/msg00455.html

Thanks,
Andrew

>
> In summary: the Nintendo 64 title has a limited amount of RAM (4MB, 8MB if you add Expansion Pak, which our ROM target uses for debug reasons); in order to accomplish this, the codebase packs actors/objects into overlays which the game determines need to be loaded per room/system transition. Once loaded into RAM, the game applies the overlay's relocations generated at compile time to the code to move the data and code correctly and make sure the jumps and loads get recalculated correctly.
>
> Unfortunately.. there's a problem. Here's the function that applies the relocs to MIPS: https://github.com/zeldaret/oot/blob/master/src/code/relocation.c
>
> While enabling overlays to be recompiled with GCC instead of the IDO compiler, we have found the relocs generated did not guarantee 0x45/0x46 (Hi/lo pairs) pairs to be 1:1, and GCC would share any possible hi/lo in O2 mode. While O0 and O1 gcc overlays will work, or even Og, this is not a solution for an N64 ROM due to limited RAM and space will quickly run out since memory is so tight. While investigating why gcc will optimize relocs, we have found the following:
>
> The MIPS ABI specified at https://refspecs.linuxfoundation.org/elf/mipsabi.pdf on pages 79-80 (page 82 regarding the GP caveat) demands that hi/los be in pairs). Thus, we have found that the reloc data generated erroneously applies the relocation twice. Several LOs following a HI seems to be in a spec, but several HIs following a LO does not. This is causing issues for our relocation due to the relocs being applied incorrectly as a result of non-compliant relocation data. It turned out this reloc optimization is caused by an unmentioned, undocumented GNU extension.
>
> We have found the GNU extension was ONLY ever mentioned here: https://people.freebsd.org/~adrian/mips/20160819-mips-elf-reloc-gcc-5.3-3.diff
>
> Here is the file we compiled: https://github.com/zeldaret/oot/blob/master/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> This is the line we used to compile it:
>
> mips-linux-gnu-gcc -c -O2 -c -G 0 -nostdinc -Iinclude -Isrc -Iassets -Ibuild -I. -DNON_MATCHING=1 -DNON_EQUIVALENT=1 -DAVOID_UB=1 -mno-shared -march=vr4300 -mfix4300 -mabi=32 -mhard-float -mdivide-breaks -fno-stack-protector -fno-common -fno-zero-initialized-in-bss -mno-abicalls -fno-strict-aliasing -fno-inline-functions -fno-inline-small-functions -fno-toplevel-reorder -ffreestanding -fwrapv -Wall -Wextra -g -fno-gcse -fno-cse-follow-jumps -mno-load-store-pairs -mno-explicit-relocs -fno-peephole2 -mips3 -o build/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.o src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> To note, we have tried with and without explicit relocs and with and without peephole2 and with and without mips2/3 and it didnt make a difference: the relocs were still noncompliant per the PDF posted earlier. We need a way to turn this undocumented GNU extension off because it is causing relocs when optimized to not be processed correctly. To note, our use case is attempting to compile this repo with GCC (this file is a test case) but if you were to compile the ROM with the Heishi4 file being compiled as GCC using the above call (make any Makefile alterations to force the object to be GCC), spawn on the SPOT00 map at the start of the game and go inside the castle town area and observe the crash which takes like 60 seconds. This is ultimately what we're trying to fix which following this rabbit hole leads us to this GNU extension in a haystack hunt. Can you guys help us resolve this?
>
> v/r,
> Revo
>

[-- Attachment #2: z_en_heishi4.o --]
[-- Type: application/octet-stream, Size: 365664 bytes --]

Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Project Revolution]

Gentlemen: this was fixed, although it's a bit of an odd solution. We had to combine both -mno-explicit-relocs and -mno-split-addresses, even though per the MIPS compiler documentation explicit relocs supersedes the split addresses one. Neither of these options on their own work, and it appears as though they're same result individually until you enable both of these. It's really odd, but we're not questioning it since it resolved our issue.

________________________________
From: Andrew Pinski <pinskia@gmail.com>
Sent: Thursday, February 18, 2021 3:28 PM
To: Project Revolution <projectrevotpp@hotmail.com>
Cc: gcc@gcc.gnu.org <gcc@gcc.gnu.org>; kenixwhisperwind@gmail.com <kenixwhisperwind@gmail.com>
Subject: Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

On Thu, Feb 18, 2021 at 12:15 PM Project Revolution via Gcc
<gcc@gcc.gnu.org> wrote:
>
> Hi GCC folks,
>
> We were working on a decompilation project for a Nintendo 64 title and attempting to enable support for using GCC instead of the emulated IRIX compiler and we ran into a big problem with how GCC generates relocations for the MIPS target which appears to show that GCC is generating non-compliant relocation data for MIPS target.

Try compiling with -fno-section-anchors .
https://gcc.gnu.org/legacy-ml/gcc-help/2009-07/msg00455.html

Thanks,
Andrew

>
> In summary: the Nintendo 64 title has a limited amount of RAM (4MB, 8MB if you add Expansion Pak, which our ROM target uses for debug reasons); in order to accomplish this, the codebase packs actors/objects into overlays which the game determines need to be loaded per room/system transition. Once loaded into RAM, the game applies the overlay's relocations generated at compile time to the code to move the data and code correctly and make sure the jumps and loads get recalculated correctly.
>
> Unfortunately.. there's a problem. Here's the function that applies the relocs to MIPS: https://github.com/zeldaret/oot/blob/master/src/code/relocation.c
>
> While enabling overlays to be recompiled with GCC instead of the IDO compiler, we have found the relocs generated did not guarantee 0x45/0x46 (Hi/lo pairs) pairs to be 1:1, and GCC would share any possible hi/lo in O2 mode. While O0 and O1 gcc overlays will work, or even Og, this is not a solution for an N64 ROM due to limited RAM and space will quickly run out since memory is so tight. While investigating why gcc will optimize relocs, we have found the following:
>
> The MIPS ABI specified at https://refspecs.linuxfoundation.org/elf/mipsabi.pdf on pages 79-80 (page 82 regarding the GP caveat) demands that hi/los be in pairs). Thus, we have found that the reloc data generated erroneously applies the relocation twice. Several LOs following a HI seems to be in a spec, but several HIs following a LO does not. This is causing issues for our relocation due to the relocs being applied incorrectly as a result of non-compliant relocation data. It turned out this reloc optimization is caused by an unmentioned, undocumented GNU extension.
>
> We have found the GNU extension was ONLY ever mentioned here: https://people.freebsd.org/~adrian/mips/20160819-mips-elf-reloc-gcc-5.3-3.diff
>
> Here is the file we compiled: https://github.com/zeldaret/oot/blob/master/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> This is the line we used to compile it:
>
> mips-linux-gnu-gcc -c -O2 -c -G 0 -nostdinc -Iinclude -Isrc -Iassets -Ibuild -I. -DNON_MATCHING=1 -DNON_EQUIVALENT=1 -DAVOID_UB=1 -mno-shared -march=vr4300 -mfix4300 -mabi=32 -mhard-float -mdivide-breaks -fno-stack-protector -fno-common -fno-zero-initialized-in-bss -mno-abicalls -fno-strict-aliasing -fno-inline-functions -fno-inline-small-functions -fno-toplevel-reorder -ffreestanding -fwrapv -Wall -Wextra -g -fno-gcse -fno-cse-follow-jumps -mno-load-store-pairs -mno-explicit-relocs -fno-peephole2 -mips3 -o build/src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.o src/overlays/actors/ovl_En_Heishi4/z_en_heishi4.c
>
> To note, we have tried with and without explicit relocs and with and without peephole2 and with and without mips2/3 and it didnt make a difference: the relocs were still noncompliant per the PDF posted earlier. We need a way to turn this undocumented GNU extension off because it is causing relocs when optimized to not be processed correctly. To note, our use case is attempting to compile this repo with GCC (this file is a test case) but if you were to compile the ROM with the Heishi4 file being compiled as GCC using the above call (make any Makefile alterations to force the object to be GCC), spawn on the SPOT00 map at the start of the game and go inside the castle town area and observe the crash which takes like 60 seconds. This is ultimately what we're trying to fix which following this rabbit hole leads us to this GNU extension in a haystack hunt. Can you guys help us resolve this?
>
> v/r,
> Revo
>

Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Maciej W. Rozycki]

On Fri, 19 Feb 2021, Project Revolution via Gcc wrote:

> Gentlemen: this was fixed, although it's a bit of an odd solution. We 
> had to combine both -mno-explicit-relocs and -mno-split-addresses, even 
> though per the MIPS compiler documentation explicit relocs supersedes 
> the split addresses one. Neither of these options on their own work, and 
> it appears as though they're same result individually until you enable 
> both of these. It's really odd, but we're not questioning it since it 
> resolved our issue.

 The GNU extension that permits multiple R_MIPS_HI16 relocations to be 
matched with one R_MIPS_LO16 relocation for the ABIs such as o32 that use 
the REL relocation format lets the compiler make optimisations that would 
otherwise not be possible.  A typical use case is moving a LUI instruction 
targetted by multiple branches into the respective delay slots, resulting 
in overall shrinking of code by one instruction, such as transforming this 
(delay-slot instructions conventionally indented by one space):

	.set	noreorder
# ...
	beq	$2, $3, $L16
	 nop
# ...
$L16:
	lui	$4, %hi(foo)
	lw	$5, %lo(foo)($4)
# ...
	bltz	$4, $L16
	 nop

into this:

	.set	noreorder
# ...
	beq	$2, $3, $L16
	 lui	$4, %hi(foo)
# ...
$L16:
	lw	$5, %lo(foo)($4)
# ...
	bltz	$4, $L16
	 lui	$4, %hi(foo)

(depending on the execution flow, optimisation options and the ISA level 
chosen branch-likely instructions might be used instead).

 I agree the outcome of the years of MIPS psABI development reflected in 
what GCC and GNU binutils produce nowadays hasn't been properly documented 
and sources of information may be scarce.  The original SVR4 MIPS psABI 
document has had its issues and I believe no exact implementation exists, 
including though not limited to SGI IRIX.

 That said attempts were made in the past to document the state of affairs 
and here's one kept by archive.org that actually mentions the feature: 
<https://web.archive.org/web/20140908233719/https://dmz-portal.mips.com/wiki/MIPS_relocation_types#R_MIPS_HI16>.
The original has been lost however in the turbulent history of the various 
MIPS companies.

 I'm glad to hear you have found a usable workaround.  Otherwise I think 
we might consider adding an option to GCC to disable this psABI extension, 
however offhand I am not sure how difficult it would be to implement.

 It looks to me however that you actually have control over the relocation 
processing code you have referred, so how about improving it to handle the 
GNU R_MIPS_HI16 extension as well?

 It should be straightforward as proved by the usual consumers of MIPS 
object code, such as the GNU linker, the Linux kernel module loader, etc.  
It should give you a smaller code footprint too, to say nothing of the 
size regression the use of `-mno-explicit-relocs' usually results in.

 Have you considered it?

  Maciej

Re: GCC generates non-compliant MIPS relocation data? Obscure GNU extension?

[Maciej W. Rozycki]

On Fri, 19 Feb 2021, Maciej W. Rozycki wrote:

>  It looks to me however that you actually have control over the relocation 
> processing code you have referred, so how about improving it to handle the 
> GNU R_MIPS_HI16 extension as well?

 FWIW note that the extension has been around for ~25 years now (which I 
forgot to mention previously).

  Maciej