[ELF] -z combreloc: sort dynamic relocations by (symbol_index,r_offset)

[MaskRay]

Summary

Fixes PR41692.

We currently sort dynamic relocations by (!is_relative,symbol_index).
Change it to (symbol_index,r_offset). We still place relative
relocations first because we only emit R_*_RELATIVE as dynamic
relocations with 0 symbol index.

This makes readelf -r debugging easier (relocations to the same symbol
are ordered by r_offset).

Refactor the test combreloc.s (renamed from combrelocs.s) to check
R_X86_64_RELATIVE, and delete --expand-relocs.

[MaskRay]

ld.bfd's sorting logic is unnecessarily complex.
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=41f61c65a2e1cfdb4aca3bccf6e11025495ba02e;f=bfd/elflink.c#l9305
It uses elf_link_sort_cmp1 to sort relative relocations, then elf_link_sort_cmp2 to sort the non-relative relocations. The two functions can be combined to one: sorting by the triple (!IsRelative, SymIndex, r_offset)

gold's rule is at https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=41f61c65a2e1cfdb4aca3bccf6e11025495ba02e;f=gold/output.cc#l1180
As @mcgrathr mentioned in PR41692, it has the fourth key SymType, which probably just serves the purpose of std::stable_sort.

By using std::make_tuple(), this added a small cost as we unconditionally call A.getOffset() and B.getOffset() - this cost doesn't matter.

• Non-PIE executables/shared objects don't have many dynamic relocations.
• Most dynamic relocations of an PIE are relative relocations. The comparison function has to call getOffset() anyway.

[grimar]

But why this is an issue? Both PR and this patch description does not answer that it seems.
Is it just a cosmetic change for the output?

[mcgrathr]

The sorting behavior is entirely an optimization for locality at dynamic reloc time. Both locality of symtab indices and locality of reloc offsets are useful to that goal.

[grimar]

In D61477#1490167, @mcgrathr wrote:

The sorting behavior is entirely an optimization for locality at dynamic reloc time. Both locality of symtab indices and locality of reloc offsets are useful to that goal.

When we initially implemented sorting of relocations, we sorted by symbol index only, because testing showed that it was the only
thing that made a difference: https://reviews.llvm.org/D19528#423828

After that at some point we started sorting by RelativeRel to set the DT_RELACOUNT tag.
(Setting this tag was needed for FreeBSD I think, but I do not remember honestly).

So what I want to say that probably sorting by offset is not really usefull. At least would be nice to see the numbers before doing that.

[MaskRay]

For the PR41692 reproduce tarball, ld.lld @response.txt --pack-dyn-relocs=none (without the patch) shows the relative relocations aren't sorted by r_offset.

# I deleted some other flags to compare the result with gold and ld.bfd
Relocation section '.rela.dyn' at offset 0x14008 contains 65020 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000405000  0000000000000008 R_X86_64_RELATIVE                         1954a5
0000000000405010  0000000000000008 R_X86_64_RELATIVE                         19eb00
000000000049d0f0  0000000000000008 R_X86_64_RELATIVE                         1ee500
000000000049d100  0000000000000008 R_X86_64_RELATIVE                         1ee54f
000000000049d110  0000000000000008 R_X86_64_RELATIVE                         1ee525
0000000000403000  0000000000000008 R_X86_64_RELATIVE                         1ee580
0000000000403008  0000000000000008 R_X86_64_RELATIVE                         1ee5a0
0000000000403010  0000000000000008 R_X86_64_RELATIVE                         0

Relocations sorted by r_offset would make a poor person's life easier when debugging with readelf -r :) (I use readelf -r much while debugging numerous internal issues)

[grimar]

In D61477#1491929, @MaskRay wrote:

For the PR41692 reproduce tarball, ld.lld @response.txt --pack-dyn-relocs=none (without the patch) shows the relative relocations aren't sorted by r_offset.

# I deleted some other flags to compare the result with gold and ld.bfd
Relocation section '.rela.dyn' at offset 0x14008 contains 65020 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000405000  0000000000000008 R_X86_64_RELATIVE                         1954a5
0000000000405010  0000000000000008 R_X86_64_RELATIVE                         19eb00
000000000049d0f0  0000000000000008 R_X86_64_RELATIVE                         1ee500
000000000049d100  0000000000000008 R_X86_64_RELATIVE                         1ee54f
000000000049d110  0000000000000008 R_X86_64_RELATIVE                         1ee525
0000000000403000  0000000000000008 R_X86_64_RELATIVE                         1ee580
0000000000403008  0000000000000008 R_X86_64_RELATIVE                         1ee5a0
0000000000403010  0000000000000008 R_X86_64_RELATIVE                         0

