SHF_LINK_ORDER fixup_link_order in ld

This moves the SHF_LINK_ORDER sorting from bfd_elf_final_link to
the linker which means generic ELF targets now support SHF_LINK_ORDER
and  we cope with odd cases that require resizing of output sections.
The patch also fixes two bugs in the current implementation,
introduced by commit cd6d537c48fa.  The pattern test used by that
commit meant that sections matching something like
"*(.IA_64.unwind* .gnu.linkonce.ia64unw.*)" would not properly sort a
mix of sections matching the two wildcards.  That commit also assumed
a stable qsort.

bfd/
	PR 27160
	* section.c (struct bfd_section): Remove pattern field.
	(BFD_FAKE_SECTION): Adjust to suit.
	* bfd-in2.h: Regenerate.
	* elflink.c (compare_link_order, elf_fixup_link_order): Delete.
	(bfd_elf_final_link): Don't call elf_fixup_link_order.
ld/
	PR 27160
	* ldlang.h (lang_output_section_statement_type): Add data field.
	(lang_input_section_type, lang_section_bst_type): Add pattern field.
	(statement_list): Declare.
	(lang_add_section): Adjust prototype.
	* emultempl/aarch64elf.em: Adjust lang_add_section calls.
	* emultempl/armelf.em: Likewise.
	* emultempl/beos.em: Likewise.
	* emultempl/cskyelf.em: Likewise.
	* emultempl/hppaelf.em: Likewise.
	* emultempl/m68hc1xelf.em: Likewise.
	* emultempl/metagelf.em: Likewise.
	* emultempl/mipself.em: Likewise.
	* emultempl/mmo.em: Likewise.
	* emultempl/msp430.em: Likewise.
	* emultempl/nios2elf.em: Likewise.
	* emultempl/pe.em: Likewise.
	* emultempl/pep.em: Likewise.
	* emultempl/ppc64elf.em: Likewise.
	* emultempl/spuelf.em: Likewise.
	* emultempl/vms.em: Likewise.
	* ldelf.c: Likewise.
	* ldelfgen.c: Include ldctor.h.
	(struct os_sections): New.
	(add_link_order_input_section, link_order_scan): New functions.
	(compare_link_order, fixup_link_order): New functions.
	(ldelf_map_segments): Call link_order_scan and fixup_link_order.
	* ldlang.c (statement_list): Make global.
	(output_section_callback_fast): Save pattern in tree node.
	(lang_add_section): Add pattern parameter, save in lang_input_section.
	(output_section_callback_tree_to_list): Adjust lang_add_section calls.
	(lang_insert_orphan, output_section_callback): Likewise.
	(ldlang_place_orphan): Likewise.
	(gc_section_callback): Don't set section->pattern
	* testsuite/ld-elf/pr26256-2a.d: Don't xfail generic.
	* testsuite/ld-elf/pr26256-3b.d: Likewise.
	* testsuite/ld-elf/pr26256-2b.d: Likewise.  notarget xgate.

4 files changed, 13 insertions, 204 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 158b798..0e12e74 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,12 @@
+2021-01-13  Alan Modra  <amodra@gmail.com>
+
+	PR 27160
+	* section.c (struct bfd_section): Remove pattern field.
+	(BFD_FAKE_SECTION): Adjust to suit.
+	* bfd-in2.h: Regenerate.
+	* elflink.c (compare_link_order, elf_fixup_link_order): Delete.
+	(bfd_elf_final_link): Don't call elf_fixup_link_order.
+
 2021-01-12  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR binutils/26792
diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h
index 7eff85b..d142bb5 100644
--- a/bfd/bfd-in2.h
+++ b/bfd/bfd-in2.h
@@ -1184,9 +1184,6 @@ typedef struct bfd_section
   struct bfd_symbol *symbol;
   struct bfd_symbol **symbol_ptr_ptr;
 
-  /* The matching section name pattern in linker script.  */
-  const char *pattern;
-
   /* Early in the link process, map_head and map_tail are used to build
      a list of input sections attached to an output section.  Later,
      output sections use these fields for a list of bfd_link_order
@@ -1380,8 +1377,8 @@ discarded_section (const asection *sec)
   /* target_index, used_by_bfd, constructor_chain, owner,           */ \
      0,            NULL,        NULL,              NULL,               \
                                                                        \
