[binutils-gdb] Introduce class parent_map for DIE range map

[binutils-gdb] Introduce class parent_map for DIE range map

[Tom Tromey]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=0b398cf8f30af07977763ffdf0c26547e46f8c09

commit 0b398cf8f30af07977763ffdf0c26547e46f8c09
Author: Tom Tromey <tom@tromey.com>
Date:   Thu Jan 11 20:07:06 2024 -0700

    Introduce class parent_map for DIE range map
    
    This changes the DIE range map from a raw addrmap to a custom class.
    A new type is used to represent the ranges, in an attempt to gain a
    little type safety as well.
    
    Note that the new code includes a map-of-maps type.  This is not used
    yet, but will be used in the next patch.
    
    Co-Authored-By: Tom de Vries <tdevries@suse.de>

Diff:
---
 gdb/dwarf2/cooked-index.h |   7 +--
 gdb/dwarf2/parent-map.h   | 132 ++++++++++++++++++++++++++++++++++++++++++++++
 gdb/dwarf2/read.c         |  46 +++++++---------
 3 files changed, 154 insertions(+), 31 deletions(-)

diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index 7ff609b9d73..6400750b587 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -35,6 +35,7 @@
 #include "dwarf2/read.h"
 #include "dwarf2/tag.h"
 #include "dwarf2/abbrev-cache.h"
+#include "dwarf2/parent-map.h"
 #include "gdbsupport/range-chain.h"
 #include "gdbsupport/task-group.h"
 #include "complaints.h"
@@ -72,7 +73,7 @@ DEF_ENUM_FLAGS_TYPE (enum cooked_index_flag_enum, cooked_index_flag);
 
 union cooked_index_entry_ref
 {
-  cooked_index_entry_ref (CORE_ADDR deferred_)
+  cooked_index_entry_ref (parent_map::addr_type deferred_)
   {
     deferred = deferred_;
   }
@@ -83,7 +84,7 @@ union cooked_index_entry_ref
   }
 
   const cooked_index_entry *resolved;
-  CORE_ADDR deferred;
+  parent_map::addr_type deferred;
 };
 
 /* Return a string representation of FLAGS.  */
@@ -221,7 +222,7 @@ struct cooked_index_entry : public allocate_on_obstack<cooked_index_entry>
   }
 
   /* Return deferred parent entry.  */
-  CORE_ADDR get_deferred_parent () const
+  parent_map::addr_type get_deferred_parent () const
   {
     gdb_assert ((flags & IS_PARENT_DEFERRED) != 0);
     return m_parent_entry.deferred;
diff --git a/gdb/dwarf2/parent-map.h b/gdb/dwarf2/parent-map.h
new file mode 100644
index 00000000000..f070d505356
--- /dev/null
+++ b/gdb/dwarf2/parent-map.h
@@ -0,0 +1,132 @@
+/* DIE indexing 
+
+   Copyright (C) 2024 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   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/>.  */
+
+#ifndef GDB_DWARF2_PARENT_MAP_H
+#define GDB_DWARF2_PARENT_MAP_H
+
+#include <algorithm>
+
+class cooked_index_entry;
+
+/* A class that handles mapping from a DIE range to a parent
+   entry.
+
+   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.  */
+class parent_map
+{
+public:
+
+  parent_map () = default;
+  ~parent_map () = default;
+
+  /* Move only.  */
+  DISABLE_COPY_AND_ASSIGN (parent_map);
+  parent_map (parent_map &&) = default;
+  parent_map &operator= (parent_map &&) = default;
+
+  /* A reasonably opaque type that is used here to combine a section
+     offset and the 'dwz' flag into a single value.  */
+  enum addr_type : CORE_ADDR { };
+
+  /* Turn a section offset into a value that can be used in a parent
+     map.  */
+  static addr_type form_addr (sect_offset offset, bool is_dwz)
+  {
+    CORE_ADDR value = to_underlying (offset);
+    if (is_dwz)
+      value |= ((CORE_ADDR) 1) << (8 * sizeof (CORE_ADDR) - 1);
+    return addr_type (value);
+  }
+
+  /* Add a new entry to this map.  DIEs from START to END, inclusive,
+     are mapped to PARENT.  */
+  void add_entry (addr_type start, addr_type end,
+		  const cooked_index_entry *parent)
+  {
+    gdb_assert (parent != nullptr);
+    m_map.set_empty (start, end, (void *) parent);
+  }
+
+  /* Look up an entry in this map.  */
+  const cooked_index_entry *find (addr_type search) const
+  {
+    return static_cast<const cooked_index_entry *> (m_map.find (search));
+  }
+
+  /* Return a fixed addrmap that is equivalent to this map.  */
+  addrmap_fixed *to_fixed (struct obstack *obstack) const
+  {
+    return new (obstack) addrmap_fixed (obstack, &m_map);
+  }
+
+private:
+
+  /* An addrmap that maps from section offsets to cooked_index_entry *.  */
+  addrmap_mutable m_map;
+};
+
+/* Keep a collection of parent_map objects, and allow for lookups
+   across all of them.  */
+class parent_map_map
+{
+public:
+
+  parent_map_map () = default;
+  ~parent_map_map () = default;
+
+  DISABLE_COPY_AND_ASSIGN (parent_map_map);
+
+  /* Add a parent_map to this map.  */
+  void add_map (const parent_map &map)
+  {
+    m_maps.push_back (map.to_fixed (&m_storage));
+  }
+
+  /* Look up an entry in this map.  */
+  const cooked_index_entry *find (parent_map::addr_type search) const
+  {
+    for (const auto &iter : m_maps)
+      {
+	const cooked_index_entry *result
+	  = static_cast<const cooked_index_entry *> (iter->find (search));
+	if (result != nullptr)
+	  return result;
+      }
+    return nullptr;
+  }
+
+private:
+
+  /* Storage for the convert maps.  */
+  auto_obstack m_storage;
+
+  /* While conceptually this class is a combination of parent_maps, in
+     practice it is just a number of fixed maps.  This is important
+     because we want to allow concurrent lookups, but a mutable
+     addrmap is based on a splay-tree, which is not thread-safe, even
+     for nominally read-only lookups.  */
+  std::vector<addrmap_fixed *> m_maps;
+};
+
+#endif /* GDB_DWARF2_PARENT_MAP_H */
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index b7e04a1ebf3..9de261252c0 100644
--- a/gdb/dwarf2/read.c
+++ b/gdb/dwarf2/read.c
@@ -94,6 +94,7 @@
 #include "split-name.h"
 #include "gdbsupport/thread-pool.h"
 #include "run-on-main-thread.h"
+#include "dwarf2/parent-map.h"
 
 /* When == 1, print basic high level tracing messages.
    When > 1, be more verbose.
@@ -4473,16 +4474,6 @@ public:
 
 private:
 
-  /* A helper function to turn a section offset into an address that
-     can be used in an addrmap.  */
-  CORE_ADDR form_addr (sect_offset offset, bool is_dwz)
-  {
-    CORE_ADDR value = to_underlying (offset);
-    if (is_dwz)
-      value |= ((CORE_ADDR) 1) << (8 * sizeof (CORE_ADDR) - 1);
-    return value;
-  }
-
   /* A helper function to scan the PC bounds of READER and record them
      in the storage's addrmap.  */
   void check_bounds (cutu_reader *reader);
@@ -4520,7 +4511,7 @@ private:
 				   cooked_index_flag *flags,
 				   sect_offset *sibling_offset,
 				   const cooked_index_entry **parent_entry,
-				   CORE_ADDR *maybe_defer,
+				   parent_map::addr_type *maybe_defer,
 				   bool *is_enum_class,
 				   bool for_specification);
 
