Fix slowdown in ld -r for most common case of out-of-order relocs

I chose insertion sort since relocs are mostly sorted, but there is a
common case we can handle better;  A run of relocs put out of order
due to not linking input files in order.

	PR 18867
	* elflink.c (elf_link_adjust_relocs): Modify insertion sort to
	insert a run.  Return status in case of malloc failure.
	Adjust callers.

2 files changed, 58 insertions, 15 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index fb809a3..a99c2e0 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,10 @@
+2015-09-16  Alan Modra  <amodra@gmail.com>
+
+	PR 18867
+	* elflink.c (elf_link_adjust_relocs): Modify insertion sort to
+	insert a run.  Return status in case of malloc failure.
+	Adjust callers.
+
 2015-09-15  Max Filippov  <jcmvbkbc@gmail.com>
 
 	* elf32-xtensa.c (elf_xtensa_be_plt_entry)
diff --git a/bfd/elflink.c b/bfd/elflink.c
index 4f86700..8659099 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -8193,7 +8193,7 @@ ext64b_r_offset (const void *p)
    referenced must be updated.  Update all the relocations found in
    RELDATA.  */
 
-static void
+static bfd_boolean
 elf_link_adjust_relocs (bfd *abfd,
 			struct bfd_elf_section_reloc_data *reldata,
 			bfd_boolean sort)
@@ -8259,7 +8259,7 @@ elf_link_adjust_relocs (bfd *abfd,
       bfd_vma r_off;
       size_t elt_size;
       bfd_byte *base, *end, *p, *loc;
-      bfd_byte buf[sizeof (Elf64_External_Rela)];
+      bfd_byte *buf = NULL;
 
       if (bed->s->arch_size == 32)
 	{
@@ -8282,12 +8282,12 @@ elf_link_adjust_relocs (bfd *abfd,
 	    abort ();
 	}
 
-      /*  Must use a stable sort here.  Insertion sort, since the
-	  relocs are mostly sorted already.  */
+      /*  Must use a stable sort here.  A modified insertion sort,
+	  since the relocs are mostly sorted already.  */
       elt_size = reldata->hdr->sh_entsize;
       base = reldata->hdr->contents;
       end = base + count * elt_size;
-      if (elt_size > sizeof (buf))
+      if (elt_size > sizeof (Elf64_External_Rela))
 	abort ();
 
       /* Ensure the first element is lowest.  This acts as a sentinel,
@@ -8307,12 +8307,13 @@ elf_link_adjust_relocs (bfd *abfd,
 	  /* Don't just swap *base and *loc as that changes the order
 	     of the original base[0] and base[1] if they happen to
 	     have the same r_offset.  */
-	  memcpy (buf, loc, elt_size);
+	  bfd_byte onebuf[sizeof (Elf64_External_Rela)];
+	  memcpy (onebuf, loc, elt_size);
 	  memmove (base + elt_size, base, loc - base);
-	  memcpy (base, buf, elt_size);
+	  memcpy (base, onebuf, elt_size);
 	}
 
-      for (p = base + elt_size; (p += elt_size) < end; )
+      for (p = base + elt_size; p < end; )
 	{
 	  /* base to p is sorted, *p is next to insert.  */
 	  r_off = (*ext_r_off) (p);
@@ -8323,15 +8324,48 @@ elf_link_adjust_relocs (bfd *abfd,
 	  loc += elt_size;
 	  if (loc != p)
 	    {
-	      memcpy (buf, p, elt_size);
-	      memmove (loc + elt_size, loc, p - loc);
-	      memcpy (loc, buf, elt_size);
+	      /* Chances are there is a run of relocs to insert here,
+		 from one of more input files.  Files are not always
+		 linked in order due to the way elf_link_input_bfd is
+		 called.  See pr17666.  */
+	      size_t sortlen = p - loc;
+	      bfd_vma r_off2 = (*ext_r_off) (loc);
+	      size_t runlen = elt_size;
+	      size_t buf_size = 96 * 1024;
+	      while (p + runlen < end
+		     && (sortlen <= buf_size
+			 || runlen + elt_size <= buf_size)
+		     && r_off2 > (*ext_r_off) (p + runlen))
+		runlen += elt_size;
+	      if (buf == NULL)
+		{
+		  buf = bfd_malloc (buf_size);
+		  if (buf == NULL)
+		    return FALSE;
+		}
+	      if (runlen < sortlen)
+		{
+		  memcpy (buf, p, runlen);
+		  memmove (loc + runlen, loc, sortlen);
+		  memcpy (loc, buf, runlen);
+		}
+	      else
+		{
+		  memcpy (buf, loc, sortlen);
+		  memmove (loc, p, runlen);
+		  memcpy (loc + runlen, buf, sortlen);
+		}
+	      p += runlen;
 	    }
+	  else
+	    p += elt_size;
 	}
       /* Hashes are no longer valid.  */
       free (reldata->hashes);
       reldata->hashes = NULL;
+      free (buf);
     }
+  return TRUE;
 }
 
 struct elf_link_sort_rela
@@ -11577,10 +11611,12 @@ bfd_elf_final_link (bfd *abfd, struct bfd_link_info *info)
 	continue;
 
       sort = bed->sort_relocs_p == NULL || (*bed->sort_relocs_p) (o);
-      if (esdo->rel.hdr != NULL)
-	elf_link_adjust_relocs (abfd, &esdo->rel, sort);
-      if (esdo->rela.hdr != NULL)
-	elf_link_adjust_relocs (abfd, &esdo->rela, sort);
+      if (esdo->rel.hdr != NULL
+	  && !elf_link_adjust_relocs (abfd, &esdo->rel, sort))
+	return FALSE;
+      if (esdo->rela.hdr != NULL
+	  && !elf_link_adjust_relocs (abfd, &esdo->rela, sort))
+	return FALSE;
 
       /* Set the reloc_count field to 0 to prevent write_relocs from
 	 trying to swap the relocs out itself.  */