Mach-O Binaries (2015) | Hacker News Reader

Mach-O Binaries (2015)

m4b.io

33 pointsjaprozs7 comments

The trie structure described in the article can be (ab)used to export an infinite number of symbols from a library: https://www.corsix.org/content/exporting-an-infinite-number-...

That seems like another case of excessive complexity leading to surprising results.

Presumably the additional complexity was thought to be beneficial to performance, but PE's simple list of names with ordinal hints, or just ordinals alone, was sufficient for decent performance even with the much slower systems on which it was initially designed for. (Its predecessor, NE, was similar.)

There are different kinds of complexity. Thanks to ordinals, PE has two ways to link against a symbol (by name and by ordinal), and if you use ordinals then you need a .def file, which has to be kept consistent over time if you want to keep your DLL ABI-compatible. That adds a bunch of developer-facing complexity. In contrast, improved exported-symbol data structures such as Mach-O’s export tries or ELF’s DT_GNU_HASH are mostly just implementation details that developers don’t need to care about.

As far as I know, when not using ordinals, Windows’ dynamic linker resolves symbols by binary-searching the export table, which is sorted by symbol name. This is almost identical to the mechanism that Mach-O relied on prior to the introduction of the export trie, and macOS’s dynamic linker isn’t particularly inefficient. So the only time PE wins is when using ordinals, with their associated complexity.

Also, if you compare today’s systems to the systems that PE was designed for, today’s processors are much faster, but today’s programs are also much larger with a greater number of symbols being imported and exported. And performance expectations are higher… well, at least when it comes to low-level system components. (User-facing app launch times may well be worse, but that’s a more complicated problem.)

This is a nice writeup, especially the part about the import binding FSA! These kinds of little state machines show in all sorts of image format and image format-adjacent places, like DWARF's line program[1] and location expression encoding.

(Having written parsers for all three, I think Mach-O is the best "major" program image format. It's certainly the most well abstracted.)

[1]: https://swatinem.de/blog/dwarf-lines/

Yes, I enjoyed the write-up. I think for the same reasons as you. I found it easy to trace the program control through successive library loading. I have always been excited about Apple optimizing it's silicon for the abstractions used by mach.

Surprised that there was not a mention of the multi-architecture fat binaries; on NEXTSTEP you could have quad-Fat binaries that had in a single binary, code for SPARC, Motorola 68K, HP PA-RISC and x86.

I suppose the mentioned structures were used to hold the different bits of code, while sharing e.g. text strings that were loaded in .text or whatnot.

> I suppose the mentioned structures were used to hold the different bits of code, while sharing e.g. text strings that were loaded in .text or whatnot.

I don't believe so: universal ("fat") binaries are basically a container type, with N fully independent contained Mach-O slices. It isn't even compressed; each architecture's binary is just mashed into the file, one after another.

Reply on news.ycombinator.com