DWARF Line Tables and How an Address Becomes a Source Line

An address inside a stripped binary is a number. Inside a binary with debug information it is a file, a line, a column, and a flag saying whether a breakpoint there would land on a statement boundary. The transformation is not a hash lookup or an interval tree stored directly; it is the output of a small virtual machine whose program is embedded in the .debug_line section. The compiler emits the program, and the debugger runs it to rebuild the table.

That design choice, storing a program rather than a table, is the origin of most of the format’s oddities. A table of address-to-line pairs would be far larger than the code it describes, because a typical statement spans several instructions and consecutive rows would repeat the same file and line. The line-number program compresses those repetitions by making each row an increment from the previous one, and the cost is that readers must simulate the machine rather than binary-search a sorted array.

The matrix and its registers

Conceptually the line table is a matrix with one row per address range and columns for address, file, line, column, and several boolean flags. The machine that produces it has a register for each column: address, file, line, column, is_stmt, basic_block, end_sequence, prologue_end, epilogue_begin, isa, and discriminator. All start at defined initial values — address zero, file 1, line 1, is_stmt set — and are reset at the start of each sequence.

The program is a sequence of opcodes in three classes. Special opcodes are the compressed common case: a single byte that simultaneously advances the address by a small amount, advances the line by a small amount, and appends a row. Standard opcodes do one thing each: DW_LNS_copy appends a row, DW_LNS_advance_pc adds to the address, DW_LNS_advance_line adds a signed offset to the line, DW_LNS_set_file changes the file register. Extended opcodes have a length field and a sub-opcode; the important one is DW_LNE_end_sequence, which appends a final row and starts a new sequence.

The result of running the program is a list of rows, each covering the address range from its own address up to the address of the next row. Because special opcodes encode the line delta in a fixed number of bits with a bias, the encoder can only use them when the deltas fit; otherwise it falls back to standard opcodes. This is why the same source produces different table sizes under different optimisation levels: aggressive inlining and reordering produce larger line deltas and more fallbacks.

A sequence is a contiguous run of rows terminated by DW_LNE_end_sequence. Sequences matter because they are not globally ordered by address. A function placed at a high address may have its sequence appear before one at a low address in the section, and a single function’s code can be split into several sequences when the compiler emits cold blocks into a separate section. A reader that assumes rows are sorted by address will produce wrong answers on exactly the binaries that matter — optimised ones.

Finding the program for a given address

The line table does not stand alone. It is reached through the debugging information entry for the compilation unit. In .debug_info, a compile unit’s DIE carries DW_AT_stmt_list, an offset into .debug_line, and usually DW_AT_comp_dir and DW_AT_name. The line table’s header, at that offset, holds the unit length, the version, the address size, the minimum instruction length, the line range used by special opcodes, the opcode base, the standard opcode lengths, and the tables of directories and file names.

Version differences are a practical hazard. DWARF 4 and earlier store directory and file entries as NUL-terminated strings with fixed fields. DWARF 5 introduced a directory index per file entry, content-type and MD5 checksum fields, and string offsets into .debug_line_str rather than inline strings. A reader that parses a DWARF 5 header with DWARF 4 assumptions will misread the file table and report wrong names, or crash. Debuggers and symbolizers therefore branch on the version field immediately after reading it.

The file table is also where the answer to “which file” gets complicated. A row’s file register is an index into the table, not a path. In DWARF 5, the entry gives a directory index and a file name, and the full path is assembled from the compile unit’s directory, the directory table entry, and the name, with rules about absolute paths that differ between producers. Two compilers can emit equivalent tables that resolve to different strings, and a symbolizer that concatenates naively will print a path that does not exist. The -f output of addr2line sidesteps this by printing the name as recorded.

Looking up an address

Lookup is a two-stage search. First the reader finds the compile unit whose address range covers the target, using the ranges in .debug_info: either DW_AT_low_pc and DW_AT_high_pc, or a range list for units that are not contiguous. Then it runs the unit’s line program once, building the row list, and finds the row whose address is the greatest one not exceeding the target, provided the target falls before that sequence’s end.

Running the program once per lookup is wasteful, so real readers run each unit’s program once and cache the resulting rows, or build a sorted index per sequence. Because rows within a sequence are non-decreasing in address but sequences are unordered, the index must be keyed by sequence. A sorted merge across sequences is the standard approach: sort sequences by start address, discard overlaps, and binary-search the merged array. Overlaps do occur, especially with inlining and identical code folding, and the format does not forbid them; a reader must pick one, typically the first in section order, and accept that the answer is one of several valid ones.

The row’s line number is not necessarily the line a programmer would point at. Compilers emit is_stmt rows at points where a breakpoint is meaningful, and non-is_stmt rows for instructions that belong to the same statement, such as the setup of a loop or the evaluation of part of an expression. A debugger setting a breakpoint on line 12 selects the first row with is_stmt set for that line. A symbolizer resolving a faulting instruction address reports whatever row covers it, is_stmt or not, which is why a crash inside an inlined function’s argument setup can map to a line that looks unrelated.

# Rows for one unit, with the machine's output already decoded.
readelf --debug-dump=decodedline ./program

# Address to function, file, and line; -i follows inlined frames.
addr2line -e ./program -f -i -a 0x4011a6

readelf --debug-dump=decodedline prints the decoded matrix, which is the fastest way to see whether a suspicious address falls inside a sequence at all. addr2line -i walks the inline chain recorded in .debug_info, printing one frame per inlined call, which is the only way to recover a source location for code that was inlined into a caller.

Where the mapping breaks

Four failure modes account for nearly every wrong line number.

Missing or mismatched debug information is the first. Line tables are tied to exact addresses in the exact binary that was compiled. Rebuilding the source, relinking, or patching a byte shifts addresses, and the table then points into the wrong function. The link between a binary and its debug information is recorded as a build identifier in an ELF note, not in the line table itself; the consequences of getting that association wrong are the subject of matching binaries to debug information.

Optimisation is the second. A statement can be attributed to instructions scattered across a function, and a single instruction can serve several statements. Variables may not exist at the point where their line appears. The line table remains accurate about which instruction the compiler attributed to which source line, and that attribution is a compiler decision, not a property of the program’s semantics.

Third-party code without tables is the third. A crash in a library built without -g has an address but no line. The fallback is the symbol table, which gives a function name at best, or a build identifier lookup to fetch separate debug information.

Truncated or compressed sections are the fourth. .debug_line may be compressed with SHF_COMPRESSED or with the older .zdebug convention, and a reader that does not decompress sees a header of nonsense. The section may also be split across multiple objects with .dwo files, in which case the skeleton unit in the main binary holds only an index and the rows live elsewhere.

Why the indirection earns its place

A naive alternative, a sorted array of (address, file, line) triples, is simpler to read and would compress badly. Text sections are typically several times larger than the source they came from, and a triple per instruction would add tens of bytes per instruction. The line program’s increments reduce that to a few bits per row in the common case, at the cost of a simulation step at load time. Debuggers pay that cost once and cache the result; symbolizers that process one address at a time pay it per invocation, which is why batch symbolization of a whole core file is far cheaper per address than a loop of individual lookups.

The same rows feed unwinding diagnostics and coverage tools, so the line program is not only a debugger’s concern. Any tool that reports a source location, whether a profiler, a crash reporter, or a coverage tool, is running this machine. The addresses it consumes usually come from a register state captured at a stop or a fault, described in what an ELF core file preserves, and the frame addresses it needs in order to report more than the innermost line come from the unwinder discussed in stack unwinding with call frame information.