[lld-macho][NFC] Handle GOT bindings and regular bindings more uniformly

[int3]

Summary

Previously, the BindingEntry struct could only store bindings to offsets
within InputSections. Since the GOTSection and TLVPointerSections are
OutputSections, I handled those in a separate code path. However, this
makes it awkward to support weak bindings properly without code
duplication. This diff allows BindingEntries to point directly to
OutputSections, simplifying the upcoming weak binding implementation.

Along the way, I also converted a bunch of functions taking references
to symbols to take pointers instead. Given how much casting we do for
Symbol (especially in the upcoming weak binding diffs), it's cleaner
this way.

[smeenai]

LGTM; this is a nice cleanup.

lld/MachO/SyntheticSections.cpp

109

I get that we're accounting for the got and tlvPointers the same as all other bindings now, but how come we don't need the bindings.size() != 0 check at all anymore?

[int3]

lld/MachO/SyntheticSections.cpp

109

oops -- I'd meant to move this method to the header, not delete it

(we don't have a test that checks to make sure we don't emit a BindingSection when we don't need one... not super important since it doesn't affect correctness, but I'll see if it's easy to add)

[int3]

fix, add test

lld/MachO/Arch/X86_64.cpp

uint64_t getImplicitAddend(MemoryBufferRef, const section_64 &,
                              const relocation_info &) const override;
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t val) const override;
 
   void writeStub(uint8_t *buf, const DylibSymbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                             uint64_t entryAddr) const override;
 
