Re: Slow _bfd_strip_section_from_output

["H. J. Lu" <hjl at lucon dot org>]

On Tue, May 03, 2005 at 10:04:51AM +0930, Alan Modra wrote:
> On Sat, Apr 30, 2005 at 12:50:29PM -0700, H. J. Lu wrote:
> > _bfd_strip_section_from_output is known to be very slow:
> > 
> > http://sourceware.org/ml/binutils/2005-03/msg00826.html
> > 
> > It scans every section in all input files to find a match. We do
> > have link_order_head/link_order_tail. But they aren't available
> > when _bfd_strip_section_from_output is called. Can we build them
> > when we assign the output sections and fix them up before we need
> > them for output?
> 
> Yes, that's what I suggested in
> http://sourceware.org/ml/binutils/2005-03/msg00827.html
> 

This is what I come up with. I added link_order_input so that I
don't have to seatch the whole list to find a bfd_input_link_order.
Otherwise, bfd_new_link_order will be as slow as the old
_bfd_strip_section_from_output.

Everything seems OK on ia32, ia64 and x86_64. But I did get some
failures on "cris-elf". I don't know if they are harmless.


H.J.
-----
bfd/

2005-04-30  H.J. Lu  <hongjiu.lu@intel.com>

	* linker.c (bfd_new_link_order): Reuse link_order_input.
	(bfd_new_input_link_order): New.
	(_bfd_default_link_order): Ignore bfd_input_link_order.

	* section.c (bfd_section): Add link_order_input.
	(STD_SECTION): Initialize link_order_input.
	(_bfd_strip_section_from_output): Scan bfd_input_link_order
	for input sections.
	* bfd-in2.h: Regenerated.

include/

2005-04-30  H.J. Lu  <hongjiu.lu@intel.com>

	* bfdlink.h (bfd_link_order_type): Add bfd_input_link_order.
	(bfd_new_input_link_order): New.

ld/

2005-04-30  H.J. Lu  <hongjiu.lu@intel.com>

	* ldlang.c (lang_add_section): Call bfd_new_input_link_order
	to set up link_order_input.

