[lld][ELF2] Apply relocations.

[Bigcheese]

Summary

This is located in the Writer as opposed to SectionChunk so that the Writer can
do a single pass over the relocations and simultaneously generate GOT/PLT
entries which will be placed after the relocated SectionChunks.

Fully supporting linker scripts, which allow placement of the PLT and GOT
anywhere, will require a pre-layout pass to generate them.

[ruiu]

I kind of like the original approach to teach Chunks how to apply
relocations to themselves. It looks more modular and easy to use
(the writer has to just tell Chunks to "write to here" and everything
including applying relocations is done in one shot).

For COFF, we iterate the relocation table three times for dead-
stripping, applying relocations, and construct COFF base relocation
table. Iterating over a relocation table is not slow -- it's fast enough
to make me think to keep the three things separated. I'd keep them
separated in this file too.

ELF/Chunks.cpp

21–22 ↗

(On Diff #30961)

May fit in 80 cols?

ELF/InputFiles.cpp

48 ↗

(On Diff #30961)

Does this have to be std::stable_sort? std::sort doesn't work?

ELF/Symbols.h

90 ↗

(On Diff #30961)

Add a blank line.

ELF/Writer.h

54 ↗

(On Diff #30961)

These functions are sorted in the same order as they are called. So move this after writeSections (and move writeHeader below writeSections.)

[Bigcheese]

@rafael really wanted this to be a single pass, which is why I designed it this way.

In my RelWithDebInfo build of llvm+lld there are about 1GiB of relocations from .o files. I assume that quite a few of these will be COMDAT merged away before being looked at, but that's still a lot of memory.

[ruiu]

IIUC, doing GOT/PLT and applying relocations in one pass is just merging
multiple loops to one loop, and the total number of computation we need
to do for GOT/PLT and applying relocations wouldn't change that much.
Because relocations are continuous in memory and they are fixed in size,
iterating over them should be very fast, so I don't see loop-merging would
make things noticeably faster (that's what I observed in COFF.)

So I feel like it's a premature optimization. I'd like to keep it really simple and
straightforward as possible at this moment. We'll be able to do optimization
later.

Rafael, I'd like to hear from you since this is your idea.

[• rafael]

Starting to take a look at this. Please rebase it on top of trunk now
previous issues have been addressed.

[• rafael]

I do want us to be able to do a single pass over the relocations. On other ELF linkers at least relocation processing shows up in profiles.

Having said that, I am not sure that forces where the code lives.

Rui, are you ok with this going in with the code in writer.cpp, we add GOT/PLT support and then try to refactor it to some other file? It seems easier than starting with 2 passes and trying to then combine them.

ELF/Chunks.h

19 ↗

(On Diff #30961)

Independent cleanup, please commit it first.

81 ↗

(On Diff #30961)

Why do you need to pass an ObjectFile here?

ELF/InputFiles.cpp

35 ↗

(On Diff #30961)

For SparseChunks you can use resize and drop the push_backs below.

42 ↗

(On Diff #30961)

This is not checking if getSection fails.

ELF/InputFiles.h

57 ↗

(On Diff #30961)

Add a comment on why it is deterministic to use < on pointers (they are all from one file).

73 ↗

(On Diff #30961)

don't use report_fatal_error.

ELF/SymbolTable.h

19 ↗

(On Diff #30961)

independent cleanup. Please commit first.

ELF/Symbols.h

105 ↗

(On Diff #30961)

This is dead.

108 ↗

(On Diff #30961)

This is dead.

125 ↗

(On Diff #30961)

Seems better to just cast to DefinedRegular at use.

ELF/Writer.cpp

189 ↗

(On Diff #30961)

Can you use a range loop.

test/elf2/relocation.test

1 ↗

(On Diff #30961)

llvm-mc

[ruiu]

I was thinking about the cost. I'm still thinking but I don't want to block this,
so writing a comment. I still prefer to not write code for relocations in Writer.cpp,
as I think the original code is much more cleaner than this is.

I believe it shouldn't be hard to rewrite it as one pass if we have to.
So it looks like a premature optimization to me.

[atanasyan]

I believe it shouldn't be hard to rewrite it as one pass if we have to.
So it looks like a premature optimization to me.

Suppose we have a relocation R. This relocation is in the .text section and refers a symbol in the .data section. Suppose that the .data section goes after the .text one. It is still a common case even if we forget about a linker script support. How will we write result of this relocation using a single pass approach? Will we know an address of the symbol in the .data section at the moment of writing the .text section?

[atanasyan]

There is one more question about single-pass relocation handling. On MIPS if you call non-PIC routine from a PIC one you should create a thunk contains three instructions. We do not known the number of the thunks until we scan all relocations. So we cannot predict the output .text section's size and offsets. IIRC ARM requires some kind of thunks too. How can the single-pass relocation calculation handle this problem?

[ruiu]

There may be more things to think. I'd like to see to land with
non-single-pass approach as I suggested so that it doesn't block anyone. We
can revisit this later when needed.

[silvas]

test/elf2/relocation.test

1 ↗

(On Diff #30961)

That doesn't make sense. It's like using a C file for an LLVM IR test. If we are testing relocations, there better be R_ in the input and not in a comment.

30–38 ↗

(On Diff #30961)

Delete the data and bss sections. They don't matter for this test.

71 ↗

(On Diff #30961)

For clarity, please have an explicit offset here.

[Bigcheese]

Rebase and address review comments.

ELF/Chunks.h

81 ↗

(On Diff #30961)

Because we need to know which ObjectFile a section is from to get its relocations.

ELF/InputFiles.cpp

35 ↗

(On Diff #30961)

I cleaned it up some. Using resize and array indexing was just as complicated.

test/elf2/relocation.test

1 ↗

(On Diff #30961)

This is testing explicit relocations. Assembly doesn't represent specific relocations, and it's not obvious what gets generated.

[llvm-commits]

llvm-mc

This is testing explicit relocations. Assembly doesn't represent specific relocations, and it's not obvious what gets generated.

This test is using a valid file that can be created with assembly.
YAML is an unnecessary LLVM only invention here. Use assembly.

Cheers,
Rafael

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[Bigcheese]

Fixed symbol indexing bug. The underlying code changed while the patch was out for review.

I still find using assembly to represent relocations to be an obfuscation, but I'm not going to let that delay work.

[davide]

I'm fine with the general structure of this patch. I would really like to see this moving forward. Rafael is doing a fair amount of work that may potentially conflict with this, so, the more we delay the check-in of this code, the harder it will be (delays due to rebase etc..). Also, having the scaffolding for relocation in place will ease implementation of other relocations. Is there anything else outstanding?

[Bigcheese]

I'm just waiting for a lgtm.

[ruiu]

Rafael should be the person who signs off.

[• rafael]

This doesn't even compile:

/home/espindola/llvm/llvm/tools/lld/ELF/Symbols.h:135:12: error: use
of undeclared identifier 'Sym'

return Sym.st_value;

[• rafael]

The attached patch fixes the build and runs git-clang-format.

• t.diff30 KBDownload

[• rafael]

elf2/basic64be.s is still failing, looking.

[• rafael]

Hacked to pass all tests.

Trying to merge now.

• t.diff14 KBDownload

[llvm-commits]

Rebased to trunk with all tests passing.

Main issues I see so far:

• There seems to be more code than needed for the test.
• Treating local symbols like regular symbols is incredibly wasteful.

They don't need the replacement logic.

I will try to further reduce the patch tomorrow.

• t.diff11 KBDownload
• msg-11994-262.txt162 BDownload

lld/trunk/ELF/Chunks.h

 // A chunk corresponding a section of an input file.
 template <class ELFT> class SectionChunk {
   typedef llvm::object::Elf_Shdr_Impl<ELFT> Elf_Shdr;
   typedef llvm::object::Elf_Rel_Impl<ELFT, true> Elf_Rela;
   typedef llvm::object::Elf_Rel_Impl<ELFT, false> Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
-  SectionChunk(llvm::object::ELFFile<ELFT> *Obj, const Elf_Shdr *Header);
+  SectionChunk(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
 
   // Returns the size of this chunk (even if this is a common or BSS.)
   size_t getSize() const { return Header->sh_size; }
 
   // Write this chunk to a mmap'ed file, assuming Buf is pointing to
   // beginning of the output section.
   void writeTo(uint8_t *Buf);
 
   StringRef getSectionName() const;
   const Elf_Shdr *getSectionHdr() const { return Header; }
+  ObjectFile<ELFT> *getFile() { return File; }
 
   // The writer sets and uses the addresses.
   uintX_t getOutputSectionOff() const { return OutputSectionOff; }
   uintX_t getAlign() { return Header->sh_addralign; }
   void setOutputSectionOff(uint64_t V) { OutputSectionOff = V; }
 
   void setOutputSection(OutputSection<ELFT> *O) { Out = O; }
   OutputSection<ELFT> *getOutputSection() const { return Out; }
 
+  // Relocation sections that refer to this one.
+  SmallVector<const Elf_Shdr *, 1> RelocSections;
+
 private:
   // The offset from beginning of the output sections this chunk was assigned
   // to. The writer sets a value.
   uint64_t OutputSectionOff = 0;
 
-  // A file this chunk was created from.
-  llvm::object::ELFFile<ELFT> *Obj;
+  // The file this chunk was created from.
+  ObjectFile<ELFT> *File;
 
   OutputSection<ELFT> *Out = nullptr;
 
   const Elf_Shdr *Header;
 };
 
 } // namespace elf2
 } // namespace lld
 
 #endif

lld/trunk/ELF/Chunks.cpp

 //===- Chunks.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Chunks.h"
 #include "Error.h"
+#include "InputFiles.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf2;
 
 template <class ELFT>
-SectionChunk<ELFT>::SectionChunk(object::ELFFile<ELFT> *Obj,
-                                 const Elf_Shdr *Header)
-    : Obj(Obj), Header(Header) {}
+SectionChunk<ELFT>::SectionChunk(ObjectFile<ELFT> *F, const Elf_Shdr *Header)
+    : File(F), Header(Header) {}
 
 template <class ELFT> void SectionChunk<ELFT>::writeTo(uint8_t *Buf) {
   if (Header->sh_type == SHT_NOBITS)
     return;
   // Copy section contents from source object file to output file.
-  ArrayRef<uint8_t> Data = *Obj->getSectionContents(Header);
+  ArrayRef<uint8_t> Data = *File->getObj()->getSectionContents(Header);
   memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
-
-  // FIXME: Relocations
 }
 
 template <class ELFT> StringRef SectionChunk<ELFT>::getSectionName() const {
-  ErrorOr<StringRef> Name = Obj->getSectionName(Header);
+  ErrorOr<StringRef> Name = File->getObj()->getSectionName(Header);
   error(Name);
   return *Name;
 }
 
 namespace lld {
 namespace elf2 {
 template class SectionChunk<object::ELF32LE>;
 template class SectionChunk<object::ELF32BE>;
 template class SectionChunk<object::ELF64LE>;
 template class SectionChunk<object::ELF64BE>;
 }
 }

lld/trunk/ELF/InputFiles.h

public:
   explicit ObjectFile(MemoryBufferRef M) : ObjectFileBase(getKind(), M) {}
   void parse() override;
 
   // Returns the underying ELF file.
   llvm::object::ELFFile<ELFT> *getObj() const { return ELFObj.get(); }
 
   ArrayRef<SectionChunk<ELFT> *> getChunks() { return Chunks; }
 
+  SymbolBody *getSymbolBody(uint32_t SymbolIndex) {
+    uint32_t FirstNonLocal = Symtab->sh_info;
+    if (SymbolIndex < FirstNonLocal)
+      return nullptr;
+    return SymbolBodies[SymbolIndex - FirstNonLocal]->getReplacement();
+  }
+
 private:
   void initializeChunks();
   void initializeSymbols();
 
   SymbolBody *createSymbolBody(StringRef StringTable, const Elf_Sym *Sym);
 
   std::unique_ptr<llvm::object::ELFFile<ELFT>> ELFObj;
 

lld/trunk/ELF/InputFiles.cpp

for (const Elf_Shdr &Sec : ELFObj->sections()) {
     case SHT_SYMTAB_SHNDX: {
       ErrorOr<ArrayRef<Elf_Word>> ErrorOrTable = ELFObj->getSHNDXTable(Sec);
       error(ErrorOrTable);
       SymtabSHNDX = *ErrorOrTable;
       break;
     }
     case SHT_STRTAB:
     case SHT_NULL:
+      break;
     case SHT_RELA:
-    case SHT_REL:
+    case SHT_REL: {
+      uint32_t RelocatedSectionIndex = Sec.sh_info;
+      if (RelocatedSectionIndex >= Size)
+        error("Invalid relocated section index");
+      SectionChunk<ELFT> *RelocatedSection = Chunks[RelocatedSectionIndex];
+      if (!RelocatedSection)
+        error("Unsupported relocation reference");
+      RelocatedSection->RelocSections.push_back(&Sec);
       break;
+    }
     default:
-      Chunks[I] = new (Alloc) SectionChunk<ELFT>(this->getObj(), &Sec);
+      Chunks[I] = new (Alloc) SectionChunk<ELFT>(this, &Sec);
       break;
     }
     ++I;
   }
 }
 
 template <class ELFT> void elf2::ObjectFile<ELFT>::initializeSymbols() {
   ErrorOr<StringRef> StringTableOrErr =

lld/trunk/ELF/Symbols.h

public:
 
   // A SymbolBody has a backreference to a Symbol. Originally they are
   // doubly-linked. A backreference will never change. But the pointer
   // in the Symbol may be mutated by the resolver. If you have a
   // pointer P to a SymbolBody and are not sure whether the resolver
   // has chosen the object among other objects having the same name,
   // you can access P->Backref->Body to get the resolver's result.
   void setBackref(Symbol *P) { Backref = P; }
+  SymbolBody *getReplacement() { return Backref ? Backref->Body : this; }
 
   // Decides which symbol should "win" in the symbol table, this or
   // the Other. Returns 1 if this wins, -1 if the Other wins, or 0 if
   // they are duplicate (conflicting) symbols.
   int compare(SymbolBody *Other);
 
 protected:
   SymbolBody(Kind K, StringRef Name) : SymbolKind(K), Name(Name) {}

lld/trunk/ELF/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Chunks.h"
 #include "Config.h"
 #include "Error.h"
+#include "Symbols.h"
 #include "SymbolTable.h"
 #include "Writer.h"
 #include "Symbols.h"
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/FileOutputBuffer.h"
+#include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 
 using namespace lld;
 using namespace lld::elf2;
 

 };
 }
 
 template <class ELFT>
 class lld::elf2::OutputSection final
     : public OutputSectionBase<ELFT::Is64Bits> {
 public:
   typedef typename OutputSectionBase<ELFT::Is64Bits>::uintX_t uintX_t;
+  typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
+  typedef typename ELFFile<ELFT>::Elf_Rela Elf_Rela;
   OutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_flags)
       : OutputSectionBase<ELFT::Is64Bits>(Name, sh_type, sh_flags) {}
 
   void addChunk(SectionChunk<ELFT> *C);
   void writeTo(uint8_t *Buf) override;
 
 private:
   std::vector<SectionChunk<ELFT> *> Chunks;
void OutputSection<ELFT>::addChunk(SectionChunk<ELFT> *C) {
 
   uintX_t Off = this->Header.sh_size;
   Off = RoundUpToAlignment(Off, Align);
   C->setOutputSectionOff(Off);
   Off += C->getSize();
   this->Header.sh_size = Off;
 }
 
+template <class ELFT>
+static typename llvm::object::ELFFile<ELFT>::uintX_t
+getSymVA(DefinedRegular<ELFT> *DR) {
+  const SectionChunk<ELFT> *SC = &DR->Section;
+  OutputSection<ELFT> *OS = SC->getOutputSection();
+  return OS->getVA() + SC->getOutputSectionOff() + DR->Sym.st_value;
+}
+
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
-  for (SectionChunk<ELFT> *C : Chunks)
+  for (SectionChunk<ELFT> *C : Chunks) {
     C->writeTo(Buf);
+    ObjectFile<ELFT> *File = C->getFile();
+    ELFFile<ELFT> *EObj = File->getObj();
+    uint8_t *Base = Buf + C->getOutputSectionOff();
+
+    // Iterate over all relocation sections that apply to this section.
+    for (const Elf_Shdr *RelSec : C->RelocSections) {
+      // Only support RELA for now.
+      if (RelSec->sh_type != SHT_RELA)
+        continue;
+      for (const Elf_Rela &RI : EObj->relas(RelSec)) {
+        uint32_t SymIndex = RI.getSymbol(EObj->isMips64EL());
+        SymbolBody *Body = File->getSymbolBody(SymIndex);
+        if (!Body)
+          continue;
+        // Skip undefined weak for now.
+        if (isa<UndefinedWeak<ELFT>>(Body))
+          continue;
+        if (!isa<DefinedRegular<ELFT>>(Body))
+          error(Twine("Can't relocate symbol ") + Body->getName());
+        uintX_t Offset = RI.r_offset;
+        uint32_t Type = RI.getType(EObj->isMips64EL());
+        uintX_t P = this->getVA() + C->getOutputSectionOff();
+        uintX_t SymVA = getSymVA<ELFT>(cast<DefinedRegular<ELFT>>(Body));
+        switch (Type) {
+        case llvm::ELF::R_X86_64_PC32:
+          support::endian::write32le(Base + Offset,
+                                     SymVA + (RI.r_addend - (P + Offset)));
+          break;
+        default:
+          llvm::errs() << Twine("unrecognized reloc ") + Twine(Type) << '\n';
+          break;
+        }
+      }
+    }
+  }
 }
 
 template <bool Is64Bits>
 void StringTableSection<Is64Bits>::writeTo(uint8_t *Buf) {
   StringRef Data = StrTabBuilder.data();
   memcpy(Buf, Data.data(), Data.size());
 }
 

lld/trunk/test/elf2/invalid-relocations.test

+# RUN: yaml2obj -format elf %s -o %t
+# RUN: not lld -flavor gnu2 %t -o %tout 2>&1 | FileCheck %s
+
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  OSABI:           ELFOSABI_GNU
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x0000000000000004
+    Content:         E800000000
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Info:            12 # Invalid index
+    Relocations:
+      - Offset:          0x0000000000000001
+        Symbol:          lulz
+        Type:            R_X86_64_PC32
+        Addend:          -4
+Symbols:
+  Global:
+    - Name:            lulz
+      Type:            STT_FUNC
+      Section:         .text
+
+# CHECK: Invalid relocated section index

lld/trunk/test/elf2/relocation.s

+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+// RUN: lld -flavor gnu2 %t -o %t2
+// RUN: llvm-objdump -d %t2 | FileCheck %s
+// REQUIRES: x86
+
+
+.section       .text,"ax",@progbits,unique,1
+.global _start
+_start:
+  call lulz
+
+.section       .text,"ax",@progbits,unique,2
+.zero 4
+.global lulz
+lulz:
+
+// CHECK: e8 04 00 00 00  callq   4