DWARF Debug Information: Abbreviation Tables and the Line Number State Machine

A debugger asked to print the value of a local variable must answer four questions: which function is executing, which lexical block encloses the current instruction, what the variable’s location is at that point, and what its type is. None of that is recoverable from machine code. The compiler records it in DWARF, a format that describes a program as a tree of typed entries with attributes, and separately describes the mapping from instruction addresses to source positions.

The two halves are independent and often used separately. A symbol server needs only the line table to turn a faulting address into a file and line. A debugger needs the tree to evaluate expressions and the line table to place breakpoints. The encoding of both is unusual: the tree is heavily compressed through shared abbreviation definitions, and the line table is not a table at all but a program for a small state machine. Reading either requires executing the format rather than indexing it.

Entries, abbreviations, and the tags that give them meaning

The tree lives in .debug_info, which is a sequence of compilation units, and that section is one of many that a linker assembles and a strip step can discard; the bookkeeping that names and locates them is described in Section Headers, String Tables, and the Bookkeeping a Linker Needs. Each unit begins with a header giving the unit’s length, its DWARF version, an abbreviation table offset, and an address size. What follows is a series of Debugging Information Entries, each identified by a tag: DW_TAG_subprogram for a function, DW_TAG_variable for a variable, DW_TAG_structure_type for a struct, DW_TAG_lexical_block for a scope, DW_TAG_base_type for an integer or floating type.

An entry is not self-describing. It begins with an unsigned LEB128 value that indexes into the unit’s abbreviation table, and the abbreviation declares both the tag and the ordered list of attributes the entry carries. A single byte therefore can stand for “a subprogram with a name, a low PC, a high PC, and a declaration file and line”, which is why the abbreviation mechanism exists: without it, every entry would repeat its tag and its attribute names, and a typical object’s debug information would be several times larger.

An attribute specification in an abbreviation pairs an attribute name, such as DW_AT_name or DW_AT_type, with a form, such as DW_FORM_string, DW_FORM_data4, DW_FORM_ref4, or DW_FORM_exprloc. The form determines how the value is encoded and how many bytes it occupies. This is the part that a reader cannot shortcut: the size of an entry is not stored anywhere, so the only way to advance to the next entry is to decode every attribute in order, using the form from the abbreviation. A single wrong form choice desynchronises the entire remainder of the unit, producing plausible-looking nonsense rather than an error.

The forms also carry meaning about resolution. DW_FORM_ref4 holds an offset within the current unit, so a reference must be resolved relative to the unit’s start. DW_FORM_ref_addr holds an offset into the whole .debug_info section, which makes it usable across units and therefore larger. DW_FORM_strp holds an offset into .debug_str, a shared string table, so identical type names across thousands of units occupy one copy. DW_FORM_strx and DW_FORM_addrx index into per-unit tables introduced with version 5, which allow a linker to merge units without rewriting their contents.

Walking the tree and the sibling chain

Entries nest. A compilation unit’s root entry, usually DW_TAG_compile_unit, has children; each function entry has children for its parameters and locals; a struct type has children for its members. The nesting is encoded with two sentinel values. A 0 abbreviation index in place of an entry means “end of the current sibling list”, returning to the parent. A DW_CHILDREN_yes flag in the abbreviation means the entry has children, so the parser descends; DW_CHILDREN_no means the next byte begins a sibling or a terminator.

The consequence is that a tree walk needs a stack or recursion, and the depth is bounded only by the file’s contents. A malformed unit consisting of thousands of nested entries with children will exhaust a naive recursive parser’s stack. Iterative walking with an explicit depth counter is the standard defence, and the depth limit must be chosen by the reader rather than read from the file.

A subtlety of the sibling chain: a 0 terminator closes one level, not all levels. A function entry with three parameter children ends with a single zero abbreviation index, which closes the parameter list; the function entry’s own children are then complete, and the next byte belongs to the function’s sibling. Getting this wrong produces trees where the debugger attributes a local variable to the wrong function, and the symptom is an expression evaluation that reports a variable as unavailable rather than an error.

/* Decode an abbreviation declaration: tag, children flag, then
   (attribute, form) pairs terminated by a zero pair. */
#include <stdint.h>

static uint64_t uleb(const uint8_t **p) {
    uint64_t v = 0; unsigned shift = 0;
    while (**p & 0x80) { v |= (uint64_t)(**p & 0x7f) << shift; shift += 7; (*p)++; }
    return v | ((uint64_t)**p++ << shift);
}

struct abbrev { uint64_t code, tag; int has_children; };

int read_abbrev(const uint8_t **p, struct abbrev *out, uint32_t *attrs, int max) {
    out->code = uleb(p);
    if (out->code == 0) return 0;                 /* end of abbrev table */
    out->tag = uleb(p);
    out->has_children = *(*p)++ != 0;
    int n = 0;
    while (n < max) {
        uint32_t at = (uint32_t)uleb(p);
        uint32_t fm = (uint32_t)uleb(p);
        if (at == 0 && fm == 0) break;            /* zero pair ends the list */
        attrs[n * 2] = at; attrs[n * 2 + 1] = fm; n++;
    }
    return n;
}

