This is the mail archive of the binutils@sources.redhat.com mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: PATCH: Use a double section list to speed up linker by 30%


On Mon, May 02, 2005 at 04:11:10PM +0930, Alan Modra wrote:
> On Sun, May 01, 2005 at 11:14:29PM -0700, H. J. Lu wrote:
> > On Mon, May 02, 2005 at 02:47:13PM +0930, Alan Modra wrote:
> > > On Sun, May 01, 2005 at 12:47:57PM -0700, H. J. Lu wrote:
> > > > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote:
> > > > > In case of address overlap check, we only
> > > > > need to check the previous section.
> > > 
> > > I don't think this is true.
> > 
> > I guess I need to go back until the end of the current section <
> > the start of the section.
> 
> No.  A section's address can be specified in a linker script.  The order
> of sections in the output is irrelevant.  If you want to fix
> lang_check_section_addresses properly, then replace the algorithm with
> one that scales better.  For example, build an array of pointers to the
> output sections, then qsort this array on lma.  After doing that you can
> simply compare adjacent lmas.

Here is the updated patch.

> 
> > > > 	(bfd_section_double_list_remove): New.
> > > > 	(bfd_section_list_remove): Updated.
> > > 
> > > I also can't see the sense in both adding new macros and keeping the old
> > > ones.
> > 
> > I will remove bfd_section_list_remove.
> 
> Better would be to remove "double_" from the macro names.
> 

"** section_tail" doesn't work since it points to the next field of
the last section. I can't get the prev field from that.



H.J.
----
bfd/

2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>

	* bfd.c (bfd): Remove section_tail and add section_last.
	(bfd_preserve): Likewise.
	(bfd_preserve_save): Likewise.
	(bfd_preserve_restore): Likewise.
	* opncls.c (_bfd_new_bfd): Likewise.

	* coffcode.h (coff_compute_section_file_positions): Updated.
	(coff_compute_section_file_positions): Likewise.
	* elf.c (assign_section_numbers): Likewise.
	* elf32-i370.c (i370_elf_size_dynamic_sections): Likewise.
	* elf64-mmix.c (mmix_elf_final_link): Likewise.
	* elfxx-ia64.c (elfNN_ia64_object_p): Likewise.
	* elfxx-mips.c (_bfd_mips_elf_link_hash_table_create): Likewise.
	* sunos.c (sunos_add_dynamic_symbols): Likewise.
	* xcofflink.c (_bfd_xcoff_bfd_final_link): Likewise.

	* ecoff.c (bfd_debug_section): Initialize prev.

	* section.c (bfd_section): Add prev.
	(bfd_section_list_remove): Updated.
	(bfd_section_list_append): New.
	(bfd_section_list_insert_after): New.
	(bfd_section_list_insert_before): New.
	(bfd_section_list_insert): Removed.
	(bfd_section_removed_from_list): Updated.
	(STD_SECTION): Initialize prev.
	(bfd_section_init): Updated.
	(bfd_section_list_clear): Updated.

	* bfd-in2.h: Regenerated.

gas/

2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>

	* write.c (write_object_file): Use bfd_section_double_list_remove
	to remove sections.

ld/

2005-05-01  H.J. Lu  <hongjiu.lu@intel.com>

	* emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section):
	Updated for bfd_section_list_remove change.
	* ldlang.c (lang_insert_orphan): Likewise.
	(strip_excluded_or_unused_output_sections): Likewise.
	(sort_sections_by_lma): New.
	(lang_check_section_addresses): Sort the sections before
	checking addresses.

--- binutils/bfd/bfd.c.dbl	2005-01-19 09:06:06.000000000 -0800
+++ binutils/bfd/bfd.c	2005-05-02 12:25:36.000000000 -0700
@@ -111,8 +111,8 @@ CODE_FRAGMENT
 .  {* Pointer to linked list of sections.  *}
 .  struct bfd_section *sections;
 .
