From 86b6dd408847a6fe651aaed75f3a9c8bc0f670f2 Mon Sep 17 00:00:00 2001 From: Roland McGrath Date: Sun, 28 Jun 2009 18:51:38 -0700 Subject: Use a separate tracker for subtree comparisons inside reference_match. --- libdw/c++/dwarf_comparator | 75 ++++++++++++++++++++++++++++++++++++---------- libdw/c++/dwarf_tracker | 72 +++++++++++++++++++++++++++++++++++++------- src/dwarfcmp.cc | 13 +++++++- 3 files changed, 134 insertions(+), 26 deletions(-) diff --git a/libdw/c++/dwarf_comparator b/libdw/c++/dwarf_comparator index 8042a949..56bcd81d 100644 --- a/libdw/c++/dwarf_comparator +++ b/libdw/c++/dwarf_comparator @@ -127,6 +127,23 @@ namespace elfutils { return false; } + + inline dwarf_tracker_base () + {} + + inline dwarf_tracker_base (const dwarf_tracker_base &, + const left_context_type &, const die1 &, + const right_context_type &, const die2 &) + {} + + inline bool quick_reference_match (const die1 &, const die2 &) + { + return false; + } + + inline void notice_reference_match (const die1 &, const die2 &) + { + } }; template struct matcher : public std::binary_function { - dwarf_comparator &_m_cmp; - matcher (dwarf_comparator &cmp) + dwarf_comparator &_m_cmp; + matcher (dwarf_comparator &cmp) : _m_cmp (cmp) {} @@ -233,8 +250,8 @@ namespace elfutils struct match_rhs : public std::binary_function { - dwarf_comparator &_m_cmp; - match_rhs (dwarf_comparator &cmp) + dwarf_comparator &_m_cmp; + match_rhs (dwarf_comparator &cmp) : _m_cmp (cmp) {} @@ -249,7 +266,7 @@ namespace elfutils typename ait2_map::value_type, bool> { - dwarf_comparator &_m_cmp; + dwarf_comparator &_m_cmp; match_sorted (dwarf_comparator &cmp) : _m_cmp (cmp) @@ -315,8 +332,8 @@ namespace elfutils struct die_matcher : public std::binary_function { - dwarf_comparator &_m_cmp; - die_matcher (dwarf_comparator &cmp) + dwarf_comparator &_m_cmp; + die_matcher (dwarf_comparator &cmp) : _m_cmp (cmp) {} @@ -434,8 +451,11 @@ namespace elfutils return true; // Simplest mismatches with the cheapest checks first. - if (a.tag () != b.tag () - || a.has_children () != b.has_children ()) + if (a.tag () != b.tag ()) + return false; + + const bool any_children = a.has_children (); + if (any_children != b.has_children ()) return false; // Now we have to get the tracker involved. @@ -444,15 +464,40 @@ namespace elfutils const typename tracker::right_context_type &rhs = _m_tracker.right_context (ref2); - // First do the cheap mismatch check on the contexts, then check the - // contents and contexts in ascending order of costliness of a check. - return (!_m_tracker.context_quick_mismatch (lhs, rhs) - && match (a.attributes (), b.attributes ()) - && _m_tracker.context_match (lhs, rhs) - && match (a.children (), b.children ())); + // Maybe the tracker has already cached a correspondence of references. + if (_m_tracker.quick_reference_match (ref1, ref2)) + return true; + + /* First do the cheap mismatch check on the contexts, then check the + contents and contexts in ascending order of costliness of a check. */ + if (_m_tracker.context_quick_mismatch (lhs, rhs) + || !match (a.attributes (), b.attributes ()) + || !_m_tracker.context_match (lhs, rhs)) + return false; + + /* To compare the children, we have to clone the tracker and use a + new one. The new tracker jump-starts its walk to the referenced + DIE from the root of the CU. */ + bool result = !any_children || (dwarf_comparator (tracker (_m_tracker, + lhs, ref1, + rhs, ref2)) + .match (a.children (), b.children ())); + + // Let the tracker cache a known match for its quick_reference_match. + if (result) + _m_tracker.notice_reference_match (ref1, ref2); + + return result; } + inline explicit dwarf_comparator (const tracker &t) + : _m_tracker (t) + {} + public: + inline dwarf_comparator () + {} + inline bool operator () (const dwarf1 &a, const dwarf2 &b) { return match (a, b); diff --git a/libdw/c++/dwarf_tracker b/libdw/c++/dwarf_tracker index 8382d2e1..70782258 100644 --- a/libdw/c++/dwarf_tracker +++ b/libdw/c++/dwarf_tracker @@ -72,34 +72,74 @@ namespace elfutils template struct tracker { - cu _m_root; - typedef std::list die_path; - die_path _m_path; /* We record every DIE we have seen here, mapping its .identity () to the die_path of parent DIEs taken to reach it. */ typedef std::tr1::unordered_map< ::Dwarf_Off, const die_path> die_map; - die_map _m_seen; + die_map *_m_seen; + bool _m_delete_seen; + + cu _m_root; + + die_path _m_path; + + static const die_path bad_die_path () + { + return die_path (1); + } + + static bool bad_die_path (const die_path &path) + { + typename die_path::const_iterator it = path.begin (); + if (it == path.end ()) + return false; + const die &elt = *it; + return ++it == path.end () && elt == die (); + } + + inline tracker () + : _m_seen (new die_map), _m_delete_seen (true) + {} + + inline tracker (const tracker &proto, const die_path &context) + : _m_seen (proto._m_seen), _m_delete_seen (false), + _m_root (proto._m_root), _m_path (context) + { + } ~tracker () { // We should never be left with a partial walk on the books. assert (_m_path.empty ()); + if (_m_delete_seen) + delete _m_seen; } inline const die_path &path_to (const die &a) { - typename die_map::iterator it = _m_seen.find (a->identity ()); - if (it == _m_seen.end ()) + ::Dwarf_Off id = a->identity (); + std::pair found + = _m_seen->insert (std::make_pair (id, bad_die_path ())); + if (found.second) { - ::Dwarf_Off id = a->identity (); + /* We have a forward reference. That is, we didn't + already hit this DIE in our top-level walk and so + it is not in _m_seen yet. We must do a separate + walk to find it. */ + die_path path; if (!walk_to (*_m_root, id, path)) throw std::runtime_error ("DIE not reachable from CU!"); - it = _m_seen.insert (std::make_pair (id, path)).first; + _m_seen->erase (found.first); + found.first = _m_seen->insert (found.first, + std::make_pair (id, path)); } - return it->second; + + if (bad_die_path (found.first->second)) + abort (); // XXX + + return found.first->second; } // Return true if this is the droid we're looking for, @@ -143,7 +183,7 @@ namespace elfutils inline void pre_order (const die &a) { // Record the path down from the CU to see this DIE. - _m_seen.insert (std::make_pair (a->identity (), _m_path)); + _m_seen->insert (std::make_pair (a->identity (), _m_path)); // Append this DIE to the path we'll record for its children. _m_path.push_back (a); } @@ -175,6 +215,9 @@ namespace elfutils }; public: + inline dwarf_ref_tracker () + {} + inline void start_walk (const cu1 &a, const cu2 &b) { _m_left.start_walk (a); @@ -225,6 +268,15 @@ namespace elfutils { return std::equal (a.begin (), a.end (), b.begin (), equal_enough ()); } + + // Share the _m_seen maps with the prototype tracker, + // but start a fresh walk from the given starting point. + inline dwarf_ref_tracker (const dwarf_ref_tracker &proto, + const left_context_type &lhs, const die1 &, + const right_context_type &rhs, const die2 &) + : _m_left (tracker1 (proto._m_left, lhs)), + _m_right (tracker2 (proto._m_right, rhs)) + {} }; }; diff --git a/src/dwarfcmp.cc b/src/dwarfcmp.cc index ecadfd52..c779fc49 100644 --- a/src/dwarfcmp.cc +++ b/src/dwarfcmp.cc @@ -128,6 +128,7 @@ template struct talker : public dwarf_ref_tracker { typedef dwarf_tracker_base _base; + typedef dwarf_ref_tracker _tracker; typedef typename _base::cu1 cu1; typedef typename _base::cu2 cu2; typedef typename _base::die1 die1; @@ -138,7 +139,17 @@ struct talker : public dwarf_ref_tracker const typename dwarf1::debug_info_entry *a_; const typename dwarf2::debug_info_entry *b_; - inline talker () : a_ (NULL), b_ (NULL) {} + inline talker () + : a_ (NULL), b_ (NULL) + {} + + inline talker (const talker &proto, + const typename _tracker::left_context_type &l, const die1 &a, + const typename _tracker::right_context_type &r, const die2 &b) + : _tracker (static_cast (proto), l, a, r, b), + a_ (NULL), b_ (NULL) + { + } inline ostream &location () const { -- cgit v1.2.1