I was recently answering questions about
dsymutil’s multi-threading
model and lockstep algorithm. I decided to write it down here for future
reference. This article focuses on types and the .debug_info
section.
Background
As a reminder, dsymutil is an optimizing DWARF linker.
- It only retains debug info for elements that appear in the final executable.
- It uses the One Definition Rule (ODR) to unique C++ types.
As will become clear, both of these heavily shaped its design.
The Debug Map
An important concept is the debug map. It’s emitted by the static linker (as nlist stabs records). It tells dsymutil which object files contributed debug information to the linked binary and, for each object file, which symbols and addresses from the original object files ended up in the linked binary.
dsymutil can dump the debug map in YAML format:
dsymutil --dump-debug-map <executable>
The algorithm starts by iterating through the object files in the debug map and
creating a LinkContext
. The analysis phase and the cloning phase each
operate on a single context (i.e., a single object file).
The Analysis Phase
During the analysis phase, dsymutil walks all the input DWARF data to build
the global DeclContext
information and gather the parent/child relationships
within the original compile unit.
A DeclContext
is a named program scope used for ODR-based type uniquing. The
set of DeclContext
s grows as new object files are analyzed. Conceptually, the
contexts form a tree: for example, a function scope may be contained in a
namespace scope, which itself may contain other scopes.
An important part of this process is pruning DIEs. DIEs (and their children)
are pruned when their DeclContext
already has a canonical DIE. A DIE is
marked as canonical when it is emitted in the output and assigned a canonical
offset in the cloning phase.
The Cloning Phase
The cloning phase consists of two stages. First, dsymutil identifies all DIEs that need to be present in the output. Starting from DIEs that have relocations, it builds a dependency tree of DIEs to retain. This involves walking both the children of a DIE (e.g., keeping a function means keeping its arguments) and its parents (e.g., keeping a member variable means keeping the class it belongs to).
In the second stage, all the retained DIEs are cloned and streamed to the
output. Once a DIE is emitted, it is assigned an offset, and becomes the
canonical DIE. When a DeclContext
is encountered again, dsymutil references
the already emitted DIE rather than emitting a redundant copy.
The Lockstep Algorithm
For the same object file, canonical DIE offsets create a dependency between the analysis phase and the cloning phase. However, the next object file can be analyzed while the cloning phase of the current file is still running. The two phases execute concurrently on two threads, but each phase only progresses after the other has completed. The algorithm mimics lockstep marching, hence the name.