Predicting the Go linker

September 2, 2026

The Go linker amplifies a change. Edit one line and it regenerates half the binary, because most of a Go executable is tables derived from the function list, and the binary keeps that list because the runtime needs it. So nearly all of what changes is predictable from the old binary and a description of the edit, and a patch only has to carry what the prediction misses. A one-line change in a 30 MB program patches in 1.1 KB, against 150 KB for bsdiff. A Prometheus patch release patches in 80 KB, against 2.7 MB.

Presage is a patcher built on that idea: the patch is a plan the decoder predicts the new binary from, plus a correction for the bytes it got wrong. Applied to Chrome, it halved the patch Chrome's own updater ships for a 291 MB C++ binary. Go suits the idea better than C++, because the linker derives so much more of the file, and derives it by rules simple enough to follow exactly.

What the linker derives

A Go program is statically linked and carries the runtime and everything the runtime needs. Less than half of it is code:

.gopclntab is the runtime's symbol table. It holds every function's name and address, and for every instruction the file and line it came from, how deep the stack is, and which words of the stack hold pointers, packed into tables that functions with identical entries share. Stack traces, panics and the garbage collector all read it, which is why stripping a Go binary leaves it alone: debug/gosym can list every function in a stripped binary. .rodata holds the type descriptors behind reflection, interfaces and the collector's bitmaps, and each descriptor names its element types, methods and name string by offsets from a base address.

None of it survives a build. The linker lays out the code package by package, with main last, then regenerates every table from the result: sorted by address, packed, and cross-referenced by offset. Grow one function and every function after it moves, every table entry naming an address moves with it, and every offset into a table that grew shifts. A byte-level differ finds the moved code, since finding moved regions is what it does. It cannot know that a 35 MB table is a function of the function list, so it ships the differences.

What one line does

Add w.Header().Set("X-Foo", "bar") to one HTTP handler of a 30 MB program. The handler grows by 192 bytes, since functions are aligned to 32. It lives in main, the last package in the layout, so only the functions after it move; an edit in a low-level library would move nearly everything. Even so, 14% of the file's bytes change. The compiled edit is under 200 of them.

Nearly all of the rest is offsets moved by constants. Each function's tables sit together in one shared blob, and a function's record holds the offset where each of its tables starts. The edited function's tables grew by 34 bytes in total:

Its own record changes in one field, the line table's offset, by the 7 bytes the file table in front of it grew. The record of every function after it changes in four fields: the entry offset by 192, and the three table offsets by 34. Records before the edit are byte-identical.

Two numbers, the 192 and the 34, determine every changed field in every record after the edit, and the same holds for the function index, the stack maps and the type descriptors that name moved code. The linker computed all of it from the new function list. A decoder holding the old binary and the two numbers can predict all of it.

Predicting it

That is what the Go module does. Its plan is the new function list as a diff against the old one, which functions were added, removed or resized, plus how the data sections shifted. For this pair that is one resized function, and the plan compresses to almost nothing. For Chrome, the equivalent function map had to be built from unstripped binaries on the encoder side and took up a tenth of the patch. A Go binary carries its own.

From the plan and the old binary, the decoder predicts the new file in full. It copies each function to its new address, decodes it as x86-64, and re-targets every PC-relative operand through the function map, so calls, jumps and loads point where they should. It regenerates .gopclntab: the function index, every entry offset, and every offset into the shared tables. It walks the type descriptors from the runtime's module data and rewrites every offset in them. It recomputes the ELF headers from the section table it now knows, and the FIPS integrity sum, an HMAC over the crypto module that the runtime checks at startup, from the finished image. An edited function is predicted in pieces that may come from anywhere in the old code, since the compiler emits the same sequences for the same constructs; the encoder tries each candidate and keeps the ones that beat a plain copy.

The encoder runs the same prediction, compares it with the real new binary, and ships the difference as a correction. Here that is 330 bytes, nearly all of them the compiled edit and the two build-ID notes, which hash the build's inputs and cannot be derived from its output. With the plan and the container's BLAKE3 hashes, the patch is 1,100 bytes. A wrong prediction costs bytes, never correctness: the decoder checks the result against the release hash before anything uses it.

A release

Prometheus 3.13.1 to 3.13.2 edits two source files and bumps a few dependencies. Fewer than a hundred of the binary's 114 thousand functions are added or resized. The linker amplifies that into a file that differs from its predecessor in 84% of its bytes.

Region by region across the new file, this is how much each differ sends:

Chunk dedup, the rsync family, sends most of the file, because a block survives only if it is byte-identical, and slid code has a changed displacement every few dozen bytes. xdelta3 and bsdiff find the slide and then pay for the displacements, one with copy instructions and the other with a difference stream. Zucchini would translate the references it recognises inside its copies, but it does not recognise a Go binary as something it can disassemble, and patches it raw. The prediction is wrong about a sixth of a percent of the file, and what it misses is the change itself: the new functions, the descriptors and index entries that came with them, and the bodies the compiler resized. Encoding takes four seconds and applying one.

The further apart two builds are, the more of the new file is new rather than derived, and the less of it the prediction covers. The next minor release, 3.13.2 to 3.14.0, adds six thousand functions and resizes hundreds more; its patch is 4.8 MB against bsdiff's 9.8 MB, half rather than a thirtieth.

Debug information

Upstream ships Prometheus unstripped: 38 MB of symbol tables and DWARF on top of the stripped binary, the DWARF compressed section by section. On that file the same patch release costs bsdiff 28 MB. Compression is a second amplifier. Debug information is full of code addresses, so moving the functions changes it throughout, and a compressed stream whose input changed near its start differs from there to its end.

DWARF is derived the same way the tables are. Its addresses are the function list's addresses, and its cross-references are offsets that move by the size of whatever grew in front of them. So the same prediction applies, one layer up. Presage unwraps the compression, predicts the DWARF from the function map the code layer already built, and compresses the result again with the compressor the linker used. Each layer predicts the structure it understands and hands the rest down, and what reaches the patch is the edit. The patch is 468 KB, against 28 MB for bsdiff. The one-line change with debug information patches in 1.9 KB.

Which linker

The patches are small because the prediction is exact, and it is exact because it models one linker: where this release of Go puts each table, how it aligns functions, which compressor it runs over the debug sections. The price is that the model has to follow the linker. Go 1.27 moved the type descriptors into a section of their own and replaced the debug compressor, and a model of 1.26 lays a 1.27 binary down wrong from the first descriptor. Presage was designed as modules for this reason. The Go module reads the Go version the binary carries, models that release, and checks that the file looks the way that linker wrote it; when it cannot, it declines and the generic ELF module that patched Chrome takes over. A release is supported once presage predicts a corpus of its binaries from themselves byte for byte. Today that is Go 1.26 and 1.27.

Every patch above was applied and compared with the target byte for byte. In each case what the patch carries is the edit and the code the compiler made from it. The linker's share, the larger half of the file, is predicted rather than sent.

presage is on GitHub at wjordan/presage.