Re: [PATCH] Optimize ldlang_add_file for large input quantities

[Alan Modra <amodra at bigpond dot net dot au>]

On Mon, May 28, 2007 at 05:48:29AM -0700, Noah Misch wrote:
> On Mon, May 28, 2007 at 01:04:04PM +0930, Alan Modra wrote:
> > On Sat, May 26, 2007 at 08:47:16AM -0700, Noah Misch wrote:
> > > 	include/
> > > 	* bfdlink.h (struct bfd_link_info): Add input_bfds_tail.
> > > 	
> > > 	ld/
> > > 	* ldlang.c (ldlang_add_file): Use input_bfds_tail.
> > 
> > Have you audited all bfd and ld code that touches input_bfds to ensure
> > that no other place inserts or deletes list elements?  If you find
> > such a place then it might need to update input_bfds_tail..
> 
> I audited that to the best of my ability.  Of the numerous input_bfds consumers,
> only ldlang_add_file appears to modify the structure of the list.

Thanks, I'm fairly certain that is the case too.  Applying this
modified version of your patch.

include/
	* bfdlink.h (struct bfd_link_info): Add input_bfds_tail.
bfd/
	* simple.c (bfd_simple_get_relocated_section_content): Init
	input_bfds_tail.
ld/
	* ldlang.c (ldlang_add_file): Use input_bfds_tail.
	* ldmain.c (main): Init input_bfds_tail.  Sort link_info
	initialization.

Index: include/bfdlink.h
===================================================================
RCS file: /cvs/src/src/include/bfdlink.h,v
retrieving revision 1.67
diff -u -p -r1.67 bfdlink.h
--- include/bfdlink.h	30 Apr 2007 14:06:40 -0000	1.67
+++ include/bfdlink.h	31 May 2007 14:46:13 -0000
@@ -395,6 +395,7 @@ struct bfd_link_info
   /* The list of input BFD's involved in the link.  These are chained
      together via the link_next field.  */
   bfd *input_bfds;
+  bfd **input_bfds_tail;
 
   /* If a symbol should be created for each input BFD, this is section
      where those symbols should be placed.  It must be a section in
Index: bfd/simple.c
===================================================================
RCS file: /cvs/src/src/bfd/simple.c,v
retrieving revision 1.26
diff -u -p -r1.26 simple.c
--- bfd/simple.c	26 Apr 2007 14:46:58 -0000	1.26
+++ bfd/simple.c	31 May 2007 14:45:54 -0000
@@ -183,6 +183,7 @@ bfd_simple_get_relocated_section_content
   /* Fill in the bare minimum number of fields for our purposes.  */
   memset (&link_info, 0, sizeof (link_info));
   link_info.input_bfds = abfd;
+  link_info.input_bfds_tail = &abfd->link_next;
 
   link_info.hash = _bfd_generic_link_hash_table_create (abfd);
   link_info.callbacks = &callbacks;
Index: ld/ldlang.c
===================================================================
RCS file: /cvs/src/src/ld/ldlang.c,v
retrieving revision 1.263
diff -u -p -r1.263 ldlang.c
--- ld/ldlang.c	2 May 2007 01:22:40 -0000	1.263
+++ ld/ldlang.c	31 May 2007 14:46:17 -0000
@@ -5435,8 +5435,6 @@ lang_for_each_file (void (*func) (lang_i
 void
 ldlang_add_file (lang_input_statement_type *entry)
 {
-  bfd **pp;
-
   lang_statement_append (&file_chain,
 			 (lang_statement_union_type *) entry,
 			 &entry->next);
@@ -5445,9 +5443,9 @@ ldlang_add_file (lang_input_statement_ty
      a link.  */
   ASSERT (entry->the_bfd->link_next == NULL);
   ASSERT (entry->the_bfd != output_bfd);
-  for (pp = &link_info.input_bfds; *pp != NULL; pp = &(*pp)->link_next)
-    ;
-  *pp = entry->the_bfd;
+
+  *link_info.input_bfds_tail = entry->the_bfd;
+  link_info.input_bfds_tail = &entry->the_bfd->link_next;
   entry->the_bfd->usrdata = entry;
   bfd_set_gp_size (entry->the_bfd, g_switch_value);
 
Index: ld/ldmain.c
===================================================================
RCS file: /cvs/src/src/ld/ldmain.c,v
retrieving revision 1.123
diff -u -p -r1.123 ldmain.c
--- ld/ldmain.c	7 May 2007 15:04:53 -0000	1.123
+++ ld/ldmain.c	31 May 2007 14:46:17 -0000
@@ -265,15 +265,16 @@ main (int argc, char **argv)
   link_info.keep_memory = TRUE;
   link_info.combreloc = TRUE;
   link_info.strip_discarded = TRUE;
-  link_info.callbacks = &link_callbacks;
   link_info.emit_hash = TRUE;
+  link_info.callbacks = &link_callbacks;
+  link_info.input_bfds_tail = &link_info.input_bfds;
   /* SVR4 linkers seem to set DT_INIT and DT_FINI based on magic _init
      and _fini symbols.  We are compatible.  */
   link_info.init_function = "_init";
   link_info.fini_function = "_fini";
+  link_info.relax_pass = 1;
   link_info.pei386_auto_import = -1;
   link_info.spare_dynamic_tags = 5;
-  link_info.relax_pass = 1;
 
   ldfile_add_arch ("");
   emulation = get_emulation (argc, argv);


-- 
Alan Modra
IBM OzLabs - Linux Technology Centre