-  /* symbol,                    symbol_ptr_ptr, pattern,            */ \
-     (struct bfd_symbol *) SYM, &SEC.symbol,    NULL,                  \
+  /* symbol,                    symbol_ptr_ptr,                     */ \
+     (struct bfd_symbol *) SYM, &SEC.symbol,                           \
                                                                        \
   /* map_head, map_tail, already_assigned                           */ \
      { NULL }, { NULL }, NULL                                          \
diff --git a/bfd/elflink.c b/bfd/elflink.c
index acc959d..d20857e 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -11863,193 +11863,6 @@ elf_reloc_link_order (bfd *output_bfd,
   return TRUE;
 }
 
-
-/* Compare two sections based on the locations of the sections they are
-   linked to.  Used by elf_fixup_link_order.  */
-
-static int
-compare_link_order (const void *a, const void *b)
-{
-  const struct bfd_link_order *alo = *(const struct bfd_link_order **) a;
-  const struct bfd_link_order *blo = *(const struct bfd_link_order **) b;
-  asection *asec = elf_linked_to_section (alo->u.indirect.section);
-  asection *bsec = elf_linked_to_section (blo->u.indirect.section);
-  bfd_vma apos, bpos;
-
-  /* Check if any sections are unordered.  */
-  if (asec == NULL || bsec == NULL)
-    {
-      /* Place unordered sections before ordered sections.  */
-      if (bsec != NULL)
-	return -1;
-      else if (asec != NULL)
-	return 1;
-      return 0;
-    }
-
-  apos = asec->output_section->lma + asec->output_offset;
-  bpos = bsec->output_section->lma + bsec->output_offset;
-
-  if (apos < bpos)
-    return -1;
-  if (apos > bpos)
-    return 1;
-
-  /* The only way we should get matching LMAs is when the first of two
-     sections has zero size.  */
-  if (asec->size < bsec->size)
-    return -1;
-  if (asec->size > bsec->size)
-    return 1;
-
-  /* If they are both zero size then they almost certainly have the same
-     VMA and thus are not ordered with respect to each other.  Test VMA
-     anyway, and fall back to id to make the result reproducible across
-     qsort implementations.  */
-  apos = asec->output_section->vma + asec->output_offset;
-  bpos = bsec->output_section->vma + bsec->output_offset;
-  if (apos < bpos)
-    return -1;
-  if (apos > bpos)
-    return 1;
-
-  return asec->id - bsec->id;
-}
-
-
-/* Looks for sections with SHF_LINK_ORDER set.  Rearranges them into the same
-   order as their linked sections.  Returns false if this could not be done
-   because an output section includes both ordered and unordered
-   sections.  Ideally we'd do this in the linker proper.  */
-
-static bfd_boolean
-elf_fixup_link_order (struct bfd_link_info *info, bfd *abfd, asection *o)
-{
-  size_t seen_linkorder;
-  size_t seen_other;
-  size_t n;
-  struct bfd_link_order *p;
-  bfd *sub;
-  struct bfd_link_order **sections, **indirect_sections;
-  asection *other_sec, *linkorder_sec;
-  bfd_vma offset;  /* Octets.  */
-
-  other_sec = NULL;
-  linkorder_sec = NULL;
-  seen_other = 0;
-  seen_linkorder = 0;
-  for (p = o->map_head.link_order; p != NULL; p = p->next)
-    {
-      if (p->type == bfd_indirect_link_order)
-	{
-	  asection *s = p->u.indirect.section;
-	  sub = s->owner;
-	  if ((s->flags & SEC_LINKER_CREATED) == 0
-	      && bfd_get_flavour (sub) == bfd_target_elf_flavour
-	      && elf_section_data (s) != NULL
-	      && elf_linked_to_section (s) != NULL)
-	    {
-	      seen_linkorder++;
-	      linkorder_sec = s;
-	    }
-	  else
-	    {
-	      seen_other++;
-	      other_sec = s;
-	    }
-	}
-      else
-	seen_other++;
-
-      /* Allow mixed ordered and unordered input sections for
-         non-relocatable link.  */
-      if (bfd_link_relocatable (info) && seen_other && seen_linkorder)
-	{
-	  if (other_sec && linkorder_sec)
-	    _bfd_error_handler
-	      /* xgettext:c-format */
-	      (_("%pA has both ordered [`%pA' in %pB] "
-		 "and unordered [`%pA' in %pB] sections"),
-	       o, linkorder_sec, linkorder_sec->owner,
-	       other_sec, other_sec->owner);
-	  else
-	    _bfd_error_handler
-	      (_("%pA has both ordered and unordered sections"), o);
-	  bfd_set_error (bfd_error_bad_value);
-	  return FALSE;
-	}
-    }
-
-  if (!seen_linkorder)
-    return TRUE;
-
-  /* Non-relocatable output can have both ordered and unordered input
-     sections.  */
-  seen_linkorder += seen_other;
-
-  sections = bfd_malloc (seen_linkorder * sizeof (*sections));
-  if (sections == NULL)
-    return FALSE;
-
-  seen_linkorder = 0;
-  for (p = o->map_head.link_order; p != NULL; p = p->next)
-    sections[seen_linkorder++] = p;
-
-  for (indirect_sections = sections, n = 0;
-       n < seen_linkorder;
-       indirect_sections++, n++)
-    {
-      /* Find the first bfd_indirect_link_order section.  */
-      if (indirect_sections[0]->type == bfd_indirect_link_order)
-	{
-	  /* Count the consecutive bfd_indirect_link_order sections
-	     with the same pattern.  */
-	  size_t i, n_indirect;
-	  const char *pattern
-	    = indirect_sections[0]->u.indirect.section->pattern;
-	  for (i = n + 1; i < seen_linkorder; i++)
-	    if (sections[i]->type != bfd_indirect_link_order
-		|| sections[i]->u.indirect.section->pattern != pattern)
-	      break;
-	  n_indirect = i - n;
-	  /* Sort the bfd_indirect_link_order sections in the order of
-	     their linked section.  */
-	  qsort (indirect_sections, n_indirect, sizeof (*sections),
-		 compare_link_order);
-	  indirect_sections += n_indirect;
-	  n += n_indirect;
-	}
-    }
-
-  /* Change the offsets of the bfd_indirect_link_order sections.  */
-  offset = 0;
-  for (n = 0; n < seen_linkorder; n++)
-    if (sections[n]->type == bfd_indirect_link_order)
-      {
-	bfd_vma mask;
-	asection *s = sections[n]->u.indirect.section;
-	unsigned int opb = bfd_octets_per_byte (abfd, s);
-
-	mask = ~(bfd_vma) 0 << s->alignment_power * opb;
-	offset = (offset + ~mask) & mask;
-	sections[n]->offset = s->output_offset = offset / opb;
-	offset += sections[n]->size;
-      }
-    else
-      offset = sections[n]->offset + sections[n]->size;
-
-  free (sections);
-
-  /* Verify that fixing up SHF_LINK_ORDER doesn't increase the section
-     size.  */
-  if (offset > o->size)
-    info->callbacks->einfo
-      (_("%F%P: %pA has ordered sections with incompatible alignments\n"),
-       o);
-
-  return TRUE;
-}
-
 /* Generate an import library in INFO->implib_bfd from symbols in ABFD.
    Returns TRUE upon success, FALSE otherwise.  */
 
