[3/3,applied] Bug 29857 - Better detect comparison cycles in type graph
Commit Message
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 <dodji@seketeli.org>
Signed-off-by: Dodji Seketeli <dodji@redhat.com>
---
src/abg-ir-priv.h | 94 ++++++++++++++++-------------------------------
src/abg-ir.cc | 24 ------------
2 files changed, 31 insertions(+), 87 deletions(-)
@@ -369,6 +369,13 @@ typedef std::pair<uint64_t, uint64_t> uint64_t_pair_type;
/// A convenience typedef for a set of @ref uint64_t_pair
typedef unordered_set<uint64_t_pair_type,
uint64_t_pair_hash> uint64_t_pairs_set_type;
+
+/// A convenience typedef for a set of pointer to @ref class_or_union
+typedef unordered_set<const class_or_union*> class_set_type;
+
+/// A convenience typedef for a set of pointer to @ref function_type.
+typedef unordered_set<const function_type*> 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<class_or_union*>(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<function_type*>(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<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&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<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&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<uint64_t>(&first),
- reinterpret_cast<uint64_t>((&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<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&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<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&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<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&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
@@ -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