The DIE Tree

20 minintermediateModule 3: DIEs, Types, Scopes, Locations and FramesContinues from dwarf-address-to-line

20 min · Module 3: DIEs, Types and Scopes · Structures

Why This Matters

Modules 1 and 2 read the line number program, which answers one question: which source line is this address on. Everything else a debugger needs is in a different section, and that section is not a table. It is a tree, compressed so aggressively that the compression is itself the first thing you have to understand.

The unit of the tree is the DIE — a Debugging Information Entry. Each one is a tag (what kind of thing), a list of attributes (what is known about it), and a flag saying whether it has children. A struct's members, a function's parameters, a variable's type: all of it is DIEs arranged in a tree, and the whole tree is what lets a debugger say g_nest.next->x and be right.

A Simple Model

Three ideas, in the order you need them:

A DIE is a number plus a list. In .debug_info, a DIE is a single ULEB128 — an abbreviation code — followed by a run of attribute values. The code says which shape the DIE has; the values fill that shape in.
The shape lives in .debug_abbrev. For each code: a tag, a has-children flag, and a list of (attribute, form) pairs. A form says how to read the value — one byte, four bytes, a ULEB, an offset into a string section.
A zero code ends a run of siblings. A 0 byte in .debug_info is not a DIE. It is a closing bracket.

Why the abbreviation table exists at all. The reference binary has 54 DIEs. Written out naively, every one of them would repeat the tag and the attribute names — roughly 40 bytes of pure repetition per DIE. Instead each distinct shape is described once in .debug_abbrev, and the DIE itself becomes just the code plus the values. Two DW_TAG_member DIEs with identical attribute lists both use code 7, and cost one byte each. The design is the reason .debug_info is 0x2e0 bytes for 54 DIEs rather than several kilobytes.

The Actual Detail

The first DIE of the reference binary, at .debug_info offset 0x0c, decoded field by field. Every value here was produced by a decoder written from the specification and then required to match both readelf and llvm-dwarfdump.

Offset	Bytes	Attribute	Form	Value
0x0c	`0b`	abbreviation code 11			`DW_TAG_compile_unit`, has children
0x0d	`63 00 00 00`	`DW_AT_producer`	`strp`	offset 0x63 into `.debug_str`
0x11	`1d`	`DW_AT_language`	`data1`	29 = C11
0x12	`03`	attribute 0x90	`data1`	3 = C
0x13	`47 16 03 00`	attribute 0x91	`data4`	0x31647 = 202311
0x17	`00 00 00 00`	`DW_AT_name`	`line_strp`	offset 0 → `types.c`
0x1b	`08 00 00 00`	`DW_AT_comp_dir`	`line_strp`	offset 8 → the build directory
0x1f	`49 11 00 00 00 00 00 00`	`DW_AT_low_pc`	`addr`	0x1149
0x27	`80 00 00 00 00 00 00 00`	`DW_AT_high_pc`	`data8`	0x80 = 128 bytes
0x2f	`00 00 00 00`	`DW_AT_stmt_list`	`sec_offset`	0 — the join to `.debug_line`
0x33	`01`	next DIE’s abbrev code			`DW_TAG_base_type`

Two things in that table are worth a second look, because both are traps rather than facts.

Attributes 0x90 and 0x91 have no agreed name. The two reference readers disagree about them:

readelf: DW_AT_language_name DW_AT_language_version llvm-dwarfdump: DW_AT_unknown_90 DW_AT_unknown_91

The numbers and the values agree; only the names differ. These are gcc extensions sitting in the DWARF 5 range with no standard name, so each tool picks a label. The attribute number is the truth and the name is a convention. When you write a tool, key off the number.

DW_AT_high_pc is a length here, not an address. Its form is DW_FORM_data8, which means the value 0x80 is a byte count. The function runs 0x1149 to 0x11c9. A reader that treats 0x80 as an address concludes the function spans from 0x1149 to 0x80, which is nonsense — and the form is the only thing that tells you. The rule is: if the form is an address form, high_pc is an address; if it is a constant form, it is a length. This is the same trap you met in the line program, in a different attribute.

One section, many units

The reference binary links two .c files, so .debug_info holds two units back to back, each with its own length and its own abbreviation table:

Unit at	`unit_length`	`debug_abbrev_offset`	DIEs
0x0	0x20b	0x0	27
0x20f	0xcd	0x100	27

A decoder that reads the first unit and stops reports 27 DIEs where readelf reports 54, and raises no error at all. The unit header is self-delimiting, so the fix is to loop until the section is exhausted.

The abbreviation table trap

Those two units point at two different tables in .debug_abbrev, and the second reuses the codes 1 to 15 for entirely different tags. readelf lists all thirty entries:

$ readelf --debug-dump=abbrev assets/samples/types_O0 | grep -cE '^   [0-9]+ '
30

