[PATCH v6 1/3] gdb/dwarf: split cooked index finalization into separate steps

[Simon Marchi <simon.marchi@efficios.com>]

This patch refactors the existing cooked index "finalize" step into
multiple steps.  This is a preparatory patch for the following patch,
which will add some more steps.  I believe that using this pattern will
help keep the code readable and easy to understand, despite the
increasing amount of work done.

The following patch introduces a step that needs to run after the
deferred parents have been resolved, but before the name
canonicalization happens, so factor out the deferred parents code into a
step of its own.

The code that remains in cooked_index_shard::finalize is all about name
canonicalization (if we consider the Ada stuff to be a special case of
that), so rename that step to cooked_index_shard::canonicalize_names().

For clarity, move the "write to cache" code out of the "done" callback
to make it clear that it is logically a separate step.

So as of this patch, we have the steps:

 - resolve deferred parents
 - canonicalize names
 - write to cache

The term "finalization" now refers to all these steps.  Or, depending on
your definition, it could refer to all but "write to cache", since the
index reaches the FINALIZED state (i.e. becomes fully usable) just
before that one.

Here are the implementation details:

 - The first step is called by cooked_index::set_contents(), then each
   step is responsible for calling the next one (thus forming a chain),
   until we are done.

 - Steps that involve per-shard parallel processing use gdb::task_group,
   the "done" callback of the task_group starts the next task.

   A special case of that is: if some steps are able to detect ahead of
   time that it's unnecessary to run the step for a given shard, they
   can omit adding a task for that shard.

   An even more special case of that is: if no tasks are added to a task
   group, the "done" callback for that task group is invoked
   immediately when the group is started.  This allows easily and
   cheaply skipping entire steps when they are not needed.

   This is used in this patch for the new "resolve deferred parents"
   step.  Each shard records whether it has at least one deferred parent
   during the initial scan.  If a shard has none (which is a common
   case), then cooked_index_shard::resolve_deferred_parents would
   iterate the index entries for nothing.  The step therefore omits
   adding a task for that shard in that case.  If no shards have any
   deferred parents that require resolving, we go directly to the next
   step with very little cost.

During review, Claude pointed out that my change actually fixes a
potential problem.  The current code resolves the deferred parent of an
entry in the same loop where it potentially calls "full_name" for that
entry (to create the special Ada entries).  "full_name" walks up the
parent chain, and thus requires all grand-parents to be resolved.
Depending on the order of DIEs in the file, it might not be true.
Having the "resolve deferred parents" step run completely before the
name canonicalization step avoids this.

