From c8f5a7d9725e882eed142722a4b9e097c16fd88f Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Thu, 13 Jan 2011 13:09:31 +0100 Subject: Remove unused output-shape from dwarf_output collector. --- libdw/Makefile.am | 2 +- libdw/c++/dwarf_output | 33 ---------- libdw/c++/output-shape.cc | 159 ---------------------------------------------- 3 files changed, 1 insertion(+), 193 deletions(-) delete mode 100644 libdw/c++/output-shape.cc diff --git a/libdw/Makefile.am b/libdw/Makefile.am index 279e8599..3fcfdb71 100644 --- a/libdw/Makefile.am +++ b/libdw/Makefile.am @@ -101,7 +101,7 @@ libdwpp_a_SOURCES = c++/values.cc \ c++/known.cc \ c++/line_info.cc \ c++/edit-values.cc \ - c++/output-values.cc c++/output-shape.cc + c++/output-values.cc if MAINTAINER_MODE BUILT_SOURCES = $(srcdir)/known-dwarf.h diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index b7bbaadc..9d0f6782 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -994,39 +994,6 @@ namespace elfutils return &x; } - struct shape_type - { - typedef std::vector > attrs_type; - attrs_type _m_attrs; - bool _m_has_children; - size_t _m_hash; - - friend class subr::hashed_hasher; - typedef subr::hashed_hasher hasher; - - inline void hashnadd (int name, int form); - inline shape_type (const die_type &die, bool last_sibling); - - inline bool operator== (const shape_type &other) const - { - return (_m_hash == other._m_hash - && _m_has_children == other._m_has_children - && _m_attrs == other._m_attrs); - } - inline bool operator!= (const shape_type &other) const - { - return !(*this == other); - } - }; - - typedef subr::nothing shape_info; - - typedef std::tr1::unordered_map shape_map; - shape_map _m_shapes; - - void add_shape (die_type &die, bool last_sibling); - struct stats_cmp : public std::binary_function. */ - -#include -#include "dwarf_output" - -using namespace elfutils; - -static inline int -attr_form (int tag, const dwarf_output::attribute &attr) -{ - switch (attr.second.what_space ()) - { - case dwarf::VS_address: - return DW_FORM_addr; - - case dwarf::VS_flag: - return DW_FORM_flag; - - case dwarf::VS_reference: - return DW_FORM_ref_addr; - - case dwarf::VS_string: - case dwarf::VS_identifier: - return DW_FORM_string; - - case dwarf::VS_constant: - if (! attr.second.constant_is_integer ()) - return DW_FORM_block; - /* Fall through. */ - - case dwarf::VS_dwarf_constant: - case dwarf::VS_source_line: - case dwarf::VS_source_column: - return DW_FORM_udata; - - case dwarf::VS_location: - if (!attr.second.location ().is_list ()) - return DW_FORM_block; - /* Fall through. */ - - case dwarf::VS_lineptr: - case dwarf::VS_macptr: - case dwarf::VS_rangelistptr: - /* For class *ptr (including loclistptr), the one of data[48] that - matches offset_size is the only form encoding to use. Other data* - forms can mean the attribute is class constant instead. */ - return DW_FORM_data4; - - case dwarf::VS_source_file: - switch (attr.first) - { - case DW_AT_decl_file: - case DW_AT_call_file: - return DW_FORM_udata; - - case DW_AT_comp_dir: - return DW_FORM_string; - - case DW_AT_name: - switch (tag) - { - case DW_TAG_compile_unit: - case DW_TAG_partial_unit: - return DW_FORM_string; - } - break; - } - throw std::runtime_error ("source_file value unexpected in " - + to_string (attr)); - - case dwarf::VS_discr_list: - return DW_FORM_block; - } - - throw std::logic_error ("strange value_space"); -} - -inline void -dwarf_output_collector::shape_type::hashnadd (int name, int form) -{ - subr::hash_combine (_m_hash, name); - subr::hash_combine (_m_hash, form); - _m_attrs.push_back (std::make_pair (name, form)); -} - -inline -dwarf_output_collector::shape_type::shape_type (const die_type &die, - bool last_sibling) - : _m_has_children (die.has_children ()), _m_hash (8675309 << _m_has_children) -{ - if (!last_sibling) - hashnadd (DW_AT_sibling, DW_FORM_ref_udata); - - for (die_type::attributes_type::const_iterator it = die.attributes ().begin (); - it != die.attributes ().end (); - ++it) - hashnadd (it->first, attr_form (die.tag (), *it)); -} -#if 0 -void -dwarf_output_collector::add_shape (die_type &die, bool last_sibling) -{ - assert (die._m_shape == NULL); - - shape_map::value_type &x - = *_m_shapes.insert (std::make_pair (shape_type (die, last_sibling), - shape_info ())).first; - // x.second.nusers++, etc. - - die._m_shape = &x; -} -#endif -- cgit v1.2.1 From 35727d56106182c7513c1d4c5f784cb087d2f4ec Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Wed, 23 Feb 2011 17:26:09 +0100 Subject: DW_AT_*_file is allowed to be zero, meaning "no file". --- libdw/c++/dwarf | 3 ++- libdw/c++/line_info.cc | 20 ++++++++++++++++++-- 2 files changed, 20 insertions(+), 3 deletions(-) diff --git a/libdw/c++/dwarf b/libdw/c++/dwarf index 8342dc78..c386f0ed 100644 --- a/libdw/c++/dwarf +++ b/libdw/c++/dwarf @@ -1126,7 +1126,8 @@ namespace elfutils } /* Return a value unique to us while we're in memory. - This is a stable pointer into the Dwarf_Files data. */ + This is a stable pointer into the Dwarf_Files data + or to a static empty string. */ inline uintptr_t identity () const { return (uintptr_t) name (); diff --git a/libdw/c++/line_info.cc b/libdw/c++/line_info.cc index e613c16b..df7a2172 100644 --- a/libdw/c++/line_info.cc +++ b/libdw/c++/line_info.cc @@ -61,6 +61,15 @@ stringform (Dwarf_Attribute *attr) return false; } +/* Returns true if the attribute represents a valid zero udata. + This represents "no-file". */ +static bool +zero_formudata (Dwarf_Attribute *attr) +{ + Dwarf_Word zero; + return dwarf_formudata (attr, &zero) == 0 && zero == 0; +} + /* Mock up a dummy attribute with a special kludge that get_files groks. We use these for source_file objects consed directly from an index rather than from a real attribute. */ @@ -91,7 +100,7 @@ get_files (const Dwarf_Attribute *attr, Dwarf_Files **files, Dwarf_Word *idx) Dwarf_Word dwarf::source_file::mtime () const { - if (stringform (thisattr ())) + if (stringform (thisattr ()) || zero_formudata (thisattr ())) return 0; Dwarf_Files *files; @@ -106,7 +115,7 @@ dwarf::source_file::mtime () const Dwarf_Word dwarf::source_file::size () const { - if (stringform (thisattr ())) + if (stringform (thisattr ()) || zero_formudata (thisattr ())) return 0; Dwarf_Files *files; @@ -118,12 +127,16 @@ dwarf::source_file::size () const return result; } +static const char *no_file = ""; + const char * dwarf::source_file::name () const { const char *result; if (stringform (thisattr ())) result = dwarf_formstring (thisattr ()); + else if (zero_formudata (thisattr ())) + result = no_file; else { Dwarf_Files *files; @@ -154,6 +167,9 @@ dwarf::source_file::to_string () const return plain_string (result); } + if (zero_formudata (thisattr ())) + return plain_string (no_file); + Dwarf_Files *files; Dwarf_Word idx; xif (thisattr (), get_files (thisattr (), &files, &idx)); -- cgit v1.2.1 From 17a29217e9145989ca15479132f8d6d8f80f0258 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Wed, 23 Feb 2011 19:59:41 +0100 Subject: Add the *info () hack in dwarf_output, so we can rely on it for now. --- libdw/c++/dwarf_output | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 9d0f6782..ac546267 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -151,6 +151,12 @@ namespace elfutils friend class dwarf_output; friend class dwarf_output_collector; + __attribute__((used)) die_info_pair *info () const + { + return reinterpret_cast + (const_cast (this)); + } + public: class attributes_type : public dwarf_data::attributes_type -- cgit v1.2.1 From 4a5f27364dcd30d43c49ac7292e29cd7cf7530d8 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Thu, 20 Jan 2011 15:28:59 +0100 Subject: Introduce local_hash for dwarf_output debug_info_die. Very simplistic local_hash implementation. Just takes tag name, attributes and children sizes into account. But is good enough to make all the dwarf_edit_output tests pass. Some dwarfcmp-test-self tests fail though. it also generates a significant number of collissions for the dwarf_output_collector attr_sets. --- libdw/c++/dwarf_output | 59 +++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 46 insertions(+), 13 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index ac546267..d9852535 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -393,6 +393,18 @@ namespace elfutils { return 0; } + + /* The hash as used for a reference attribute value that points + to this die. Only uses "local" (non-reference) values. The + culculation should match the pending_entry::local_hash () + method result. */ + inline size_t local_hash () const + { + size_t hash = _m_tag; + subr::hash_combine (hash, _m_attributes->size ()); + subr::hash_combine (hash, _m_children->size ()); + return hash; + } }; struct value::value_reference @@ -409,13 +421,12 @@ namespace elfutils : _base (i, dummy) {} - /* The hash of a value_reference is its referent's identity, - because we can have multiple value_reference objects that - wind up pointing to the same entry. This method is virtual - for the circular_reference case, below. */ + /* The hash of a value_reference is its referent's local hash, + which only takes non-reference values into account. This + method is virtual for the circular_reference case, below. */ virtual size_t hash () const { - return ref->identity (); + return ref->local_hash (); } }; @@ -1179,9 +1190,10 @@ namespace elfutils { private: const std::vector *_m_entry; + const size_t _m_hash; // The local hash of the reference die (entry). inline circular_reference (const circular_reference &) - : value::value_reference () + : value::value_reference (), _m_hash (0) { throw std::logic_error ("cannot copy-construct"); } @@ -1189,7 +1201,8 @@ namespace elfutils public: inline circular_reference (const entry *die, copier *) : value::value_reference (), - _m_entry (new std::vector (1, const_cast (die))) + _m_entry (new std::vector (1, const_cast (die))), + _m_hash (die->local_hash ()) { die->dump () << " new circular_reference " << this << "\n"; } @@ -1229,14 +1242,11 @@ namespace elfutils } /* We have a special case for a reference attribute that is part - of a circular chain. That value always hashes as zero, so that - each entry in a circular chain of references has the same hash - value as any entry that it otherwise matches and that has any - (eventually) circular reference as the corresponding - attribute's value. */ + of a circular chain. It gets calculated from the + pending_entry. */ virtual size_t hash () const { - return 0; + return _m_hash; } }; @@ -1449,6 +1459,20 @@ namespace elfutils subr::for_each (_m_children, std::mem_fun (&entry::dump_entry)); self->dump (false, true) << " ends\n"; } + + /* This should match the calculation of local_hash () of an + debug_info_die. If we already matched, just take the hash of + the matched die instead of recalculating. */ + inline size_t local_hash () const + { + if (_m_matched != NULL) + return _m_matched->first.local_hash (); + + size_t hash = _m_tag; + subr::hash_combine (hash, _m_attributes.size ()); + subr::hash_combine (hash, _m_children.size ()); + return hash; + } }; // This keeps state in the pending_entry's _m_finalizing pointer while live. @@ -1753,6 +1777,15 @@ namespace elfutils assert (_m_pending != NULL); return _m_parent->_m_pending->child (_m_self_idx); } + + /* The local hash of the debug_info_entry if we are already + final, otherwise calculate it from the pending_entry. */ + inline size_t local_hash () const + { + if (_m_final) + return _m_final->first.local_hash (); + return _m_pending->local_hash (); + } }; // This object lives while we are copying one particular input DIE. -- cgit v1.2.1 From 18804275adb5dfbb9ba17322de9f6a17c38c2f04 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Thu, 20 Jan 2011 16:23:48 +0100 Subject: Turn copier::entry into a value_reference so what_space works on it. copier::entry is used as a value_reference when an attr_value has a dangling reference to a DIE not yet built in the output. So make sure its type matches that usage. --- libdw/c++/dwarf_output | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index d9852535..970d991a 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -1511,7 +1511,7 @@ namespace elfutils built in the output has one of these in place of a value_reference. These all live in the _m_entries map, one per input-side DIE. */ struct entry - : public value::value_dispatch + : public value::value_reference { ::Dwarf_Off _m_offset; // For debugging and statistics only. ::Dwarf_Off _m_cost; // For statistics only. -- cgit v1.2.1 From ea1437c20f3ff873b1ddb4457775749ea28d278a Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 21 Jan 2011 10:37:08 +0100 Subject: Add local_hash to attributes_type and use it for die hash. Skips values of reference attributes. --- libdw/c++/dwarf_output | 41 +++++++++++++++++++++++++++++++++++------ 1 file changed, 35 insertions(+), 6 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 970d991a..03d89265 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -167,9 +167,10 @@ namespace elfutils typedef dwarf_data::attributes_type _base; size_t _m_hash; + size_t _m_local_hash; inline attributes_type () - : _base (), _m_hash (0) + : _base (), _m_hash (0), _m_local_hash (0) {} struct same_attr : public std::equal_to @@ -185,7 +186,16 @@ namespace elfutils { // Precompute our hash value based on our contents. for (iterator i = begin (); i != end (); ++i) - subr::hash_combine (_m_hash, *i); + { + subr::hash_combine (_m_hash, *i); + // XOR the attribute values together (so order doesn't matter) + // but exclude reference attributes values (just include + // their tag). + if (i->second.what_space () != dwarf::VS_reference) + _m_local_hash ^= subr::hash_this (*i); + else + _m_local_hash ^= (i->first << 3); + } } inline const _base &base () const @@ -196,7 +206,7 @@ namespace elfutils public: template inline attributes_type (const iter &from, const iter &to) - : _base (from, to), _m_hash (0) + : _base (from, to), _m_hash (0), _m_local_hash (0) { do_hash (); } @@ -206,7 +216,7 @@ namespace elfutils template inline attributes_type (const input &other, arg_type &c) - : _base (other, c), _m_hash (0) + : _base (other, c), _m_hash (0), _m_local_hash (0) { do_hash (); } @@ -214,10 +224,16 @@ namespace elfutils inline bool is (const attributes_type &these) const { return (_m_hash == these._m_hash + && _m_local_hash == these._m_local_hash && size () == these.size () && std::equal (begin (), end (), these.begin (), same_attr ())); } + + inline size_t local_hash () const + { + return _m_local_hash; + } }; class children_type @@ -401,7 +417,7 @@ namespace elfutils inline size_t local_hash () const { size_t hash = _m_tag; - subr::hash_combine (hash, _m_attributes->size ()); + subr::hash_combine (hash, _m_attributes->local_hash ()); subr::hash_combine (hash, _m_children->size ()); return hash; } @@ -1469,7 +1485,20 @@ namespace elfutils return _m_matched->first.local_hash (); size_t hash = _m_tag; - subr::hash_combine (hash, _m_attributes.size ()); + size_t attr_hash = 0; + // XOR the attribute values together (so order doesn't matter) + // but exclude reference attributes values (just include + // their tag). + for (attr_map::const_iterator it = _m_attributes.begin (); + it != _m_attributes.end (); + ++it) + { + if (it->second.what_space () != dwarf::VS_reference) + attr_hash ^= subr::hash_this (*it); + else + attr_hash ^= (it->first << 3); + } + subr::hash_combine (hash, attr_hash); subr::hash_combine (hash, _m_children.size ()); return hash; } -- cgit v1.2.1 From 2fd892f1d51536513fda839653c61529b6bbe5be Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 21 Jan 2011 22:44:15 +0100 Subject: Add local hash for children_types. --- libdw/c++/dwarf_output | 25 ++++++++++++++++++++++--- 1 file changed, 22 insertions(+), 3 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 03d89265..b6452917 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -246,12 +246,17 @@ namespace elfutils typedef std::vector _base; size_t _m_hash; + size_t _m_local_hash; inline void set_hash () { _m_hash = 0; + _m_local_hash = 0; for (_base::iterator i = _base::begin (); i != _base::end (); ++i) - subr::hash_combine (_m_hash, (uintptr_t) *i); + { + subr::hash_combine (_m_hash, (uintptr_t) *i); + subr::hash_combine (_m_local_hash, (*i)->first.local_hash ()); + } } inline children_type () {} @@ -293,6 +298,7 @@ namespace elfutils inline bool is (const children_type &these) const { return (_m_hash == these._m_hash + && _m_local_hash == these._m_local_hash && size () == these.size () && std::equal (_base::begin (), _base::end (), these._base::begin ())); @@ -311,6 +317,11 @@ namespace elfutils { return const_iterator (_base::end (), subr::nothing ()); } + + inline size_t local_hash () const + { + return _m_local_hash; + } }; typedef children_type::iterator pointer; @@ -418,7 +429,7 @@ namespace elfutils { size_t hash = _m_tag; subr::hash_combine (hash, _m_attributes->local_hash ()); - subr::hash_combine (hash, _m_children->size ()); + subr::hash_combine (hash, _m_children->local_hash ()); return hash; } }; @@ -1499,7 +1510,15 @@ namespace elfutils attr_hash ^= (it->first << 3); } subr::hash_combine (hash, attr_hash); - subr::hash_combine (hash, _m_children.size ()); + + size_t children_hash = 0; + for (typename std::vector::const_iterator it + = _m_children.begin (); + it != _m_children.end (); + ++it) + subr::hash_combine (children_hash, (*it)->local_hash ()); + subr::hash_combine (hash, children_hash); + return hash; } }; -- cgit v1.2.1 From b8d66b1de27b1c407115fb15e572e9b5b00dc871 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Mon, 14 Feb 2011 14:36:28 +0100 Subject: Calculate local_hash only on finalizing entry, store in die_info. --- libdw/c++/dwarf_output | 153 +++++++++++++++++++++---------------------------- 1 file changed, 66 insertions(+), 87 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index b6452917..58a0b76c 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -167,10 +167,9 @@ namespace elfutils typedef dwarf_data::attributes_type _base; size_t _m_hash; - size_t _m_local_hash; inline attributes_type () - : _base (), _m_hash (0), _m_local_hash (0) + : _base (), _m_hash (0) {} struct same_attr : public std::equal_to @@ -186,16 +185,9 @@ namespace elfutils { // Precompute our hash value based on our contents. for (iterator i = begin (); i != end (); ++i) - { + // XXX booo - still aren't handling circularity right... + if (i->second.what_space () != dwarf::VS_reference) subr::hash_combine (_m_hash, *i); - // XOR the attribute values together (so order doesn't matter) - // but exclude reference attributes values (just include - // their tag). - if (i->second.what_space () != dwarf::VS_reference) - _m_local_hash ^= subr::hash_this (*i); - else - _m_local_hash ^= (i->first << 3); - } } inline const _base &base () const @@ -206,7 +198,7 @@ namespace elfutils public: template inline attributes_type (const iter &from, const iter &to) - : _base (from, to), _m_hash (0), _m_local_hash (0) + : _base (from, to), _m_hash (0) { do_hash (); } @@ -216,7 +208,7 @@ namespace elfutils template inline attributes_type (const input &other, arg_type &c) - : _base (other, c), _m_hash (0), _m_local_hash (0) + : _base (other, c), _m_hash (0) { do_hash (); } @@ -224,16 +216,10 @@ namespace elfutils inline bool is (const attributes_type &these) const { return (_m_hash == these._m_hash - && _m_local_hash == these._m_local_hash && size () == these.size () && std::equal (begin (), end (), these.begin (), same_attr ())); } - - inline size_t local_hash () const - { - return _m_local_hash; - } }; class children_type @@ -246,17 +232,12 @@ namespace elfutils typedef std::vector _base; size_t _m_hash; - size_t _m_local_hash; inline void set_hash () { _m_hash = 0; - _m_local_hash = 0; for (_base::iterator i = _base::begin (); i != _base::end (); ++i) - { - subr::hash_combine (_m_hash, (uintptr_t) *i); - subr::hash_combine (_m_local_hash, (*i)->first.local_hash ()); - } + subr::hash_combine (_m_hash, (uintptr_t) *i); } inline children_type () {} @@ -298,7 +279,6 @@ namespace elfutils inline bool is (const children_type &these) const { return (_m_hash == these._m_hash - && _m_local_hash == these._m_local_hash && size () == these.size () && std::equal (_base::begin (), _base::end (), these._base::begin ())); @@ -317,11 +297,6 @@ namespace elfutils { return const_iterator (_base::end (), subr::nothing ()); } - - inline size_t local_hash () const - { - return _m_local_hash; - } }; typedef children_type::iterator pointer; @@ -422,15 +397,11 @@ namespace elfutils } /* The hash as used for a reference attribute value that points - to this die. Only uses "local" (non-reference) values. The - culculation should match the pending_entry::local_hash () - method result. */ + to this die. Only uses "local" (non-reference) values. + Result cached in die_info. */ inline size_t local_hash () const { - size_t hash = _m_tag; - subr::hash_combine (hash, _m_attributes->local_hash ()); - subr::hash_combine (hash, _m_children->local_hash ()); - return hash; + return info ()->second._m_local_hash; } }; @@ -628,10 +599,12 @@ namespace elfutils std::bitset<2> _m_with_sibling; unsigned int _m_uses; - inline die_info () + size_t _m_local_hash; + + inline die_info (size_t local_hash) : _m_parent (NULL), _m_refs (), _m_originals (), _m_original_cost (0), - _m_with_sibling (), _m_uses (0) + _m_with_sibling (), _m_uses (0), _m_local_hash (local_hash) {} inline ~die_info () @@ -1026,11 +999,12 @@ namespace elfutils inline die_info_pair *add_entry (int tag, const children_type *children, - const attrs_type *attrs) + const attrs_type *attrs, + size_t local_hash) { std::pair ins = _m_unique.insert (std::make_pair (die_type (tag, children, attrs), - die_info ())); + die_info (local_hash))); die_info_pair &x = *ins.first; if (ins.second) x.second.assert_unused (); @@ -1217,10 +1191,10 @@ namespace elfutils { private: const std::vector *_m_entry; - const size_t _m_hash; // The local hash of the reference die (entry). + bool _m_final; inline circular_reference (const circular_reference &) - : value::value_reference (), _m_hash (0) + : value::value_reference () { throw std::logic_error ("cannot copy-construct"); } @@ -1229,14 +1203,15 @@ namespace elfutils inline circular_reference (const entry *die, copier *) : value::value_reference (), _m_entry (new std::vector (1, const_cast (die))), - _m_hash (die->local_hash ()) + _m_final (false) { die->dump () << " new circular_reference " << this << "\n"; } inline bool final () const { - return _m_entry == NULL; + // XXX was return _m_entry == NULL; + return _m_final; } inline typename std::vector::const_iterator pending () const @@ -1254,8 +1229,10 @@ namespace elfutils { pending_entry ()->dump () << " placed circular_reference " << this << "\n"; - delete _m_entry; - _m_entry = NULL; + // XXX Keeping around for local hash... + _m_final = true; + // delete _m_entry; + // _m_entry = NULL; } inline ~circular_reference () @@ -1273,7 +1250,7 @@ namespace elfutils pending_entry. */ virtual size_t hash () const { - return _m_hash; + return pending_entry ()->local_hash (); } }; @@ -1395,6 +1372,40 @@ namespace elfutils typedef typename final_children_getter:: template copy get_final_children; + inline size_t calculate_local_hash () + { + // Calculate the local hash for this new die. + // XOR the attribute values together (so order doesn't matter) + // but exclude reference attributes values (just include + // their tag). XXX - shouldn't be necessary, double check. + size_t lhash = _m_tag; + size_t attr_hash = 0; + for (attr_map::const_iterator it = _m_attributes.begin (); + it != _m_attributes.end (); + ++it) + { + if (it->second.what_space () != dwarf::VS_reference) + attr_hash ^= subr::hash_this (*it); + else + attr_hash ^= (it->first << 3); + } + subr::hash_combine (lhash, attr_hash); + + size_t children_hash = 0; + for (typename std::vector::const_iterator it + = _m_children.begin (); + it != _m_children.end (); + ++it) + { + die_info_pair *final_child = get_final_child (*it); + size_t child_lhash = final_child->second._m_local_hash; + subr::hash_combine (children_hash, child_lhash); + } + subr::hash_combine (lhash, children_hash); + + return lhash; + } + inline die_info_pair *final (copier *c, ::Dwarf_Off offset, ::Dwarf_Off cost) { @@ -1405,6 +1416,9 @@ namespace elfutils bool fresh = false; if (_m_matched == NULL) { + size_t lhash = calculate_local_hash (); + + // XXX We should drop this cache, or use the lhash in it... attrs_matcher equalator (c); const debug_info_entry::attributes_type *attrs = &co->add_attributes (_m_tag, _m_attributes, equalator)->first; @@ -1414,7 +1428,7 @@ namespace elfutils (_m_children, std::ptr_fun (get_final_child)), fresh); - _m_matched = co->add_entry (_m_tag, children, attrs); + _m_matched = co->add_entry (_m_tag, children, attrs, lhash); } // Final bookkeeping in the collector for this copied entry. @@ -1486,41 +1500,6 @@ namespace elfutils subr::for_each (_m_children, std::mem_fun (&entry::dump_entry)); self->dump (false, true) << " ends\n"; } - - /* This should match the calculation of local_hash () of an - debug_info_die. If we already matched, just take the hash of - the matched die instead of recalculating. */ - inline size_t local_hash () const - { - if (_m_matched != NULL) - return _m_matched->first.local_hash (); - - size_t hash = _m_tag; - size_t attr_hash = 0; - // XOR the attribute values together (so order doesn't matter) - // but exclude reference attributes values (just include - // their tag). - for (attr_map::const_iterator it = _m_attributes.begin (); - it != _m_attributes.end (); - ++it) - { - if (it->second.what_space () != dwarf::VS_reference) - attr_hash ^= subr::hash_this (*it); - else - attr_hash ^= (it->first << 3); - } - subr::hash_combine (hash, attr_hash); - - size_t children_hash = 0; - for (typename std::vector::const_iterator it - = _m_children.begin (); - it != _m_children.end (); - ++it) - subr::hash_combine (children_hash, (*it)->local_hash ()); - subr::hash_combine (hash, children_hash); - - return hash; - } }; // This keeps state in the pending_entry's _m_finalizing pointer while live. @@ -1827,12 +1806,12 @@ namespace elfutils } /* The local hash of the debug_info_entry if we are already - final, otherwise calculate it from the pending_entry. */ + final, otherwise get it from the pending_entry. */ inline size_t local_hash () const { if (_m_final) return _m_final->first.local_hash (); - return _m_pending->local_hash (); + return _m_pending->calculate_local_hash (); } }; -- cgit v1.2.1 From 4c6a8c74352f95bd4a39851ddc6ff936959f0d8f Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Wed, 16 Feb 2011 09:14:23 +0100 Subject: Don't finalize entries on first go, just create and store die_info for them. Do all finalization for the whole CU after walking the whole tree. --- libdw/c++/dwarf_output | 41 ++++++++++++++++++++++++----------------- 1 file changed, 24 insertions(+), 17 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 58a0b76c..401aec67 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -1000,11 +1000,11 @@ namespace elfutils inline die_info_pair *add_entry (int tag, const children_type *children, const attrs_type *attrs, - size_t local_hash) + die_info *info) { std::pair ins = _m_unique.insert (std::make_pair (die_type (tag, children, attrs), - die_info (local_hash))); + *info)); die_info_pair &x = *ins.first; if (ins.second) x.second.assert_unused (); @@ -1285,9 +1285,14 @@ namespace elfutils // Set if _m_children contains any entries not already final. bool _m_unfinished_children; + // The die_info that will be used when putting the die into + // the collector. Stores local hash as soon as all children + // are defined in defined_self (). + die_info *_m_info; + inline pending_entry (int tag) : _m_finalizing (NULL), _m_self (NULL), _m_matched (NULL), - _m_tag (tag), _m_unfinished_children (false) + _m_tag (tag), _m_unfinished_children (false), _m_info (NULL) {} inline ~pending_entry () @@ -1397,8 +1402,8 @@ namespace elfutils it != _m_children.end (); ++it) { - die_info_pair *final_child = get_final_child (*it); - size_t child_lhash = final_child->second._m_local_hash; + size_t child_lhash; + child_lhash = (*it)->_m_pending->_m_info->_m_local_hash; subr::hash_combine (children_hash, child_lhash); } subr::hash_combine (lhash, children_hash); @@ -1416,9 +1421,6 @@ namespace elfutils bool fresh = false; if (_m_matched == NULL) { - size_t lhash = calculate_local_hash (); - - // XXX We should drop this cache, or use the lhash in it... attrs_matcher equalator (c); const debug_info_entry::attributes_type *attrs = &co->add_attributes (_m_tag, _m_attributes, equalator)->first; @@ -1428,7 +1430,7 @@ namespace elfutils (_m_children, std::ptr_fun (get_final_child)), fresh); - _m_matched = co->add_entry (_m_tag, children, attrs, lhash); + _m_matched = co->add_entry (_m_tag, children, attrs, _m_info); } // Final bookkeeping in the collector for this copied entry. @@ -1627,10 +1629,9 @@ namespace elfutils } /* We are no longer an undefined entry, so decrement the count. - Then finalize as much as we can now. We attempt finalization - even when the count is nonzero, so that a leaf entry with no - forward references finishes immediately, and so then can its - parents and on up if they don't own any pending references. */ + But don't finalize yet. Since all children are known now we + can create a candidate die_info that includes the local hash + for this entry. */ inline void defined_self (copier *c) { assert (_m_final == NULL); @@ -1638,9 +1639,9 @@ namespace elfutils assert (c->_m_undefined_entries > 0); --c->_m_undefined_entries; dump () << " defined_self => " << c->_m_undefined_entries << "\n"; - finalize (c); - if (_m_final == NULL) - assert (c->_m_undefined_entries > 0); + + size_t lhash = _m_pending->calculate_local_hash (); + _m_pending->_m_info = new die_info (lhash); } /* A reference-following matching operation noticed along @@ -1907,11 +1908,17 @@ namespace elfutils return *_m_copier; } - /* Complain if we still have dangling references. + /* Try to finalize everything at once. + Complain if we still have dangling references. If not, it should be impossible to have pending entries left. */ inline die_info_pair *final_unit () const { assert (_m_out == NULL); + + // We should now be able to finalize everything at once. + if (_m_copier->_m_undefined_entries == 0) + _m_in->finalize (_m_copier); + if (unlikely (_m_in->_m_final == NULL)) { _m_in->dump_entry (); -- cgit v1.2.1 From 6119d0a9b815c1960b2d1051d79a0a337f306a0c Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Wed, 16 Feb 2011 18:42:29 +0100 Subject: Fetch local hash from pending or finalized entry die. Use it in attr_value. --- libdw/c++/dwarf_output | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 401aec67..f121be0f 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -185,9 +185,7 @@ namespace elfutils { // Precompute our hash value based on our contents. for (iterator i = begin (); i != end (); ++i) - // XXX booo - still aren't handling circularity right... - if (i->second.what_space () != dwarf::VS_reference) - subr::hash_combine (_m_hash, *i); + subr::hash_combine (_m_hash, *i); } inline const _base &base () const @@ -1402,8 +1400,18 @@ namespace elfutils it != _m_children.end (); ++it) { + // child lhash is always in the die_info, which might + // be in the pending_entry when not yet finalized, or + // part of the finalized child die_info. size_t child_lhash; - child_lhash = (*it)->_m_pending->_m_info->_m_local_hash; + struct pending_entry *pending = (*it)->_m_pending; + if (pending) + child_lhash = pending->_m_info->_m_local_hash; + else + { + die_info_pair *final_child = get_final_child (*it); + child_lhash = final_child->second._m_local_hash; + } subr::hash_combine (children_hash, child_lhash); } subr::hash_combine (lhash, children_hash); -- cgit v1.2.1 From 1969a041977cd887be949e9d164b26ea7b9f4494 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 18 Feb 2011 09:58:28 +0100 Subject: Never recalculate local hash, always reuse die_info stored one. --- libdw/c++/dwarf_output | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index f121be0f..8ca98b57 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -1820,7 +1820,7 @@ namespace elfutils { if (_m_final) return _m_final->first.local_hash (); - return _m_pending->calculate_local_hash (); + return _m_pending->_m_info->_m_local_hash; } }; -- cgit v1.2.1 From 3c2d866d87ca26676dbf9603e145266c19e303ab Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 18 Feb 2011 11:03:52 +0100 Subject: Add get_die_info to references, use for hash calculation. --- libdw/c++/dwarf_output | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 8ca98b57..bc681d22 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -393,14 +393,6 @@ namespace elfutils { return 0; } - - /* The hash as used for a reference attribute value that points - to this die. Only uses "local" (non-reference) values. - Result cached in die_info. */ - inline size_t local_hash () const - { - return info ()->second._m_local_hash; - } }; struct value::value_reference @@ -420,9 +412,15 @@ namespace elfutils /* The hash of a value_reference is its referent's local hash, which only takes non-reference values into account. This method is virtual for the circular_reference case, below. */ - virtual size_t hash () const + inline size_t hash () const + { + struct die_info *info = get_die_info (); + return info->_m_local_hash; + } + + virtual die_info *get_die_info () const { - return ref->local_hash (); + return &ref->info ()->second; } }; @@ -602,7 +600,8 @@ namespace elfutils inline die_info (size_t local_hash) : _m_parent (NULL), _m_refs (), _m_originals (), _m_original_cost (0), - _m_with_sibling (), _m_uses (0), _m_local_hash (local_hash) + _m_with_sibling (), _m_uses (0), + _m_local_hash (local_hash) {} inline ~die_info () @@ -1246,9 +1245,9 @@ namespace elfutils /* We have a special case for a reference attribute that is part of a circular chain. It gets calculated from the pending_entry. */ - virtual size_t hash () const + virtual die_info *get_die_info () const { - return pending_entry ()->local_hash (); + return pending_entry ()->get_die_info (); } }; @@ -1816,11 +1815,11 @@ namespace elfutils /* The local hash of the debug_info_entry if we are already final, otherwise get it from the pending_entry. */ - inline size_t local_hash () const + inline die_info *get_die_info () const { if (_m_final) - return _m_final->first.local_hash (); - return _m_pending->_m_info->_m_local_hash; + return &_m_final->second; + return _m_pending->_m_info; } }; -- cgit v1.2.1 From a6abbd6d1396e1238b0dab78ab233cd8bedd70df Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 18 Feb 2011 20:16:03 +0100 Subject: Calculate reference hash before finalizing, store in die_info. Follows whole reference chain (ignoring children) and combines local references of all dies found. Reduces number of attr_set collisions a lot. Unfortunately there are circular reference chains for some larger c++ programs. That was unexpected. Needs cycle detection to figure out what is going on. --- libdw/c++/dwarf_output | 66 +++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 63 insertions(+), 3 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index bc681d22..aeffa036 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -415,7 +415,7 @@ namespace elfutils inline size_t hash () const { struct die_info *info = get_die_info (); - return info->_m_local_hash; + return info->_m_reference_hash; } virtual die_info *get_die_info () const @@ -595,13 +595,21 @@ namespace elfutils std::bitset<2> _m_with_sibling; unsigned int _m_uses; + /* The local hash of the die, set when die_info is created. + Uses only none-reference values. */ size_t _m_local_hash; + /* The reference hash of the die, based on just reference + attribute values. Needs all local hashes of referenced dies + to be set. */ + size_t _m_reference_hash; + inline die_info (size_t local_hash) : _m_parent (NULL), _m_refs (), _m_originals (), _m_original_cost (0), _m_with_sibling (), _m_uses (0), - _m_local_hash (local_hash) + _m_local_hash (local_hash), + _m_reference_hash (0) {} inline ~die_info () @@ -1374,6 +1382,32 @@ namespace elfutils typedef typename final_children_getter:: template copy get_final_children; + inline size_t get_reference_hash () const + { + assert (_m_info != NULL); + + // Could already have been set by forward reference. + if (_m_info->_m_reference_hash != 0) + return _m_info->_m_reference_hash; + + size_t rhash = _m_info->_m_local_hash; + size_t attr_rhashes = 0; + for (attr_map::const_iterator it = _m_attributes.begin (); + it != _m_attributes.end (); + ++it) + { + // XXX XOR is for order irrelevance, but shouldn't be necessary. + // See also calculate_local_hash, which does the same. + const entry *ref + = dynamic_cast (it->second._m_value); + if (ref != NULL) + attr_rhashes ^= ref->get_reference_hash (); + } + subr::hash_combine (rhash, attr_rhashes); + + return rhash; + } + inline size_t calculate_local_hash () { // Calculate the local hash for this new die. @@ -1681,6 +1715,27 @@ namespace elfutils *p.second = true; } + /* Recursively sets up reference hashes for the die_info of this + pending_entry. Depends on all local hashes having been setup + already. At this point all entries are still pending. */ + inline void setup_reference_hash () const + { + _m_pending->_m_info->_m_reference_hash = get_reference_hash (); + + for (typename std::vector::const_iterator it + = _m_pending->_m_children.begin (); + it != _m_pending->_m_children.end (); + ++it) + (*it)->setup_reference_hash (); + } + + inline size_t get_reference_hash () const + { + // XXX Need some recursion detection to assert we aren't + // running in circles. Probably just pass in stack of entries. + return _m_pending->get_reference_hash (); + } + // Attempt to turn the pending entry into a final entry. void finalize (copier *c) { @@ -1915,13 +1970,18 @@ namespace elfutils return *_m_copier; } - /* Try to finalize everything at once. + /* Walk over the whole cu again to set reference hashes up. + Then try to finalize everything at once. Complain if we still have dangling references. If not, it should be impossible to have pending entries left. */ inline die_info_pair *final_unit () const { assert (_m_out == NULL); + // First walk over the whole CU tree again to setup the + // reference hash for each die_info. + _m_in->setup_reference_hash (); + // We should now be able to finalize everything at once. if (_m_copier->_m_undefined_entries == 0) _m_in->finalize (_m_copier); -- cgit v1.2.1 From c3f2fadf9e8fff850aa0851698471600a204e70b Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Mon, 21 Feb 2011 15:21:51 +0100 Subject: Add reference chain cycle detection. --- libdw/c++/dwarf_output | 35 ++++++++++++++++++++++++++++------- 1 file changed, 28 insertions(+), 7 deletions(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index aeffa036..1f756f69 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -1382,7 +1382,7 @@ namespace elfutils typedef typename final_children_getter:: template copy get_final_children; - inline size_t get_reference_hash () const + inline size_t get_reference_hash (std::vector &stack) const { assert (_m_info != NULL); @@ -1401,7 +1401,7 @@ namespace elfutils const entry *ref = dynamic_cast (it->second._m_value); if (ref != NULL) - attr_rhashes ^= ref->get_reference_hash (); + attr_rhashes ^= ref->get_reference_hash (stack); } subr::hash_combine (rhash, attr_rhashes); @@ -1720,7 +1720,9 @@ namespace elfutils already. At this point all entries are still pending. */ inline void setup_reference_hash () const { - _m_pending->_m_info->_m_reference_hash = get_reference_hash (); + std::vector stack; + _m_pending->_m_info->_m_reference_hash = get_reference_hash (stack); + assert (stack.empty ()); for (typename std::vector::const_iterator it = _m_pending->_m_children.begin (); @@ -1729,11 +1731,30 @@ namespace elfutils (*it)->setup_reference_hash (); } - inline size_t get_reference_hash () const + inline size_t get_reference_hash (std::vector &stack) const { - // XXX Need some recursion detection to assert we aren't - // running in circles. Probably just pass in stack of entries. - return _m_pending->get_reference_hash (); + if (std::find (stack.begin (), stack.end (), this) != stack.end ()) + { + std::cout << "Reference chain cycle detected\n" + << "offset=[0x" << std::hex << _m_offset << std::dec + << "] already on the reference chain stack\n"; + typename std::vector::iterator it; + for (it = stack.begin (); + it != stack.end (); + it++) + { + std::cout << "offset=[0x" << std::hex << (*it)->_m_offset + << std::dec << "] " + << dwarf::tags::name ((*it)->_m_pending->_m_tag) + << "\n"; + } + abort (); + } + + stack.push_back (this); + size_t res = _m_pending->get_reference_hash (stack); + stack.pop_back (); + return res; } // Attempt to turn the pending entry into a final entry. -- cgit v1.2.1 From 2664290538c387bca3b8f05d3e3f8a8894aa5958 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Mon, 21 Feb 2011 16:58:26 +0100 Subject: Workaround weird (buggy) self referential DW_AT_containing_type case. https://fedorahosted.org/pipermail/elfutils-devel/2011-February/001792.html --- libdw/c++/dwarf_output | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/libdw/c++/dwarf_output b/libdw/c++/dwarf_output index 1f756f69..aeb192c4 100644 --- a/libdw/c++/dwarf_output +++ b/libdw/c++/dwarf_output @@ -1401,7 +1401,15 @@ namespace elfutils const entry *ref = dynamic_cast (it->second._m_value); if (ref != NULL) - attr_rhashes ^= ref->get_reference_hash (stack); + { + // Workaround weird case (bug?) + // https://fedorahosted.org/pipermail/elfutils-devel/2011-February/001792.html + if (it->first == DW_AT_containing_type + && ref->_m_pending == this) + continue; + else + attr_rhashes ^= ref->get_reference_hash (stack); + } } subr::hash_combine (rhash, attr_rhashes); -- cgit v1.2.1