Re: [Bug default/26646] unexpected declaration-only types

[Giuliano Procida <gprocida@google.com>]

(Not sure what's going on with the addresses, I've added back libabigail here.)

Hi.

On Wed, 2 Mar 2022 at 13:34, dodji at seketeli dot org
<sourceware-bugzilla@sourceware.org> wrote:
>
> https://sourceware.org/bugzilla/show_bug.cgi?id=26646
>
> --- Comment #31 from dodji at seketeli dot org ---
> Dodji Seketeli via Libabigail <libabigail@sourceware.org> a écrit:
>
> [...]
>
>
> > This addresses https://sourceware.org/bugzilla/show_bug.cgi?id=26646#c21.
> >
> >       * src/abg-dwarf-reader.cc (compare_dies): Do not propagate
> >       canonical type when aggregate redundancy is detected.
> >
>
> [...]
>
> gprocida at google dot com via Libabigail <libabigail@sourceware.org> a
> écrit:
>
> [...]
>
> > I've thought a little bit more about this one.
> >
> > The current check is "local", recursion prevention at *this* DIE
> > prevents it from being canonicalised, but it could still depend on
> > child DIEs that are actually also parent DIEs and whose processing has
> > not yet been completed.
>
> You are right.  The current state is an improvement, but it's not
> "complete".  Some DIEs might still wrongly considered as being
> equivalent just because they depend on a "recursive DIE" that was
> detected as such.  The canonical DIE propagation might have happened
> during the window of time where the recursive DIE was comparing equal to
> its counterpart.
>
> This is addressed in the IR type canonicalization algorithm in
> abg-ir.cc.
> To learn more about this, look for
> /// @defgroup OnTheFlyCanonicalization On-the-fly Canonicalization
>
> and that comment.
>
> The implementation is scattered in the functions
> return_comparison_result, maybe_propagate_canonical_type and in the
> macro RETURN_TRUE_IF_COMPARISON_CYCLE_DETECTED.
>
> More on this below ...
>
> > Would it be safer (more precise) to inhibit on-the-fly
> > canonicalisation whenever the set (stack) of aggregates being compared
> > is non-empty?
>
> Right, that is the obvious thing to do, as I thought.  But then the
> problem I encountered, when doing this for IR types, was that things
> were too slow.  Really really slow.  In the time window where the
> canonical type DIE is inhibited, the amount of (quadratic) structural
> DIE comparisons goes through the roof.  That is why I came up with the
> canonical type propagation in the first place.
>
> So, the other (harder) approach I've taken is to not disable the
> on-the-fly canonicalization when the stack of aggregates being compared
> is non-empty, but rather, keep track of the types which are resolved as
> being equivalent, but that depend on recursive aggregate that were
> detected as such.
>
> I call these types "dependent types".  Let's consider one such dependent
> type D.  D's canonical type is the result of canonical propagation that
> happened as the recursive type (that D depends on) was on the stack of
> aggregates being compared.  D is labelled as having a "non-confirmed"
> canonical type.  If the recursive type it depends on is later considered
> not being equivalent to its counterpart, then the non-confirmed
> canonical of D is going to be "cancelled" and then D is going to be
> considered as being non canonicalized.
>
> This is done for D and all the types that depends on it.
>
> By doing this, the number of non canonicalized types is reduced to its
> absolute minimum and so comparisons are reasonably fast, even for an
> applications like the Kernel or Gimp.  Libraries usually have smaller
> type graphs so we don't usually see the speed issue there.  Unless it's
> llvm.so or libwebkit.so ;-)
>
> So, I wasn't going to get into doing this for DIEs right away because it
> takes a lot of time doing careful coding/debugging/profiling cycles.
>
> But I definitely think we'll need to do this to have perfectly precise
> canonicalizer.  My point was to get this in as it's an improvement
> already and then work on the subsequent patch with a cooler head.
>
> Does that make any sense?
>

I think it makes some sense, but it would take me some time to read
through, digest and reason about this properly.

Instead... I'm going to advertise my comparison algorithm again (for
which I've already done all the hard thinking and testing). :-) I'm
not sure how directly applicable it is to canonicalisation, but there
is the *potential* to eliminate all redundant comparisons.

