[lld-macho] 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

Immediate future work will involve implementing section merging.

Depends on D76839: [lld-macho] Extend SyntheticSections to cover all segment load commands.

Initial version by @Ktwu, commandeered by @int3.

[int3]

lld/MachO/Writer.cpp

53

this could be constructed locally in the using method I think

lld/test/MachO/symtab_basic.s

40 ↗

(On Diff #252459)

maybe put one of these in a different section like .data?

[smeenai]

lld/MachO/InputSection.h

46 ↗

(On Diff #252459)

Nit: we normally use lowerCamelCase instead of snake_case.

lld/MachO/Writer.cpp

352

Hmm. This is gonna be incorrect for multiple sections of the same name, which should get merged together. Section merging is currently broken, as you pointed out.

I think we need an OutputSection class, similar to OutputSection in LLD ELF, to handle section merging. We have OutputSegments, but the sections in a segment themselves need merging too. That's also a much better place for the addr (which is the address in the *output*, not the address from the input) and n_sect fields to go.

[smeenai]

lld/MachO/Writer.cpp

390

It's n_desc, and we need a TODO here for filling this out.

397

Nit: variable naming

401

Do we need a TODO here for handling more types?

lld/test/MachO/symtab_basic.s

15 ↗

(On Diff #252459)

I think we should check the values, to make sure they're written correctly. They should be consistent (they'll depend on the base address, but that should be fixed).

[Ktwu]

lld/MachO/Writer.cpp

352

That makes sense, although I'm afraid any logic I write up for merging probably won't be correct. I'll try referencing what ELF's stuff does.

lld/test/MachO/symtab_basic.s

15 ↗

(On Diff #252459)

I didn't put down a value because I didn't know, at this stage, how to tell if a value is correct or not. Is there another command I can invoke to see if these values are sane (like if readobj uses the value and hopefully doesn't crash, for example)?

40 ↗

(On Diff #252459)

Yup, will try that!

[int3]

lld/test/MachO/symtab_basic.s

15 ↗

(On Diff #252459)

you could use FileCheck's numeric substitution blocks to write these values as offsets from the start of the __text section. I'm doing something like that in dylink.s in D76252.

[int3]

lld/MachO/Writer.cpp

397

I wonder if we should just drop the n_ prefix for internal variable names, i.e. just strx instead of nStrx. Not really sure why n_ was added in the first place, but it seems like some kind of ad-hoc namespace convention? (Not that it really makes sense for struct members...) In any case it doesn't seem to add much to code readability

[Ktwu]

Addressing first round of comments (minus the value checks in the test)

[Ktwu]

Verify that address offsets for the text segment are reasonable

[int3]

lld/MachO/Writer.cpp

395

s/contensOs/contentsOs/

[int3]

lld/MachO/InputSection.h

49 ↗

(On Diff #253738)

I think we should name this sectionIndex in accordance with lld-ELF's OutputSection::sectionIndex. (I've made that change in D76839)

lld/test/MachO/symtab_basic.s

1 ↗

(On Diff #253738)

naming nits:

1. Use hyphens instead of underscores for test names (consistent with other lld tests)
2. The "_basic" suffix seems a bit unnecessary since this will (hopefully quickly) become a non-basic test

[ruiu]

lld/MachO/Driver.cpp

168–169 ↗

(On Diff #253738)

This can now fit to a single line?

lld/MachO/Writer.cpp

381

Can you add a function comment about the structure fo the symbol table, so that readers can get a sense what this function is supposed to do without reading the code?

395

but maybe just os is fine.

[Ktwu]

Sorry for the delay in response, and thanks for the review so far!

lld/test/MachO/symtab_basic.s

1 ↗

(On Diff #253738)

Sure; I hoped that we could have a series of tests with one sanity test, but I'll happily rename this.

[Ktwu]

Address comments, rebase on D76252

[ruiu]

We usually construct a section in three phases as follows:

1. In the first phase, we add pieces of information to each section object (e.g. adding symbols to the symbol table section object), but we don't construct the actual contents at this stage. We only compute the size of each section.
2. We fix the layout of the output file, which can be done once we know the size of each section.
3. Finally, we let each section to write their contents directly to the output buffer.

This design has several advantages over constructing section contents early:

• This last phase can be parallelized for each section, which significantly improves performance of the writer.
• As we directly construct section contents to the output buffer, we can avoid an extra copy.

My understanding of this patch is that this creates section contents early. But can you avoid doing that?

[Ktwu]

My understanding of this patch is that this creates section contents early. But can you avoid doing that?

Of course!

lld/MachO/Writer.cpp

397

I think it helps map the value to the intended struct name; if I see a variable with this nPattern naming, it's easier to understand that the value is ultimately intended for use within the symbol table given the documented struct variable names.

[Ktwu]

@ruiu

Since D76839 is based on this diff, it'd be easier to land this diff as-is so that D76839 doesn't have to rebase. Any qualms about landing as-is and then changing the write order in another diff?

[MaskRay]

In D76742#1965176, @Ktwu wrote:

@ruiu

Since D76839 is based on this diff, it'd be easier to land this diff as-is so that D76839 doesn't have to rebase. Any qualms about landing as-is and then changing the write order in another diff?

For a patch series, amending an earlier patch may require the rebase of subsequent patches. I think that is just how things work. Email based reviews (e.g. [PATCH 0/5]) work this way, too. I don't think a question can be dismissed just because "landing a patch as-is can avoid rebasing future patches".

[Ktwu]

Addressing request to split generating content and assigning addresses. This doesn't functionally
do anything different than before since nothing in the writer is parallelized, but in principle
this could be adapted to be so.

[smeenai]

@ruiu, does this look good to you now?

lld/MachO/Writer.cpp

390

Idk if this is a useful reference to put in a comment, since it's a random person's GitHub copy of a document which may or may not stay alive. There's lots more official documentation of the Mach-O structures; in fact, LLVM has its own ones in http://llvm.org/doxygen/BinaryFormat_2MachO_8h_source.html#l00992. I'd say it's safe to omit this.

392

This is called after assignAddresses, so we should know our exact string table size at this point, right? We could call reserve on it with that exact size.

407

Change to nDesc

409

Nit: you don't need the parentheses.

lld/test/MachO/symtab.s

26

Nice!

32

How come you're not checking the section index for this one?

[ruiu]

lld/MachO/Writer.cpp

372

This function should be called finalize and should belong to LCSymtab class instead of Writer. nSyms and strSize member variables as well as how to compute the size of symtab are internal details of the symtab section, and Write shouldn't take care of them.

In ELF, we call function in this order:

1. For each output section, call finalize()
2. Call Writer::assignAddresses()
3. For each output section, call write()

(1) finalizes the contents of the section. Each section knows how to compute its size, and the size should be computed by finalize and shouldn't change afterwards.

391

This should move to LCSymtab as LCSymtab::write(uint8_t *buf). That function should directly write symbol table section contents to a given buffer (specifically without using SmallVector or raw_svector_ostream). I think you should take a look at ELF's writer.cpp as an example how we writer a writer.

[Ktwu]

lld/MachO/Writer.cpp

372

Gotcha; I'll move the functionality to LCSymtab, change the function names, and make sure I don't use local buffers when writing out the contents since that's unnecessary.

390

Sure!

392

Good point.

lld/test/MachO/symtab.s

32

It differs from what the system ld emits for the section index -- this diff emits 0x2, ld emits 0x3

For lack of understanding for why that it at the moment I figured neglecting the value to check is better than checking against an anomaly.

[int3]

For a patch series, amending an earlier patch may require the rebase of subsequent patches.

I'd agree if it were a series put up by one person, but with multiple people this creates a lot of friction. @Ktwu and I chatted and we agreed that I'd commandeer this, but I hope we can be more flexible for future work.

[int3]

address comments / rebase on top of D76839

[int3]

format

[ruiu]

Much better! Thank you for making the changes, this patch looks pretty good now. LGTM

[int3]

order section name declarations by output order

[int3]

only emit defined symbols for now

[int3]

rebase

[smeenai]

lld/MachO/SyntheticSections.h

97–141

Should this be part of this diff instead of the previous one?

Also, the same comment about renaming this to string table everywhere applies.

[int3]

rebase

[smeenai]

Reverted in rGfbae153ca583588de73d8fae84ec262c24d09025 because of a UBSan failure.

[int3]

Relanded as rG4f0cccdd7a06: [lld-macho][reland] Add basic symbol table output.

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:
   // 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) 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;
+}
+
+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 openFile();
   void writeSections();
 
   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.
   uint32_t sectionIndex = 0;
   // Add input sections to output segments.
   for (InputSection *isec : inputSections) {
     if (isec->isNeeded()) {
       if (!isec->isHidden())
         isec->sectionIndex = ++sectionIndex;
       getOrCreateOutputSegment(isec->segname)->addSection(isec);
     }
   }
 }
 
 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);
       isec->addr = addr;
       addr += isec->getSize();
       fileOff += isec->getFileSize();
     }
   }
 }
 
 void Writer::openFile() {
   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
       FileOutputBuffer::create(config->outputFile, fileOff,
                                FileOutputBuffer::F_executable);
 
   if (!bufferOrErr)
     error("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
   else
     buffer = std::move(*bufferOrErr);
 }
 
 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) {
         isec->writeTo(buf + fileOff);
         fileOff += isec->getFileSize();
       }
     }
   }
 }
 
 void Writer::run() {
   scanRelocations();
   createHiddenSections();
   // Sort and assign sections to their respective segments. No more sections can
   // be created after this method runs.
   sortSections();
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   getOrCreateOutputSegment(segment_names::linkEdit);
   // No more segments can be created after this method runs.
   createLoadCommands();
 
   // Ensure that segments (and the sections they contain) are allocated
   // addresses in ascending order, which dyld requires.
   //
   // 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