dwarf_output overview
by Roland McGrath
https://fedorahosted.org/elfutils/wiki/DwarfOutput is still accurate in its
basic description about the collector (class dwarf_output_collector).
We don't really need to get into right now why it's a separate object
from dwarf_output. For uses in the time being, we'll use one collector
with one dwarf_output for one input file.
The simple attribute values, and some bits of interface glue, are shared
via template use from dwarf_data, with dwarf_edit. The only difference is
that in dwarf_output we never have mutable versions of thse objects, only
const pointers/references to immutable copies sitting in the collector.
Whereas dwarf_edit has mutable containers, there is no modification you can
do to a dwarf_output object once it's created. Instead, like dwarf_edit
you can copy-construct a dwarf_output object from any dwarf-compatible
class (i.e. dwarf, dwarf_edit, or dwarf_output)--this is the only way to
get a nonempty dwarf_output object.
The dwarf_output constructor takes two arguments, unlike the simple
dwarf_edit constructor. The second argument is the collector object.
This actually uses a second helper object, whose only purpose is to live as
long as copy construction is going on. That's dwarf_output::copier, which
is actually dwarf_output::copier<input> parameterized by the particular
top-level input type (dwarf or dwarf_edit). (This will one day be exposed
outside dwarf_output for some of the same cases where a separate collector
is really useful, but we won't get into that now.)
The copy construction is doing the whole file, or at least a whole CU, from
the root of the tree down to the leaves and all attribute values. The
copier holds some bookkeeping and some caches during that process.
The essential method is that the tree from the CU on down has its
debug_info_entry objects constructed recursively, with
debug_info_entry::attr_value objects being constructed for each node. Each
attr_value on up to each debug_info_entry is "constructed" by finding its
exact match stored in the collector, inserting it only if it's not already
there, and then returning the pointer (i.e. actually all C++ references) to
the (now) existing data structure.
The copier's part in this is twofold. First, there is some simple caching
related to copying the simple attribute values. (All the value types other
than references are "simple".) Second, there is all the hairy bookkeeping
for the complexity brought on by references.
The copier's caching is a simple optimization, so I'll describe it first.
This is for strings, identifier strings (which we distinguish from other
strings, though they are just strings in DWARF), and source files. In one
input file, even across many CUs (because of linker SHF_MERGE|SHF_STRINGS
merging), every DW_AT_name "foobar" will point to point to the same
"foobar" in the .debug_str table. Likewise, a dwarf::source_file object
that represents a source file from the .debug_line table is what we get for
every DW_AT_decl_file attribute on the input tree, but there will be many
DIEs with that attribute pointing to the same file entry (same index into
the CU's .debug_ling table, so getting the same dwarf::source_file again
and again). Hence, we expect to see the actual same pointer (in a dwarf
reader object, really the same pointer into the mmapped DWARF file data)
appearing many times in the input tree's attr_values. Matching pointers
you've seen before is quicker than matching string values you've seen
before. So the copier keeps maps keyed by these string (and file entry)
pointers into the input data, to find exact attr_value's already
found/created to match other instances of the same input string (or file
entry). (This sped things up a fair bit when I added it, though I don't
recall the details.)
For all the simple attribute values the method is simple. For each flavor
of attr_value, the collector holds a set of values seen before. The
subr::value_set container type is used for this. It's based on the STL
unordered_set, which is a hash table where we supply the key type and the
hash and comparison functions on that type. In these sets, our key types
are dwarf_output::value::value_*, which are the flavor-specific subtypes
that an attr_value actually points to. So, each of those types has to
provide an integer hash function (a "hasher" inner class) and a comparison
function (operator==).
The copier does a set insertion of the input value object, which installs a
new dwarf_output::value::value_foobar object if none matched, or doesn't if
one did, and then produces an attr_value that points to that. Note that
since this is the only way any dwarf_output::attr_value objects can ever
get created, within one dwarf_output object (really, one collector), simple
pointer equality is exactly correct as a semantic equality check for the
non-reference attribute values. A corollary is that just this pointer
value itself can be used as the hash value for the attr_value object (a
perfect hash function).
If there are no reference attributes to consider, then it proceeds from the
bottom up in the same straightforward way. That is, the entire map of
attributes (considered as a sequence of <int name, attr_value> pairs in a
canonical name-keyed order) can be hashed together to get a hash value for
the attributes container. Then a leaf node can combine the tag into the
that hash value to get a hash value for the whole DIE. Then, a sequence of
sibling leaf nodes' hash values are combined to form a hash value for the
whole children container. Then that hash value is combined with the tag
and the attribute map hash value to form a hash value for the whole DIE.
Then on up.
So this is what we do. The simple attribute values are hashed on the
actual values (string data, integer values, etc.), and then those pointer
values along with the attribute name (integers) in a canonical order are
combined with the DIE tag into a single integer hash. The _m_attr_sets set
(i.e. hash table) holds these <attribute map, tag integer> pairs. Then
children vectors, starting with the empty vector for leaf DIEs, are hashed
into the _m_broods set. (The empty vector has hash value zero.) Finally,
a dwarf_output::debug_info_entry just consists of pointers to the
attributes map and children vector, and the DIE tag integer. We just
combine those two pointer values and the tag to make the integer hash of
the debug_info_entry object itself. _m_unique holds the set of unique
debug_info_entry objects. So, a leaf DIE gets created with an attributes
map pointer and a pointer to the one and only empty children vector object.
Then a non-empty children vector is simply a vector of pointers to
debug_info_entry objects like that one. Like for the other sets, a pointer
to a particular debug_info_entry in the collector serves as a perfect
integer hash, since by definition pointer equality of the debug_info_entry
object exactly maps to semantic equivalence. So, the children vector is a
simple container of pointers, and the vector itself has a hash value made
just by combining the pointer values as so many constituent integer hash
values.
So, it's like that when no attribute values are references. The exact
control flow between the constructors of the dwarf_output inner classes and
dwarf_output::copier is extremely hairy. But the extreme template
weirdness is mostly just to get the copier pointer passed down the levels
of constructors to where it calls an add_* method on the copier. It's
there, and the collector methods they call, where the real work happens.
It's even like that when there are some references, for simple cases.
So, start with a completely simple leaf node:
<base_type name="int" byte_size=0x4 encoding=signed/>
That's all simple, so its attribute values, map, empty children vector,
debug_info_entry will all be hashed and inserted in the collector as above.
Now there is a known debug_info_entry pointer for that DIE.
Next, say you are copying:
<variable name="x" type="#int" location=.../>
The various simple attributes all resolve to known value pointers. The
type="#int" attribute is the only reference value, pointing to the DIE we
just mentioned. Since that's a fully resolved known DIE now, we can in
fact treat it the same way as we treat simple attribute values. Along with
the one debug_info_entry object in the collector, we only need to have
exactly one dwarf_output::value::value_reference object that points to it.
So here, that value object pointer is perfect hash and equality test for a
reference attribute that refers to a DIE identical to the "int" above, just
like the value object pointers for the simple value flavors are.
If that's all there were to do, it would be easy.
Of course, there are circular references.
So say we have:
<structure_type id="t1" name="list">
<member name="next" type="#p1"/>
</structure_type>
<pointer_type id="p1" type="#t1"/>
Now, the structure_type's own attribute map is simple, so that hashes up
nicely. But, the member's attribute map includes a circular reference.
So, what we do is still hash up the whole attribute map, but use zero as
the hash value for the reference value. Now <member/> as a whole has a
hash value that contributes to the children vector hash value, and that
contributes to the structure_type's overall hash value.
Two entries that look like this but have different references in the type
attribute--but both circular references in the overall graph--would have
the same hash value. So when comparing those, we'd get a hash collision
and have to do a full comparison. That would find the two attribute maps
identical, so look at the two children vectors. The corresponding member
entries' attribute maps would then be compared for equivalence, the
non-reference attribute values (i.e. name="next") matching by simple
pointer comparison. But for the reference, we have to do a ref-walking
comparison in the manner of dwarf_comparator.
This plan means that for <pointer_type type="something circular"/> and
<reference_type type="something circular"/>, we'll actually have dozens to
thousands of entries with the same hash value--basically every single
pointer_type to a nontrivial class/struct is a hash collision with every
other. If that's the plan, then the ref-walking comparisons we do have to
be very well-optimized. We'll be doing many, many of them every time we
come across another pointer_type entry in the input.
Picayune as I've been, this is just the broad overview. It seems solid,
and the obvious thing to do, up to the point of the plan for circular
references. It's not entirely clear that having so many hash collisions in
this approach is a reasonable way to go. But I don't know what a different
plan would be for efficiently identifying equivalent subtrees in the
presence of circular references.
Most of the real complexity in the copier has to do with handling forward
references in attributes, including circular references. Aside from the
simple-value mapping caches I described earlier, everything else is pretty
much just interface glue for making the dwarf_output constructors work.
The possibility of forward references means we have to partially construct
entries while waiting to resolve their references, so there are lots of
internal data structures for that.
In valid input data, a single entire (logical) CU tree has no dangling
references. So all the partially-built tracking data structures only need
to live (at most) during the construction of one compile_unit tree in the
dwarf_output object. The only things that live longer in the copier are
just caches keyed on parts of the input that might be shared across input
logical CUs (like the strings, but also input DIEs--for when eventually
reading compressed format input). For following the control flow, you can
start at dwarf_output::copier::make_unit. You can read the classes it
calls to see how it's all organized. (Note how at various levels, most of
the actual work happens inside a foo_copier constructor.)
For all of the entry-copying hair inside dwarf_output::copier, I think it
will be easiest to just answer questions as you read through the code,
rather than trying to describe a structure and a plan. I can explain it
all piece by piece, but at this point will largely be recovering the
knowledge from re-reading the code anyway, so we can read it together.
How that all works is quite ad hoc (and about the third generation of how I
organized it), and I probably couldn't articulate an overall algorithm it
is implementing. There is:
#if 0 // Toggle this to enable massive debugging spew during construction.
and making that 1 will get you quite a lot of spew that may help get a
handle on how the partial entry resolution control flow goes. The usual
ways to drive a test of this is:
tests/dwarf-print --output file
For nontrivial CUs in the input file, the debugging spew is truly massive.
Thanks,
Roland
12 years, 8 months
Spam on the list
by Kurt Roeckx
Hi,
I've been seeing alot of spam on this list the past week or
something. Could someone please check the filters? Mine
would have catched most of this if I didn't trust the
mailinglist.
Kurt
12 years, 11 months
dwarflint --stats
by Roland McGrath
(Petr is on vacation, so it will most likely be at least a few weeks before
anyone starts to work on this.)
Jakub was interested in sampling some DWARF data to compare what one
compiler vs another is doing with some broad statistics of semantic
interest. The first particular thing to measure is how much location/value
information we are getting for variables and parameters.
This is not at all an error check, but I think it fits well enough into
dwarflint as a special option to request statistics reports (in future
perhaps several different kinds of things) either in addition to or instead
of the normal warnings/errors. The first kind of statistic of interest is
in stuff that I think dwarflint looks at already for some of its checks.
So, it would go something like this:
Consider each DW_TAG_variable or DW_TAG_formal_parameter that might have a
location. That is, ignore variables with DW_AT_declaration and ignore the
formal_parameter children of subprograms with DW_AT_declaration. Look at
all the rest, and tally. (Double-check the cases with no DW_AT_location or
DW_AT_const_value at all to see if there is some other exclusion from
"might have a location" that I'm overlooking at the moment.) For each,
compute what percentage of the variable's scope has locations or values.
An extern global has DW_AT_external and no location at all, but is not
missing any info. So exclude those from the tally.
Globals (with DW_AT_external) and statics (without) are identified by
having a non-list DW_AT_location that is a singleton DW_OP_addr expression.
Perhaps (optionally?) exclude these from the tally entirely, so they don't
dilute the cumulative percentages. Every compiler always just emits those
locations regardless of optimization or debuginfo fanciness, so for
comparing compilers it is probably more meaningful to measure only among
the pool of variables with dynamic extent.
If it has DW_AT_const_value, then call that 100%.
If it has a non-list DW_AT_location with a nonempty expression,
also call that 100%. If it has no DW_AT_location or a non-list
DW_AT_location with an empty expression, call that 0%.
Otherwise, it's a location list. So, first find the "scope" ranges set for
this DIE. That is, if the DIE itself has a DW_AT_start_scope that is a
rangelistptr, then exactly that is the set. If the DIE itself has
DW_AT_{ranges,high_pc} then that's the set (but it won't). Otherwise, look
back up parent DIEs until one has ranges/high_pc. If the variable DIE has
a DW_AT_start_scope that is a constant, then exclude the portion of the
range before it (see DWARFv4 3.3.8.2 item 11).
If the location list covers any address bytes outside the "scope" set,
then exclude those portions from the location list set for further
consideration. I think dwarflint might already have a warning about that
happening, or if not perhaps it should (though perhaps it is also an OK
thing in the data, it remains unclear).
Exclude any location list entries whose expression is empty. (You might
already have a warning about those too, since they are superfluous entries
to have.)
Finally, count up the cumulative bytes covered by the scope set and those
covered by the location set. Tally the ratio of those two counts as a
percentage. Perhaps produce a scatter plot with x axis the location/scope
rounded to an integer percentage and y axis the percentage of the DIEs
considered whose ratio is x. And perhaps say min/max/avg(/median?) ratios
seen.
Another variant would be to also tally what portion of available locations
is mutable vs immutable (or distribution of the ratios, or whatever). That
is, DW_AT_const_value is immutable. A location expression is immutable if
it ends in DW_OP_implicit_value or DW_OP_stack_value. If an expression
uses DW_OP_{,bit_}piece, then it can be partially mutable and partially
immutable. You can probably just choose arbitrarily to count those on one
side or the other, or perhaps tally them as a separate third statistic.
Jakub can say better than I which statistical analyses he is most
interested in seeing.
Thanks,
Roland
12 years, 11 months
caching bug example
by Roland McGrath
To play along at home, use the roland/dwarf-hacking branch.
This has the cache reenablement patch I included before, plus
some debugging hacks I'm using.
The test file is just elfcmp from my build. But to keep us stably working
with the same data and so we can talk about file offsets and all, it's here:
http://roland.fedorapeople.org/tmp/test-elfcmp
My build is by gcc-4.4.4-10.fc13.x86_64 and uses:
CFLAGS='-fexceptions -g' CXXFLAGS='-D_GLIBCXX_DEBUG -g' --enable-maintainer-mode --enable-tests-rpath --prefix=/usr --libdir=/usr/lib64 --program-prefix=eu-
You'll need to match that for the frame counts in my gdb fragments to be
right for you. Otherwise, you can poke around with "up RET RET RET ..."
until you hit the right place and see how many frames it actually is for
each case in your build.
The test is the first failure in make check on this branch:
src/dwarfcmp-test -T test-elfcmp{,}
It fails because the copied dwarf_output doesn't match the dwarf.
It comes out arcanely different because of bad reference matches
that influenced what subtrees got unified into one shared tree.
Firstly, we look at the trees for reference:
tests/dwarf-print --sort-attrs test-elfcmp > a
tests/dwarf-print --output test-elfcmp > b
tests/dwarf-print --offsets test-elfcmp > c
tests/dwarf-print --output --stats --silent test-elfcmp > s
The --sort-attrs output is the input file (dwarf class), but with
attributes sorted by (integer) name so that the conceptually unordered
attribute set is in a canonical order that prints identically regardless of
the order the input file uses. The --output (dwarf_output class) data
always has sorted attributes, so that makes a and b directly comparable.
The --offsets output (you can add --sort-attrs after it if you want) is
handy for cross-referencing while you debug. It prints a fake attribute
offset=[0x1234] in each DIE (whereas the other format prints a fake
attribute ref="ref123"). It's otherwise the same as a, but it's not
textually comparable to b. Importantly, it has the line breaks in all the
same places. So each line of c corresponds to the same-numbered line in a
(and should to b, if dwarf_output is not too buggy).
So when you are debugging, look at the DIE offset you are dealing with and
then you can look that up in c, go to the same line number in a and b, and
see how they each look.
The dump in s can also come in handy. You can look up original input file
DIE (hex) offsets in there to see what did or didn't get shared, etc. To
the extent that the output formats are not obvious, just ask. (I actually
don't remember off hand exactly what all the numbers are.)
So, with this data in hand, now you can do:
diff -u a b
and you'll see that all the differences seem to be in the ref numbers,
so you know it's harder than that.
I'm using these gdb macros:
(gdb) define pp
Type commands for definition of "pp".
End with a line saying just "end".
>p/x b.offset()
>p b.to_string()
>p/x *(a.info())
>end
(gdb) define refmatch
Type commands for definition of "refmatch".
End with a line saying just "end".
>up 7
>pp
>end
(gdb) define diematch
Type commands for definition of "diematch".
End with a line saying just "end".
>up 8
>pp
>end
(gdb)
Btw, I always use:
(gdb) catch throw
Catchpoint 1 (throw)
(gdb)
first thing.
Set a breakpoint at dwarf_comparator:309.
That's the debugging hack line with asm("nop").
I always use C-x SPC, but that's the line number.
Now run it:
(gdb) r -T ../test-elfcmp{,}
Starting program: /home/roland/build/elfutils/src/dwarfcmp-test -T ../test-elfcmp{,}
[Thread debugging using libthread_db enabled]
Breakpoint 5, elfutils::dwarf_comparator<elfutils::dwarf_output, elfutils::dwarf, false, elfutils::dwarf_ref_tracker<elfutils::dwarf_output, elfutils::dwarf> >::match_rhs::operator() (this=0x7fffffff60f0, it1=..., it2=...)
at ../../../redhat/elfutils/src/../libdw/c++/dwarf_comparator:309
(If you followed these instructions exactly, yours will be "Breakpoint 2".)
That breakpoint hits only when an attribute value mismatch was just seen.
So we are down inside however many layers of recursion we might be when
the first wrong detail was noticed.
(gdb) up 4
#4 0x00000000004d386d in elfutils::dwarf_comparator<elfutils::dwarf_output, elfutils::dwarf, false, elfutils::dwarf_ref_tracker<elfutils::dwarf_output, elfutils::dwarf> >::reference_match (this=0x7fffffff7530, ref1=..., ref2=...)
at ../../../redhat/elfutils/src/../libdw/c++/dwarf_comparator:551
This gets you to reference_match. The DIEs that had differing values for
some attribute were being compared to satisfy a reference comparison.
That's what the first macro is for:
(gdb) pp
$110 = 0x6c63
$111 = "<typedef name=\"int64_t\"/>"
$112 = {
first = {
_m_children = 0x8712f0,
_m_attributes = 0x8a8310,
_m_hash = 0xbb7652b333a4027,
_m_tag = 0x16
},
second = {
_m_parent = 0xff65c0,
_m_refs = std::queue wrapping: std::__debug::deque with 1 elements = {
0x893c30
},
_m_originals = std::__debug::set with 4 elements = {
[0] = 0x534,
[1] = 0x2b28,
[2] = 0x5097,
[3] = 0x5e4e
},
_m_original_cost = 0x2c,
_m_with_sibling = std::__debug::bitset = {
[1] = 0x1
},
_m_uses = 0x4
}
}
(gdb)
The output shows us we are comparing (references to) input DIE [6c63] and
what should be its corresponding dwarf_output::debug_info_entry
incarnation. The debugging hack there gets the die_info_pair, of which
.first is the debug_info_entry itself. The die_info part holds all the
interesting stuff we recorded in the dwarf_output building process.
In particular, notice some nice STL pretty-printing there and we have the
_m_originals set nicely shown. That's where we record (just for this kind
of debugging) the offsets of all the original dwarf::debug_info_entry's
that were consolidated into this one dwarf_output::debug_info_entry.
If you find 0x534 in s, you'll see:
4 hash=0x281033975398eb41 (10) 44 (33) <typedef name="int64_t"/> 0x534 0x2b28 0x5097 0x5e4e
That's just printing the same _m_originals set.
You can also find 0x6c63 and see:
1 hash=0x28105a1a3bd43b54 (10) 11 (0) <typedef name="int64_t"/> 0x6c63
So 4 instances of int64_t were merged and one was not.
You can wonder why that might have been and do:
$ src/dwarfcmp -l test-elfcmp{,} 0x534 0x6c63
534 vs 6c63: decl_file="/usr/include/sys/types.h" vs decl_file="/usr/include/stdint.h"
534 vs 6c63: decl_line=198 vs decl_line=41
$
So, they differ because they really do differ. Fine and dandy.
So, how did we get here, thinking they should be the same?
Remember, our current frame now is in reference_match.
We have a macro for that.
(gdb) refmatch
#11 0x0000000000489121 in elfutils::dwarf_comparator<elfutils::dwarf_output, elfutils::dwarf, false, elfutils::dwarf_ref_tracker<elfutils::dwarf_output, elfutils::dwarf> >::match (this=0x7fffffff7530, a=..., b=...)
at ../../../redhat/elfutils/src/../libdw/c++/dwarf_comparator:265
$113 = 0x76cf
$114 = "<formal_parameter/>"
$115 = {
first = {
_m_children = 0x8712f0,
_m_attributes = 0x13c2a60,
_m_hash = 0xc237b1935c5,
_m_tag = 0x5
},
second = {
_m_parent = 0x13c3ae0,
_m_refs = std::queue wrapping: std::__debug::deque with 1 elements = {
0x13c0d10
},
_m_originals = std::__debug::set with 8 elements = {
[0] = 0x1170,
[1] = 0x1190,
[2] = 0x3f7a,
[3] = 0x3f9a,
[4] = 0x5ab0,
[5] = 0x5ad0,
[6] = 0x686d,
[7] = 0x688d
},
_m_original_cost = 0x2c,
_m_with_sibling = std::__debug::bitset = {
[0] = 0x1,
[1] = 0x1
},
_m_uses = 0x2
}
}
Now our current frame is in DIE matching, not reference_match (you just
have to look). We have a macro for that.
(gdb) diematch
#19 0x00000000004d3946 in elfutils::dwarf_comparator<elfutils::dwarf_output, elfutils::dwarf, false, elfutils::dwarf_ref_tracker<elfutils::dwarf_output, elfutils::dwarf> >::reference_match (this=0x7fffffff7f00, ref1=..., ref2=...)
at ../../../redhat/elfutils/src/../libdw/c++/dwarf_comparator:557
$116 = 0x76c5
$117 = "<subroutine_type>"
$118 = {
first = {
_m_children = 0x13c1020,
_m_attributes = 0x13b69d0,
_m_hash = 0x8e92e3c9b8cb158d,
_m_tag = 0x15
},
second = {
_m_parent = 0xff65c0,
_m_refs = std::queue wrapping: std::__debug::deque with 1 elements = {
0x13c1d60
},
_m_originals = std::__debug::set with 4 elements = {
[0] = 0x1166,
[1] = 0x3f70,
[2] = 0x5aa6,
[3] = 0x6863
},
_m_original_cost = 0x68,
_m_with_sibling = std::__debug::bitset = {
[1] = 0x1
},
_m_uses = 0x4
}
}
Now we're back in reference_match, it so happens. This could be all
thoroughly automated with some gdb python, but I just did it the old
school way with the macros that are easy to write, and the eyeball test
at each iteration. Doing that all the way back, I culled the sequence
of comparison steps that got us here (shown here innermost first). (I
didn't record which were refs and which were DIEs, but you can repeat
the experiment for yourself.)
0x6c63 "<typedef name=\"int64_t\"/>"
[0] = 0x534,
[1] = 0x2b28,
[2] = 0x5097,
[3] = 0x5e4e
0x76cf "<formal_parameter/>"
[0] = 0x1170,
[1] = 0x1190,
[2] = 0x3f7a,
[3] = 0x3f9a,
[4] = 0x5ab0,
[5] = 0x5ad0,
[6] = 0x686d,
[7] = 0x688d
0x76c5 "<subroutine_type>"
[0] = 0x1166,
[1] = 0x3f70,
[2] = 0x5aa6,
[3] = 0x6863
0x76df "<pointer_type/>"
[0] = 0x1180,
[1] = 0x3f8a,
[2] = 0x5ac0,
[3] = 0x687d
0x7337 "<member name=\"dynamic_tag_name\"/>"
[0] = 0x3be8,
[1] = 0x5718,
[2] = 0x64d5
0x7222 "<structure_type name=\"ebl\">"
[0] = 0x5603,
[1] = 0x63c0
0x7217 "<typedef name=\"Ebl\"/>"
[0] = 0x55f8,
[1] = 0x63b5
0x7601 "<pointer_type/>"
[0] = 0x59e2,
[1] = 0x679f
0x75f6 "<formal_parameter/>"
[0] = 0x59d7,
[1] = 0x5a80,
[2] = 0x5ba7,
[3] = 0x5c9a,
[4] = 0x5cd9,
[5] = 0x5d42,
[6] = 0x6794,
[7] = 0x683d,
[8] = 0x6964,
[9] = 0x6a57,
[10] = 0x6a96,
[11] = 0x6aff,
[12] = 0x75f6,
[13] = 0x769f
0x75ec "<subroutine_type>"
[0] = 0x59cd,
[1] = 0x678a,
[2] = 0x75ec
0x7607 "<pointer_type/>"
[0] = 0x59e8,
[1] = 0x67a5,
[2] = 0x7607
0x729b "<member name=\"reloc_simple_type\"/>"
[0] = 0x567c,
[1] = 0x6439,
[2] = 0x729b
0x7222 "<structure_type name=\"ebl\">"
[0] = 0x7222
0x7217 "<typedef name=\"Ebl\"/>"
[0] = 0x7217
0x6c2c "<compile_unit name=\"../../../redhat/elfutils/libebl/ebldebugscnp.c\">"
So, what's really going on here is that there are some different entries
for <structure_type name="ebl"> that have gotten mixed up weirdly.
M-x occur says:
4 matches for "<structure_type name="ebl">" in buffer: s
363:2 hash=0x25ae7a82f071dcfe (10) 1180 (590) <structure_type name="ebl"> 0x5603 0x63c0
433:1 hash=0x6570b7d2bd1d5b7d (10) 590 (0) <structure_type name="ebl"> 0x7222
434:1 hash=0x2e42f8c64d6c4a2c (10) 590 (0) <structure_type name="ebl"> 0x3ad3
435:1 hash=0x9248a5043861eca7 (10) 590 (0) <structure_type name="ebl"> 0xcc9
So, there were 5 different DIEs in the input (in different CUs, we expect).
Two got consolidated together and the others didn't. That's fine for now.
They might differ for good reasons or ill reasons, but that's not quite our
concern at the moment.
What's certainly a concern is how that comparison path somehow led from one
copy to another. In that comparison path, we started comparing 0x7222 to
the output DIE that came from 0x7222. But when the input side ("b" in gdb)
went circular at 0x7217->0x7222, the output side ("a" in gdb) instead went
to a different <typedef name="Ebl"/> instead. If we look back, the first
comparison step that was looking at an output copy that did not include the
input peer in its originals set is:
0x7601 "<pointer_type/>"
[0] = 0x59e2,
[1] = 0x679f
There is no 0x7601 in that set. But the <formal_parameter/> copied from
0x75f6 points to it. So, how did that come to be?
It means the dwarf_output tracker decided that some type=[0x7601] attribute
was equal to some type=[0x59e2] attribute so it could merge 0x75f6 and its
peers together. But then when it came to 0x7601 vs 0x59e2 as DIEs, it
didn't think they were equal, so 0x7601 didn't merge with 0x59e2.
We can try to figure it out with:
$ src/dwarfcmp test-elfcmp{,} 0x7601 0x59e2
7601 vs 59e2: type=[0x7217] vs type=[0x55f8] (<typedef name="Ebl"/> with reference mismatches)
reference 7217 vs 55f8: 7217 vs 55f8: type=[0x7222] vs type=[0x5603] (<structure_type name="ebl"> with reference mismatches)
reference 7222 vs 5603: 7337 vs 5718: type=[0x76df] vs type=[0x5ac0] (<pointer_type/> with reference mismatches)
reference 76df vs 5ac0: 76df vs 5ac0: type=[0x76c5] vs type=[0x5aa6] (<subroutine_type> with reference mismatches)
reference 76c5 vs 5aa6: 76cf vs 5ab0: type=[0x6c63] vs type=[0x5097] (<typedef name="int64_t"/> != <typedef name="int64_t"/>)
reference 6c63 vs 5097: 6c63 vs 5097: decl_file="/usr/include/stdint.h" vs decl_file="/usr/include/sys/types.h"
$
But that just tells us that dwarfcmp is not as confused as dwarf_output--at
least when starting from those two DIEs, though perhaps not so further out
in the circularity path. We can see good reason that these two were not
conflated together. But we don't know why references to them *did* get
conflated. So, get to investigating! (I expect this to generate a lot
of questions about dwarf_output::copier.)
Thanks,
Roland
13 years
DW_TAG_variable for both decl and defn?
by Roland McGrath
In kernel-debuginfo-2.6.33.6-147.fc13.x86_64
/usr/lib/debug/lib/modules/2.6.33.6-147.fc13.x86_64/vmlinux
Compilation unit at offset 63884337:
Version: 3, Abbreviation section offset: 1655619, Address size: 8, Offset size: 4
[3cecc3c] compile_unit
producer (strp) "GNU C 4.4.4 20100630 (Red Hat 4.4.4-10)"
language (data1) ISO C89 (1)
name (strp) "net/ipv4/tcp.c"
comp_dir (strp) "/usr/src/debug/kernel-2.6.33/linux-2.6.33.x86_64"
we see:
[3d0b497] variable
name (strp) "tcp_memory_pressure"
decl_file (data1) 10
decl_line (data1) 247
type (ref4) [3ceccfc]
external (flag) Yes
declaration (flag) Yes
(extern decl in header file) and later in the same CU:
[3d0c424] variable
name (strp) "tcp_memory_pressure"
decl_file (data1) 1
decl_line (data2) 318
type (ref4) [3ceccfc]
external (flag) Yes
location (block1) [ 0] addr 0xffffffff81b8cb04
(global defn in this CU's main source file).
I guess it's kosher enough to have one DIE for the declaration and one for
the definition. But it was a surprise to see this happen. In a simple
test case:
extern int global_var;
static int static_var;
static int static_var = 123;
int global_var = 456;
(with plain -g) I only get one DW_TAG_variable for each.
So I would like to understand under what conditions GCC does (or should?)
generate two entries in cases like these.
IMHO, it would be nice, if you're going to have both a decl and a defn,
for the defn to have DW_AT_specification pointing to the decl (even for C).
But that's a tangential idea.
We noticed this with systemtap, because dwarf_getscopevar (which it uses)
stops at the first matching name. So it found the declaration DIE and said
"this has no known location" (i.e. punt to methods for extern decls of
things defined in other CUs). This is fine for this kind of case, since we
do have those methods in systemtap (it looks up an ELF symbol to resolve
the global between CUs).
However, if it ever generated two DIEs like that for a static variable,
this would break systemtap as things stand today (if the DW_AT_declaration
one appears first in the CU's DIE list).
If that is how it's going to be, then perhaps dwarf_getscopevar should do
something like keep looking until it sees a match without DW_AT_declaration,
only giving the (first? last?) DW_AT_declaration match if there is no later
non-declaration DIE.
Petr, a check related to this is a to-do item for dwarflint high-level checks.
If you think (as I suspect) that it's just a bug for there to be two DIEs
for the same variable, then I have the reproducer:
1 extern int global_var;
2
3 extern __typeof (global_var) global_var;
4
5 int global_var = 456;
Through some macro magic, this is the essence of what's happening in the
kernel case. The DW_AT_declaration entry emitted is for the first decl
(line 1). I'm guessing that the __typeof magic in the line 3 decl confuses
it somehow into thinking that the extern on line 1 and the defn on line 5
don't go together, so line 5 fails to trump line 1 as it ordinarily would.
(Perhaps this would also happen if it redeclared it with __attribute__ or
something, though I haven't found another case in things I've tried.)
Thanks,
Roland
13 years
dwarfcmp comparison caching
by Mark Wielaard
Hi,
I think I see now why dwarfcmp is so slow. But I don't fully understand
the intent/design of the comparison caching. But it seems we are not
using the results of the dwarf_comparator tracker caching as often (at
all?) as we could.
For future reference, there are a couple of similar, but different
comparing operators/functions constructs used. An important difference
to look for is whether dwarf_comparator comparisons are made through
equals () or match (). In the case of equals () the tracker can "short
circuit" a successful comparison if it has cached the result.
- subr::container_equal calls begin() on the arguments to get iterators
and compares each element through a predicate function given.
- class dwarf_comparator extends std::binary_function and defines an
bool operator (). This is implemented by calling match (a, b).
- a dwarf_comparator has a template function for equals (a, b) which
consults the tracker set and the match (a, b) function through
return _m_tracker.identical (a, b) || match (a, b);
- the private dwarf_comparator match (a, b) functions are specialized:
- dwarfs (calls match on compile_units),
- compile_units (uses subr::container_equal with match () as
predicate, while tracker.mismatch),
- debug_info_entries (creates a tracker::visitor calls == on tags,
equals () on attributes and children),
- die attributes (uses subr::container_equal, with match_rhs () as
predicate, which uses the comparator equals ()
method on the values of attributes, while
tracker.mismatch, then tries ordered attribute
lists comparing keys with == and values with equals)
- die children (uses subr::container_equal with match as predicate,
while tracker.mismatch)
- attribute (calls == on value and equals () on values),
- attribute values (depending on the value space almost all
comparisons are done through ==, except for
reference which are compared through
calling reference_match ())
- child iterator (calls reference_match ())
- reference_match works on two die iterators. If the comparator ignores
refs then it always returns true. Otherwise a die identity comparison
is done first, then the tags are compared and whether both have
children. Then the tracker is queried. First the tracker
reference_matched () and cannot_match () are tried. Then a subtracker
and a subcomparator are created (with a reference to the original
tracker). Then the subcomparator equals () is called on the
attributes, the original tracker context_match () and the
subcomparator equals () in the children. Finally the original tracker
notice_match () is called with the actual result so it can possibly
log and/or cache that.
- dwarfcmp extends dwarf_comparator and overrides the () operator to
call equals (a, b) in quiet mode or in the noisy variant it calls
equals (a, b) && tracker.result.
- A dwarf_ref_tracker notice_match is ignored in both the base_tracker
and the dwarf_ref_tracker. dwarfcmp overrides it, but stores the
result in the base tracker, so it seems that is lost too.
identical (a, b) is defined as false in the base tracker (which means
the dwarf_comparator equals short circuit doesn't work).
So what is happening in even a small example is:
int
main (int argc, char **argv)
{
return 0;
}
compiled with gcc -g this gives: tests/dwarf-print main
main:
<compile_unit ...>
<subprogram external=1 name="main" ... type="#ref1" ...>
<formal_parameter name="argc" ... type="#ref1" .../>
<formal_parameter name="argv" ... type="#ref2" .../>
</subprogram>
<base_type ref="ref1" byte_size=0x4 encoding=signed name="int"/>
<pointer_type ref="ref2" byte_size=0x8 type="#ref3"/>
<pointer_type ref="ref3" byte_size=0x8 type="#ref4"/>
<base_type ref="ref4" byte_size=0x1 encoding=signed_char name="char"/>
</compile_unit>
Note that the subprogram has #refs to types that are declared later in
the compile unit.
If we compare two of the above compile_units, even though the
ref_tracker keeps a cache of the context path, the "down path" isn't
cached. So the argv #ref2 is followed down to #ref3 and finally compared
down to ref4. But then when we encounter ref2 itself, the #ref3 type
reference is fully compared down to ref4. And again for the #ref4 in
ref3 itself.
I am not really sure where we the compare caching should really go and
be fixed because he precise idea behind the equal/match and
identical/notice_match are not completely clear to me. Is the
entanglement of the context path caching and the identical tracking on
purpose?
Cheers,
Mark
13 years