[PATCH] section-select: Fix performance problem (PR30367)

[PATCH] section-select: Fix performance problem (PR30367)

[Michael Matz]

when using many wild-statements with non-wildcard filenames we
were running into quadraticness via repeatedly using lookup_name
on a long list of loaded files.  I've originally retained using
lookup_name because that preserved existing behaviour most obviously.
In particular in matching wild-statements when using a non-wildcard
filename it matches against local_sym_name, not the filename member.
If the wildspec would have an archive-spec or a wildcard it would use
the filename member, though.  Also it would load the named file
(and ignore it, as being not equal to the currently considered
input-statement).

Rewrite this to not use lookup_name but retain the comparison
against local_sym_name with a comment to that effect.

	PR 30367
	* ldlang.c (walk_wild_section_match): Don't use lookup_name
	but directly compare spec and local_sym_name.
---

As the comment aludes to there is pre-existing inconsistency in that
some cases used to (and still do) compare against 
input_statement->filename, and other cases against ->local_sym_name.
Not just in section-matching but also other routines.  In general the 
->local_sym_name is the naming as given on cmdline or script (which may 
be "-lfoo"!) and ->filename is the one that's loaded from the filesystem,
in particular may contain sysroot and search-dir directory prefixes.

I'm not brave enough to change this with this patch, as all added 
consistency probably breaks currently working linker scripts people 
might have written over the years according to the current quirks.

But, regression tested on 158 targets, and it fixes the noted performance 
problem.  Okay for master?

---
 ld/ldlang.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index b684e2d479a..4bec280b9df 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -433,10 +433,18 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
     }
   else
     {
-      lang_input_statement_type *f;
-      /* Perform the iteration over a single file.  */
-      f = lookup_name (file_spec);
-      if (f != file)
+      /* XXX Matching against non-wildcard filename in wild statements
+	 was done by going through lookup_name, which uses
+	 ->local_sym_name to compare against, not ->filename.  We retain
+	 this behaviour even though the above code paths use filename.
+	 It would be more logical to use it here as well, in which
+	 case the above wildcarp() arm could be folded into this by using
+	 name_match.  This would also solve the worry of what to do
+	 about unset local_sym_name (in which case lookup_name simply adds
+	 the input file again).  */
+      const char *filename = file->local_sym_name;
+      if (filename == NULL
+	  || filename_cmp (filename, file_spec) != 0)
 	return;
     }
 
-- 
2.39.1

Re: [PATCH] section-select: Fix performance problem (PR30367)

[Alan Modra]

On Tue, Apr 18, 2023 at 03:12:12PM +0000, Michael Matz via Binutils wrote:
> when using many wild-statements with non-wildcard filenames we
> were running into quadraticness via repeatedly using lookup_name
> on a long list of loaded files.  I've originally retained using
> lookup_name because that preserved existing behaviour most obviously.
> In particular in matching wild-statements when using a non-wildcard
> filename it matches against local_sym_name, not the filename member.

If any consistency changes were contemplated, I think I'd be inclined
to replace filename with local_sym_name not the other way around.
Also rename local_sym_name to cmdline_name, since there aren't any
uses of local_sym_name as "Name to use for the symbol giving address
of text start" as far as I'm aware.

> If the wildspec would have an archive-spec or a wildcard it would use
> the filename member, though.  Also it would load the named file
> (and ignore it, as being not equal to the currently considered
> input-statement).
> 
> Rewrite this to not use lookup_name but retain the comparison
> against local_sym_name with a comment to that effect.
> 
> 	PR 30367
> 	* ldlang.c (walk_wild_section_match): Don't use lookup_name
> 	but directly compare spec and local_sym_name.
> ---
> 
> As the comment aludes to there is pre-existing inconsistency in that
> some cases used to (and still do) compare against 
> input_statement->filename, and other cases against ->local_sym_name.
> Not just in section-matching but also other routines.  In general the 
> ->local_sym_name is the naming as given on cmdline or script (which may 
> be "-lfoo"!) and ->filename is the one that's loaded from the filesystem,
> in particular may contain sysroot and search-dir directory prefixes.
> 
> I'm not brave enough to change this with this patch, as all added 
> consistency probably breaks currently working linker scripts people 
> might have written over the years according to the current quirks.
> 
> But, regression tested on 158 targets, and it fixes the noted performance 
> problem.  Okay for master?

OK, but

> ---
>  ld/ldlang.c | 16 ++++++++++++----
>  1 file changed, 12 insertions(+), 4 deletions(-)
> 
> diff --git a/ld/ldlang.c b/ld/ldlang.c
> index b684e2d479a..4bec280b9df 100644
> --- a/ld/ldlang.c
> +++ b/ld/ldlang.c
> @@ -433,10 +433,18 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
>      }
>    else
>      {
> -      lang_input_statement_type *f;
> -      /* Perform the iteration over a single file.  */
> -      f = lookup_name (file_spec);
> -      if (f != file)
> +      /* XXX Matching against non-wildcard filename in wild statements
> +	 was done by going through lookup_name, which uses
> +	 ->local_sym_name to compare against, not ->filename.  We retain
> +	 this behaviour even though the above code paths use filename.
> +	 It would be more logical to use it here as well, in which
> +	 case the above wildcarp() arm could be folded into this by using

this is fishy.  :)      ^^^^^^^^

> +	 name_match.  This would also solve the worry of what to do
> +	 about unset local_sym_name (in which case lookup_name simply adds
> +	 the input file again).  */
> +      const char *filename = file->local_sym_name;
> +      if (filename == NULL
> +	  || filename_cmp (filename, file_spec) != 0)
>  	return;
>      }
>  
> -- 
> 2.39.1

-- 
Alan Modra
Australia Development Lab, IBM