[lld-macho] Emit indirect symbol table

[int3]

Summary

Makes it a little easier to read objdump's disassembly.

[gkm]

Very nice!

lld/MachO/OutputSection.h

66–67

Semantically blank names are beyond our reach in struct section_64, but class OutputSection is ours and we have the freedom to grant meaningful names. In writeTo() the assignments from members of OutputSection to section_64 will make it clear how the meaningful names map onto the meaningless names.

lld/MachO/SyntheticSections.h

396

English style nit.

[int3]

lld/MachO/OutputSection.h

66–67

It's not clear to me that reserved1 is *only* used to point to the indirect symbol table. Its semantics might be section-type-specific. That's why I didn't call it indirectSymtabOffset or something

[int3]

lld/MachO/SyntheticSections.h

396

Aren't they the same thing? Accordingly to Grammarly:

Comprise is a verb that means “to be composed of.”

On second thought though it would be more accurate to say that "the indirect symbol table *is* a concatentation"

[int3]

grammar

[gkm]

lld/MachO/OutputSection.h

66–67

Ah, I see. OutputSection is very superclassy, so the reserved[12] members are just as generic as for section_64. My suggestion would be better suited to a subclass shared by GotSection, TlvPointerSection, and StubsSection.

lld/MachO/SyntheticSections.h

396

While Grammarly is technically correct (as are you), the nit I am picking is a matter of style.

This is the famous passage from Strunk & White's The Elements of Style (do you know it?):

Omit needless words.

Vigorous writing is concise. A sentence should contain no unnecessary words, a paragraph no unnecessary sentences, for the same reason that a drawing should have no unnecessary lines and a machine no unnecessary parts. This requires not that the writer make all his sentences short, or that he avoid all detail and treat his subjects only in outline, but that every word tell.

Many expressions in common use violate this principle:

the question as to whether	whether
there is no doubt but that	no doubt (doubtless)
used for fuel purposes	used for fuel
he is a man who	he
in a hasty manner	hastily
this is a subject which	this subject
His story is a strange one	His story is strange

In especial the expression the fact that should be revised out of every sentence in which it occurs.

owing to the fact that	since (because)
in spite of the fact that	though (although)
call your attention to the fact that	remind you (notify you)
I was unaware of the fact that	I was unaware that (did not know)
the fact that he had not succeeded	his failure
the fact that I had arrived	my arrival

... and your second thought is even better!

lld/MachO/OutputSection.h

public:
   StringRef name;
   OutputSegment *parent = nullptr;
 
   uint32_t index = 0;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   uint32_t align = 1;
   uint32_t flags = 0;
+  uint32_t reserved1 = 0;
+  uint32_t reserved2 = 0;
 
 private:
   Kind sectionKind;
 };
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Symbols.h

public:
 
   // The index of this symbol in the GOT or the TLVPointer section, depending
   // on whether it is a thread-local. A given symbol cannot be referenced by
   // both these sections at once.
   uint32_t gotIndex = UINT32_MAX;
 
   uint32_t stubsIndex = UINT32_MAX;
 
+  uint32_t symtabIndex = UINT32_MAX;
+
 protected:
   Symbol(Kind k, StringRefZ name) : symbolKind(k), name(name) {}
 
   Kind symbolKind;
   StringRefZ name;
 };
 
 class Defined : public Symbol {

lld/MachO/SyntheticSections.h

 constexpr const char pageZero[] = "__pagezero";
 constexpr const char common[] = "__common";
 constexpr const char header[] = "__mach_header";
 constexpr const char binding[] = "__binding";
 constexpr const char weakBinding[] = "__weak_binding";
 constexpr const char lazyBinding[] = "__lazy_binding";
 constexpr const char export_[] = "__export";
 constexpr const char symbolTable[] = "__symbol_table";
+constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
 constexpr const char stringTable[] = "__string_table";
 constexpr const char got[] = "__got";
 constexpr const char threadPtrs[] = "__thread_ptrs";
 constexpr const char unwindInfo[] = "__unwind_info";
 // these are not synthetic, but in service of synthetic __unwind_info
 constexpr const char compactUnwind[] = "__compact_unwind";
 constexpr const char ehFrame[] = "__eh_frame";
 
public:
   uint64_t getRawSize() const override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   StringTableSection &stringTableSection;
   std::vector<SymtabEntry> symbols;
 };
 
