From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from relay6-d.mail.gandi.net (relay6-d.mail.gandi.net [217.70.183.198]) by sourceware.org (Postfix) with ESMTPS id 088213858D28 for ; Mon, 19 Dec 2022 17:14:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 088213858D28 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 8704EC0004; Mon, 19 Dec 2022 17:14:13 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=seketeli.org; s=gm1; t=1671470053; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=UUdXOUtkCk70XIVuKV2TRfq4esd9Y+1AELEv40WZXZg=; b=YO4AnRjP9ymIvy1GKcuF90+d1F/S9U62X4AfIMSR4tlc5J/Mac07MoPJXOsUdgM5q3vQ80 IkrwulpRSoOlzgJgDs9PRjfVLECLd5x/LUGj5zygDNaQfMp2HloyNUvop8xIiRiOnJmjOL 4YLRBo0oZWckmIyD8jY9hnlQJFX4UQ44I5UQKQmMxkZAO+1Rad6rEjG3OhQLRI+yp22+H1 hWkPCQg86IxZtT2/q5/F0nSlzVg8oysJXtSMyiSSmSwokqEDTAphLvsv6HbX4siPyDgjaE W7xr0RtC114YDezVZbie8cXP2FZFLCper89rEv1+Lj/xmqP5U5/Kr7FbssGToQ== Received: by localhost (Postfix, from userid 1000) id B808FB5649; Mon, 19 Dec 2022 18:14:12 +0100 (CET) From: Dodji Seketeli To: Dodji Seketeli via Libabigail Cc: Dodji Seketeli Subject: [PATCH 3/3, applied] Bug 29857 - Better detect comparison cycles in type graph Organization: Me, myself and I References: <87wn6ne30e.fsf@redhat.com> X-Operating-System: CentOS Stream release 9 X-URL: http://www.seketeli.net/~dodji Date: Mon, 19 Dec 2022 18:14:12 +0100 In-Reply-To: <87wn6ne30e.fsf@redhat.com> (Dodji Seketeli via Libabigail's message of "Mon, 19 Dec 2022 18:07:13 +0100") Message-ID: <87k02ne2or.fsf@seketeli.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Status: No, score=-9.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,JMQ_SPF_NEUTRAL,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_LOW,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hello, When comparing two aggregates A and B, it can happen that has a sub-type of A is itself; similarly for B. This is a cycle in the type graph, obviously. Also, A and B are said to be recursive types. Structally comparing two recursive types (i.e, comparing them member-wise) can lead to an endless loop. So, during type canonicalization, comparison cycles must be detected to avoid those endless loop. This is currently done in the equals() overload for class_decl, union_decl, class_or_union as well as function_type. Those are the aggregate types that are subject to these cycles when comparing recursive types. Currently, detecting comparison cycles is based on ir::environment::priv::mark_as_being_compared(), ir::environment::priv::priv::unmark_as_being_compared(), ir::environment::priv::comparison_started() considering the pair of pointer to aggregate types being currently compared. If that pair appears more than once in the stack of aggregates being compared a cycle is detected. But then, watching the stack of aggregates during the analsysis of the /usr/lib64/libgs.so.9 binary from the ghostscript-9.52-5.oe1.x86_64 package from https://sourceware.org/bugzilla/show_bug.cgi?id=29857 it appears that the stack of aggregates (structs) was growing endlessly, when comparing the "struct gs_memory_s" type, and the same struct gs_memory_s aggregate was appearing several times on the right-hand side of the comparison stack. Clearly, this is a comparison cycle. The gs_memory struct is appearing several times as the right hand side operand in the stack of operands being compared, even though no pair of operands being compared was present more than once. This prompted me to use another heuristic to detect comparison cycles: If the same aggregate type is appearing several times on either the left or right hand side of the comparison stack then a cycle is detected. This fixes the cycle detection failure above and comparing the two binaries completes in ~ 43 minutes on my laptop, with a non optimized libabigail build. * src/abg-ir-priv.h (class_set_type, fn_set_type): Define new typedefs. * src/abg-ir.cc (environment::priv::{left_classes_being_compared_, right_classes_being_compared_, left_fn_types_being_compared_, right_fn_types_being_compared_}): Define new data members. (environment::priv::{classes_being_compared_, fn_types_being_compared_}): Erase data members. (environment::priv::{dump_classes_being_compared, dump_fn_types_being_compared}): Erase member functions. (environment::priv::{mark_as_being_compared, unmark_as_being_compared, comparison_started}): Change this to use the left-hand-side and right-hand-side comparison stack introduced above. (dump_classes_being_compared, dump_fn_types_being_compared): Remove functions. Signed-off-by: Dodji Seketeli Signed-off-by: Dodji Seketeli --- src/abg-ir-priv.h | 94 ++++++++++++++++------------------------------- src/abg-ir.cc | 24 ------------ 2 files changed, 31 insertions(+), 87 deletions(-) diff --git a/src/abg-ir-priv.h b/src/abg-ir-priv.h index 32041d31..ae6fabd7 100644 --- a/src/abg-ir-priv.h +++ b/src/abg-ir-priv.h @@ -369,6 +369,13 @@ typedef std::pair uint64_t_pair_type; /// A convenience typedef for a set of @ref uint64_t_pair typedef unordered_set uint64_t_pairs_set_type; + +/// A convenience typedef for a set of pointer to @ref class_or_union +typedef unordered_set class_set_type; + +/// A convenience typedef for a set of pointer to @ref function_type. +typedef unordered_set fn_set_type; + /// A convenience typedef for a map which key is a pair of uint64_t /// and which value is a boolean. This is initially intended to cache /// the result of comparing two (sub-)types. @@ -387,12 +394,14 @@ struct environment::priv // used to avoid endless loops while recursively comparing types. // This should be empty when none of the 'equal' overloads are // currently being invoked. - uint64_t_pairs_set_type classes_being_compared_; + class_set_type left_classes_being_compared_; + class_set_type right_classes_being_compared_; // The set of pairs of function types being currently compared. It's used // to avoid endless loops while recursively comparing types. This // should be empty when none of the 'equal' overloads are currently // being invoked. - uint64_t_pairs_set_type fn_types_being_compared_; + fn_set_type left_fn_types_being_compared_; + fn_set_type right_fn_types_being_compared_; // This is a cache for the result of comparing two sub-types (of // either class or function types) that are designated by their // memory address in the IR. @@ -605,48 +614,6 @@ struct environment::priv clear_type_comparison_results_cache() {type_comparison_results_cache_.clear();} - /// Dumps a textual representation (to the standard error output) of - /// the content of the set of classes being currently compared using - /// the @ref equal overloads. - /// - /// This function is for debugging purposes. - void - dump_classes_being_compared() - { - std::cerr << "classes being compared: " << classes_being_compared_.size() - << "\n" - << "=====================================\n"; - for (auto& p : classes_being_compared_) - { - class_or_union* c = reinterpret_cast(p.first); - std::cerr << "'" << c->get_pretty_representation() - << " / (" << std::hex << p.first << "," << p.second << ")" - << "'\n"; - } - std::cerr << "=====================================\n"; - } - - /// Dumps a textual representation (to the standard error output) of - /// the content of the set of classes being currently compared using - /// the @ref equal overloads. - /// - /// This function is for debugging purposes. - void - dump_fn_types_being_compared() - { - std::cerr << "fn_types being compared: " << fn_types_being_compared_.size() - << "\n" - << "=====================================\n"; - for (auto& p : fn_types_being_compared_) - { - function_type* c = reinterpret_cast(p.first); - std::cerr << "'" << c->get_pretty_representation() - << " / (" << std::hex << p.first << "," << p.second << ")" - << "'\n"; - } - std::cerr << "=====================================\n"; - } - /// Push a pair of operands on the stack of operands of the current /// type comparison, during type canonicalization. /// @@ -1174,9 +1141,9 @@ struct class_or_union::priv const class_or_union& second) const { const environment& env = first.get_environment(); - env.priv_->classes_being_compared_.insert - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast(&second))); + + env.priv_->left_classes_being_compared_.insert(&first); + env.priv_->right_classes_being_compared_.insert(&second); } /// Mark a pair of classes or unions as being currently compared @@ -1236,9 +1203,9 @@ struct class_or_union::priv const class_or_union& second) const { const environment& env = first.get_environment(); - env.priv_->classes_being_compared_.erase - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast(&second))); + + env.priv_->left_classes_being_compared_.erase(&first); + env.priv_->right_classes_being_compared_.erase(&second); } /// If a pair of class_or_union has been previously marked as @@ -1277,10 +1244,10 @@ struct class_or_union::priv const class_or_union& second) const { const environment& env = first.get_environment(); - return env.priv_-> - classes_being_compared_.count - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast((&second)))); + + return (env.priv_->left_classes_being_compared_.count(&first) + || + env.priv_->right_classes_being_compared_.count(&second)); } /// Test if a pair of class_or_union is being currently compared. @@ -1337,9 +1304,9 @@ struct function_type::priv const function_type& second) const { const environment& env = first.get_environment(); - env.priv_->fn_types_being_compared_.insert - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast(&second))); + + env.priv_->left_fn_types_being_compared_.insert(&first); + env.priv_->right_fn_types_being_compared_.insert(&second); } /// Mark a given pair of @ref function_type as being compared. @@ -1354,9 +1321,9 @@ struct function_type::priv const function_type& second) const { const environment& env = first.get_environment(); - env.priv_->fn_types_being_compared_.erase - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast(&second))); + + env.priv_->left_fn_types_being_compared_.erase(&first); + env.priv_->right_fn_types_being_compared_.erase(&second); } /// Tests if a @ref function_type is currently being compared. @@ -1369,9 +1336,10 @@ struct function_type::priv const function_type& second) const { const environment& env = first.get_environment(); - return env.priv_->fn_types_being_compared_.count - (std::make_pair(reinterpret_cast(&first), - reinterpret_cast(&second))); + + return (env.priv_->left_fn_types_being_compared_.count(&first) + || + env.priv_->right_fn_types_being_compared_.count(&second)); } };// end struc function_type::priv diff --git a/src/abg-ir.cc b/src/abg-ir.cc index 3a87ca09..0c9a32df 100644 --- a/src/abg-ir.cc +++ b/src/abg-ir.cc @@ -21941,30 +21941,6 @@ class_or_union::operator==(const class_or_union& other) const return class_or_union::operator==(o); } -/// Dumps a textual representation (to the standard error output) of -/// the content of the set of classes being currently compared using -/// the @ref equal overloads. -/// -/// This function is for debugging purposes. -/// -/// @param c an artifact that belongs to the environment in which the -/// classes of interest are being compared. -void -dump_classes_being_compared(const type_or_decl_base& c) -{c.get_environment().priv_->dump_classes_being_compared();} - -/// Dumps a textual representation (to the standard error output) of -/// the content of the set of function types being currently compared -/// using the @ref equal overloads. -/// -/// This function is for debugging purposes. -/// -/// @param c an artifact that belongs to the environment in which the -/// function types of interest are being compared. -void -dump_fn_types_being_compared(const type_or_decl_base& t) -{t.get_environment().priv_->dump_fn_types_being_compared();} - /// Compares two instances of @ref class_or_union. /// /// If the two intances are different, set a bitfield to give some -- 2.31.1 -- Dodji