diff mbox

[01/14] Fix latent bug in dwarf2_find_containing_comp_unit

Message ID 87o8tu86ci.fsf@tromey.com
State New
Headers show

Commit Message

Tom Tromey Feb. 20, 2020, 12:12 a.m. UTC
Simon> By refactoring the code a bit, we could maybe factor out the
Simon> meat of this function into one that operates on an std::vector<dwarf2_per_cu_data> instead
Simon> of on a dwarf2_per_objfile.  It should then be feasible to create an std::vector with
Simon> dwarf2_per_cu_data elements out of thin air to unit-test the function, including edge
Simon> cases like this.

Oops, I meant to attach the patch in that last email.

Let me know what you think.

Tom

commit 5d02b8ad013451b03e004ef1e71c4636b43252c2
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Feb 15 09:08: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-19  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.

Comments

Simon Marchi Feb. 20, 2020, 3:44 p.m. UTC | #1
On 2020-02-19 7:12 p.m., Tom Tromey wrote:
> Simon> By refactoring the code a bit, we could maybe factor out the
> Simon> meat of this function into one that operates on an std::vector<dwarf2_per_cu_data> instead
> Simon> of on a dwarf2_per_objfile.  It should then be feasible to create an std::vector with
> Simon> dwarf2_per_cu_data elements out of thin air to unit-test the function, including edge
> Simon> cases like this.
> 
> Oops, I meant to attach the patch in that last email.
> 
> Let me know what you think.
> 
> Tom

Thanks, that LGTM.  If you want to use std::binary_search, that would be fine
as well.

Simon
Tom Tromey Feb. 20, 2020, 4:49 p.m. UTC | #2
>>>>> "Simon" == Simon Marchi <simark@simark.ca> writes:

Simon> Thanks, that LGTM.  If you want to use std::binary_search, that would be fine
Simon> as well.

I tried this but it wasn't notably simpler and it meant changes to the
error handling, so I dropped it.

Tom
diff mbox

Patch

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index b4a586c333a..b07c9156e28 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,11 @@ 
+2020-02-19  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-19  Simon Marchi  <simon.marchi@efficios.com>
 
 	* dwarf2/read.c (allocate_signatured_type_table,
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index 4d767a59af7..f998fe6b8d0 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
 }