[lld-macho] Emit local symbols in symtab; record metadata in LC_DYSYMTAB

[int3]

Summary

Symbols of the same type must be laid out contiguously: following ld64's
lead, we choose to emit all local symbols first, then external symbols,
and finally undefined symbols. For each symbol type, the LC_DYSYMTAB
load command will record the range (start index and total number) of
those symbols in the symbol table.

This work was motivated by the fact that LLDB won't search for debug
info if LC_DYSYMTAB says there are no local symbols (since STABS symbols
are all local symbols). With this change, LLDB is now able to display
the source lines at a given breakpoint when debugging our binaries.

Some tests had to be updated due to local symbol names now appearing in
llvm-objdump's output.

[int3]

test dysymtab

[int3]

don't match unnecessarily on exact addresses in test

[compnerd]

Given that Darwin has fully moved to DWARF at this point, why STABS?

[int3]

I'm not familiar with Darwin's history with STABS, but these symbols are still necessary for dsymutil / lldb to locate the DWARF debug info.

[smeenai]

LGTM

[clayborg]

LGTM as long as local symbols always have names (see inlined comment).

lld/MachO/SyntheticSections.cpp

643

Do all symbols have names? If not we should check that the symbol has a name and not add it if it doesn't?

[clayborg]

In D89285#2332489, @compnerd wrote:

Given that Darwin has fully moved to DWARF at this point, why STABS?

STABS are deprecated for normal actually containing debug info, but they are used for the DWARF in .o file format. This allows the linker to not have to link DWARF from all of the .o files, it just needs to emit a debug map, using STAB entries in the symbol table. Since the entries are debug entries, "strip" can strip the debug map out prior to shipping.

[int3]

lld/MachO/SyntheticSections.cpp

643

To my knowledge, yes they do... are you aware of a way to generate unnamed local symbols?

[clayborg]

lld/MachO/SyntheticSections.cpp

643

No I am not.

lld/MachO/SyntheticSections.h

struct StabsEntry {
   uint32_t strx = 0;
   uint8_t sect = 0;
   uint16_t desc = 0;
   uint64_t value = 0;
 
   explicit StabsEntry(uint8_t type) : type(type) {}
 };
 
+// Symbols of the same type must be laid out contiguously: we choose to emit
+// all local symbols first, then external symbols, and finally undefined
+// symbols. For each symbol type, the LC_DYSYMTAB load command will record the
+// range (start index and total number) of those symbols in the symbol table.
 class SymtabSection : public LinkEditSection {
 public:
   SymtabSection(StringTableSection &);
   void finalizeContents();
-  size_t getNumSymbols() const { return stabs.size() + symbols.size(); }
+  uint32_t getNumSymbols() const;
+  uint32_t getNumLocalSymbols() const {
+    return stabs.size() + localSymbols.size();
+  }
+  uint32_t getNumExternalSymbols() const { return externalSymbols.size(); }
+  uint32_t getNumUndefinedSymbols() const { return undefinedSymbols.size(); }
   uint64_t getRawSize() const override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   void emitBeginSourceStab(llvm::DWARFUnit *compileUnit);
   void emitEndSourceStab();
   void emitObjectFileStab(InputFile *);
   void emitFunStabs(Defined *);
 
   StringTableSection &stringTableSection;
+  // STABS symbols are always local symbols, but we represent them with special
+  // entries because they may use fields like n_sect and n_desc differently.
   std::vector<StabsEntry> stabs;
-  std::vector<SymtabEntry> symbols;
+  std::vector<SymtabEntry> localSymbols;
+  std::vector<SymtabEntry> externalSymbols;
+  std::vector<SymtabEntry> undefinedSymbols;
 };
 
 // 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.
 //

lld/MachO/SyntheticSections.cpp

 #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/ADT/STLExtras.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/Path.h"
 
 using namespace llvm;
 using namespace llvm::support;
 using namespace llvm::support::endian;
