[binutils-gdb] Fix latent bug in dwarf2_find_containing_comp_unit

[binutils-gdb] Fix latent bug in dwarf2_find_containing_comp_unit

[Tom Tromey]

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

commit 22b6cd70430d6bdaa3ae6c01414de8fd1f15a556
Author: Tom Tromey <tom@tromey.com>
Date:   Thu Feb 20 18:22:09 2020 -0700

    Fix latent bug in dwarf2_find_containing_comp_unit
    
    dwarf2_find_containing_comp_unit has this in its binary search:
    
          if (mid_cu->is_dwz > offset_in_dwz
    	  || (mid_cu->is_dwz == offset_in_dwz
    	      && mid_cu->sect_off + mid_cu->length >= sect_off))
    	high = mid;
    
    The intent here is to determine whether SECT_OFF appears in or before
    MID_CU.
    
    I believe this has an off-by-one error, and that the check should use
    ">" rather than ">=".  If the two side are equal, then SECT_OFF
    actually appears at the start of the next CU.
    
    I've had this patch kicking around for ages but I forget how I found
    the problem.
    
    gdb/ChangeLog
    2020-02-20  Tom Tromey  <tom@tromey.com>
    
    	* dwarf2/read.c (dwarf2_find_containing_comp_unit): Use ">", not
    	">=", in binary search.
    	(dwarf2_find_containing_comp_unit): New overload.
    	(run_test): New self-test.
    	(_initialize_dwarf2_read): Register new test.

Diff:
---
 gdb/ChangeLog     |  8 +++++
 gdb/dwarf2/read.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 91 insertions(+), 11 deletions(-)

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index f8a491b..748788a 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,11 @@
+2020-02-20  Tom Tromey  <tom@tromey.com>
+
+	* dwarf2/read.c (dwarf2_find_containing_comp_unit): Use ">", not
+	">=", in binary search.
+	(dwarf2_find_containing_comp_unit): New overload.
+	(run_test): New self-test.
+	(_initialize_dwarf2_read): Register new test.
+
 2020-02-20  Nelson Chu  <nelson.chu@sifive.com>
 
 	* riscv-tdep.c: Updated since the DECLARE_CSR is changed.
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index 4d767a5..f998fe6 100644
--- a/gdb/dwarf2/read.c
+++ b/gdb/dwarf2/read.c
@@ -24136,34 +24136,53 @@ dwarf2_per_cu_data::addr_type () const
   return addr_type;
 }
 
-/* Locate the .debug_info compilation unit from CU's objfile which contains
-   the DIE at OFFSET.  Raises an error on failure.  */
+/* A helper function for dwarf2_find_containing_comp_unit that returns
+   the index of the result, and that searches a vector.  It will
+   return a result even if the offset in question does not actually
+   occur in any CU.  This is separate so that it can be unit
+   tested.  */
 
-static struct dwarf2_per_cu_data *
-dwarf2_find_containing_comp_unit (sect_offset sect_off,
-				  unsigned int offset_in_dwz,
-				  struct dwarf2_per_objfile *dwarf2_per_objfile)
+static int
+dwarf2_find_containing_comp_unit
+  (sect_offset sect_off,
+   unsigned int offset_in_dwz,
+   const std::vector<dwarf2_per_cu_data *> &all_comp_units)
 {
-  struct dwarf2_per_cu_data *this_cu;
   int low, high;
 
   low = 0;
-  high = dwarf2_per_objfile->all_comp_units.size () - 1;
+  high = all_comp_units.size () - 1;
   while (high > low)
     {
       struct dwarf2_per_cu_data *mid_cu;
       int mid = low + (high - low) / 2;
 
-      mid_cu = dwarf2_per_objfile->all_comp_units[mid];
+      mid_cu = all_comp_units[mid];
       if (mid_cu->is_dwz > offset_in_dwz
 	  || (mid_cu->is_dwz == offset_in_dwz
-	      && mid_cu->sect_off + mid_cu->length >= sect_off))
+	      && mid_cu->sect_off + mid_cu->length > sect_off))
 	high = mid;
       else
 	low = mid + 1;
     }
   gdb_assert (low == high);
-  this_cu = dwarf2_per_objfile->all_comp_units[low];
+  return low;
+}
+
+/* Locate the .debug_info compilation unit from CU's objfile which contains
+   the DIE at OFFSET.  Raises an error on failure.  */
+
+static struct dwarf2_per_cu_data *
+dwarf2_find_containing_comp_unit (sect_offset sect_off,
+				  unsigned int offset_in_dwz,
+				  struct dwarf2_per_objfile *dwarf2_per_objfile)
+{
+  int low
+    = dwarf2_find_containing_comp_unit (sect_off, offset_in_dwz,
+					dwarf2_per_objfile->all_comp_units);
+  struct dwarf2_per_cu_data *this_cu
+    = dwarf2_per_objfile->all_comp_units[low];
+
   if (this_cu->is_dwz != offset_in_dwz || this_cu->sect_off > sect_off)
     {
       if (low == 0 || this_cu->is_dwz != offset_in_dwz)
@@ -24186,6 +24205,57 @@ dwarf2_find_containing_comp_unit (sect_offset sect_off,
     }
 }
 
+#if GDB_SELF_TEST
+
+namespace selftests {
+namespace find_containing_comp_unit {
+
+static void
+run_test ()
+{
+  struct dwarf2_per_cu_data one {};
+  struct dwarf2_per_cu_data two {};
+  struct dwarf2_per_cu_data three {};
+  struct dwarf2_per_cu_data four {};
+
+  one.length = 5;
+  two.sect_off = sect_offset (one.length);
+  two.length = 7;
+
+  three.length = 5;
+  three.is_dwz = 1;
+  four.sect_off = sect_offset (three.length);
+  four.length = 7;
+  four.is_dwz = 1;
+
+  std::vector<dwarf2_per_cu_data *> units;
+  units.push_back (&one);
+  units.push_back (&two);
+  units.push_back (&three);
+  units.push_back (&four);
+
+  int result;
+
+  result = dwarf2_find_containing_comp_unit (sect_offset (0), 0, units);
+  SELF_CHECK (units[result] == &one);
+  result = dwarf2_find_containing_comp_unit (sect_offset (3), 0, units);
+  SELF_CHECK (units[result] == &one);
+  result = dwarf2_find_containing_comp_unit (sect_offset (5), 0, units);
+  SELF_CHECK (units[result] == &two);
+
+  result = dwarf2_find_containing_comp_unit (sect_offset (0), 1, units);
+  SELF_CHECK (units[result] == &three);
+  result = dwarf2_find_containing_comp_unit (sect_offset (3), 1, units);
+  SELF_CHECK (units[result] == &three);
+  result = dwarf2_find_containing_comp_unit (sect_offset (5), 1, units);
+  SELF_CHECK (units[result] == &four);
+}
+
+}
+}
+
+#endif /* GDB_SELF_TEST */
+
 /* Initialize dwarf2_cu CU, owned by PER_CU.  */
 
 dwarf2_cu::dwarf2_cu (struct dwarf2_per_cu_data *per_cu_)
@@ -24690,5 +24760,7 @@ Warning: This option must be enabled before gdb reads the file."),
 #if GDB_SELF_TEST
   selftests::register_test ("dw2_expand_symtabs_matching",
 			    selftests::dw2_expand_symtabs_matching::run_test);
+  selftests::register_test ("dwarf2_find_containing_comp_unit",
+			    selftests::find_containing_comp_unit::run_test);
 #endif
 }