So a table ends at a lone 0 code, and a decoder must stop there. Collecting every entry into one dictionary keyed by code lets the second table overwrite the first, and the result is the nastiest kind of wrong: the byte walk stays in step, every DIE is still found at the correct offset, every value is still read with the correct form — and every tag name and attribute list belongs to the wrong table. Nothing crashes. Nothing misaligns. It simply describes a different program.

A Real Example

Reading the tree by hand. The first four DIEs, with the indentation showing the nesting:

<0><0c>  abbrev 11  DW_TAG_compile_unit        [has children]
  <1><33>  abbrev 1   DW_TAG_base_type         unsigned char
  <1><3a>  abbrev 1   DW_TAG_base_type         short unsigned int
  <1><41>  abbrev 1   DW_TAG_base_type         unsigned int

And the shape that code 1 has, from .debug_abbrev:

1  DW_TAG_base_type  [no children]
     DW_AT_byte_size  DW_FORM_data1
     DW_AT_encoding   DW_FORM_data1
     DW_AT_name       DW_FORM_strp

Put those together and the walk is mechanical. At 0x33 read one byte: 1. Look up code 1: a DW_TAG_base_type with no children and three attributes. Read three values in the order the table gives — one byte, one byte, four bytes — which lands the next DIE at 0x3a. It is byte-for-byte the same shape, so it is code 1 again.

Now the nesting. A code with the has-children flag set opens a level; the next 0 byte closes it. struct Nest at 0xb4 looks like this:

<1><b4>  abbrev 6   DW_TAG_structure_type  Nest  [has children]
  <2><bf>  abbrev 2   DW_TAG_member  origin
  <2><cb>  abbrev 2   DW_TAG_member  label
  <2><d7>  abbrev 2   DW_TAG_member  flags
  <2><e3>  abbrev 2   DW_TAG_member  next
  <2><ef>  00                      <- closes the member list
<1><f0>  abbrev 8   DW_TAG_array_type  [has children]
  <2><f9>  abbrev 9   DW_TAG_subrange_type
  <2><ff>  00                      <- closes it

The <2> prefix is the depth. The zero at 0xef is not a DIE and has no abbreviation code; it is the bracket closing the four members. A decoder that treats a zero as an error stops here, and one that treats it as a DIE desynchronises at the very next byte.

All 54 DIEs of the reference binary, their depths, offsets, codes and tags, were compared against both readers. Not a single one differs.

Try It Yourself

$ gcc -gdwarf-5 -O0 -o shape types.c main.c
$ readelf --debug-dump=info shape | head -30
$ readelf --debug-dump=abbrev shape | head -20

Then use the decoder that ships with this course, which is written from the specification rather than from a tool:

$ cd courses/dwarf/assets
$ python3 dwarf_decode.py ../samples/types_O0 --limit 6
$ python3 crosscheck.py ../samples/types_O0
  types_O0   OK   (54 DIEs, 281 attributes, CFI ops agree)
CROSS-CHECK: ALL READERS AGREE

Three checks worth making on any binary you open:

How many abbreviation tables are there? More than one unit usually means more than one table. readelf --debug-dump=abbrev prints them consecutively with no separator, which is exactly why they get merged by accident.
Do the unit lengths add up? Start at 0, add unit_length plus 4, and you should land on the next unit header. For the reference binary: 0x0 + 0x20b + 4 = 0x20f, which is where the second unit starts.
Is the has-children flag consistent with the zeros? Every [has children] DIE must be followed by a matching 0 at the same depth. If a depth never closes, the tree is truncated and something upstream ate a byte.

And check the trap that cost the most time here: compile with -c instead of linking, and compare readelf’s output against a hex dump of the same bytes. They will disagree, and readelf will be right — it applied the relocations that the linker would have applied, and the file itself still holds zeros. This is why every byte-level example in this course uses a linked executable.

Check Your Understanding

Without looking back: you are walking the DIE tree, you have just read a DIE at 0xb4 that is DW_TAG_structure_type with the has-children flag set, and the next byte is 02. What does the 02 mean, and where does the next DIE go?

Apply It

You are writing a DWARF reader and it works on every single-unit binary you test it against. On a binary built from two source files it reports half the functions and no error. What is the bug, and what is the general rule your reader needs?

The general habit: a container that is self-delimiting must be walked to its end, and the walk must be checked against the container's own size. A parser that stops early is the one class of bug that produces plausible output rather than a crash.

Connect

The DIE tree is the same data the ELF symbol table holds, with a great deal more structure. An ELF symbol gives you a name, an offset and a size; a DIE gives you a type, a scope, a source location and a relationship to other DIEs. The DWARF sections concept explains why .debug_info is the biggest of them, and the versions concept covers what changes between DWARF 2 and 5 in the unit header you just read.

The abbreviation table has a direct ancestor in the COFF course: the COFF string table is the same idea of resolving a small number to a name through a shared pool, and the COFF aux record is a cousin of the attribute list — both exist so a record can name a shape once and then store only what varies.

Two concepts build directly on this one. Next, the thing the tree exists to describe: Types and Type Chains.