Re: [PATCH] libdw: Make dwarf_getfuncs find all (defining) DW_TAG_subprogram DIEs.

[Mark Wielaard <mjw at redhat dot com>]

On Thu, 2013-09-19 at 18:42 -0700, Josh Stone wrote:
> On 09/18/2013 06:33 AM, Mark Wielaard wrote:
> > dwarf_getfuncs used to return only the DW_TAG_subprogram DIEs that were
> > direct children of the given CU. This is normally how GCC outputs the
> > subprogram DIEs. But not always. For nested functions the subprogram DIE
> > is placed under the subprogram DIE where it is nested. Other compilers
> > might output the defining subprogram DIE of a C++ class function under
> > the DW_TAG_namespace DIE where it was defined. Both such constructs seem
> > allowed by the DWARF specification. So just searching the CU DIE children
> > was wrong.
> > 
> > To find all (defining) subprogram DIEs in a CU dwarf_getfuncs should
> > use __libdw_visit_scopes to walk the tree. The only tricky part is
> > making sure the offset returned and used when the callback returns
> > DWARF_CB_ABORT is correct and the search continues at the right spot
> > in the CU DIE tree.
> 
> As one might expect, deeper iteration ends up quite a bit slower, but we
> may have to pay that price for correctness.

Yes, I agree, especially with imported/partial units we would miss to
return correct results. It is a little slower, but normally this would
be a one-time call.

> We have full DIE walks in a few
> different contexts, and I figured that if dwarf_getfuncs is now going to
> be more expensive, maybe I could instead just consolidate our own full
> DIE walks and cache multiple things at once.

I had been pondering exposing a public DIE tree walk function, since
there are some tricky corner cases to take care of. If you have a
particular need/design it would be interesting to compare notes. Would
something like the __libdw_visit_scopes interface be generic enough?

> And now that I've laid that out, I think I know why it's missed.  Your
> new tree_visitor is filtering out (die_offset < offset), in an attempt
> to make the dwarf_getfuncs offset parameter work to resume.  This can
> fail with partial_units, because the DIE offsets as they are traversed
> are not necessarily ordered anymore.

Nice catch.

> Resuming is still going to be problematic with a less-than comparison.
> I think rather it needs to iterate until the exact requested offset is
> found, without assuming any order.  Unless offset==0, of course, then
> just start at the beginning.
> 
> I think this also means that you can't prune out whole subtrees, since
> you don't know whether that offset could be found within, via an import.

Indeed, the resume capability is what makes this tricky, if we want to
optimize for that case. Now that you showed the issue with partial unit
ordering, it is obvious to see that it isn't possible. So when we are
resuming we need to walk everything every time. That is a pity. But in
practice I haven't seen any program ever use this functionality of
dwarf_getfuncs. I guess we just have to document that resuming really
isn't recommended, because it cannot be done efficiently. Other tree
query functions don't have this capability to begin with.

>  And if a tree happens to be imported multiple times (can it?), then
> resuming on an offset within that is ambiguous -- oh well.

It can indeed. But in this particular case it won't happen because you
can not have two defining subprogram declarations in the same CU.

Thanks,

Mark