On 12/12/23 20:27, Tom Tromey wrote:
>>>>>> "Tom" == Tom de Vries <tdevries@suse.de> writes:
>
> Tom> +cooked_index_entry parent_map::deferred((sect_offset)0, (dwarf_tag)0,
> Tom> + (cooked_index_flag)0, nullptr,
> Tom> + nullptr, nullptr);
>
> Several missing spaces.
> > However see the other note. Maybe this isn't needed.
>
> Tom> cooked_index::cooked_index (vec_type &&vec)
> Tom> : m_vector (std::move (vec))
> Tom> {
> Tom> + handle_deferred_entries ();
> Tom> +
> Tom> for (auto &idx : m_vector)
> Tom> idx->finalize ();
>
> Here, parent resolution is single-threaded. However, I think it can
> probably be handled entirely in finalize -- and therefore distributed to
> worker threads. However, some changes are needed.
>
> Tom> +const cooked_index_entry *
> Tom> +cooked_index::find_parent_deferred_entry
> Tom> + (const cooked_index_shard::deferred_entry &entry) const
> Tom> +{
> Tom> + const cooked_index_entry *parent_entry = nullptr;
> Tom> + for (auto &parent_map_shard : m_vector)
> Tom> + {
> Tom> + auto res = parent_map_shard->find_parent (entry.spec_offset);
>
> The main issue with threading is that addrmaps are not thread-safe.
> They are implemented as splay trees and these restructure themselves
> during lookups.
>
> However, I'm not sure we need splay trees. Instead, it seems to me that
> the relevant parts of the DIE tree can be handled with a sorted vector
> that maps DIE ranges to entries.
>
> Then, parent resolution can be done by binary search, and this can be
> done by each shard in parallel -- and in particular, in do_finalize,
> because that is already visiting every entry anyway.
>
That'll still have to take care of inter-shard dependencies somehow.
> Tom> +void
> Tom> +cooked_index::handle_deferred_entries ()
> Tom> +{
> Tom> + bool changed;
> Tom> + bool deferred;
> Tom> + do
> Tom> + {
> Tom> + deferred = false;
> Tom> + changed = false;
> Tom> + for (auto &shard : m_vector)
> Tom> + for (auto it = shard->m_deferred_entries->begin ();
> Tom> + it != shard->m_deferred_entries->end (); )
> Tom> + {
> Tom> + const cooked_index_entry *parent_entry
> Tom> + = find_parent_deferred_entry (*it);
> Tom> + if (parent_entry == &parent_map::deferred)
> Tom> + {
> Tom> + deferred = true;
> Tom> + it++;
> Tom> + continue;
> Tom> + }
> Tom> + shard->resolve_deferred_entry (*it, parent_entry);
> Tom> + it = shard->m_deferred_entries->erase (it);
> Tom> + changed = true;
>
> I don't really understand this method.
>
> What is the scenario leading to the need for 'deferred' and multiple
> iterations?
>
Investigated by adding a "gdb_assert (false)" at "deferred = true".
For instance, this triggers with
/usr/lib/debug/usr/lib64/gcc/x86_64-suse-linux/7/gnat1-7.5.0+r278197-150000.4.35.1.x86_64.debug.
There's a DIE:
...
<2><d952b5>: Abbrev Number: 46 (DW_TAG_inlined_subroutine)
<d952b6> DW_AT_abstract_origin: <0x56f99>
<d952ba> DW_AT_low_pc : 0xfefc33
<d952c2> DW_AT_high_pc : 18
<d952c3> DW_AT_call_file : 1
<d952c4> DW_AT_call_line : 1811
<d952c6> DW_AT_sibling : <0xd952d4>
...
whose parent is the parent of DIE 0x56f99:
...
<1><56f99>: Abbrev Number: 88 (DW_TAG_subprogram)
<56f9a> DW_AT_specification: <0x5520e>
<56f9e> DW_AT_object_pointer: <0x56fa1>
<56f9f> DW_AT_inline : 3 (declared as inline and inlined)
<56fa0> DW_AT_object_pointer: <0x56fa1>
...
whose parent is the parent of DIE 0x5520e:
...
<2><5520e>: Abbrev Number: 58 (DW_TAG_subprogram)
<5520f> DW_AT_external : 1
<5520f> DW_AT_name : (indirect string, offset: 0x15762e):
operator[]
<55213> DW_AT_decl_file : 3
<55214> DW_AT_decl_line : 1217
<55216> DW_AT_linkage_name: (indirect string, offset: 0x3dd5b3):
_ZN3vecIPKc7va_heap6vl_ptrEixEj
<5521a> DW_AT_type : <0x15e233>
<5521e> DW_AT_declaration : 1
<5521e> DW_AT_object_pointer: <0x55222>
<55220> DW_AT_sibling : <0x5522b>
...
So, two DIEs are deferred, and resolving them can happen only in one
specific order. If the loop encounters them in the wrong order, it
skips the first one in the first iteration, and handles it in the second
one.
> Tom> + for (auto &shard : m_vector)
> Tom> + {
> Tom> + shard->m_die_range_map.reset (nullptr);
> Tom> + shard->m_deferred_entries.reset (nullptr);
> Tom> + }
> Tom> +}
>
> In the background reading series, there's a new cooked_index_worker that
> holds data that is needed before scanning is complete. These things
> could be put there instead.
Ack.
Thanks,
- Tom
@@ -228,6 +228,12 @@ cooked_index_entry::write_scope (struct obstack *storage,
/* See cooked-index.h. */
+cooked_index_entry parent_map::deferred((sect_offset)0, (dwarf_tag)0,
+ (cooked_index_flag)0, nullptr,
+ nullptr, nullptr);
+
+/* See cooked-index.h. */
+
const cooked_index_entry *
cooked_index_shard::add (sect_offset die_offset, enum dwarf_tag tag,
cooked_index_flag flags, const char *name,
@@ -450,6 +456,8 @@ cooked_index_shard::wait (bool allow_quit) const
cooked_index::cooked_index (vec_type &&vec)
: m_vector (std::move (vec))
{
+ handle_deferred_entries ();
+
for (auto &idx : m_vector)
idx->finalize ();
@@ -648,6 +656,75 @@ cooked_index::maybe_write_index (dwarf2_per_bfd *per_bfd,
global_index_cache.store (per_bfd, ctx);
}
+/* See cooked-index.h. */
+
+const cooked_index_entry *
+cooked_index_shard::resolve_deferred_entry
+ (const deferred_entry &de, const cooked_index_entry *parent_entry)
+{
+ reset_parent_deferred (parent_map::form_addr (de.die_offset, de.per_cu_2->is_dwz,
+ de.per_cu_2->is_debug_types));
+ return add (de.die_offset, de.tag, de.flags, de.name,
+ parent_entry, de.per_cu);
+}
+
+/* See cooked-index.h. */
+
+const cooked_index_entry *
+cooked_index::find_parent_deferred_entry
+ (const cooked_index_shard::deferred_entry &entry) const
+{
+ const cooked_index_entry *parent_entry = nullptr;
+ for (auto &parent_map_shard : m_vector)
+ {
+ auto res = parent_map_shard->find_parent (entry.spec_offset);
+ if (res != nullptr)
+ {
+ parent_entry = res;
+ break;
+ }
+ }
+
+ return parent_entry;
+}
+
+/* See cooked-index.h. */
+
+void
+cooked_index::handle_deferred_entries ()
+{
+ bool changed;
+ bool deferred;
+ do
+ {
+ deferred = false;
+ changed = false;
+ for (auto &shard : m_vector)
+ for (auto it = shard->m_deferred_entries->begin ();
+ it != shard->m_deferred_entries->end (); )
+ {
+ const cooked_index_entry *parent_entry
+ = find_parent_deferred_entry (*it);
+ if (parent_entry == &parent_map::deferred)
+ {
+ deferred = true;
+ it++;
+ continue;
+ }
+ shard->resolve_deferred_entry (*it, parent_entry);
+ it = shard->m_deferred_entries->erase (it);
+ changed = true;
+ }
+ }
+ while (changed && deferred);
+
+ for (auto &shard : m_vector)
+ {
+ shard->m_die_range_map.reset (nullptr);
+ shard->m_deferred_entries.reset (nullptr);
+ }
+}
+
/* Wait for all the index cache entries to be written before gdb
exits. */
static void
@@ -34,6 +34,7 @@
#include "dwarf2/mapped-index.h"
#include "dwarf2/tag.h"
#include "gdbsupport/range-chain.h"
+#include <unordered_set>
struct dwarf2_per_cu_data;
struct dwarf2_per_bfd;
@@ -242,19 +243,29 @@ struct cooked_index_entry : public allocate_on_obstack
class parent_map
{
public:
+ /* A dummy cooked_index_entry to mark that computing the parent has been
+ deferred. */
+ static cooked_index_entry deferred;
+
/* A helper function to turn a section offset into an address that
can be used in a parent_map. */
- static CORE_ADDR form_addr (sect_offset offset, bool is_dwz)
+ static CORE_ADDR form_addr (sect_offset offset, bool is_dwz,
+ bool is_debug_types)
{
CORE_ADDR value = to_underlying (offset);
if (is_dwz)
value |= ((CORE_ADDR) 1) << (8 * sizeof (CORE_ADDR) - 1);
+ if (is_debug_types)
+ value |= ((CORE_ADDR) 1) << (8 * sizeof (CORE_ADDR) - 2);
return value;
}
/* Find the parent of DIE LOOKUP. */
const cooked_index_entry *find_parent (CORE_ADDR lookup) const
{
+ if (m_deferred.find (lookup) != m_deferred.end ())
+ return &parent_map::deferred;
+
const void *obj = m_parent_map.find (lookup);
return static_cast<const cooked_index_entry *> (obj);
}
@@ -265,12 +276,28 @@ class parent_map
{
/* Calling set_empty with nullptr is currently not allowed. */
if (parent_entry != nullptr)
- m_parent_map.set_empty (start, end, (void *)parent_entry);
+ {
+ gdb_assert (parent_entry != &parent_map::deferred);
+ m_parent_map.set_empty (start, end, (void *)parent_entry);
+ }
+ }
+
+ void set_parent_deferred (CORE_ADDR addr)
+ {
+ m_deferred.emplace (addr);
+ }
+
+ void reset_parent_deferred (CORE_ADDR addr)
+ {
+ m_deferred.erase (addr);
}
private:
/* An addrmap that maps from section offsets to cooked_index_entry *. */
addrmap_mutable m_parent_map;
+
+ /* DIEs that are deffered. */
+ std::unordered_set<CORE_ADDR> m_deferred;
};
class cooked_index;
@@ -285,7 +312,12 @@ class cooked_index;
class cooked_index_shard
{
public:
- cooked_index_shard () = default;
+ cooked_index_shard ()
+ {
+ m_die_range_map.reset (new parent_map);
+ m_deferred_entries.reset (new std::vector<deferred_entry>);
+ }
+
DISABLE_COPY_AND_ASSIGN (cooked_index_shard);
/* Create a new cooked_index_entry and register it with this object.
@@ -329,6 +361,52 @@ class cooked_index_shard
for completion, will be returned. */
range find (const std::string &name, bool completing) const;
+ /* Find the parent of DIE LOOKUP. */
+ const cooked_index_entry *
+ find_parent (CORE_ADDR lookup) const
+ {
+ return m_die_range_map->find_parent (lookup);
+ }
+
+ /* Set the parent of DIES in range [START, END] to PARENT_ENTRY. */
+ void set_parent (CORE_ADDR start, CORE_ADDR end,
+ const cooked_index_entry *parent_entry)
+ {
+ m_die_range_map->set_parent (start, end, parent_entry);
+ }
+
+ void set_parent_deferred (CORE_ADDR addr)
+ {
+ m_die_range_map->set_parent_deferred (addr);
+ }
+
+ void reset_parent_deferred (CORE_ADDR addr)
+ {
+ m_die_range_map->reset_parent_deferred (addr);
+ }
+
+ /* A single deferred entry. See m_deferred_entries. */
+ struct deferred_entry
+ {
+ sect_offset die_offset;
+ const char *name;
+ CORE_ADDR spec_offset;
+ dwarf_tag tag;
+ cooked_index_flag flags;
+ dwarf2_per_cu_data *per_cu;
+ dwarf2_per_cu_data *per_cu_2;
+ };
+
+ /* Defer creating a cooked_index_entry corresponding to DEFERRED. */
+ void defer_entry (deferred_entry de)
+ {
+ m_deferred_entries->push_back (de);
+ }
+
+ /* Variant of add that takes a deferred_entry as parameter. */
+ const cooked_index_entry *resolve_deferred_entry
+ (const deferred_entry &entry, const cooked_index_entry *parent_entry);
+
private:
/* Return the entry that is believed to represent the program's
@@ -386,6 +464,20 @@ class cooked_index_shard
that the 'get' method is never called on this future, only
'wait'. */
gdb::future<void> m_future;
+
+ /* An addrmap that maps from section offsets (see the form_addr
+ method) to newly-created entries. See m_deferred_entries to
+ understand this. */
+ std::unique_ptr<parent_map> m_die_range_map;
+
+ /* The generated DWARF can sometimes have the declaration for a
+ method in a class (or perhaps namespace) scope, with the
+ definition appearing outside this scope... just one of the many
+ bad things about DWARF. In order to handle this situation, we
+ defer certain entries until the end of scanning, at which point
+ we'll know the containing context of all the DIEs that we might
+ have scanned. This vector stores these deferred entries. */
+ std::unique_ptr<std::vector<deferred_entry>> m_deferred_entries;
};
/* The main index of DIEs. The parallel DIE indexers create
@@ -469,6 +561,13 @@ class cooked_index : public dwarf_scanner_base
private:
+ /* Find the parent corresponding to deferred entry ENTRY. */
+ const cooked_index_entry *find_parent_deferred_entry
+ (const cooked_index_shard::deferred_entry &entry) const;
+
+ /* Create cooked_index_entries for the deferred entries. */
+ void handle_deferred_entries ();
+
/* Maybe write the index to the index cache. */
void maybe_write_index (dwarf2_per_bfd *per_bfd,
const index_cache_store_context &);
@@ -4491,6 +4491,31 @@ class cooked_index_storage
return &m_addrmap;
}
+ /* Find the parent of DIE LOOKUP. */
+ const cooked_index_entry *find_parent (CORE_ADDR lookup)
+ {
+ return m_index->find_parent (lookup);
+ }
+
+ /* Set the parent of DIES in range [START, END] to PARENT_ENTRY. */
+ void set_parent (CORE_ADDR start, CORE_ADDR end,
+ const cooked_index_entry *parent_entry)
+ {
+ m_index->set_parent (start, end, parent_entry);
+ }
+
+ /* Set the parent of DIE at ADDR as deferred. */
+ void set_parent_deferred (CORE_ADDR addr)
+ {
+ m_index->set_parent_deferred (addr);
+ }
+
+ /* Defer creating a cooked_index_entry corresponding to deferred_entry DE. */
+ void defer_entry (cooked_index_shard::deferred_entry de)
+ {
+ m_index->defer_entry (de);
+ }
+
private:
/* Hash function for a cutu_reader. */
@@ -4613,59 +4638,26 @@ class cooked_indexer
/* Find the parent of DIE LOOKUP. */
const cooked_index_entry *find_parent (CORE_ADDR lookup) const
{
- return m_die_range_map.find_parent (lookup);
+ return m_index_storage->find_parent (lookup);
}
/* Set the parent of DIES in range [START, END] to PARENT_ENTRY. */
void set_parent (CORE_ADDR start, CORE_ADDR end,
const cooked_index_entry *parent_entry)
{
- m_die_range_map.set_parent (start, end, parent_entry);
+ m_index_storage->set_parent (start, end, parent_entry);
}
- /* A single deferred entry. */
- struct deferred_entry
- {
- sect_offset die_offset;
- const char *name;
- CORE_ADDR spec_offset;
- dwarf_tag tag;
- cooked_index_flag flags;
- };
-
- /* The generated DWARF can sometimes have the declaration for a
- method in a class (or perhaps namespace) scope, with the
- definition appearing outside this scope... just one of the many
- bad things about DWARF. In order to handle this situation, we
- defer certain entries until the end of scanning, at which point
- we'll know the containing context of all the DIEs that we might
- have scanned. This vector stores these deferred entries. */
- std::vector<deferred_entry> m_deferred_entries;
-
- /* Defer creating a cooked_index_entry corresponding to deferred_entry DE. */
- void defer_entry (const deferred_entry &de)
+ /* Set the parent of DIE at ADDR as deferred. */
+ void set_parent_deferred (CORE_ADDR addr)
{
- m_deferred_entries.push_back (de);
+ m_index_storage->set_parent_deferred (addr);
}
- /* Create a cooked_index_entry corresponding to deferred_entry DE with
- parent PARENT_ENTRY. */
- const cooked_index_entry *resolve_deferred_entry
- (const deferred_entry &de, const cooked_index_entry *parent_entry)
- {
- return m_index_storage->add (de.die_offset, de.tag, de.flags, de.name,
- parent_entry, m_per_cu);
- }
-
- /* Create cooked_index_entries for the deferred entries. */
- void handle_deferred_entries ()
+ /* Defer creating a cooked_index_entry corresponding to deferred_entry DE. */
+ void defer_entry (const cooked_index_shard::deferred_entry &de)
{
- for (const auto &entry : m_deferred_entries)
- {
- const cooked_index_entry *parent_entry
- = find_parent (entry.spec_offset);
- resolve_deferred_entry (entry, parent_entry);
- }
+ m_index_storage->defer_entry (de);
}
};
@@ -16201,13 +16193,36 @@ cooked_indexer::scan_attributes (dwarf2_per_cu_data *scanning_per_cu,
if (*parent_entry == nullptr)
{
+ gdb_assert (reader->cu->per_cu->is_debug_types
+ == new_reader->cu->per_cu->is_debug_types);
CORE_ADDR addr
- = parent_map::form_addr (origin_offset, origin_is_dwz);
- if (new_reader->cu == reader->cu
- && new_info_ptr > watermark_ptr)
- *maybe_defer = addr;
+ = parent_map::form_addr (origin_offset, origin_is_dwz,
+ reader->cu->per_cu->is_debug_types);
+ if (new_reader->cu == reader->cu)
+ {
+ /* Intra-CU case. */
+ if (new_info_ptr > watermark_ptr)
+ {
+ /* Defer because origin is not read yet. */
+ *maybe_defer = addr;
+ }
+ else
+ {
+ auto tmp = find_parent (addr);
+ if (tmp == &parent_map::deferred)
+ {
+ /* Defer because origin is deferred. */
+ *maybe_defer = addr;
+ }
+ else
+ *parent_entry = tmp;
+ }
+ }
else
- *parent_entry = find_parent (addr);
+ {
+ /* Inter-CU case. */
+ *maybe_defer = addr;
+ }
}
unsigned int bytes_read;
@@ -16327,10 +16342,12 @@ cooked_indexer::recurse (cutu_reader *reader,
limit the range to the children of parent_entry. */
CORE_ADDR start
= parent_map::form_addr (parent_entry->die_offset + 1,
- reader->cu->per_cu->is_dwz);
+ reader->cu->per_cu->is_dwz,
+ reader->cu->per_cu->is_debug_types);
CORE_ADDR end
= parent_map::form_addr (sect_offset (info_ptr - 1 - reader->buffer),
- reader->cu->per_cu->is_dwz);
+ reader->cu->per_cu->is_dwz,
+ reader->cu->per_cu->is_debug_types);
set_parent (start, end, parent_entry);
}
@@ -16397,9 +16414,16 @@ cooked_indexer::index_dies (cutu_reader *reader,
if (name != nullptr)
{
if (defer != 0)
- defer_entry ({
- this_die, name, defer, abbrev->tag, flags
- });
+ {
+ CORE_ADDR addr
+ = parent_map::form_addr (this_die, reader->cu->per_cu->is_dwz,
+ reader->cu->per_cu->is_debug_types);
+ set_parent_deferred (addr);
+ defer_entry ({
+ this_die, name, defer, abbrev->tag, flags, m_per_cu,
+ reader->cu->per_cu
+ });
+ }
else
this_entry = m_index_storage->add (this_die, abbrev->tag, flags,
name, this_parent_entry,
@@ -16501,8 +16525,6 @@ cooked_indexer::make_index (cutu_reader *reader)
if (!reader->comp_unit_die->has_children)
return;
index_dies (reader, reader->info_ptr, nullptr, false);
-
- handle_deferred_entries ();
}
/* An implementation of quick_symbol_functions for the cooked DWARF