@@ -12683,13 +12496,6 @@ bfd_elf_final_link (bfd *abfd, struct bfd_link_info *info)
       htab->tls_size = end - base;
     }
 
-  /* Reorder SHF_LINK_ORDER sections.  */
-  for (o = abfd->sections; o != NULL; o = o->next)
-    {
-      if (!elf_fixup_link_order (info, abfd, o))
-	return FALSE;
-    }
-
   if (!_bfd_elf_fixup_eh_frame_hdr (info))
     return FALSE;
 
diff --git a/bfd/section.c b/bfd/section.c
index 10efc3c..3e6ba0c 100644
--- a/bfd/section.c
+++ b/bfd/section.c
@@ -541,9 +541,6 @@ CODE_FRAGMENT
 .  struct bfd_symbol *symbol;
 .  struct bfd_symbol **symbol_ptr_ptr;
 .
-.  {* The matching section name pattern in linker script.  *}
-.  const char *pattern;
-.
 .  {* Early in the link process, map_head and map_tail are used to build
 .     a list of input sections attached to an output section.  Later,
 .     output sections use these fields for a list of bfd_link_order
@@ -737,8 +734,8 @@ CODE_FRAGMENT
 .  {* target_index, used_by_bfd, constructor_chain, owner,           *}	\
 .     0,            NULL,        NULL,              NULL,		\
 .									\
-.  {* symbol,                    symbol_ptr_ptr, pattern,            *}	\
-.     (struct bfd_symbol *) SYM, &SEC.symbol,    NULL,			\
+.  {* symbol,                    symbol_ptr_ptr,                     *}	\
+.     (struct bfd_symbol *) SYM, &SEC.symbol,				\
 .									\
 .  {* map_head, map_tail, already_assigned                           *}	\
 .     { NULL }, { NULL }, NULL						\