dsymutil links the
DWARF from a program’s object files into a .dSYM
bundle. The part that does the actual work is the DWARF linker. LLVM provides
two implementations: the original classic linker and the parallel linker, a
modern rewrite that
became the default in June
after it was deemed
ready for widespread adoption.
The classic linker remains available through --linker=classic.
Both take the same input and should produce equivalent debug info. The classic linker does most of its work on one thread in a fixed order, while the parallel linker distributes the work across all available cores. The parallel linker must make its output independent of the order in which threads complete their work. I’ve written about the classic linker’s lockstep algorithm before. This post puts the two side by side.
What a DWARF Linker Does
On Darwin, the static linker doesn’t copy DWARF into the executable. It leaves the debug info in the object files and records a debug map that identifies which object files contributed to the binary and, for each of them, which symbols were kept and at what address. The DWARF linker reads the object files and the debug map and writes one set of DWARF sections for the whole program.
Consider the example below: two source files that share a header.
// geo.h
namespace geo {
struct Point { int x, y; };
inline int twice(const Point &p) { return 2 * (p.x + p.y); }
}
// a.cpp
#include "geo.h"
int use_b(const geo::Point &p);
int main() { geo::Point p{1, 2}; return geo::twice(p) + use_b(p); }
// b.cpp
#include "geo.h"
int use_b(const geo::Point &p) { return geo::twice(p); }
Both object files describe geo::Point, and both contain a copy of
geo::twice. The static linker kept the copy from a.o, so the debug map only
lists twice under a.o.
The figures in this post show what the two linkers generate for this example.
Debug info entries (DIEs) from a.o are blue, those from b.o are orange, and
linker-generated entries are green.
The DWARF linker has four responsibilities:
- Relocate addresses. Object files contain relative addresses, while the debug map provides their relocated addresses.
- Drop the DIEs for code that the static linker dropped. In the example that’s
the copy of
twiceinb.o. - Emit only one copy of a type when several units describe it by taking
advantage of the C++ One Definition Rule (ODR).
geo::Pointis such a type. - Assign final values to string offsets, abbreviation codes, cross-unit references, and range and location list offsets.
How the linkers assign these values accounts for much of the difference between
their designs. A reference from one unit to a DIE in another, a
DW_FORM_ref_addr, is an offset from the start of .debug_info. It depends on
the size of everything written before its target. The classic linker assigns
offsets while it clones DIEs, so it has to clone them in one fixed order. The
parallel linker clones each unit into per-unit buffers and assigns offsets
afterwards, so it can clone units in any order and on any thread.
Scheduling
The classic linker processes object files one at a time, in debug map order, on
two threads that move in
lockstep. The
first thread runs the analysis phase. It parses the DIEs of an object file,
records the parent of each one, and works out which
DeclContext
each DIE belongs to—information later used for ODR uniquing. The second thread
runs the cloning phase, which only starts on an object file once its analysis
is complete. It decides which DIEs are live, clones them, and streams them to
the output together with the unit’s line table, ranges and location lists. In
the meantime, the first thread analyzes the next object file.
The cloning thread also assigns DIE offsets, string offsets and abbreviation codes as it writes the output. All units share one string table and one abbreviation table. Processing this shared state on a single thread makes the output deterministic, but also creates a bottleneck that prevents the classic linker from making use of more than two threads. Once an object file is written, its DIEs are freed, so only one object file’s cloned DIEs are in memory at a time.
The parallel linker schedules work at the compile-unit level. The thread pool processes object files, scheduling each compile unit within them as a separate task. A unit loads its DIEs, marks what’s live, names its types, clones the live DIEs into buffers that belong to the unit, and frees its input. Unlike the classic linker’s lockstep pipeline, compile units ordinarily proceed through these stages independently.
Units that reference each other are the exception. In the input, a
DW_FORM_ref_addr can point into another unit of the same object file, which is
possible with Link Time Optimization (LTO). Because liveness in one unit
then depends on the other, such units stop after loading and advance together,
one stage at a time. Their liveness stage repeats until it finds no new
references between units.
The tasks share two concurrent hash tables, one for strings and one for types.
After processing all object files, the linker uses the type table to build an
ordinary compile unit containing the types shared between units. The linker
calls this the type unit, although it isn’t a DWARF type unit (DW_UT_type)
and has no type signature. It then assigns each buffer a location in the output,
patches the values that depend on the final layout, and writes the sections.
Liveness and the Parent Walk
Both linkers use the debug map to seed liveness. If it provides an address for a DIE, the corresponding code or data was kept by the static linker and the DIE becomes a root. This covers functions, labels and variables with static storage, while base types are always kept. From a kept DIE, three kinds of related DIEs are kept as well:
- the DIEs it references, such as its type
- its children when they are necessary for completeness, such as the members of a struct
- its ancestors, since a function in a namespace needs the namespace DIE around it
Let’s take a look at b.o on its own, where use_b is the only root. Its
parameter type leads through const Point & and const Point to geo::Point,
which causes the struct’s members and its parent geo to be retained. The copy
of twice has no address in the debug map and is dropped, even though its parent
is kept.
The step from a kept DIE up to its ancestors is the parent walk. It keeps the ancestors but not their other children, unless an ancestor is itself incomplete without them.
The classic linker walks each unit once and marks DIEs with a keep bit. When it keeps a DIE, it walks up the parent chain and keeps each ancestor until it reaches one that’s already kept. References can lead into other units of the same object file, so the walk needs the parent links of every unit in that file. That’s why the analysis phase finishes a whole object file before the cloning phase starts on it.
The classic walk also considers ODR state. When a reference leads to a type
whose definition an earlier object file already supplied, the walk stops there
and the local copy is never marked. This happens in b.o: by the time it’s
processed, a.o has supplied geo::Point, so neither Point nor geo is kept
for b.o. Liveness in one object file therefore depends on the object files
that precede it.
The parallel linker processes object files independently, so its liveness decisions depend only on the object file being processed. For each DIE, it decides whether to keep it and where to emit it: in its own unit, in the type unit, or in both.
With two destinations, there are two parent walks. A type assigned to the type
unit needs its enclosing namespaces there, and a function that remains in its
unit needs them in that unit. Each walk sets its own flag on the ancestors and,
like the classic one, stops at the first ancestor that already has it. In the
example, geo is emitted in both places: as the parent of Point in the type
unit and as the parent of twice in the unit of a.cpp.
The marks of a DIE are bits in one atomic word. Most of the time only one thread works on a unit, but units that reference each other mark DIEs in each other’s trees at the same time.
Moving shared types into a separate compile unit introduces one constraint: a DIE in the type unit may only reference other DIEs in the type unit. If a type refers to something that has to stay in its own unit, such as a type from an anonymous namespace, the type is moved back to its unit as well. The linker repeats this check until it reaches a fixed point where no more types need to be moved.
ODR Uniquing
The linker receives two descriptions of geo::Point, but the ODR guarantees
that both represent the same type, so one copy is enough. Both linkers perform
ODR uniquing only for C++ and Objective-C++ units, because C has no such rule.
For large C++ projects, ODR uniquing can make the difference between fitting within
Mach-O’s 4GB limit or not.
The classic linker identifies a type by its DeclContext: the names of the
enclosing scopes plus its own name, with the declaration file, line and byte
size as a safeguard. Only DIEs that declare something by name are assigned one:
namespaces, structs, classes, unions, enumerations, typedefs, members and
functions. Pointer types, const types and base types are not assigned a
DeclContext and are never shared.
The classic linker retains the first copy it encounters. When it clones the
first live definition for a DeclContext, that DIE becomes the canonical DIE
and its output offset is recorded in the context. From then on, a reference to
the type becomes a DW_FORM_ref_addr to the recorded offset, and the local
copy isn’t kept, as described above. The type stays in the unit that first
defined it; “first” is well defined because one thread clones the object files
in order.1
The unit of b.cpp keeps its own int, const Point & and const Point, with
only the last of these pointing into the unit of a.cpp.
The parallel linker clones units concurrently, so it cannot use the first copy it encounters as the canonical definition.
A type is identified by a key computed from the DIE itself: its tag, the key of
its enclosing scope, and its name. Functions, templates and arrays add the keys
of their parameters, template arguments and dimensions. Unnamed types use their
declaration position and their contents. Every type gets a key, including base
types, pointers and const types. A key only depends on the unit’s own DIEs, so
each unit computes its keys without coordination. Equal keys from different
units map to the same entry in the shared type table.
The linker selects a definition based on link order. Every unit has a priority based on its position in the link order: the earlier it appears in the input, the higher its priority. When several units provide a definition for the same key, the definition from the highest-priority unit is selected. If a lower-priority unit clones its definition provisionally, a higher-priority unit can replace it later. The same definition is selected on every run, regardless of timing.
The selected definitions are moved from their original units into the type
unit, which appears first in the output as a compile unit named
__artificial_type_unit. The linker builds it after processing all object files
by sorting the entries of the type table, ensuring that its layout does not
depend on insertion order. The other units refer into it with
DW_FORM_ref_addr.
Every type in the type unit came from a.o, because a.o appears first in the
link order. The units of a.cpp and b.cpp are left with their functions and
an int each, since base types are always kept.
Writing the Output
The classic linker knows a DIE’s output offset as soon as it clones it, because everything before it is already laid out. A string is assigned its final offset the first time it’s seen. All units share one abbreviation table and, in DWARF 5, one string offsets table. References to DIEs that appear later in the same object file are fixed up before that file’s units are written.
In the parallel linker, each unit writes its sections into per-unit buffers. Wherever a value depends on the final layout, the unit writes a placeholder and records a patch. These patches cover string offsets, references into other units and into the type unit, and the offsets of range and location lists.
After all units are cloned, the linker assigns each buffer a start offset in a fixed order: the type unit first, then the units in debug map order. Strings receive their offsets in the same order, after which the patches are applied and the buffers are concatenated into the output sections.
Because units are written independently, each has its own abbreviation table
and, in DWARF 5, its own string offsets table. The type unit is a special case:
every thread adds to it, so indices into a string offsets table would depend on
timing. It therefore refers to strings by their offset in .debug_str, using
DW_FORM_strp, and fills in that offset using the same patching mechanism.
Trade-offs
The classic linker is deterministic by construction: one thread assigns DIE offsets, string offsets and abbreviation codes in a fixed order and holds the cloned DIEs of only one object file at a time. This thread is also the bottleneck, so additional cores don’t help.
For clang, using every core reduces the link time from
roughly 3 minutes to about 40 seconds.
This speedup comes at the cost of keeping the output of all units in memory
until the final pass, maintaining separate tables per unit, and replacing the
classic linker’s implicit reliance on order with explicit rules: a priority to
select the retained type, a sort to lay out the type unit, and a fixed order to
assign offsets.
This is also why the per-object numbers printed by
--statisticsdepend on the order in which the object files are processed. ↩︎