Commit: Better caching in elf_find_function

Commit: Better caching in elf_find_function

[Nick Clifton]

[-- Attachment #1: Type: text/plain, Size: 1689 bytes --]

Hi Guys,

  I Following on from the fix for addr2line inconsistent behaviour, as
  reported in PR 30150, I am applying the attached patch to correct a
  related problem.  The issue is _bfd_elf_find_function() and its
  attempts to cache a previous result in order to speed up future
  lookups.  If the function is called successively with two addresses
  and the second address happens to lie within the region of the symbol
  discovered for the first address, then the cached value will be used,
  even if there is a better match available.  For example:

    % addr2line -fipae vmlinux 0xffffffff81002000 0xffffffff81002020
    0xffffffff81002000: hypercall_page at /tmp/linux-5.15.92/linux-5.15.92/arch/x86/kernel/../../x86/xen/xen-head.S:75
    0xffffffff81002020: hypercall_page at /tmp/linux-5.15.92/linux-5.15.92/arch/x86/kernel/../../x86/xen/xen-head.S:75

  The second result is wrong as there is an exact match for the
  0xffffffff8100202 address:

    % readelf --syms --wide vmlinux | grep -e hypercall_page -e xen_hypercall_mmu_update
        82: ffffffff81002020    32 FUNC    LOCAL  DEFAULT    1 xen_hypercall_mmu_update
    117144: ffffffff81002000  4096 NOTYPE  GLOBAL DEFAULT    1 hypercall_page

  The patch fixes the problem by checking to see if symbols beyond the
  target address lie within the region covered by the current best-fit,
  and if they do, reducing the size of the best fit so that it no longer
  overlaps.

  In addition the patch moves the logic for choosing a best fit into a
  separate inline function in order to make it simpler and easier to
  understand.

  Tested with no regressions on a large number of different toolchains.

Cheers
  Nick
  

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: elf-find-function.patch --]
[-- Type: text/x-patch, Size: 5152 bytes --]

diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c
index 8c9bd7a3026..ac7c4f63c57 100644
--- a/bfd/dwarf2.c
+++ b/bfd/dwarf2.c
@@ -4681,6 +4681,7 @@ comp_unit_find_nearest_line (struct comp_unit *unit,
 
   *function_ptr = NULL;
   func_p = lookup_address_in_function_table (unit, addr, function_ptr);
+
   if (func_p && (*function_ptr)->tag == DW_TAG_inlined_subroutine)
     unit->stash->inliner_chain = *function_ptr;
 
@@ -6134,6 +6135,60 @@ _bfd_dwarf2_cleanup_debug_info (bfd *abfd, void **pinfo)
     bfd_close (stash->alt.bfd_ptr);
 }
 
+typedef struct elf_find_function_cache
+{
+  asection *     last_section;
+  asymbol *      func;
+  const char *   filename;
+  bfd_size_type  code_size;
+  bfd_vma        code_off;
+
+} elf_find_function_cache;
+
+
+/* Returns TRUE if the symbol with address CODE_OFF and size CODE_SIZE
+   is a better fit to match OFFSET than whatever is currenly stored in
+   CACHE.  */
+
+static inline bool
+better_fit (elf_find_function_cache *  cache,
+	    bfd_vma                    code_off,
+	    bfd_size_type              code_size,
+	    bfd_vma                    offset)
+{
+  /* If the symbol is beyond the desired offset, ignore it.  */
+  if (code_off > offset)
+    return false;
+
+  /* If the symbol is further away from the desired
+     offset than our current best, then ignore it.  */
+  if (code_off < cache->code_off)
+    return false;
+
+  /* On the other hand, if it is closer, then use it.  */
+  if (code_off > cache->code_off)
+    return true;
+
+  /* If our current best fit does not actually reach the desired
+     offset...  */
+  if (cache->code_off + cache->code_size <= offset)
+    {
+      /* Then return whichever candidate covers more area.  */
+      return code_size > cache->code_size;
+    }
+
+  /* If the new symbol also covers the desired offset... */
+  if (code_off + code_size > offset)
+    {
+      /* Then choose whichever is smaller.  */
+      /* FIXME: Maybe prefer LOCAL over GLOBAL or something else here ?  */
+      return code_size < cache->code_size;
+    }
+
+  /* Otherwise the cached symbol is better.  */
+  return false;
+}
+
 /* Find the function to a particular section and offset,
    for error reporting.  */
 
