[PATCH 5/7] Correctly handle DIE parent computations

[Tom Tromey <tom@tromey.com>]

Tom de Vries pointed out that the combination of sharding,
multi-threading, and per-CU "racing" means that sometimes a cross-CU
DIE reference might not be correctly resolved.  However, it's
important to handle this correctly, due to some unfortunate aspects of
DWARF.

This patch implements this by arranging to preserve each worker's DIE
map through the end of index finalization.  The extra data is
discarded when finalization is done.  This approach also allows the
parent name resolution to be sharded, by integrating it into the
existing entry finalization loop.

In an earlier review, I remarked that addrmap couldn't be used here.
However, I was mistaken.  A *mutable* addrmap cannot be used, as those
are based on splay trees and restructure the tree even during lookups
(and thus aren't thread-safe).  A fixed addrmap, on the other hand, is
just a vector and is thread-safe.

Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=30846
---
 gdb/dwarf2/cooked-index.c | 13 ++++++++---
 gdb/dwarf2/cooked-index.h | 45 ++++++++++++++++++++++++++++--------
 gdb/dwarf2/read.c         | 59 ++++++++++++++++++++---------------------------
 3 files changed, 70 insertions(+), 47 deletions(-)

diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c
index e4f112b6ee0..93370f96bec 100644
--- a/gdb/dwarf2/cooked-index.c
+++ b/gdb/dwarf2/cooked-index.c
@@ -319,7 +319,7 @@ cooked_index_shard::handle_gnat_encoded_entry (cooked_index_entry *entry,
 /* See cooked-index.h.  */
 
 void
-cooked_index_shard::finalize ()
+cooked_index_shard::finalize (const parent_map_map *parent_maps)
 {
   auto hash_name_ptr = [] (const void *p)
     {
@@ -360,6 +360,13 @@ cooked_index_shard::finalize ()
 
   for (cooked_index_entry *entry : m_entries)
     {
+      if ((entry->flags & IS_PARENT_DEFERRED) != 0)
+	{
+	  const cooked_index_entry *new_parent
+	    = parent_maps->find (entry->get_deferred_parent ());
+	  entry->resolve_parent (new_parent);
+	}
+
       /* Note that this code must be kept in sync with
 	 language_requires_canonicalization.  */
       gdb_assert (entry->canonical == nullptr);
@@ -479,7 +486,7 @@ cooked_index::wait (cooked_state desired_state, bool allow_quit)
 }
 
 void
-cooked_index::set_contents (vec_type &&vec)
+cooked_index::set_contents (vec_type &&vec, const parent_map_map *parent_maps)
 {
   gdb_assert (m_vector.empty ());
   m_vector = std::move (vec);
@@ -502,7 +509,7 @@ cooked_index::set_contents (vec_type &&vec)
   for (auto &idx : m_vector)
     {
       auto this_index = idx.get ();
-      finalizers.add_task ([=] () { this_index->finalize (); });
+      finalizers.add_task ([=] () { this_index->finalize (parent_maps); });
     }
 
   finalizers.start ();
diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index 442ee9e14fd..d8e6fe476a4 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -392,9 +392,9 @@ class cooked_index_shard
 
   /* Finalize the index.  This should be called a single time, when
      the index has been fully populated.  It enters all the entries
-     into the internal table.  This may be invoked in a worker
-     thread.  */
-  void finalize ();
+     into the internal table and fixes up all missing parent links.
+     This may be invoked in a worker thread.  */
+  void finalize (const parent_map_map *parent_maps);
 
   /* Storage for the entries.  */
   auto_obstack m_storage;
@@ -459,6 +459,19 @@ class cooked_index_storage
     return &m_addrmap;
   }
 
+  /* Return the parent_map that is currently being created.  */
+  parent_map *get_parent_map ()
+  {
+    return &m_parent_map;
+  }
+
+  /* Return the parent_map that is currently being created.  Ownership
+     is passed to the caller.  */
+  parent_map release_parent_map ()
+  {
+    return std::move (m_parent_map);
+  }
+
 private:
 
   /* Hash function for a cutu_reader.  */
@@ -474,6 +487,9 @@ class cooked_index_storage
   /* The index shard that is being constructed.  */
   std::unique_ptr<cooked_index_shard> m_index;
 
+  /* Parent map for each CU that is read.  */
+  parent_map m_parent_map;
+
   /* A writeable addrmap being constructed by this scanner.  */
   addrmap_mutable m_addrmap;
 };
@@ -544,13 +560,17 @@ class cooked_index_worker
  		    unit_iterator end);
 
   /* Each thread returns a tuple holding a cooked index, any collected
-     complaints, and a vector of errors that should be printed.  The
-     latter is done because GDB's I/O system is not thread-safe.
-     run_on_main_thread could be used, but that would mean the
-     messages are printed after the prompt, which looks weird.  */
+     complaints, a vector of errors that should be printed, and a
+     vector of parent maps.
+
+     The errors are retained because GDB's I/O system is not
+     thread-safe.  run_on_main_thread could be used, but that would
+     mean the messages are printed after the prompt, which looks
+     weird.  */
   using result_type = std::tuple<std::unique_ptr<cooked_index_shard>,
 				 complaint_collection,
-				 std::vector<gdb_exception>>;
+				 std::vector<gdb_exception>,
+				 parent_map>;
 
   /* The per-objfile object.  */
   dwarf2_per_objfile *m_per_objfile;
@@ -567,6 +587,10 @@ class cooked_index_worker
      This is enforced in the cooked_index_worker constructor.  */
   deferred_warnings m_warnings;
 
+  /* A map of all parent maps.  Used during finalization to fix up
+     parent relationships.  */
+  parent_map_map m_all_parents_map;
+
 #if CXX_STD_THREAD
   /* Current state of this object.  */
   cooked_state m_state = cooked_state::INITIAL;
@@ -654,8 +678,9 @@ class cooked_index : public dwarf_scanner_base
   void start_reading ();
 
   /* Called by cooked_index_worker to set the contents of this index
-     and transition to the MAIN_AVAILABLE state.  */
-  void set_contents (vec_type &&vec);
+     and transition to the MAIN_AVAILABLE state.  PARENT_MAPS is used
+     when resolving pending parent links.  */
+  void set_contents (vec_type &&vec, const parent_map_map *parent_maps);
 
   /* A range over a vector of subranges.  */
   using range = range_chain<cooked_index_shard::range>;
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index 585c15212f8..494f2b5625c 100644
--- a/gdb/dwarf2/read.c
+++ b/gdb/dwarf2/read.c
@@ -4463,7 +4463,8 @@ class cooked_indexer
 		  enum language language)
     : m_index_storage (storage),
       m_per_cu (per_cu),
-      m_language (language)
+      m_language (language),
+      m_die_range_map (storage->get_parent_map ())
   {
   }
 
@@ -4538,18 +4539,8 @@ class cooked_indexer
   /* The language that we're assuming when reading.  */
   enum language m_language;
 
-  /* Map from DIE ranges to newly-created entries.  See
-     m_deferred_entries to understand this.  */
-  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::vector<cooked_index_entry *> m_deferred_entries;
+  /* Map from DIE ranges to newly-created entries.  */
+  parent_map *m_die_range_map;
 };
 
 /* Subroutine of dwarf2_build_psymtabs_hard to simplify it.
@@ -4866,7 +4857,8 @@ cooked_index_worker::process_cus (size_t task_number, unit_iterator first,
 
   m_results[task_number] = result_type (thread_storage.release (),
 					complaint_handler.release (),
-					std::move (errors));
+					std::move (errors),
+					std::move (thread_storage.release_parent_map ()));
 }
 
 void
@@ -4876,7 +4868,10 @@ cooked_index_worker::done_reading ()
      can only be dealt with on the main thread.  */
   std::vector<std::unique_ptr<cooked_index_shard>> indexes;
   for (auto &one_result : m_results)
