From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from relay7-d.mail.gandi.net (relay7-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::227]) by sourceware.org (Postfix) with ESMTPS id 4C8373858D20 for ; Tue, 1 Mar 2022 17:46:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4C8373858D20 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=seketeli.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=seketeli.org Received: (Authenticated sender: dodji@seketeli.org) by mail.gandi.net (Postfix) with ESMTPSA id 69D9520002; Tue, 1 Mar 2022 17:46:00 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id B3288581C3A; Tue, 1 Mar 2022 18:45:59 +0100 (CET) From: Dodji Seketeli To: Dodji Seketeli via Libabigail Cc: gprocida@google.com, Dodji Seketeli Subject: Re: [PATCH 1/2 / RFC] Bug 26646 - unexpected declaration-only types (part 2) Organization: Me, myself and I References: <87wnhfjpwt.fsf@redhat.com> X-Operating-System: Fedora 36 X-URL: http://www.seketeli.net/~dodji Date: Tue, 01 Mar 2022 18:45:59 +0100 In-Reply-To: <87wnhfjpwt.fsf@redhat.com> (Dodji Seketeli via Libabigail's message of "Mon, 28 Feb 2022 10:34:10 +0100") Message-ID: <87zgm9in1k.fsf@seketeli.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 01 Mar 2022 17:46:10 -0000 Hey Giuliano, Thank you for reviewing the patch! Dodji Seketeli via Libabigail a =C3=A9crit: [...] > * 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 a =C3=A9crit: > 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 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=3D26646#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 --- 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 addr= _elf_symbol_sptr_map_type; /// Convenience typedef for a set of ELF addresses. typedef unordered_set address_set_type; =20 -typedef unordered_set istring_set_t= ype; +/// 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& p) const + {return abigail::hashing::combine_hashes(p.first, p.second);} +};// end struct dwarf_offset_pair_hash + +typedef unordered_set, + dwarf_offset_pair_hash> dwarf_offset_pair_set_type; =20 /// Convenience typedef for a shared pointer to an @ref address_set_type. typedef shared_ptr address_set_sptr; @@ -297,6 +308,12 @@ get_scope_die(const read_context& ctxt, size_t where_offset, Dwarf_Die& scope_die); =20 +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); =20 @@ -6230,6 +6247,24 @@ void set_do_log(read_context& ctxt, bool f) {ctxt.do_log(f);} =20 +/// 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(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 &c= txt, && llinkage_name =3D=3D rlinkage_name); } =20 +/// 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 p(p1, p2); + if (set.find(p) !=3D 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_Of= f p2) +{set.insert(std::pair(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 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 &ct= xt, 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 =3D ctxt.get_die_pretty_type_representation(l, 0); - interned_string rn =3D ctxt.get_die_pretty_type_representation(r, 0); - - if ((aggregates_being_compared.find(ln) - !=3D aggregates_being_compared.end()) - || (aggregates_being_compared.find(rn) - !=3D aggregates_being_compared.end())) + if (has_offset_pair(aggregates_being_compared, + die_offset(l), die_offset(r))) result =3D true; - else if (!compare_as_decl_dies(l, r)) - result =3D false; - else if (!compare_as_type_dies(l, r)) + else if (!compare_as_decl_dies(l, r) || !compare_as_type_dies(l, r)) result =3D 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 =3D dwarf_child(const_cast(l), @@ -10316,8 +10388,8 @@ compare_dies(const read_context& ctxt, if (found_l_member !=3D found_r_member) result =3D false; =20 - 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 =3D ctxt.get_die_pretty_type_representation(l, 0); interned_string rn =3D ctxt.get_die_pretty_type_representation(r, 0); =20 - if ((aggregates_being_compared.find(ln) - !=3D aggregates_being_compared.end()) - || (aggregates_being_compared.find(rn) - !=3D aggregates_being_compared.end())) + if (has_offset_pair(aggregates_being_compared, die_offset(l), + die_offset(r))) { result =3D true; break; @@ -10498,8 +10568,8 @@ compare_dies(const read_context& ctxt, } } =20 - aggregates_being_compared.erase(ln); - aggregates_being_compared.erase(rn); + erase_offset_pair(aggregates_being_compared, + die_offset(l), die_offset(r)); } break; =20 @@ -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 =3D 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 =3D 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); } --=20 2.35.0.rc2 --=20 Dodji