-.  {* The place where we add to the section list.  *}
-.  struct bfd_section **section_tail;
+.  {* The last section on the section list.  *}
+.  struct bfd_section *section_last;
 .
 .  {* The number of sections.  *}
 .  unsigned int section_count;
@@ -1390,7 +1390,7 @@ CODE_FRAGMENT
 .  flagword flags;
 .  const struct bfd_arch_info *arch_info;
 .  struct bfd_section *sections;
-.  struct bfd_section **section_tail;
+.  struct bfd_section *section_last;
 .  unsigned int section_count;
 .  struct bfd_hash_table section_htab;
 .};
@@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
   preserve->arch_info = abfd->arch_info;
   preserve->flags = abfd->flags;
   preserve->sections = abfd->sections;
-  preserve->section_tail = abfd->section_tail;
+  preserve->section_last = abfd->section_last;
   preserve->section_count = abfd->section_count;
   preserve->section_htab = abfd->section_htab;
 
@@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
   abfd->arch_info = &bfd_default_arch_struct;
   abfd->flags &= BFD_IN_MEMORY;
   abfd->sections = NULL;
-  abfd->section_tail = &abfd->sections;
+  abfd->section_last = NULL;
   abfd->section_count = 0;
 
   return TRUE;
@@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct 
   abfd->flags = preserve->flags;
   abfd->section_htab = preserve->section_htab;
   abfd->sections = preserve->sections;
-  abfd->section_tail = preserve->section_tail;
+  abfd->section_last = preserve->section_last;
   abfd->section_count = preserve->section_count;
 
   /* bfd_release frees all memory more recently bfd_alloc'd than
--- binutils/bfd/coffcode.h.dbl	2005-04-21 10:09:46.000000000 -0700
+++ binutils/bfd/coffcode.h	2005-05-02 12:55:39.000000000 -0700
@@ -1717,7 +1717,6 @@ coff_set_alignment_hook (bfd *abfd, asec
 {
   struct internal_scnhdr *hdr = (struct internal_scnhdr *) scnhdr;
   asection *real_sec;
-  asection **ps;
 
   if ((hdr->s_flags & STYP_OVRFLO) == 0)
     return;
@@ -1729,14 +1728,10 @@ coff_set_alignment_hook (bfd *abfd, asec
   real_sec->reloc_count = hdr->s_paddr;
   real_sec->lineno_count = hdr->s_vaddr;
 
-  for (ps = &abfd->sections; *ps != NULL; ps = &(*ps)->next)
+  if (!bfd_section_removed_from_list (abfd, section))
     {
-      if (*ps == section)
-	{
-	  bfd_section_list_remove (abfd, ps);
-	  --abfd->section_count;
-	  break;
-	}
+      bfd_section_list_remove (abfd, section);
+      --abfd->section_count;
     }
 }
 
@@ -3033,11 +3028,12 @@ coff_compute_section_file_positions (bfd
     /* Rethread the linked list into sorted order; at the same time,
        assign target_index values.  */
     target_index = 1;
