ELF: Properly group and place orphan note sections

Properly group orphan note sections.  When placing orphan note section
as the first note section, place it after the section before all note
sections.

	PR ld/23658
	* ldlang.c (lang_insert_orphan): Properly group and place orphan
	note sections.  Properly handle orphan note section before all
	note sections.
	* testsuite/ld-elf/pr23658-1.d: Renamed to ...
	* testsuite/ld-elf/pr23658-1a.d: This.  Updated.
	* testsuite/ld-elf/pr23658-1b.d: New test.
	* testsuite/ld-elf/pr23658-1c.d: Likewise.

5 files changed, 140 insertions, 56 deletions

diff --git a/ld/ChangeLog b/ld/ChangeLog
index e0a6f72..6c322c3 100644
--- a/ld/ChangeLog
+++ b/ld/ChangeLog
@@ -1,3 +1,14 @@
+2018-10-08  H.J. Lu  <hongjiu.lu@intel.com>
+
+	PR ld/23658
+	* ldlang.c (lang_insert_orphan): Properly group and place orphan
+	note sections.  Properly handle orphan note section before all
+	note sections.
+	* testsuite/ld-elf/pr23658-1.d: Renamed to ...
+	* testsuite/ld-elf/pr23658-1a.d: This.  Updated.
+	* testsuite/ld-elf/pr23658-1b.d: New test.
+	* testsuite/ld-elf/pr23658-1c.d: Likewise.
+
 2018-10-08  Alan Modra  <amodra@gmail.com>
 
 	* ldexp.c (fold_name <SIZEOF_HEADERS>): Set link_info.load_phdrs.
