mjw/dwarf_output branch
by Mark Wielaard
Hi,
Trying to get some of the algorithm ideas going on the mjw/dwarf_output
branch. Although I started out trying to change te way the copier marked
entries final and put them into the collector I ended up not immediately
needing that. Because when the entries are marked final both their
children and reference attributes are resolved already.
So what the code does at the moment is add a local_hash function to both
dwarf_output::debug_info_die and copier::pending_entry. These hash
functions should be in sync because a not fully resolved attribute
reference could be pointing to a pending_entry. Both calculate the local
hash based on the local hash of the attributes_type and the
children_type. Then the hash of a value_reference is the local hash of
the debug_info_die hash it is pointing at.
For now the really tricky case inside the local hash function of the
attribute_types containing a reference attribute is side stepped by just
using the tag of the reference attribute. This is enough to get the
small testcases in dwarf_edit_output working that failed before. Because
this makes the hashes of similar structures always the same (before they
would have hash slightly differently based on where a attribute
reference cycle was detected).
So what is missing is "chaining" the reference attribute local hashes
(if we don't chain them, we end up with very "flat" hashes where lots
dies get the same hash just because they have a reference attribute).
Ideally this would just be ref_attr.reference()->local_hash (), but
since we calculate the hash of the attributes_type just before it is
inserted into the collector this doesn't work (the way this aborts is
somewhat obscure though - it ends up in in the dwarf_data::variant
constructor that throws a "can't happen!"). I am a little confused atm
about how the instantiation of the attributes_type gets triggered
precisely. It is probably necessary to do this in two phases by lifting
parts of pending_entry::final () method out in a second initialization
step.
Please do poke holes in the code or the whole story.
Cheers,
Mark
12 years, 7 months
dwarfcmp performance
by Petr Machata
Hi there,
about two weeks ago I let dwarfcmp spin on one of the difficult cases.
After a week or so it answered that the files are equal. Another case
ended up after about a day. So I suppose the algorithms are sound, it's
just that it takes ages to get through it all.
OProfile shows that one major time sink is dwarf_path_finder::step ctor.
That is called from a bunch of places, but the interesting cases come
from dwarf_comparator::reference_match where it calls
dwarf_ref_tracker::left_context and dwarf_ref_tracker::right_context.
This gets called when the comparator hits forward reference. The
algorithm then starts from where in the tree we are (since it's
guaranteed to not need any of the already-seen dies, these are cached),
and traverses it in a linear fashion, looking for the referenced die.
I added counters to see how long these walks were. Average over our
build tree (excluding the cases that would take ages, where "ages" for
my purposes was anything above 20 seconds) is 18 steps, but many C++
modules make easily 100+ steps on average. Average over dwarflint
objects is 90 steps. Clearly C++ produces forward references that lead
further ahead on average (or there's more detailed and deeper structure
between here and there).
So the problem is we simply end up doing walks over those same dies
again and again and again, as we look for some far-ahead die. I don't
know if there are other time sinks, but getting rid of this traversing
should help a great deal.
The obvious solution is to do an initial pass over all dies, noting
forward references, and when we hit the die that is forward-referred to,
remembering the path for later. That way we would avoid all the
repetitve walking that context extraction entails. I suspect that
should help a great deal with the overall performance.
Thanks,
PM
12 years, 8 months
0.151 release
by Roland McGrath
I think we are ready to make the 0.151 release now.
Don't forget git tag -s and git push.
If I haven't heard from you my midday Thursday, I'll do it myself.
Thanks,
Roland
12 years, 8 months
entry vs pending_entry in dwarf_output::copier
by Roland McGrath
dwarf_output::copier::entry is the main struct describing each input DIE
encountered. These live as long as the copier lives, and thus are the
"permanent" record about each input DIE. These are created via
copier::enter from either copier::add_child or copier::add_reference.
Thus, an entry will exist for an input DIE not yet encountered in the
copying walk, if another DIE's attributes contained a reference to it.
All entry objects live in the copier::_m_entries map, which is a hash
table keyed by the <impl>::debug_info_entry::identity () value, which is
actually a globally-unique pointer. For <impl>=dwarf, this is actually
the Dwarf_Die::addr value, i.e. the pointer to the file data mapped in
memory. For the other implementations, it's the address of the
debug_info_entry object itself.
Once a new DIE has been finalized, entry::_m_final points to its
instance in the collector. Before that, entry::_m_pending might point
to a pending_entry. If both of those are NULL, then this is an entry
that has only been encountered in a reference attribute, and no other
members are set except for _m_offset (used in the debugging output).
dwarf_output::copier::pending_entry describes an input DIE currently
being copied, but not yet made final. This first exists while the
copier is copying that entry on the initial copying walk. It lives
until the entry can be finalized, when it is freed and replaced by
setting _m_final. It's somewhat important to do this as early as we can
manage, because duplicative identical input DIEs each have their own
entry, and thus their own pending_entry before they're final. The
pending_entry's members are where the most memory is consumed in the
copier. The quicker we can finalize entries, the less memory we consume
during the copying of the whole tree.
In the current code, a pending_entry lives until the hairy bookkeeping
figures out that it can do the finalization. In the new plan's first
cut, each pending_entry will live until the whole first copying walk is
done. (The exception being that if the input uses DW_TAG_imported_unit,
then any shared duplicate entries will have been finalized in the
copying of the first CU containing them, and thereafter another CU's
copying walk will encounter an entry that already has its _m_final set.)
In the new plan's second walk, each entry will be finalized so its
pending_entry can be freed.
Because of the aforementioned memory consumption, we will want to do
early finalization during the first copying walk whenever possible.
That is, do the "second walk" work for any subtree that has no
references to other entries that are not yet final.
Is that all clear? I'm not sure it's entirely necessary wrap one's head
around all the hairy bookkeeping of the current plan. The new plan is
replacing it with something easier to understand anyway.
There will still be some hairy magic for cases of circular references.
An entry can't be truly final until all its references are final, and
thus that's a circular requirement. That's why we need the "placed"
stage, where a value_reference already in the collector gets reified
with the actual iterator into its referent's parent's children vector.
Thanks,
Roland
12 years, 8 months
0.151 release this week
by Roland McGrath
I need to make the 0.151 release this week. I'd like to have it done on
Thursday. We are waiting for Josh to supply some additional test cases to
help verify the recent fixes in libdwfl vs prelink. I hope those will all
be in and the fixes thoroughly verified by the end of Wednesday.
When tagging, remember to use git tag -s.
And don't forget to git push everything after building release files.
If you can't easily get to this in time, I can do it myself.
Thanks,
Roland
12 years, 8 months
readelf and % of bits sets
by Colin Pitrat
Hello,
I was surprised to see in src/readelf.c that how the % of bits sets in the
Bloom filter bitset is computed.
The formula taken is the following:
%set = (nbits * 100 + 50) / (nb_bitmask_words * sizeof(bitmask_word) * 8);
Do you have any hint on why there is this + 50 that corresponds to adding
half a bit in the bit set ?
Regards,
Colin
12 years, 8 months
[patch] Fix elf_getdata_rawchunk false error
by Jan Kratochvil
Hi,
if you run jankratochvil/gdbserver as:
./gdbserver 1234 corefile
without this change it prints:
./gdbserver: Error reading note at core file offset 0x468
due to:
81 if (unlikely (size > elf->maximum_size
82 || (off64_t) (elf->maximum_size - size) < offset))
(gdb) p size > elf->maximum_size
$6 = 0
(gdb) p (off64_t) (elf->maximum_size - size) < offset
$7 = 1
(gdb) p offset
$10 = 1128
(gdb) p (off64_t) (elf->maximum_size - size)
$8 = -1369
(gdb) p elf->maximum_size - size
$9 = 18446744073709550247
(gdb) p/x elf->maximum_size
$11 = 0xffffffffffffffff
In fact I believe Elf->maximum_size should be off64_t and not size_t as this
way 32bit hosts cannot handle >2GB ELF files, can they? But as 32bit hosts
are dead I did not try to do the more invasive change.
OK to merge to master? It is now in <jankratochvil/pending>.
No regressions on {x86_64,i686}-fedora13-linux-gnu.
Thanks,
Jan
libelf/
2010-12-19 Jan Kratochvil <jan.kratochvil(a)redhat.com>
* elf_getdata_rawchunk.c (elf_getdata_rawchunk): Fix off64_t overflow
when MAXIMUM_SIZE == ~0.
--- a/libelf/elf_getdata_rawchunk.c
+++ b/libelf/elf_getdata_rawchunk.c
@@ -78,8 +78,8 @@ elf_getdata_rawchunk (elf, offset, size, type)
return NULL;
}
- if (unlikely (size > elf->maximum_size
- || (off64_t) (elf->maximum_size - size) < offset))
+ if (unlikely (offset < 0 || offset + (off64_t) size < offset
+ || offset + size > elf->maximum_size))
{
/* Invalid request. */
__libelf_seterrno (ELF_E_INVALID_OP);
12 years, 8 months
some notes on dwarf_output::copier
by Mark Wielaard
Just some notes that I made trying to figure out the state of the copier
and entry classes. More of a reference of all fields that hold state and
the control structures that exist to change them. Trying to figure out
what to change where to plug in the new setup/algorithm.
The dwarf_output::copier is responsible for transforming the input die
tree into unique dies in the collector, that then will make up the
dwarf_output dwarf hierarchy.
The copier is instantiated when a dwarf_output object is instantiated
and it creates the compile_units, which will call copier::make_unit ()
through the cu_maker for each cu. make_unit () will create a
copier::unit_copier for each cu using the
compile_units_type::const_iterator, and then calls final_unit () on it,
which just does a sanity check on the result, making sure there are no
undefined entries left, and returns the final die_info_pair.
copier::unit_copier is derived from copier::entry_copier and just makes
sure that the copier is setup, through a call to copier::enter
(input_die) to create a new copier::entry, and then a call to
entry_copier::populate () to setup the die children.
An entry_copier lives as long as the copier is transforming the
input_die. It holds the copier, the copier::entry input die, and a
copier::pending_entry output which gets created in the constructor from
the input die tag. The constructor set the input copier::entry
_m_building field to the entry_copier to indicate it is being
constructed. The destructor clears it again. It doesn't hold the actual
input_die as state, all methods take an input_die as argument.
entry_copier::populate (as called from the unit_copier constructor)
takes an input_die, sets the _m_pending field of the input entry to the
output pending_entry of the entry_copier. It will populate the
_m_attributes if the _m_out entry from the given input_die and call
add_child() for each child of the given input_die. After that it will
clear the _m_out field to indicate the we are done with the
pending_entry. And call entry::defined_self () on the _m_in entry.
When the _m_attributes set of the entry is populated the value maker
will call back into the entry_copier::add_reference() for each reference
value. add_reference() will setup the copier to enter the input_die to
which the attribute is pointing and provide a "backptr" to the
entry::refer() method that fill it in with either the finalized entry
itself (if it is finalized) or to the entry itself and pushes the
backptr to the _m_pending_refs of pending_entry.
entry_copier::add_child will setup the copier to start copying the given
child die and create a new copier::entry for it, add the child to the
_m_out pending_entry. If the child is already know, but not yet final
(because it comes from an DW_TAG_imported_unit in a logical walk) it
will update the _m_parent and create a new entry_copier and populate
that.
entry_copier::final_unit() as called from make_unit() will do sanity
checks to make sure the _m_in entry has really been finalized and return
the die_info_pair stored in the collector.
A copier::entry holds the following state: _m_offset, the Dwarff_Off of
the original die, _m_cost, the cost of the original die, _m_final a
pointer to a die_info_pair in the collector indicating this entry has
been finalized, _m_pending the pending entry state set by the
entry_copier, _m_parent entry pointing to direct parent, _m_building the
entry_copier (cleared on entry_copier destruction), _m_matching state
for the tracker, _m_self_idx used to find an child iterator to this
entry of its parent from a pending_entry, _m_final_ref "fake"
value_reference set and returned when self() is called to indicate the
entry is final but not yet "placed".
A copier::pending_entry holds the following sate: _m_tag the die tag,
_m_attributes the attributes, _m_children a vector of entry children,
_m_unfinished_children boolean to flag not all entry children are final,
_m_pending_regs stack of reference attribute values that aren't
resolved/final yet, _m_self a circular_reference to ourself,
_m_finalizing entry_finalizer set when actually finalizing the entry,
_m_matched and _m_mismatched caches for the tracker.
Next up is actually describing the control flow that changes the entry
and pending_entry state.
12 years, 8 months
new dwarf_output algorithm
by Mark Wielaard
Hi,
After rereading some of the discussions we had last year on the
dwarf_output algorithm, here is a recap and a new description of how I
think we should go forward with it.
The goal of dwarf_output is given an existing dwarf data structure to
provide a dwarf data structure where as many items as possible are
shared because they end up being (semantically) equal in the original
dwarf structure.
To that end the dwarf_output::copier goes over the CU and puts elements
into the dwarf_output_collector, which makes sure every element is
uniquely represented. To put an element into the collector we need to
make sure it is "complete", which also means it has a stable hash that
can be used for quick comparisons.
The copier goes over the DIEs keeping track of each DIE reference to
know its state (undefined - not seen yet, pending - depends on non-final
references, final - all references also final, placed - done).
The problem we had came from the fact that if taking the DIE children
and DIE attribute references together we got a full graph which could
contain cycles. So the hash of an attribute reference was defined as the
identify (pointer) of the DIE it was pointing to, or zero if it was part
of a circular chain. But only the reference that was detected as
"causing" the chain. It was that last issue that caused problems, since
in identical structures different references could be pin-pointed as
"causing" the cycle.
Just hashing all references to zero that are part of a cycle makes too
many structures hash identical, and cycle detection in arbitrary graphs
is not fun. So I was proposing a way to define categorizing/hashing the
DIEs based on properties that don't involve arbitrary cycles.
The algorithm depends on the fact that you can see the CU as two
different trees/forests without cycles in themselves. First there is the
DIE trees where we ignore the attribute references and only look at the
children of a DIE. Secondly there is the attribute reference tree
(attributes reference other DIEs to describe properties, but these
properties itself aren't cyclic or self-referential (this seems
semantically true for all current dwarf reference attribute types, but
structurally dwarf seems to allow DIEs with reference attributes that
would allow backreferences, so we would need to detect this as a sanity
check).
The original proposal was worded as walking the DIE tree multiple times.
https://fedorahosted.org/pipermail/elfutils-devel/2010-November/001699.html
But it might be easier to describe/fit into the current copier design by
describing it as when elements can be finalized into the collector
and/or how hashes are calculated.
In the below I assume we will keep two hashes per element. The
"children-hash" and the "references-hash". An element can be
finalized/put in the collector if both are fully defined. We can
probably keep one hash, but it seemed simpler to describe using two.
(These two are different from the use pointer as hash recently discussed
on the list.)
- The children-hash of a DIE without children is calculated from its
attributes but only using the values of basic attributes (ignoring the
value of reference attributes).
- The children-hash of a DIE with children is the same as one without,
combined with all children-hashes of its children.
- The references-hash of a DIE without reference attributes is equal to
its children-hash.
- The references-hash of a DIE with reference attributes is the
combination of the children DIE of the DIE itself, combined with all
reference-hashes of all DIEs that are referenced by the reference
attributes.
- For an attribute set to be finalized all DIEs pointed to by referece
attributes should have a reference-hash set. The hash of an attribute
set then is the combination of simple attribute values hashes combined
with the reference-hashes of all those DIEs.
- For a vector of DIEs (children of another DIE or the CU) to be placed
in the collector all DIEs need to have reference-hashes. The hash of a
children vector is the combination of all DIE reference-hashes.
- For a DIE to be finalized, the attribute set and the children vector
need to have been finalized and it has to have its reference-hash set.
So by calculating the children-hash of a DIE always before the
reference-hash of the DIE, we make sure we are chasing down one "tree"
at a time.
I think the above should fit into the current copier code setup. But I
am sure I forgot something. It will come up when actually trying to
implement it this way. Missing is the sanity check to make sure that a
reference attribute never references a DIE for which its reference hash
is currently being resolved (which shouldn't ever happen, but might be
caused by funky dwarf).
Cheers,
Mark
12 years, 8 months
FYI <jankratochvil/gdbserver> gdbserver-for-core branch
by Jan Kratochvil
Hi,
FYI there is now branch <jankratochvil/gdbserver> containing a mostly done
<src/gdbserver.c> (except registers NOTEs) as a gdbserver only for core files.
FSF gdbserver cannot load core files. Created for ABRT purposes.
(I hope it is OK to create the <jankratochvil/*> branch(es).)
Regards,
Jan
12 years, 8 months