Cached random access to CUs and DIEs #264

mdmillerii · 2020-01-23T01:30:51Z

Here is a series that refactors the DIE cache to cache entries without walking from the top of a CU,
and also one that adds a similar cache to the CU lookup in the DWARFInfo.

mdmillerii · 2020-01-23T01:45:28Z

I've been working on this for a few weeks now, developing a test to locate static variables. I've been testing using a full Linux kernel build so testing a few is useful.

This part has been refactored enough that I'm comfortable pushing it; the bigger script still needs a few rounds.

This addresses #262 so I've put some efffort into getting this commented and pushed. I just added the LUTEntry object today.

eliben · 2020-02-04T14:14:39Z

Thanks for the contribution. Do you think it would be possible to split this PR into two? One fir DIE cache and one for CU cache?

@sevaa would you like to help review this, since it addresses #262?

sevaa · 2020-02-04T18:30:06Z

_get_cached_DIE assumes that the _diemap of a CU already has at least one entry. get_DIE_from_refaddr eventually calls _get_cached_DIE for the target CU.

I'm dealing with cases of both intra-CU and cross-CU references (Xcode loves the latter). If one tries to follow the reference to another CU where not a single DIE has been parsed/cached so far, will that work? Please test the scenario.

If it works as it is, remove the misleading comment please :)

Note that self._diemap cannot be empty because a die, the argument,
is already parsed.

mdmillerii · 2020-02-04T22:19:40Z

@sevaa does a4fb515 address your concern?

I left this as two commits to show the code motion for review but will squash as requested by Eli.

sevaa · 2020-02-05T02:20:43Z

It does.

mdmillerii · 2020-02-06T04:02:36Z

Do you think it would be possible to split this PR into two? One fir DIE cache and one for CU cache?

I initially read this as can I factor this into two commits, but then I realized you asked for multiple PRs.
It would take at least 3 to get back to this state:

The first two commits (the get_parent and the DIE by ref within a CU) can be squashed.
CU caching is the third commmit
The DIE API helpers and the testcase can be squashed.

Based on your request I squashed DIE cache cleanup (which was always just showing my work but caused review noise), and consolidated the find a DIE pieces into a helpers commit.

Review note: github seems to show the commits by authored date instead of parent order so the test case is appearing before the API helpers in the GUI.

eliben · 2020-03-06T14:22:25Z

@rhelmot @rupran @woodruffw pinging some folks who've been active recently -- since this is a large change, I'd really appreciate some help with reviewing :-) My review queue for pycparser has grown rather long.

eliben · 2020-03-06T14:25:56Z

@mdmillerii do you have some measurements / benchmark numbers to report? What kind of operations does this make faster, and how much faster?

Note to self: we really need some portfolio of files for performance measurements

woodruffw · 2020-03-06T15:33:11Z

I can review (and test) here in a bit, thanks for the ping!

eliben · 2020-03-07T13:46:32Z

I can review (and test) here in a bit, thanks for the ping!

Thanks! I'll assign you, just unassign when you're done

woodruffw · 2020-03-09T19:30:48Z

elftools/dwarf/dwarfinfo.py

@@ -112,6 +117,84 @@ def has_debug_info(self):
        """
        return bool(self.debug_info_sec)

+    def get_DIE_from_lute(self, lutentry):


Nit: Maybe rename to either get_DIE_from_lut or get_DIE_from_lut_entry?

@eliben want me to fix this up and rebase? (I'd choose lut_entry) .. then I can rebase @265 on top

lut_entry SGTM

woodruffw

This looks pretty good to me! I left one (style) nit, and am currently testing this against a big suite of internal projects to see if it breaks anything.

woodruffw · 2020-03-09T20:28:33Z

Confirmed that this works with my internal tooling. I'll do some additional performance testing.

eliben · 2020-03-09T23:14:14Z

@woodruffw out of curiosity, what is this big suite of projects you have? Do you have a setup to analyze many different ELF binaries with pyelftools?

rupran · 2020-03-10T08:01:23Z

elftools/dwarf/die.py

+        """ Search for our parent by, starting with the CU top die,
+            setting the _parent link of each child and then iterating on
+            the child which was closest to object DIE offset without over,
+            whithan to the object DIE offset, which is an ancestor.


This sentence does not make sense to me, maybe reword or split the sentence in two parts.

yes, that was trying to stuff everything into a sentence and it got lost.

eliben

Looks good overall. I left some minor comments. Feel free to fix these and the comments made by others (thanks for the reviews!), and rebase.

eliben · 2020-03-10T12:37:44Z

elftools/dwarf/compileunit.py

+            self.cu_die_offset <= refaddr < self.cu_offset + self.size,
+            'refaddr %s not in DIE range of CU %s' % (refaddr, self.cu_offset))
+
+        die = self._get_cached_DIE(refaddr)


Maybe just return this directly without the die = intermediate?

eliben · 2020-03-10T12:40:04Z

elftools/dwarf/die.py

+        search = self.cu.get_top_DIE()
+
+        while search.offset < self.offset:
+


Nit: remove this empty line

eliben · 2020-03-10T12:40:36Z

elftools/dwarf/die.py

+
+            search = prev
+
+        pass


Not sure what's going on here. pass outside the loop?

Should this line be removed?

Also the commented code following it

refactoring remenants, fixed.

eliben · 2020-03-10T12:41:41Z

elftools/dwarf/dwarfinfo.py

