Re: [PATCH] Add a trie to map quickly from address range to compilation unit.

[Alan Modra <amodra@gmail.com>]

On Mon, Mar 28, 2022 at 12:19:52PM +0200, Jan Beulich wrote:
> On 25.03.2022 00:30, Alan Modra via Binutils wrote:
> > On Thu, Mar 24, 2022 at 09:01:38AM +0100, Steinar H. Gunderson wrote:
> >> On Thu, Mar 24, 2022 at 03:52:27PM +1030, Alan Modra wrote:
> >>> Huh, I remember looking at this code a while ago and finding it
> >>> confusing.  I think the code would be clearer, and behave the same on
> >>> normal line number info with the following patch:
> >>
> >> An interesting question is: Do you want to keep searching through
> >> compilation units once you've found a match with a line number?
> >> Should we go straight to “goto done” then?
> > 
> > This would be reverting commit 240d6706c6a2.  In
> > https://sourceware.org/bugzilla/show_bug.cgi?id=15935#c3 I came to the
> > conclusion that the pr15935 testcase had bogus debug info and closed
> > the bug as invalid.  The reporter apparently opened another bug,
> > https://sourceware.org/bugzilla/show_bug.cgi?id=15994 a month later
> > that Nick fixed by making _bfd_dwarf2_find_nearest_line do extra work.
> > Which of course is unnecessary with good debug info, but in many cases
> > we try to make binutils give the best result even with bad input.  I
> > don't know the details beyond that.  It might have been that the
> > compiler producing the bad debug info was one supported by RedHat.
> > 
> > Now we have pr28592 and others complaining that objdump or addr2line
> > have significantly slowed.  Given that pr15935 dates back to 2013, I
> > would presume that people have moved on from whatever broken compiler
> > produced bad line info, and that we should indeed revert commit
> > 240d6706c6a2.  Nick?
> 
> Since I ended up working on that function as well, I did notice another
> potentially relevant aspect: The adjustment done back at the time was
> only for the case of already processed CUs. The subsequent loop reading
> any remaining ones doesn't similarly attempt to find a better match.
> IOW the effects of that change can only have been partial anyway.

Yes, Steinar noticed that too.  Another thing I noticed is that prior
to Nick's original patch looking for the best line range match, we
used to return a function name result for addresses that matched a
DW_TAG_subprogram (and similar) address ramge info.  See the
comp_unit_find_nearest_line change in the following, a patch to revert
commit 240d6706c6a2.

	PR 28592
	PR 15994
	PR 15935
	* dwarf2.c (lookup_address_in_line_info_table): Return bool rather
	than a range.
	(comp_unit_find_nearest_line): Likewise.  Return true if function
	info found without line info.
	(_bfd_dwarf2_find_nearest_line): Revert range handling code.

diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c
index 8b5ac6012e1..4beebcd2835 100644
--- a/bfd/dwarf2.c
+++ b/bfd/dwarf2.c
@@ -2543,13 +2543,12 @@ decode_line_info (struct comp_unit *unit)
   return NULL;
 }
 
-/* If ADDR is within TABLE set the output parameters and return the
-   range of addresses covered by the entry used to fill them out.
-   Otherwise set * FILENAME_PTR to NULL and return 0.
+/* If ADDR is within TABLE set the output parameters and return TRUE,
+   otherwise set *FILENAME_PTR to NULL and return FALSE.
    The parameters FILENAME_PTR, LINENUMBER_PTR and DISCRIMINATOR_PTR
    are pointers to the objects to be filled in.  */
 
-static bfd_vma
+static bool
 lookup_address_in_line_info_table (struct line_info_table *table,
 				   bfd_vma addr,
 				   const char **filename_ptr,
@@ -2608,12 +2607,12 @@ lookup_address_in_line_info_table (struct line_info_table *table,
       *linenumber_ptr = info->line;
       if (discriminator_ptr)
 	*discriminator_ptr = info->discriminator;
-      return seq->last_line->address - seq->low_pc;
+      return true;
     }
 
  fail:
   *filename_ptr = NULL;
-  return 0;
+  return false;
 }
 
 /* Read in the .debug_ranges section for future reference.  */
