R_RISCV_ALIGN friendly to linkers not supporting relaxation (riscv_relax_delete_bytes)

[MaskRay]

In ELF, many relocation types capable of linker optimization are pure optional features: R_AVR_CALL, R_PPC64_PCREL_OPT, R_X86_64_GOTPCRELX, R_X86_64_REX_GOTPCRELX, TLS relocation types supporting GD->LE/GD->IE/LD->LE/etc optimizations. A linker not understanding the advanced feature can provide the basic feature and move on. However, R_RISCV_ALIGN is different.

Currently R_RISCV_ALIGN just encodes the expected alignment. Can it encode the actual bytes of NOPs beside the expected alignment?
Then linkers not supporting linker relaxation can happily accept -mrelax object files.

There are several schemes

• Encode the actual bytes of NOPs in the symbol part of the r_info field. The associated symbol can be absolute (st_shndx==SHN_ABS).
• Encode the actual bytes of NOPs in the high bits of the r_addend field.
• Introduce a new relocation type used together with R_RISCV_ALIGN.

The third approach is probably least favored. The first one should be compatible with existing implementations.

There would add additional complexity to the only linker implementation today: GNU ld.
Skimming bfd/elfnn-riscv.c:riscv_relax_delete_bytes, this probably won't be too difficult.

https://maskray.me/blog/2021-03-14-the-dark-side-of-riscv-linker-relaxation (Apologies for the title:) Someone said I probably should have postponed it to 05-04 😹)

[kito-cheng]

@Nelson1225 @jrtc27 @PkmX @kuanlinchentw

[kito-cheng]

@MaskRay I assume linker not supporting relaxation means NO instructions deletion during linking process, correct me if I misunderstand.

I would suggest add new relocation for a relax-free-safe, the reason is I think it would require different behavior of NOP padding, we are always padding N - 2 byte of NOP before the .align or .p2align, no matter it's already align or not, so that means we might not satisfy the alignment requirement if there is no NOP deletion.

e.g.

$ cat foo.s
foo:
        add a0, a0, a0
        add a0, a0, a0
        .align 3 # align to 8 byte
        sub a0, a0, a0
        ret

But currently we'll padding 6 byte NOP before the align point, the sub isn't align to 8 byte if we don't delete any NOP!

$ riscv64-unknown-elf-as -mrelax foo.s -o foo.o -march=rv64gc
$ riscv64-unknown-elf-objdump -dr foo.o 
foo.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <foo>:
   0:   952a                    add     a0,a0,a0
   2:   952a                    add     a0,a0,a0
   4:   0001                    nop
                        4: R_RISCV_ALIGN        *ABS*+0x6
   6:   00000013                nop
   a:   8d09                    sub     a0,a0,a0
   c:   8082                    ret
        ...

So in this case, we only need to padding 4 byte in this case, and then it's relax-free-safe and also satisfy the alignment requirement.

$ riscv64-unknown-elf-as -mrelax foo.s -o foo.o -march=rv64gc
$ riscv64-unknown-elf-objdump -dr foo.o 
foo.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <foo>:
   0:   952a                    add     a0,a0,a0
   2:   952a                    add     a0,a0,a0
                        4: R_RISCV_ALIGN        *ABS*+0x6
   4:   00000013                nop
   8:   8d09                    sub     a0,a0,a0
   a:   8082                    ret
        ...

But the behavior of R_RISCV_ALIGN is changed, so I think this will cause problem for backward compatible problem.

---

And I guess this behavior will also cause the relaxation process more complicate, linker might need to insert NOP during relaxation process, it's always complicated than deletion/shrink only, consider following case:

$ cat foo.s 
foo:
        call bar
        add a0, a0, a0
        add a0, a0, a0
        .align 3 # align to 8 byte
        sub a0, a0, a0
        ret
$ riscv64-unknown-elf-as -mrelax foo.s -o foo.o -march=rv64gc
$ riscv64-unknown-elf-objdump -dr foo.o 

foo.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <foo>:
   0:   00000097                auipc   ra,0x0
                        0: R_RISCV_CALL bar
                        0: R_RISCV_RELAX        *ABS*
   4:   000080e7                jalr    ra # 0 <foo>
                        10: R_RISCV_ALIGN_NEW
   8:   8d09                    sub     a0,a0,a0
  10:   8082                    ret
...

If we the function call could be relaxed into only jalr only...the alignment requirement is not satisfied now:

0000000000000000 <foo>:
   0:   000080e7                jalr    ra # 0 <foo>
                        10: R_RISCV_ALIGN_NEW       *ABS*+0x6
   4:   8d09                    sub     a0,a0,a0
   6:   8082                    ret

