gdb/dwarf: sort dwarf2_per_bfd::all_units by (section, offset)

This patch started as a fix for PR 29518 ("GDB doesn't handle
DW_FORM_ref_addr DIE references correctly with .debug_types sections")
[1], but the scope has expanded a bit to fix the problem more generally,
after I spotted a few issues related to the order of all_units.  The
first version of this patch is here [2].

PR 29518 shows that dwarf2_find_containing_comp_unit can erroneously
find a type unit.  The obvious problem is that the
dwarf2_find_containing_comp_unit function searches the whole all_units
vector (containing both comp and type units), when really it should just
search the compilation units.  A simple solution would be to make it
search the all_comp_units view (which is removed in a patch earlier in
this series).

I then realized that in DWARF 5, since type units are in .debug_info
(versus .debug_types in DWARF 4), type units can be interleaved with
comp type in the all_units vector.  That would make the all_comp_units
and all_type_units views erroneous, and dwarf2_find_containing_comp_unit
could still return something wrong.  In v1, I added a sort in
finalize_all_units to make sure all_units is in the order that
dwarf2_find_containing_comp_unit expects:

 - comp units from the main file
 - type units from the main file
 - comp units from the dwz file
 - type units from the dwz file (not actually supported, see PR 30838)

Another problem I spotted is that the .gdb_index reader creates units in
this order:

 - comp units from .gdb_index from main file
 - comp units from .gdb_index from dwz file
 - type units from .gdb_index from main file

This isn't the same order as above, so it would need the same sort step.

Finally, I'm not exactly sure if and when it happens, but it looks like
lookup_signatured_type can be called at a later time (after the initial
scan and creation of dwarf2_per_cu object creation), when expanding a
symtab.  And that could lead to the creation of a new type unit (see
function add_type_unit), which would place the new type unit at the end
of the all_units vector, possibly screwing up the previous order.

To handle all this in a nice and generic way, Tom Tromey proposed to
change the all_units order, so that units are sorted by section, then
section offset.  This is what this patch implements.  The sorting is
done in finalize_all_units.

This works well, because when looking up a unit by section offset, the
caller knows which section the unit is in.  Passing down a (section,
section offset) tuple makes it clear and unambiguous what unit the
caller is referring to.  It should help eliminate some bugs where the
callee used the section offset in the wrong section.  Passing down the
section along with the section offset replaces the "is_dwz" flag passed
to dwarf2_find_containing_comp_unit and a bunch of other functions in a
more general way.

dwarf2_find_containing_comp_unit can now legitimately find and return
type units even though it should be needed (type units are typically
referred to by signature).  But I don't think there is harm for this
function to be more generic than needed.  I therefore I renamed it to
dwarf2_find_containing_unit.

The sort criterion for "section" can be anything, as long as we use the
same for sorting and searching.  In this patch, I use the pointer to
dwarf2_section_info, because it's easy.  The downside is that the actual
order depends on what the memory allocator decided to return, so could
change from run to run, or machine to machine.  Later, I might change it
so that sections are ordered based on their properties, making the order
stable across the board.  This logic is encapsulated in the
all_units_less_than function, so it's easy to change.

The .debug_names reader can no longer rely on the order of the all_units
vector for its checks, since all_units won't be the same order as found
in the .debug_names lists.  In fact, even before, it wasn't: this check
assumed that .debug_info had all CUs before TUs, and that the index
listed them in the exact same order.  When I build a file with gcc and
"-gdwarf-5 -fdebug-types-section", type units appear first in
.debug_info.  This caused GDB to reject a .debug_names index that is had
produced:

    $ GDB="./gdb -nx -q --data-directory=data-directory" /home/smarchi/src/binutils-gdb/gdb/contrib/gdb-add-index.sh -dwarf-5 hello.so
    $ ./gdb -nx -q --data-directory=data-directory hello.so
    Reading symbols from hello.so...

    ⚠️  warning: Section .debug_names has incorrect entry in CU table, ignoring .debug_names.

To make it work, add a new dwarf2_find_unit function that allows looking
up a unit by start address (unlike dwarf2_find_containing_unit, which
can find by any containing address), and make the .debug_names reader
use it.  It might make the load time of .debug_names a bit longer (the
build and check step is now going to be O(n*log(n)) instead of O(n)
where n is the number of units, or something like that), but I think
it's important to be correct here.

This patch adds a test
(gdb.dwarf2/dw-form-ref-addr-with-type-units.exp), which tries to
replicate the problem as shown by PR 29518.

gdb.base/varval.exp needs a small change, because an error message
changes (for the better, I think)

gdb.dwarf2/debug-names-non-ascending-cu.exp now fails, because GDB no
longer rejects a .debug_names index which lists CUs in a different order
than .debug_info.  Given the change I did to the .debug_names reader,
explained above, I don't think this is a problem anymore (GDB can accept
an index like that).  I also don't think that DWARF 5 mandates that CUs
are in ascending order.  Delete this test.