diff --git a/ld/ldlang.c b/ld/ldlang.c
index 0041f57..8d35e0d 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -1879,6 +1879,7 @@ lang_insert_orphan (asection *s,
     {
       asection *snew, *as;
       bfd_boolean place_after = place->stmt == NULL;
+      bfd_boolean insert_after = TRUE;
 
       snew = os->bfd_section;
 
@@ -1934,7 +1935,9 @@ lang_insert_orphan (asection *s,
 	  asection *after_sec;
 	  /* True if we need to insert the orphan section after a
 	     specific section to maintain output note section order.  */
-	  bfd_boolean after_sec_note;
+	  bfd_boolean after_sec_note = FALSE;
+
+	  static asection *first_orphan_note = NULL;
 
 	  /* Group and sort output note section by alignments in
 	     ascending order.  */
@@ -1942,11 +1945,12 @@ lang_insert_orphan (asection *s,
 	  if (elf_section_type (s) == SHT_NOTE
 	      && (s->flags & SEC_LOAD) != 0)
 	    {
-	      /* Search forward for the last output note section
-		 with equal or larger alignments.  */
-	      asection *first_note = NULL;
+	      /* Search from the beginning for the last output note
+		 section with equal or larger alignments.  NB: Don't
+		 place orphan note section after non-note sections.  */
 
-	      for (sec = as;
+	      first_orphan_note = NULL;
+	      for (sec = link_info.output_bfd->sections;
 		   (sec != NULL
 		    && !bfd_is_abs_section (sec));
 		   sec = sec->next)
@@ -1954,52 +1958,34 @@ lang_insert_orphan (asection *s,
 		    && elf_section_type (sec) == SHT_NOTE
 		    && (sec->flags & SEC_LOAD) != 0)
 		  {
-		    if (!first_note)
-		      first_note = sec;
+		    if (!first_orphan_note)
+		      first_orphan_note = sec;
 		    if (sec->alignment_power >= s->alignment_power)
 		      after_sec = sec;
 		  }
+		else if (first_orphan_note)
+		  {
+		    /* Stop if there is non-note section after the first
+		       orphan note section.  */
+		    break;
+		  }
 
-	      if (after_sec)
-		after_sec_note = TRUE;
-	      else
+	      /* If this will be the first orphan note section, it can
+		 be placed at the default location.  */
+	      after_sec_note = first_orphan_note != NULL;
+	      if (after_sec == NULL && after_sec_note)
 		{
-		  /* Search backward for the first output note section
-		     as well as the last output note section with equal
-		     or larger alignments.  */
-		  after_sec = NULL;
-		  for (sec = as;
-		       (sec != NULL
-			&& !bfd_is_abs_section (sec));
-		       sec = sec->prev)
-		    if (sec != snew
-			&& elf_section_type (sec) == SHT_NOTE
-			&& (sec->flags & SEC_LOAD) != 0)
-		      {
-			first_note = sec;
-			if (!after_sec
-			    && sec->alignment_power >= s->alignment_power)
-			  after_sec = sec;
-		      }
-
-		  /* If this will be the first note section, it can be
-		     placed at the default location.  */
-		  after_sec_note = first_note != NULL;
-		  if (after_sec == NULL && after_sec_note)
-		    {
-		      /* If all output note sections have smaller
-			 alignments, place the section before all
-			 output note sections.  AFTER_SEC will be
-			 NULL if FIRST_NOTE is the first output
-			 section.  */
-		      after_sec = first_note->prev;
-		    }
+		  /* If all output note sections have smaller
+		     alignments, place the section before all
+		     output orphan note sections.  */
+		  after_sec = first_orphan_note;
+		  insert_after = FALSE;
 		}
 	    }
-	  else
+	  else if (first_orphan_note)
 	    {
-	      /* Don't place non-note sections in the middle of note
-		 sections.  */
+	      /* Don't place non-note sections in the middle of orphan
+	         note sections.  */
 	      after_sec_note = TRUE;
 	      after_sec = as;
 	      for (sec = as->next;
@@ -2015,20 +2001,68 @@ lang_insert_orphan (asection *s,
 	    {
 	      if (after_sec)
 		{
-		  /* Insert OS after AFTER_SEC output statement.  */
-		  lang_output_section_statement_type *stmt;
-		  for (stmt = after;
-		       stmt != NULL;
-		       stmt = stmt->next)
-		    if (stmt->bfd_section == after_sec)
+		  /* Search forward to insert OS after AFTER_SEC output
+		     statement.  */
+		  lang_output_section_statement_type *stmt, *next;
+		  bfd_boolean found = FALSE;
+		  for (stmt = after; stmt != NULL; stmt = next)
+		    {
+		      next = stmt->next;
+		      if (insert_after)
+			{
+			  if (stmt->bfd_section == after_sec)
+			    {
+			      place_after = TRUE;
+			      found = TRUE;
+			      after = stmt;
+			      break;
+			    }
+			}
+		      else
+			{
+			  /* If INSERT_AFTER is FALSE, place OS before
+			     AFTER_SEC output statement.  */
+			  if (next && next->bfd_section == after_sec)
+			    {
+			      place_after = TRUE;
+			      found = TRUE;
+			      after = stmt;
+			      break;
+			    }
+			}
+		    }
+
+		  /* Search backward to insert OS after AFTER_SEC output
+		     statement.  */
+		  if (!found)
+		    for (stmt = after; stmt != NULL; stmt = stmt->prev)
 		      {
-			place_after = TRUE;
-			after = stmt;
-			break;
+			if (insert_after)
+			  {
+			    if (stmt->bfd_section == after_sec)
+			      {
+				place_after = TRUE;
+				after = stmt;
+				break;
+			      }
+			  }
+			else
+			  {
+			    /* If INSERT_AFTER is FALSE, place OS before
+			       AFTER_SEC output statement.  */
+			    if (stmt->next->bfd_section == after_sec)
+			      {
+				place_after = TRUE;
+				after = stmt;
+				break;
+			      }
+			  }
 		      }
 		}
 
-	      if (after_sec == NULL || after_sec->next != snew)
+	      if (after_sec == NULL
+		  || (insert_after && after_sec->next != snew)
+		  || (!insert_after && after_sec->prev != snew))
 		{
 		  /* Unlink the section.  */
 		  bfd_section_list_remove (link_info.output_bfd, snew);
@@ -2036,8 +2070,14 @@ lang_insert_orphan (asection *s,
 		  /* Place SNEW after AFTER_SEC.  If AFTER_SEC is NULL,
 		     prepend SNEW.  */
 		  if (after_sec)
-		    bfd_section_list_insert_after (link_info.output_bfd,
-						   after_sec, snew);
+		    {
+		      if (insert_after)
+			bfd_section_list_insert_after (link_info.output_bfd,
+						       after_sec, snew);
+		      else
+			bfd_section_list_insert_before (link_info.output_bfd,
+						       after_sec, snew);
+		    }
 		  else
 		    bfd_section_list_prepend (link_info.output_bfd, snew);
 		}
diff --git a/ld/testsuite/ld-elf/pr23658-1.d b/ld/testsuite/ld-elf/pr23658-1a.d
index e21206b..5cfc7d2 100644
--- a/ld/testsuite/ld-elf/pr23658-1.d
+++ b/ld/testsuite/ld-elf/pr23658-1a.d
@@ -7,8 +7,12 @@
 #readelf: -l --wide
 # Since generic linker targets don't place SHT_NOTE sections as orphan,
 # SHT_NOTE sections aren't grouped nor sorted.
-#xfail: cr16-* crx-* d30v-* dlx-* fr30-* frv-* ft32-* iq2000-*
+#xfail: d30v-* dlx-* fr30-* frv-*-elf ft32-* iq2000-*
 #xfail: m68hc12-* mn10200-* moxie-* mt-* msp430-* pj-* xgate-*
+# The following targets don't support --build-id.
+#xfail: cr16-* crx-* visium-* xc16x-*
+# The following targets place .note.gnu.build-id in unusual places.
+#xfail: pru-*
 
 #...
  +[0-9]+ +\.note\.4 \.note\.1 +
diff --git a/ld/testsuite/ld-elf/pr23658-1b.d b/ld/testsuite/ld-elf/pr23658-1b.d
new file mode 100644
index 0000000..a8e7d16
--- /dev/null
+++ b/ld/testsuite/ld-elf/pr23658-1b.d
@@ -0,0 +1,16 @@
+#source: pr23658-1a.s
+#source: pr23658-1b.s
+#source: pr23658-1c.s
+#source: pr23658-1d.s
+#source: start.s
+#ld:
+#readelf: -l --wide
+# Since generic linker targets don't place SHT_NOTE sections as orphan,
+# SHT_NOTE sections aren't grouped nor sorted.
+#xfail: d30v-* dlx-* fr30-* frv-*-elf ft32-* iq2000-*
+#xfail: mn10200-* moxie-* mt-* msp430-* pj-* xgate-*
+
+#...
+ +[0-9]+ +\.note\.4 \.note\.1( .note.gnu.property|) +
+ +[0-9]+ +\.note\.2 .note\.3( .note.gnu.property|) +
+#pass
diff --git a/ld/testsuite/ld-elf/pr23658-1c.d b/ld/testsuite/ld-elf/pr23658-1c.d
new file mode 100644
index 0000000..6d8fd7e
--- /dev/null
+++ b/ld/testsuite/ld-elf/pr23658-1c.d
@@ -0,0 +1,13 @@
+#source: pr23658-1a.s
+#source: pr23658-1b.s
+#source: pr23658-1c.s
+#source: pr23658-1d.s
+#source: start.s
+#ld: --build-id -shared
+#readelf: -l --wide
+#target: *-*-linux* *-*-gnu* arm*-*-uclinuxfdpiceabi
+
+#...
+ +[0-9]+ +\.note\.4 \.note\.1 +
+ +[0-9]+ +\.note.gnu.build-id \.note\.2 .note\.3 +
+#pass