[PATCH 1/2 / RFC] Bug 26646 - unexpected declaration-only types (part 2)
Giuliano Procida
gprocida@google.com
Wed Mar 2 08:58:05 GMT 2022
Answering on phone.
This looks fine. You might be able to shorten things a bit with make_pair
but that's just code style.
Giuliano.
On Tue, 1 Mar 2022, 17:46 Dodji Seketeli, <dodji@seketeli.org> wrote:
> Hey Giuliano,
>
> Thank you for reviewing the patch!
>
> Dodji Seketeli via Libabigail <libabigail@sourceware.org> a écrit:
>
> [...]
>
> > * src/abg-dwarf-reader.cc (struct dwarf_offset_pair_hash)
> > (dwarf_offset_pair_set_type): Define new type.
> > (die_offset, has_offset_pair, insert_offset_pair)
> > (erase_offset_pair): Define new static helper functions.
> > (compare_dies): Use a set of DWARF offsets for the
> > 'aggregates_being_compared' data structure, rather than a set of
> > string representation of the DIEs. Always look at the size of the
> > types being compared first so that we can get out quickly if they
> > differ. For DIEs of DW_TAG_{union,struct}_type kind, don't limit
> > the depth of the stack of DIEs being compared to 5; so we don't
> > consider two types as being equal just because the depth of the
> > stack being compared is 5 and the two types have the same size and
> > are equal. Hopefully things don't take too long.
> >
>
> OK, you actually posted your comment as a bugzilla comment which is
> fine. As I'd like the review to be found by people reading the patch
> post as well, I am replying it here.
>
> [...]
>
> gprocida at google dot com via Libabigail <libabigail@sourceware.org> a
> écrit:
>
> > Two (overlapping) things:
> >
> > 1. I wouldn't bother with inserting / testing / erasing the reverse
> > pair o(p2, p1)
> >
> > It might cost more than it ever saves. But it would take
> > instrumentation to see if it ever makes a difference.
> >
> > If you make this change then s/unordered pair/ordered pair/ in the doc
> > comments.
>
> OK, I am going with your inclination here. I updated the patch
> accordingly.
>
> > 2. There is a typo.
> >
> > One of the reverse pairs is written as o(p2, 1).
>
> Good catch. Thanks. Updated.
>
> > Otherwise, it looks good to me.
>
> Thanks. I am posting an updated version of the patch below.
>
> From 3b67a367ce6b8a141f0cb29a130c002ca7b984eb Mon Sep 17 00:00:00 2001
> From: Dodji Seketeli <dodji@redhat.com>
> Date: Thu, 10 Feb 2022 17:43:38 +0100
> Subject: [PATCH 1/2] Bug 26646 - unexpected declaration-only types (part 2)
>
> This patch addresses the comment
> https://sourceware.org/bugzilla/show_bug.cgi?id=26646#c15 of the
> reported problem.
>
> The core of the problem seems to be that when compare_dies compares
> two DW_TAG_{structure,union}_type, it "gives up" when the comparison
> stack contains more than 5 such DIEs being compared. Giving up means
> that it considers the two DIEs to be equivalent if they have the same
> size and kind, basically. This is to avoid infinite loops or too long
> loops that we've seen with artificial DWARF input generated by
> fuzzers.
>
> This patch fixes that by better using the "aggregates_being_compared"
> data structure that is meant to prevent looping infinitely over
> aggregate DIEs that might be recursively defined. That data structure
> now contains the DWARF offset pairs of the DIEs being compared, rather
> than their "string representation". Lookups in that data structure
> should now be faster and more precise.
>
> The artificial limit of the comparison stack not having more than 5
> DIEs is now lifted.
>
> * src/abg-dwarf-reader.cc (struct dwarf_offset_pair_hash)
> (dwarf_offset_pair_set_type): Define new type.
> (die_offset, has_offset_pair, insert_offset_pair)
> (erase_offset_pair): Define new static helper functions.
> (compare_dies): Use a set of DWARF offsets for the
> 'aggregates_being_compared' data structure, rather than a set of
> string representation of the DIEs. Always look at the size of the
> types being compared first so that we can get out quickly if they
> differ. For DIEs of DW_TAG_{union,struct}_type kind, don't limit
> the depth of the stack of DIEs being compared to 5; so we don't
> consider two types as being equal just because the depth of the
> stack being compared is 5 and the two types have the same size and
> are equal. Hopefully things don't take too long.
>
> Signed-off-by: Dodji Seketeli <dodji@redhat.com>
> ---
> src/abg-dwarf-reader.cc | 135 +++++++++++++++++++++++++++++-----------
> 1 file changed, 98 insertions(+), 37 deletions(-)
>
> diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
> index 53b5845d..18f49037 100644
> --- a/src/abg-dwarf-reader.cc
> +++ b/src/abg-dwarf-reader.cc
> @@ -161,7 +161,18 @@ typedef unordered_map<GElf_Addr, elf_symbol_sptr>
> addr_elf_symbol_sptr_map_type;
> /// Convenience typedef for a set of ELF addresses.
> typedef unordered_set<GElf_Addr> address_set_type;
>
> -typedef unordered_set<interned_string, hash_interned_string>
> istring_set_type;
> +/// A hasher for a pair of Dwarf_Off. This is used as a hasher for
> +/// the type @ref dwarf_offset_pair_set_type.
> +struct dwarf_offset_pair_hash
> +{
> + size_t
> + operator()(const std::pair<Dwarf_Off, Dwarf_Off>& p) const
> + {return abigail::hashing::combine_hashes(p.first, p.second);}
> +};// end struct dwarf_offset_pair_hash
> +
> +typedef unordered_set<std::pair<Dwarf_Off,
> + Dwarf_Off>,
> + dwarf_offset_pair_hash> dwarf_offset_pair_set_type;
>
> /// Convenience typedef for a shared pointer to an @ref address_set_type.
> typedef shared_ptr<address_set_type> address_set_sptr;
> @@ -297,6 +308,12 @@ get_scope_die(const read_context& ctxt,
> size_t where_offset,
> Dwarf_Die& scope_die);
>
> +static Dwarf_Off
> +die_offset(Dwarf_Die* die);
> +
> +static Dwarf_Off
> +die_offset(const Dwarf_Die* die);
> +
> static bool
> die_is_anonymous(const Dwarf_Die* die);
>
> @@ -6230,6 +6247,24 @@ void
> set_do_log(read_context& ctxt, bool f)
> {ctxt.do_log(f);}
>
> +/// Get the offset of a DIE
> +///
> +/// @param die the DIE to consider.
> +///
> +/// @return the offset of the DIE.
> +static Dwarf_Off
> +die_offset(Dwarf_Die* die)
> +{return dwarf_dieoffset(die);}
> +
> +/// Get the offset of a DIE
> +///
> +/// @param die the DIE to consider.
> +///
> +/// @return the offset of the DIE.
> +static Dwarf_Off
> +die_offset(const Dwarf_Die* die)
> +{return die_offset(const_cast<Dwarf_Die*>(die));}
> +
> /// Test if a given DIE is anonymous
> ///
> /// @param die the DIE to consider.
> @@ -10097,6 +10132,51 @@ fn_die_equal_by_linkage_name(const read_context
> &ctxt,
> && llinkage_name == rlinkage_name);
> }
>
> +/// Test if the pair of offset {p1,p2} is present in a set.
> +///
> +/// @param set the set of pairs of DWARF offsets to consider.
> +///
> +/// @param p1 the first value of the pair.
> +///
> +/// @param p2 the second value of the pair.
> +///
> +/// @return if the pair {p1,p2} is present in the set.
> +static bool
> +has_offset_pair(const dwarf_offset_pair_set_type& set,
> + Dwarf_Off p1, Dwarf_Off p2)
> +{
> + std::pair<Dwarf_Off, Dwarf_Off> p(p1, p2);
> + if (set.find(p) != set.end())
> + return true;
> + return false;
> +}
> +
> +/// Insert a new pair of offset into the set of pair.
> +///
> +/// @param set the set of pairs of DWARF offsets to consider.
> +///
> +/// @param p1 the first value of the pair.
> +///
> +/// @param p2 the second value of the pair.
> +static void
> +insert_offset_pair(dwarf_offset_pair_set_type& set, Dwarf_Off p1,
> Dwarf_Off p2)
> +{set.insert(std::pair<Dwarf_Off, Dwarf_Off>(p1, p2));}
> +
> +/// Erase a pair of DWARF offset from a set of pairs.
> +///
> +///
> +/// @param set the set of pairs of DWARF offsets to consider.
> +///
> +/// @param p1 the first value of the pair.
> +///
> +/// @param p2 the second value of the pair.
> +static void
> +erase_offset_pair(dwarf_offset_pair_set_type& set, Dwarf_Off p1,
> Dwarf_Off p2)
> +{
> + std::pair<Dwarf_Off, Dwarf_Off> p(p1, p2);
> + set.erase(p);
> +}
> +
> /// Compare two DIEs emitted by a C compiler.
> ///
> /// @param ctxt the read context used to load the DWARF information.
> @@ -10123,7 +10203,7 @@ fn_die_equal_by_linkage_name(const read_context
> &ctxt,
> static bool
> compare_dies(const read_context& ctxt,
> const Dwarf_Die *l, const Dwarf_Die *r,
> - istring_set_type& aggregates_being_compared,
> + dwarf_offset_pair_set_type& aggregates_being_compared,
> bool update_canonical_dies_on_the_fly)
> {
> ABG_ASSERT(l);
> @@ -10268,23 +10348,15 @@ compare_dies(const read_context& ctxt,
> case DW_TAG_structure_type:
> case DW_TAG_union_type:
> {
> - interned_string ln = ctxt.get_die_pretty_type_representation(l, 0);
> - interned_string rn = ctxt.get_die_pretty_type_representation(r, 0);
> -
> - if ((aggregates_being_compared.find(ln)
> - != aggregates_being_compared.end())
> - || (aggregates_being_compared.find(rn)
> - != aggregates_being_compared.end()))
> + if (has_offset_pair(aggregates_being_compared,
> + die_offset(l), die_offset(r)))
> result = true;
> - else if (!compare_as_decl_dies(l, r))
> - result = false;
> - else if (!compare_as_type_dies(l, r))
> + else if (!compare_as_decl_dies(l, r) || !compare_as_type_dies(l,
> r))
> result = false;
> else
> {
> - aggregates_being_compared.insert(ln);
> - aggregates_being_compared.insert(rn);
> -
> + insert_offset_pair(aggregates_being_compared,
> + die_offset(l), die_offset(r));
> Dwarf_Die l_member, r_member;
> bool found_l_member, found_r_member;
> for (found_l_member = dwarf_child(const_cast<Dwarf_Die*>(l),
> @@ -10316,8 +10388,8 @@ compare_dies(const read_context& ctxt,
> if (found_l_member != found_r_member)
> result = false;
>
> - aggregates_being_compared.erase(ln);
> - aggregates_being_compared.erase(rn);
> + erase_offset_pair(aggregates_being_compared,
> + die_offset(l), die_offset(r));
> }
> }
> break;
> @@ -10402,10 +10474,8 @@ compare_dies(const read_context& ctxt,
> interned_string ln = ctxt.get_die_pretty_type_representation(l, 0);
> interned_string rn = ctxt.get_die_pretty_type_representation(r, 0);
>
> - if ((aggregates_being_compared.find(ln)
> - != aggregates_being_compared.end())
> - || (aggregates_being_compared.find(rn)
> - != aggregates_being_compared.end()))
> + if (has_offset_pair(aggregates_being_compared, die_offset(l),
> + die_offset(r)))
> {
> result = true;
> break;
> @@ -10498,8 +10568,8 @@ compare_dies(const read_context& ctxt,
> }
> }
>
> - aggregates_being_compared.erase(ln);
> - aggregates_being_compared.erase(rn);
> + erase_offset_pair(aggregates_being_compared,
> + die_offset(l), die_offset(r));
> }
> break;
>
> @@ -10535,19 +10605,10 @@ compare_dies(const read_context& ctxt,
> Dwarf_Die l_type, r_type;
> ABG_ASSERT(die_die_attribute(l, DW_AT_type, l_type));
> ABG_ASSERT(die_die_attribute(r, DW_AT_type, r_type));
> - if (aggregates_being_compared.size () < 5)
> - {
> - if (!compare_dies(ctxt, &l_type, &r_type,
> - aggregates_being_compared,
> - update_canonical_dies_on_the_fly))
> - result = false;
> - }
> - else
> - {
> - if (!compare_as_type_dies(&l_type, &r_type)
> - ||!compare_as_decl_dies(&l_type, &r_type))
> - return false;
> - }
> + if (!compare_dies(ctxt, &l_type, &r_type,
> + aggregates_being_compared,
> + update_canonical_dies_on_the_fly))
> + result = false;
> }
> }
> else
> @@ -10661,7 +10722,7 @@ compare_dies(const read_context& ctxt,
> const Dwarf_Die *r,
> bool update_canonical_dies_on_the_fly)
> {
> - istring_set_type aggregates_being_compared;
> + dwarf_offset_pair_set_type aggregates_being_compared;
> return compare_dies(ctxt, l, r, aggregates_being_compared,
> update_canonical_dies_on_the_fly);
> }
> --
> 2.35.0.rc2
>
>
> --
> Dodji
>
More information about the Libabigail
mailing list