milen.me
milen.me

Apple’s Linker & Deterministic Builds

Permalink | RSS

TL;DR

  • Universal deterministic builds require that all paths in artifacts must be repo checkout independent.
  • On Apple platforms, the linker will insert absolute paths to object files in executables.
  • In Xcode 11, Apple added a new linker option, -oso_prefix, that can relativise OSO absolute paths.
  • Another source of non-determinism in object files are the OSO timestamp entries.
  • Deterministic Builds

    One of the requirements for universal deterministic builds is that they are independent of the source checkout path, on any machine. Consequently, there can be no absolute paths in the output artifacts.

    Debug Info & Paths

    When it comes to compiling C/Obj-C/C++ code for Apple platforms, absolute paths in executables can be found in debug info inserted by:

    • Compiler: paths to source files.
    • Linker: paths to object files.

    An obvious question arises: why does the linker insert paths to object files?

    DWARF on macOS

    On Apple platforms, DWARF debugging data can reside in one of two places:

    • Object Files: The object file for each translation unit will contain DWARF debugging data. Executables will contain absolute paths to the object files, so that the debugger can find the debugging info there.
    • dSYM Bundles: An Apple bundle which contains the combined DWARF data from all the object files. The executable and its corresponding debug information are linked using an UUID.

    Rationale

    There’s very special reason why DWARF data is embedded in the object files rather than the compiled executables: much faster incremental builds. Such builds do not have to incur the cost of embedding the full debug info on every build, even if just a single object file changes.

    The obvious downside is that it makes debugging of executables depend on having access to the original object files. That’s why dSYM bundles exist which combine all the debugging info from the object files. dsymutil can be thought of a DWARF linker.

    Avoiding Absolute Paths

    Compiler

    Clang supports the -fdebug-prefix-map flag which provides the ability to relativise absolute source paths in the debug info. For example, you can use it like so: -fdebug-prefix-map=/Users/milen/repo=..

    Linker

    As explained earlier, Mach-O executables would store paths to the object files which contain debug data in OSO entries. You can run the nm command on a binary with debug information to inspect such entries:

    nm -a out/main | grep OSO
    000000005eaede8d - 03 0001   OSO /Users/milen/repo/out/hello.o
    000000005eaede8f - 03 0001   OSO /Users/milen/repo/out/main.o

    In 2019, as part of Xcode 11, Apple added a new linker option, -oso_prefix, which can be used to relativise the OSO paths. For example, when linking using the Clang driver, we can pass:

    clang ... -Wl,-oso_prefix,/Users/milen/repo/

    If we then print the OSO entries, we will see that they have been relativised:

    nm -a out/main | grep OSO
    000000005eaede8d - 03 0001   OSO out/hello.o
    000000005eaede8f - 03 0001   OSO out/main.o

    I’d also recommend using MachO-Explorer to visually inspect the symbol tables.

    OSO Entries & Timestamps

    Another source of non-determinism in Mach-O executables are the timestamps associated with the OSO symtab entries. Those are used to determine if the object files are out of sync with the executables.

    For example, if the debugger determines that an object file is newer than the executable which points to it, that means the executable was not recompiled after recompiling the object file.

    The strategy used in Buck to guarantee deterministic executables is to always set the modification dates of all object files / static libraries to a predefined date. The tradeoff there is that it breaks the ability of the debugger to detect object file / executable synchronisation issues.

    libtool & ld64

    If you do not want to apply postprocessing yourself, you have a few options.

    libtool supports the -D option which can be used to guarantee deterministic values. The documentation says:

    When building a static library, set archive contents' user ids, group ids, dates, and file modes to reasonable defaults. This allows libraries created with identical input to be identical to each other, regardless of time of day, user, group, umask, and other aspects of the environment.

    In addition, both libtool and ld64 support the ZERO_AR_DATE environment variable to control the timestamps for the OSO entries (ld64 code, libtool code).

    Debugging

    lldb tries to resolve relative paths against the current working directory, so to make sure debugging works, we need to adjust the cwd and add a source mapping. This can be done either at the lldb prompt or in a lldbinit script.

    script import os
    script os.chdir("/Users/milen/repo")
    settings append target.source-map ./ /Users/milen/repo

    Buck

    Buck, which supports distributed caching, is used as a core build system at Facebook. As the addition of -oso_prefix is relatively recent, how did Buck produce deterministic Mach-O executables until now?

    The answer is that Buck performs an optional post-processing step where all OSO entries are relativised, making the executables independent of the checkout path.

    While that’s a working solution, there are several downsides.

    Performance

    Relativisation requires rewriting both the symbol table and the string table. For large binaries (e.g., 500MiB-1,500MiB), the combined size of the tables can be around 50% of the binaries and processing that much data can be slow.

    Note that while we can patch the symbol and string tables in-place, different machines will produce string tables of different length depending on the checkout path length. That’s why we need to rewrite the full strings and symbol tables, to ensure that executables are bit for bit equal.

    As relativisation is very performance sensitive, special attention needs to be paid to the code implementing it. For example, just an additional 1 microsecond to process a symtab entry will result in ~5s slow down if we need to process 5 million entries (not unusual for binaries of this size).

    For example, you can see several optimisations ([1] [2] [3] [4]) I made to improve the performance of the process in Buck.

    Maintenance

    More code means higher maintenance cost. Furthermore, as we have to keep compatibility with Apple’s tooling, the code's behaviour has to be verified against every major Xcode release.

    Code Signing

    Relativisation, as a post-processing step, only works if the executables are not already code signed. As we mutate the binaries, this would in turn invalidate their signatures. While that’s not a problem if we are building from source, the approach would not work in all situations.

    Acknowledgement

    Many thanks to Michael Eisel for finding the new -oso_prefix option. Thanks to Mark Rowe for surfacing libtool's option.

    ← Back to Writings

    Any opinions and viewpoints expressed, explicitly or implicitly, are not endorsed by and do not represent any of my previous, current or future employers.