Re: new dwarf_output algorithm

[Roland McGrath <roland at redhat dot com>]

> 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