[lld-macho] Avoid unnecessary preprocessing of relocations

[int3]

Summary

Previously, we parsed them into a Reloc struct when reading the input,
but that's unnecessary. Handling them at output time is closer to what
lld-ELF is doing, and should make future parallelization work easier.

Depends on D79114.

[int3]

update

[smeenai]

Hmm. I thought part of the reason the original prototype parsed them early was to handle subsections via symbols (where you may need to adjust relocations based on subsection splitting). Do you have a sense of how this would play with that?

If I understand our current setup, we're parsing the relocations early but only resolving them (as in writing out their target) at the end, so that end part should still represent opportunities for parallelism, I think. (We should also figure out exactly what it is that COFF and ELF parallelize, and check if our design can handle parallelizing those as well.)

[int3]

I'm still a bit hazy on how subsections and their relocations will end up looking like, but I don't see why we might need to adjust relocations at load time instead of at output time. From what I understand, we basically need to figure out which subsection a given relocation's address points into. Presumably subsections will keep track of their original address ranges in the input file, so we can do the relocation -> subsection mapping at output time too. Well, I should probably have a look at how ld64 handles subsections...

[int3]

I *think* what ld64 does is to translate the raw relocation structures into "fixups" that target specific atoms / subsections. But it's still not clear to me that we can't do the relocation -> subsection mapping at output time. Moreover, given the current state of the implementation, I don't think having a separate Reloc struct is super useful -- all we're really doing is doing a 1:1 copy of various field values, plus the symbol/section resolution, and the latter can definitely be done at output time.

[pcc]

The architecture may need to be different here IMHO because of subsections. Don't forget that you need to map relocations onto subsections in order to implement gc-sections, and depending on the number of subsections you have per section, that could get expensive without an intermediate data structure. On top of that you'd still need the O(M log N) at output time. To me it seemed better to pay the O(M log N) up front once and avoid the cost at gc-sections time.

[int3]

Oh, that makes sense, I hadn't thought about gc-sections. Thanks for the insight @pcc!

lld/MachO/InputFiles.h

public:
   std::vector<Symbol *> symbols;
   std::vector<InputSection *> sections;
 
 protected:
   InputFile(Kind kind, MemoryBufferRef mb) : mb(mb), fileKind(kind) {}
 
   std::vector<InputSection *> parseSections(ArrayRef<llvm::MachO::section_64>);
 
-  void parseRelocations(const llvm::MachO::section_64 &,
-                        std::vector<Reloc> &relocs);
-
 private:
   const Kind fileKind;
 };
 
 // .o file
 class ObjFile : public InputFile {
 public:
   explicit ObjFile(MemoryBufferRef mb);

lld/MachO/InputFiles.cpp

for (const section_64 &sec : sections) {
     isec->segname = StringRef(sec.segname, strnlen(sec.segname, 16));
     isec->data = {buf + sec.offset, static_cast<size_t>(sec.size)};
     if (sec.align >= 32)
       error("alignment " + std::to_string(sec.align) + " of section " +
             isec->name + " is too large");
     else
       isec->align = 1 << sec.align;
     isec->flags = sec.flags;
+    isec->relOff = sec.reloff;
+    isec->nReloc = sec.nreloc;
     ret.push_back(isec);
   }
 
   return ret;
 }
 