+// The indirect symbol table is a list of 32-bit integers that serve as indices
+// into the (actual) symbol table. The indirect symbol table is a
+// concatentation of several sub-arrays of indices, each sub-array belonging to
+// a separate section. The starting offset of each sub-array is stored in the
+// reserved1 header field of the respective section.
+//
+// These sub-arrays provide symbol information for sections that store
+// contiguous sequences of symbol references. These references can be pointers
+// (e.g. those in the GOT and TLVP sections) or assembly sequences (e.g.
+// function stubs).
+class IndirectSymtabSection : public LinkEditSection {
+public:
+  IndirectSymtabSection();
+  void finalizeContents();
+  uint32_t getNumSymbols() const;
+  uint64_t getRawSize() const override {
+    return getNumSymbols() * sizeof(uint32_t);
+  }
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) const override;
+};
+
 struct InStruct {
   MachHeaderSection *header = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;

lld/MachO/SyntheticSections.cpp

void macho::addNonLazyBindingEntries(const Symbol *sym,
   } else {
     // Undefined symbols are filtered out in scanRelocations(); we should never
     // get here
     llvm_unreachable("cannot bind to an undefined symbol");
   }
 }
 
 StubsSection::StubsSection()
-    : SyntheticSection(segment_names::text, "__stubs") {}
+    : SyntheticSection(segment_names::text, "__stubs") {
+  flags = MachO::S_SYMBOL_STUBS;
+  reserved2 = target->stubSize;
+}
 
 uint64_t StubsSection::getSize() const {
   return entries.size() * target->stubSize;
 }
 
 void StubsSection::writeTo(uint8_t *buf) const {
   size_t off = 0;
   for (const Symbol *sym : entries) {
: LinkEditSection(segment_names::linkEdit, section_names::symbolTable),
       stringTableSection(stringTableSection) {}
 
 uint64_t SymtabSection::getRawSize() const {
   return symbols.size() * sizeof(structs::nlist_64);
 }
 
 void SymtabSection::finalizeContents() {
   // TODO support other symbol types
-  for (Symbol *sym : symtab->getSymbols())
-    if (isa<Defined>(sym))
+  for (Symbol *sym : symtab->getSymbols()) {
+    if (isa<Defined>(sym) || sym->isInGot() || sym->isInStubs()) {
+      sym->symtabIndex = symbols.size();
       symbols.push_back({sym, stringTableSection.addString(sym->getName())});
     }
+  }
+}
 
 void SymtabSection::writeTo(uint8_t *buf) const {
   auto *nList = reinterpret_cast<structs::nlist_64 *>(buf);
   for (const SymtabEntry &entry : symbols) {
     nList->n_strx = entry.strx;
     // TODO support other symbol types
     // TODO populate n_desc with more flags
     if (auto *defined = dyn_cast<Defined>(entry.sym)) {
       nList->n_type = MachO::N_EXT | MachO::N_SECT;
       nList->n_sect = defined->isec->parent->index;
       nList->n_desc |= defined->isWeakDef() ? MachO::N_WEAK_DEF : 0;
       // For the N_SECT symbol type, n_value is the address of the symbol
       nList->n_value = defined->value + defined->isec->getVA();
     }
     ++nList;
   }
 }
 
+IndirectSymtabSection::IndirectSymtabSection()
+    : LinkEditSection(segment_names::linkEdit,
+                      section_names::indirectSymbolTable) {}
+
+uint32_t IndirectSymtabSection::getNumSymbols() const {
+  return in.got->getEntries().size() + in.tlvPointers->getEntries().size() +
+         in.stubs->getEntries().size();
+}
+
+bool IndirectSymtabSection::isNeeded() const {
+  return in.got->isNeeded() || in.tlvPointers->isNeeded() ||
+         in.stubs->isNeeded();
+}
+
+void IndirectSymtabSection::finalizeContents() {
+  uint32_t off = 0;
+  in.got->reserved1 = off;
+  off += in.got->getEntries().size();
+  in.tlvPointers->reserved1 = off;
+  off += in.tlvPointers->getEntries().size();
+  // There is a 1:1 correspondence between stubs and LazyPointerSection
+  // entries, so they can share the same sub-array in the table.
+  in.stubs->reserved1 = in.lazyPointers->reserved1 = off;
+}
+
+void IndirectSymtabSection::writeTo(uint8_t *buf) const {
+  uint32_t off = 0;
+  for (const Symbol *sym : in.got->getEntries()) {
+    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    ++off;
+  }
+  for (const Symbol *sym : in.tlvPointers->getEntries()) {
+    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    ++off;
+  }
+  for (const Symbol *sym : in.stubs->getEntries()) {
+    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    ++off;
+  }
+}
+
 StringTableSection::StringTableSection()
     : LinkEditSection(segment_names::linkEdit, section_names::stringTable) {}
 
 uint32_t StringTableSection::addString(StringRef str) {
   uint32_t strx = size;
   strings.push_back(str);
   size += str.size() + 1; // account for null terminator
   return strx;

lld/MachO/Writer.cpp

public:
   void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   MachHeaderSection *header = nullptr;
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
+  IndirectSymtabSection *indirectSymtabSection = nullptr;
   UnwindInfoSection *unwindInfoSection = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
   LCDyldInfo(BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
public:
   BindingSection *bindingSection;
   WeakBindingSection *weakBindingSection;
   LazyBindingSection *lazyBindingSection;
   ExportSection *exportSection;
 };
 
 class LCDysymtab : public LoadCommand {
 public:
+  LCDysymtab(IndirectSymtabSection *indirectSymtabSection)
+      : indirectSymtabSection(indirectSymtabSection) {}
+
   uint32_t getSize() const override { return sizeof(dysymtab_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dysymtab_command *>(buf);
     c->cmd = LC_DYSYMTAB;
     c->cmdsize = getSize();
+    c->indirectsymoff = indirectSymtabSection->fileOff;
+    c->nindirectsyms = indirectSymtabSection->getNumSymbols();
   }
+
+  IndirectSymtabSection *indirectSymtabSection = nullptr;
 };
 
 class LCSegment : public LoadCommand {
 public:
   LCSegment(StringRef name, OutputSegment *seg) : name(name), seg(seg) {}
 
   uint32_t getSize() const override {
     return sizeof(segment_command_64) +
for (OutputSection *osec : seg->getSections()) {
       memcpy(sectHdr->sectname, osec->name.data(), osec->name.size());
       memcpy(sectHdr->segname, name.data(), name.size());
 
       sectHdr->addr = osec->addr;
       sectHdr->offset = osec->fileOff;
       sectHdr->align = Log2_32(osec->align);
       sectHdr->flags = osec->flags;
       sectHdr->size = osec->getSize();
+      sectHdr->reserved1 = osec->reserved1;
+      sectHdr->reserved2 = osec->reserved2;
     }
   }
 
 private:
   StringRef name;
   OutputSegment *seg;
 };
 
for (InputSection *isec : inputSections) {
     }
   }
 }
 
 void Writer::createLoadCommands() {
   in.header->addLoadCommand(
       make<LCDyldInfo>(in.binding, in.weakBinding, in.lazyBinding, in.exports));
   in.header->addLoadCommand(make<LCSymtab>(symtabSection, stringTableSection));
-  in.header->addLoadCommand(make<LCDysymtab>());
+  in.header->addLoadCommand(make<LCDysymtab>(indirectSymtabSection));
   for (StringRef path : config->runtimePaths)
     in.header->addLoadCommand(make<LCRPath>(path));
 
   switch (config->outputType) {
   case MH_EXECUTE:
     in.header->addLoadCommand(make<LCMain>());
     in.header->addLoadCommand(make<LCLoadDylinker>());
     break;
static int sectionOrder(OutputSection *osec) {
   if (segname == segment_names::text) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::header, -1)
         .Case(section_names::unwindInfo, std::numeric_limits<int>::max() - 1)
         .Case(section_names::ehFrame, std::numeric_limits<int>::max())
         .Default(0);
   } else if (segname == segment_names::linkEdit) {
     return StringSwitch<int>(osec->name)
-        .Case(section_names::binding, -6)
-        .Case(section_names::weakBinding, -5)
-        .Case(section_names::lazyBinding, -4)
-        .Case(section_names::export_, -3)
-        .Case(section_names::symbolTable, -2)
+        .Case(section_names::binding, -7)
+        .Case(section_names::weakBinding, -6)
+        .Case(section_names::lazyBinding, -5)
+        .Case(section_names::export_, -4)
+        .Case(section_names::symbolTable, -3)
+        .Case(section_names::indirectSymbolTable, -2)
         .Case(section_names::stringTable, -1)
         .Default(0);
   }
   // ZeroFill sections must always be the at the end of their segments,
   // otherwise subsequent sections may get overwritten with zeroes at runtime.
   if (isZeroFill(osec->flags))
     return std::numeric_limits<int>::max();
   return 0;
static void sortSegmentsAndSections() {
   }
 }
 
 void Writer::createOutputSections() {
   // First, create hidden sections
   stringTableSection = make<StringTableSection>();
   unwindInfoSection = make<UnwindInfoSection>(); // TODO(gkm): only when no -r
   symtabSection = make<SymtabSection>(*stringTableSection);
+  indirectSymtabSection = make<IndirectSymtabSection>();
 
   switch (config->outputType) {
   case MH_EXECUTE:
     make<PageZeroSection>();
     break;
   case MH_DYLIB:
     break;
   default:
if (seg != linkEditSegment)
       assignAddresses(seg);
 
   // Fill __LINKEDIT contents.
   in.binding->finalizeContents();
   in.weakBinding->finalizeContents();
   in.lazyBinding->finalizeContents();
   in.exports->finalizeContents();
   symtabSection->finalizeContents();
+  indirectSymtabSection->finalizeContents();
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
   // addresses and offsets.
   assignAddresses(linkEditSegment);
 
   openFile();
   if (errorCount())
     return;

lld/test/MachO/indirect-symtab.s

+# REQUIRES: x86
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/libfoo.s -o %t/libfoo.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: lld -flavor darwinnew -dylib %t/libfoo.o -o %t/libfoo.dylib -syslibroot %S/Inputs/MacOSX.sdk -lSystem
+# RUN: lld -flavor darwinnew %t/test.o %t/libfoo.dylib -o %t/test -syslibroot %S/Inputs/MacOSX.sdk -lSystem
+# RUN: llvm-objdump --macho -d --no-show-raw-insn --indirect-symbols %t/test | FileCheck %s
+
+# CHECK:      (__TEXT,__text) section
+# CHECK-NEXT: _main:
+# CHECK-NEXT: movq  {{.*}}(%rip), %rax ## literal pool symbol address: _foo
+# CHECK-NEXT: movq  {{.*}}(%rip), %rax ## literal pool symbol address: _bar
+# CHECK-NEXT: movq  {{.*}}(%rip), %rax ## literal pool symbol address: _foo_tlv
+# CHECK-NEXT: movq  {{.*}}(%rip), %rax ## literal pool symbol address: _bar_tlv
+# CHECK-NEXT: callq {{.*}} ## symbol stub for: _foo_fn
+# CHECK-NEXT: callq {{.*}} ## symbol stub for: _bar_fn
+# CHECK-NEXT: retq
+
+# CHECK:      Indirect symbols for (__TEXT,__stubs) 2 entries
+# CHECK-NEXT: address            index name
+# CHECK-NEXT: _bar_fn
+# CHECK-NEXT: _foo_fn
+# CHECK-NEXT: Indirect symbols for (__DATA,__thread_ptrs) 2 entries
+# CHECK-NEXT: address            index name
+# CHECK-NEXT: _bar_tlv
+# CHECK-NEXT: _foo_tlv
+# CHECK-NEXT: Indirect symbols for (__DATA,__la_symbol_ptr) 2 entries
+# CHECK-NEXT: address            index name
+# CHECK-NEXT: _bar_fn
+# CHECK-NEXT: _foo_fn
+# CHECK-NEXT: Indirect symbols for (__DATA_CONST,__got) 3 entries
+# CHECK-NEXT: address            index name
+# CHECK-NEXT: _bar
+# CHECK-NEXT: _foo
+# CHECK-NEXT: _stub_binder
+
+#--- libfoo.s
+
+.globl _foo, _foo_fn, _bar, _bar_fn
+_foo:
+_foo_fn:
+_bar:
+_bar_fn:
+
+.section  __DATA,__thread_vars,thread_local_variables
+.globl _foo_tlv, _bar_tlv
+_foo_tlv:
+_bar_tlv:
+
+#--- test.s
+
+.globl _main
+_main:
+  movq _foo@GOTPCREL(%rip), %rax
+  movq _bar@GOTPCREL(%rip), %rax
+  mov _foo_tlv@TLVP(%rip), %rax
+  mov _bar_tlv@TLVP(%rip), %rax
+  callq _foo_fn
+  callq _bar_fn
+  ret