Relocations sorted by r_offset would make a poor person's life easier when debugging with readelf -r :) (I use readelf -r much while debugging numerous internal issues)

Then this is a cosmetic change, as I supposed initially. I'll leave it up to Rui I think.

[mcgrathr]

Sorting R_*_RELATIVE relocs first and setting REL(A)COUNT is a format requirement, period. It's not a debatable question of optimization.

The multi-level sorting behavior here makes lld consistent with the GNU linkers, which it is not today.

[ruiu]

Can you give me a pointer to the formal spec and also include that to the patch description?

[MaskRay]

I can't find a spec of DT_RELACOUNT in gABI or psABI. I find its definition in Linux Standard Base but can't find its description. elfutils has a lint tool, it checks some properties of DT_RELACOUNT but doesn't require its entries to be sorted.

In glibc, there is a commit with changelog "If DT_GNU_PRELINKED, DT_RELACOUNT relocations can be skipped."
In Oracle Solaris Linkers and Libraries Guide, it is describe but nothing is said about the sorted r_offset: "Combining relocation records in this manner enables all RELATIVE relocations to be grouped together. All symbolic relocations are sorted by symbol name. The grouping of RELATIVE relocations permits optimized runtime processing using the DT_RELACOUNT/DT_RELCOUNT .dynamic entries. Sorted symbolic entries help reduce runtime symbol lookup"
FreeBSD copied the definition to their sys/sys/elf_common.h in 2016 from somewhere, but its rtld doesn't use DT_RELACOUNT. musl doesn't use DT_RELACOUNT.

I don't know if DT_RELACOUNT was a glibc invention or a Sun invention. To be honest, if it is not that we've added it in the first place, I wouldn't suggest adding it :D

To me this is a cosmetic change. You make the decision if it is worth doing.

[grimar]

In D61477#1492293, @mcgrathr wrote:

Sorting R_*_RELATIVE relocs first and setting REL(A)COUNT is a format requirement, period. It's not a debatable question of optimization.

I never said we should stop doing that. Sorting by an offset implemented in this patch is completely different story.

The multi-level sorting behavior here makes lld consistent with the GNU linkers, which it is not today.

Above you wrote "The sorting behavior is entirely an optimization for locality at dynamic reloc time. Both locality of symtab indices and locality of reloc offsets are useful to that goal."
I pointed to Rafael's comment saying that sorting by offsets did not show any improvements during the testing and was not useful that time.

Now you're talking about consistency reasons. We are inconsistent with the GNU linkers in a many things and not always we want to fix it.
"consistency" by itself usually is not a reason for doing a change.

One reasonable argument to land this I saw in this thread was "Relocations sorted by r_offset would make a poor person's life easier when debugging with readelf -r :)"
It sounds useful.

In D61477#1492925, @ruiu wrote:

Can you give me a pointer to the formal spec and also include that to the patch description?

FWIW here is the most detailed explanation of the feature I found were:
https://www.airs.com/blog/archives/186
http://people.redhat.com/jakub/prelink.pdf (p.2)

I says it worth sorting by r_offset though. But out tests showed that sorting did not improve anything (https://reviews.llvm.org/D19528#423828).
So this patch seems to be for a nice output only (i.e. not about the optimization).
I am not against doing this, but I think we should explicitly mention this in comments and/or patch description.

[grimar]

In D61477#1492942, @MaskRay wrote:

I don't know if DT_RELACOUNT was a glibc invention or a Sun invention. To be honest, if it is not that we've added it in the first place, I wouldn't suggest adding it :D

I am not sure why we are discussing DT_RELACOUNT :), but there was a solid reason to add it I believe:
https://reviews.llvm.org/D23661

[MaskRay]

Add comment

[MaskRay]

In D61477#1492961, @grimar wrote:

In D61477#1492942, @MaskRay wrote:

I don't know if DT_RELACOUNT was a glibc invention or a Sun invention. To be honest, if it is not that we've added it in the first place, I wouldn't suggest adding it :D

I am not sure why we are discussing DT_RELACOUNT :), but there was a solid reason to add it I believe:
https://reviews.llvm.org/D23661

It's fine. Not too complex anyway :) (off-topic: musl could leverage the same optimization http://git.musl-libc.org/cgit/musl/tree/ldso/dynlink.c#n342 but it doesn't bother doing that probably because the improvement is insignificant)

