Hi,
I finally fully implemented the dwarf_output hashing algorithm, with a local hash that depends only on non-reference attributes and the local hash of the children of a die, and a reference hash that depends on the local hashes of all reference attributes (recursively) of the die.
This does reduce the number of attr_set hash collisions a lot. Unfortunately there are circular reference chains for some larger c++ programs. That was unexpected. Here is an example running dwarfcmp-test on itself:
$ src/dwarfcmp-test -T src/dwarfcmp-test src/dwarfcmp-test Reference chain cycle detected offset=[0x2898c8] already on the reference chain stack offset=[0x2889cb] subprogram offset=[0x2959bd] reference_type offset=[0x289b7c] structure_type offset=[0x2898c8] structure_type Aborted (core dumped)
And offset=[0x2898c8] is:
<structure_type offset=[0x2898c8] specification=[0x28889b] byte_size=0x8 decl_file="...libdw/c++/dwarf_data" decl_line=761 containing_type=[0x2898c8]>
Is this valid dwarf? Can a structure_type have a containing_type? A strict reading of the dwarf4 spec seems to imply only a DW_TAG_ptr_to_member_type may have a DW_AT_containing_type.
Not yet sure how to handle this case. The original algorithm depended on the reference chain not being cyclic on its own (when ignoring children). Obviously that isn't true in at least this case.
Code, plus cycle detection is on mjw/dwarf_output branch.
Cheers,
Mark
On Mon, 2011-02-21 at 15:23 +0100, Mark Wielaard wrote:
Unfortunately there are circular reference chains for some larger c++ programs. That was unexpected. Here is an example running dwarfcmp-test on itself:
$ src/dwarfcmp-test -T src/dwarfcmp-test src/dwarfcmp-test Reference chain cycle detected offset=[0x2898c8] already on the reference chain stack offset=[0x2889cb] subprogram offset=[0x2959bd] reference_type offset=[0x289b7c] structure_type offset=[0x2898c8] structure_type Aborted (core dumped)
And offset=[0x2898c8] is:
<structure_type offset=[0x2898c8] specification=[0x28889b] byte_size=0x8 decl_file="...libdw/c++/dwarf_data" decl_line=761 containing_type=[0x2898c8]>
Is this valid dwarf? Can a structure_type have a containing_type? A strict reading of the dwarf4 spec seems to imply only a DW_TAG_ptr_to_member_type may have a DW_AT_containing_type.
For reference, this is the top of reference chain leading to this self-referential containing_type:
<subprogram offset=[0x2889cb] external=1 name="variant<elfutils::dwarf_data::value<elfutils::dwarf_edit, true>::value_flag>" decl_file="/home/mark/src/elfutils/libdw/c++/dwarf_data" decl_line=779 MIPS_linkage_name="<...some_giant_string...>" type=[0x2959bd] declaration=1>
<reference_type offset=[0x2959bd] byte_size=0x8 type=[0x289b7c]/>
<structure_type offset=[0x289b7c] specification=[0x2888bf] byte_size=0x10 decl_file="/home/mark/src/elfutils/libdw/c++/dwarf_data" decl_line=882 containing_type=[0x2898c8]>
"Mark" == Mark Wielaard mjw@redhat.com writes:
Mark> <structure_type offset=[0x2898c8] Mark> specification=[0x28889b] Mark> byte_size=0x8 Mark> decl_file="...libdw/c++/dwarf_data" decl_line=761 Mark> containing_type=[0x2898c8]>
Mark> Is this valid dwarf? Can a structure_type have a containing_type? A Mark> strict reading of the dwarf4 spec seems to imply only a Mark> DW_TAG_ptr_to_member_type may have a DW_AT_containing_type.
If only DWARF actually specified that anything at all was invalid.
One thing to know is that GCC does not properly emit DW_TAG_ptr_to_member_type. Instead it emits a structure type that the consumer must know is "really" a pointer to member.
See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28767
Tom
One thing to know is that GCC does not properly emit DW_TAG_ptr_to_member_type. Instead it emits a structure type that the consumer must know is "really" a pointer to member.
This does not explain the case we're seeing.
On Mon, 2011-02-21 at 15:23 +0100, Mark Wielaard wrote:
Not yet sure how to handle this case. The original algorithm depended on the reference chain not being cyclic on its own (when ignoring children). Obviously that isn't true in at least this case.
Code, plus cycle detection is on mjw/dwarf_output branch.
I added a special case/workaround for self-referential DW_AT_containing_type attributes (commit 0a1e1b on mjw/dwarf_output branch). And that seems to "solve" the issue. At least there are no other reference chain cycles in the make check self tests. So for now I hope to just continue with the current algorithm setup and regard this one as just a weird case that shouldn't happen.
I do see dwarfcmp-test failures and crashes though. These might indicate that dwarf_output is creating bogus trees (or at least ones that dwarfcmp cannot proof equal to the original). Looking into that.
Cheers,
Mark
It certainly merits investigation on the GCC side to see if this data is coming out as it ought to. Butk, we have to cope with the data as it exists, even bad old data from buggy old compilers.
So far the only violation of our assumption for the algorithm design is this case of direct self-reference. That is far simpler to handle than the general case of circular chains of references. For hashing purposes, we can treat a direct self reference as hashing to zero. If we come across cases of indirect circularity in the data, then we'll have to reconsider more fully. But this alone doesn't seem like it fouls our plans.
Thanks, Roland
elfutils-devel@lists.fedorahosted.org
-
Mark Wielaard -
Roland McGrath -
Tom Tromey