Sort relocs output by ld -r

bfd/
	PR 17666
	* elflink.c: Include bfd_stdint.h.
	(cmp_ext32l_r_offset, cmp_ext32b_r_offset,
	cmp_ext64l_r_offset, cmp_ext64b_r_offset): New functions.
	(elf_link_adjust_relocs): Sort relocs.  Free reloc hashes after
	sorting invalidates.
ld/testsuite/
	* ld-powerpc/vxworks-relax.rd: Update for reloc sorting.
	* ld-powerpc/vxworks-relax-2.rd: Likewise.
	* ld-sh/sh64/reldl32.rd: Likewise.
	* ld-sh/sh64/reldl64.rd: Likewise.

7 files changed, 182 insertions, 8 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 65c7243..5144eb6 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,12 @@
+2014-12-04  Alan Modra  <amodra@gmail.com>
+
+	PR 17666
+	* elflink.c: Include bfd_stdint.h.
+	(cmp_ext32l_r_offset, cmp_ext32b_r_offset,
+	cmp_ext64l_r_offset, cmp_ext64b_r_offset): New functions.
+	(elf_link_adjust_relocs): Sort relocs.  Free rel hashes after
+	sorting invalidates.
+
 2014-12-03  Nick Clifton  <nickc@redhat.com>
 
 	PR binutils/17512
diff --git a/bfd/elflink.c b/bfd/elflink.c
index c964a98..e768634 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -20,6 +20,7 @@
 
 #include "sysdep.h"
 #include "bfd.h"
+#include "bfd_stdint.h"
 #include "bfdlink.h"
 #include "libbfd.h"
 #define ARCH_SIZE 0
@@ -7957,6 +7958,138 @@ bfd_elf_perform_complex_relocation (bfd *input_bfd,
   return r;
 }
 
