[lld-macho] Ensure reads from nlist_64 structs are aligned when necessary

[int3]

Summary

My test refactoring in D80217 seems to have caused yaml2obj to emit unaligned
nlist_64 structs, causing ASAN'd lld to be unhappy. I don't think this is an
issue with yaml2obj though -- llvm-mc also seems to emit unaligned nlist_64s.
This diff makes lld able to safely do aligned reads under ASAN builds while
hopefully creating no overhead for regular builds on architectures that support
unaligned reads.

Depends on D80217.

[smeenai]

Hmm. We're in for a world of hurt if this memcpy doesn't get optimized, so I wanna have a good sense of how reliable that is. Adding Reid and Kostya to see if they've dealt with similar issues/have thoughts on this.

Looking at a basic example https://godbolt.org/z/YjzzcQ, seems like clang, gcc and MSVC are all able to elide the memcpy (though interestingly enough, MSVC doesn't do this when it's optimizing for size, and ends up generating larger code as a result). Our case is a bit more complex though (it involes loops and ArrayRefs), so it's probably worth examining the generated assembly to confirm the elision is still happening.

Additionally, it seems unfortunate to have to rely on this optimization. An alternative would be making llvm-mc and yaml2obj create aligned outputs; I don't know what the potential downsides are (I'm sure there's some reason they aren't doing this already), but I'm also wondering how those tools aren't invoking UB if they're writing an nlist_64 out to an unaligned location (I guess it'd be fine if they're writing to the file directly instead of using memory mapping). From a brief look into ld64's object file parsing, it's also accessing the nlist_64 structs directly from the input file via a cast, so the same alignment issue exists there.

[efriedma]

Alternatively, we have some integer wrappers in llvm/Support/Endian.h that deal with both endianness and alignment. For example, you could define nlist_64 like this:

struct nlist_64 {
  support::ulittle32_t n_strx;
  uint8_t n_type;
  uint8_t n_sect;
  support::ulittle16_t n_desc;
  support::ulittle64_t n_value;
};

[smeenai]

In D80414#2055477, @efriedma wrote:

Alternatively, we have some integer wrappers in llvm/Support/Endian.h that deal with both endianness and alignment. For example, you could define nlist_64 like this:

struct nlist_64 {
  support::ulittle32_t n_strx;
  uint8_t n_type;
  uint8_t n_sect;
  support::ulittle16_t n_desc;
  support::ulittle64_t n_value;
};

Ah, those look really neat! Thanks for the pointer.

I don't know if it'd be wise to change BinaryFormat's nlist_64 definition at this point (the pervasive pattern with Mach-O is to use various swapStruct overloads to handle endianness), but we can look into that for LLD. Under the hood, those seem to use memcpy as well, but with some __builtin_assume_aligned trickery that might help with the elision?

[efriedma]

In terms of optimization, the primary benefit would just be that you're doing smaller memcpys at the same place you're using the values; that simplifies alias analysis, and smaller memcpys are more likely to optimize the way you want.

In terms of actually writing code, of course, the biggest benefit is that it just works; once you've defined the struct with the right types, you never have to think about alignment/endianness again.

[alexander-shaposhnikov]

lld/MachO/InputFiles.cpp

234

i suspect you might face the same issue with other data structures which should be properly aligned too,
so it would be good to think about a general consistent approach how to handle it.
Just for the record I'd like to mention how libObject solves this problem:

https://llvm.org/doxygen/MachOObjectFile_8cpp_source.html#l04264
https://llvm.org/doxygen/MachOObjectFile_8cpp_source.html#l00068

[int3]

The alignment wrappers are really neat! Especially that operator value_type() trick...

I've defined the struct in its own namespace to avoid colliding with the one in BinaryFormat/MachO.h. The duplication is a bit unfortunate but I reckon we can unify them later if desired?

[int3]

use support::ulittle

[int3]

remove comment

[int3]

lld/MachO/Writer.cpp

417–418

removed this comment since it's no longer relevant, though I'm still keeping the alignTo call since I believe ld64 does something similar

lld/MachO/InputFiles.h

 //===- InputFiles.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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_INPUT_FILES_H
 #define LLD_MACHO_INPUT_FILES_H
 
+#include "MachOStructs.h"
+
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 #include <map>
 #include <vector>
public:
   ArrayRef<llvm::MachO::section_64> sectionHeaders;
   std::vector<SubsectionMap> subsections;
 
 protected:
   InputFile(Kind kind, MemoryBufferRef mb) : mb(mb), fileKind(kind) {}
 
   void parseSections(ArrayRef<llvm::MachO::section_64>);
 
-  void parseSymbols(ArrayRef<llvm::MachO::nlist_64> nList, const char *strtab,
+  void parseSymbols(ArrayRef<lld::structs::nlist_64> nList, const char *strtab,
                     bool subsectionsViaSymbols);
 
   void parseRelocations(const llvm::MachO::section_64 &, SubsectionMap &);
 
 private:
   const Kind fileKind;
 };
 

lld/MachO/InputFiles.cpp

 // and COFF for Mach-O.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputSection.h"
+#include "MachOStructs.h"
 #include "OutputSection.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
for (const any_relocation_info &anyRel : relInfos) {
     }
 
     r.offset = rel.r_address;
     InputSection *subsec = findContainingSubsection(subsecMap, &r.offset);
     subsec->relocs.push_back(r);
   }
 }
 
