[llvm-objcopy] Add support for relocations

[jakehehrlich]

Summary

This change adds support for SHT_REL and SHT_RELA sections in llvm-objcopy

[jhenderson]

Not specifically related to this change, but I've seen a lot of cases when referencing the Sections vector, where you have to adjust the sh_link/sh_info value by one, to compensate for the lack of a null section in the vector. Would it be perhaps be easier to explicitly add a null section to the front of the vector up front?

As noted in D34167, symbol names are not necessarily unique, so the current algorithm for creating relocations won't work. I'll let you update this diff before trying to review it further!

tools/llvm-objcopy/Object.cpp

162

++Buf

172

Ditto

294–307

Looks to me like this block here and the block below for SHT_REL should be shared in a separate function.

[jakehehrlich]

1. Changed increments as James requested
2. Deduplicated Rel vs Rela code using setAddend and getAddend along with a new method initRelocations which is templated
3. Updated the code the work with LGTMed symbol table code

[jhenderson]

The overall approach looks fine, but I've just noticed that this code won't handle dynamic relocation sections properly, because their sh_link field will point to a dynamic symbol table (SHT_DYNSYM), which is not treated as a symbol table by the current code. If you make the change in the code separately to treat the dynamic symbol table as a SymbolTableSection for initialisation purposes, and adopt the changes I suggest in this review as well, regarding using "RelSec->Symbols" instead of "SymbolTable", then I think this should then work.

test/tools/llvm-objcopy/basic-relocations.test

92

Could you add a case for a relocation that doesn't refer to a symbol at all, please? This would be the case for e.g. R_X86_64_RELATIVE relocations.

tools/llvm-objcopy/Object.cpp

174–175

Debug text left in by accident?

342

Nits: relocaiton -> relocation. Also full stop!

345–346

We need to check that RelSec->Info and RelSec->Link are in range. Also, we should probably emit an error if the link section is not a symbol table.

350

This and the case below should use the relocation section's linked section (i.e. RelSec->Symbols), because it may refer to a symbol table that isn't the static symbol table.

[jakehehrlich]

In D36554#855174, @jhenderson wrote:

The overall approach looks fine, but I've just noticed that this code won't handle dynamic relocation sections properly, because their sh_link field will point to a dynamic symbol table (SHT_DYNSYM), which is not treated as a symbol table by the current code.

This is actually on purpose (for the most part). Dynamic relocations and dynamic symbol tables are allocated. We shouldn't change the size, layout, or content of allocated sections. I think the actual mistake I made here is treating allocated relocations as relocation sections when they should just be copied and not messed with. I have the same issue in dynamic string tables in fact (though I was aware of that issue but not this one). See how I planned on adding support for dynamic sections here: https://reviews.llvm.org/D36560. For instance say the DT_JMPREL .dynamic entry could be invalidated by messing with an allocated relocation. Also there's really no benefit to removing dynamic relocations since we can't change the size/layout of sections within a segment.

So I propose that we have two classes for relocations, one for allocated and one for non-allocated. This will mirror how I plan on adding support for dynamic symbol tables and dynamic string tables. We should throw an error if the link of an allocated relocation table doesn't have a dynamic (and allocated) symbol table as it's link.

I think support for dynamic/allocated relocations should be added in a later diff (perhaps D36560 or one immediately after it) but I'm fine adding some of it now since it mostly dosn't interact with things from that diff. If I were to add support in this diff I would add a class called DynamicRelocationsSection and it would be constructed when a SHT_REL(A) section is an allocated section instead of constructing a RelocationsSection. It would still have the setSection and setSymTab methods and would have a finalize method that did the same thing. It would inherit from Section rather than SectionBase so that the writeSection method was implemented correctly for us.

[jakehehrlich]

1. Added error handling requested by James
2. Fixed comment as requested by James

I did not add the requested test because yaml2obj doesn't support adding relocations without symbols. I plan on adding that feature to yaml2obj and then adding that test.

