When working on compilers dealing with machine code, you eventually have to deal with linking. For most cases, the system linker is fine… until you need to link libraries for another platform1 or don’t want to rely on the system linker at all.

For many projects, the typical solution is to reach for something like LLD. While that’s an excellent tool, it’s also a massive dependency and can drastically increase build times. It’s also not a library that is all that easy to embed into your own code either.

While working on Esper and Conjure, I wanted a “good enough” linker that could be embedded into the compiler runtime itself without causing my build times to go from seconds to (almost) hours.

What’s shocking is that there wasn’t a lot of options in this space, especially that could do the job across platforms. The closest I could find was Fabrice Bellard’s phenomneal TinyCC project, which has a small linker that can write ELF, PE/COFF and Mach-O. But there were a few problems with it:

  • It’s deeply tied to the rest of TinyCC, which is a C compiler.
  • It doesn’t appear to support cross-linking (one of my main goals)2.
  • It’s licensed as GPLv2, which is incompatible with my projects.

#What’s a linker even do?

For those unfamiliar with the concept, your compiler3 (typically) spits out object files containing the machine code equivalent of your program. However, this code is incomplete.

Many of the functions in your program are likely coming from other libraries4, and the compiler doesn’t know where those functions are located in memory. The linker takes all of your object files, along with any libraries you want to link against, and produces a single executable file that can be run on your system.

main.o util.o libc.a linker executable

#Creating a cross-platform linker

Step one was a refresher on the three major executable formats:

  • ELF for Linux and other Unix-like systems
  • PE/COFF for Windows
  • Mach-O for macOS

I had to understand how they worked, how they differed, and what the linker needed to do to produce them.

Then I started scaffolding out the architeture of the library itself. I wanted a straight forward, plain C99 library that could be reduced into a single, amalgamated header with as few dependencies as possible.

tl_State *s = tl_new(TL_TARGET_HOST);

tl_set_output_type(s, TL_OUTPUT_MEMORY);
tl_add_symbol(s, "host_callback", host_callback);  /* resolve against your own code */
tl_add_file(s, "plugin.o");
tl_relocate(s);

void (*init)(void) = tl_get_symbol(s, "plugin_init");
init();

The API is quite primitive and hopefully straight forward. It does demand that you understand the steps involved in linking, and then gives you a lot of control over the process. You can link into memory, write an executable or shared library, or even merge multiple object files into a single object file.

main.o util.o libc.a tinylinker executable / .so / .dll / .dylib merged .o function pointers in memory
AI Disclaimer

Once the architecture and API were in place, I leaned on Claude to help fill in a lot of the implementation specifics. A big chunk of writing a linker is tedious “read the manual and implement it” busy work, like encoding every relocation type for every format, and that’s exactly the kind of thing AI is good at grinding through.

I also used it to build out a rather large test suite, which made it much easier to trust all of that code across ten different targets and has helped me uncover a lot of edge cases I would have otherwise missed.

#Runtime target selection

One of the coolest features of the library is that you can link for any of the three supported formats on any host. You can link a Mach-O binary on Linux, or a PE/COFF binary on macOS. This is done by specifying the target architecture and format when creating the linker state.

Or put more bluntly: Every target is picked at runtime, so any host can cross-link for any of them.

That said, there are some limitations. Not every target is supported on every host, and some features are not available on all targets. For example, Mach-O has a lot of features that are not present in ELF or PE/COFF, and vice versa.

The current list of supported targets is below.

ELFPE/COFFMach-O
i386yesyesno
x86_64yesyesyes
armyesnono
arm64yesyesyes
riscv64yesnono

#Targets

A fun side effect of picking the target at runtime is that Mach-O output gets ad-hoc signed by the linker itself5. This means you can link a binary on Linux, copy it over to an arm64 Mac, and it’ll just run.

#Linking straight into memory

Instead of writing a file to disk, you can link into memory and ask for function pointers back. That’s exactly what a compiler runtime needs when it wants to compile some code and immediately run it, similar to how a JIT works.

You can also hand the linker symbols from your own program (like host_callback in the example above). This lets the code you just linked call back into the program that linked it, which is super handy for things like plugins or hot reloading.

#Is it fast?

Yes! At least it is on my M4 Max. I haven’t fully setup a CI/CD pipeline to do benchmarks across proper machines, so many of my initial benchmarks are collected from my daily driver via emulation or by using specialized libraries like mold. I’m hoping to change that soon though!

LinktinylinkerComparison
Tiny Mach-O4.19ms17.21ms (Apple ld)
Large ELF42.08ms87.33ms (mold)

Most of that lead comes from not doing things. It doesn’t do link-time optimization7, it doesn’t write out a symbol table, and it doesn’t use multiple threads. Linkers, like mold, are doing a lot more work6.

#What it does and doesn’t do

Being “good enough” means making some tradeoffs. Here’s a quick look at what you get, and what you give up.

  • Under 1MB as a static archive
  • No dependencies beyond libc
  • Never calls exit() on you, errors are reported back to your code
  • Handles all four thread-local storage models
  • No link-time optimization
  • Single threaded
  • No PE unwind tables
  • COFF output has no GOT

#Error handling is a big deal

Since this is meant to be embedded inside other programs, it’s not enough for the linker to fail gracefully on bad input. The program using it needs to survive too.

So the test suite links about 380 deliberately damaged files for each target. A crash, a link that never finishes, or a failure that doesn’t report an error all count as test failures.

#Some fun problems along the way

Linkers are full of tiny details that nobody tells you about until something breaks. Here are a few of my favorites.

What’s musl?

A couple of these involve musl, a small alternative to the glibc C library most Linux systems ship with. My Linux tests run inside Alpine Linux containers, which use musl, so it’s the C library tinylinker sees the most of.

#The 2048 bytes nobody told me about

musl on RISC-V answers __tls_get_addr({1, 0}) with an address that’s 2048 bytes past the thread-local variable you actually asked for8.

Rather than just trusting that offset, the tests now write each thread-local variable one way and read it back another. Two unrelated relocation paths have to land on the exact same byte, or the test fails.

#The eight byte libm

musl ships a libm.a that’s only eight bytes long, since the math functions actually live in libc. tinylinker was rejecting it as broken, which meant refusing every -lm on a musl system. Oops.

#Still a work in progress

This library is an important piece of a toolchain I’m relying on for several of my own projects and I’m excited to finally have it in a state where I can start using it. That said, it’s still a work in progress and there are plenty of features I want to add.