[MaskRay]

This is useful to compare the result with ld.bfd to check if we emit more or fewer relocations. (This helped D62107)

[MaskRay]

How about

return std::make_tuple(A.getSymIndex(), A.getOffset()) < std::make_tuple(B.getSymIndex(), B.getOffset());

? i.e. don't check if this is a relative relocation. In the dynamic loader, if SymIndex is 0, IMHO the dynamic relocation can only be relative (R_*_NONE doesn't make sense).

[MaskRay]

Sort by (symbol_index,r_offset)

[MaskRay]

Inline the comparator

[ruiu]

LGTM

Recently I started thinking of adding a "greasing" mechanism to the linker output. Modern network protocols such as QUIC adds some randomness (such as adding an unsupported extension chunk to a packet to make sure that an unsupported chunk is just skipped by the peer), so that the specification doesn't stick to a specific implementation. That technique is called greasing. It might be interesting to use the same technique for the linker output, to make sure that the consumer side works as required by the spec.

ELF/SyntheticSections.cpp

 RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
     : RelocationBaseSection(Name, Config->IsRela ? SHT_RELA : SHT_REL,
                             Config->IsRela ? DT_RELA : DT_REL,
                             Config->IsRela ? DT_RELASZ : DT_RELSZ),
       Sort(Sort) {
   this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
 }
 
-static bool compRelocations(const DynamicReloc &A, const DynamicReloc &B) {
-  bool AIsRel = A.Type == Target->RelativeRel;
-  bool BIsRel = B.Type == Target->RelativeRel;
-  if (AIsRel != BIsRel)
-    return AIsRel;
-  return A.getSymIndex() < B.getSymIndex();
-}
-
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
+  // Sort symbol index then by r_offset. Because we only emit R_*_RELATIVE as
+  // dynamic relocations with symbol index 0, this essentially places
+  // R_*_RELATIVE first (required by DT_REL[A]COUNT).
   if (Sort)
-    llvm::stable_sort(Relocs, compRelocations);
+    llvm::stable_sort(Relocs, [](const DynamicReloc &A, const DynamicReloc &B) {
+      return std::make_tuple(A.getSymIndex(), A.getOffset()) <
+             std::make_tuple(B.getSymIndex(), B.getOffset());
+    });
 
   for (const DynamicReloc &Rel : Relocs) {
     encodeDynamicReloc<ELFT>(reinterpret_cast<Elf_Rela *>(Buf), Rel);
     Buf += Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
   }
 }
 
 template <class ELFT>

test/ELF/combreloc.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: echo 'mov aaa@gotpcrel(%rip), %rax' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+
+# RUN: ld.lld -shared %t.o %t1.o -o %t.so
+# RUN: llvm-readobj -r --dynamic-table %t.so | FileCheck %s
+# RUN: ld.lld -shared %t.o %t1.o -o %t.so -z combreloc
+# RUN: llvm-readobj -r --dynamic-table %t.so | FileCheck %s
+
+# -z combreloc is the default: sort relocations by (SymIndex, r_offset), and
+# emit DT_RELACOUNT (except on MIPS) to indicate the number of relative
+# relocations.
+
+# CHECK:      Relocations [
+# CHECK-NEXT:   Section ({{.*}}) .rela.dyn {
+# CHECK-NEXT:     0x3020 R_X86_64_RELATIVE - 0x3028
+# CHECK-NEXT:     0x20B0 R_X86_64_GLOB_DAT aaa 0x0
+# CHECK-NEXT:     0x3000 R_X86_64_64 aaa 0x0
+# CHECK-NEXT:     0x3018 R_X86_64_64 aaa 0x0
+# CHECK-NEXT:     0x3010 R_X86_64_64 bbb 0x0
+# CHECK-NEXT:     0x3008 R_X86_64_64 ccc 0x0
+# CHECK-NEXT:   }
+# CHECK:      DynamicSection [
+# CHECK:        RELACOUNT 1
+
+# RUN: ld.lld -z nocombreloc -shared %t.o %t1.o -o %t.so
+# RUN: llvm-readobj -r --dynamic-table %t.so | FileCheck --check-prefix=NOCOMB %s
+
+# NOCOMB:      Relocations [
+# NOCOMB-NEXT:   Section ({{.*}}) .rela.dyn {
+# NOCOMB-NEXT:     0x3000 R_X86_64_64 aaa 0x0
+# NOCOMB-NEXT:     0x3008 R_X86_64_64 ccc 0x0
+# NOCOMB-NEXT:     0x3010 R_X86_64_64 bbb 0x0
+# NOCOMB-NEXT:     0x3018 R_X86_64_64 aaa 0x0
+# NOCOMB-NEXT:     0x3020 R_X86_64_RELATIVE - 0x3028
+# NOCOMB-NEXT:     0x20A0 R_X86_64_GLOB_DAT aaa 0x0
+# NOCOMB-NEXT:   }
+# NOCOMB:      DynamicSection [
+# NOCOMB-NOT:    RELACOUNT
+
+.data
+ .quad aaa
+ .quad ccc
+ .quad bbb
+ .quad aaa
+ .quad relative
+relative:

test/ELF/combrelocs.s

-# REQUIRES: x86
-
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
-# RUN: ld.lld -shared %t.o -o %t.out
-# RUN: llvm-readobj -r --expand-relocs --dynamic-table %t.out | FileCheck %s
-
-# RUN: ld.lld -shared %t.o -o %t.out -z combreloc
-# RUN: llvm-readobj -r --expand-relocs --dynamic-table %t.out | FileCheck %s
-
-# CHECK:      Relocations [
-# CHECK-NEXT:   Section ({{.*}}) .rela.dyn {
-# CHECK-NEXT:     Relocation {
-# CHECK-NEXT:       Offset: 0x2000
-# CHECK-NEXT:       Type: R_X86_64_64
-# CHECK-NEXT:       Symbol: aaa (1)
-# CHECK-NEXT:       Addend: 0x0
-# CHECK-NEXT:     }
-# CHECK-NEXT:     Relocation {
-# CHECK-NEXT:       Offset: 0x2018
-# CHECK-NEXT:       Type: R_X86_64_64
-# CHECK-NEXT:       Symbol: aaa (1)
-# CHECK-NEXT:       Addend: 0x0
-# CHECK-NEXT:     }
-# CHECK-NEXT:     Relocation {
-# CHECK-NEXT:       Offset: 0x2010
-# CHECK-NEXT:       Type: R_X86_64_64
-# CHECK-NEXT:       Symbol: bbb (2)
-# CHECK-NEXT:       Addend: 0x0
-# CHECK-NEXT:     }
-# CHECK-NEXT:     Relocation {
-# CHECK-NEXT:       Offset: 0x2008
-# CHECK-NEXT:       Type: R_X86_64_64
-# CHECK-NEXT:       Symbol: ccc (3)
-# CHECK-NEXT:       Addend: 0x0
-# CHECK-NEXT:     }
-# CHECK-NEXT:     Relocation {
-# CHECK-NEXT:       Offset: 0x2020
-# CHECK-NEXT:       Type: R_X86_64_64
-# CHECK-NEXT:       Symbol: ddd (4)
-# CHECK-NEXT:       Addend: 0x0
-# CHECK-NEXT:     }
-# CHECK-NEXT:   }
-# CHECK-NEXT: ]
-# CHECK:      DynamicSection [
-# CHECK-NEXT:   Tag
-# CHECK-NOT:    RELACOUNT
-
-# RUN: ld.lld -z nocombreloc -shared %t.o -o %t.out
-# RUN: llvm-readobj -r --expand-relocs --dynamic-table %t.out | \
-# RUN:    FileCheck --check-prefix=NOCOMB %s
-
-# NOCOMB:      Relocations [
-# NOCOMB-NEXT:    Section ({{.*}}) .rela.dyn {
-# NOCOMB-NEXT:     Relocation {
-# NOCOMB-NEXT:       Offset: 0x2000
-# NOCOMB-NEXT:       Type: R_X86_64_64
-# NOCOMB-NEXT:       Symbol: aaa (1)
-# NOCOMB-NEXT:       Addend: 0x0
-# NOCOMB-NEXT:     }
-# NOCOMB-NEXT:     Relocation {
-# NOCOMB-NEXT:       Offset: 0x2008
-# NOCOMB-NEXT:       Type: R_X86_64_64
-# NOCOMB-NEXT:       Symbol: ccc (3)
-# NOCOMB-NEXT:       Addend: 0x0
-# NOCOMB-NEXT:     }
-# NOCOMB-NEXT:     Relocation {
-# NOCOMB-NEXT:       Offset: 0x2010
-# NOCOMB-NEXT:       Type: R_X86_64_64
-# NOCOMB-NEXT:       Symbol: bbb (2)
-# NOCOMB-NEXT:       Addend: 0x0
-# NOCOMB-NEXT:     }
-# NOCOMB-NEXT:     Relocation {
-# NOCOMB-NEXT:       Offset: 0x2018
-# NOCOMB-NEXT:       Type: R_X86_64_64
-# NOCOMB-NEXT:       Symbol: aaa (1)
-# NOCOMB-NEXT:       Addend: 0x0
-# NOCOMB-NEXT:     }
-# NOCOMB-NEXT:     Relocation {
-# NOCOMB-NEXT:       Offset: 0x2020
-# NOCOMB-NEXT:       Type: R_X86_64_64
-# NOCOMB-NEXT:       Symbol: ddd (4)
-# NOCOMB-NEXT:       Addend: 0x0
-# NOCOMB-NEXT:     }
-# NOCOMB-NEXT:   }
-# NOCOMB-NEXT:  ]
-# NOCOMB:      DynamicSection [
-# NOCOMB-NEXT:   Tag
-# NOCOMB-NOT:    RELACOUNT
-
-.data
- .quad aaa
- .quad ccc
- .quad bbb
- .quad aaa
- .quad ddd