@@ -6145,21 +6200,14 @@ _bfd_elf_find_function (bfd *abfd,
 			const char **filename_ptr,
 			const char **functionname_ptr)
 {
-  struct elf_find_function_cache
-  {
-    asection *last_section;
-    asymbol *func;
-    const char *filename;
-    bfd_size_type func_size;
-  } *cache;
-
   if (symbols == NULL)
     return NULL;
 
   if (bfd_get_flavour (abfd) != bfd_target_elf_flavour)
     return NULL;
 
-  cache = elf_tdata (abfd)->elf_find_function_cache;
+  elf_find_function_cache * cache = elf_tdata (abfd)->elf_find_function_cache;
+
   if (cache == NULL)
     {
       cache = bfd_zalloc (abfd, sizeof (*cache));
@@ -6167,13 +6215,13 @@ _bfd_elf_find_function (bfd *abfd,
       if (cache == NULL)
 	return NULL;
     }
+
   if (cache->last_section != section
       || cache->func == NULL
       || offset < cache->func->value
-      || offset >= cache->func->value + cache->func_size)
+      || offset >= cache->func->value + cache->code_size)
     {
       asymbol *file;
-      bfd_vma low_func;
       asymbol **p;
       /* ??? Given multiple file symbols, it is impossible to reliably
 	 choose the right file name for global symbols.  File symbols are
@@ -6187,11 +6235,11 @@ _bfd_elf_find_function (bfd *abfd,
       const struct elf_backend_data *bed = get_elf_backend_data (abfd);
 
       file = NULL;
-      low_func = 0;
       state = nothing_seen;
       cache->filename = NULL;
       cache->func = NULL;
-      cache->func_size = 0;
+      cache->code_size = 0;
+      cache->code_off = 0;
       cache->last_section = section;
 
       for (p = symbols; *p != NULL; p++)
@@ -6208,24 +6256,36 @@ _bfd_elf_find_function (bfd *abfd,
 	      continue;
 	    }
 
+	  if (state == nothing_seen)
+	    state = symbol_seen;
+
 	  size = bed->maybe_function_sym (sym, section, &code_off);
-	  if (size != 0
-	      && code_off <= offset
-	      && (code_off > low_func
-		  || (code_off == low_func
-		      && size > cache->func_size)))
+
+	  if (size == 0)
+	    continue;
+
+	  if (better_fit (cache, code_off, size, offset))
 	    {
 	      cache->func = sym;
-	      cache->func_size = size;
+	      cache->code_size = size;
+	      cache->code_off = code_off;
 	      cache->filename = NULL;
-	      low_func = code_off;
+
 	      if (file != NULL
 		  && ((sym->flags & BSF_LOCAL) != 0
 		      || state != file_after_symbol_seen))
 		cache->filename = bfd_asymbol_name (file);
 	    }
-	  if (state == nothing_seen)
-	    state = symbol_seen;
+	  /* Otherwise, if the symbol is beyond the desired offset but it
+	     lies within the bounds of the current best match then reduce
+	     the size of the current best match so that future searches
+	     will not not used the cached symbol by mistake.  */
+	  else if (code_off > offset 
+		   && code_off > cache->code_off
+		   && code_off < cache->code_off + cache->code_size)
+	    {
+	      cache->code_size = code_off - cache->code_off;
+	    }
 	}
     }
 

Re: Commit: Better caching in elf_find_function

