[lld-macho] Support binding dysyms to any section

[int3]

Summary

Previously, we only supported binding dysyms to the GOT. This
diff adds support for binding them to any arbitrary section. C++
programs appear to use this, I believe for vtables and type_info.

This diff also makes our bind opcode encoding a bit smarter -- we now
encode just the differences between bindings, which will make things
more compact.

I was initially concerned about the performance overhead of iterating
over these relocations, but it turns out that the number of such
relocations is small. A quick analysis of my llvm-project build
directory showed that < 1.3% out of ~7M relocations are RELOC_UNSIGNED
bindings to symbols (including both dynamic and static symbols).

[int3]

update

[int3]

more const

[smeenai]

The approach looks good to me. Once we're able to e.g. self-host and link clang, we can get more accurate numbers and confirm that the overhead of storing all these bindings won't be too high.

lld/MachO/SyntheticSections.cpp

105

Super nit: can we use = initialization instead, for consistency with the rest of the code? (At least, I think = initialization is standard in LLD.)

112

"that dyld to write" -> "that tell dyld to write"?

131–132

Nit: an assert seems more conventional

182–183

We'll initialize e.g. addend to 0 here, and for the GOT entries, the addend is always 0, so the lastBinding.addend != addend condition will never be taken and we won't emit an initial BIND_OPCODE_SET_ADDEND_SLEB. Will dyld assume 0 in that case, or should we initialize it explicitly?

Seems like we were never setting the addend at all before, so maybe assuming dyld will default to 0 is okay? Should probably double-check though.

183

Same nit about = initialization.

184

Are we creating a copy of all the entries here?

185

Is the switch from a range-based for loop only so we have i? If so, I think I'd prefer to just keep a separate offset variable and increment it in a range-based for loop.

[int3]

address comments

lld/MachO/SyntheticSections.cpp

105

ah yeah I'm just in the habit of using {} normally. will change

182–183

yes I'm pretty sure this is okay. ld64 doesn't emit SET_ADDEND unless we have a non-zero addend.

184

oops

[smeenai]

LGTM

lld/MachO/SyntheticSections.cpp

158

Thanks for the comment!

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 &, uint8_t type) override;
+  void prepareSymbolRelocation(lld::macho::Symbol &, const InputSection *,
+                               const Reloc &) override;
   uint64_t getSymbolVA(const lld::macho::Symbol &, uint8_t type) const override;
 };
 
 } // namespace
 
 static std::string getErrorLocation(MemoryBufferRef mb, const section_64 &sec,
                                     const relocation_info &rel) {
   return ("invalid relocation at offset " + std::to_string(rel.r_address) +

 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, uint8_t type) {
-  switch (type) {
+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);
     break;
   case X86_64_RELOC_BRANCH: {
     if (auto *dysym = dyn_cast<DylibSymbol>(&sym))
       in.stubs->addEntry(*dysym);
     break;
   }
-  case X86_64_RELOC_UNSIGNED:
+  case X86_64_RELOC_UNSIGNED: {
+    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_SUBTRACTOR:
   case X86_64_RELOC_TLV:
-    fatal("TODO: handle relocation type " + std::to_string(type));
+    fatal("TODO: handle relocation type " + std::to_string(r.type));
     break;
   default:
     llvm_unreachable("unexpected relocation type");
   }
 }
 
 uint64_t X86_64::getSymbolVA(const lld::macho::Symbol &sym,
                              uint8_t type) const {

lld/MachO/SyntheticSections.h

public:
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(Symbol &sym);
 
 private:
   llvm::SetVector<const Symbol *> entries;
 };
 
+struct BindingEntry {
+  const DylibSymbol *dysym;
+  const InputSection *isec;
+  uint64_t offset;
+  int64_t addend;
+  BindingEntry(const DylibSymbol *dysym, const InputSection *isec,
+               uint64_t offset, int64_t addend)
+      : dysym(dysym), isec(isec), offset(offset), addend(addend) {}
+};
+
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection : public SyntheticSection {
 public:
   BindingSection();
   void finalizeContents();
   uint64_t getSize() 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);
+  }
+
+private:
+  std::vector<BindingEntry> bindings;
   SmallVector<char, 128> contents;
 };
 
 // The following sections implement lazy symbol binding -- very similar to the
 // PLT mechanism in ELF.
 //
 // ELF's .plt section is broken up into two sections in Mach-O: StubsSection and
 // StubHelperSection. Calls to functions in dylibs will end up calling into