-    abfd->sections = section_list[0];
+    abfd->sections = NULL;
+    abfd->section_last = NULL;
     for (i = 0; i < count; i++)
       {
 	current = section_list[i];
-	current->next = section_list[i + 1];
+	bfd_section_list_append (abfd, current);
 
 	/* Later, if the section has zero size, we'll be throwing it
 	   away, so we don't want to number it now.  Note that having
@@ -3056,7 +3052,6 @@ coff_compute_section_file_positions (bfd
 	else
 	  current->target_index = target_index++;
       }
-    abfd->section_tail = &current->next;
 
     free (section_list);
   }
--- binutils/bfd/ecoff.c.dbl	2005-03-16 14:22:39.000000000 -0800
+++ binutils/bfd/ecoff.c	2005-05-02 12:25:36.000000000 -0700
@@ -52,8 +52,8 @@
 /* This stuff is somewhat copied from coffcode.h.  */
 static asection bfd_debug_section =
 {
-  /* name,      id,  index, next, flags, user_set_vma,             */
-     "*DEBUG*", 0,   0,     NULL, 0,     0,
+  /* name,      id,  index, next, prev, flags, user_set_vma,       */
+     "*DEBUG*", 0,   0,     NULL, NULL, 0,     0,
   /* linker_mark, linker_has_input, gc_mark, segment_mark,         */
      0,           0,                0,       0,
   /* sec_info_type, use_rela_p, has_tls_reloc, has_gp_reloc,       */
--- binutils/bfd/elf.c.dbl	2005-05-02 12:25:36.000000000 -0700
+++ binutils/bfd/elf.c	2005-05-02 13:32:17.000000000 -0700
@@ -2770,22 +2770,21 @@ assign_section_numbers (bfd *abfd, struc
   /* SHT_GROUP sections are in relocatable files only.  */
   if (link_info == NULL || link_info->relocatable)
     {
-      asection **secp;
+      asection *n;
 
       /* Put SHT_GROUP sections first.  */
-      secp = &abfd->sections;
-      while (*secp)
+      for (sec = abfd->sections; sec; sec = n)
 	{
-	  d = elf_section_data (*secp);
+	  d = elf_section_data (sec);
 
+	  n = sec->next;
 	  if (d->this_hdr.sh_type == SHT_GROUP)
 	    { 
-	      if ((*secp)->flags & SEC_LINKER_CREATED)
+	      if (sec->flags & SEC_LINKER_CREATED)
 		{
 		  /* Remove the linker created SHT_GROUP sections.  */
-		  bfd_section_list_remove (abfd, secp);
+		  bfd_section_list_remove (abfd, sec);
 		  abfd->section_count--;
-		  continue;
 		}
 	      else 
 		{
@@ -2794,8 +2793,6 @@ assign_section_numbers (bfd *abfd, struc
 		  d->this_idx = section_number++;
 		}
 	    }
-
-	  secp = &(*secp)->next;
 	}
     }
 
--- binutils/bfd/elf32-i370.c.dbl	2005-03-21 09:13:21.000000000 -0800
+++ binutils/bfd/elf32-i370.c	2005-05-02 13:00:58.000000000 -0700
@@ -756,18 +756,12 @@ i370_elf_size_dynamic_sections (output_b
 
       if (strip)
 	{
-	  asection **spp;
-
-	  for (spp = &s->output_section->owner->sections;
-	       *spp != NULL;
-	       spp = &(*spp)->next)
+	  if (!bfd_section_removed_from_list (s->output_section->owner,
+					      s->output_section))
 	    {
-	      if (*spp == s->output_section)
-		{
-		  bfd_section_list_remove (s->output_section->owner, spp);
-		  --s->output_section->owner->section_count;
-		  break;
-		}
+	      bfd_section_list_remove (s->output_section->owner,
+				       s->output_section);
+	      --s->output_section->owner->section_count;
 	    }
 	  continue;
 	}
--- binutils/bfd/elf64-mmix.c.dbl	2005-02-21 11:07:41.000000000 -0800
+++ binutils/bfd/elf64-mmix.c	2005-05-02 12:58:02.000000000 -0700
@@ -2249,7 +2249,6 @@ mmix_elf_final_link (abfd, info)
   /* We never output a register section, though we create one for
      temporary measures.  Check that nobody entered contents into it.  */
   asection *reg_section;
-  asection **secpp;
 
   reg_section = bfd_get_section_by_name (abfd, MMIX_REG_SECTION_NAME);
 
@@ -2260,11 +2259,7 @@ mmix_elf_final_link (abfd, info)
 	_bfd_abort (__FILE__, __LINE__, _("Register section has contents\n"));
 
       /* Really remove the section.  */
-      for (secpp = &abfd->sections;
-	   *secpp != reg_section;
-	   secpp = &(*secpp)->next)
-	;
-      bfd_section_list_remove (abfd, secpp);
+      bfd_section_list_remove (abfd, reg_section);
       --abfd->section_count;
     }
 
--- binutils/bfd/elfxx-ia64.c.dbl	2005-05-02 12:25:35.000000000 -0700
+++ binutils/bfd/elfxx-ia64.c	2005-05-02 12:56:26.000000000 -0700
@@ -4923,7 +4923,6 @@ static bfd_boolean
 elfNN_ia64_object_p (bfd *abfd)
 {
   asection *sec;
-  asection **tail;
   asection *group, *unwi, *unw;
   flagword flags;
   const char *name;
@@ -4964,8 +4963,6 @@ elfNN_ia64_object_p (bfd *abfd)
 	  strcpy (stpcpy (unw_name, ".gnu.linkonce.ia64unw."), name);
 	  unw = bfd_get_section_by_name (abfd, unw_name);
 
-	  tail = abfd->section_tail;
-
 	  /* We need to create a fake group section for it and its
 	     unwind sections.  */
 	  group = bfd_make_section_anyway (abfd, name);
@@ -4974,9 +4971,8 @@ elfNN_ia64_object_p (bfd *abfd)
 	    return FALSE;
 
 	  /* Move the fake group section to the beginning.  */
-	  BFD_ASSERT (*tail == group);
-	  bfd_section_list_remove (abfd, tail);
-	  bfd_section_list_insert (abfd, &abfd->sections, group);
+	  bfd_section_list_remove (abfd, group);
+	  bfd_section_list_insert_before (abfd, abfd->sections, group);
 
 	  elf_next_in_group (group) = sec;
 
--- binutils/bfd/elfxx-mips.c.dbl	2005-05-02 12:25:35.000000000 -0700
+++ binutils/bfd/elfxx-mips.c	2005-05-02 13:02:08.000000000 -0700
@@ -8902,7 +8902,6 @@ _bfd_mips_elf_link_hash_table_create (bf
 bfd_boolean
 _bfd_mips_elf_final_link (bfd *abfd, struct bfd_link_info *info)
 {
-  asection **secpp;
   asection *o;
   struct bfd_link_order *p;
   asection *reginfo_sec, *mdebug_sec, *gptab_data_sec, *gptab_bss_sec;
@@ -9319,11 +9318,7 @@ _bfd_mips_elf_final_link (bfd *abfd, str
 	      o->link_order_head = NULL;
 
 	      /* Really remove the section.  */
-	      for (secpp = &abfd->sections;
-		   *secpp != o;
-		   secpp = &(*secpp)->next)
-		;
-	      bfd_section_list_remove (abfd, secpp);
+	      bfd_section_list_remove (abfd, o);
 	      --abfd->section_count;
 
 	      continue;
--- binutils/bfd/opncls.c.dbl	2005-03-13 21:36:48.000000000 -0800
+++ binutils/bfd/opncls.c	2005-05-02 12:25:36.000000000 -0700
@@ -77,7 +77,7 @@ _bfd_new_bfd (void)
       return NULL;
     }
   nbfd->sections = NULL;
-  nbfd->section_tail = &nbfd->sections;
+  nbfd->section_last = NULL;
   nbfd->format = bfd_unknown;
   nbfd->my_archive = NULL;
   nbfd->origin = 0;
--- binutils/bfd/section.c.dbl	2005-05-02 12:25:36.000000000 -0700
+++ binutils/bfd/section.c	2005-05-02 12:32:31.000000000 -0700
@@ -164,6 +164,9 @@ CODE_FRAGMENT
 .  {* The next section in the list belonging to the BFD, or NULL.  *}
 .  struct bfd_section *next;
 .
+.  {* The previous section in the list belonging to the BFD, or NULL.  *}
+.  struct bfd_section *prev;
+.
 .  {* The field flags contains attributes of the section. Some
 .     flags are read in from the object file, and some are
 .     synthesized from other information.  *}
@@ -547,31 +550,73 @@ CODE_FRAGMENT
 .{* Macros to handle insertion and deletion of a bfd's sections.  These
 .   only handle the list pointers, ie. do not adjust section_count,
 .   target_index etc.  *}
-.#define bfd_section_list_remove(ABFD, PS) \
+.#define bfd_section_list_remove(ABFD, S) \
+.  do							\
+.    {							\
+.      asection *_s = S;				\
+.      asection *_next = _s->next;			\
+.      asection *_prev = _s->prev;			\
+.      if (_prev)					\
+.        _prev->next = _next;				\
+.      else						\
+.        (ABFD)->sections = _next;			\
+.      if (_next)					\
+.        {						\
+.          _next->prev = _prev;				\
+.          _s->next = NULL;				\
+.        }						\
+.      else						\
+.        (ABFD)->section_last = _prev;			\
+.    }							\
+.  while (0)
+.#define bfd_section_list_append(ABFD, S) \
 .  do							\
 .    {							\
-.      asection **_ps = PS;				\
-.      asection *_s = *_ps;				\
-.      *_ps = _s->next;					\
-.      if (_s->next == NULL)				\
-.        (ABFD)->section_tail = _ps;			\
+.      asection *_s = S;				\
+.      bfd *_abfd = ABFD;				\
+.      _s->next = NULL;					\
+.      if (_abfd->section_last)				\
+.        {						\
+.          _s->prev = _abfd->section_last;		\
+.          _abfd->section_last->next = _s;		\
+.        }						\
+.      else						\
+.        _abfd->sections = _s;				\
+.      _abfd->section_last = _s;			\
+.    }							\
+.  while (0)
+.#define bfd_section_list_insert_after(ABFD, A, S) \
+.  do							\
+.    {							\
+.      asection *_a = A;				\
+.      asection *_s = S;				\
+.      asection *_next = _a->next;			\
+.      _s->next = _next;				\
+.      _s->prev = _a;					\
+.      _a->next = _s;					\
+.      if (_next)					\
+.        _s->next->prev = _s;				\
 .      else						\
-.        _s->next = NULL;				\
+.        (ABFD)->section_last = _s;			\
 .    }							\
 .  while (0)
-.#define bfd_section_list_insert(ABFD, PS, S) \
+.#define bfd_section_list_insert_before(ABFD, B, S) \
 .  do							\
 .    {							\
-.      asection **_ps = PS;				\
+.      asection *_b = B;				\
 .      asection *_s = S;				\
-.      _s->next = *_ps;					\
-.      *_ps = _s;					\
-.      if (_s->next == NULL)				\
-.        (ABFD)->section_tail = &_s->next;		\
+.      asection *_prev = _b->prev;			\
+.      _s->prev = _prev;				\
+.      _s->next = _b;					\
+.      _b->prev = _s;					\
+.      if (_prev)					\
+.        _prev->next = _s;				\
+.      else						\
+.        (ABFD)->sections = _s;				\
 .    }							\
 .  while (0)
-.#define bfd_section_removed_from_list(ABFD, S)	\
-.  ((S)->next == NULL && &(S)->next != (ABFD)->section_tail)
+.#define bfd_section_removed_from_list(ABFD, S) \
+.  ((S)->next == NULL && (S) != (ABFD)->section_last)
 .
 */
 
@@ -603,8 +648,8 @@ static const asymbol global_syms[] =
 #define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX)				\
   const asymbol * const SYM = (asymbol *) &global_syms[IDX]; 		\
   asection SEC = 							\
-    /* name, id,  index, next, flags, user_set_vma,                  */	\
-    { NAME,  IDX, 0,     NULL, FLAGS, 0,				\
+    /* name, id,  index, next, prev, flags, user_set_vma,            */	\
+    { NAME,  IDX, 0,     NULL, NULL, FLAGS, 0,				\
 									\
     /* linker_mark, linker_has_input, gc_mark, segment_mark,         */	\
        0,           0,                1,       0,			\
@@ -718,8 +763,7 @@ bfd_section_init (bfd *abfd, asection *n
 
   section_id++;
   abfd->section_count++;
-  *abfd->section_tail = newsect;
-  abfd->section_tail = &newsect->next;
+  bfd_section_list_append (abfd, newsect);
   return newsect;
 }
 
@@ -749,7 +793,7 @@ void
 bfd_section_list_clear (bfd *abfd)
 {
   abfd->sections = NULL;
-  abfd->section_tail = &abfd->sections;
+  abfd->section_last = NULL;
   abfd->section_count = 0;
   memset (abfd->section_htab.table, 0,
 	  abfd->section_htab.size * sizeof (struct bfd_hash_entry *));
--- binutils/bfd/sunos.c.dbl	2005-04-11 08:54:43.000000000 -0700
+++ binutils/bfd/sunos.c	2005-05-02 13:29:50.000000000 -0700
@@ -832,7 +832,6 @@ sunos_add_dynamic_symbols (bfd *abfd,
   bfd *dynobj;
   struct sunos_dynamic_info *dinfo;
   unsigned long need;
-  asection **ps;
 
   /* Make sure we have all the required sections.  */
   if (info->hash->creator == abfd->xvec)
@@ -856,12 +855,18 @@ sunos_add_dynamic_symbols (bfd *abfd,
      want, because that one still implies that the section takes up
      space in the output file.  If this is the first object we have
      seen, we must preserve the dynamic sections we just created.  */
-  for (ps = &abfd->sections; *ps != NULL; )
+  if (abfd != dynobj)
+    abfd->sections = NULL;
+  else
     {
-      if (abfd != dynobj || ((*ps)->flags & SEC_LINKER_CREATED) == 0)
-	bfd_section_list_remove (abfd, ps);
-      else
-	ps = &(*ps)->next;
+      asection *s, *n;
+
+      for (s = abfd->sections; s != NULL; s = n)
+	{
+	  n = s->next;
+	  if ((s->flags & SEC_LINKER_CREATED) == 0)
+	    bfd_section_list_remove (abfd, s);
+	}
     }
 
   /* The native linker seems to just ignore dynamic objects when -r is
--- binutils/bfd/xcofflink.c.dbl	2005-04-11 08:54:46.000000000 -0700
+++ binutils/bfd/xcofflink.c	2005-05-02 13:16:57.000000000 -0700
@@ -5454,20 +5454,18 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st
 		    saw_contents = TRUE;
 		  else
 		    {
-		      asection *n, **st;
+		      asection *n;
 
 		      /* Create a pad section and place it before the section
 			 that needs padding.  This requires unlinking and
 			 relinking the bfd's section list.  */
 
-		      st = abfd->section_tail;
 		      n = bfd_make_section_anyway (abfd, ".pad");
 		      n->flags = SEC_HAS_CONTENTS;
 		      n->alignment_power = 0;
 
-		      BFD_ASSERT (*st == n);
-		      bfd_section_list_remove (abfd, st);
-		      bfd_section_list_insert (abfd, op, n);
+		      bfd_section_list_remove (abfd, n);
+		      bfd_section_list_insert_before (abfd, *op, n);
 
 		      op = &n->next;
 		      saw_contents = FALSE;
--- binutils/gas/write.c.dbl	2005-04-27 08:28:38.000000000 -0700
+++ binutils/gas/write.c	2005-05-02 12:34:52.000000000 -0700
@@ -1471,20 +1471,11 @@ write_object_file (void)
 #ifdef BFD_ASSEMBLER
   /* Remove the sections created by gas for its own purposes.  */
   {
-    asection **seclist;
     int i;
 
-    seclist = &stdoutput->sections;
-    while (*seclist)
-      {
-	if (*seclist == reg_section || *seclist == expr_section)
-	  {
-	    bfd_section_list_remove (stdoutput, seclist);
-	    stdoutput->section_count--;
-	  }
-	else
-	  seclist = &(*seclist)->next;
-      }
+    bfd_section_list_remove (stdoutput, reg_section);
+    bfd_section_list_remove (stdoutput, expr_section);
+    stdoutput->section_count -= 2;
     i = 0;
     bfd_map_over_sections (stdoutput, renumber_sections, &i);
   }
--- binutils/ld/emultempl/elf32.em.dbl	2005-05-02 12:25:36.000000000 -0700
+++ binutils/ld/emultempl/elf32.em	2005-05-02 12:37:12.000000000 -0700
@@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section
 	  if (os == abs_output_section || os->constraint == -1)
 	    continue;
 	  s = os->bfd_section;
-	  if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0)
+	  if (s != NULL
+	      && s->size == 0
+	      && (s->flags & SEC_KEEP) == 0
+	      && !bfd_section_removed_from_list (output_bfd, s))
 	    {
-	      asection **p;
-
-	      for (p = &output_bfd->sections; *p; p = &(*p)->next)
-		if (*p == s)
-		  {
-		    bfd_section_list_remove (output_bfd, p);
-		    output_bfd->section_count--;
-		    break;
-		  }
+	      bfd_section_list_remove (output_bfd, s);
+	      output_bfd->section_count--;
 	    }
 	}
     }
--- binutils/ld/ldlang.c.dbl	2005-05-02 12:25:36.000000000 -0700
+++ binutils/ld/ldlang.c	2005-05-02 12:52:52.000000000 -0700
@@ -1273,7 +1273,6 @@ lang_insert_orphan (lang_input_statement
   etree_type *load_base;
   lang_output_section_statement_type *os;
   lang_output_section_statement_type **os_tail;
-  asection **bfd_tail;
 
   /* Start building a list of statements for this section.
      First save the current statement pointer.  */
@@ -1327,7 +1326,6 @@ lang_insert_orphan (lang_input_statement
 
   os_tail = ((lang_output_section_statement_type **)
 	     lang_output_section_statement.tail);
-  bfd_tail = output_bfd->section_tail;
   os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL,
 					    load_base, 0);
 
@@ -1359,7 +1357,7 @@ lang_insert_orphan (lang_input_statement
 
   if (after != NULL && os->bfd_section != NULL)
     {
-      asection *snew;
+      asection *snew, *as;
 
       snew = os->bfd_section;
 
@@ -1385,12 +1383,15 @@ lang_insert_orphan (lang_input_statement
       if (place->section == NULL)
 	place->section = &output_bfd->sections;
 
-      /* Unlink the section.  */
-      ASSERT (*bfd_tail == snew);
-      bfd_section_list_remove (output_bfd, bfd_tail);
+      as = *place->section;
+      if (as != snew && as->prev != snew)
+	{
+	  /* Unlink the section.  */
+	  bfd_section_list_remove (output_bfd, snew);
 
-      /* Now tack it back on in the right place.  */
-      bfd_section_list_insert (output_bfd, place->section, snew);
+	  /* Now tack it back on in the right place.  */
+	  bfd_section_list_insert_before (output_bfd, as, snew);
+	}
 
       /* Save the end of this list.  Further ophans of this type will
 	 follow the one we've just added.  */
@@ -3119,8 +3120,6 @@ strip_excluded_or_unused_output_sections
 		  && s->linker_has_input == 0
 		  && (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0)))
 	{
-	  asection **p;
-
 	  /* We don't set bfd_section to NULL since bfd_section of 
 	     the used output section may still be used.  */
 	  if (unused)
@@ -3128,13 +3127,11 @@ strip_excluded_or_unused_output_sections
 	  else
 	    os->bfd_section = NULL;
 
-	  for (p = &output_bfd->sections; *p; p = &(*p)->next)
-	    if (*p == s)
-	      {
-		bfd_section_list_remove (output_bfd, p);
-		output_bfd->section_count--;
-		break;
-	      }
+	 if (!bfd_section_removed_from_list (output_bfd, s))
+	   {
+	     bfd_section_list_remove (output_bfd, s);
+	     output_bfd->section_count--;
+	   }
 	}
     }
 }
@@ -3763,6 +3760,22 @@ size_input_section
   return dot;
 }
 
+static int
+sort_sections_by_lma (const void *arg1, const void *arg2)
+{
+  const asection *sec1 = *(const asection **) arg1;
+  const asection *sec2 = *(const asection **) arg2;
+
+  if (bfd_section_lma (sec1->owner, sec1)
+      < bfd_section_lma (sec2->owner, sec2))
+    return -1;
+  else if (bfd_section_lma (sec1->owner, sec1)
+	   > bfd_section_lma (sec2->owner, sec2))
+    return 1;
+
+  return 0;
+}
+
 #define IGNORE_SECTION(s) \
   ((s->flags & SEC_NEVER_LOAD) != 0				\
    || (s->flags & SEC_ALLOC) == 0				\
@@ -3776,52 +3789,62 @@ size_input_section
 static void
 lang_check_section_addresses (void)
 {
-  asection *s;
+  asection *s, *os;
+  asection **sections, **spp;
+  unsigned int count;
+  bfd_vma s_start;
+  bfd_vma s_end;
+  bfd_vma os_start;
+  bfd_vma os_end;
+  bfd_size_type amt;
+
+  if (bfd_count_sections (output_bfd) <= 1)
+    return;
+
+  amt = bfd_count_sections (output_bfd) * sizeof (asection *);
+  sections = xmalloc (amt);
 
   /* Scan all sections in the output list.  */
+  count = 0;
   for (s = output_bfd->sections; s != NULL; s = s->next)
     {
-      asection *os;
-
-      /* Ignore sections which are not loaded or which have no contents.  */
+      /* Only consider loadable sections with real contents.  */
       if (IGNORE_SECTION (s) || s->size == 0)
 	continue;
 
-      /* Once we reach section 's' stop our seach.  This prevents two
-	 warning messages from being produced, one for 'section A overlaps
-	 section B' and one for 'section B overlaps section A'.  */
-      for (os = output_bfd->sections; os != s; os = os->next)
-	{
-	  bfd_vma s_start;
-	  bfd_vma s_end;
-	  bfd_vma os_start;
-	  bfd_vma os_end;
-
-	  /* Only consider loadable sections with real contents.  */
-	  if (IGNORE_SECTION (os) || os->size == 0)
-	    continue;
-
-	  /* We must check the sections' LMA addresses not their
-	     VMA addresses because overlay sections can have
-	     overlapping VMAs but they must have distinct LMAs.  */
-	  s_start = bfd_section_lma (output_bfd, s);
-	  os_start = bfd_section_lma (output_bfd, os);
-	  s_end = s_start + TO_ADDR (s->size) - 1;
-	  os_end = os_start + TO_ADDR (os->size) - 1;
-
-	  /* Look for an overlap.  */
-	  if ((s_end < os_start) || (s_start > os_end))
-	    continue;
+      sections[count] = s;
+      count++;
+    }
+  
+  if (count <= 1)
+    return;
 
-	  einfo (
-_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
-		 s->name, s_start, s_end, os->name, os_start, os_end);
+  qsort (sections, (size_t) count, sizeof (asection *),
+	 sort_sections_by_lma);
 
-	  /* Once we have found one overlap for this section,
-	     stop looking for others.  */
-	  break;
-	}
+  spp = sections;
+  s = *spp++;
+  s_start = bfd_section_lma (output_bfd, s);
+  s_end = s_start + TO_ADDR (s->size) - 1;
+  for (count--; count; count--)
+    {
+      /* We must check the sections' LMA addresses not their VMA
+	 addresses because overlay sections can have overlapping VMAs
+	 but they must have distinct LMAs.  */
+      os = s;
+      os_start = s_start; 
+      os_end = s_end;
+      s = *spp++;
+      s_start = bfd_section_lma (output_bfd, s);
+      s_end = s_start + TO_ADDR (s->size) - 1;
+
+      /* Look for an overlap.  */
+      if (s_end >= os_start && s_start <= os_end)
+	einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
+	       s->name, s_start, s_end, os->name, os_start, os_end);
     }
+
+  free (sections);
 }
 
 /* Make sure the new address is within the region.  We explicitly permit the


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]