test/ELF/i386-got-and-copy.s

 # REQUIRES: x86
 
 # If there are two relocations such that the first one requires
 # dynamic COPY relocation, the second one requires GOT entry
 # creation, linker should create both - dynamic relocation
 # and GOT entry.
 
 # RUN: llvm-mc -filetype=obj -triple=i386-pc-linux \
 # RUN:         %S/Inputs/copy-in-shared.s -o %t.so.o
 # RUN: llvm-mc -filetype=obj -triple=i386-pc-linux %s -o %t.o
 # RUN: ld.lld %t.so.o -shared -o %t.so
 # RUN: ld.lld --hash-style=sysv %t.o %t.so -o %t.exe
 # RUN: llvm-readobj -r %t.exe | FileCheck %s
 
 # CHECK:      Relocations [
 # CHECK-NEXT:   Section (4) .rel.dyn {
-# CHECK-NEXT:     0x{{[0-9A-F]+}} R_386_COPY foo
 # CHECK-NEXT:     0x{{[0-9A-F]+}} R_386_GLOB_DAT foo
+# CHECK-NEXT:     0x{{[0-9A-F]+}} R_386_COPY foo
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
   .text
   .global _start
 _start:
   movl $foo, (%esp)     # R_386_32 - requires R_386_COPY relocation
   movl foo@GOT, %eax    # R_386_GOT32 - requires GOT entry

test/ELF/mips-mgot.s

 # GOT:      Relocations [
 # GOT-NEXT:   Section (7) .rel.dyn {
 # GOT-NEXT:     0x70018 R_MIPS_REL32 - 0x0
 # GOT-NEXT:     0x7001C R_MIPS_REL32 - 0x0
 # GOT-NEXT:     0x70020 R_MIPS_REL32 - 0x0
 # GOT-NEXT:     0x70024 R_MIPS_REL32 - 0x0
 # GOT-NEXT:     0x70028 R_MIPS_REL32 - 0x0
 # GOT-NEXT:     0x7002C R_MIPS_REL32 - 0x0
-# GOT-NEXT:     0x70030 R_MIPS_REL32 foo0 0x0
-# GOT-NEXT:     0x70034 R_MIPS_REL32 foo2 0x0
 # GOT-NEXT:     0x70044 R_MIPS_TLS_DTPMOD32 - 0x0
 # GOT-NEXT:     0x70010 R_MIPS_TLS_TPREL32 tls0 0x0
 # GOT-NEXT:     0x70038 R_MIPS_TLS_TPREL32 tls0 0x0
 # GOT-NEXT:     0x7003C R_MIPS_TLS_DTPMOD32 tls0 0x0
 # GOT-NEXT:     0x70040 R_MIPS_TLS_DTPREL32 tls0 0x0
 # GOT-NEXT:     0x70014 R_MIPS_TLS_TPREL32 tls1 0x0
+# GOT-NEXT:     0x70030 R_MIPS_REL32 foo0 0x0
+# GOT-NEXT:     0x70034 R_MIPS_REL32 foo2 0x0
 # GOT-NEXT:   }
 # GOT-NEXT: ]
 
 # GOT:      DynamicSymbols [
 # GOT:        Symbol {
 # GOT:          Name: foo0
 # GOT-NEXT:     Value: 0x10000
 # GOT:        }