public:
   void writeTo(uint8_t *buf) const override;
 
 private:
   StringTableSection &stringTableSection;
   std::vector<SymtabEntry> symbols;
 };
 
 struct InStruct {
+  BindingSection *binding = nullptr;
   GotSection *got = nullptr;
   LazyPointerSection *lazyPointers = nullptr;
   StubsSection *stubs = nullptr;
   StubHelperSection *stubHelper = nullptr;
   ImageLoaderCacheSection *imageLoaderCache = nullptr;
 };
 
 extern InStruct in;
 extern std::vector<SyntheticSection *> syntheticSections;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SyntheticSections.cpp

 //===- SyntheticSections.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 "SyntheticSections.h"
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputFiles.h"
 #include "MachOStructs.h"
+#include "MergedOutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/EndianStream.h"
void GotSection::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()
     : SyntheticSection(segment_names::linkEdit, section_names::binding) {}
 
-bool BindingSection::isNeeded() const { return in.got->isNeeded(); }
+bool BindingSection::isNeeded() const {
+  return bindings.size() != 0 || in.got->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,
+                          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) {
+    assert(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) {
+      os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
+                                 dysym.file->ordinal);
+    } else {
+      error("TODO: Support larger dylib symbol ordinals");
+      return;
+    }
+    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'
+     << 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;
+}
 
 // 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() {
-  if (!isNeeded())
-    return;
-
   raw_svector_ostream os{contents};
-  os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
-                             in.got->parent->index);
-  encodeULEB128(in.got->getSegmentOffset(), os);
-  uint32_t entries_to_skip = 0;
+  Binding lastBinding;
+  bool didEncode = false;
+  size_t gotIdx = 0;
   for (const Symbol *sym : in.got->getEntries()) {
     if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
-      if (entries_to_skip != 0) {
-        os << static_cast<uint8_t>(MachO::BIND_OPCODE_ADD_ADDR_ULEB);
-        encodeULEB128(WordSize * entries_to_skip, os);
-        entries_to_skip = 0;
-      }
-
-      // TODO: Implement compact encoding -- we only need to encode the
-      // differences between consecutive symbol entries.
-      if (dysym->file->ordinal <= MachO::BIND_IMMEDIATE_MASK) {
-        os << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
-                                   dysym->file->ordinal);
-      } else {
-        error("TODO: Support larger dylib symbol ordinals");
-        continue;
-      }
-      os << static_cast<uint8_t>(
-                MachO::BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
-         << dysym->getName() << '\0'
-         << static_cast<uint8_t>(MachO::BIND_OPCODE_SET_TYPE_IMM |
-                                 MachO::BIND_TYPE_POINTER)
-         << static_cast<uint8_t>(MachO::BIND_OPCODE_DO_BIND);
-    } else {
-      // We have a defined symbol with a pre-populated address; skip over it.
-      ++entries_to_skip;
+      didEncode = true;
+      encodeBinding(*dysym, in.got, gotIdx * WordSize, 0, lastBinding, os);
     }
+    ++gotIdx;
   }
 
+  // Sorting the relocations by segment and address allows us to encode them
+  // more compactly.
+  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;
+  });
+  for (const BindingEntry &b : bindings) {
+    didEncode = true;
+    encodeBinding(*b.dysym, b.isec->parent, b.isec->outSecOff + b.offset,
+                  b.addend, lastBinding, os);
+  }
+  if (didEncode)
     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") {}

lld/MachO/Target.h

public:
   virtual void writeStubHelperHeader(uint8_t *buf) const = 0;
   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 getSymbolVA() will return the addresses of those
   // entries.
-  virtual void prepareSymbolRelocation(Symbol &, uint8_t type) = 0;
+  virtual void prepareSymbolRelocation(Symbol &, const InputSection *,
+                                       const Reloc &) = 0;
   virtual uint64_t getSymbolVA(const Symbol &, uint8_t type) const = 0;
 
   uint32_t cpuType;
   uint32_t cpuSubtype;
 
   size_t stubSize;
   size_t stubHelperHeaderSize;
   size_t stubHelperEntrySize;

lld/MachO/Writer.cpp

public:
   void writeSections();
 
   void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   MachHeaderSection *headerSection = nullptr;
-  BindingSection *bindingSection = nullptr;
   LazyBindingSection *lazyBindingSection = nullptr;
   ExportSection *exportSection = nullptr;
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {

 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, r.type);