@@ -4008,14 +4007,11 @@ comp_unit_contains_address (struct comp_unit *unit, bfd_vma addr)
 }
 
 /* If UNIT contains ADDR, set the output parameters to the values for
-   the line containing ADDR.  The output parameters, FILENAME_PTR,
-   FUNCTION_PTR, and LINENUMBER_PTR, are pointers to the objects
-   to be filled in.
-
-   Returns the range of addresses covered by the entry that was used
-   to fill in *LINENUMBER_PTR or 0 if it was not filled in.  */
+   the line containing ADDR and return TRUE.  Otherwise return FALSE.
+   The output parameters, FILENAME_PTR, FUNCTION_PTR, and
+   LINENUMBER_PTR, are pointers to the objects to be filled in.  */
 
-static bfd_vma
+static bool
 comp_unit_find_nearest_line (struct comp_unit *unit,
 			     bfd_vma addr,
 			     const char **filename_ptr,
@@ -4023,7 +4019,7 @@ comp_unit_find_nearest_line (struct comp_unit *unit,
 			     unsigned int *linenumber_ptr,
 			     unsigned int *discriminator_ptr)
 {
-  bool func_p;
+  bool line_p, func_p;
 
   if (!comp_unit_maybe_decode_line_info (unit))
     return false;
@@ -4033,10 +4029,11 @@ comp_unit_find_nearest_line (struct comp_unit *unit,
   if (func_p && (*function_ptr)->tag == DW_TAG_inlined_subroutine)
     unit->stash->inliner_chain = *function_ptr;
 
-  return lookup_address_in_line_info_table (unit->line_table, addr,
-					    filename_ptr,
-					    linenumber_ptr,
-					    discriminator_ptr);
+  line_p = lookup_address_in_line_info_table (unit->line_table, addr,
+					      filename_ptr,
+					      linenumber_ptr,
+					      discriminator_ptr);
+  return line_p || func_p;
 }
 
 /* Check to see if line info is already decoded in a comp_unit.
@@ -5187,54 +5184,17 @@ _bfd_dwarf2_find_nearest_line (bfd *abfd,
     }
   else
     {
-      bfd_vma min_range = (bfd_vma) -1;
-      const char * local_filename = NULL;
-      struct funcinfo *local_function = NULL;
-      unsigned int local_linenumber = 0;
-      unsigned int local_discriminator = 0;
-
       for (each = stash->f.all_comp_units; each; each = each->next_unit)
 	{
-	  bfd_vma range = (bfd_vma) -1;
-
 	  found = ((each->arange.high == 0
 		    || comp_unit_contains_address (each, addr))
-		   && (range = (comp_unit_find_nearest_line
-				(each, addr, &local_filename,
-				 &local_function, &local_linenumber,
-				 &local_discriminator))) != 0);
+		   && comp_unit_find_nearest_line (each, addr,
+						   filename_ptr,
+						   &function,
+						   linenumber_ptr,
+						   discriminator_ptr));
 	  if (found)
-	    {
-	      /* PRs 15935 15994: Bogus debug information may have provided us
-		 with an erroneous match.  We attempt to counter this by
-		 selecting the match that has the smallest address range
-		 associated with it.  (We are assuming that corrupt debug info
-		 will tend to result in extra large address ranges rather than
-		 extra small ranges).
-
-		 This does mean that we scan through all of the CUs associated
-		 with the bfd each time this function is called.  But this does
-		 have the benefit of producing consistent results every time the
-		 function is called.  */
-	      if (range <= min_range)
-		{
-		  if (filename_ptr && local_filename)
-		    * filename_ptr = local_filename;
-		  if (local_function)
-		    function = local_function;
-		  if (discriminator_ptr && local_discriminator)
-		    * discriminator_ptr = local_discriminator;
-		  if (local_linenumber)
-		    * linenumber_ptr = local_linenumber;
-		  min_range = range;
-		}
-	    }
-	}
-
-      if (* linenumber_ptr)
-	{
-	  found = true;
-	  goto done;
+	    goto done;
 	}
     }
 
@@ -5259,7 +5219,7 @@ _bfd_dwarf2_find_nearest_line (bfd *abfd,
 						 filename_ptr,
 						 &function,
 						 linenumber_ptr,
-						 discriminator_ptr) != 0);
+						 discriminator_ptr));
 
       if (found)
 	break;

-- 
Alan Modra
Australia Development Lab, IBM