-  void prepareSymbolRelocation(lld::macho::Symbol &, const InputSection *,
+  void prepareSymbolRelocation(lld::macho::Symbol *, const InputSection *,
                                const Reloc &) override;
   uint64_t resolveSymbolVA(uint8_t *buf, const lld::macho::Symbol &,
                            uint8_t type) const override;
 };
 
 } // namespace
 
 static std::string getErrorLocation(MemoryBufferRef mb, const section_64 &sec,

 void X86_64::writeStubHelperEntry(uint8_t *buf, const DylibSymbol &sym,
                                   uint64_t entryAddr) const {
   memcpy(buf, stubHelperEntry, sizeof(stubHelperEntry));
   write32le(buf + 1, sym.lazyBindOffset);
   writeRipRelative(buf, entryAddr, sizeof(stubHelperEntry),
                    in.stubHelper->addr);
 }
 
-void X86_64::prepareSymbolRelocation(lld::macho::Symbol &sym,
+void X86_64::prepareSymbolRelocation(lld::macho::Symbol *sym,
                                      const InputSection *isec, const Reloc &r) {
   switch (r.type) {
   case X86_64_RELOC_GOT_LOAD:
     // TODO: implement mov -> lea relaxation for non-dynamic symbols
   case X86_64_RELOC_GOT:
     in.got->addEntry(sym);
-    if (sym.isTlv())
+    if (sym->isTlv())
       error("found GOT relocation referencing thread-local variable in " +
             toString(isec));
     break;
   case X86_64_RELOC_BRANCH: {
     // TODO: weak dysyms should go into the weak binding section instead
-    if (auto *dysym = dyn_cast<DylibSymbol>(&sym))
-      in.stubs->addEntry(*dysym);
+    if (auto *dysym = dyn_cast<DylibSymbol>(sym))
+      in.stubs->addEntry(dysym);
     break;
   }
   case X86_64_RELOC_UNSIGNED: {
-    if (auto *dysym = dyn_cast<DylibSymbol>(&sym)) {
+    if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
       if (r.length != 3) {
         error("X86_64_RELOC_UNSIGNED referencing the dynamic symbol " +
               dysym->getName() + " must have r_length = 3");
         return;
       }
       in.binding->addEntry(dysym, isec, r.offset, r.addend);
     }
     break;
   }
   case X86_64_RELOC_SIGNED:
   case X86_64_RELOC_SIGNED_1:
   case X86_64_RELOC_SIGNED_2:
   case X86_64_RELOC_SIGNED_4:
     break;
   case X86_64_RELOC_TLV:
-    if (isa<DylibSymbol>(&sym)) {
+    if (isa<DylibSymbol>(sym)) {
       in.tlvPointers->addEntry(sym);
     } else {
-      assert(isa<Defined>(&sym));
+      assert(isa<Defined>(sym));
       // TLV relocations on x86_64 are always used with a movq opcode, which
       // can be converted to leaq opcodes if they reference a defined symbol.
       // (This is in contrast to GOT relocations, which can be used with
       // non-movq opcodes.) As such, there is no need to add an entry to
       // tlvPointers here.
     }
-    if (!sym.isTlv())
+    if (!sym->isTlv())
       error(
           "found X86_64_RELOC_TLV referencing a non-thread-local variable in " +
           toString(isec));
     break;
   case X86_64_RELOC_SUBTRACTOR:
     fatal("TODO: handle relocation type " + std::to_string(r.type));
     break;
   default:

lld/MachO/SyntheticSections.h

 
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
+#include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace lld {
 namespace macho {
 
 namespace section_names {
 
public:
   const llvm::SetVector<const Symbol *> &getEntries() const { return entries; }
 
   bool isNeeded() const override { return !entries.empty(); }
 
   uint64_t getSize() const override { return entries.size() * WordSize; }
 
   void writeTo(uint8_t *buf) const override;
 
-  void addEntry(Symbol &sym);
+  void addEntry(Symbol *sym);
 
 private:
   llvm::SetVector<const Symbol *> entries;
 };
 
 class GotSection : public NonLazyPointerSectionBase {
 public:
   GotSection()
       : NonLazyPointerSectionBase(segment_names::dataConst,
                                   section_names::got) {
     // TODO: section_64::reserved1 should be an index into the indirect symbol
     // table, which we do not currently emit
   }
 };
 
 class TlvPointerSection : public NonLazyPointerSectionBase {
 public:
   TlvPointerSection()
       : NonLazyPointerSectionBase(segment_names::data,
                                   section_names::threadPtrs) {}
 };
 
+using SectionPointerUnion =
+    llvm::PointerUnion<const InputSection *, const OutputSection *>;
+
 struct BindingEntry {
   const DylibSymbol *dysym;
-  const InputSection *isec;
+  SectionPointerUnion section;
   uint64_t offset;
   int64_t addend;
-  BindingEntry(const DylibSymbol *dysym, const InputSection *isec,
+
+  BindingEntry(const DylibSymbol *dysym, SectionPointerUnion section,
                uint64_t offset, int64_t addend)
-      : dysym(dysym), isec(isec), offset(offset), addend(addend) {}
+      : dysym(dysym), section(section), offset(offset), addend(addend) {}
+
+  uint64_t getVA() const;
 };
 
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection : public LinkEditSection {
 public:
   BindingSection();
   void finalizeContents();
   uint64_t getRawSize() const override { return contents.size(); }
   // Like other sections in __LINKEDIT, the binding section is special: its
   // offsets are recorded in the LC_DYLD_INFO_ONLY load command, instead of in
   // section headers.
   bool isHidden() const override { return true; }
-  bool isNeeded() const override;
   void writeTo(uint8_t *buf) const override;
 
-  void addEntry(const DylibSymbol *dysym, const InputSection *isec,
-                uint64_t offset, int64_t addend) {
-    bindings.emplace_back(dysym, isec, offset, addend);
+  void addEntry(const DylibSymbol *dysym, SectionPointerUnion section,
+                uint64_t offset, int64_t addend = 0) {
+    bindings.emplace_back(dysym, section, offset, addend);
   }
 
 private:
   std::vector<BindingEntry> bindings;
   SmallVector<char, 128> contents;
 };
 
 // The following sections implement lazy symbol binding -- very similar to the

 public:
   StubsSection();
   uint64_t getSize() const override;
   bool isNeeded() const override { return !entries.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   const llvm::SetVector<DylibSymbol *> &getEntries() const { return entries; }
 
-  void addEntry(DylibSymbol &sym);
+  void addEntry(DylibSymbol *sym);
 
 private:
   llvm::SetVector<DylibSymbol *> entries;
 };
 
 class StubHelperSection : public SyntheticSection {
 public:
   StubHelperSection();

lld/MachO/SyntheticSections.cpp

 
 NonLazyPointerSectionBase::NonLazyPointerSectionBase(const char *segname,
                                                      const char *name)
     : SyntheticSection(segname, name) {
   align = 8;
   flags = MachO::S_NON_LAZY_SYMBOL_POINTERS;
 }
 
-void NonLazyPointerSectionBase::addEntry(Symbol &sym) {
-  if (entries.insert(&sym)) {
-    assert(sym.gotIndex == UINT32_MAX);
-    sym.gotIndex = entries.size() - 1;
+void NonLazyPointerSectionBase::addEntry(Symbol *sym) {
+  if (entries.insert(sym)) {
+    assert(sym->gotIndex == UINT32_MAX);
+    sym->gotIndex = entries.size() - 1;
+
+    if (auto *dysym = dyn_cast<DylibSymbol>(sym))
+      in.binding->addEntry(dysym, this, sym->gotIndex * WordSize);
   }
 }
 
 void NonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
   for (size_t i = 0, n = entries.size(); i < n; ++i)
     if (auto *defined = dyn_cast<Defined>(entries[i]))
       write64le(&buf[i * WordSize], defined->getVA());
 }
 
 BindingSection::BindingSection()
     : LinkEditSection(segment_names::linkEdit, section_names::binding) {}
 
-bool BindingSection::isNeeded() const {
-  return bindings.size() != 0 || in.got->isNeeded() ||
-         in.tlvPointers->isNeeded();
-}
-
 namespace {
 struct Binding {
   OutputSegment *segment = nullptr;
   uint64_t offset = 0;
   int64_t addend = 0;
   uint8_t ordinal = 0;
 };
 } // namespace
 
 // Encode a sequence of opcodes that tell dyld to write the address of dysym +
 // addend at osec->addr + outSecOff.
 //
 // The bind opcode "interpreter" remembers the values of each binding field, so
 // we only need to encode the differences between bindings. Hence the use of
 // lastBinding.
-static void encodeBinding(const DylibSymbol &dysym, const OutputSection *osec,
+static void encodeBinding(const DylibSymbol *dysym, const OutputSection *osec,
                           uint64_t outSecOff, int64_t addend,
                           Binding &lastBinding, raw_svector_ostream &os) {
   using namespace llvm::MachO;
   OutputSegment *seg = osec->parent;
   uint64_t offset = osec->getSegmentOffset() + outSecOff;
   if (lastBinding.segment != seg) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                                seg->index);
     encodeULEB128(offset, os);
     lastBinding.segment = seg;
     lastBinding.offset = offset;
   } else if (lastBinding.offset != offset) {
     os << static_cast<uint8_t>(BIND_OPCODE_ADD_ADDR_ULEB);
     encodeULEB128(offset - lastBinding.offset, os);
     lastBinding.offset = offset;
   }
 
-  if (lastBinding.ordinal != dysym.file->ordinal) {
-    if (dysym.file->ordinal <= BIND_IMMEDIATE_MASK) {
+  if (lastBinding.ordinal != dysym->file->ordinal) {
+    if (dysym->file->ordinal <= BIND_IMMEDIATE_MASK) {
       os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
-                                 dysym.file->ordinal);
+                                 dysym->file->ordinal);
     } else {
       os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
-      encodeULEB128(dysym.file->ordinal, os);
+      encodeULEB128(dysym->file->ordinal, os);
     }
-    lastBinding.ordinal = dysym.file->ordinal;
+    lastBinding.ordinal = dysym->file->ordinal;
   }
 
   if (lastBinding.addend != addend) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB);
     encodeSLEB128(addend, os);
     lastBinding.addend = addend;
   }
 
   os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
-     << dysym.getName() << '\0'
+     << dysym->getName() << '\0'
      << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER)
      << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += WordSize;
 }
 
-static bool encodeNonLazyPointerSection(NonLazyPointerSectionBase *osec,
-                                        Binding &lastBinding,
-                                        raw_svector_ostream &os) {
-  bool didEncode = false;
-  size_t idx = 0;
-  for (const Symbol *sym : osec->getEntries()) {
-    if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
-      didEncode = true;
-      encodeBinding(*dysym, osec, idx * WordSize, /*addend=*/0, lastBinding,
-                    os);
-    }
-    ++idx;
-  }
-  return didEncode;
+uint64_t BindingEntry::getVA() const {
+  if (auto *isec = section.dyn_cast<const InputSection *>())
+    return isec->getVA() + offset;
+  auto *osec = section.get<const OutputSection *>();
+  return osec->addr + offset;
 }
 
 // Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
 // interprets to update a record with the following fields:
 //  * segment index (of the segment to write the symbol addresses to, typically
 //    the __DATA_CONST segment which contains the GOT)
 //  * offset within the segment, indicating the next location to write a binding
 //  * symbol type
 //  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
 //  * symbol name
 //  * addend
 // When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
 // a symbol in the GOT, and increments the segment offset to point to the next
 // entry. It does *not* clear the record state after doing the bind, so
 // subsequent opcodes only need to encode the differences between bindings.
 void BindingSection::finalizeContents() {
   raw_svector_ostream os{contents};
   Binding lastBinding;
-  bool didEncode = encodeNonLazyPointerSection(in.got, lastBinding, os);
-  didEncode |= encodeNonLazyPointerSection(in.tlvPointers, lastBinding, os);
 
-  // Sorting the relocations by segment and address allows us to encode them
-  // more compactly.
+  // Since bindings are delta-encoded, sorting them allows for a more compact
+  // result. Note that sorting by address alone ensures that bindings for the
+  // same segment / section are located together.
   llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
-    OutputSegment *segA = a.isec->parent->parent;
-    OutputSegment *segB = b.isec->parent->parent;
-    if (segA != segB)
-      return segA->fileOff < segB->fileOff;
-    OutputSection *osecA = a.isec->parent;
-    OutputSection *osecB = b.isec->parent;
-    if (osecA != osecB)
-      return osecA->addr < osecB->addr;
-    if (a.isec != b.isec)
-      return a.isec->outSecOff < b.isec->outSecOff;
-    return a.offset < b.offset;
+    return a.getVA() < b.getVA();
   });
   for (const BindingEntry &b : bindings) {
-    didEncode = true;
-    encodeBinding(*b.dysym, b.isec->parent, b.isec->outSecOff + b.offset,
-                  b.addend, lastBinding, os);
+    if (auto *isec = b.section.dyn_cast<const InputSection *>()) {
+      encodeBinding(b.dysym, isec->parent, isec->outSecOff + b.offset, b.addend,
+                    lastBinding, os);
+    } else {
+      auto *osec = b.section.get<const OutputSection *>();
+      encodeBinding(b.dysym, osec, b.offset, b.addend, lastBinding, os);
+    }
   }
-  if (didEncode)
+  if (!bindings.empty())
     os << static_cast<uint8_t>(MachO::BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
 }
 
 StubsSection::StubsSection()
     : SyntheticSection(segment_names::text, "__stubs") {}
 
 uint64_t StubsSection::getSize() const {
   return entries.size() * target->stubSize;
 }
 
 void StubsSection::writeTo(uint8_t *buf) const {
   size_t off = 0;
   for (const DylibSymbol *sym : in.stubs->getEntries()) {
     target->writeStub(buf + off, *sym);
     off += target->stubSize;
   }
 }
 
-void StubsSection::addEntry(DylibSymbol &sym) {
-  if (entries.insert(&sym))
-    sym.stubsIndex = entries.size() - 1;
+void StubsSection::addEntry(DylibSymbol *sym) {
+  if (entries.insert(sym))
+    sym->stubsIndex = entries.size() - 1;
 }
 
 StubHelperSection::StubHelperSection()
     : SyntheticSection(segment_names::text, "__stub_helper") {}
 
 uint64_t StubHelperSection::getSize() const {
   return target->stubHelperHeaderSize +
          in.stubs->getEntries().size() * target->stubHelperEntrySize;

 
 void StubHelperSection::setup() {
   stubBinder = dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder"));
   if (stubBinder == nullptr) {
     error("symbol dyld_stub_binder not found (normally in libSystem.dylib). "
           "Needed to perform lazy binding.");
     return;
   }
-  in.got->addEntry(*stubBinder);
+  in.got->addEntry(stubBinder);
 
   inputSections.push_back(in.imageLoaderCache);
   symtab->addDefined("__dyld_private", in.imageLoaderCache, 0,
                      /*isWeakDef=*/false);
 }
 
 ImageLoaderCacheSection::ImageLoaderCacheSection() {
   segname = segment_names::data;

lld/MachO/Target.h

public:
   virtual void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                                     uint64_t entryAddr) const = 0;
 
   // Symbols may be referenced via either the GOT or the stubs section,
   // depending on the relocation type. prepareSymbolRelocation() will set up the
   // GOT/stubs entries, and resolveSymbolVA() will return the addresses of those
   // entries. resolveSymbolVA() may also relax the target instructions to save
   // on a level of address indirection.
-  virtual void prepareSymbolRelocation(Symbol &, const InputSection *,
+  virtual void prepareSymbolRelocation(Symbol *, const InputSection *,
                                        const Reloc &) = 0;
   virtual uint64_t resolveSymbolVA(uint8_t *buf, const Symbol &,
                                    uint8_t type) const = 0;
 
   uint32_t cpuType;
   uint32_t cpuSubtype;
 
   size_t stubSize;

lld/MachO/Writer.cpp

 void Writer::scanRelocations() {
   for (InputSection *isec : inputSections) {
     for (Reloc &r : isec->relocs) {
       if (auto *s = r.target.dyn_cast<lld::macho::Symbol *>()) {
         if (isa<Undefined>(s))
           error("undefined symbol " + s->getName() + ", referenced from " +
                 sys::path::filename(isec->file->getName()));
         else
-          target->prepareSymbolRelocation(*s, isec, r);
+          target->prepareSymbolRelocation(s, isec, r);
       }
     }
   }
 }
 
 void Writer::createLoadCommands() {
   in.header->addLoadCommand(
       make<LCDyldInfo>(in.binding, lazyBindingSection, exportSection));