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

[MaskRay]

Summary

We currently sort dynamic relocations by (!is_relative,symbol_index).
Add r_offset as the third key. 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.

The difference from the reverted D61477 is that we add !is_relative as
the first key. In local dynamic TLS model, DTPMOD (e.g.
R_ARM_TLS_DTPMOD32 R_X86_64_DTPMOD and R_PPC{,64}_DTPMOD) may use 0 as
the symbol index.

[grimar]

LGTM

[MaskRay]

FreeBSD ld.so/musl don't use DT_RELACOUNT. In glibc, glibc/sysdeps/x86_64/dl-machine.h (but not on other arch) has an assertion that the first DT_REL[A]COUNT relocations must all be relative.

@evgeny777 I'm curious how your dynamic loader uses DT_REL{,A}COUNT since you created D23661:)

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 by (!IsRelative,SymIndex,r_offset). DT_REL[A]COUNT
+  // requires us to place R_*_RELATIVE first. SymIndex is to improve locality,
+  // while r_offset is to make results easier to read.
   if (Sort)
-    llvm::stable_sort(Relocs, compRelocations);
+    llvm::stable_sort(Relocs, [](const DynamicReloc &A, const DynamicReloc &B) {
+      return std::make_tuple(A.Type != Target->RelativeRel, A.getSymIndex(),
+                             A.getOffset()) <
+             std::make_tuple(B.Type != Target->RelativeRel, 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