[lld-macho][reland] Add basic symbol table output

[int3]

Summary

This diff implements basic support for writing a symbol table.

Attributes are loosely supported for extern symbols and not at all for
other types.

Initial version by Kellie Medlin <[e-mail]>

Original diff got reverted due to UBSAN erroring over unaligned writes.
That has been fixed in the current diff with the following changes:

diff --git a/lld/MachO/SyntheticSections.cpp b/lld/MachO/SyntheticSections.cpp
--- a/lld/MachO/SyntheticSections.cpp
+++ b/lld/MachO/SyntheticSections.cpp
@@ -133,6 +133,9 @@ SymtabSection::SymtabSection(StringTableSection &stringTableSection)
     : stringTableSection(stringTableSection) {
   segname = segment_names::linkEdit;
   name = section_names::symbolTable;
+  // TODO: When we introduce the SyntheticSections superclass, we should make
+  // all synthetic sections aligned to WordSize by default.
+  align = WordSize;
 }

 size_t SymtabSection::getSize() const {
diff --git a/lld/MachO/Writer.cpp b/lld/MachO/Writer.cpp
--- a/lld/MachO/Writer.cpp
+++ b/lld/MachO/Writer.cpp
@@ -371,6 +371,7 @@ void Writer::assignAddresses(OutputSegment *seg) {
     ArrayRef<InputSection *> sections = p.second;
     for (InputSection *isec : sections) {
       addr = alignTo(addr, isec->align);
+      // We must align the file offsets too to avoid misaligned writes of
+      // structs.
+      fileOff = alignTo(fileOff, isec->align);
       isec->addr = addr;
       addr += isec->getSize();
       fileOff += isec->getFileSize();
@@ -396,6 +397,7 @@ void Writer::writeSections() {
     uint64_t fileOff = seg->fileOff;
     for (auto &sect : seg->getSections()) {
       for (InputSection *isec : sect.second) {
+        fileOff = alignTo(fileOff, isec->align);
         isec->writeTo(buf + fileOff);
         fileOff += isec->getFileSize();
       }

I don't think it's easy to write a test for alignment (that doesn't
involve brittly hard-coding file offsets), so there isn't one... but
UBSAN builds pass now.

[int3]

add a comment

[smeenai]

(this was a recommit, so I just landed it without an explicit accept)

lld/MachO/SyntheticSections.h

 namespace lld {
 namespace macho {
 
 namespace section_names {
 
 constexpr const char *pageZero = "__pagezero";
 constexpr const char *header = "__mach_header";
 constexpr const char *binding = "__binding";
+constexpr const char *symbolTable = "__symbol_table";
+constexpr const char *stringTable = "__string_table";
 
 } // namespace section_names
 
 class DylibSymbol;
 class LoadCommand;
 
 // The header of the Mach-O file, which must have a file offset of zero.
 class MachHeaderSection : public InputSection {
public:
   // section headers.
   bool isHidden() const override { return true; }
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) override;
 
   SmallVector<char, 128> contents;
 };
 
+// Stores the strings referenced by the symbol table.
+class StringTableSection : public InputSection {
+public:
+  StringTableSection();
+  // Returns the start offset of the added string.
+  uint32_t addString(StringRef);
+  size_t getSize() const override { return size; }
+  // Like other sections in __LINKEDIT, the string table section is special: its
+  // offsets are recorded in the LC_SYMTAB load command, instead of in section
+  // headers.
+  bool isHidden() const override { return true; }
+  void writeTo(uint8_t *buf) override;
+
+private:
+  // An n_strx value of 0 always indicates the empty string, so we must locate
+  // our non-empty string values at positive offsets in the string table.
+  // Therefore we insert a dummy value at position zero.
+  std::vector<StringRef> strings{"\0"};
+  size_t size = 1;
+};
+
+struct SymtabEntry {
+  Symbol *sym;
+  size_t strx;
+};
+
+class SymtabSection : public InputSection {
+public:
+  SymtabSection(StringTableSection &);
+  void finalizeContents();
+  size_t getNumSymbols() const { return symbols.size(); }
+  size_t getSize() const override;
+  // Like other sections in __LINKEDIT, the symtab section is special: its
+  // offsets are recorded in the LC_SYMTAB load command, instead of in section
+  // headers.
+  bool isHidden() const override { return true; }
+  void writeTo(uint8_t *buf) override;
+
+private:
+  StringTableSection &stringTableSection;
+  std::vector<SymtabEntry> symbols;
+};
+
 struct InStruct {
   GotSection *got = nullptr;
 };
 
 extern InStruct in;
 
 } // 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 "InputFiles.h"
 #include "OutputSegment.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/LEB128.h"
 
 using namespace llvm;
void BindingSection::finalizeContents() {
 
   os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) {
   memcpy(buf, contents.data(), contents.size());
 }
 
+SymtabSection::SymtabSection(StringTableSection &stringTableSection)
+    : stringTableSection(stringTableSection) {
+  segname = segment_names::linkEdit;
+  name = section_names::symbolTable;
+  // TODO: When we introduce the SyntheticSections superclass, we should make
+  // all synthetic sections aligned to WordSize by default.
+  align = WordSize;
+}
+
+size_t SymtabSection::getSize() const {
+  return symbols.size() * sizeof(nlist_64);
+}
+
+void SymtabSection::finalizeContents() {
+  // TODO: We should filter out some symbols.
+  for (Symbol *sym : symtab->getSymbols())
+    symbols.push_back({sym, stringTableSection.addString(sym->getName())});
+}
+
+void SymtabSection::writeTo(uint8_t *buf) {
+  auto *nList = reinterpret_cast<nlist_64 *>(buf);
+  for (const SymtabEntry &entry : symbols) {
+    // TODO support other symbol types
+    // TODO populate n_desc
+    if (auto defined = dyn_cast<Defined>(entry.sym)) {
+      nList->n_strx = entry.strx;
+      nList->n_type = N_EXT | N_SECT;
+      nList->n_sect = defined->isec->sectionIndex;
+      // For the N_SECT symbol type, n_value is the address of the symbol
+      nList->n_value = defined->value + defined->isec->addr;
+    }
+
+    ++nList;
+  }
+}
+
+StringTableSection::StringTableSection() {
+  segname = segment_names::linkEdit;
+  name = 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;
+}
+
+void StringTableSection::writeTo(uint8_t *buf) {
+  uint32_t off = 0;
+  for (StringRef str : strings) {
+    memcpy(buf + off, str.data(), str.size());
+    off += str.size() + 1; // account for null terminator
+  }
+}
+
 InStruct in;
 
 } // namespace macho
 } // namespace lld

lld/MachO/Writer.cpp

public:
 
   void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   MachHeaderSection *headerSection = nullptr;
   BindingSection *bindingSection = nullptr;
+  SymtabSection *symtabSection = nullptr;
+  StringTableSection *stringTableSection = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
   LCDyldInfo(BindingSection *bindingSection) : bindingSection(bindingSection) {}
 
   uint32_t getSize() const override { return sizeof(dyld_info_command); }
void writeTo(uint8_t *buf) const override {
     c->cmdsize = getSize();
     c->entryoff = config->entry->getVA();
     c->stacksize = 0;
   }
 };
 
 class LCSymtab : public LoadCommand {
 public:
+  LCSymtab(SymtabSection *symtabSection, StringTableSection *stringTableSection)
+      : symtabSection(symtabSection), stringTableSection(stringTableSection) {}
+
   uint32_t getSize() const override { return sizeof(symtab_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<symtab_command *>(buf);
     c->cmd = LC_SYMTAB;
     c->cmdsize = getSize();
+    c->symoff = symtabSection->getFileOffset();
+    c->nsyms = symtabSection->getNumSymbols();
+    c->stroff = stringTableSection->getFileOffset();
+    c->strsize = stringTableSection->getFileSize();
   }
+
+  SymtabSection *symtabSection = nullptr;
+  StringTableSection *stringTableSection = nullptr;
 };
 
 class LCLoadDylib : public LoadCommand {
 public:
   LCLoadDylib(StringRef path) : path(path) {}
 
   uint32_t getSize() const override {
     return alignTo(sizeof(dylib_command) + path.size() + 1, 8);
SectionComparator() {
     // sections that are not mentioned will end up at the end of the section
     // list for their given segment.
     std::vector<std::pair<StringRef, std::vector<StringRef>>> ordering{
         {segment_names::pageZero, {}},
         {segment_names::text, {section_names::header}},
         {defaultPosition, {}},
         // Make sure __LINKEDIT is the last segment (i.e. all its hidden
         // sections must be ordered after other sections).
-        {segment_names::linkEdit, {section_names::binding}},
+        {segment_names::linkEdit,
+         {
+             section_names::binding,
+             section_names::symbolTable,
+             section_names::stringTable,
+         }},
     };
 
     for (uint32_t i = 0, n = ordering.size(); i < n; ++i) {
       auto &p = ordering[i];
       StringRef segname = p.first;
       const std::vector<StringRef> &sectOrdering = p.second;
       OrderInfo &info = orderMap[segname];
       info.segmentOrder = i;
for (Reloc &r : sect->relocs)
       if (auto *s = r.target.dyn_cast<Symbol *>())
         if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
           in.got->addEntry(*dylibSymbol);
 }
 
 void Writer::createLoadCommands() {
   headerSection->addLoadCommand(make<LCDyldInfo>(bindingSection));
   headerSection->addLoadCommand(make<LCLoadDylinker>());
-  headerSection->addLoadCommand(make<LCSymtab>());
+  headerSection->addLoadCommand(
+      make<LCSymtab>(symtabSection, stringTableSection));
   headerSection->addLoadCommand(make<LCDysymtab>());
   headerSection->addLoadCommand(make<LCMain>());
 
   uint8_t segIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     if (seg->isNeeded()) {
       headerSection->addLoadCommand(make<LCSegment>(seg->name, seg));
       seg->index = segIndex++;
void Writer::createLoadCommands() {
   // binary and we don't have support for that yet, so mock it out here.
   headerSection->addLoadCommand(
       make<LCLoadDylib>("/usr/lib/libSystem.B.dylib"));
 }
 
 void Writer::createHiddenSections() {
   headerSection = createInputSection<MachHeaderSection>();
   bindingSection = createInputSection<BindingSection>();
+  stringTableSection = createInputSection<StringTableSection>();
+  symtabSection = createInputSection<SymtabSection>(*stringTableSection);
   createInputSection<PageZeroSection>();
 }
 
 void Writer::sortSections() {
   llvm::stable_sort(inputSections, SectionComparator());
 
   // TODO This is wrong; input sections ought to be grouped into
   // output sections, which are then organized like this.
void Writer::assignAddresses(OutputSegment *seg) {
   addr = alignTo(addr, PageSize);
   fileOff = alignTo(fileOff, PageSize);
   seg->fileOff = fileOff;
 
   for (auto &p : seg->getSections()) {
     ArrayRef<InputSection *> sections = p.second;
     for (InputSection *isec : sections) {
       addr = alignTo(addr, isec->align);
+      fileOff = alignTo(fileOff, isec->align);
       isec->addr = addr;
       addr += isec->getSize();
       fileOff += isec->getFileSize();
     }
   }
 }
 
 void Writer::openFile() {

 }
 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
   for (OutputSegment *seg : outputSegments) {
     uint64_t fileOff = seg->fileOff;
     for (auto &sect : seg->getSections()) {
       for (InputSection *isec : sect.second) {
+        fileOff = alignTo(fileOff, isec->align);
         isec->writeTo(buf + fileOff);
         fileOff += isec->getFileSize();
       }
     }
   }
 }
 
 void Writer::run() {
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)
     assignAddresses(seg);
 
   // Fill __LINKEDIT contents.
   bindingSection->finalizeContents();
+  symtabSection->finalizeContents();
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
   // addresses and offsets. We don't have to recalculate the other segments
   // since sortSections() ensures that __LINKEDIT is the last segment.
   assignAddresses(getOutputSegment(segment_names::linkEdit));
 
   openFile();
   if (errorCount())

lld/test/MachO/symtab.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: lld -flavor darwinnew -o %t %t.o
+# RUN: llvm-readobj -symbols %t | FileCheck %s
+
+# CHECK:      Symbols [
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _main
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __text (0x1)
+# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: bar
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __text (0x1)
+# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __data
+# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+.data
+.global foo
+foo:
+  .asciz "Hello world!\n"
+
+.text
+.global bar
+.global _main
+
+_main:
+  mov $0, %rax
+  ret
+
+bar:
+  mov $2, %rax
+  ret