[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

104

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

49

Nit: we normally use lowerCamelCase instead of snake_case.

lld/MachO/Writer.cpp

337

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

397

Nit: variable naming

401

Do we need a TODO here for handling more types?

433

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

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

337

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

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

167–168

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

368

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.

370

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.

385

Change to nDesc

387

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

350

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.

369

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

350

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.

368

Sure!

370

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

99 ↗

(On Diff #258141)

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/Driver.cpp

 //===- Driver.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
 //
 //===----------------------------------------------------------------------===//
 
bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
   config = make<Configuration>();
   symtab = make<SymbolTable>();
   target = createTargetInfo(args);
 
   config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"));
   config->outputFile = args.getLastArgValue(OPT_o, "a.out");
   config->searchPaths = getSearchPaths(args);
 
-  getOrCreateOutputSegment("__TEXT", VM_PROT_READ | VM_PROT_EXECUTE);
-  getOrCreateOutputSegment("__DATA", VM_PROT_READ | VM_PROT_WRITE);
-  getOrCreateOutputSegment("__DATA_CONST", VM_PROT_READ | VM_PROT_WRITE);
+  getOrCreateOutputSegment("__TEXT");
+  getOrCreateOutputSegment("__DATA");
+  getOrCreateOutputSegment("__DATA_CONST");
 
   for (opt::Arg *arg : args) {
     switch (arg->getOption().getID()) {
     case OPT_INPUT:
       addFile(arg->getValue());
       break;
     case OPT_l:
       if (Optional<std::string> path = findDylib(arg->getValue()))
bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
   createSyntheticSections();
 
   // Initialize InputSections.
   for (InputFile *file : inputFiles)
     for (InputSection *sec : file->sections)
       inputSections.push_back(sec);
 
   // Add input sections to output segments.
   for (InputSection *isec : inputSections) {
-    OutputSegment *os =
-        getOrCreateOutputSegment(isec->segname, VM_PROT_READ | VM_PROT_WRITE);
+    OutputSegment *os = getOrCreateOutputSegment(isec->segname);
     isec->parent = os;
     os->sections[isec->name].push_back(isec);
   }
 
   // Write to an output file.
   writeResult();
 
   if (canExitEarly)
     exitLld(errorCount() ? 1 : 0);
 
   freeArena();
   return !errorCount();
 }

lld/MachO/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
public:
   virtual size_t getSize() const { return data.size(); }
 
   InputFile *file = nullptr;
   OutputSegment *parent = nullptr;
   StringRef name;
   StringRef segname;
 
   ArrayRef<uint8_t> data;
+
+  // TODO these properties ought to live in an OutputSection class.
+  // Move them once available.
   uint64_t addr = 0;
   uint32_t align = 1;
+  uint32_t sectionIndex = 0;
   uint32_t flags = 0;
 
   std::vector<Reloc> relocs;
 };
 
 extern std::vector<InputSection *> inputSections;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/OutputSegment.h

 //===- OutputSegment.h ------------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
public:
   StringRef name;
   uint32_t perms;
   uint8_t index;
   llvm::MapVector<StringRef, std::vector<InputSection *>> sections;
 };
 
 extern std::vector<OutputSegment *> outputSegments;
 
-OutputSegment *getOrCreateOutputSegment(StringRef name, uint32_t perms);
+OutputSegment *getOrCreateOutputSegment(StringRef name);
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/OutputSegment.cpp

 //===- OutputSegment.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 "OutputSegment.h"
 #include "lld/Common/Memory.h"
+#include "llvm/BinaryFormat/MachO.h"
 
 using namespace llvm;
+using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<OutputSegment *> macho::outputSegments;
 
-OutputSegment *macho::getOrCreateOutputSegment(StringRef name, uint32_t perms) {
+OutputSegment *macho::getOrCreateOutputSegment(StringRef name) {
   for (OutputSegment *os : outputSegments)
     if (os->name == name)
       // TODO: assert that os->perms == perms, once we figure out what to do
       // about default-created segments.
       return os;
 
   auto *os = make<OutputSegment>();
   os->name = name;
-  os->perms = perms;
+
+  if (name == "__TEXT") {
+    os->perms = VM_PROT_READ | VM_PROT_EXECUTE;
+  } else {
+    os->perms = VM_PROT_READ | VM_PROT_WRITE;
+  }
+
   outputSegments.push_back(os);
   return os;
 }

lld/MachO/Writer.cpp

 //===- Writer.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
 //
 //===----------------------------------------------------------------------===//
 

 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void createLoadCommands();
   void scanRelocations();
   void assignAddresses();
 
   void createDyldInfoContents();
+  void createSymtabContents();
 
   void openFile();
   void writeHeader();
   void writeSections();
 
   void run();
 
   std::vector<LoadCommand *> loadCommands;
void writeTo(uint8_t *buf) const override {
     c->initprot = VM_PROT_READ;
   }
 
   uint64_t getOffset() const { return fileOff + contents.size(); }
 
   uint64_t fileOff = 0;
   uint64_t addr = 0;
   SmallVector<char, 128> contents;
 };
 
 class LCDyldInfo : public LoadCommand {
 public:
   uint32_t getSize() const override { return sizeof(dyld_info_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dyld_info_command *>(buf);
     c->cmd = LC_DYLD_INFO_ONLY;

 class LCSymtab : public LoadCommand {
 public:
   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 = symOff;
+    c->nsyms = nSyms;
+    c->stroff = strOff;
+    c->strsize = strSize;
   }
+
+  uint64_t symOff = 0;
+  uint64_t nSyms = 0;
+  uint64_t strOff = 0;
+  uint64_t strSize = 0;
 };
 
 class LCLoadDylib : public LoadCommand {
 public:
   LCLoadDylib(StringRef path) : path(path) {}
 
   uint32_t getSize() const override {
     return alignTo(sizeof(dylib_command) + path.size() + 1, 8);
void Writer::assignAddresses() {
   uint64_t addr = ImageBase + sizeof(mach_header_64);
 
   uint64_t size = 0;
   for (LoadCommand *lc : loadCommands)
     size += lc->getSize();
   sizeofCmds = size;
   addr += size;
 
+  // TODO This is wrong; input sections ought to be grouped into
+  // output sections, which are then organized like this.
+  uint64_t sectionIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     addr = alignTo(addr, PageSize);
 
     for (auto &p : seg->sections) {
       ArrayRef<InputSection *> sections = p.second;
       for (InputSection *isec : sections) {
         addr = alignTo(addr, isec->align);
         isec->addr = addr;
         addr += isec->getSize();
+        isec->sectionIndex = ++sectionIndex;
       }
     }
   }
 
   addr = alignTo(addr, PageSize);
   linkEditSeg->addr = addr;
   linkEditSeg->fileOff = addr - ImageBase;
 }
 
 // LC_DYLD_INFO_ONLY contains symbol import/export information. Imported
 // symbols are described by a sequence of bind opcodes, which allow for a
 // compact encoding. Exported symbols are described using a trie.
 void Writer::createDyldInfoContents() {
   uint64_t sectionStart = linkEditSeg->getOffset();
   raw_svector_ostream os{linkEditSeg->contents};
 
   // Emit bind opcodes, which tell dyld which dylib symbols to load.
 
   // Tell dyld to write to the section containing the GOT.
   os << (char)(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | in.got->parent->index);
   encodeULEB128(in.got->addr - in.got->parent->firstSection()->addr, os);
   for (const DylibSymbol *sym : in.got->getEntries()) {
     // TODO: Implement compact encoding -- we only need to encode the
     // differences between consecutive symbol entries.
     if (sym->file->ordinal <= BIND_IMMEDIATE_MASK) {
       os << (char)(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | sym->file->ordinal);
     } else {
       error("TODO: Support larger dylib symbol ordinals");
       continue;
     }
     os << (char)BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
     os << sym->getName() << '\0';
     os << (char)(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
     os << (char)BIND_OPCODE_DO_BIND;
   }
 
   // TODO: emit bind opcodes for lazy symbols.
   os << (char)BIND_OPCODE_DONE;
 
   dyldInfoSeg->bindOff = sectionStart;
   dyldInfoSeg->bindSize = linkEditSeg->getOffset() - sectionStart;
+}
 
-  // TODO: Implement symbol export trie.
+// A symbol table is composed of two lists:
+// - The symbol table: A sequence of nlist_64 structs
+// - The string table: A sequence of symbol names delimited by \0
+// symbol table entry [i] corresponds to string table entry [i]
+// https://github.com/aidansteele/osx-abi-macho-file-format-reference#nlist_64
+void Writer::createSymtabContents() {
+  uint64_t start = linkEditSeg->getOffset();
+
+  symtabSeg->symOff = start;
+  symtabSeg->nSyms = 0;
+
+  SmallVector<char, 128> stringTable;
+  raw_svector_ostream stringTableOs{stringTable};
+  // 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 pool.
+  // Therefore we insert a dummy value at position zero.
+  stringTableOs << '\0';
+
+  raw_svector_ostream os{linkEditSeg->contents};
+  for (Symbol *sym : symtab->getSymbols()) {
+    uint8_t nType = N_UNDF;
+    uint8_t nSect = NO_SECT;
+    uint16_t nDesc = 0;
+    uint64_t nValue = 0;
+
+    // TODO support other symbol types
+    // TODO populate n_desc
+    if (auto defined = dyn_cast<Defined>(sym)) {
+      nType = (N_EXT | N_SECT);
+      nSect = defined->isec->sectionIndex;
+
+      // For the N_SECT symbol type, n_value is the address of the symbol
+      nValue = defined->value + defined->isec->addr;
+    }
+
+    ++symtabSeg->nSyms;
+    auto nStrx = stringTable.size();
+    stringTableOs << sym->getName() << '\0';
+
+    // Emit one nlist_64 struct.
+    endian::write<uint32_t>(os, nStrx, endianness::little);  // n_strx
+    os << nType;                                             // n_type
+    os << nSect;                                             // n_sect
+    endian::write<uint16_t>(os, nDesc, endianness::little);  // n_desc
+    endian::write<uint64_t>(os, nValue, endianness::little); // n_value
+  }
+
+  // The string table is located right after the symbol table.
+  symtabSeg->strOff = start + symtabSeg->nSyms * sizeof(nlist_64);
+  symtabSeg->strSize = stringTable.size();
+  os << stringTable;
 }
 
 void Writer::openFile() {
   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
       FileOutputBuffer::create(config->outputFile, fileSize,
                                FileOutputBuffer::F_executable);
 
   if (!bufferOrErr)
     error("failed to open " + config->outputFile + ": " +

 
 void Writer::run() {
   createLoadCommands();
   scanRelocations();
   assignAddresses();
 
   // Fill __LINKEDIT contents
   createDyldInfoContents();
+  createSymtabContents();
+
   fileSize = linkEditSeg->fileOff + linkEditSeg->contents.size();
 
   openFile();
   if (errorCount())
     return;
 
   writeHeader();
   writeSections();

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: 0x[[#%x, MAIN_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: 0x[[#MAIN_VALUE + 8]]
+# 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