From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd30.google.com (mail-io1-xd30.google.com [IPv6:2607:f8b0:4864:20::d30]) by sourceware.org (Postfix) with ESMTPS id 5CC743858D39 for ; Wed, 2 Mar 2022 09:28:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5CC743858D39 Received: by mail-io1-xd30.google.com with SMTP id w7so1161772ioj.5 for ; Wed, 02 Mar 2022 01:28:56 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=USWHdVfeoCOR0nvNhkgXru52OYO/J1rEJ/yb5PQN1UE=; b=ta3df6Lz47C0ujwor5a0UYRK+CB9PbqthakjUN1R7O6SlgrU3g8zMTe9MzEir3pe5L V3XqJpiIYEfy0vwaolFiI/ha3jIUA2b1HNY7wnIvKxLclIaxDj5apqCYhSi8vvLL+rwI VK7FR7/BZOX6SE6Q6WlgfvqqJw5S3vItp6GbMQr4d2Km9GurW29KfttPK/M7rMDi9Sv4 85Phy4zZllMUi+582A2X5+t/vAwL7eK9ZSa/rtQiz4jgX3k3iETgznvOC1Yuwls+svQD d4Jw642BZySbHdea2tjfXYCnqPguzsPWKQMhLpaiTtxwuVM3XbwvhlGGfcws1cYJaoM+ O17A== X-Gm-Message-State: AOAM532IlgrefXAbRvR7RH1gTDGtxOzH45bmgW11n8WwPQxI+CricRrb ij2ZDWEfJPp5iJ2bJKqoTJ4TeBpRNqYGktvU+WE5oQ== X-Google-Smtp-Source: ABdhPJx3Dq0oxkaLZjhc8skq1Fc0VafLLBA1Oq3Zmhn5WHsr/2b1jqOj2jY1nAZSTuGn6672D4tG2rY0DIdFwPJFBwg= X-Received: by 2002:a05:6638:346f:b0:30e:149c:4dbb with SMTP id q47-20020a056638346f00b0030e149c4dbbmr26337391jav.31.1646213335298; Wed, 02 Mar 2022 01:28:55 -0800 (PST) MIME-Version: 1.0 References: <87wnhfjpwt.fsf@redhat.com> <87zgm9in1k.fsf@seketeli.org> In-Reply-To: <87zgm9in1k.fsf@seketeli.org> From: Giuliano Procida Date: Wed, 2 Mar 2022 08:58:05 +0000 Message-ID: Subject: Re: [PATCH 1/2 / RFC] Bug 26646 - unexpected declaration-only types (part 2) To: Dodji Seketeli Cc: Dodji Seketeli via Libabigail , Dodji Seketeli X-Spam-Status: No, score=-27.5 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, ENV_AND_HDR_SPF_MATCH, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL, USER_IN_DEF_SPF_WL autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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: Wed, 02 Mar 2022 09:28:59 -0000 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, wrote: > 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 th= e > > 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 an= d > > 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 th= e > 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 an= d > 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; > > -typedef unordered_set > 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& p) const > + {return abigail::hashing::combine_hashes(p.first, p.second);} > +};// end struct dwarf_offset_pair_hash > + > +typedef unordered_set + 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_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(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 =3D=3D 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 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_Off 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 > &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 =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; > > - 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); > > - 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, > } > } > > - 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 =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); > } > -- > 2.35.0.rc2 > > > -- > Dodji >