[PPC64] Sort .toc sections accessed with small code model relocs close to the .got

[sfertile]

Summary

Small code model global variable access on PPC64 has a very limited range of addressing. The instructions the relocations are used on add an offset in the range [-0x8000, 0x7FFC] to the toc pointer which points to .got +0x8000, giving an addressable range of [.got, .got + 0xFFFC]. While user code can be recompiled with medium and large code models when the binary grows too large for small code model, there are small code model relocations in the crt files and libgcc.a which are typically shipped with the distros, and the ABI dictates that linkers must allow linking of relocatable object files using different code models.

To minimze the chance of relocation overflow, any file that contains a small code model relocation should have its .toc section placed closer to the .got then any .toc from a file without small code model relocations.

[grimar]

I am not PPC expert, but approach itself seems probably OK to me. At least I do not have good ideas on how to do what you want much simpler/better atm.
Maybe other reviewers will have something.

My comments/suggestions are below.

Also, do you know how this problem is solved by the GNU linkers?

ELF/Arch/PPC64.cpp

112 ↗

(On Diff #182537)

This does not seem to be clang-formatted.
Also, since you only have 3 entries here, probably it will be better to use if instead of switch.

ELF/InputFiles.h

128 ↗

(On Diff #182537)

then -> than

ELF/Writer.cpp

1256 ↗

(On Diff #182537)

I would return early.

if (Script->HasSectionsCommand)
  return;

test/ELF/Inputs/ppc64-sort-small-cm-relocs-Input2.s

24 ↗

(On Diff #182537)

Seems Lfunc_end0 is not used. And I think you do not need .size set...
Also seems there are a lot of instructions that are not needed for the test. I think you could remove stw, blr, .p2align, .abiversion,
probably others.

That applies to all input files. They are a bit bulky now and it feels can be reduced significantly probably.

One more minor issue: we do not use uppercase in file names I think. Your input files contain *-Input*.

test/ELF/ppc64-sort-small-cm-relocs.s

6 ↗

(On Diff #182537)

Do you really need so many inputs? You have 6. Feels to be a bit excessive amount.

33 ↗

(On Diff #182537)

This can be written in a single line:

# RUN: echo "SECTIONS {  .text : { *(.text*) } } " > %t.script

38 ↗

(On Diff #182537)

Can it be just an empty script?

78 ↗

(On Diff #182537)

Since you're testing the order of files here, I think you can omit addresses, entsize, alignment:

# CHECK:  .got
# CHECK:   <internal>:(.got)
# CHECK:  .toc
# CHECK:     {{.*}}/ppc64-sort-small-cm-relocs.s.tmp4.o:(.toc)
...

Also, please use CHECK-NEXT too.

[MaskRay]

ELF/Arch/PPC64.cpp

112 ↗

(On Diff #182537)

Using a switch for 3 entries looks good to me. I guess this is an incomplete list (but enough to make some not-so-small applications able to link against libgcc.a). If it is indeed incomplete, this code deserves a comment.

I've checked some powerpc64le target which failed to link due to
libgcc/libgcc2.c:1444: relocation R_PPC64_ADDR16_DS out of range: 37088 is not in [-32768, 32767]
The relocation out-of-range issues goes away with this patch.

"Power Architecture 64-bit ELF V2 ABI Specification" published on July 16, 2015 does not give examples what relocation types may be used in small/medium/large code models... The x86-64 ABI gives a few regarding PIC/non-PIC * small/medium/large code model..

[MaskRay]

In D56920#1364451, @grimar wrote:

I am not PPC expert, but approach itself seems probably OK to me. At least I do not have good ideas on how to do what you want much simpler/better atm.
Maybe other reviewers will have something.

My comments/suggestions are below.

Also, do you know how this problem is solved by the GNU linkers?

Both ld.bfd and gold have the similar "small_toc_reloc" notation and binutils-gdb/gold/power.cc does similar TOC sorting (ld.bfd has a much more complicated rule).
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=dff021e14a9c72380311c15a90c1a646b179b987;f=gold/powerpc.cc#l8376

ELF/Arch/PPC64.cpp

112 ↗

(On Diff #182537)

There are indeed a few other relocation types that need to be added. They can be added in another patch, though.

gold
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=dff021e14a9c72380311c15a90c1a646b179b987;f=gold/powerpc.cc#l7291

ld.bfd
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=dff021e14a9c72380311c15a90c1a646b179b987;f=bfd/elf64-ppc.c#l4395
and line 4535

c
	  if (r_type == R_PPC64_GOT_TLSLD16
	      || r_type == R_PPC64_GOT_TLSGD16
	      || r_type == R_PPC64_GOT_TPREL16_DS
	      || r_type == R_PPC64_GOT_DTPREL16_DS
	      || r_type == R_PPC64_GOT16
	      || r_type == R_PPC64_GOT16_DS)
	    {
	      htab->do_multi_toc = 1;
	      ppc64_elf_tdata (abfd)->has_small_toc_reloc = 1;
	    }

[grimar]

! In D56920#1364896, @MaskRay wrote:
Both ld.bfd and gold have the similar "small_toc_reloc" notation and binutils-gdb/gold/power.cc does similar TOC sorting (ld.bfd has a much more complicated rule).
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=dff021e14a9c72380311c15a90c1a646b179b987;f=gold/powerpc.cc#l8376

Thanks for the info!

ELF/Writer.cpp

1254 ↗

(On Diff #182537)

You should probably check for Config->EMachine == EM_PPC64 here too as
.toc can be (in theory) a name of a regular section for other targets and would be simpler to do nothing at all in that case.

[sfertile]

Addressed review comments and cut down the test.

[sfertile]

ELF/Arch/PPC64.cpp

112 ↗

(On Diff #182537)

Thanks for looking into this, glad to hear it fixes the libgcc related relocation overflows.
I intend to add the tls related relocations as follow on patches, 1 for the GOT related ones, then a separate patch for R_PPC_TPREL16 and R_PPC64_TPREL16_DS (which I seemed to have missed when adding tls support)

test/ELF/ppc64-sort-small-cm-relocs.s

6 ↗

(On Diff #182537)

I've cut it down to 2 inputs with small code model relocations and 2 without (mainly to show the sorting is meant to be stable).

38 ↗

(On Diff #182537)

Thank you, I didn't realize an empty script was valid.

[MaskRay]

ELF/InputFiles.h

133 ↗

(On Diff #182537)

Placing PPC64SmallCodeModelRelocs here increases sizeof(InputFile) from 184 to 192. If you place it below bool JustSymbols = false;, the size does not change (due to padding).

[grimar]

I think this is OK. Let's see what Rui think about it.
(few more nits are below)

ELF/Arch/PPC64.cpp

111 ↗

(On Diff #182845)

This would be 2 lines instead of 7 if you would use if.

return Type == R_PPC64_GOT16 || Type == R_PPC64_TOC16 ||
       Type == R_PPC64_TOC16_DS;

It is common to use if in LLD for relocations, see: https://github.com/llvm-mirror/lld/blob/master/ELF/Arch/X86_64.cpp#L166

test/ELF/ppc64-sort-small-cm-relocs.s

18 ↗

(On Diff #182845)

This relies on a test suite temporary file naming rules it seems. I am not sure if it can bring any inconsistencies or troubles, I would just use
something like

*4.o(.toc*)

It should also be more consistent with our other tests I think.

65 ↗

(On Diff #182845)

Could you remove excessive indentations in the tests, please?

[sfertile]

Addressed second round of review comments.

[ruiu]

LGTM

ELF/Writer.cpp

1254 ↗

(On Diff #182927)

Can you add a comment describing what this code does? It doesn't have to be a complete explanation because you already added it to InputFiles.h, but something like this would help readers of the code:

.toc is allocated just after .got and is accessed using GOT-relative relocations. The addressable range is [.got, .got + 0xFFFC] if an object file is compiled with the small code model. To reduce the risk of relocation overflow, .toc contents are sorted so that sections having smaller relocation offsets are at beginning of .toc.

lld/trunk/ELF/Arch/PPC64.cpp

unsigned elf::getPPC64GlobalEntryToLocalEntryOffset(uint8_t StOther) {
   // log-base-2(offset).
   if (GepToLep < 7)
     return 1 << GepToLep;
 
   error("reserved value of 7 in the 3 most-significant-bits of st_other");
   return 0;
 }
 
+bool elf::isPPC64SmallCodeModelReloc(RelType Type) {
+  // List is not yet complete, at the very least the got based tls related
+  // relocations need to be added, and we need to determine how the section
+  // sorting interacts with the thread pointer and dynamic thread pointer
+  // relative tls relocations.
+  return Type == R_PPC64_GOT16 || Type == R_PPC64_TOC16 ||
+         Type == R_PPC64_TOC16_DS;
+}
+
 namespace {
 class PPC64 final : public TargetInfo {
 public:
   PPC64();
   uint32_t calcEFlags() const override;
   RelExpr getRelExpr(RelType Type, const Symbol &S,
                      const uint8_t *Loc) const override;
   void writePltHeader(uint8_t *Buf) const override;

lld/trunk/ELF/InputFiles.h

public:
   mutable std::string ToStringCache;
 
   std::string getSrcMsg(const Symbol &Sym, InputSectionBase &Sec,
                         uint64_t Offset);
 
   // True if this is an argument for --just-symbols. Usually false.
   bool JustSymbols = false;
 
+  // On PPC64 we need to keep track of which files contain small code model
+  // relocations. To minimize the chance of a relocation overflow files that do
+  // contain small code model relocations should have their .toc sections sorted
+  // closer to the .got section than files that do not contain any small code
+  // model relocations. Thats because the toc-pointer is defined to point at
+  // .got + 0x8000 and the instructions used with small code model relocations
+  // support immediates in the range [-0x8000, 0x7FFC], making the addressable
+  // range relative to the toc pointer [.got, .got + 0xFFFC].
+  bool PPC64SmallCodeModelRelocs = false;
+
   // GroupId is used for --warn-backrefs which is an optional error
   // checking feature. All files within the same --{start,end}-group or
   // --{start,end}-lib get the same group ID. Otherwise, each file gets a new
   // group ID. For more info, see checkDependency() in SymbolTable.cpp.
   uint32_t GroupId;
   static bool IsInGroup;
   static uint32_t NextGroupId;
 

lld/trunk/ELF/Relocations.cpp

static void scanReloc(InputSectionBase &Sec, OffsetGetter &GetOffset, RelTy *&I,
 
   const uint8_t *RelocatedAddr = Sec.data().begin() + Rel.r_offset;
   RelExpr Expr = Target->getRelExpr(Type, Sym, RelocatedAddr);
 
   // Ignore "hint" relocations because they are only markers for relaxation.
   if (isRelExprOneOf<R_HINT, R_NONE>(Expr))
     return;
 
+  if (Config->EMachine == EM_PPC64 && isPPC64SmallCodeModelReloc(Type))
+    Sec.File->PPC64SmallCodeModelRelocs = true;
+
   // Strenghten or relax relocations.
   //
   // GNU ifunc symbols must be accessed via PLT because their addresses
   // are determined by runtime.
   //
   // On the other hand, if we know that a PLT entry will be resolved within
   // the same ELF module, we can skip PLT access and directly jump to the
   // destination function. For example, if we are linking a main exectuable,

lld/trunk/ELF/Target.h

 // a global entry point (GEP) which typically is used to intiailzie the TOC
 // pointer in general purpose register 2.  The second is a local entry
 // point (LEP) which bypasses the TOC pointer initialization code. The
 // offset between GEP and LEP is encoded in a function's st_other flags.
 // This function will return the offset (in bytes) from the global entry-point
 // to the local entry-point.
 unsigned getPPC64GlobalEntryToLocalEntryOffset(uint8_t StOther);
 
+bool isPPC64SmallCodeModelReloc(RelType Type);
+
 uint64_t getPPC64TocBase();
 uint64_t getAArch64Page(uint64_t Expr);
 
 extern TargetInfo *Target;
 TargetInfo *getTarget();
 
 template <class ELFT> bool isMipsPIC(const Defined *Sym);
 

lld/trunk/ELF/Writer.cpp

if (!Script->HasSectionsCommand)
       Sec->sortCtorsDtors();
     return;
   }
 
   // Never sort these.
   if (Name == ".init" || Name == ".fini")
     return;
 
+  // .toc is allocated just after .got and is accessed using GOT-relative
+  // relocations. Object files compiled with small code model have an
+  // addressable range of [.got, .got + 0xFFFC] for GOT-relative relocations.
+  // To reduce the risk of relocation overflow, .toc contents are sorted so that
+  // sections having smaller relocation offsets are at beginning of .toc
+  if (Config->EMachine == EM_PPC64 && Name == ".toc") {
+    if (Script->HasSectionsCommand)
+      return;
+    assert(Sec->SectionCommands.size() == 1);
+    auto *ISD = cast<InputSectionDescription>(Sec->SectionCommands[0]);
+    std::stable_sort(ISD->Sections.begin(), ISD->Sections.end(),
+                     [](const InputSection *A, const InputSection *B) -> bool {
+                       return A->File->PPC64SmallCodeModelRelocs &&
+                              !B->File->PPC64SmallCodeModelRelocs;
+                     });
+    return;
+  }
+
   // Sort input sections by priority using the list provided
   // by --symbol-ordering-file.
   if (!Order.empty())
     for (BaseCommand *B : Sec->SectionCommands)
       if (auto *ISD = dyn_cast<InputSectionDescription>(B))
         sortISDBySectionOrder(ISD, Order);
 }
 

lld/trunk/test/ELF/Inputs/ppc64-sort-small-cm-relocs-input2.s

+    .text
+
+    .global set
+    .type set,@function
+set:
+.Lgep:
+    addis 2, 12, .TOC.-.Lgep@ha
+    addi 2, 2, .TOC.-.Lgep@l
+.Llep:
+    .localentry set, .Llep-.Lgep
+    addis 5, 2, .LC0@toc@ha
+    addis 6, 2, .LC1@toc@ha
+    ld 5, .LC0@toc@l(5)
+    ld 6, .LC1@toc@l(6)
+    stw 3, 0(5)
+    stw 4, 0(6)
+    blr
+
+    .section .toc,"aw",@progbits
+.LC0:
+    .tc c[TC],c
+.LC1:
+    .tc d[TC],d

lld/trunk/test/ELF/Inputs/ppc64-sort-small-cm-relocs-input3.s

+    .text
+    .global getA
+    .type getA,@function
+getA:
+.LgepA:
+    addis 2, 12, .TOC.-.LgepA@ha
+    addi 2, 2, .TOC.-.LgepA@l
+.LlepA:
+    .localentry getA, .LlepA-.LgepA
+    ld 3, .LC0@toc(2)
+    lwa 3, 0(3)
+    blr
+
+    .global getB
+    .type getB,@function
+getB:
+.LgepB:
+    addis 2, 12, .TOC.-.LgepB@ha
+    addi 2, 2, .TOC.-.LgepB@l
+.LlepB:
+    .localentry getB, .LlepB-.LgepB
+    ld 3, .LC1@toc(2)
+    lwa 3, 0(3)
+    blr
+
+    .section .toc,"aw",@progbits
+.LC0:
+    .tc a[TC],a
+.LConst1:
+    .quad 0xa
+.LC1:
+    .tc b[TC],b
+.Lconst2:
+    .quad 0xaabbccddeeff
+
+    .type b,@object
+    .data
+    .global b
+b:
+    .long 22
+    .size b, 4

lld/trunk/test/ELF/Inputs/ppc64-sort-small-cm-relocs-input4.s

+    .text
+    .global getRodata
+    .type getRodata,@function
+getRodata:
+.Lgep:
+    addis 2, 12, .TOC.-.Lgep@ha
+    addi 2, 2, .TOC.-.Lgep@l
+.Llep:
+    .localentry     getRodata, .Llep-.Lgep
+    lwa 3, .LC0@toc(2)
+    blr
+
+    .section        .rodata,"aMS",@progbits,8
+    .quad _start
+
+    .section        .toc,"aw",@progbits
+.LC0:
+    .tc .rodata[TC], .rodata

lld/trunk/test/ELF/ppc64-sort-small-cm-relocs.s

+# REQUIRES: ppc
+# RUN: llvm-mc -filetype=obj -triple=powerpc64le-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=powerpc64le-unknown-linux %p/Inputs/ppc64-sort-small-cm-relocs-input2.s -o %t2.o
+# RUN: llvm-mc -filetype=obj -triple=powerpc64le-unknown-linux %p/Inputs/ppc64-sort-small-cm-relocs-input3.s -o %t3.o
+# RUN: llvm-mc -filetype=obj -triple=powerpc64le-unknown-linux %p/Inputs/ppc64-sort-small-cm-relocs-input4.s -o %t4.o
+
+# RUN: ld.lld %t1.o %t2.o %t3.o %t4.o -o %t -Map=%t.map
+# RUN: FileCheck %s < %t.map
+
+# Test an alternate link order.
+# RUN: ld.lld %t2.o %t3.o %t4.o %t1.o -o %t -Map=%t.map
+# RUN: FileCheck %s -check-prefix=ALTERNATE < %t.map
+
+# If a linker script has a sections command then allow that to override the
+# default sorting behavior.
+# RUN: echo "SECTIONS {          \
+# RUN:         .toc : {          \
+# RUN:            */ppc64-sort-small-cm-relocs.s.tmp4.o(.toc*) \
+# RUN:            */ppc64-sort-small-cm-relocs.s.tmp1.o(.toc*)  \
+# RUN:            *(.toc*)       \
+# RUN:          }                \
+# RUN:       } " > %t.script
+# RUN: ld.lld %t1.o %t2.o %t3.o %t4.o -o %t -script %t.script -Map=%t.map
+# RUN: FileCheck %s -check-prefix=SEC-CMD < %t.map
+
+# RUN: echo "SECTIONS { .text : {*(.text*)} } " > %t.script
+# RUN: ld.lld %t1.o %t2.o %t3.o %t4.o -o %t -script %t.script -Map=%t.map
+# RUN: FileCheck %s -check-prefix=SEC-CMD2 < %t.map
+
+# Default sort if the linker script does not have a sections command.
+# RUN: echo "" > %t.script
+# RUN: ld.lld %t1.o %t2.o %t3.o %t4.o -o %t -script %t.script -Map=%t.map
+# RUN: FileCheck %s -check-prefix=NOSEC < %t.map
+    .text
+
+    .global _start
+    .type _start,@function
+_start:
+    li 3, 55
+    blr
+
+    .type a,@object
+    .data
+    .global a
+a:
+    .long 10
+    .size a, 4
+
+    .type c,@object
+    .data
+    .global c
+c:
+    .long  55
+    .size  c, 4
+
+    .type   d,@object
+    .global d
+d:
+    .long 33
+    .size d, 4
+
+    # .toc section contains only some constants.
+    .section        .toc,"aw",@progbits
+    .quad 0xa1a1a1a1a1a1a1a1
+    .quad 0xb2b2b2b2b2b2b2b2
+
+# Input files tmp3.o and tmp4.o contain small code model relocs.
+
+# CHECK:      .got
+# CHECK-NEXT:         <internal>:(.got)
+# CHECK-NEXT: .toc
+# CHECK-NEXT:         {{.*}}3.o:(.toc)
+# CHECK-NEXT:         {{.*}}4.o:(.toc)
+# CHECK-NEXT:         {{.*}}1.o:(.toc)
+# CHECK-NEXT:         {{.*}}2.o:(.toc)
+
+# ALTERNATE:      .got
+# ALTERNATE-NEXT:         <internal>:(.got)
+# ALTERNATE-NEXT: .toc
+# ALTERNATE-NEXT:         {{.*}}3.o:(.toc)
+# ALTERNATE-NEXT:         {{.*}}4.o:(.toc)
+# ALTERNATE-NEXT:         {{.*}}2.o:(.toc)
+# ALTERNATE-NEXT:         {{.*}}1.o:(.toc)
+
+# SEC-CMD:      .got
+# SEC-CMD-NEXT:         <internal>:(.got)
+# SEC-CMD-NEXT: .toc
+# SEC-CMD-NEXT:         {{.*}}4.o:(.toc)
+# SEC-CMD-NEXT:         {{.*}}1.o:(.toc)
+# SEC-CMD-NEXT:         {{.*}}2.o:(.toc)
+# SEC-CMD-NEXT:         {{.*}}3.o:(.toc)
+
+# SEC-CMD2:      .got
+# SEC-CMD2-NEXT:         <internal>:(.got)
+# SEC-CMD2-NEXT: .toc
+# SEC-CMD2-NEXT:         {{.*}}1.o:(.toc)
+# SEC-CMD2-NEXT:         {{.*}}2.o:(.toc)
+# SEC-CMD2-NEXT:         {{.*}}3.o:(.toc)
+# SEC-CMD2-NEXT:         {{.*}}4.o:(.toc)
+
+# NOSEC:      .got
+# NOSEC-NEXT:         <internal>:(.got)
+# NOSEC-NEXT: .toc
+# NOSEC-NEXT:         {{.*}}3.o:(.toc)
+# NOSEC-NEXT:         {{.*}}4.o:(.toc)
+# NOSEC-NEXT:         {{.*}}1.o:(.toc)
+# NOSEC-NEXT:         {{.*}}2.o:(.toc)
+