--- binutils/bfd/linker.c.input	2005-04-30 15:00:46.000000000 -0700
+++ binutils/bfd/linker.c	2005-04-30 15:00:46.000000000 -0700
@@ -2648,9 +2648,20 @@ _bfd_generic_reloc_link_order (bfd *abfd
 struct bfd_link_order *
 bfd_new_link_order (bfd *abfd, asection *section)
 {
-  bfd_size_type amt = sizeof (struct bfd_link_order);
+  bfd_size_type amt;
   struct bfd_link_order *new;
 
+  new = section->link_order_input;
+  if (new)
+    {
+      if (new->type != bfd_input_link_order)
+	abort ();
+      section->link_order_input = new->next;
+      new->type = bfd_undefined_link_order;
+      return new;
+    }
+
+  amt = sizeof (struct bfd_link_order);
   new = bfd_zalloc (abfd, amt);
   if (!new)
     return NULL;
@@ -2666,6 +2677,36 @@ bfd_new_link_order (bfd *abfd, asection 
   return new;
 }
 
+/* Allocate a new bfd_input_link_order for a section.  */
+
+struct bfd_link_order *
+bfd_new_input_link_order (bfd *abfd, asection *section)
+{
+  bfd_size_type amt = sizeof (struct bfd_link_order);
+  struct bfd_link_order *new;
+  asection *output_section;
+
+  new = bfd_zalloc (abfd, amt);
+  if (!new)
+    return NULL;
+
+  output_section = section->output_section;
+
+  new->type = bfd_input_link_order;
+  new->u.indirect.section = section;
+
+  if (output_section->link_order_tail != NULL)
+    output_section->link_order_tail->next = new;
+  else
+    {
+      output_section->link_order_head = new;
+      output_section->link_order_input = new;
+    }
+  output_section->link_order_tail = new;
+
+  return new;
+}
+
 /* Default link order processing routine.  Note that we can not handle
    the reloc_link_order types here, since they depend upon the details
    of how the particular backends generates relocs.  */
@@ -2678,6 +2719,8 @@ _bfd_default_link_order (bfd *abfd,
 {
   switch (link_order->type)
     {
+    case bfd_input_link_order:
+      return TRUE;
     case bfd_undefined_link_order:
     case bfd_section_reloc_link_order:
     case bfd_symbol_reloc_link_order:
--- binutils/bfd/section.c.input	2005-04-30 15:00:46.000000000 -0700
+++ binutils/bfd/section.c	2005-04-30 15:00:46.000000000 -0700
@@ -500,6 +500,7 @@ CODE_FRAGMENT
 .
 .  struct bfd_link_order *link_order_head;
 .  struct bfd_link_order *link_order_tail;
+.  struct bfd_link_order *link_order_input;
 .} asection;
 .
 .{* These sections are global, and are managed by BFD.  The application
@@ -639,8 +640,8 @@ static const asymbol global_syms[] =
     /* symbol_ptr_ptr,                                               */	\
        (struct bfd_symbol **) &SYM,					\
 									\
-    /* link_order_head, link_order_tail                              */	\
-       NULL,            NULL						\
+    /* link_order_head, link_order_tail, link_order_input            */	\
+       NULL,            NULL,		 NULL				\
     }
 
 STD_SECTION (bfd_com_section, SEC_IS_COMMON, bfd_com_symbol,
@@ -1412,11 +1413,12 @@ DESCRIPTION
 	to remove sections.
 */
 void
-_bfd_strip_section_from_output (struct bfd_link_info *info, asection *s)
+_bfd_strip_section_from_output
+  (struct bfd_link_info *info ATTRIBUTE_UNUSED, asection *s)
 {
   asection *os;
   asection *is;
-  bfd *abfd;
+  struct bfd_link_order *p;
 
   s->flags |= SEC_EXCLUDE;
 
@@ -1429,10 +1431,18 @@ _bfd_strip_section_from_output (struct b
 
   /* If the output section has other (non-excluded) input sections, we
      can't remove it.  */
-  for (abfd = info->input_bfds; abfd != NULL; abfd = abfd->link_next)
-    for (is = abfd->sections; is != NULL; is = is->next)
-      if (is->output_section == os && (is->flags & SEC_EXCLUDE) == 0)
-	return;
+  for (p = os->link_order_head; p; p = p->next)
+    switch (p->type)
+      {
+      default:
+	abort ();
+	break;
+      case bfd_input_link_order:
+	is = p->u.indirect.section;
+	if ((is->flags & SEC_EXCLUDE) == 0)
+	  return;
+	break;
+      }
 
   /* If the output section is empty, flag it for removal too.
      See ldlang.c:strip_excluded_output_sections for the action.  */
--- binutils/include/bfdlink.h.input	2005-03-22 06:09:08.000000000 -0800
+++ binutils/include/bfdlink.h	2005-04-30 15:00:46.000000000 -0700
@@ -546,6 +546,7 @@ enum bfd_link_order_type
 {
   bfd_undefined_link_order,	/* Undefined.  */
   bfd_indirect_link_order,	/* Built from a section.  */
+  bfd_input_link_order,		/* bfd_indirect_link_order.  */
   bfd_data_link_order,		/* Set to explicit data.  */
   bfd_section_reloc_link_order,	/* Relocate against a section.  */
   bfd_symbol_reloc_link_order	/* Relocate against a symbol.  */
@@ -636,6 +637,10 @@ struct bfd_link_order_reloc
 /* Allocate a new link_order for a section.  */
 extern struct bfd_link_order *bfd_new_link_order (bfd *, asection *);
 
+/* Allocate a new bfd_input_link_order for a section.  */
+extern struct bfd_link_order *bfd_new_input_link_order
+  (bfd *, asection *);
+
 /* These structures are used to describe version information for the
    ELF linker.  These structures could be manipulated entirely inside
    BFD, but it would be a pain.  Instead, the regular linker sets up
--- binutils/ld/ldlang.c.input	2005-04-30 15:00:46.000000000 -0700
+++ binutils/ld/ldlang.c	2005-04-30 15:19:33.000000000 -0700
@@ -1728,6 +1728,8 @@ lang_add_section (lang_statement_list_ty
       new->ifile = file;
       section->output_section = output->bfd_section;
 
+      ASSERT (bfd_new_input_link_order (output_bfd, section) != NULL);
+
       flags = section->flags;
 
       /* We don't copy the SEC_NEVER_LOAD flag from an input section