Skip scanRelocs for non-alloc sections.

[ruiu]

Summary

Relocations against sections with no SHF_ALLOC bit are R_ABS relocations.
Currently we are creating Relocations vector for them, but that is wasteful.
This patch is to skip vector construction and to directly apply relocations
in place.

[• rafael]

I really like this. It is a lot simpler than what I was expecting.
But why the test changed?

ELF/InputSection.h

222 ↗

(On Diff #55375)

Native?

ELF/Writer.cpp

535 ↗

(On Diff #55375)

This is now always false.

test/ELF/relocation-non-alloc.s

36 ↗

(On Diff #55375)

Is the change expected?

[ruiu]

ELF/InputSection.h

222 ↗

(On Diff #55375)

Do you have any suggestions for better name?

test/ELF/relocation-non-alloc.s

36 ↗

(On Diff #55375)

Yes. BFD and gold both produces this pattern rather than the old one. This is a test to produce a DSO file with a non-alloc section pointing to an interruptible symbol. This seems to be unrealistic test case. LLD previously handle interruptible symbols addresses as 0 because it can change at runtime, but GNU linkers don't seem to bother it.

[• rafael]

LGTM with the name changed and the IsAlloc bool replaced with false.

ELF/InputSection.cpp

230 ↗

(On Diff #55375)

Debug section is -> Debug sections are.

ELF/InputSection.h

222 ↗

(On Diff #55375)

Maybe just relocateNonAlloc?

test/ELF/relocation-non-alloc.s

36 ↗

(On Diff #55375)

OK, I think I see what is going on.

For preemptable symbols in alloc sections we have to create a dynamic relocation. Having created one, we know the dynamic linker will take care of everything and we don't need to do anything else.

I am not sure if these show up in practice in non alloc sections, but it seems reasonable to have them point to the symbol in the file we are producing since there will be no dynamic relocation.

[ruiu]

So, this patch seems to be pretty effective for large executables with debug info. r266158 (Rafael's patch to change the way how we apply relocations) caused a temporary performance degradation for such executables, but this patch makes it even faster than before.

Time to link clang with debug info (output size is 1070 MB):

before r266158: 15.312 seconds (0%)
r266158:        17.301 seconds (+13.0%)
Head:           16.484 seconds (+7.7%)
w/patch:        13.166 seconds (-14.0%)

lld/trunk/ELF/InputSection.h

public:
   void addThunk(SymbolBody &Body);
 
   // The offset of synthetic thunk code from beginning of this section.
   uint64_t getThunkOff() const;
 
   // Size of chunk with thunks code.
   uint64_t getThunksSize() const;
 
+  template <class RelTy>
+  void relocateNonAlloc(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
+
 private:
   template <class RelTy>
   void copyRelocations(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   // Called by ICF to merge two input sections.
   void replace(InputSection<ELFT> *Other);
 
   // Used by ICF.

lld/trunk/ELF/InputSection.cpp

getSymVA(uint32_t Type, typename ELFT::uint A, typename ELFT::uint P,
   case R_PC:
     return Body.getVA<ELFT>(A) - P;
   case R_PAGE_PC:
     return getAArch64Page(Body.getVA<ELFT>(A)) - getAArch64Page(P);
   }
   llvm_unreachable("Invalid expression");
 }
 
+// This function applies relocations to sections without SHF_ALLOC bit.
+// Such sections are never mapped to memory at runtime. Debug sections are
+// an example. Relocations in non-alloc sections are much easier to
+// handle than in allocated sections because it will never need complex
+// treatement such as GOT or PLT (because at runtime no one refers them).
+// So, we handle relocations for non-alloc sections directly in this
+// function as a performance optimization.
+template <class ELFT>
+template <class RelTy>
+void InputSection<ELFT>::relocateNonAlloc(uint8_t *Buf, ArrayRef<RelTy> Rels) {
+  const unsigned Bits = sizeof(uintX_t) * 8;
+  for (const RelTy &Rel : Rels) {
+    uint8_t *BufLoc = Buf + Rel.r_offset;
+    uintX_t AddrLoc = this->OutSec->getVA() + Rel.r_offset;
+    uint32_t Type = Rel.getType(Config->Mips64EL);
+    SymbolBody &Sym = this->File->getRelocTargetSym(Rel);
+
+    if (Target->getRelExpr(Type, Sym) != R_ABS) {
+      error(this->getSectionName() + " has non-ABS reloc");
+      return;
+    }
+
+    uint64_t SymVA = SignExtend64<Bits>(getSymVA<ELFT>(
+        Type, getAddend<ELFT>(Rel), AddrLoc, Sym, BufLoc, *this->File, R_ABS));
+    Target->relocateOne(BufLoc, Type, SymVA);
+  }
+}
+
 template <class ELFT>
 void InputSectionBase<ELFT>::relocate(uint8_t *Buf, uint8_t *BufEnd) {
+  // scanReloc function in Writer.cpp constructs Relocations
+  // vector only for SHF_ALLOC'ed sections. For other sections,
+  // we handle relocations directly here.
+  auto *IS = dyn_cast<InputSection<ELFT>>(this);
+  if (IS && !(IS->Header->sh_flags & SHF_ALLOC)) {
+    for (const Elf_Shdr *RelSec : IS->RelocSections) {
+      if (RelSec->sh_type == SHT_RELA)
+        IS->relocateNonAlloc(Buf, IS->File->getObj().relas(RelSec));
+      else
+        IS->relocateNonAlloc(Buf, IS->File->getObj().rels(RelSec));
+    }
+    return;
+  }
+
   const unsigned Bits = sizeof(uintX_t) * 8;
   for (const Relocation &Rel : Relocations) {
     uintX_t Offset = Rel.Offset;
     uint8_t *BufLoc = Buf + Offset;
     uint32_t Type = Rel.Type;
     uintX_t A = Rel.Addend;
 
     uintX_t AddrLoc = OutSec->getVA() + Offset;

lld/trunk/ELF/Writer.cpp

 // is needed after applying relocations. If it is, it will go after rw and rx
 // sections. Given that it is ro, we will need an extra PT_LOAD. This
 // complicates things for the dynamic linker and means we would have to reserve
 // space for the extra PT_LOAD even if we end up not using it.
 template <class ELFT>
 template <class RelTy>
 void Writer<ELFT>::scanRelocs(InputSectionBase<ELFT> &C, ArrayRef<RelTy> Rels) {
   uintX_t Flags = C.getSectionHdr()->sh_flags;
-  bool IsAlloc = Flags & SHF_ALLOC;
   bool IsWrite = Flags & SHF_WRITE;
 
   auto AddDyn = [=](const DynamicReloc<ELFT> &Reloc) {
-    if (IsAlloc)
-      Out<ELFT>::RelaDyn->addReloc(Reloc);
   };
 
   const elf::ObjectFile<ELFT> &File = *C.getFile();
   ArrayRef<uint8_t> SectionData = C.getSectionData();
   const uint8_t *Buf = SectionData.begin();
   for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
     const RelTy &RI = *I;
     SymbolBody &Body = File.getRelocTargetSym(RI);
if (Expr == R_GOT && !isRelRelative<ELFT>(Expr, Type, Body) &&
         Config->Shared)
       AddDyn({Target->RelativeRel, C.OutSec, Offset, true, &Body,
               getAddend<ELFT>(RI)});
 
     // If a symbol in a DSO is referenced directly instead of through GOT
     // in a read-only section, we need to create a copy relocation for the
     // symbol.
     if (auto *B = dyn_cast<SharedSymbol<ELFT>>(&Body)) {
-      if (IsAlloc && !IsWrite && needsCopyRel(Expr, *B)) {
+      if (!IsWrite && needsCopyRel(Expr, *B)) {
         if (!B->needsCopy())
           addCopyRelSymbol(B);
         C.Relocations.push_back({Expr, Type, Offset, Addend, &Body});
         continue;
       }
     }
 
     bool Preemptible = Body.isPreemptible();
if (NeedPlt) {
       uint32_t Rel;
       if (Body.isGnuIFunc())
         Rel = Preemptible ? Target->PltRel : Target->IRelativeRel;
       else
         Rel = Target->UseLazyBinding ? Target->PltRel : Target->GotRel;
 
       if (Target->UseLazyBinding) {
         Out<ELFT>::GotPlt->addEntry(Body);
-        if (IsAlloc)
-          Out<ELFT>::RelaPlt->addReloc({Rel, Out<ELFT>::GotPlt,
-                                        Body.getGotPltOffset<ELFT>(),
-                                        !Preemptible, &Body, 0});
       } else {
         if (Body.isInGot())
           continue;
         Out<ELFT>::Got->addEntry(Body);
         AddDyn({Rel, Out<ELFT>::Got, Body.getGotOffset<ELFT>(), !Preemptible,
                 &Body, 0});
       }
       continue;
void Writer<ELFT>::scanRelocs(InputSectionBase<ELFT> &C, ArrayRef<RelTy> Rels) {
   if (Config->EMachine == EM_MIPS)
     scanRelocsForThunks(File, Rels);
 }
 
 template <class ELFT> void Writer<ELFT>::scanRelocs(InputSection<ELFT> &C) {
   // Scan all relocations. Each relocation goes through a series
   // of tests to determine if it needs special treatment, such as
   // creating GOT, PLT, copy relocations, etc.
-  //
-  // The current code is a bit wasteful because it scans relocations
-  // in non-SHF_ALLOC sections. Such sections are never mapped to
-  // memory at runtime. Debug section is an example. Relocations in
-  // non-alloc sections are much easier to handle because it will
-  // never need complex treatement such as GOT or PLT (because at
-  // runtime no one refers them). We probably should skip non-alloc
-  // sections here and directly handle non-alloc relocations in
-  // writeTo function.
+  // Note that relocations for non-alloc sections are directly
+  // processed by InputSection::relocateNative.
+  if (C.getSectionHdr()->sh_flags & SHF_ALLOC)
     for (const Elf_Shdr *RelSec : C.RelocSections)
       scanRelocs(C, *RelSec);
 }
 
 template <class ELFT>
 void Writer<ELFT>::scanRelocs(InputSectionBase<ELFT> &S,
                               const Elf_Shdr &RelSec) {
   ELFFile<ELFT> &EObj = S.getFile()->getObj();
   if (RelSec.sh_type == SHT_RELA)
     scanRelocs(S, EObj.relas(&RelSec));

lld/trunk/test/ELF/relocation-non-alloc.s

 // CHECK-NEXT: Address: 0x0
 // CHECK-NEXT: Offset:
 // CHECK-NEXT: Size: 16
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 1
 // CHECK-NEXT: EntrySize: 0
 // CHECK-NEXT: SectionData (
-// CHECK-NEXT:   0000: 00100000 00000000 00000000 00000000
+// CHECK-NEXT:   0000: 00100000 00000000 00100000 00000000
 // CHECK-NEXT: )
 
 // CHECK:      Relocations [
 // CHECK-NEXT:   Section ({{.}}) .rela.dyn {
 // CHECK-NEXT:     0x1000 R_X86_64_RELATIVE - 0x1000
 // CHECK-NEXT:     0x1008 R_X86_64_64 zed 0x0
 // CHECK-NEXT:   }
 // CHECK-NEXT: ]