Hi,
A am a bit stumbling forward. Current progress pushed on the mjw/dwarf_output branch. Not stuck, just fighting and backtracking on some ideas. So best to give a little status update in case more course corrections are necessary.
The local hash for dies is now no longer (re)calculated in the dwarf_output::debug_info_entry hierarchy, but stored in the die_info. This is calculated when the pending_entry is finalized. This also puts all calculations in one place.
This is slightly too late (or too early depending on how you look at it). Although at that time all children of the die have already been finalized, not all (circular) references have. But we are putting the candidate into the collector anyway.
At first I thought that I just needed to get rid of the attributes_type cache, since that is where the reference chasing ends up. That would get rid of some complexity, but doesn't actually solve the actual algorithmic problem. Then the reference chasing ends up in the hash calculation of the debug_info_entry itself. So I abandoned that idea for now.
Instead what we need is to make sure that the local hash is calculated for every entry die before we try to put the attributes_type (or debug_info_entry) into the collector, since the full hash is based on the reference attributes, which can point to any die, and so need their local hash set.
So I am now looking at only calculating the local hash when we currently finalize, but don't put the items directly in the cache, but only after we scanned over the whole CU. That way when we do put the item in the cache, we can calculate the full hash because we can be sure that all dies that the reference attributes (recursively) points at have their local hash set.
Cheers,
Mark
The local hash for dies is now no longer (re)calculated in the dwarf_output::debug_info_entry hierarchy, but stored in the die_info. This is calculated when the pending_entry is finalized. This also puts all calculations in one place.
That makes sense to me.
This is slightly too late (or too early depending on how you look at it). Although at that time all children of the die have already been finalized, not all (circular) references have. But we are putting the candidate into the collector anyway.
It's neither too late nor too early, it's just right. The whole subtree is being finalized, and that's what matters. Circularities only affect the order in which you can do the final "placement" and subsequent reification of references to their proper iterators into finalized children vectors.
At first I thought that I just needed to get rid of the attributes_type cache, since that is where the reference chasing ends up. That would get rid of some complexity, but doesn't actually solve the actual algorithmic problem. Then the reference chasing ends up in the hash calculation of the debug_info_entry itself. So I abandoned that idea for now.
Right, this change should not be material to the essential algorithm. It only affects the complexity of the code (in which direction, it's hard to tell ;-), and the memory vs CPU time (in hash collision comparisons) tradeoff that I mentioned earlier.
Instead what we need is to make sure that the local hash is calculated for every entry die before we try to put the attributes_type (or debug_info_entry) into the collector, since the full hash is based on the reference attributes, which can point to any die, and so need their local hash set.
That sounds right.
So I am now looking at only calculating the local hash when we currently finalize, but don't put the items directly in the cache, but only after we scanned over the whole CU. That way when we do put the item in the cache, we can calculate the full hash because we can be sure that all dies that the reference attributes (recursively) points at have their local hash set.
I can't tell whether that sounds like exactly what I always thought the plan of the new algorithm was, or sounds like you're still not changing the old way of doing things enough.
"When we currently finalize" is based on all the dismal hairy bookkeeping that we ought to be getting rid of. In initial cut of the new plan, nothing actually gets finalized until the whole CU is being finalized. For the basic algorithm, the only aspect of the bookkeeping hair that we need to preserve is noting the places with circular references so that we can back-patch those after final placement. For a really straightforward first cut, you could record all forward references of any kind that way, so that you just do a single back-patching pass after the whole CU is finalized in tree order and that's the only means of reifying references. (This version of back-patching is nearly as simple as dwarf_edit's dwarf_ref_maker logic.)
For the slight refinement of the basic algorithm, we do the simple level of bookkeeping that notices when a subtree has no references at all, or has only references to things already found finalized in the collector. That's just enough to permit early finalization of the simple leaves, percolating up to early finalization of the subtrees containing those, and thus percolating up to early finalization of all subtrees that contain only backward references. When early finalization already finalized a previous duplicate, then this also covers forward references to previously finalized duplicates.
Thanks, Roland
On Mon, 2011-02-14 at 17:26 -0800, Roland McGrath wrote:
So I am now looking at only calculating the local hash when we currently finalize, but don't put the items directly in the cache, but only after we scanned over the whole CU. That way when we do put the item in the cache, we can calculate the full hash because we can be sure that all dies that the reference attributes (recursively) points at have their local hash set.
I can't tell whether that sounds like exactly what I always thought the plan of the new algorithm was, or sounds like you're still not changing the old way of doing things enough.
I am probably not changing enough, trying to not disturb the current setup too much.
"When we currently finalize" is based on all the dismal hairy bookkeeping that we ought to be getting rid of.
yeah, I am probably just bad at splitting out the necessary versus dismal hairy parts.
In initial cut of the new plan, nothing actually gets finalized until the whole CU is being finalized.
So, the reason that I didn't do that directly was because only when we finalize, do we create a die_info, which is necessary to hold the local hash for each input die we transform to an output die and put into the collector.
On my branch I now delay finalization till the whole CU is done in final_unit (). In defined_self () a die_info with the local hash is created (at which point all children exist and have their local hash set). Then when the entry gets finalized all referenced entries already have a die_info with a local hash set which can be used in calculating the final hash.
This works for the small examples in tests/dwarf_edit_output. The attributes_type hash is now calculated using all the local hashes of the referenced dies in the attributes.
For the bigger examples in the testsuite with dwarfcmp-test -T it will fail with a logic_error since it dwarfcmp detects that the input and dwarf_output aren't equal. Next up is looking into that (I believe most of these self-tests with dwarfcmp did also fail before/on the dwarf branch proper).
Cheers,
Mark
I am probably not changing enough, trying to not disturb the current setup too much.
The current setup is the problem. Changing is the solution.
"When we currently finalize" is based on all the dismal hairy bookkeeping that we ought to be getting rid of.
yeah, I am probably just bad at splitting out the necessary versus dismal hairy parts.
Talking it out can help.
Thanks, Roland
elfutils-devel@lists.fedorahosted.org