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 DeclContexts 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.