.rela.eh_frame isn't sorted by r_offset about riscv-binutils-gdb HOT 6 CLOSED

Ya, that seems fishy. We also rely on relocations being in order (though just for high-performance relaxations, not correctness), so I'd consider this wrong as well.

Do you happen to know if it's always the SET6/SUB6 relocations that are out of order? They're all added as a second pass here

https://github.com/riscv/riscv-binutils-gdb/blob/riscv-binutils-2.29/gas/config/tc-riscv.c#L1940

so I could entirely believe that's what's causing the reordering (though that looks like it's putting them in the correct order).

from riscv-binutils-gdb.

@palmer-dabbelt That's the only case I've found (as it is linked with -Os) so far; I haven't investigated further.

from riscv-binutils-gdb.

I've constructed a minimal case to produce an out-of-order SETN/SUBN pair:

foo:
.cfi_startproc
    j   1f
# .skip 0x100
1:
.cfi_escape 0
.cfi_endproc

bar:
.cfi_startproc
.cfi_endproc

$ riscv32-unknown-linux-gnu-as test.s -o test.o && riscv32-unknown-linux-gnu-readelf -r test.o
Relocation section '.rela.eh_frame' at offset 0x164 contains 8 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
0000001c  00000439 R_RISCV_32_PCREL  00000000   .L0  + 0
00000020  00000723 R_RISCV_ADD32     00000004   .L0  + 0
00000020  00000427 R_RISCV_SUB32     00000000   .L0  + 0
00000030  00000839 R_RISCV_32_PCREL  00000004   .L0  + 0
00000034  00000a23 R_RISCV_ADD32     00000004   .L0  + 0
00000034  00000827 R_RISCV_SUB32     00000004   .L0  + 0
00000025  00000635 R_RISCV_SET6      00000004   .L0  + 0
00000025  00000434 R_RISCV_SUB6      00000000   .L0  + 0

If you uncomment the .skip 0x100 directive you get an out-of-order SET16/SUB16 pair, so I think the issue affects all DW_CFA_advance_loc* operands.

from riscv-binutils-gdb.

There is no requirement in the ELF standard that relocs be sorted by offset.

Gas does a single pass over the input file, creating relocs as it goes, which are appended to a list, so normally they will be sorted by offset because of how gas works. However, any reloc created after reading the input file will be appended to the same list, and hence will appear out of order. For riscv, this includes any reloc created by relaxation, which includes for instance R_RISCV_BRANCH in text sections, R_RISCV_ADD16 in .debug_line sections, and R_RISCV_SET8 in .eh_frame.

What is different about RISC-V is the fact that we have linker relaxations that change code size, and hence we can't actually resolve some relocations at gas relaxation time, and so we end up with relaxations passed through to the linker that normal targets would not have. It is these relaxations that are showing up out of order. Normal targets would not have relaxations against sections like debug_line and eh_frame and hence would not have this problem.

Risc-v is certainly not the only target with out-of-order relocs though. The MIPS port deliberately reorders relocations based on the symbol, not the offset, because you can have multiple LO16 relocs using a single HI16 reloc. To make sure the right HI16 reloc is matched with the right LO16 reloc, even when instruction scheduling reorders instructions, they have to deliberately reorder the relocs by symbol. I see some other gas ports doing the same thing: iq2000, m32r, and mep. There may also be other gas ports doing the same thing, but just not obviously enough that I can find it with grep.

Here is a simple mips example showing out-of-order relocs.

rohan:2277$ cat tmp.s
lui $4,%hi(foo)
lui $5,%hi(bar)
lh $4,%lo(foo)($4)
lh $5,%lo(bar)($5)
rohan:2278$ gas/as-new tmp.s
rohan:2279$ binutils/objdump -r a.out

a.out: file format elf32-bigmips

RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
00000000 R_MIPS_HI16 foo
00000008 R_MIPS_LO16 foo
00000004 R_MIPS_HI16 bar
0000000c R_MIPS_LO16 bar

rohan:2280$

This sorting by symbol, not offset, is required by the MIPS ABI and so is not a bug. There is a MIPS clang/llvm port, so lld would have to handle this correctly if/when there is an lld port for MIPS.

It would be possible to sort relocs by offset for RISC-V currently, as we don't have any ABI requirement like MIPS. However, doing this would be inconvenient, and might make it impossible to add some relocation related optimizations later. I'm not going to do this without a very good reason to do so. Just saying that lld expects it is not sufficient reason. If there is some flaw with lld that prevents you from making it work correctly, then that might be sufficient reason, but I'd want details explaining why lld can't be fixed to handle this correctly.

from riscv-binutils-gdb.

Thanks for looking into this, Jim!

I think we're going to WONTFIX this, as it'll be a huge pain to fix these on our end. It looks like this is just another case where RISC-V's aggressive use of linker relaxation finds some edge cases. I think we still rely on some amount of relocation ordering when relaxing, but there we're essentially just optimizing for the common case where they're sorted to avoid an extra bookkeeping pass. We should eventually fix that, maybe if we ever convert everything to use R_RISCV_DELETE?

@PkmX I'm going to close this, but feel free to re-open it if you have more info.

from riscv-binutils-gdb.

The issue was a limitation on lld's end to translate offsets in input .eh_frame to output .eh_frame. If relocations are sorted by r_offset (and thus as each relocation is processed the offset increases monotonically), instead of searching for the whole EH frame for the record containing the offset, it can just continue linear search starting from the last record.

Anyway, I'll fix this on lld's end. Thanks for your inputs!

from riscv-binutils-gdb.