@@ -112,6 +117,84 @@ def has_debug_info(self):
        """
        return bool(self.debug_info_sec)

+    def get_DIE_from_lute(self, lutentry):


lut_entry SGTM

eliben · 2020-03-10T12:42:43Z

elftools/dwarf/dwarfinfo.py

@@ -253,23 +336,41 @@ def range_lists(self):

    #------ PRIVATE ------#

-    def _parse_CUs_iter(self):
+    def _parse_CUs_iter(self, offset=0):


Document what offset means

eliben · 2020-03-10T12:43:37Z

elftools/dwarf/dwarfinfo.py

+            See get_CU_at().
+        """
+        # If the insert point is 0 the entry does not match (perhaps the cache
+        # is empty).  Otherwise on a miss parse and insert.


I'm not sure I understand what the second sentence in this comment means. Please rephrase.

it was saying if the first sentence was false, then do the actions. Hopefully the new is clearer,

eliben · 2020-03-10T12:43:57Z

test/test_dwarf_cu_and_die_cache.py

+            for (k, v) in pt.items():
+                ndie = dwarf.get_DIE_from_lute(v)
+                self.dprint(ndie)
+                # if not ndie.tag == 'DW_TAG_variable':


woodruffw · 2020-03-10T14:12:57Z

out of curiosity, what is this big suite of projects you have? Do you have a setup to analyze many different ELF binaries with pyelftools?

Sorry for the ambiguity there: it's both a big suite of projects (i.e. test binaries) and tools that use pyelftools (as a dependency) to extract information from those binaries.

There's nothing publicly available at the moment, but it's all part of the DARPA CHESS program.

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.

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.

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.

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.

This commit addresses the review comments in eliben#264 showing the changes to the prior submission after rebasing before folding them into the prior commits.

mdmillerii · 2020-04-09T05:33:00Z

Here's my update. I also pushed a branch random-die-review that shows the previous content rebased then 1 patch reverted so reviewers can see what was changed, specifically on a5d42a4

mdmillerii mentioned this pull request Jan 23, 2020

dwarf .debug_types and .debug_macros #265

Closed

mdmillerii force-pushed the random-die branch from 38e210e to f8892cb Compare February 6, 2020 03:48

mdmillerii mentioned this pull request Feb 6, 2020

for sibling of form ref_addr, only sibling value should be used #268

Merged

sevaa mentioned this pull request Feb 11, 2020

Get memory address of C++ class members #280

Open

eliben assigned woodruffw Mar 7, 2020

woodruffw reviewed Mar 9, 2020

View reviewed changes

rupran reviewed Mar 10, 2020

View reviewed changes

eliben reviewed Mar 10, 2020

View reviewed changes

eliben assigned mdmillerii and unassigned woodruffw Mar 10, 2020

mdmillerii added 4 commits April 3, 2020 00:03

mdmillerii force-pushed the random-die branch from f8892cb to 73f603e Compare April 9, 2020 05:13

mdmillerii mentioned this pull request Apr 9, 2020

A few additonal changes #307

Closed

mdmillerii mentioned this pull request Apr 22, 2020

CompileUnit: Track DIEs by offset #113

Closed

eliben approved these changes Apr 22, 2020

View reviewed changes

eliben merged commit 519a234 into eliben:master Apr 22, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Cached random access to CUs and DIEs #264

Cached random access to CUs and DIEs #264

mdmillerii commented Jan 23, 2020

mdmillerii commented Jan 23, 2020

eliben commented Feb 4, 2020

sevaa commented Feb 4, 2020 •

edited

mdmillerii commented Feb 4, 2020

sevaa commented Feb 5, 2020

mdmillerii commented Feb 6, 2020 •

edited

eliben commented Mar 6, 2020

eliben commented Mar 6, 2020

woodruffw commented Mar 6, 2020

eliben commented Mar 7, 2020

woodruffw Mar 9, 2020

mdmillerii Mar 10, 2020

eliben Mar 10, 2020

woodruffw left a comment

woodruffw commented Mar 9, 2020

eliben commented Mar 9, 2020

rupran Mar 10, 2020

mdmillerii Apr 9, 2020

eliben left a comment •

edited

eliben Mar 10, 2020

mdmillerii Apr 9, 2020

eliben Mar 10, 2020

mdmillerii Apr 9, 2020

eliben Mar 10, 2020

mdmillerii Apr 9, 2020

eliben Mar 10, 2020

eliben Mar 10, 2020

eliben Mar 10, 2020

mdmillerii Apr 9, 2020

eliben Mar 10, 2020

woodruffw commented Mar 10, 2020 •

edited

mdmillerii commented Apr 9, 2020

		search = self.cu.get_top_DIE()

		while search.offset < self.offset:

Cached random access to CUs and DIEs #264

Cached random access to CUs and DIEs #264

Conversation

mdmillerii commented Jan 23, 2020

mdmillerii commented Jan 23, 2020

eliben commented Feb 4, 2020

sevaa commented Feb 4, 2020 • edited

mdmillerii commented Feb 4, 2020

sevaa commented Feb 5, 2020

mdmillerii commented Feb 6, 2020 • edited

eliben commented Mar 6, 2020

eliben commented Mar 6, 2020

woodruffw commented Mar 6, 2020

eliben commented Mar 7, 2020

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

woodruffw left a comment

Choose a reason for hiding this comment

woodruffw commented Mar 9, 2020

eliben commented Mar 9, 2020

Choose a reason for hiding this comment

Choose a reason for hiding this comment

eliben left a comment • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

woodruffw commented Mar 10, 2020 • edited

mdmillerii commented Apr 9, 2020

sevaa commented Feb 4, 2020 •

edited

mdmillerii commented Feb 6, 2020 •

edited

eliben left a comment •

edited

woodruffw commented Mar 10, 2020 •

edited