-*-org-*-

(See http://pmachata.github.io/dwgrep/ for a full HTML documentation.)

Dwgrep is a tool and an associated language for querying Dwarf (debuginfo) graphs. If you want to find out more about Dwarf, you can check out the following links. But you can also pretend that Dwarf is like XML, except nodes are called DIE’s. That, and perusing the output of eu-readelf -winfo, should be enough to get you started.

http://www.dwarfstd.org/doc/Debugging%20using%20DWARF.pdf http://dwarfstd.org/Download.php

You can think of dwgrep expressions as instructions describing a path through a graph, with assertions about the type of nodes along the way: that a node is of given type, that it has a given attribute, etc. There are also means of expressing sub-conditions, i.e. assertions that a given node is acceptable if a separate expression matches (or doesn’t match) a different path through the graph.

Apart from Dwarf objects (DIE’s and Attributes), dwgrep expressions can work with integers, strings, and sequences of other objects.

In particular, a simple expression in dwgrep might look like this:

entry ?DW_TAG_subprogram child ?DW_TAG_formal_parameter @DW_AT_name

On a command line, you would issue it like this:

dwgrep /some/file/somewhere -e 'entry ?DW_TAG_subprogram ...etc....'

The query itself (ignoring the initial colon that’s part of meta-syntax) says: show me values of attribute DW_AT_name of DW_TAG_formal_parameter nodes that are children of DW_TAG_subprogram entries (which here means debug information entries, or DIE’s). Reading forward, you get list of instructions to a matcher: take DIE’s, accept all DW_TAG_subprogram’s, look at their children, accept those that are DW_TAG_formal_parameter, take value of attribute DW_AT_name.

Another example comes from dwarflint:

entry ?DW_AT_decl_column !DW_AT_decl_line

… which looks for DIE’s that have DW_AT_decl_column, but don’t have DW_AT_decl_line–a semantic violation that is worth reporting.

• elem, relem, length – container-like access
• child, parent – vertical tree access
• next, prev – horizontal tree access
• root – access to root tree element
• high, low – boundaries
• label – node denotation (attribute code, DIE tag, …)
• abbrev – access to abbreviation(s)
• attribute – access to attribute(s)
• form – attribute form (a DW_FORM_* constant)
• name – string associated with entity (file name, symbol name)
• offset – constant describing where in the file the object is defined
• address – address(es) of where in user space the object is defined
• merge – re-establish logical view of the whole
• entry – access to entries of a unit
• unit – access to unit

• Pops a file name, opens an ELF with that name, and pushes a value representing that file to TOS.
• When files are passed on command line, those are pre-opened and pre-pushed by the query driver, and appear as sole value on runtime stack:

  $ dwgrep ./a.out -e 'type'
  T_DWARF
      

• Yields all DIE’s in a .debug_info section.

entry ?root unit

• Yields all abbreviation units in a .debug_abbrev section.

• Yields all symbols in .symtab, or minisymtab, or .dynsym.

• Produce an abbreviation unit associated with this CU.

root child*	# except in the right order

• Produce a CU DIE of a CU.

Yields DIE tag.

Like dwarf_dieoffset.

• Selects unit that this DIE comes from.

attribute ?AT_highpc address

@AT_lowpc

Like dwarf_ranges.

Yields children of the DIE.

Yields attributes of the DIE.

Yields the parent of the DIE, if there’s any.

XXX DW_TAG_partial_unit

root := {parent* !(parent)};

?root holds if the DIE is a root node. Equivalent to !(parent).

parent* ?root        # finds a root node of node on TOS

Like dwarf_siblingof, returns next sibling of the DIE.

def next {|D| D parent child (pos == D parent child (== D) pos 1 add)}

The first line is necessary to make sure that pos later refers to order in children array, not to e.g. a result of ([XYZ] each).

The opposite of next.

let merge := { ?DW_TAG_imported_unit @AT_import child+ };

A typical use would then be:

entry merge*		# if you want to see deref'd DIE's
entry merge* !(merge)	# if you care about the actual tree

XXX But that is fairly impractical, as one would have to use such operation after each DIE traversal (in particular after every (child) traversal). You actually rarely need the (entry merge*) thing above, because it already is the case that (entry) visits everyone. If you need anything at all, it is more likely to be:

entry !(merge)

… so that you filter out partial unit headers.

A better approach could be to have two types for DIE-related elements–raw and cooked DIE’s, raw and cooked CU’s, etc. Raw values don’t do attribute integration, don’t inline imported units and present attribute values as offsets instead of the referenced thing. Words (cooked) and (raw) switch between the two types. The default types would be “cooked”.

It’s not clear yet whether attributes that even raw DIE’s yield shouldn’t be cooked implicitly, as things like getting string or DIE offset instead of the thing itself seem rarely useful.Dwarf’s.

Cooked DIE’s will also have to keep track of the original DIE where the partial unit import took place, so that when you ask for (parent), you travel back to where you came from without trouble, as if the whole thing were one monolithic unit.

(unit) on cooked Dwarf would skip partial units. (entry) would descend through CU’s and include partial units this way, so that the logical tree is presented in its whole, and parent/child paths are preserved.

Value of this attribute is represented as actual string including path.

(XXX we ignore mtime and size. Those aren’t stored anyway, but maybe it would be useful to have them so that one can do this sort of querying in the first place–do we have any files where this is stored? Or after it gets to be stored in general, where this is not stored?)

Yield abbreviation associated with this DIE.

@AT_name

Syntactic sugar for (attribute ?(label == AT_*) value).

Holds if DIE has this attribute.

Holds if DIE has this tag.

Holds if (@AT_language == DW_LANG_*).

Holds if @AT_encoding == DW_ATE_*.

abbrev ?haschildren

Note that to find out whether a DIE actually does have children, one asks simply ?(child).

Yield an attribute name.

Yields value(s) of attribute on TOS.

Some attributes refer to a location expression. These are represented as a number of nodes of type T_LOCLIST_ELEM. Children of these nodes are T_LOCLIST_OP, individual operations of location expression.

• For DW_AT_high_pc, DW_AT_entry_pc with constant forms, this converts the value to address.
• For attributes with address form, this is like calling “value”.
• Otherwise it is an error to use this.

Yield a form of an attribute.

• Yield a DIE that this attribute is associated with.

die unit

Holds if it is this attribute.

Holds if the attribute has this form.

Holds if (?AT_language value == DW_LANG_*).

Holds if (?AT_encoding value == DW_ATE_*)

• Yield offset of this abbreviation unit.

• Yield abbreviations defined in this unit. XXX this is currently done by elem.

• Yields all abbreviation attributes.

• Yields abbreviation code.

• Yield an abbreviation unit that this abbreviation comes from.

Holds if abbreviation has this tag.

Holds if abbreviation has this attribute.

• Holds for abbreviations that form child-ful DIE’s.

Yields attribute name.

Yields offset of attribute within abbreviation.

Yields attribute form.

Holds if it is this attribute.

Holds if the attribute has this form.

Yields symbol type, such as STT_FUNC.

Yield symbol value.

XXX or maybe @section?

This find a symbol associated with an address on TOS. The match doesn’t have to be exact, offset would then be:

let A := some addr; A symbol dup address A sub
 # now TOS has offset and below TOS is symbol

XXX some of this is fairly easy to get by cross-matching like this:

symtab (address == some addr)

fuzzy matching (getting symbol/offset) would be more involved.

Yields where given location expression applies.

Yields individual location expression operators.

Like elem, but yields in opposite direction.

Holds if this location expression contains an operation with this opcode.

Yields operation opcode (a DW_OP_* constant).

Yields an offset of this op within the location expression.

Yields operands associated with this location expression operation. Operands have anywhere between zero and two operands of various types (some are e.g. T_DIE references).

For example:

[4e] variable
     [...]
     location (exprloc) [0x0..0xffffffffffffffff, [0:fbreg<-18>]]

Here we have only one T_LOCLIST_OP, and that has an offset of 0, a label of DW_OP_fbreg, and yields one value, -18.

Holds if this is an operation with this opcode.

• For holding a set of addresses.

• Extract continuous subranges of this aset and present them as individual asets.

Highest address set in this aset. Doesn’t yield at all if an aset is empty.

Lowest address set in this aset. Doesn’t yield at all if an aset is empty.

[|A| address] length

!(elem)

• Holds if there is at least one value common to both osets.

?(|A C| A elem (|E| (C >= E low) (C <= E high)))

• Holds if the lower aset contains all addresses of the TOS aset.

!(address !contains)

Compute aset that contains addresses common to both asets. Produces an empty aset if there’s no overlap.

• Actually enumerates all addresses in a range. Potentially a very bad idea for ranges that cover whole address space.

[|A| A elem] relem

• A value representing .debug_macro and .debug_macinfo units. Might be useful for DW_MACRO_GNU_transparent_include opcode, and for DW_AT_macro_info and DW_AT_GNU_macros attributes, which would hold this as a value.

• A value used for representing both .debug_macro and .debug_macinfo entries. Domain of entry label disambiguates which is which.

• Opcode of this macro entry.

• Yields value(s) associated with this opcode.
• XXX could we somehow query a form?

let merge := { ?DW_MACRO_GNU_transparent_include value };

Should be used as with DIE’s, depending on what exactly is needed either (merge*) or (merge* !(merge)).

• Should this resemble DIE’s or T_LOCLIST_OP’s? Shouldn’t T_LOCLIST_OP’s actually resemble DIE’s as well? @X as a shorthand for (value (pos == X)) seems fairly natural.

  If X is a name instead of a number, it means:

  (attribute (label == X))
      

• Note that label is explicitly not applicable

let A := entry ?TAG_subprogram !AT_declaration
         ?(@AT_decl_file (=~ "^/usr/") (!~ "^/usr/src/debug"));

:

let B := A child ?TAG_formal_parameter
         ?(@AT_type ((?TAG_const_type, ?TAG_volatile_type, ?TAG_typedef)
           @AT_type)* (?TAG_structure_type, ?TAG_class_type));

:

"%( A @AT_decl_file %): %( A @AT_decl_line %): note: in function "\
"`%( A @AT_name %)', parameter `%( B @AT_name %)' type is not trivial"

(entry ?AT_decl_column !AT_decl_line "%s has decl_column, but NOT decl_line"
, etc.)

let A := entry (?TAG_subprogram, ?TAG_inlined_subroutine, ?TAG_entry_point,
               ?TAG_lexical_block, ?TAG_label, ?TAG_with_stmt,
               ?TAG_try_block, ?TAG_catch_block);
let B := A (@AT_entry_pc, address);
let C := A root address;
?(B C !overlaps || B C overlap != B)
"Address range %( B %) referenced from %( A %)"\
" not fully covered by line table."

entry !AT_frame_base (@AT_location elem label == DW_OP_fbreg)

entry ?(@AT_location elem label
        (== DW_OP_bregx || (>= DW_OP_reg0) (<= DW_OP_regx)))

entry ?(@AT_location elem label "%s" "_b?reg" ?find)

entry ?(@AT_location elem label (?OP_deref, ?OP_xderef, ?OP_deref_size,
                                 ?OP_xderef_size, ?OP_GNU_deref_type))

entry ?(@AT_location elem label "%s" "deref" ?find)

entry (@AT_low_pc == 0) ?(@AT_frame_base ?OP_call_frame_cfa)

entry ?(@AT_location !(elem))

entry ?([@AT_location] relem (pos == 0) label
        (?DW_OP_implicit_value, ?DW_OP_stack_value))

• http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43053

  let A := entry ?TAG_subprogram;
  let B := A child ?TAG_formal_parameter;
  let C := A @AT_specification child ?TAG_formal_parameter;
  (B pos == C pos) (B @AT_type != C @AT_type) A
      

• http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56740

  # Leaves on stack two DIE's that describe the same type.
  let A := entry (?TAG_const_type||?TAG_volatile_type||?TAG_restrict_type);
  A root child* (> A) (label == A label) (@AT_type == A @AT_type) A
      

attribute (value == "blah")

Check for two full DW_TAG_variable DIEs with the same DW_AT_name value.

entry ?TAG_variable (@AT_name == next+ ?TAG_variable @AT_name)

(|Dw|
 let GetSym := {|X| Dw symtab (?STT_OBJECT, ?STT_FUNC)
                    (@name == X @AT_linkage_name)};
 Dw entry ?AT_linkage_name
 if !(GetSym) then (
     !AT_declaration !AT_const_value
     (!structure_type !enumeration_type !union_type, ?AT_name)
     "%s has linkage_name attribute that's not in symtab, "\
     "but is not marked as declaration"
 ) else if (GetSym ?STB_LOCAL) then (
     !AT_declaration ?AT_external
     "%s has linkage_name attribute, "\
     "but the corresponding symbol is local"
 ) else (
     !AT_external
     "%s has linkage_name attribute, but no external attribute"
 ))

This is still 1:10 vs. dwarflint C++ (i.e., say 1:20 if we had to explore the DIE tree by hand), but fairly involved.

The interpreter would need to notice the ?symbol nodes are used as a sort of global variable for cross-referencing, otherwise this would lead to an ugly combinatorial explosion of states. Noticing that we look at the bottom slot and cross-reference @AT_name with @AT_linkage_name should be possible.

An alternative start would be something like:

let Dw := $1 dwopen;

let imports := {root child ?TAG_imported_unit @AT_import};

:

let U := entry ?root ;
let A := U child ?TAG_imported_unit @AT_import ;
let B := U child ?TAG_imported_unit @AT_import (> A) ;
A imports B imports (== swap)
"PU %(offset%) is imported by PU's %(A offset%) and %(B offset%), "\
"which are both imported by %(U offset%)."

• dsmith asked for a way to get typedef “resolution” from DWARF (for use with the syscall types in the kernel). Which was timely since I was just thinking about having some “roundtripping” tests for GCC/elfutils DWARF types. So hacked up a dwfltypedef that prints all (C) typedefs found:

  $ ./dwfltypedef -e ./dwfltypedef [2d] typedef size_t long unsigned int (unsigned, 8 bytes); [70] typedef __off_t long int (signed, 8 bytes); [7b] typedef __off64_t long int (signed, 8 bytes); […]

  let T := entry ?TAG_typedef ;
  let U := T @AT_type (?TAG_typedef @AT_type)* !TAG_typedef ;
  "[%(T offset%)] typedef %(T @AT_name%) %(U @AT_name%) "\
  "(%( U @AT_encoding || "???" %), %( U @AT_byte_size || "???" %) bytes)"
      

  [0x57] typedef __int32_t int (DW_ATE_signed, 4 bytes) [0x70] typedef __off_t long int (DW_ATE_signed, 8 bytes) [0x7b] typedef __off64_t long int (DW_ATE_signed, 8 bytes) [0x9c] typedef __intptr_t long int (DW_ATE_signed, 8 bytes) [0xa7] typedef size_t long unsigned int (DW_ATE_unsigned, 8 bytes) […]

(@AT_name == "a") child (@AT_name == "b") child (@AT_name == "c")