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

[Jan Beulich <jbeulich@suse.com>]

On 29.03.2022 01:47, Alan Modra wrote:
> 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.

Yeah, makes sense to me. I guess if bad input was to be worked around
again, a testcase covering the specific situation would want adding, so
it won't be lost what specifically is to be worked around.

Jan

> 	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;
>