Cached random access to CUs and DIEs (#264)
authorMilton D. Miller II <miltonm@us.ibm.com>
Wed, 22 Apr 2020 12:57:32 +0000 (12:57 +0000)
committerGitHub <noreply@github.com>
Wed, 22 Apr 2020 12:57:32 +0000 (05:57 -0700)
commit519a234fc1316ac0e9e5628b34308f0d47995f71
tree504d6a36c037ccac8c7b2d0549a166e5852a22be
parentea81c3edb2c9de7db2cc0b86ab11b40799f9a3c1
Cached random access to CUs and DIEs (#264)

* dwarf/compileunit: Lookup DIE from a reference

Accept a resolved reference address for a DIE in a compile unit and
parse the DIE at that location.  Insert into the _diemap / _dielist
cache shared with iter_DIE_children() for fast repeated lookups.

This can be used to follow attribute references to a DIE that be
referenced several times (eg for a DW_AT_type reference) or find
a DIE referenced in a lookup table.

* dwarf/dwarfinfo: Cache CUs, direct parse or search from known units

Maintain a cache of compile units parsed and a map of their offsets
similar to the one mainained of DIEs by compile units.

Add the ability to parse a random compile unit when the offset of
the compile unit header is known.

Add the ability to search for a compile unit containing (spanning)
a given refaddr, such as that obtained from a DIE reference class
attribute, starting from the closest previous cached compile unit.

* dwarf/die: search for parents on demand

Add a function to set the _parent link of known chldren, iterating
down each parent of a target DIE.  Walk all children of a given
parent and set each child's ._parent to avoid O(n^2) walking.

A future commit will add other methods to instatiate a DIE that will
not set the _parent link as the DIE is instantiated.

This walk uses the knowledge that in a flattened tree a parents offset
will always be less than the childs.

The call to die.set_parent in compile_unit iter_DIE_children could be
removed to make the method private,, but it is free to set starting
from the top DIE.  Alternativly make it an optional argument to
DIE creation.

* dwarf/dwarfinfo: APIs to lookup DIEs

Add APIs to lookup a DIE from: (a) a DIE reference class attribute
taking into account the attribute form, (b) from a lookup table entry
(NameLUTEntry) from a .pub_types or .pub_names section, or (c) directly
from a reference addresss (.debug_info offset) regardless of how it
was obtained.

Add a test that will lookup dies from pubnames and follow die by ref.

This is a simple test that exercises the new cache lookup
methods and provides a starting point on how to determine a
variables type.

For now raise NotImplemented exception for type signature lookup
and supplemental dwarf object files.
elftools/dwarf/compileunit.py
elftools/dwarf/die.py
elftools/dwarf/dwarfinfo.py
test/test_dwarf_cu_and_die_cache.py [new file with mode: 0644]