Re: [PATCH v2 05/13] [gdb/symtab] Resolve deferred entries, inter-shard case

[Tom de Vries <tdevries@suse.de>]

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