-    indexes.push_back (std::move (std::get<0> (one_result)));
+    {
+      indexes.push_back (std::move (std::get<0> (one_result)));
+      m_all_parents_map.add_map (std::get<3> (one_result));
+    }
 
   /* This has to wait until we read the CUs, we need the list of DWOs.  */
   process_skeletonless_type_units (m_per_objfile, &m_index_storage);
@@ -4884,11 +4879,13 @@ cooked_index_worker::done_reading ()
   indexes.push_back (m_index_storage.release ());
   indexes.shrink_to_fit ();
 
+  m_all_parents_map.add_map (m_index_storage.release_parent_map ());
+
   dwarf2_per_bfd *per_bfd = m_per_objfile->per_bfd;
   cooked_index *table
     = (gdb::checked_static_cast<cooked_index *>
        (per_bfd->index_table.get ()));
-  table->set_contents (std::move (indexes));
+  table->set_contents (std::move (indexes), &m_all_parents_map);
 }
 
 void
@@ -16327,13 +16324,17 @@ cooked_indexer::scan_attributes (dwarf2_per_cu_data *scanning_per_cu,
 
 	  if (*parent_entry == nullptr)
 	    {
+	      /* We only perform immediate lookups of parents for DIEs
+		 from earlier in this CU.  This avoids any problem
+		 with a NULL result when when we see a reference to a
+		 DIE in another CU that we may or may not have
+		 imported locally.  */
 	      parent_map::addr_type addr
 		= parent_map::form_addr (origin_offset, origin_is_dwz);
-	      if (new_reader->cu == reader->cu
-		  && new_info_ptr > watermark_ptr)
+	      if (new_reader->cu != reader->cu || new_info_ptr > watermark_ptr)
 		*maybe_defer = addr;
 	      else
-		*parent_entry = m_die_range_map.find (addr);
+		*parent_entry = m_die_range_map->find (addr);
 	    }
 
 	  unsigned int bytes_read;
@@ -16457,7 +16458,7 @@ cooked_indexer::recurse (cutu_reader *reader,
       parent_map::addr_type end
 	= parent_map::form_addr (sect_offset (info_ptr - 1 - reader->buffer),
 				 reader->cu->per_cu->is_dwz);
-      m_die_range_map.add_entry (start, end, parent_entry);
+      m_die_range_map->add_entry (start, end, parent_entry);
     }
 
   return info_ptr;
@@ -16534,13 +16535,10 @@ cooked_indexer::index_dies (cutu_reader *reader,
       if (name != nullptr)
 	{
 	  if (defer != 0)
-	    {
-	      this_entry
-		= m_index_storage->add (this_die, abbrev->tag,
-					flags | IS_PARENT_DEFERRED, name,
-					defer, m_per_cu);
-	      m_deferred_entries.push_back (this_entry);
-	    }
+	    this_entry
+	      = m_index_storage->add (this_die, abbrev->tag,
+				      flags | IS_PARENT_DEFERRED, name,
+				      defer, m_per_cu);
 	  else
 	    this_entry
 	      = m_index_storage->add (this_die, abbrev->tag, flags, name,
@@ -16632,13 +16630,6 @@ cooked_indexer::make_index (cutu_reader *reader)
   if (!reader->comp_unit_die->has_children)
     return;
   index_dies (reader, reader->info_ptr, nullptr, false);
-
-  for (const auto &entry : m_deferred_entries)
-    {
-      const cooked_index_entry *parent
-	= m_die_range_map.find (entry->get_deferred_parent ());
-      entry->resolve_parent (parent);
-    }
 }
 
 /* An implementation of quick_symbol_functions for the cooked DWARF

-- 
2.43.0