I built a gdb.dwarf2 test case around the DWARF structure it proposed to
hit the bug.  It is perhaps not something we expect from real-world
producers, but it's also not completely unthinkable.  It hits this
assert when the patch is not applied:

    gdb/dwarf2/cooked-index-entry.h:217: internal-error: get_parent: Assertion `(flags & IS_PARENT_DEFERRED) == 0' failed.

... and passes with it.

Change-Id: I1cf5e181ecd2d7399a1e885fe686e7e76a5419cb
Approved-By: Andrew Burgess <aburgess@redhat.com>
---
 gdb/dwarf2/cooked-index-entry.c               |  2 +-
 gdb/dwarf2/cooked-index-shard.c               | 30 +++++--
 gdb/dwarf2/cooked-index-shard.h               | 22 +++--
 gdb/dwarf2/cooked-index.c                     | 80 +++++++++++++-----
 gdb/dwarf2/cooked-index.h                     | 36 ++++++---
 .../ada-forward-spec-deferred-grandparent.exp | 81 +++++++++++++++++++
 6 files changed, 210 insertions(+), 41 deletions(-)
 create mode 100644 gdb/testsuite/gdb.dwarf2/ada-forward-spec-deferred-grandparent.exp

diff --git a/gdb/dwarf2/cooked-index-entry.c b/gdb/dwarf2/cooked-index-entry.c
index 21e25e946158..8c324f77904b 100644
--- a/gdb/dwarf2/cooked-index-entry.c
+++ b/gdb/dwarf2/cooked-index-entry.c
@@ -194,7 +194,7 @@ cooked_index_entry::full_name (struct obstack *storage,
 	 of writing), then we need to compute the linkage name here.
 	 However for traditional GNAT, the linkage name will be in
 	 'name'.  Detect this by looking for "__"; see also
-	 cooked_index_shard::finalize.  */
+	 cooked_index_shard::canonicalize_names.  */
       if ((name_flags & FOR_ADA_LINKAGE_NAME) != 0)
 	{
 	  if (strstr (name, "__") != nullptr)
diff --git a/gdb/dwarf2/cooked-index-shard.c b/gdb/dwarf2/cooked-index-shard.c
index 91dc9ab89455..51b2eacd46d8 100644
--- a/gdb/dwarf2/cooked-index-shard.c
+++ b/gdb/dwarf2/cooked-index-shard.c
@@ -82,6 +82,9 @@ cooked_index_shard::add (sect_offset die_offset, enum dwarf_tag tag,
 				       parent_entry, per_cu);
   m_entries.push_back (result);
 
+  if ((flags & IS_PARENT_DEFERRED) != 0)
+    m_have_deferred_parents = true;
+
   /* An explicitly-tagged main program should always override the
      implicit "main" discovery.  */
   if ((flags & IS_MAIN) != 0)
@@ -190,7 +193,24 @@ struct cooked_index_entry_name_ptr_eq
 /* See cooked-index-shard.h.  */
 
 void
-cooked_index_shard::finalize (const parent_map_map *parent_maps)
+cooked_index_shard::resolve_deferred_parents
+	(const parent_map_map *parent_maps)
+{
+  gdb_assert (m_have_deferred_parents);
+
+  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);
+      }
+}
+
+/* See cooked-index-shard.h.  */
+
+void
+cooked_index_shard::canonicalize_names ()
 {
   gdb::unordered_set<const cooked_index_entry *,
 		     cooked_index_entry_name_ptr_hash,
@@ -216,12 +236,8 @@ cooked_index_shard::finalize (const parent_map_map *parent_maps)
 
   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);
-	}
+      /* Deferred parents should not reach this point.  */
+      gdb_assert ((entry->flags & IS_PARENT_DEFERRED) == 0);
 
       /* Note that this code must be kept in sync with
 	 cooked_index::get_main -- if canonicalization is required
diff --git a/gdb/dwarf2/cooked-index-shard.h b/gdb/dwarf2/cooked-index-shard.h
index 84c37958c833..9b9ffa7a76e3 100644
--- a/gdb/dwarf2/cooked-index-shard.h
+++ b/gdb/dwarf2/cooked-index-shard.h
@@ -118,22 +118,34 @@ class cooked_index_shard
        (cooked_index_entry *entry, htab_t gnat_entries,
 	std::vector<cooked_index_entry *> &new_entries);
 
-  /* 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 and fixes up all missing parent links.
-     This may be invoked in a worker thread.  */
-  void finalize (const parent_map_map *parent_maps);
+  /* Use PARENT_MAPS to resolve the deferred parent links of entries in this
+     shard.  */
+  void resolve_deferred_parents (const parent_map_map *parent_maps);
+
+  /* Compute the canonical name for the entries in this shard.
+
+     Due to how Ada name lookups work, this function may also create new index
+     entries with full names.  */
+  void canonicalize_names ();
 
   /* Storage for the entries.  */
   auto_obstack m_storage;
+
   /* List of all entries.  */
   std::vector<cooked_index_entry *> m_entries;
+
   /* If we found an entry with 'is_main' set, store it here.  */
   cooked_index_entry *m_main = nullptr;
+
   /* The addrmap.  This maps address ranges to dwarf2_per_cu objects.  */
   addrmap_fixed *m_addrmap = nullptr;
+
   /* Storage for canonical names.  */
   gdb::string_set m_names;
+
+  /* True if at least one entry in this shard has a parent link that requires
+     deferred resolution.  */
+  bool m_have_deferred_parents = false;
 };
 
 using cooked_index_shard_up = std::unique_ptr<cooked_index_shard>;
diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c
index 167e39ffc89a..bf1ea5223671 100644
--- a/gdb/dwarf2/cooked-index.c
+++ b/gdb/dwarf2/cooked-index.c
@@ -74,31 +74,73 @@ cooked_index::set_contents ()
 
   m_state->set (cooked_state::MAIN_AVAILABLE);
 
-  /* This is run after finalization is done -- but not before.  If
-     this task were submitted earlier, it would have to wait for
-     finalization.  However, that would take a slot in the global
-     thread pool, and if enough such tasks were submitted at once, it
-     would cause a livelock.  */
-  gdb::task_group finalizers ([this] ()
-  {
-    m_state->set (cooked_state::FINALIZED);
-    m_state->write_to_cache (index_for_writing ());
-    m_state->set (cooked_state::CACHE_DONE);
-  });
+  /* Start the first step of index finalization.  */
+  this->start_resolve_deferred_parents ();
+}
 
-  for (auto &shard : m_shards)
+/* See cooked-index.h.  */
+
+void
+cooked_index::start_resolve_deferred_parents ()
+{
+  gdb::task_group group ([this] ()
     {
-      auto this_shard = shard.get ();
-      const parent_map_map *parent_maps = m_state->get_parent_map_map ();
-      finalizers.add_task ([this, this_shard, parent_maps] ()
+      this->start_canonicalize_names ();
+    });
+
+  /* Arrange to call resolve_deferred_parents on each shard that has at least
+     one deferred parent link.  */
+  for (const cooked_index_shard_up &shard : m_shards)
+    {
+      if (!shard->m_have_deferred_parents)
+	continue;
+
+      group.add_task ([this, this_shard = shard.get ()] ()
 	{
-	  scoped_time_it time_it ("DWARF finalize worker",
+	  scoped_time_it time_it ("DWARF resolve deferred parents worker",
 				  m_state->m_per_command_time);
-	  this_shard->finalize (parent_maps);
+
+	  this_shard->resolve_deferred_parents (m_state->get_parent_map_map ());
 	});
     }
 
-  finalizers.start ();
+  group.start ();
+}
+
+/* See cooked-index.h.  */
+
+void
+cooked_index::start_canonicalize_names ()
+{
+  gdb::task_group group ([this] ()
+    {
+      /* The index is considered finalized (fully usable) at this point.  */
+      m_state->set (cooked_state::FINALIZED);
+      this->write_to_cache ();
+    });
+
+  /* Arrange to call canonicalize_names on each shard.  */
+  for (const cooked_index_shard_up &shard : m_shards)
+    {
+      group.add_task ([this, this_shard = shard.get ()] ()
+	{
+	  scoped_time_it time_it ("DWARF canonicalize names worker",
+				  m_state->m_per_command_time);
+
+	  this_shard->canonicalize_names ();
+	});
+    }
+
+  group.start ();
+}
+
+/* See cooked-index.h.  */
+
+void
+cooked_index::write_to_cache ()
+{
+  m_state->write_to_cache (index_for_writing ());
+  m_state->set (cooked_state::CACHE_DONE);
 }
 
 cooked_index::~cooked_index ()
@@ -190,7 +232,7 @@ cooked_index::get_main () const
 	  if ((entry->flags & IS_MAIN) != 0)
 	    {
 	      /* This should be kept in sync with
-		 cooked_index_shard::finalize.  Note that there, C
+		 cooked_index_shard::canonicalize_names.  Note that there, C
 		 requires canonicalization -- but that is only for
 		 types, 'main' doesn't count.  Similarly, C++ requires
 		 canonicalization, but again "main" is an
diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index 2e177cb62dd2..758e399706ba 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -70,14 +70,17 @@
    .                                        |
    .   if main thread calls...              v
    .   compute_main_name         cooked_index::set_contents
-   .          |                           / | \
-   .          v                          /  |  \
-   .   wait (MAIN_AVAILABLE)          finalization
-   .          |                          \  |  /
-   .          v                           \ | /
-   .        done                      state = FINALIZED
-   .                                        |
-   .                                        v
+   .          |                              |
+   .          v                              v
+   .   wait (MAIN_AVAILABLE)      resolve deferred parents
+   .          |                              |
+   .          v                              v
+   .        done                     canonicalize names
+   .                                         |
+   .                                         v
+   .                                 state = FINALIZED
+   .                                         |
+   .                                         v
    .                              maybe write to index cache
    .                                  state = CACHE_DONE
    .                                 ~cooked_index_worker
@@ -91,7 +94,10 @@
    .          |
    .          v
    .    use the index
-*/
+
+   The steps between set_contents and FINALIZED can be thought of as the
+   "index finalization", where we fix up a number of things that couldn't
+   be done during the parallel scan.  */
 
 class cooked_index : public dwarf_scanner_base
 {
@@ -170,6 +176,18 @@ class cooked_index : public dwarf_scanner_base
   { wait (cooked_state::CACHE_DONE); }
 
 private:
+  /* Start the "resolve deferred parents" step of index finalization.  */
+  void start_resolve_deferred_parents ();
+
+  /* Start the "canonicalize names" step of index finalization.
+
+     This step must run after "resolve deferred parents", because it depends on
+     the parents being set.  */
+  void start_canonicalize_names ();
+
+  /* Execute the "write to cache" step at the end of index
+     finalization.  */
+  void write_to_cache ();
 
   /* The vector of cooked_index objects.  This is stored because the
      entries are stored on the obstacks in those objects.  */
diff --git a/gdb/testsuite/gdb.dwarf2/ada-forward-spec-deferred-grandparent.exp b/gdb/testsuite/gdb.dwarf2/ada-forward-spec-deferred-grandparent.exp
new file mode 100644
index 000000000000..24a55e5fbae3
--- /dev/null
+++ b/gdb/testsuite/gdb.dwarf2/ada-forward-spec-deferred-grandparent.exp
@@ -0,0 +1,81 @@
+# Copyright 2026 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# This test reproduces a case that caused a crash in the DWARF indexer, where
+# we were trying to compute the full name of an index entry whose parent's
+# parent link was not yet resolved.
+
+load_lib dwarf.exp
+
+# This test can only be run on targets which support DWARF-2 and use gas.
+require dwarf2_support
+
+standard_testfile main.c -debug.S
+
+set asm_file [standard_output_file $srcfile2]
+Dwarf::assemble $asm_file {
+    declare_labels v_decl pkg_decl myint
+
+    cu {} {
+	DW_TAG_compile_unit {
+	    DW_AT_language @DW_LANG_Ada95
+	} {
+	    # The definition of variable "v".  Its DW_AT_specification
+	    # points forward, so its parent link is deferred.
+	    #
+	    # The crash would happen when the index attempted to create a
+	    # "full name" entry for this variable.
+	    DW_TAG_variable {
+		DW_AT_specification %$v_decl
+		DW_AT_location {
+		    DW_OP_const1u 23
+		    DW_OP_stack_value
+		} SPECIAL_expr
+	    }
+
+	    # The definition of package "pkg".  Its DW_AT_specification
+	    # points forward, so its parent link is also deferred.
+	    DW_TAG_module {
+		DW_AT_specification %$pkg_decl
+	    } {
+		v_decl: DW_TAG_variable {
+		    DW_AT_name v
+		    DW_AT_type :$myint
+		    DW_AT_declaration 1 DW_FORM_flag_present
+		}
+	    }
+
+	    pkg_decl: DW_TAG_module {
+		DW_AT_name pkg
+		DW_AT_declaration 1 DW_FORM_flag_present
+	    } {}
+
+	    myint: DW_TAG_base_type {
+		DW_AT_byte_size 4 DW_FORM_sdata
+		DW_AT_encoding  @DW_ATE_signed
+		DW_AT_name      myint
+	    }
+	}
+    }
+}
+
+if {[build_executable "failed to build executable" ${testfile} \
+	 [list $srcfile $asm_file] {nodebug}]} {
+    return
+}
+
+clean_restart $testfile
+
+gdb_test "with language ada -- print pkg.v" " = 23"
-- 
2.55.0