We need to insert 4 byte NOP to fix the alignment requirement:

0000000000000000 <foo>:
   0:   000080e7                jalr    ra # 0 <foo>
   4:   00000013                nop
                        10: R_RISCV_ALIGN_NEW       *ABS*+0x6
   8:   8d09                    sub     a0,a0,a0
  10:   8082                    ret

[jim-wilson]

It is always safe to delete bytes at link time. However, adding bytes is not always safe. That may cause symbols to end up out-of-bounds for a compressed branch, or may cause a regular conditional branch target to end up out of bounds, etc. GNU as will generate compressed branches when it can determine that they are safe to use. And GCC will generate conditional branches when it can determine that they are safe to use. Hence the current implementation takes the safe approach of adding the maximum bytes that might be required at assembly time, and then we delete extra bytes at link time. I don't think that there is a way to fix this and still have relaxation work. Anything that requires adding bytes at link time to make alignment work is going to be a major project, and it will be difficult to find anyone with the skills and time necessary to do the work. Plus it will destabilize the GNU toolchain until all of the bugs are found and fixed which is undesirable.

lld doesn't need full relaxation support. You just need a pre-pass that finds the R_RISCV_ALIGN and deletes the extra nops, and then you can link normally without relaxation. This does reqjuire updating info as you delete nops, relocation offsets, function sizes, etc.

Another alternative would be to treat relaxation as a multilib, and have a toolchain build libraries with and without relaxation.

I suppose another option would be to make the GNU toolchain ignore alignment directives by default, and then require users to add an option to enable alignment, thus the output would work by default with LLD. However, this punishes GNU toolchain users, and thus I wouldn't be happy with it.

[palmer-dabbelt]

I haven't actually read this thread, so this may just be a complete non-sequitur, but:

This isn't the first time we ran into this issue. I don't know if we ever wrote anything down and I think this was before Kito was around, but IIRC Jim and I spent some time trying to sort out a better way to do alignment back when were kept running into those compressed alignment bugs. There are currently two issue with R_RISCV_ALIGN that we can fix at the same time:

• Processing of R_RISCV_ALIGN is required for correct operation, as R_RISCV_ALIGN is all but guaranteed to incorrectly align the target address.
• R_RISCV_ALIGN falls over when users insert .byte into text segments, because we would need 2**n-1 bytes to guarantee alignment (and we only have 2**n-2 bytes, because we don't have 1-byte instructions).

We can't just change the number of NOP bytes encoded by R_RISCV_ALIGN, as that would be an ABI break. The original solution I remember was to add something like R_RISCV_ALIGN_DOWN (don't really care about the name, maybe we alias the old one to R_RISCV_ALIGN_UP though) with different semantics: rather than aligning to the next greater power of two, it aligns to the next smaller power of two. This would allow us to insert 2**n-m bytes of NOPs, with m being a free variable used to align the address in the input section. That would allow linkers that want to avoid shifting bytes around just copy the addresses over, which still allowing higher performance linkers to delete arbitrary bytes. Linkers that don't delete bytes pay an extra cost for that alignment, but there's really no way around that -- if you know you're generating code for a linker that doesn't relax you can do a better job at a bunch of stuff anyway, so just use -mno-relax.

There may be a way to do this without introducing a linker upgrade requirement: just encode two back-to-back R_RISCV_ALIGN directives, with the second one having m+2 bytes. The second relocation can always be processed with 0 bytes, so it should be safe for old linkers. New linkers that don't want to delete bytes can just verify that the back-to-back relocatoins result in correct behavior by checking to see that there are no symbols or instructions in the middle. Not sure if this actually works, though, as I just came up with it.

[PkmX]

AFAIK R_RISCV_ALIGN already encodes the number of nop bytes in addend, and it is always alignment - 2.

Both workarounds to create object files that can accommodate both relaxing and non-relaxing linkers seem to just penalize both:

• For non-relaxing linkers they always need to pay additional 2^n bytes of nop when linking objects that were meant for relaxation
• Those extra nops may further disable some assembler's compressed branch/jump conversion, which can't be recovered even by linkers that do perform relaxation.

For me it seems like the easiest solution would be just multilibing mno-relax if your toolchain needs to support non-relaxing linkers.

[kito-cheng]

We are not going this way, and LLD has supported that now, gonna close this issue :)

[MaskRay]

Closing is fine. The design is really "the damage has been done, and existing toolchain won't change, so new ones have to follow" scenario :(