[PATCH 1/1] abg-writer.cc: Track types by plain address

[Giuliano Procida]

Hi there.

The patch was sent before I read your reply to my other message about
anonymous types, but my reply here addresses both.

On Wed, 5 Aug 2020 at 06:38, Dodji Seketeli <dodji@seketeli.org> wrote:
>
> Giuliano Procida <gprocida@google.com> a écrit:
>
> > The XML writer tracks the state of referenced and emitted types so it
> > can emit the right types with no repetitions or omissions.
> >
> > The sets and maps are keyed using type_hasher and deep_ptr_eq_functor,
> > effectively resulting in structural equality checks in some cases.
> >
> > The helper function type_is_emitted looks up types in a set but the
> > corresponding record_type_as_emitted stores the canonical pointer
> > where possible.
>
> AFAIU, the look-up process of type_is_emitted uses the canonical type of
> the type stored in the set.  So record_type_as_emitted storing the
> canonical pointer should not be a problem.
>
> > Any discrepancy between structural and canonical equality may result
> > in types being treated as emitted when there are not or vice versa,
> > resulting in duplicate or omitted type ids.
>
> There should not be a discrepancy between structural canonical equality.
> If there is, then it's a bug that ought to be fixed at that level.
>
> > Together, the result is that some types are unexpectedly conflated.
>
> I'd like to see an example binary of that, please.  If two types are
> structurally equivalent, it's expected that they are treated equal, for
> ABI purposes.  And so, only one instance of that type is kept in the
> resulting abixml, by design.  I am not sure what you mean by "conflated"
> would be pathological in that case.  If it is, then I suspect there is
> an underlying problem that ought to be fixed.
>
> > Also, depending on the toolchain and libraries, some types are not
> > emitted even when referred to elsewhere in the XML.
> >
> >       * src/abg-writer.cc (writer_context): Change type_ptr_map,
> >       type_ptr_set_type and fn_type_ptr_set_type to use plain
> >       pointer equality and hashing. (type_is_emitted): Look up
> >       canonical type if it exists, to match record_type_as_emitted,
> >       get_id_for_type etc.
>
> Doing this looks like papering over an underlying issue that would need
> to be fixed.  If that is possible, I'd prefer to have access to the
> binary that reveals the issue so I can have a look at it.
>

There is probably^Wdefinitely (see below) an underlying issue. I did
post a patch [https://sourceware.org/pipermail/libabigail/2020q3/002573.html]
a week or two ago to show how there were inconsistencies between
canonical and structural equality. If those issues carry over into the
XML writer (whether directly or via a broken equality / hash contract)
then that could be the reason. Equality is not a simple thing in
libabigail and that is a concern whenever it's relied on for data
structure or algorithm correctness (as opposed to business logic).

I think I can raise a few arguments against the current behaviour of
the XML writer. There may be some holes in them. Comments welcome.

The first is the most fundamental. I would argue that equating
distinct but isomorphic types has the following downsides:

* It is done specially for anonymous types (which C and C++ treat as
having unique but unknowable names) and not for named types.
* It is not faithful to language level semantics - such types are distinct.
* It is surprising to users (well, at least one user) of libabigail.
* If one anonymous type in an isomorphic set changes, it's not clear
what the abidiff output is going to look like - it may depend on the
order the XML writer saw the types at the time of serialisation.
* C++ distinguishes such anonymous types when it comes to producing
mangled names for them (presumably when used in template
instantiations etc.) and this is a distinction notable, in some sense,
at the ABI level.

The second relates to separation of responsibilities. Simply, I don't
think this logic belongs in the XML writer.

* If types need to be identified with each other, it should happen
before ABI serialisation.
* The DWARF reader already contains logic that compares and identifies types.
* BTF (BPF Type Format) is a nascent alternative to DWARF for kernel
type information. BTF consists of a single unified graph of symbols
and types. It's up to whatever produces the BTF to decide which
(possibly anonymous, possibly identically-named) types are in fact the
same type. If we were to process BTF, we wouldn't want to start
merging types at the point of serialisation.

The third argument is entirely pragmatic. Without guaranteed
consistency between equality, hashing and (to the extent that this is
relied on in various places) canonical types, code that stores types
in hash tables is just not safe (and a similar statement can be made
about ordered trees).

This circles back to the existence of an underlying issue. I think
it's fair to say I have spent weeks of effort investigating type
equality issues in libabigail but I have happily spent a little more
time determining which specific types and hashes resulted in the
failed insertion that resulted in ill-formed XML.

We unfortunately cannot send you an internal (built with Clang and
linked to libc++) binary. :-/ We have seen bad XML output with both
proprietary and AOSP kernel builds, but not as yet with a plain
GCC/libstdc++ abidw.

Here are the debugging details.

record_type_as_referenced is passed a type
it's an instance of "union { }" nested in a struct - these can appear
in the kernel if their content is #if optional
m_referenced_non_canonical_types_set.insert is called and fails, b'cos:
* the type has hash code 4146663795 (and has an internal name of
"__anonymous_union__18")
* another type already in the set has hash code 3049540639 (and has an
internal name of "__anonymous_union__5")
* the hash codes modulo the hash table bucket count 97 are both 28
* the two types compare as equal

At a surface level the equals/hash contract is broken and this should
be fixed. Some extensive checking could be done to verify it's not
broken in other places, but given the complexity of "equals", that may
be some effort. It's possible that fixing this would make more
anonymous types be treated as equal (but see my arguments above).

Regards,
Giuliano

>
> Cheers,
>
> [...]
>
> --
>                 Dodji
>
> --
> To unsubscribe from this group and stop receiving emails from it, send an email to kernel-team+unsubscribe@android.com.
>