A debugger looking up a name such as main should not have to read every
DIE in __debug_info. Apple’s tools therefore add four hash tables to the
__DWARF segment of a dSYM file, all
with the same layout. They are described in LLVM’s
Source Level Debugging
document; DWARF 5 later standardised a similar index, .debug_names.
All numbers are in the file’s byte order, which the magic number shows.
The four tables
| Section | Holds |
|---|---|
__apple_names | Functions and global or static variables: DW_TAG_subprogram, DW_TAG_inlined_subroutine and DW_TAG_label DIEs that have an address (DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges or DW_AT_entry_pc), and DW_TAG_variable DIEs whose location uses DW_OP_addr. A function is entered under its full (mangled) name and its base name; a variable with a linkage name under both names. An Objective-C method is entered under its full bracketed name and its selector. |
__apple_types | Named types that are not forward declarations (no non-zero DW_AT_declaration): the DIEs tagged DW_TAG_ array_type, class_type, enumeration_type, pointer_type, reference_type, string_type, structure_type, subroutine_type, typedef, union_type, ptr_to_member_type, set_type, subrange_type, base_type, const_type, immutable_type, file_type, namelist, packed_type, volatile_type, restrict_type, atomic_type, interface_type, unspecified_type and shared_type. Unnamed pointer types are left out. |
__apple_namespac | Every DW_TAG_namespace DIE; an unnamed one is entered as (anonymous namespace). |
__apple_objc | The method DIEs of each Objective-C class, keyed by class name; a category’s methods are entered under the class name and under Class(Category). |
Header
| Offset | Size | Name | Meaning |
|---|---|---|---|
| 0 | 4 | magic | 0x48415348, the letters HASH read as a 32-bit number; also shows the byte order. |
| 4 | 2 | version | 1. |
| 6 | 2 | hash_function | 0, the DJB hash (the only value). |
| 8 | 4 | bucket_count | Number of buckets. |
| 12 | 4 | hashes_count | Number of distinct hash values, and of offsets. |
| 16 | 4 | header_data_len | Size in bytes of the header data that follows. |
| 20 | 4 | die_offset_base | Added to atoms whose form is DW_FORM_ref1, ref2, ref4, ref8 or ref_udata. |
| 24 | 4 | atom_count | Number of atoms. |
| 28 | 4 each | atoms | For each atom, a 16-bit type and a 16-bit DWARF form (DW_FORM_*) saying how that value is stored in the data. |
Atom types
| Value | Name | Meaning |
|---|---|---|
| 0 | DW_ATOM_null | Ends a list of atoms. |
| 1 | DW_ATOM_die_offset | Offset of the DIE in __debug_info. |
| 2 | DW_ATOM_cu_offset | Offset of the compile unit header that holds the DIE. |
| 3 | DW_ATOM_die_tag | The DIE’s DW_TAG_* value. |
| 4 | DW_ATOM_type_flags | Flags for a type (below). |
| 5 | DW_ATOM_type_type_flags | A dsymutil extension: further type flags. |
| 6 | DW_ATOM_qual_name_hash | A dsymutil extension: a qualified-name hash. |
The one type flag defined is DW_FLAG_type_implementation (2):
always set for C++ types, and set for an Objective-C class only on its
@implementation.
The atoms LLVM writes: __apple_names, __apple_namespac and
__apple_objc have one atom, DW_ATOM_die_offset as
DW_FORM_data4; __apple_types has
DW_ATOM_die_offset (data4), DW_ATOM_die_tag
(data2) and DW_ATOM_type_flags (data1). LLVM’s
“static” type table, for DIEs known only by offset, has DW_ATOM_die_offset
(data4), DW_ATOM_die_tag (data2), atom 5
(data1) and atom 6 (data4).
Buckets, hashes, offsets and data
After the header data come four arrays, in this order:
| Array | Entries | Each | Meaning |
|---|---|---|---|
| buckets | bucket_count | 4 bytes | Index into hashes of the first hash in this bucket, or 0xFFFFFFFF for an empty bucket. |
| hashes | hashes_count | 4 bytes | The distinct 32-bit hash values, grouped by bucket (hash mod bucket_count). |
| offsets | hashes_count | 4 bytes | For each hash, the offset of its data. |
| data | – | variable | The entries for each hash (below). |
The data for one hash is a list of names that share that hash value (usually one):
| Size | Name | Meaning |
|---|---|---|
| 4 | str_offset | Offset of the name in __debug_str. 0 ends the list for this hash. |
| 4 | hash_data_count | How many DIEs have this name. |
| per atom | hash data | hash_data_count entries, each holding one value per atom in the header’s order and forms. |
To look up a name: hash it, take the hash mod bucket_count, read that bucket’s index into hashes, and walk forward while the hashes still fall in the same bucket. For each equal hash, follow its offset and compare the names at each str_offset until the 0 terminator.
The DJB hash
Daniel J. Bernstein’s string hash, on the name’s bytes, in 32-bit arithmetic:
start with 5381, and for each byte multiply by 33 ((h << 5) + h) and
add the byte.
h = 5381
'm' (0x6D): h = 5381 × 33 + 109 = 177682
'a' (0x61): h = 177682 × 33 + 97 = 5863603
'i' (0x69): h = 5863603 × 33 + 105 = 193499004
'n' (0x6E): h = 193499004 × 33 + 110 = 6385467242 → mod 2³² = 2090499946 = 0x7C9A7F6Amain, worked by hand from the formula. With 4 buckets it falls in bucket 0x7C9A7F6A mod 4 = 2.Sources
LLVM, Source Level
Debugging with LLVM, “Name Accelerator Tables” (header, header data, layout,
lookup, the contents of each table and the type tags). LLVM source:
BinaryFormat/Dwarf.h (DW_ATOM_* values,
DW_FLAG_type_implementation, DW_hash_function_djb),
CodeGen/AccelTable.h (the atoms of each table) and
Support/DJB.h (the hash). The LLVM document’s own enumeration of atom
types differs from the values LLVM writes; this page follows Dwarf.h.