void SymtabSection::emitFunStabs(Defined *defined) {
     // FIXME this should be the size of the symbol. Using the section size in
     // lieu is only correct if .subsections_via_symbols is set.
     stab.value = defined->isec->getSize();
     stabs.emplace_back(std::move(stab));
   }
 }
 
 void SymtabSection::finalizeContents() {
-  InputFile *lastFile = nullptr;
+  // Local symbols aren't in the SymbolTable, so we walk the list of object
+  // files to gather them.
+  for (InputFile *file : inputFiles) {
+    if (auto *objFile = dyn_cast<ObjFile>(file)) {
+      for (Symbol *sym : objFile->symbols) {
+        // TODO: when we implement -dead_strip, we should filter out symbols
+        // that belong to dead sections.
+        if (auto *defined = dyn_cast<Defined>(sym)) {
+          if (!defined->isExternal()) {
+            uint32_t strx = stringTableSection.addString(sym->getName());
+            localSymbols.push_back({sym, strx});
+          }
+        }
+      }
+    }
+  }
+
   for (Symbol *sym : symtab->getSymbols()) {
-    // TODO support other symbol types
-    if (isa<Defined>(sym) || sym->isInGot() || sym->isInStubs()) {
-      sym->symtabIndex = symbols.size();
-      symbols.push_back({sym, stringTableSection.addString(sym->getName())});
-    }
+    uint32_t strx = stringTableSection.addString(sym->getName());
+    if (auto *defined = dyn_cast<Defined>(sym)) {
+      assert(defined->isExternal());
+      externalSymbols.push_back({sym, strx});
+    } else if (sym->isInGot() || sym->isInStubs()) {
+      undefinedSymbols.push_back({sym, strx});
+    }
 
+  InputFile *lastFile = nullptr;
+  for (Symbol *sym : symtab->getSymbols()) {
     // Emit STABS symbols so that dsymutil and/or the debugger can map address
     // regions in the final binary to the source and object files from which
     // they originated.
     if (auto *defined = dyn_cast<Defined>(sym)) {
       if (defined->isAbsolute())
         continue;
 
       InputSection *isec = defined->isec;
if (auto *defined = dyn_cast<Defined>(sym)) {
         emitFunStabs(defined);
       }
       // TODO emit stabs for non-function symbols too
     }
   }
 
   if (!stabs.empty())
     emitEndSourceStab();
+
+  uint32_t symtabIndex = stabs.size();
+  for (const SymtabEntry &entry :
+       concat<SymtabEntry>(localSymbols, externalSymbols, undefinedSymbols)) {
+    entry.sym->symtabIndex = symtabIndex++;
+  }
+}
+
+uint32_t SymtabSection::getNumSymbols() const {
+  return stabs.size() + localSymbols.size() + externalSymbols.size() +
+         undefinedSymbols.size();
 }
 
 void SymtabSection::writeTo(uint8_t *buf) const {
   auto *nList = reinterpret_cast<structs::nlist_64 *>(buf);
-  for (const SymtabEntry &entry : symbols) {
+  // Emit the stabs entries before the "real" symbols. We cannot emit them
+  // after as that would render Symbol::symtabIndex inaccurate.
+  for (const StabsEntry &entry : stabs) {
+    nList->n_strx = entry.strx;
+    nList->n_type = entry.type;
+    nList->n_sect = entry.sect;
+    nList->n_desc = entry.desc;
+    nList->n_value = entry.value;
+    ++nList;
+  }
+
+  for (const SymtabEntry &entry : concat<const SymtabEntry>(
+           localSymbols, externalSymbols, undefinedSymbols)) {
     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)) {
       if (defined->isAbsolute()) {
         nList->n_type = MachO::N_EXT | MachO::N_ABS;
         nList->n_sect = MachO::NO_SECT;
         nList->n_value = defined->value;
       } else {
-        nList->n_type = MachO::N_EXT | MachO::N_SECT;
+        nList->n_type =
+            (defined->isExternal() ? MachO::N_EXT : 0) | MachO::N_SECT;
         nList->n_sect = defined->isec->parent->index;
         // For the N_SECT symbol type, n_value is the address of the symbol
         nList->n_value = defined->getVA();
       }
       nList->n_desc |= defined->isWeakDef() ? MachO::N_WEAK_DEF : 0;
     }
     ++nList;
   }
-
-  // Emit the stabs entries after the "real" symbols. We cannot emit them
-  // before as that would render Symbol::symtabIndex inaccurate.
-  for (const StabsEntry &entry : stabs) {
-    nList->n_strx = entry.strx;
-    nList->n_type = entry.type;
-    nList->n_sect = entry.sect;
-    nList->n_desc = entry.desc;
-    nList->n_value = entry.value;
-    ++nList;
-  }
 }
 
 IndirectSymtabSection::IndirectSymtabSection()
     : LinkEditSection(segment_names::linkEdit,
                       section_names::indirectSymbolTable) {}
 
 uint32_t IndirectSymtabSection::getNumSymbols() const {
   return in.got->getEntries().size() + in.tlvPointers->getEntries().size() +

lld/MachO/Writer.cpp

public:
   BindingSection *bindingSection;
   WeakBindingSection *weakBindingSection;
   LazyBindingSection *lazyBindingSection;
   ExportSection *exportSection;
 };
 
 class LCDysymtab : public LoadCommand {
 public:
-  LCDysymtab(IndirectSymtabSection *indirectSymtabSection)
-      : indirectSymtabSection(indirectSymtabSection) {}
+  LCDysymtab(SymtabSection *symtabSection,
+             IndirectSymtabSection *indirectSymtabSection)
+      : symtabSection(symtabSection),
+        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->ilocalsym = 0;
+    c->iextdefsym = c->nlocalsym = symtabSection->getNumLocalSymbols();
+    c->nextdefsym = symtabSection->getNumExternalSymbols();
+    c->iundefsym = c->iextdefsym + c->nextdefsym;
+    c->nundefsym = symtabSection->getNumUndefinedSymbols();
+
     c->indirectsymoff = indirectSymtabSection->fileOff;
     c->nindirectsyms = indirectSymtabSection->getNumSymbols();
   }
 
