[BOLT] Optimizing immediate relocation with addends produces incorrect assembly

[Lawqup]

I ran into an issue running BOLT on a program that accesses a global struct field provided by the linker. When accessing a field of that struct, the optimized binary wipes the addend and instead replaces reads of that field with reads of the struct+0.

Versions of things

I tested with both x86 and aarch64 and managed to reproduce.

$ llvm-bolt --version
LLVM (http://llvm.org/):
  LLVM version 19.0.0git
  Optimized build with assertions.
BOLT revision bb6a4850553dd4140a5bd63187ec1b14d0b731f9

$ gcc --version                                                                                                
gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-17)

Repro

This is a minimal repro on x86.

The following is the C, print_global.c

#include <stdio.h>
#include <stdint.h>

struct build_id_note {
  char pad[16];
  uint8_t hash[20];
};

extern const struct build_id_note build_id_note;

void print_build_id()
{
	int x;

	for (x = 0; x < 20; x++) {
		printf("%02hhx", build_id_note.hash[x]);
	}
        printf("\n");
}

int main() {
        print_build_id();
        return 0;
}

I used the default linker script outputted by the -Wl,-verbose gcc flag, then inserted the build_id_note at an absolute location right under that first PROVIDE in build_id.ld, like so:

/* first bit of default linker script removed */
SECTIONS
{
  /* Read-only sections, merged into text segment: */
  PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000)); . = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;
  .note.gnu.build-id (0x400200):
   {
    build_id_note = ABSOLUTE(.);
    *(.note.gnu.build-id)
   }
  /* rest of default linker script removed */
}

This is compiled with

gcc -o print_global print_global.c -Wl,-T,build_id.ld -Wl,--emit-relocs -Wl,--build-id=sha1

Then bolting:

$ llvm-bolt ./print_global -o print_global.bolted --funcs print_build_id         
BOLT-INFO: Target architecture: x86_64
BOLT-INFO: BOLT version: bb6a4850553dd4140a5bd63187ec1b14d0b731f9
BOLT-INFO: first alloc address is 0x200000
BOLT-INFO: creating new program header table at address 0x800000, offset 0x600000
BOLT-INFO: enabling relocation mode
BOLT-INFO: enabling -align-macro-fusion=all since no profile was specified
BOLT-INFO: enabling lite mode
BOLT-INFO: 0 out of 12 functions in the binary (0.0%) have non-empty execution profile
BOLT-INFO: setting _end to 0xa001cc
BOLT-INFO: patched build-id (flipped last bit)

The output of the non-bolted binary is:

$ ./print_global
74007820799e8dc7eb6ff742fe419c5866842b5b

Yet, the bolted binary produces the wrong result

$ ./print_global.bolted                                                                      
040000001400000003000000474e550074007820

Of course, the build id is still as expected for the bolted binary:

$ readelf -n print_global.bolted 
Displaying notes found in: .note.gnu.build-id
  Owner                 Data size       Description
  GNU                  0x00000014       NT_GNU_BUILD_ID (unique build ID bitstring)
    Build ID: 74007820799e8dc7eb6ff742fe419c5866842b5a

So this is a case where BOLT leads to incorrect runtime behavior. Inspecting the assembly, we see the root of the problem is that the immediate address for build_id_note.hash is missing the addend and thus we print starting from the pad field:

Non-bolted asm:

$ gdb -batch -ex "disassemble print_build_id" print_global                
Dump of assembler code for function print_build_id:
   0x00000000004004e7 <+0>:     push   %rbp
   0x00000000004004e8 <+1>:     mov    %rsp,%rbp
   0x00000000004004eb <+4>:     sub    $0x10,%rsp
   0x00000000004004ef <+8>:     movl   $0x0,-0x4(%rbp)
   0x00000000004004f6 <+15>:    jmp    0x40051c <print_build_id+53>
   0x00000000004004f8 <+17>:    mov    -0x4(%rbp),%eax
   0x00000000004004fb <+20>:    cltq   
   0x00000000004004fd <+22>:    movzbl 0x400210(%rax),%eax <---------- Access of build_id_note.hash
   0x0000000000400504 <+29>:    movzbl %al,%eax
   0x0000000000400507 <+32>:    mov    %eax,%esi
   0x0000000000400509 <+34>:    mov    $0x4005d0,%edi
   0x000000000040050e <+39>:    mov    $0x0,%eax
   0x0000000000400513 <+44>:    callq  0x400410 <printf@plt>
   0x0000000000400518 <+49>:    addl   $0x1,-0x4(%rbp)
   0x000000000040051c <+53>:    cmpl   $0x13,-0x4(%rbp)
   0x0000000000400520 <+57>:    jle    0x4004f8 <print_build_id+17>
   0x0000000000400522 <+59>:    mov    $0xa,%edi
   0x0000000000400527 <+64>:    callq  0x400400 <putchar@plt>
   0x000000000040052c <+69>:    nop
   0x000000000040052d <+70>:    leaveq 
   0x000000000040052e <+71>:    retq   
End of assembler dump.

Bolted asm:

$ gdb -batch -ex "disassemble print_build_id" print_global.bolted                             
Dump of assembler code for function print_build_id:
   0x0000000000a00000 <+0>:     push   %rbp
   0x0000000000a00001 <+1>:     mov    %rsp,%rbp
   0x0000000000a00004 <+4>:     sub    $0x10,%rsp
   0x0000000000a00008 <+8>:     movl   $0x0,-0x4(%rbp)
   0x0000000000a0000f <+15>:    jmp    0xa00035 <print_build_id+53>
   0x0000000000a00011 <+17>:    mov    -0x4(%rbp),%eax
   0x0000000000a00014 <+20>:    cltq   
   0x0000000000a00016 <+22>:    movzbl 0x400200(%rax),%eax <---------- Uh oh, should be 0x400210
   0x0000000000a0001d <+29>:    movzbl %al,%eax
   0x0000000000a00020 <+32>:    mov    %eax,%esi
   0x0000000000a00022 <+34>:    mov    $0x4005d0,%edi
   0x0000000000a00027 <+39>:    mov    $0x0,%eax
   0x0000000000a0002c <+44>:    callq  0x400410 <printf@plt>
   0x0000000000a00031 <+49>:    addl   $0x1,-0x4(%rbp)
   0x0000000000a00035 <+53>:    cmpl   $0x13,-0x4(%rbp)
   0x0000000000a00039 <+57>:    jle    0xa00011 <print_build_id+17>
   0x0000000000a0003b <+59>:    mov    $0xa,%edi
   0x0000000000a00040 <+64>:    callq  0x400400 <putchar@plt>
   0x0000000000a00045 <+69>:    leaveq 
   0x0000000000a00046 <+70>:    retq   
End of assembler dump.

[yota9]

Hello! Thanks for raise an issue, should be fixed by #100890

[s-dag]

Hi @yota9, thanks for taking a look. We have found that at least on AAarch64 our linker's behavior was not correct and it should not have generated a relocation for an absolute symbol. When tested on a toolchain with the fix here, the relocation was not generated so BOLT and pre-BOLT assembly were both correct. We still think this should be fixed in BOLT as well so it works correctly with older toolchains and had come up with a similar patch to yours. This may explain why you were not able to reproduce it locally if you were using a newer toolchain.

[yota9]

@s-dag Hi! I agree that in this case using GOT table is excess on the first place. With different options clang/gcc would output different assembly that would have different impact on BOLT. But BOLT patch fixes other "legal" problems too, we still need to apply it, so I think I would be able to push it ASAP when someone from meta team would review it :)

[johndoe2012]

Hello @yota9,
not sure i understand. why do we need bolt to process it to use GOT table, is it a difference between clang and gcc behavior? because according to the ld toolchain fix, on aarch64 the relocation for ABS symbols should not be emitted at all thus no need to be handled by bolt relocation pass. so here the expected behavior would be simply to ignore any seen relocation for ABS symbols right? then for example we would have the following on aarch64

+       // This might be a relocation for an ABS symbols like __global_pointer$ on
+       // RISC-V
+-      ContainingBF->addRelocation(Rel.getOffset(), ReferencedSymbol,
+-                                  Rel.getType(), 0,
+-                                  cantFail(Symbol.getValue()));
++      // on aarch64 with ld version prior to 2.40 relocation is also mistakenly
++      // generated for an ABS symbol. in this case we ignore such relocation without
++      // rewriting
++      if (!IsAArch64) {
++        ContainingBF->addRelocation(Rel.getOffset(), ReferencedSymbol,
++                                    Rel.getType(), 0,
++                                    cantFail(Symbol.getValue()));
++      }
+       return;

[yota9]

@johndoe2012 Hello!
Sorry, I might not understand your question properly, but we need to process it with the GOT table because originally the binary has a GOT relocation and a GOT access to get the symbol. We are not creating any GOT access by this code or near it, we only preserve it if it was originally built this way. If original binary was built with the ld fix above it won't have GOT access and thus won't have it in bolted binary too.

[johndoe2012]

Hello @yota9,
while testing the patch another issue surfaces regarding the handling of R_AARCH64_ADR_PREL_PG_HI21 relocs of ABS symbols in our environment. we dont have much detail yet but is working on a reproducer and more digging into the root cause.

regarding my previous comment, i was talking about two approaches on the fix:

• ignore relocs handling for abs symbol, do nothing if not risc-v and return immediate. (my example)
• do not add relocs if not risc-v at the fixed line, but fall through into the rest of relocs handling. (your patch)

considering the right behavior is not to generate relocs for abs symbol on aarch64, wouldn't ignoring it be the correct action here?

Thanks,

[yota9]

Hello @johndoe2012! Sorry, at this point I could not tell much without looking at your binary and the problem you observe :( Currently I don't see any problems with my patch but observe some fixed test cases for both aarch64 and x86. So please provide the binary and exact place in it where you observe incorrect behaviour.

[s-dag]

Hi @yota9, we had to prioritize the dynamic linking issue first but we will try to come up with a simple enough reproducer here again for the relocation of absolute symbols. We're seeing with #100890 (and yes it does fix build id reproducer above), relocation of absolute symbols are still handled incorrectly on Aarch64.