From patchwork Mon Feb 28 09:34:10 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dodji Seketeli X-Patchwork-Id: 51435 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A0AD3385841F for ; Mon, 28 Feb 2022 09:35:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A0AD3385841F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1646040921; bh=zBWm4lcgya9LZ+ak6t4mMfiv4MTvYR7zPsqzAywt414=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Help: List-Subscribe:From:Reply-To:Cc:From; b=J2mZcSob53iQgbmipztDR1wKQIwNNwYgZk1VV0CvArRKFRK4LfPxkGTn2I4Rn6BX0 yOAtLeeewCr725gPwkqPTs6cLQ3P0Vko9fz5qRA1FklSDm1sN4uFsfF4mzL+czRq3I lJqbF9sf9r5o2TLCkx0O5DR73cIUS+Kgv/nrSGh4= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 173C93858437 for ; Mon, 28 Feb 2022 09:34:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 173C93858437 Received: from mail-wm1-f70.google.com (mail-wm1-f70.google.com [209.85.128.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-341-Uusarae6MI-lyjzSpeBF7Q-1; Mon, 28 Feb 2022 04:34:21 -0500 X-MC-Unique: Uusarae6MI-lyjzSpeBF7Q-1 Received: by mail-wm1-f70.google.com with SMTP id c62-20020a1c3541000000b003815245c642so2468999wma.6 for ; Mon, 28 Feb 2022 01:34:21 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:organization:date:message-id :user-agent:mime-version; bh=zBWm4lcgya9LZ+ak6t4mMfiv4MTvYR7zPsqzAywt414=; b=VJDeMs7/aAKZiwb137PxzggwnGfimuKa9Pqo6IL24LgJ1DNq00mkalG4fjp9IefijZ MRW/ezhh3gACT+tbP6dgDoAcIZQwK1VyIb29wMbfg1BPp9fvwDtOMPtA1PjNbTi0gReA RhMmDmtHX0/GfvP1ZbTZ9p1Vsj3ocZYNPu/RbY3kRLxlBIn5qpIdSjBRCioH/XuRQOG7 Vho29up7X0rqwVYvKmxoLTXfw23y7f0nNdJfq1JQq8vC/yPRLKjKJAAzjQWxNIEoDv/0 Ya/TW+qvKQz/nJY+QwgD6EwlLmIBQ/De1KA0Eexyhjmr+yDBMZeJw7Gdg02l7Yb63nuj 1MEQ== X-Gm-Message-State: AOAM533iIqZYYyMBJpqM2CkSVWPFtz1W6TUFufj91rTjF1N/sYYHtBvI xFx04sRO09Dqlyd2NcvKCRVDt05Uznz5HwIP7DbrXnv2dnoIsiz2fYRSGUpcORwc/qYg91M9uBf pi2CE5x20zINLP5YMObM8 X-Received: by 2002:adf:8061:0:b0:1ea:9bf6:d54f with SMTP id 88-20020adf8061000000b001ea9bf6d54fmr14201352wrk.650.1646040860262; Mon, 28 Feb 2022 01:34:20 -0800 (PST) X-Google-Smtp-Source: ABdhPJxQX0yLe9pIvi8ucLEdIxFEssvFNGOuPTf5sKPHnTHMb2urGR371xKZbJrBET/sxNKN6Vj+HQ== X-Received: by 2002:adf:8061:0:b0:1ea:9bf6:d54f with SMTP id 88-20020adf8061000000b001ea9bf6d54fmr14201329wrk.650.1646040859942; Mon, 28 Feb 2022 01:34:19 -0800 (PST) Received: from localhost ([88.120.130.27]) by smtp.gmail.com with ESMTPSA id b9-20020a5d45c9000000b001ef9200b856sm5472951wrs.115.2022.02.28.01.34.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Feb 2022 01:34:19 -0800 (PST) Received: by localhost (Postfix, from userid 1000) id 70E7B5802B4; Mon, 28 Feb 2022 10:34:10 +0100 (CET) To: gprocida@google.com Subject: [PATCH 1/2 / RFC] Bug 26646 - unexpected declaration-only types (part 2) Organization: Red Hat / France X-Operating-System: Fedora 36 X-URL: http://www.redhat.com Date: Mon, 28 Feb 2022 10:34:10 +0100 Message-ID: <87wnhfjpwt.fsf@redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, 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-Patchwork-Original-From: Dodji Seketeli via Libabigail From: Dodji Seketeli Reply-To: Dodji Seketeli Cc: libabigail@sourceware.org Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" Hello Giuliano, 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 Signed-off-by: Dodji Seketeli Signed-off-by: Dodji Seketeli --- src/abg-dwarf-reader.cc | 138 +++++++++++++++++++++++++++++----------- 1 file changed, 101 insertions(+), 37 deletions(-) diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc index 53b5845d..05a7e4d6 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_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,54 @@ fn_die_equal_by_linkage_name(const read_context &ctxt, && llinkage_name == rlinkage_name); } +/// Test if the unordered 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} or {p2,p1} 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), o(p2, p1); + if ((set.find(p) != set.end()) + || (set.find(o) != 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. +/// +/// The pair erased is non ordered. +/// +/// @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), o(p2, 1); + if (!set.erase(p)) + set.erase(o); +} + /// Compare two DIEs emitted by a C compiler. /// /// @param ctxt the read context used to load the DWARF information. @@ -10123,7 +10206,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 +10351,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(l), @@ -10316,8 +10391,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 +10477,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 +10571,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 +10608,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 +10725,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); }