qsort: elf_link_add_object_symbols weak aliases

This particular sort almost certainly does not need to be stable for
the ELF linker to work correctly.  However it is conceivable that an
unstable sort could affect linker output, and thus different output be
seen with differing qsort implementations.  The argument goes like
this:  Given more than one strong alias symbol of equal section, value,
and size, the aliases will compare equal by elf_sort_symbol and thus
which one is chosen as the "real" symbol to be made dynamic depends on
qsort.  Why would anyone define two symbols at the same address?
Well, sometimes the fact that there are more than one strong alias
symbol is due to linker script symbols like __bss_start being made
dynamic.  This will match the first symbol defined in .bss if it
doesn't have correct size, and forgetting to properly set size and
type of symbols isn't as rare as it should be.

This patch adds some more heuristics to elf_sort_symbol.

	* elflink.c (elf_sort_symbol): Sort on type and name as well.
	(elf_link_add_object_symbols): Style fix.

2 files changed, 49 insertions, 12 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 6a5f673..bb6c907 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,5 +1,10 @@
 2019-10-14  Alan Modra  <amodra@gmail.com>
 
+	* elflink.c (elf_sort_symbol): Sort on type and name as well.
+	(elf_link_add_object_symbols): Style fix.
+
+2019-10-14  Alan Modra  <amodra@gmail.com>
+
 	* elf.c (_bfd_elf_map_sections_to_segments): Init target_index
 	for sections about to be sorted.
 	(assign_file_positions_for_load_sections): Likewise.
diff --git a/bfd/elflink.c b/bfd/elflink.c
index bfd0f01..9d7f69a 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -3587,27 +3587,60 @@ on_needed_list (const char *soname,
   return FALSE;
 }
 
-/* Sort symbol by value, section, and size.  */
+/* Sort symbol by value, section, size, and type.  */
 static int
 elf_sort_symbol (const void *arg1, const void *arg2)
 {
   const struct elf_link_hash_entry *h1;
   const struct elf_link_hash_entry *h2;
   bfd_signed_vma vdiff;
+  int sdiff;
+  const char *n1;
+  const char *n2;
 
   h1 = *(const struct elf_link_hash_entry **) arg1;
   h2 = *(const struct elf_link_hash_entry **) arg2;
   vdiff = h1->root.u.def.value - h2->root.u.def.value;
   if (vdiff != 0)
     return vdiff > 0 ? 1 : -1;
-  else
-    {
-      int sdiff = h1->root.u.def.section->id - h2->root.u.def.section->id;
-      if (sdiff != 0)
-	return sdiff > 0 ? 1 : -1;
-    }
+
+  sdiff = h1->root.u.def.section->id - h2->root.u.def.section->id;
+  if (sdiff != 0)
+    return sdiff;
+
+  /* Sort so that sized symbols are selected over zero size symbols.  */
   vdiff = h1->size - h2->size;
-  return vdiff == 0 ? 0 : vdiff > 0 ? 1 : -1;
+  if (vdiff != 0)
+    return vdiff > 0 ? 1 : -1;
+
+  /* Sort so that STT_OBJECT is selected over STT_NOTYPE.  */
+  if (h1->type != h2->type)
+    return h1->type - h2->type;
+
+  /* If symbols are properly sized and typed, and multiple strong
+     aliases are not defined in a shared library by the user we
+     shouldn't get here.  Unfortunately linker script symbols like
+     __bss_start sometimes match a user symbol defined at the start of
+     .bss without proper size and type.  We'd like to preference the
+     user symbol over reserved system symbols.  Sort on leading
+     underscores.  */
+  n1 = h1->root.root.string;
+  n2 = h2->root.root.string;
+  while (*n1 == *n2)
+    {
+      if (*n1 == 0)
+	break;
+      ++n1;
+      ++n2;
+    }
+  if (*n1 == '_')
+    return -1;
+  if (*n2 == '_')
+    return 1;
+
+  /* Final sort on name selects user symbols like '_u' over reserved
+     system symbols like '_Z' and also will avoid qsort instability.  */
+  return *n1 - *n2;
 }
 
 /* This function is used to adjust offsets into .dynstr for
@@ -5345,8 +5378,8 @@ error_free_dyn:
 	 defined symbol, search time for N weak defined symbols will be
 	 O(N^2). Binary search will cut it down to O(NlogN).  */
       amt = extsymcount;
-      amt *= sizeof (struct elf_link_hash_entry *);
-      sorted_sym_hash = (struct elf_link_hash_entry **) bfd_malloc (amt);
+      amt *= sizeof (*sorted_sym_hash);
+      sorted_sym_hash = bfd_malloc (amt);
       if (sorted_sym_hash == NULL)
 	goto error_return;
       sym_hash = sorted_sym_hash;
@@ -5366,8 +5399,7 @@ error_free_dyn:
 	    }
 	}
 
-      qsort (sorted_sym_hash, sym_count,
-	     sizeof (struct elf_link_hash_entry *),
+      qsort (sorted_sym_hash, sym_count, sizeof (*sorted_sym_hash),
 	     elf_sort_symbol);
 
       while (weaks != NULL)