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

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

Generically solve the case of inter-CU dependencies, including inter-shard
dependencies:
- mark deferred entries in new data structure m_deferred,
- return &parent_map::deferred in find_parent for deferred entries,
- defer all intra-CU dependencies that depend on deferred entries,
- defer all inter-CU dependencies (note that two subsequent patches implement
  optimizations to deal with this more optimally),
- move m_die_range_map and m_deferred_dies to cooked_index_shard, and
- move handle_deferred_dies to the cooked_index, where it is called in the
  constructor, and update it to handle the intra-shard case.

Handling units from the .debug_info section alongside units from the
.debug_types section requires us to extend form_addr to take is_debug_types
into account.

Tested on x86_64-linux.

PR symtab/30846
Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=30846
---
 gdb/dwarf2/cooked-index.c |  77 +++++++++++++++++++++++
 gdb/dwarf2/cooked-index.h | 105 ++++++++++++++++++++++++++++++-
 gdb/dwarf2/read.c         | 128 ++++++++++++++++++++++----------------
 3 files changed, 254 insertions(+), 56 deletions(-)

diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c
index ba77f9cb373..ba37d4a820c 100644
--- a/gdb/dwarf2/cooked-index.c
+++ b/gdb/dwarf2/cooked-index.c
@@ -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
diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index 3c43717fc33..de54a788c42 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -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 &);
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index cf71d4c55ce..ec58125499c 100644
--- a/gdb/dwarf2/read.c
+++ b/gdb/dwarf2/read.c
@@ -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
-- 
2.35.3