[Alan Modra]

On Thu, Feb 23, 2023 at 05:26:19PM +0000, Nick Clifton via Binutils wrote:
> Hi Guys,
> 
>   I Following on from the fix for addr2line inconsistent behaviour, as
>   reported in PR 30150, I am applying the attached patch to correct a
>   related problem.  The issue is _bfd_elf_find_function() and its
>   attempts to cache a previous result in order to speed up future
>   lookups.  If the function is called successively with two addresses
>   and the second address happens to lie within the region of the symbol
>   discovered for the first address, then the cached value will be used,
>   even if there is a better match available.  For example:
> 
>     % addr2line -fipae vmlinux 0xffffffff81002000 0xffffffff81002020
>     0xffffffff81002000: hypercall_page at /tmp/linux-5.15.92/linux-5.15.92/arch/x86/kernel/../../x86/xen/xen-head.S:75
>     0xffffffff81002020: hypercall_page at /tmp/linux-5.15.92/linux-5.15.92/arch/x86/kernel/../../x86/xen/xen-head.S:75
> 
>   The second result is wrong as there is an exact match for the
>   0xffffffff8100202 address:
> 
>     % readelf --syms --wide vmlinux | grep -e hypercall_page -e xen_hypercall_mmu_update
>         82: ffffffff81002020    32 FUNC    LOCAL  DEFAULT    1 xen_hypercall_mmu_update
>     117144: ffffffff81002000  4096 NOTYPE  GLOBAL DEFAULT    1 hypercall_page
> 
>   The patch fixes the problem by checking to see if symbols beyond the
>   target address lie within the region covered by the current best-fit,
>   and if they do, reducing the size of the best fit so that it no longer
>   overlaps.
> 
>   In addition the patch moves the logic for choosing a best fit into a
>   separate inline function in order to make it simpler and easier to
>   understand.
> 
>   Tested with no regressions on a large number of different toolchains.

Failures are seen on mips targets.

mipsel-linux-gnu  +FAIL: MIPS PIC relocation 6 (MIPS16)
mipsel-linux-gnu  +FAIL: MIPS PIC relocation 7
mipsel-linux-gnu  +FAIL: MIPS PIC relocation 7 (microMIPS)

The first failure is due to this symbol
     4: 00000000     0 NOTYPE  LOCAL  DEFAULT [MIPS16]     1 $LCL
being chosen rather than
    11: 00000000    32 FUNC    GLOBAL DEFAULT [MIPS16]     1 foo
for an error on the first address of foo.  Even if the address fit is
better, I think a NOTYPE LOCAL ought to not be chosen over a
FUNC GLOBAL.

-- 
Alan Modra
Australia Development Lab, IBM

Re: Commit: Better caching in elf_find_function

[Nick Clifton]

[-- Attachment #1: Type: text/plain, Size: 832 bytes --]

Hi Alan,

> Failures are seen on mips targets.
> 
> mipsel-linux-gnu  +FAIL: MIPS PIC relocation 6 (MIPS16)

*sigh* I had noticed these, but thought that they were due to an unrelated problem.  :-(

> The first failure is due to this symbol
>       4: 00000000     0 NOTYPE  LOCAL  DEFAULT [MIPS16]     1 $LCL
> being chosen rather than
>      11: 00000000    32 FUNC    GLOBAL DEFAULT [MIPS16]     1 foo
> for an error on the first address of foo.  Even if the address fit is
> better, I think a NOTYPE LOCAL ought to not be chosen over a
> FUNC GLOBAL.

Agreed.

I am checking in the attached patch to address this problem.  It prefers
function symbols over non-function symbols and typed symbols over notype
symbols.  I was not sure if we should prefer LOCAL symbols over GLOBALS
so I did not add code for that.

Cheers
   Nick


[-- Attachment #2: elf-find-function.patch.2 --]
[-- Type: application/x-troff-man, Size: 3046 bytes --]