[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

233

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 ↗

(On Diff #267428)

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

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];
+    nlist_64 sym;
+    // nlist_64 structs should be 64-bit-aligned according to the C++ language
+    // spec, but nList (which is mmap'ed from a file) may not be at an aligned
+    // offset. This memcpy() ensures that we have the correct alignment, but
+    // it should be optimized away on architectures that support unaligned
+    // reads.
+    memcpy(&sym, nList.data() + i, sizeof(nlist_64));
 
     // Undefined symbol
     if (!sym.n_sect) {
       StringRef name = strtab + sym.n_strx;
       symbols[i] = symtab->addUndefined(name);
       continue;
     }