+          target->prepareSymbolRelocation(*s, isec, r);
       }
     }
   }
 }
 
 void Writer::createLoadCommands() {
   headerSection->addLoadCommand(
-      make<LCDyldInfo>(bindingSection, lazyBindingSection, exportSection));
+      make<LCDyldInfo>(in.binding, lazyBindingSection, exportSection));
   headerSection->addLoadCommand(
       make<LCSymtab>(symtabSection, stringTableSection));
   headerSection->addLoadCommand(make<LCDysymtab>());
 
   switch (config->outputType) {
   case MH_EXECUTE:
     headerSection->addLoadCommand(make<LCMain>());
     headerSection->addLoadCommand(make<LCLoadDylinker>());
for (auto *osec : seg->getSections()) {
       }
     }
   }
 }
 
 void Writer::createOutputSections() {
   // First, create hidden sections
   headerSection = make<MachHeaderSection>();
-  bindingSection = make<BindingSection>();
   lazyBindingSection = make<LazyBindingSection>();
   stringTableSection = make<StringTableSection>();
   symtabSection = make<SymtabSection>(*stringTableSection);
   exportSection = make<ExportSection>();
 
   switch (config->outputType) {
   case MH_EXECUTE:
     make<PageZeroSection>();
void Writer::run() {
   // Note that at this point, __LINKEDIT sections are empty, but we need to
   // determine addresses of other segments/sections before generating its
   // contents.
   for (OutputSegment *seg : outputSegments)
     if (seg != linkEditSegment)
       assignAddresses(seg);
 
   // Fill __LINKEDIT contents.
-  bindingSection->finalizeContents();
+  in.binding->finalizeContents();
   lazyBindingSection->finalizeContents();
   exportSection->finalizeContents();
   symtabSection->finalizeContents();
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
   // addresses and offsets.
   assignAddresses(linkEditSegment);
 
   openFile();
   if (errorCount())
     return;
 
   writeSections();
 
   if (auto e = buffer->commit())
     error("failed to write to the output file: " + toString(std::move(e)));
 }
 
 void macho::writeResult() { Writer().run(); }
 
 void macho::createSyntheticSections() {
+  in.binding = make<BindingSection>();
   in.got = make<GotSection>();
   in.lazyPointers = make<LazyPointerSection>();
   in.stubs = make<StubsSection>();
   in.stubHelper = make<StubHelperSection>();
   in.imageLoaderCache = make<ImageLoaderCacheSection>();
 }

lld/test/MachO/dylink.s

 
 # CHECK: movq [[#%u, HELLO_ITS_ME_OFF:]](%rip), %rsi
 # CHECK-NEXT: [[#%x, HELLO_ITS_ME_RIP:]]:
 
 # CHECK: pushq [[#%u, GOODBYE_OFF:]](%rip)
 # CHECK-NEXT: [[#%x, GOODBYE_RIP:]]: popq %rsi
 
 # CHECK-LABEL: Bind table:
-# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, HELLO_RIP + HELLO_OFF]]               pointer 0 libhello   _hello_world
-# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, HELLO_ITS_ME_RIP + HELLO_ITS_ME_OFF]] pointer 0 libhello   _hello_its_me
-# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, GOODBYE_RIP + GOODBYE_OFF]]           pointer 0 libgoodbye _goodbye_world
+# CHECK-DAG: __DATA_CONST __got  0x{{0*}}[[#%x, HELLO_RIP + HELLO_OFF]]               pointer 0   libhello   _hello_world
+# CHECK-DAG: __DATA_CONST __got  0x{{0*}}[[#%x, HELLO_ITS_ME_RIP + HELLO_ITS_ME_OFF]] pointer 0   libhello   _hello_its_me
+# CHECK-DAG: __DATA_CONST __got  0x{{0*}}[[#%x, GOODBYE_RIP + GOODBYE_OFF]]           pointer 0   libgoodbye _goodbye_world
+# CHECK-DAG: __DATA       __data 0x[[#%x, DATA_ADDR:]]                                pointer 0   libhello   _hello_world
+# CHECK-DAG: __DATA       __data 0x{{0*}}[[#%x, DATA_ADDR + 8]]                       pointer 8   libhello   _hello_its_me
+# CHECK-DAG: __DATA       __data 0x{{0*}}[[#%x, DATA_ADDR + 16]]                      pointer -15 libgoodbye _goodbye_world
 
 .section __TEXT,__text
 .globl _main
 
 _main:
   movl $0x2000004, %eax # write() syscall
   mov $1, %rdi # stdout
   movq _hello_world@GOTPCREL(%rip), %rsi
_main:
   movl $0x2000004, %eax # write() syscall
   mov $1, %rdi # stdout
   pushq _goodbye_world@GOTPCREL(%rip)
   popq %rsi
   mov $15, %rdx # length of str
   syscall
   mov $0, %rax
   ret
+
+.data
+.quad _hello_world
+.quad _hello_its_me + 0x8
+.quad _goodbye_world - 0xf