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.
Indeed. But recall that this hash is imperfect. Hence, we will always
need to fall back of "full comparison". In fact, each detection of an
authentic duplicate will involve at least one full comparison to verify
that the hash match is a true equivalence and not just a collision. So,
this scheme still relies on having a sound equivalence comparison algorithm
that does not have pathological performance.
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).
Correct.
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.
Yes, these are different ways of saying the same thing. The "first walk"
is the "copy construction" proper, where the navigation is directly via the
input DIE tree structure. This creates a 'struct entry' for each node
(that is, dwarf_output::copier::entry). The second walk is the
finalization pass, triggered where we now have the call to 'final_unit'.
Here the navigation is via the 'struct entry' graph.
That graph exists in bifurcated ways. When an entry is already finalized,
there is entry._m_final pointing to its collector object. This will arise
in the finalization pass in two ways. One is if we do some short-circuit
logic to do immediate finalization during the first walk when it's easy.
The second is when the input data already used DW_TAG_imported_unit, so
that the same input DIE identity appears more than once in the input tree.
(This latter possibility is the main reason why 'struct entry' lives for
the entire life of the copier, i.e. the whole walk of all CUs in an input
file, or later even multiple input files, rather than only living until
that entry is final.)
During the first walk, entry._m_pending holds is (that is,
dwarf_output::copier::pending_entry). Right now it has a whole attributes
map and children vector of its own. That allows quick enumeration at the
cost of more storage. It would also be possible instead to just hold the
input DIE pointer (i.e. debug_info_entry::children_type::const_iterator of
the input dwarf-like class). Then enumerating the children for the
finalization pass would entail walking the input DIE's children list again
and doing the _m_entries lookup (hash table on identity) again for each.
We can see later on how that CPU vs memory tradeoff looks in practice.
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.
I think I prefer the terms "copier hash" and "final hash" for these,
not that it really matters which terms we use.
(These two are different from the use pointer as hash recently
discussed
on the list.)
Hmm, calling the "references-hash" the "final hash" implies/presumes
that
this hash function is the same one that we use for the collector's hash
table. So perhaps that's not a good term to use, at least not yet.
- 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).
Let's call this the "local hash" of a DIE.
- The children-hash of a DIE with children is the same as one
without,
combined with all children-hashes of its children.
An equivalent way to state it would be to say that the copier hash of any
DIE is its local hash combined with the copier hashes of each child. Note
that this is slightly different from the approach of the current DIE hash
function, where the local hash is combined with a single "children_type
hash". The latter is itself the combination of the hashes of each child.
The difference is x vs hash_combine (x, 0) for a childless DIE.
- 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.
Again, we could either define it this way, or that the final hash is the
local hash combined with the "references list hash". Again, the difference
is whether for a DIE without references the final hash is exactly the
copier hash or is hash_combine (copier_hash, 0).
I'm not sure whether it really makes a difference to the bit distribution
or not. It just makes a difference to how you organize the control flow of
the computation, in a subtle way that is easily overlooked.
- 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.
Right.
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.
I haven't noticed anything you forgot. The things I mentioned above are
some implementation details you didn't mention, but not material issues.
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).
Right. The existing code has machinery that detects cycles akin to these.
So it should be moderately clear how to turn entry_finalizer into just
doing this. For now, we can just make it throw an exception when a cycle
is detected. If it ever comes up in real-world data, we'll have to
consider the subject more deeply.
Thanks,
Roland