As another note I'm not convinced that this code will handle that case since I didn't consider it when writing this. I might need to change this to support that case.

[jhenderson]

In D36554#855706, @jakehehrlich wrote:

So I propose that we have two classes for relocations, one for allocated and one for non-allocated. This will mirror how I plan on adding support for dynamic symbol tables and dynamic string tables. We should throw an error if the link of an allocated relocation table doesn't have a dynamic (and allocated) symbol table as it's link.

I think support for dynamic/allocated relocations should be added in a later diff (perhaps D36560 or one immediately after it) but I'm fine adding some of it now since it mostly dosn't interact with things from that diff. If I were to add support in this diff I would add a class called DynamicRelocationsSection and it would be constructed when a SHT_REL(A) section is an allocated section instead of constructing a RelocationsSection. It would still have the setSection and setSymTab methods and would have a finalize method that did the same thing. It would inherit from Section rather than SectionBase so that the writeSection method was implemented correctly for us.

Seems reasonable to me. I'm happy with this change to be made in a different diff (either D36560 or subsequently, whichever you prefer).

I'm guessing that yaml2obj doesn't have support for setting sh_link/sh_info to invalid values? It would be nice to test that the errors get reported when we expect them, but it's not a priority, so can be added later, if somebody gets time.

tools/llvm-objcopy/Object.cpp

346

I think this message could be reworded slightly to read a bit better. Something like: "Link field value " <value> " in relocation section " <section name> " is invalid" would work, I think. Same goes for the info message below.

356

Similar to above, maybe "Link field of relocation section " <section name> " is not a symbol table".

[jakehehrlich]

I tested it and it is not possible to add invalid info or link values using yaml2obj. The info value is not allowed to be invalid or not exist. The link value can be any section name you'd like but it will be ignored and replaced with the symbol table index.

In this update:

1. Fixed comments

[jakehehrlich]

Added test for a relocation with no symbol since the change I made to yaml2obj landed

[jhenderson]

In D36554#856890, @jakehehrlich wrote:

I tested it and it is not possible to add invalid info or link values using yaml2obj. The info value is not allowed to be invalid or not exist. The link value can be any section name you'd like but it will be ignored and replaced with the symbol table index.

Ok, fair enough. No need for that to block this, but it should go somewhere on the "Nice to Have at some point" heap!

LGTM, with changes for the two most recent minor comments, and the removal of the debug text in writeRel.

test/tools/llvm-objcopy/symboless-relocation.test

1 ↗