-void InputFile::parseSymbols(ArrayRef<nlist_64> nList, const char *strtab,
-                             bool subsectionsViaSymbols) {
+void InputFile::parseSymbols(ArrayRef<structs::nlist_64> nList,
+                             const char *strtab, bool subsectionsViaSymbols) {
   // resize(), not reserve(), because we are going to create N_ALT_ENTRY symbols
   // out-of-sequence.
   symbols.resize(nList.size());
   std::vector<size_t> altEntrySymIdxs;
 
-  auto createDefined = [&](const nlist_64 &sym, InputSection *isec,
+  auto createDefined = [&](const structs::nlist_64 &sym, InputSection *isec,
                            uint32_t value) -> Symbol * {
     StringRef name = strtab + sym.n_strx;
     if (sym.n_type & N_EXT)
       // Global defined symbol
       return symtab->addDefined(name, isec, value);
     else
       // Local defined symbol
       return make<Defined>(name, isec, value);
   };
 
   for (size_t i = 0, n = nList.size(); i < n; ++i) {
-    const nlist_64 &sym = nList[i];
+    const structs::nlist_64 &sym = nList[i];
 
     // Undefined symbol
     if (!sym.n_sect) {
       StringRef name = strtab + sym.n_strx;
       symbols[i] = symtab->addUndefined(name);
       continue;
     }
 
for (size_t i = 0, n = nList.size(); i < n; ++i) {
     secondIsec->align = MinAlign(firstIsec->align, offset);
 
     subsecMap[offset] = secondIsec;
     // By construction, the symbol will be at offset zero in the new section.
     symbols[i] = createDefined(sym, secondIsec, 0);
   }
 
   for (size_t idx : altEntrySymIdxs) {
-    const nlist_64 &sym = nList[idx];
+    const structs::nlist_64 &sym = nList[idx];
     SubsectionMap &subsecMap = subsections[sym.n_sect - 1];
     uint32_t off = sym.n_value - sectionHeaders[sym.n_sect - 1].addr;
     InputSection *subsec = findContainingSubsection(subsecMap, &off);
     symbols[idx] = createDefined(sym, subsec, off);
   }
 }
 
 ObjFile::ObjFile(MemoryBufferRef mb) : InputFile(ObjKind, mb) {
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
 
   if (const load_command *cmd = findCommand(hdr, LC_SEGMENT_64)) {
     auto *c = reinterpret_cast<const segment_command_64 *>(cmd);
     sectionHeaders = ArrayRef<section_64>{
         reinterpret_cast<const section_64 *>(c + 1), c->nsects};
     parseSections(sectionHeaders);
   }
 
   // TODO: Error on missing LC_SYMTAB?
   if (const load_command *cmd = findCommand(hdr, LC_SYMTAB)) {
     auto *c = reinterpret_cast<const symtab_command *>(cmd);
-    ArrayRef<nlist_64> nList(
-        reinterpret_cast<const nlist_64 *>(buf + c->symoff), c->nsyms);
+    ArrayRef<structs::nlist_64> nList(
+        reinterpret_cast<const structs::nlist_64 *>(buf + c->symoff), c->nsyms);
     const char *strtab = reinterpret_cast<const char *>(buf) + c->stroff;
     bool subsectionsViaSymbols = hdr->flags & MH_SUBSECTIONS_VIA_SYMBOLS;
     parseSymbols(nList, strtab, subsectionsViaSymbols);
   }
 
   // The relocations may refer to the symbols, so we parse them after we have
   // parsed all the symbols.
   for (size_t i = 0, n = subsections.size(); i < n; ++i)

lld/MachO/MachOStructs.h

+//===- MachOStructs.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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines structures used in the MachO object file format. Note that
+// unlike llvm/BinaryFormat/MachO.h, the structs here are defined in terms of
+// endian- and alignment-compatibility wrappers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_MACHO_MACHO_STRUCTS_H
+#define LLD_MACHO_MACHO_STRUCTS_H
+
+#include "llvm/Support/Endian.h"
+
+namespace lld {
+
+namespace structs {
+
+struct nlist_64 {
+  llvm::support::ulittle32_t n_strx;
+  uint8_t n_type;
+  uint8_t n_sect;
+  llvm::support::ulittle16_t n_desc;
+  llvm::support::ulittle64_t n_value;
+};
+
+} // namespace structs
+
+} // 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 "Config.h"
 #include "ExportTrie.h"
 #include "InputFiles.h"
+#include "MachOStructs.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"
SymtabSection::SymtabSection(StringTableSection &stringTableSection)
     : SyntheticSection(segment_names::linkEdit, section_names::symbolTable),
       stringTableSection(stringTableSection) {
   // 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);
+  return symbols.size() * sizeof(structs::nlist_64);
 }
 
 void SymtabSection::finalizeContents() {
   // TODO support other symbol types
   for (Symbol *sym : symtab->getSymbols())
     if (isa<Defined>(sym))
       symbols.push_back({sym, stringTableSection.addString(sym->getName())});
 }
 
 void SymtabSection::writeTo(uint8_t *buf) const {
-  auto *nList = reinterpret_cast<nlist_64 *>(buf);
+  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
     if (auto *defined = dyn_cast<Defined>(entry.sym)) {
       nList->n_type = N_EXT | N_SECT;
       nList->n_sect = defined->isec->parent->index;
       // For the N_SECT symbol type, n_value is the address of the symbol

lld/MachO/Writer.cpp

 void Writer::assignAddresses(OutputSegment *seg) {
   addr = alignTo(addr, PageSize);
   fileOff = alignTo(fileOff, PageSize);
   seg->fileOff = fileOff;
 
   for (auto &p : seg->getSections()) {
     OutputSection *section = p.second;
     addr = alignTo(addr, section->align);
-    // We must align the file offsets too to avoid misaligned writes of
-    // structs.
     fileOff = alignTo(fileOff, section->align);
     section->addr = addr;
     section->fileOff = fileOff;
     section->finalize();
 
     addr += section->getSize();
     fileOff += section->getFileSize();
   }