-  IndirectSymtabSection *indirectSymtabSection = nullptr;
+  SymtabSection *symtabSection;
+  IndirectSymtabSection *indirectSymtabSection;
 };
 
 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 (InputSection *isec : inputSections) {
     }
   }
 }
 
 void Writer::createLoadCommands() {
   in.header->addLoadCommand(make<LCDyldInfo>(
       in.rebase, in.binding, in.weakBinding, in.lazyBinding, in.exports));
   in.header->addLoadCommand(make<LCSymtab>(symtabSection, stringTableSection));
-  in.header->addLoadCommand(make<LCDysymtab>(indirectSymtabSection));
+  in.header->addLoadCommand(
+      make<LCDysymtab>(symtabSection, 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;

lld/test/MachO/stabs.s

 # REQUIRES: x86
 # RUN: split-file %s %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/foo.s -o %t/foo.o
 
 # RUN: %lld -lSystem %t/test.o %t/foo.o -o %t/test
 # RUN: llvm-nm -pa %t/test | FileCheck %s -DDIR=%t
 
 ## Check that we emit absolute paths to the object files in our OSO entries
 ## even if our inputs are relative paths.
 # RUN: cd %t && %lld -lSystem test.o foo.o -o test
 # RUN: llvm-nm -pa %t/test | FileCheck %s -DDIR=%t
 
-# CHECK-DAG:  [[#%x, MAIN:]]   T _main
-# CHECK-DAG:  [[#%x, FOO: ]]   T _foo
 # CHECK:      0000000000000000 - 00 0000    SO /tmp/test.cpp
 # CHECK-NEXT: 0000000000000000 - 03 0001   OSO [[DIR]]/test.o
-# CHECK-NEXT: [[#MAIN]]        - 01 0000   FUN _main
+# CHECK-NEXT: [[#%x, MAIN:]]   - 01 0000   FUN _main
 # CHECK-NEXT: 0000000000000001 - 00 0000   FUN
 # CHECK-NEXT: 0000000000000000 - 01 0000    SO
 # CHECK-NEXT: 0000000000000000 - 00 0000    SO /foo.cpp
 # CHECK-NEXT: 0000000000000000 - 03 0001   OSO [[DIR]]/foo.o
-# CHECK-NEXT: [[#FOO]]         - 01 0000   FUN _foo
+# CHECK-NEXT: [[#%x, FOO: ]]   - 01 0000   FUN _foo
 # CHECK-NEXT: 0000000000000001 - 00 0000   FUN
 # CHECK-NEXT: 0000000000000000 - 01 0000    SO
+# CHECK-NEXT: [[#MAIN]]        T _main
+# CHECK-NEXT: [[#FOO]]         T _foo
 
 #--- test.s
 .text
 .globl  _main
 _main:
 Lfunc_begin0:
   retq
 Lfunc_end0:

lld/test/MachO/subsections-symbol-relocs.s

 # RUN: echo "_main" >> %t/order-file-2
 # RUN: echo "_qux" >> %t/order-file-2
 
 # RUN: %lld -o %t/test-1 %t/test.o -order_file %t/order-file-1
 # RUN: llvm-objdump -d --no-show-raw-insn %t/test-1 | FileCheck %s
 # RUN: %lld -o %t/test-2 %t/test.o -order_file %t/order-file-2
 # RUN: llvm-objdump -d --no-show-raw-insn %t/test-2 | FileCheck %s
 # CHECK-LABEL: Disassembly of section __TEXT,__text:
-# CHECK:       <_bar>:
+# CHECK:       <_ba{{r|z}}>:
 # CHECK-NEXT:    callq {{.*}} <_foo>
 # CHECK-EMPTY:
 # CHECK-NEXT:  <_qux>:
 # CHECK-NEXT:    retq
 # CHECK:       <_foo>:
 # CHECK-NEXT:    retq
 # CHECK:       <_main>:
-# CHECK-NEXT:    callq {{.*}} <_bar>
+# CHECK-NEXT:    callq {{.*}} <_ba{{r|z}}>
 # CHECK-NEXT:    movq $0, %rax
 # CHECK-NEXT:    retq
 
 .text
 .globl _main, _foo, _bar, _qux
 .alt_entry _qux
 
 _foo:

lld/test/MachO/symtab.s

 # REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
-# RUN: %lld -o %t %t.o
-# RUN: llvm-readobj -symbols %t | FileCheck %s
+# RUN: rm -rf %t && split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/libfoo.s -o %t/libfoo.o
+# RUN: %lld -dylib %t/libfoo.o -o %t/libfoo.dylib
+# RUN: %lld -lSystem %t/test.o %t/libfoo.dylib -o %t/test
+# RUN: llvm-readobj -symbols %t/test | FileCheck %s
 
 # CHECK:      Symbols [
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: _main
+# CHECK-NEXT:     Name: _local (1)
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __data (0x4)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value: 0x100001000
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _main (8)
 # CHECK-NEXT:     Extern
 # CHECK-NEXT:     Type: Section (0xE)
 # CHECK-NEXT:     Section: __text (0x1)
-# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value: 0x100000530
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _external (54)
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __data (0x4)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
 # CHECK-NEXT:     Flags [ (0x0)
 # CHECK-NEXT:     ]
-# CHECK-NEXT:     Value:
+# CHECK-NEXT:     Value: 0x100001000
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: bar
+# CHECK-NEXT:     Name: _external_weak (64)
 # CHECK-NEXT:     Extern
 # CHECK-NEXT:     Type: Section (0xE)
 # CHECK-NEXT:     Section: __text (0x1)
-# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
 # CHECK-NEXT:     Flags [ (0x80)
 # CHECK-NEXT:       WeakDef (0x80)
 # CHECK-NEXT:     ]
-# CHECK-NEXT:     Value:
+# CHECK-NEXT:     Value: 0x100000530
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: foo
+# CHECK-NEXT:     Name: __dyld_private (102)
 # CHECK-NEXT:     Extern
 # CHECK-NEXT:     Type: Section (0xE)
-# CHECK-NEXT:     Section: __data
-# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Section: __data (0x4)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
 # CHECK-NEXT:     Flags [ (0x0)
 # CHECK-NEXT:     ]
-# CHECK-NEXT:     Value:
+# CHECK-NEXT:     Value: 0x100001000
 # CHECK-NEXT:   }
-# CHECK-NEXT: ]
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: dyld_stub_binder (14)
+# CHECK-NEXT:     Type: Undef (0x0)
+# CHECK-NEXT:     Section:  (0x0)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value: 0x0
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _dynamic (79)
+# CHECK-NEXT:     Type: Undef (0x0)
+# CHECK-NEXT:     Section:  (0x0)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value: 0x0
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+#--- libfoo.s
+.globl _dynamic
+_dynamic:
+
+#--- test.s
+.globl _main, _external, _external_weak
 
 .data
-.global foo
-foo:
-  .asciz "Hello world!\n"
+_external:
+  .space 0
+_local:
+  .space 0
 
 .text
-.weak_definition bar
-.global bar
-.global _main
+.weak_definition _external_weak
+_external_weak:
+  .space 0
 
 _main:
+  callq _dynamic
   mov $0, %rax
   ret
-
-bar:
-  mov $2, %rax
-  ret

lld/test/MachO/tlv.s

 # CHECK-EMPTY:
 # CHECK-NEXT:  <_main>:
 # CHECK-NEXT:  leaq    {{.*}}(%rip), %rax  # {{.*}} <_foo>
 # CHECK-NEXT:  leaq    {{.*}}(%rip), %rax  # {{.*}} <_bar>
 # CHECK-NEXT:  retq
 # CHECK-EMPTY:
 # CHECK-NEXT:  Disassembly of section __DATA,__thread_data:
 # CHECK-EMPTY:
-# CHECK-NEXT:  <__thread_data>:
-# CHECK-NEXT:  ef
-# CHECK-NEXT:  be ad de be ba
-# CHECK-NEXT:  fe ca
+# CHECK-NEXT:  <_foo$tlv$init>:
+# CHECK-NEXT:  00 00
+# CHECK-NEXT:  00 00
+# CHECK-EMPTY:
+# CHECK-NEXT:  <_bar$tlv$init>:
+# CHECK-NEXT:  00 00
+# CHECK-NEXT:  00 00
 # CHECK-EMPTY:
 # CHECK-NEXT:  Disassembly of section __DATA,__thread_vars:
 # CHECK-EMPTY:
 # CHECK-NEXT: <_foo>:
 # CHECK-NEXT:          ...
 # CHECK-EMPTY:
 # CHECK-NEXT:  <_bar>:
 # CHECK-NEXT:          ...
 # CHECK-NEXT:  04 00
 # CHECK-NEXT:  00 00
 # CHECK-NEXT:  00 00
 # CHECK-NEXT:  00 00
 
 .globl _main
 _main:
   mov _foo@TLVP(%rip), %rax
   mov _bar@TLVP(%rip), %rax
   ret
 
 .section  __DATA,__thread_data,thread_local_regular
 _foo$tlv$init:
-  .long 0xdeadbeef
+  .space 4
 _bar$tlv$init:
-  .long 0xcafebabe
+  .space 4
 
 .section  __DATA,__thread_vars,thread_local_variables
 .globl  _foo, _bar
 _foo:
   .quad __tlv_bootstrap
   .quad 0
   .quad _foo$tlv$init
 _bar:
   .quad __tlv_bootstrap
   .quad 0
   .quad _bar$tlv$init