Re: Use stable sort for ld -r relocs

[Alan Modra <amodra at gmail dot com>]

On Wed, Aug 26, 2015 at 06:04:41PM -0400, Mike Frysinger wrote:
> On 26 Aug 2015 23:32, Alan Modra wrote:
> > A number of targets emit multiple relocs at a given r_offset, and
> > depend on those relocs staying in their original order.  qsort doesn't
> > satisfy this requirement, although it appears from my non-rigorous
> > testing that glibc's msort.c implementation may in fact be stable.
> > 
> > I made the mistake of backporting my PR 17666 fix to 2.25.1, thinking
> > the code had enough time to settle on mainline, but for anyone with a
> > system libc that provides an unstable qsort this will mean 2.25.1
> > ld -r may be broken on some targets.
> > 
> > 	PR 18867
> > 	* elflink.c (cmp_ext32l_r_offset, cmp_ext32b_r_offset): Delete.
> > 	(cmp_ext64l_r_offset, cmp_ext64b_r_offset): Delete.
> > 	(ext32l_r_offset, ext32b_r_offset, ext64l_r_offset, ext64b_r_offset):
> > 	New functions.
> > 	(elf_link_adjust_relocs): Use an insertion sort to sort relocs.
> 
> were you planning on making another change ?  i tested master
> (1dc7a6235090327d7b5586f85e6115c3cd13ed83) and it still crashes
> on alpha.  this hack makes things work:
> --- a/bfd/elflink.c
> +++ b/bfd/elflink.c
> ...
> -      sort = bed->sort_relocs_p == NULL || (*bed->sort_relocs_p) (o);
> +      sort = 0; //bed->sort_relocs_p == NULL || (*bed->sort_relocs_p) (o);

Yes, I'm going to turn off reloc sorting on alpha.  glibc uses ld -r
when building startup files, libc.so and ld.so, and I see libc.so is
quite different with reloc sorting.  For starters, you get more
dynamic relocs and fewer plt entries.  I haven't fully analysed why
this happens, but I see code like the following in bfd/elf64-alpha.c
	case R_ALPHA_LITERAL:
	  need = NEED_GOT | NEED_GOT_ENTRY;

	  /* Remember how this literal is used from its LITUSEs.
	     This will be important when it comes to decide if we can
	     create a .plt entry for a function symbol.  */
	  while (++rel < relend && ELF64_R_TYPE (rel->r_info) == R_ALPHA_LITUSE)
	    if (rel->r_addend >= 1 && rel->r_addend <= 6)
	      gotent_flags |= 1 << rel->r_addend;
	  --rel;
ie. a LITUSE must immediately follow a LITERAL.

Here's a group of relocations from libc_pic.os
00000050 0000129300000011 R_ALPHA_GPRELHIGH  00002a80 __libc_argc + 0
00000054 00000e6500000004 R_ALPHA_LITERAL    000e9570 __init_misc + 0
00000078 0000000200000005 R_ALPHA_LITUSE     (JSR)
0000005c 0000129300000012 R_ALPHA_GPRELLOW   00002a80 __libc_argc + 0
00000060 000011a800000011 R_ALPHA_GPRELHIGH  00002a78 __libc_argv + 0
00000068 000011a800000012 R_ALPHA_GPRELLOW   00002a78 __libc_argv + 0
00000070 000010b600000004 R_ALPHA_LITERAL    00000508 __environ + 0
00000078 00000e6500000008 R_ALPHA_HINT       000e9570 __init_misc + 0

The same group with sorting enabled:
00000050 0000129300000011 R_ALPHA_GPRELHIGH  00002a80 __libc_argc + 0
00000054 00000e6500000004 R_ALPHA_LITERAL    000e9570 __init_misc + 0
0000005c 0000129300000012 R_ALPHA_GPRELLOW   00002a80 __libc_argc + 0
00000060 000011a800000011 R_ALPHA_GPRELHIGH  00002a78 __libc_argv + 0
00000068 000011a800000012 R_ALPHA_GPRELLOW   00002a78 __libc_argv + 0
00000070 000010b600000004 R_ALPHA_LITERAL    00000508 __environ + 0
00000078 0000000200000005 R_ALPHA_LITUSE     (JSR)
00000078 00000e6500000008 R_ALPHA_HINT       000e9570 __init_misc + 0

As you can see, the LITUSE is sorted away from the LITERAL.

	* elf64-alpha.c (elf64_alpha_sort_relocs_p): New function.
	(elf_backend_sort_relocs_p): Define.

diff --git a/bfd/elf64-alpha.c b/bfd/elf64-alpha.c
index df19da7..35c1ec6 100644
--- a/bfd/elf64-alpha.c
+++ b/bfd/elf64-alpha.c
@@ -1757,6 +1757,18 @@ elf64_alpha_want_plt (struct alpha_elf_link_hash_entry *ah)
 	  && (ah->flags & ~ALPHA_ELF_LINK_HASH_LU_PLT) == 0);
 }
 
+/* Whether to sort relocs output by ld -r or ld --emit-relocs, by r_offset.
+   Don't do so for code sections.  We want to keep ordering of LITERAL/LITUSE
+   as is.  On the other hand, elf-eh-frame.c processing requires .eh_frame
+   relocs to be sorted.  */
+
+static bfd_boolean
+elf64_alpha_sort_relocs_p (asection *sec)
+{
+  return (sec->flags & SEC_CODE) == 0;
+}
+
+
 /* Handle dynamic relocations when doing an Alpha ELF link.  */
 
 static bfd_boolean
@@ -5525,6 +5537,8 @@ static const struct elf_size_info alpha_elf_size_info =
   elf64_alpha_add_symbol_hook
 #define elf_backend_relocs_compatible \
   _bfd_elf_relocs_compatible
+#define elf_backend_sort_relocs_p \
+  elf64_alpha_sort_relocs_p
 #define elf_backend_check_relocs \
   elf64_alpha_check_relocs
 #define elf_backend_create_dynamic_sections \

-- 
Alan Modra
Australia Development Lab, IBM