+/* qsort comparison functions sorting external relocs by r_offset.  */
+
+static int
+cmp_ext32l_r_offset (const void *p, const void *q)
+{
+  union aligned32
+  {
+    uint32_t v;
+    unsigned char c[4];
+  };
+  const union aligned32 *a
+    = (const union aligned32 *) ((const Elf32_External_Rel *) p)->r_offset;
+  const union aligned32 *b
+    = (const union aligned32 *) ((const Elf32_External_Rel *) q)->r_offset;
+
+  uint32_t aval = (  (uint32_t) a->c[0]
+		   | (uint32_t) a->c[1] << 8
+		   | (uint32_t) a->c[2] << 16
+		   | (uint32_t) a->c[3] << 24);
+  uint32_t bval = (  (uint32_t) b->c[0]
+		   | (uint32_t) b->c[1] << 8
+		   | (uint32_t) b->c[2] << 16
+		   | (uint32_t) b->c[3] << 24);
+  if (aval < bval)
+    return -1;
+  else if (aval > bval)
+    return 1;
+  return 0;
+}
+
+static int
+cmp_ext32b_r_offset (const void *p, const void *q)
+{
+  union aligned32
+  {
+    uint32_t v;
+    unsigned char c[4];
+  };
+  const union aligned32 *a
+    = (const union aligned32 *) ((const Elf32_External_Rel *) p)->r_offset;
+  const union aligned32 *b
+    = (const union aligned32 *) ((const Elf32_External_Rel *) q)->r_offset;
+
+  uint32_t aval = (  (uint32_t) a->c[0] << 24
+		   | (uint32_t) a->c[1] << 16
+		   | (uint32_t) a->c[2] << 8
+		   | (uint32_t) a->c[3]);
+  uint32_t bval = (  (uint32_t) b->c[0] << 24
+		   | (uint32_t) b->c[1] << 16
+		   | (uint32_t) b->c[2] << 8
+		   | (uint32_t) b->c[3]);
+  if (aval < bval)
+    return -1;
+  else if (aval > bval)
+    return 1;
+  return 0;
+}
+
+#ifdef BFD_HOST_64_BIT
+static int
+cmp_ext64l_r_offset (const void *p, const void *q)
+{
+  union aligned64
+  {
+    uint64_t v;
+    unsigned char c[8];
+  };
+  const union aligned64 *a
+    = (const union aligned64 *) ((const Elf64_External_Rel *) p)->r_offset;
+  const union aligned64 *b
+    = (const union aligned64 *) ((const Elf64_External_Rel *) q)->r_offset;
+
+  uint64_t aval = (  (uint64_t) a->c[0]
+		   | (uint64_t) a->c[1] << 8
+		   | (uint64_t) a->c[2] << 16
+		   | (uint64_t) a->c[3] << 24
+		   | (uint64_t) a->c[4] << 32
+		   | (uint64_t) a->c[5] << 40
+		   | (uint64_t) a->c[6] << 48
+		   | (uint64_t) a->c[7] << 56);
+  uint64_t bval = (  (uint64_t) b->c[0]
+		   | (uint64_t) b->c[1] << 8
+		   | (uint64_t) b->c[2] << 16
+		   | (uint64_t) b->c[3] << 24
+		   | (uint64_t) b->c[4] << 32
+		   | (uint64_t) b->c[5] << 40
+		   | (uint64_t) b->c[6] << 48
+		   | (uint64_t) b->c[7] << 56);
+  if (aval < bval)
+    return -1;
+  else if (aval > bval)
+    return 1;
+  return 0;
+}
+
+static int
+cmp_ext64b_r_offset (const void *p, const void *q)
+{
+  union aligned64
+  {
+    uint64_t v;
+    unsigned char c[8];
+  };
+  const union aligned64 *a
+    = (const union aligned64 *) ((const Elf64_External_Rel *) p)->r_offset;
+  const union aligned64 *b
+    = (const union aligned64 *) ((const Elf64_External_Rel *) q)->r_offset;
+
+  uint64_t aval = (  (uint64_t) a->c[0] << 56
+		   | (uint64_t) a->c[1] << 48
+		   | (uint64_t) a->c[2] << 40
+		   | (uint64_t) a->c[3] << 32
+		   | (uint64_t) a->c[4] << 24
+		   | (uint64_t) a->c[5] << 16
+		   | (uint64_t) a->c[6] << 8
+		   | (uint64_t) a->c[7]);
+  uint64_t bval = (  (uint64_t) b->c[0] << 56
+		   | (uint64_t) b->c[1] << 48
+		   | (uint64_t) b->c[2] << 40
+		   | (uint64_t) b->c[3] << 32
+		   | (uint64_t) b->c[4] << 24
+		   | (uint64_t) b->c[5] << 16
+		   | (uint64_t) b->c[6] << 8
+		   | (uint64_t) b->c[7]);
+  if (aval < bval)
+    return -1;
+  else if (aval > bval)
+    return 1;
+  return 0;
+}
+#endif
+
 /* When performing a relocatable link, the input relocations are
    preserved.  But, if they reference global symbols, the indices
    referenced must be updated.  Update all the relocations found in
@@ -7975,6 +8108,7 @@ elf_link_adjust_relocs (bfd *abfd,
   int r_sym_shift;
   unsigned int count = reldata->count;
   struct elf_link_hash_entry **rel_hash = reldata->hashes;
+  int (*compare) (const void *, const void *);
 
   if (reldata->hdr->sh_entsize == bed->s->sizeof_rel)
     {
@@ -8020,6 +8154,30 @@ elf_link_adjust_relocs (bfd *abfd,
 			   | (irela[j].r_info & r_type_mask));
       (*swap_out) (abfd, irela, erela);
     }
+
+  if (bed->s->arch_size == 32)
+    {
+      if (abfd->xvec->header_byteorder == BFD_ENDIAN_LITTLE)
+	compare = cmp_ext32l_r_offset;
+      else if (abfd->xvec->header_byteorder == BFD_ENDIAN_BIG)
+	compare = cmp_ext32b_r_offset;
+      else
+	abort ();
+    }
+  else
+    {
+#ifdef BFD_HOST_64_BIT
+      if (abfd->xvec->header_byteorder == BFD_ENDIAN_LITTLE)
+	compare = cmp_ext64l_r_offset;
+      else if (abfd->xvec->header_byteorder == BFD_ENDIAN_BIG)
+	compare = cmp_ext64b_r_offset;
+      else
+#endif
+	abort ();
+    }
+  qsort (reldata->hdr->contents, count, reldata->hdr->sh_entsize, compare);
+  free (reldata->hashes);
+  reldata->hashes = NULL;
 }
 
 struct elf_link_sort_rela
diff --git a/ld/testsuite/ChangeLog b/ld/testsuite/ChangeLog
index 2a06fa0..8ebe2fb 100644
--- a/ld/testsuite/ChangeLog
+++ b/ld/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2014-12-04  Alan Modra  <amodra@gmail.com>
+
+	* ld-powerpc/vxworks-relax.rd: Update for reloc sorting.
+	* ld-powerpc/vxworks-relax-2.rd: Likewise.
+	* ld-sh/sh64/reldl32.rd: Likewise.
+	* ld-sh/sh64/reldl64.rd: Likewise.
+
 2014-12-03  H.J. Lu  <hongjiu.lu@intel.com>
 
 	* ld-x86-64/copyreloc-main.c: Removed.
diff --git a/ld/testsuite/ld-powerpc/vxworks-relax-2.rd b/ld/testsuite/ld-powerpc/vxworks-relax-2.rd
index 4d36109..8d8d39c 100644
--- a/ld/testsuite/ld-powerpc/vxworks-relax-2.rd
+++ b/ld/testsuite/ld-powerpc/vxworks-relax-2.rd
@@ -1,10 +1,10 @@
 
 Relocation section '.rela.text' at offset 0x[0-9a-f]+ contains 8 entries:
  Offset +Info +Type +Sym.Value +Sym. Name \+ Addend
-0+16 +[0-9a-f]+ R_PPC_ADDR16_HA +0+ +.text \+ 4000034
-0+1a +[0-9a-f]+ R_PPC_ADDR16_LO +0+ +.text \+ 4000034
 0+6 +[0-9a-f]+ R_PPC_ADDR16_HA +0+ +.text \+ 4000034
 0+a +[0-9a-f]+ R_PPC_ADDR16_LO +0+ +.text \+ 4000034
+0+16 +[0-9a-f]+ R_PPC_ADDR16_HA +0+ +.text \+ 4000034
+0+1a +[0-9a-f]+ R_PPC_ADDR16_LO +0+ +.text \+ 4000034
 0+26 +[0-9a-f]+ R_PPC_ADDR16_HA +0+ +undefined \+ 0
 0+2a +[0-9a-f]+ R_PPC_ADDR16_LO +0+ +undefined \+ 0
 0+400003e +[0-9a-f]+ R_PPC_ADDR16_HA +0+ +_start \+ 0
diff --git a/ld/testsuite/ld-powerpc/vxworks-relax.rd b/ld/testsuite/ld-powerpc/vxworks-relax.rd
index 572c74d..a72308b 100644
--- a/ld/testsuite/ld-powerpc/vxworks-relax.rd
+++ b/ld/testsuite/ld-powerpc/vxworks-relax.rd
@@ -1,9 +1,9 @@
 
 Relocation section '.rela.text' at offset .* contains 6 entries:
  Offset     Info    Type            Sym.Value  Sym. Name \+ Addend
-00080012  .* R_PPC_ADDR16_HA   00080000   .text \+ 4000020
-00080016  .* R_PPC_ADDR16_LO   00080000   .text \+ 4000020
 00080006  .* R_PPC_ADDR16_HA   00080000   .text \+ 4000020
 0008000a  .* R_PPC_ADDR16_LO   00080000   .text \+ 4000020
+00080012  .* R_PPC_ADDR16_HA   00080000   .text \+ 4000020
+00080016  .* R_PPC_ADDR16_LO   00080000   .text \+ 4000020
 0408002a  .* R_PPC_ADDR16_HA   00080000   _start \+ 0
 0408002e  .* R_PPC_ADDR16_LO   00080000   _start \+ 0
diff --git a/ld/testsuite/ld-sh/sh64/reldl32.rd b/ld/testsuite/ld-sh/sh64/reldl32.rd
index 400e2af..a276d7c 100644
--- a/ld/testsuite/ld-sh/sh64/reldl32.rd
+++ b/ld/testsuite/ld-sh/sh64/reldl32.rd
@@ -12,10 +12,10 @@ Relocation section '\.rela\.text' at offset 0x[0-9a-f]+ contains 26 entries:
 00000028 +0+21f6 R_SH_IMM_LOW16 +00000000 +file1text5 +\+ 8
 0000002c +0+2df6 R_SH_IMM_LOW16 +0000000c +file1data2 +\+ 30
 00000030 +0+2df6 R_SH_IMM_LOW16 +0000000c +file1data2 +\+ 0
-0000003c +0+42f6 R_SH_IMM_LOW16 +00000000 +unresolved7 +\+ 0
-00000040 +0+27f6 R_SH_IMM_LOW16 +00000000 +unresolved1 +\+ 0
 00000034 +0+35f8 R_SH_IMM_MEDLOW16 +00000000 +file2data4 +\+ 10
 00000038 +0+35f6 R_SH_IMM_LOW16 +00000000 +file2data4 +\+ 10
+0000003c +0+42f6 R_SH_IMM_LOW16 +00000000 +unresolved7 +\+ 0
+00000040 +0+27f6 R_SH_IMM_LOW16 +00000000 +unresolved1 +\+ 0
 00000068 +0+08f6 R_SH_IMM_LOW16 +00000064 +file2text1 +\+ 0
 0000006c +0+24f6 R_SH_IMM_LOW16 +00000124 +file2data2 +\+ 0
 00000070 +0+23f6 R_SH_IMM_LOW16 +00000010 +file1text3 +\+ 0
diff --git a/ld/testsuite/ld-sh/sh64/reldl64.rd b/ld/testsuite/ld-sh/sh64/reldl64.rd
index 8bd5502..71b984c 100644
--- a/ld/testsuite/ld-sh/sh64/reldl64.rd
+++ b/ld/testsuite/ld-sh/sh64/reldl64.rd
@@ -12,12 +12,12 @@ Relocation section '\.rela\.text' at offset 0x[0-9a-f]+ contains 28 entries:
 0+28 +0+21000000f6 R_SH_IMM_LOW16[ ]+0+ +file1text5[ ]+\+ 8
 0+2c +0+2d000000f6 R_SH_IMM_LOW16[ ]+0+c +file1data2[ ]+\+ 30
 0+30 +0+2d000000f6 R_SH_IMM_LOW16[ ]+0+c +file1data2[ ]+\+ 0
-0+44 +0+42000000f6 R_SH_IMM_LOW16[ ]+0+ +unresolved7[ ]+\+ 0
-0+48 +0+27000000f6 R_SH_IMM_LOW16[ ]+0+ +unresolved1[ ]+\+ 0
 0+34 +0+35000000fc R_SH_IMM_HI16[ ]+0+ +file2data4[ ]+\+ 10
 0+38 +0+35000000fa R_SH_IMM_MEDHI16[ ]+0+ +file2data4[ ]+\+ 10
 0+3c +0+35000000f8 R_SH_IMM_MEDLOW16[ ]+0+ +file2data4[ ]+\+ 10
 0+40 +0+35000000f6 R_SH_IMM_LOW16[ ]+0+ +file2data4[ ]+\+ 10
+0+44 +0+42000000f6 R_SH_IMM_LOW16[ ]+0+ +unresolved7[ ]+\+ 0
+0+48 +0+27000000f6 R_SH_IMM_LOW16[ ]+0+ +unresolved1[ ]+\+ 0
 0+70 +0+08000000f6 R_SH_IMM_LOW16[ ]+0+6c +file2text1[ ]+\+ 0
 0+74 +0+24000000f6 R_SH_IMM_LOW16[ ]+0+124 +file2data2[ ]+\+ 0
 0+78 +0+23000000f6 R_SH_IMM_LOW16[ ]+0+10 +file1text3[ ]+\+ 0