(On Diff #113354)

This test should probably be renamed slightly to either no-symbol-relocation.test or symbolless-relocation.test (note the double 'l').

tools/llvm-objcopy/Object.cpp

340

Slight rewording: Now that all sections and symbols have been added we can...

[jakehehrlich]

Fixed comment and test file name. Should be good to land now.

[jhenderson]

Sorry, not all changes I asked for have been made - the debug text at line 174 of Object.cpp is still present. Also, the comment still needs fixing slightly.

tools/llvm-objcopy/Object.cpp

340

Please delete the extra "and symbols have been added" bit.

[jakehehrlich]

Sorry about that James. They should be fixed now.

[jhenderson]

LGTM, with the latest comment change I've suggested.

tools/llvm-objcopy/Object.cpp

340

There's still one rogue "and" in that sentence: "Now that all sections and symbols have been added and we can add" - the bold "and" should be removed.

I think you can also remove the "we can" later, along with one other minor bit of rewording. Full suggested comment:

// Now that all sections and symbols have been added we can add
// relocations that reference symbols and set the link and info fields for
// relocation sections.

[jakehehrlich]

Thanks!

Should actually be good to land now

[jhenderson]

Do you need me to commit it for you?

[jakehehrlich]

The Relocation struct had a field named Symbol and a type named Symbol. Some compilers fail on this by default and I'm not sure it is standard complaint. This change fixes that issue by renaming the field RelocSymbol.

test/tools/llvm-objcopy/basic-relocations.test

+# RUN: yaml2obj %s > %t
+# RUN: llvm-objcopy %t %t2
+# RUN: llvm-readobj -relocations %t2 | FileCheck %s
+
+!ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Content:         "0000000000000000"
+  - Name:            .rel.text
+    Type:            SHT_REL
+    Link:            .symtab
+    Info:            .text
+    Relocations:
+      - Offset: 0x1000
+        Symbol: foo
+        Type:   R_X86_64_PC32
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x2000
+    AddressAlign:    0x0000000000000010
+    Content:         "0000000000000000"
+  - Name:            .rel.data
+    Type:            SHT_REL
+    Link:            .symtab
+    Info:            .data
+    Relocations:
+      - Offset: 0x2000
+        Symbol: bar
+        Type:   R_X86_64_PC32
+  - Name:            .rela.data
+    Type:            SHT_RELA
+    Link:            .symtab
+    Info:            .data
+    Relocations:
+      - Offset: 0x2000
+        Symbol: barA
+        Type:   R_X86_64_PC32
+        Addend: 0x17
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    Info:            .text
+    Relocations:
+      - Offset: 0x1000
+        Symbol: fooA
+        Type:   R_X86_64_PC32
+        Addend: 0x13
+Symbols:
+  Global:
+    - Name:     _start
+      Type:     STT_FUNC
+      Section:  .text
+      Value:    0x1000
+      Size:     4
+    - Name:     foo
+      Type:     STT_FUNC
+      Size:     4
+    - Name:     fooA
+      Type:     STT_FUNC
+      Size:     4
+    - Name:     bar
+      Type:     STT_OBJECT
+      Size:     4
+    - Name:     barA
+      Type:     STT_OBJECT
+      Size:     4
+
+# CHECK:     Relocations [
+# CHECK-NEXT:  Section (2) .rel.text {
+# CHECK-NEXT:    0x1000 R_X86_64_PC32 foo 0x0
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Section (4) .rel.data {
+# CHECK-NEXT:    0x2000 R_X86_64_PC32 bar 0x0
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Section (5) .rela.data {
+# CHECK-NEXT:    0x2000 R_X86_64_PC32 barA 0x17
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Section (6) .rela.text {
+# CHECK-NEXT:    0x1000 R_X86_64_PC32 fooA 0x13
+# CHECK-NEXT:  }
+# CHECK-NEXT:]

test/tools/llvm-objcopy/no-symbol-relocation.test

+# RUN: yaml2obj %s > %t
+# RUN: llvm-objcopy %t %t2
+# RUN: llvm-readobj -relocations %t2 | FileCheck %s
+
+!ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Content:         "0000000000000000"
+  - Name:            .rel.text
+    Type:            SHT_REL
+    Link:            .symtab
+    Info:            .text
+    Relocations:
+      - Offset: 0x1000
+        Type:   R_X86_64_RELATIVE
+
+# CHECK:     Relocations [
+# CHECK-NEXT:  Section (2) .rel.text {
+# CHECK-NEXT:    0x1000 R_X86_64_RELATIVE - 0x0
+# CHECK-NEXT:  }
+# CHECK-NEXT:]

tools/llvm-objcopy/Object.h

public:
   }
 };
 
 // Only writeSection depends on the ELF type so we implement it in a subclass.
 template <class ELFT> class SymbolTableSectionImpl : public SymbolTableSection {
   void writeSection(llvm::FileOutputBuffer &Out) const override;
 };
 
+struct Relocation {
+  const Symbol *RelocSymbol;
+  uint64_t Offset;
+  uint64_t Addend;
+  uint32_t Type;
+};
+
+template <class ELFT> class RelocationSection : public SectionBase {
+private:
+  typedef typename ELFT::Rel Elf_Rel;
+  typedef typename ELFT::Rela Elf_Rela;
+
+  std::vector<Relocation> Relocations;
+  SymbolTableSection *Symbols;
+  SectionBase *SecToApplyRel;
+
+  template <class T> void writeRel(T *Buf) const;
+
+public:
+  void setSymTab(SymbolTableSection *StrTab) { Symbols = StrTab; }
+  void setSection(SectionBase *Sec) { SecToApplyRel = Sec; }
+  void addRelocation(Relocation Rel) { Relocations.push_back(Rel); }
+  void finalize() override;
+  void writeSection(llvm::FileOutputBuffer &Out) const override;
+  static bool classof(const SectionBase *S) {
+    return S->Type == llvm::ELF::SHT_REL || S->Type == llvm::ELF::SHT_RELA;
+  }
+};
+
 template <class ELFT> class Object {
 private:
   typedef std::unique_ptr<SectionBase> SecPtr;
   typedef std::unique_ptr<Segment> SegPtr;
 
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Ehdr Elf_Ehdr;
   typedef typename ELFT::Phdr Elf_Phdr;

tools/llvm-objcopy/Object.cpp

for (auto &Symbol : Symbols) {
     if (Symbol->DefinedIn)
       Sym->st_shndx = Symbol->DefinedIn->Index;
     else
       Sym->st_shndx = SHN_UNDEF;
     ++Sym;
   }
 }
 
+template <class ELFT> void RelocationSection<ELFT>::finalize() {
+  this->Link = Symbols->Index;
+  this->Info = SecToApplyRel->Index;
+}
+
+template <class ELFT>
+void setAddend(Elf_Rel_Impl<ELFT, false> &Rel, uint64_t Addend) {}
+
+template <class ELFT>
+void setAddend(Elf_Rel_Impl<ELFT, true> &Rela, uint64_t Addend) {
+  Rela.r_addend = Addend;
+}
+
+template <class ELFT>
+template <class T>
+void RelocationSection<ELFT>::writeRel(T *Buf) const {
+  for (const auto &Reloc : Relocations) {
+    Buf->r_offset = Reloc.Offset;
+    setAddend(*Buf, Reloc.Addend);
+    Buf->setSymbolAndType(Reloc.RelocSymbol->Index, Reloc.Type, false);
+    ++Buf;
+  }
+}
+
+template <class ELFT>
+void RelocationSection<ELFT>::writeSection(llvm::FileOutputBuffer &Out) const {
+  uint8_t *Buf = Out.getBufferStart() + Offset;
+  if (Type == SHT_REL)
+    writeRel(reinterpret_cast<Elf_Rel *>(Buf));
+  else
+    writeRel(reinterpret_cast<Elf_Rela *>(Buf));
+}
+
 // Returns true IFF a section is wholly inside the range of a segment
 static bool sectionWithinSegment(const SectionBase &Section,
                                  const Segment &Segment) {
   // If a section is empty it should be treated like it has a size of 1. This is
   // to clarify the case when an empty section lies on a boundary between two
   // segments and ensures that the section "belongs" to the second segment and
   // not the first.
   uint64_t SecSize = Section.Size ? Section.Size : 1;
if (Sym.st_shndx != SHN_UNDEF) {
       DefSection = Sections[Sym.st_shndx - 1].get();
     }
     SymTab->addSymbol(Name, Sym.getBinding(), Sym.getType(), DefSection,
                       Sym.getValue(), Sym.st_size);
   }
 }
 
 template <class ELFT>
+static void getAddend(uint64_t &ToSet, const Elf_Rel_Impl<ELFT, false> &Rel) {}
+
+template <class ELFT>
+static void getAddend(uint64_t &ToSet, const Elf_Rel_Impl<ELFT, true> &Rela) {
+  ToSet = Rela.r_addend;
+}
+
+template <class ELFT, class T>
+void initRelocations(RelocationSection<ELFT> *Relocs,
+                     SymbolTableSection *SymbolTable, T RelRange) {
+  for (const auto &Rel : RelRange) {
+    Relocation ToAdd;
+    ToAdd.Offset = Rel.r_offset;
+    getAddend(ToAdd.Addend, Rel);
+    ToAdd.Type = Rel.getType(false);
+    ToAdd.RelocSymbol = SymbolTable->getSymbolByIndex(Rel.getSymbol(false));
+    Relocs->addRelocation(ToAdd);
+  }
+}
+
+template <class ELFT>
 std::unique_ptr<SectionBase>
 Object<ELFT>::makeSection(const llvm::object::ELFFile<ELFT> &ElfFile,
                           const Elf_Shdr &Shdr) {
   ArrayRef<uint8_t> Data;
   switch (Shdr.sh_type) {
+  case SHT_REL:
+  case SHT_RELA:
+    return llvm::make_unique<RelocationSection<ELFT>>();
   case SHT_STRTAB:
     return llvm::make_unique<StringTableSection>();
   case SHT_SYMTAB: {
     auto SymTab = llvm::make_unique<SymbolTableSectionImpl<ELFT>>();
     SymbolTable = SymTab.get();
     return std::move(SymTab);
   }
   case SHT_NOBITS:
     return llvm::make_unique<Section>(Data);
   default:
     Data = unwrapOrError(ElfFile.getSectionContents(&Shdr));
     return llvm::make_unique<Section>(Data);
   }
 }
 
 template <class ELFT>
 void Object<ELFT>::readSectionHeaders(const ELFFile<ELFT> &ElfFile) {
   uint32_t Index = 0;
   for (const auto &Shdr : unwrapOrError(ElfFile.sections())) {
     if (Index == 0) {
for (const auto &Shdr : unwrapOrError(ElfFile.sections())) {
     Sec->Index = Index++;
     Sections.push_back(std::move(Sec));
   }
 
   // Now that all of the sections have been added we can fill out some extra
   // details about symbol tables.
   if (SymbolTable)
     initSymbolTable(ElfFile, SymbolTable);
+
+  // Now that all sections and symbols have been added we can add
+  // relocations that reference symbols and set the link and info fields for
+  // relocation sections.
+  for (auto &Section : Sections) {
+    if (auto RelSec = dyn_cast<RelocationSection<ELFT>>(Section.get())) {
+      if (RelSec->Link - 1 >= Sections.size() || RelSec->Link == 0) {
+        error("Link field value " + Twine(RelSec->Link) + " in section " +
+              RelSec->Name + " is invalid");
+      }
+      if (RelSec->Info - 1 >= Sections.size() || RelSec->Info == 0) {
+        error("Info field value " + Twine(RelSec->Link) + " in section " +
+              RelSec->Name + " is invalid");
+      }
+      auto SymTab =
+          dyn_cast<SymbolTableSection>(Sections[RelSec->Link - 1].get());
+      if (SymTab == nullptr) {
+        error("Link field of relocation section " + RelSec->Name +
+              " is not a symbol table");
+      }
+      RelSec->setSymTab(SymTab);
+      RelSec->setSection(Sections[RelSec->Info - 1].get());
+      auto Shdr = unwrapOrError(ElfFile.sections()).begin() + RelSec->Index;
+      if (RelSec->Type == SHT_REL)
+        initRelocations(RelSec, SymTab, unwrapOrError(ElfFile.rels(Shdr)));
+      else
+        initRelocations(RelSec, SymTab, unwrapOrError(ElfFile.relas(Shdr)));
+    }
+  }
 }
 
 template <class ELFT> Object<ELFT>::Object(const ELFObjectFile<ELFT> &Obj) {
   const auto &ElfFile = *Obj.getELFFile();
   const auto &Ehdr = *ElfFile.getHeader();
 
   std::copy(Ehdr.e_ident, Ehdr.e_ident + 16, Ident);
   Type = Ehdr.e_type;