Problem statement: How to decide if two DIEs (let's call them nodes)
are equivalent, when nodes can depend on other nodes recursively and
with cycles, without comparing each pair of nodes more than once.

Nodes can have attributes (like kind (struct, union), size etc.) and
labelled edges (like member x of type y, pointer to type z etc.).
Equivalence means that node attributes are equivalent, nodes have the
same edge labels and following matching labelled edges finds
equivalent nodes.

The C and C++ type systems have various wrinkles, but the overall
structure of equivalence testing involves this kind of matching of
attributes and following edges to other nodes.

Equivalence of two nodes means we cannot find any difference, no
matter at what depth we decide to terminate recursion.

The algorithm has the following components.

1. a "known results" map from comparisons (node pairs) to equivalence
results (bool) - I think the equivalent thing in libabigail may be
on-the-fly canonicalisation itself, but this only stores true
equivalences for a subset of types and it may be better to cache all
outcomes; this needs to be part of reader_context
2. the path-based strongly-connected component algorithm factored into
2 helper functions and associated shared state (which should also be
part of the reader context) - these replace the
aggregates_being_compared data structure and its access functions
3. a comparison function that uses the data structures and helper
functions at the beginning and end with per-kind comparison logic
sandwiched in the middle (this is compare_dies)

If no comparison cycles are possible then a simple DFS works, however,
it's good to cache computed comparisons to avoid repeated work (in
case the DFS traverses a DAG rather than a tree). Such a comparison
function looks like this:

1. Check for a known result, and if present return it (this is a bit
like a check for an existing canonical DIE but additionally handles
the case where the DIEs are already known to be non-equivalent).
2. [doesn't exist yet]
3. Now do the actual comparison work updating result to false if a
difference is found (exactly as at present).
4. [doesn't exist yet]
5. Insert (comparison, result) into "known results".
6. Return result.

If cycles are possible, this DFS will go into an infinite loop (and
crash with a stack overflow). The comparison function needs to be
updated:

1. Check for a known result, and if present return it (this is a bit
like a check for an existing canonical DIE but additionally handles
the case where the DIEs are already known to be non-equivalent).
2. Call the first SCC helper to see if the comparison is already in
progress (this is a bit like the aggregates-being-compared check).
2a. If the SCC helper says the comparison is progress, return a
tentative "true" (equals) result (this is very similar to what happens
for aggregates, but it can be done for all kinds of DIE).
2b. Otherwise the SCC helper has returned an index which *must* be
used before returning from the comparison function.
3. Now do the actual comparison work updating result to false if a
difference is found (exactly as at present - though I did notice one
stray early return false which needs to be changed to result = false).
4. Pass the index to the second SCC helper function which returns a
set of comparisons.
4a. The empty set implies that comparisons are still in progress.
4b. A non-empty set means a strongly-connected component has been
found and all of its comparisons have completed.
5. Insert (comparison, result) into "known results" for each
comparison in the set.
6. Return result.

I'm not exactly sure what this means in terms of
on-the-fly-canonicalisation. I tried adapting the code at the end of
compare_dies that performs canonicalisation but something broke
somewhere. I also tried skipping on-the-fly canonicalisation
altogether but that didn't work either. So, just dropping in the SCC
helper and moving a small amount of code around doesn't quite work.
It's possible I need to fix how I got back from DIE offsets to DIEs.

I've noted similarities between the SCC approach and what you have in
place already. The SCC approach guarantees no repeated comparisons, so
it would be really great if it could be applied to the DWARF reader.

My SCC helper code is here:
https://cs.android.com/android/kernel/superproject/+/build-tools:external/stg/scc.h

A concrete comparison algorithm using the SCC helper is here (it
actually builds ABI diffs in this case, but that extra logic can be
ignored):
https://cs.android.com/android/kernel/superproject/+/build-tools:external/stg/stg.cc;drc=3b6b65e1a9190dab2eabb98701a716a895b8a7b1;l=366

I'll post a cleaned-up version of my attempt to integrate this code
tomorrow with notes about where the test suite blows up.

Cheers,
Giuliano.

> Thanks.
>
> --
> You are receiving this mail because:
> You reported the bug.