[1] https://sourceware.org/bugzilla/show_bug.cgi?id=29518
[2] https://inbox.sourceware.org/gdb-patches/20250218193443.118139-1-simon.marchi@efficios.com/

Change-Id: I45f982d824d3842ac1eb73f8cce721a0a24b5faa
Approved-By: Tom Tromey <tom@tromey.com>

3 files changed, 110 insertions, 82 deletions

diff --git a/gdb/testsuite/gdb.dwarf2/debug-names-non-ascending-cu.exp b/gdb/testsuite/gdb.dwarf2/debug-names-non-ascending-cu.exp
deleted file mode 100644
index d86b5c4..0000000
--- a/gdb/testsuite/gdb.dwarf2/debug-names-non-ascending-cu.exp
+++ /dev/null
@@ -1,81 +0,0 @@
-# Copyright 2022-2025 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/>.
-
-load_lib dwarf.exp
-
-# This test can only be run on targets which support DWARF-2 and use gas.
-require dwarf2_support
-
-standard_testfile _start.c debug-names.S
-
-set func_info_vars \
-    [get_func_info _start [list debug additional_flags=-nostartfiles]]
-
-# Create the DWARF.
-set asm_file [standard_output_file $srcfile2]
-Dwarf::assemble {
-    filename $asm_file
-    add_dummy_cus 0
-} {
-    global func_info_vars
-    foreach var $func_info_vars {
-	global $var
-    }
-
-    cu { label cu_label } {
-	compile_unit {{language @DW_LANG_C}} {
-	    subprogram {
-		{DW_AT_name _start}
-		{DW_AT_low_pc $_start_start DW_FORM_addr}
-		{DW_AT_high_pc $_start_end DW_FORM_addr}
-	    }
-	}
-    }
-
-    cu { label cu_label_2 } {
-	compile_unit {{language @DW_LANG_C}} {
-	    base_type {
-		{name int}
-		{byte_size 4 sdata}
-		{encoding @DW_ATE_signed}
-	    }
-	}
-    }
-
-    debug_names {} {
-	cu cu_label_2
-	cu cu_label
-	name _start subprogram cu_label 0xEDDB6232
-	name int base_type cu_label 0xB888030
-    }
-}
-
-if [prepare_for_testing "failed to prepare" $testfile "${asm_file} ${srcfile}" \
-	[list additional_flags=-nostartfiles]] {
-    return -1
-}
-
-# Check for warning.
-set re \
-    [list \
-	 "warning:" \
-	 "Section .debug_names has incorrect entry in CU table," \
-	 "ignoring .debug_names."]
-set re [join $re]
-gdb_assert {[regexp $re $gdb_file_cmd_msg]} "warning"
-
-# Verify that .debug_names section is ignored.
-set index [have_index $binfile]
-gdb_assert { [string equal $index ""] } ".debug_names not used"
diff --git a/gdb/testsuite/gdb.dwarf2/dw-form-ref-addr-with-type-units.exp b/gdb/testsuite/gdb.dwarf2/dw-form-ref-addr-with-type-units.exp
new file mode 100644
index 0000000..6253629
--- /dev/null
+++ b/gdb/testsuite/gdb.dwarf2/dw-form-ref-addr-with-type-units.exp
@@ -0,0 +1,109 @@
+# Copyright 2025 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 is a reproducer for PR 29518:
+#
+#   https://sourceware.org/bugzilla/show_bug.cgi?id=29518
+#
+# The root cause for the problem was that function
+# dwarf2_find_containing_comp_unit was searching the whole "all_units" vector,
+# containing both compile units and type units, causing it to sometimes
+# erroneously return a type unit.  It should have been restricted to searching
+# compile units.
+#
+# To get dwarf2_find_containing_comp_unit to be called and reproduce the
+# original bug, we need a value with form DW_FORM_ref_addr pointing to a
+# different compile unit.  This is produced by `%$int_type` below.
+
+load_lib dwarf.exp
+require dwarf2_support
+standard_testfile main.c .S
+
+set asm_file [standard_output_file $srcfile2]
+
+Dwarf::assemble $asm_file {
+    global srcfile
+    declare_labels int_type
+
+    # The source CU.
+    cu {version 4} {
+	compile_unit {
+	} {
+	    subprogram {
+		{MACRO_AT_func {main}}
+		{type %$int_type}
+	    }
+	}
+    }
+
+    # Create a bunch of empty / dummy CUs, to make the offset of int_type a bit
+    # higher.
+    for {set i 1} {$i < 10} {incr i} {
+	cu {version 4} {
+	    compile_unit {} {}
+	}
+    }
+
+    # The target CU.
+    cu {version 4} {
+	compile_unit {
+	} {
+	    int_type: DW_TAG_base_type {
+		{DW_AT_byte_size 4 DW_FORM_sdata}
+		{DW_AT_encoding  @DW_ATE_signed}
+		{DW_AT_name      int}
+	    }
+	}
+    }
+
+    # Create many TUs.
+    #
+    # We need enough type units in the "all_units" vector in order to steer the
+    # binary search in dwarf2_find_containing_comp_unit towards the type units
+    # region of the array.
+    for {set i 1} {$i < 20} {incr i} {
+	tu {version 4} $i the_type_i {
+		type_unit {} {
+		declare_labels dummy_int_type
+
+		the_type_i: structure_type {
+			{name s}
+			{byte_size 4 sdata}
+		} {
+			member {
+			{name i}
+			{type :$dummy_int_type}
+			}
+		}
+
+		dummy_int_type: base_type {
+			{name int}
+			{encoding @DW_ATE_signed}
+			{byte_size 4 sdata}
+		}
+	    }
+	}
+    }
+}
+
+if { [prepare_for_testing "failed to prepare" ${testfile} \
+	  [list $srcfile $asm_file] {nodebug}] } {
+    return -1
+}
+
+# Without the corresponding fix, we get an internal error:
+#
+#   gdb/dwarf2/read.c:3940: internal-error: load_full_comp_unit: Assertion `! this_cu->is_debug_types' failed.
+gdb_test "p main" " = {int \\(void\\)} $hex <main>"
diff --git a/gdb/testsuite/gdb.dwarf2/varval.exp b/gdb/testsuite/gdb.dwarf2/varval.exp
index 0693f43..6846ecb 100644
--- a/gdb/testsuite/gdb.dwarf2/varval.exp
+++ b/gdb/testsuite/gdb.dwarf2/varval.exp
@@ -348,6 +348,6 @@ if ![runto_main] {
 }
 gdb_test "print badval" "value has been optimized out"
 gdb_test "print bad_die_val1" \
-         "invalid dwarf2 offset 0xabcdef11"
+	 {DWARF Error: could not find unit containing offset 0xabcdef11 \[in module .*/varval\]}
 gdb_test "print bad_die_val2" \
          "Bad DW_OP_GNU_variable_value DIE\\."