-void InputFile::parseRelocations(const section_64 &sec,
-                                 std::vector<Reloc> &relocs) {
-  auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
-  ArrayRef<any_relocation_info> relInfos(
-      reinterpret_cast<const any_relocation_info *>(buf + sec.reloff),
-      sec.nreloc);
-
-  for (const any_relocation_info &anyRel : relInfos) {
-    Reloc r;
-    if (anyRel.r_word0 & R_SCATTERED) {
-      error("TODO: Scattered relocations not supported");
-    } else {
-      auto rel = reinterpret_cast<const relocation_info &>(anyRel);
-      r.type = rel.r_type;
-      r.offset = rel.r_address;
-      r.addend = target->getImplicitAddend(buf + sec.offset + r.offset, r.type);
-      if (rel.r_extern)
-        r.target = symbols[rel.r_symbolnum];
-      else {
-        error("TODO: Non-extern relocations are not supported");
-        continue;
-      }
-    }
-    relocs.push_back(r);
-  }
-}
-
 ObjFile::ObjFile(MemoryBufferRef mb) : InputFile(ObjKind, mb) {
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
   ArrayRef<section_64> objSections;
 
   if (const load_command *cmd = findCommand(hdr, LC_SEGMENT_64)) {
     auto *c = reinterpret_cast<const segment_command_64 *>(cmd);
     objSections = ArrayRef<section_64>{
for (const nlist_64 &sym : nList) {
         symbols.push_back(symtab->addDefined(name, isec, value));
         continue;
       }
 
       // Local defined symbol
       symbols.push_back(make<Defined>(name, isec, value));
     }
   }
-
-  // The relocations may refer to the symbols, so we parse them after we have
-  // the symbols loaded.
-  if (!sections.empty()) {
-    auto it = sections.begin();
-    for (const section_64 &sec : objSections) {
-      parseRelocations(sec, (*it)->relocs);
-      ++it;
-    }
-  }
 }
 
 DylibFile::DylibFile(MemoryBufferRef mb) : InputFile(DylibKind, mb) {
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
 
   // Initialize dylibName.
   if (const load_command *cmd = findCommand(hdr, LC_ID_DYLIB)) {

lld/MachO/InputSection.h

 namespace lld {
 namespace macho {
 
 class InputFile;
 class InputSection;
 class OutputSegment;
 class Symbol;
 
-struct Reloc {
-  uint8_t type;
-  uint32_t addend;
-  uint32_t offset;
-  llvm::PointerUnion<Symbol *, InputSection *> target;
-};
-
 class InputSection {
 public:
   virtual ~InputSection() = default;
   virtual size_t getSize() const { return data.size(); }
   virtual uint64_t getFileSize() const { return getSize(); }
   uint64_t getFileOffset() const;
   // Don't emit section_64 headers for hidden sections.
   virtual bool isHidden() const { return false; }
   // Unneeded sections are omitted entirely (header and body).
   virtual bool isNeeded() const { return true; }
   virtual void writeTo(uint8_t *buf);
+  ArrayRef<llvm::MachO::any_relocation_info> relocations() const;
 
   InputFile *file = nullptr;
   OutputSegment *parent = nullptr;
   StringRef name;
   StringRef segname;
 
   ArrayRef<uint8_t> data;
 
   // TODO these properties ought to live in an OutputSection class.
   // Move them once available.
   uint64_t addr = 0;
   uint32_t align = 1;
   uint32_t sectionIndex = 0;
   uint32_t flags = 0;
 
-  std::vector<Reloc> relocs;
+  // Relocation data offset in the input file.
+  uint32_t relOff = 0;
+  // Number of relocation entries.
+  uint32_t nReloc = 0;
 };
 
 extern std::vector<InputSection *> inputSections;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/InputSection.cpp

 //===- InputSection.cpp ---------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
+#include "InputFiles.h"
 #include "OutputSegment.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
+
+#include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<InputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileOffset() const {
   return parent->fileOff + addr - parent->firstSection()->addr;
 }
 
 void InputSection::writeTo(uint8_t *buf) {
   if (!data.empty())
     memcpy(buf, data.data(), data.size());
 
-  for (Reloc &r : relocs) {
+  for (const any_relocation_info &anyRel : relocations()) {
+    if (anyRel.r_word0 & R_SCATTERED)
+      fatal("TODO: Scattered relocations not supported");
+
+    auto rel = reinterpret_cast<const relocation_info &>(anyRel);
+    uint32_t addend =
+        target->getImplicitAddend(buf + rel.r_address, rel.r_type);
     uint64_t va = 0;
-    if (auto *s = r.target.dyn_cast<Symbol *>()) {
-      if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s)) {
-        va = target->getDylibSymbolVA(*dylibSymbol, r.type);
-      } else {
+    if (rel.r_extern) {
+      Symbol *s = file->symbols[rel.r_symbolnum];
+      if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
+        va = target->getDylibSymbolVA(*dylibSymbol, rel.r_type);
+      else
         va = s->getVA();
-      }
-    } else if (auto *isec = r.target.dyn_cast<InputSection *>()) {
-      va = isec->addr;
     } else {
-      llvm_unreachable("Unknown relocation target");
+      fatal("TODO: Non-extern relocations are not supported");
     }
 
-    uint64_t val = va + r.addend;
-    if (1) // TODO: handle non-pcrel relocations
-      val -= addr + r.offset;
-    target->relocateOne(buf + r.offset, r.type, val);
-  }
+    uint64_t val = va + addend;
+    if (rel.r_pcrel)
+      val -= addr + rel.r_address;
+    else
+      fatal("TODO: handle non-pcrel relocations");
+
+    target->relocateOne(buf + rel.r_address, rel.r_type, val);
+  }
+
+ArrayRef<llvm::MachO::any_relocation_info> InputSection::relocations() const {
+  // Synthetic sections will not have a corresponding InputFile.
+  if (file == nullptr)
+    return {};
+
+  return {reinterpret_cast<const any_relocation_info *>(
+              file->mb.getBufferStart() + relOff),
+          nReloc};
 }

lld/MachO/Writer.cpp

 template <typename SectionType, typename... ArgT>
 SectionType *createInputSection(ArgT &&... args) {
   auto *section = make<SectionType>(std::forward<ArgT>(args)...);
   inputSections.push_back(section);
   return section;
 }
 
 void Writer::scanRelocations() {
-  for (InputSection *sect : inputSections)
-    for (Reloc &r : sect->relocs)
-      if (auto *s = r.target.dyn_cast<Symbol *>())
+  for (InputSection *isec : inputSections) {
+    for (const any_relocation_info &anyRel : isec->relocations()) {
+      if (anyRel.r_word0 & R_SCATTERED)
+        fatal("TODO: Scattered relocations not supported");
+
+      auto rel = reinterpret_cast<const relocation_info &>(anyRel);
+      if (rel.r_extern) {
+        Symbol *s = isec->file->symbols[rel.r_symbolnum];
         if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
-          target->prepareDylibSymbolRelocation(*dylibSymbol, r.type);
+          target->prepareDylibSymbolRelocation(*dylibSymbol, rel.r_type);
+      }
+    }
+  }
 }
 
 void Writer::createLoadCommands() {
   headerSection->addLoadCommand(
       make<LCDyldInfo>(bindingSection, lazyBindingSection, exportSection));
   headerSection->addLoadCommand(
       make<LCSymtab>(symtabSection, stringTableSection));
   headerSection->addLoadCommand(make<LCDysymtab>());