@@ -4548,10 +4539,9 @@ private:
   /* The language that we're assuming when reading.  */
   enum language m_language;
 
-  /* An addrmap that maps from section offsets (see the form_addr
-     method) to newly-created entries.  See m_deferred_entries to
-     understand this.  */
-  addrmap_mutable m_die_range_map;
+  /* 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
@@ -16095,7 +16085,7 @@ cooked_indexer::scan_attributes (dwarf2_per_cu_data *scanning_per_cu,
 				 cooked_index_flag *flags,
 				 sect_offset *sibling_offset,
 				 const cooked_index_entry **parent_entry,
-				 CORE_ADDR *maybe_defer,
+				 parent_map::addr_type *maybe_defer,
 				 bool *is_enum_class,
 				 bool for_specification)
 {
@@ -16268,15 +16258,13 @@ cooked_indexer::scan_attributes (dwarf2_per_cu_data *scanning_per_cu,
 
 	  if (*parent_entry == nullptr)
 	    {
-	      CORE_ADDR addr = form_addr (origin_offset, origin_is_dwz);
+	      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)
 		*maybe_defer = addr;
 	      else
-		{
-		  void *obj = m_die_range_map.find (addr);
-		  *parent_entry = static_cast <cooked_index_entry *> (obj);
-		}
+		*parent_entry = m_die_range_map.find (addr);
 	    }
 
 	  unsigned int bytes_read;
@@ -16401,11 +16389,13 @@ cooked_indexer::recurse (cutu_reader *reader,
     {
       /* Both start and end are inclusive, so use both "+ 1" and "- 1" to
 	 limit the range to the children of parent_entry.  */
-      CORE_ADDR start = form_addr (parent_entry->die_offset + 1,
-				   reader->cu->per_cu->is_dwz);
-      CORE_ADDR end = form_addr (sect_offset (info_ptr - 1 - reader->buffer),
+      parent_map::addr_type start
+	= parent_map::form_addr (parent_entry->die_offset + 1,
+				 reader->cu->per_cu->is_dwz);
+      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.set_empty (start, end, (void *) parent_entry);
+      m_die_range_map.add_entry (start, end, parent_entry);
     }
 
   return info_ptr;
@@ -16447,7 +16437,7 @@ cooked_indexer::index_dies (cutu_reader *reader,
 
       const char *name = nullptr;
       const char *linkage_name = nullptr;
-      CORE_ADDR defer = 0;
+      parent_map::addr_type defer {};
       cooked_index_flag flags = IS_STATIC;
       sect_offset sibling {};
       const cooked_index_entry *this_parent_entry = parent_entry;
@@ -16591,8 +16581,8 @@ cooked_indexer::make_index (cutu_reader *reader)
 
   for (const auto &entry : m_deferred_entries)
     {
-      void *obj = m_die_range_map.find (entry->get_deferred_parent ());
-      cooked_index_entry *parent = static_cast<cooked_index_entry *> (obj);
+      const cooked_index_entry *parent
+	= m_die_range_map.find (entry->get_deferred_parent ());
       entry->resolve_parent (parent);
     }
 }