The zero-pair terminator is a real constraint on the format: no attribute name and no form is zero, so the pair can serve as a sentinel without a count. It also means an abbreviation whose list is unterminated consumes the remainder of the table before the parser notices, which is one of the reasons debug sections are conventionally validated by a tool that walks them fully rather than sampled.

Locations as expressions rather than addresses

A variable’s location is not always a fixed offset from a frame pointer. An optimised function may keep a value in a register for part of its range, spill it to the stack for another part, and recompute it from two other values elsewhere. DWARF expresses this with location lists: a sequence of ranges, each paired with either a register, a stack offset, or a bytecode expression that computes an address when evaluated.

The bytecode lives in .debug_loc or, from version 5, in .debug_loclists, and is a stack machine with opcodes such as DW_OP_reg5, DW_OP_fbreg, DW_OP_deref, and DW_OP_plus_uconst. A debugger evaluating a variable runs this program against the current register set and memory. The design lets the compiler describe arbitrarily complex locations without extending the format, and it makes the debugger’s correctness depend on its own expression evaluator rather than on the file being simple.

The cost is that a variable can be genuinely unavailable at some addresses, which the format expresses by giving a range an empty location description. That is not a defect in the debug information; it is the accurate statement that the value exists nowhere at that point, usually because it was optimised away. Debuggers that present such variables as zero rather than as unavailable are misreading an empty expression list as a zero value.

The line table as a program

.debug_line maps addresses to source positions, and it does so by encoding a state machine. The state consists of an address, a file index, a line number, a column, an is_stmt flag, an end_sequence flag, and a few less-used fields. The section is a series of line number programs, one per compilation unit, each with a header declaring its version, address size, the length of the header itself, the minimum instruction length, and a table of file names and directory names.

Execution begins with the state reset to defined defaults, then proceeds through opcodes. A special opcode, the most common case, advances the address by a multiple of the minimum instruction length and advances or rewinds the line number by a signed amount, then appends a row. A standard opcode such as DW_LNS_advance_pc, DW_LNS_advance_line, or DW_LNS_copy performs a single effect. An extended opcode carries a length prefix so that implementations can add new operations without breaking existing readers.

The rows are not stored in the file; they are the trace of running the program. That is why a line table cannot be read by seeking to an offset, and why tools that report line numbers must emulate the machine faithfully, including the initial state and the reset that occurs at each DW_LNE_end_sequence. It is also why the table is compact: a typical function’s line information reduces to a handful of special opcodes, each one or two bytes, describing changes rather than absolute positions.

Version 5 restructured the file name table so that file indices are per-unit rather than global and file entries can reference directory entries by index, which fixed the long-standing problem that a file’s directory was recorded as an absolute path in version 2 through 4. The change also introduced DW_LNCT_* content type descriptors, so a reader for version 5 cannot reuse the version 4 header parser even though the opcode execution is nearly identical.

Split debug files and the address that is zero

On ELF systems, debug information is commonly stripped from the executable and stored in a separate file whose build identifier matches the .note.gnu.build-id section of the binary. The debug file has the same section names but no program headers, and every address it records is the link-time address from the original, unrelocated image.

For a position-independent executable, those addresses are offsets from the load base, not runtime addresses. A debugger therefore computes the load bias by comparing a known symbol’s runtime address with its link-time address, then adds that bias to every address in the debug sections before comparing against the faulting address. A debugger that omits this step reports line numbers for the wrong instructions, and the error scales with the bias: a PIE loaded far from zero produces line information that is internally consistent but entirely misattributed. The relationship between the bias and the relocation types that produce it is covered in Position-Independent Executables and the Cost of PC-relative Addressing.

The build identifier mechanism itself is a hash of the sections that were linked, stored in a note and copied into the debug file. It allows a symbol server to locate the exact debug file for a binary without relying on a build path, and it is what makes it possible to discard debug information from deployed binaries without discarding the ability to debug them later.

Why the format resists partial reading

DWARF has no index from an address to a compilation unit. Finding the unit that contains a given address requires either scanning every unit’s root entry for its low and high PC attributes, or consulting a separate index section. Version 5 added .debug_addr and .debug_rnglists and, in the same revision, defined an optional .debug_names index that maps names to entries. Earlier versions had no standard index at all, and implementations built their own.

That absence is a consequence of the format’s design centre: DWARF describes a program as the compiler saw it, and the compiler emits units in the order it processed source files. There is no requirement that units be sorted by address, and no requirement that a unit be contiguous in address space. A linker that merges units from many objects, or a compiler that emits cold sections separately, produces an address mapping that is monotonic only by accident. Consumers that assume otherwise work on small programs and fail on large ones, which is the characteristic failure mode of a format that was specified for correctness of description rather than for the convenience of lookup.