From fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4 Mon Sep 17 00:00:00 2001
From: Tomoaki Kawada <kawada@kmckk.co.jp>
Date: Thu, 16 Jun 2022 09:54:30 +0000
Subject: [PATCH] Fix the sorting algorithm for reloc entries

The optimized insertion sort algorithm in `elf_link_adjust_relocs`
incorrectly assembled "runs" from unsorted entries and inserted them to an
already-sorted prefix, breaking the loop invariants of insertion sort.
This commit updates the run assembly loop to break upon encountering a
non-monotonic change in the sort key.

	PR 29259
bfd/
	* elflink.c (elf_link_adjust_relocs): Ensure run being inserted
	is sorted.
ld/
	* testsuite/ld-elf/pr29259.d,
	* testsuite/ld-elf/pr29259.s,
	* testsuite/ld-elf/pr29259.t: New test.
---
 bfd/elflink.c                 | 12 ++++++++++--
 ld/testsuite/ld-elf/pr29259.d | 13 +++++++++++++
 ld/testsuite/ld-elf/pr29259.s | 14 ++++++++++++++
 ld/testsuite/ld-elf/pr29259.t |  4 ++++
 4 files changed, 41 insertions(+), 2 deletions(-)
 create mode 100644 ld/testsuite/ld-elf/pr29259.d
 create mode 100644 ld/testsuite/ld-elf/pr29259.s
 create mode 100644 ld/testsuite/ld-elf/pr29259.t

diff --git a/bfd/elflink.c b/bfd/elflink.c
index e4f6df43042..dcafac32800 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -9548,12 +9548,20 @@ elf_link_adjust_relocs (bfd *abfd,
 	      size_t sortlen = p - loc;
 	      bfd_vma r_off2 = (*ext_r_off) (loc);
 	      size_t runlen = elt_size;
+	      bfd_vma r_off_runend = r_off;
+	      bfd_vma r_off_runend_next;
 	      size_t buf_size = 96 * 1024;
 	      while (p + runlen < end
 		     && (sortlen <= buf_size
 			 || runlen + elt_size <= buf_size)
-		     && r_off2 > (*ext_r_off) (p + runlen))
-		runlen += elt_size;
+		     /* run must not break the ordering of base..loc+1 */
+		     && r_off2 > (r_off_runend_next = (*ext_r_off) (p + runlen))
+		     /* run must be already sorted */
+		     && r_off_runend_next >= r_off_runend)
+		{
+		  runlen += elt_size;
+		  r_off_runend = r_off_runend_next;
+		}
 	      if (buf == NULL)
 		{
 		  buf = bfd_malloc (buf_size);
diff --git a/ld/testsuite/ld-elf/pr29259.d b/ld/testsuite/ld-elf/pr29259.d
new file mode 100644
index 00000000000..c7eaa7a5a23
--- /dev/null
+++ b/ld/testsuite/ld-elf/pr29259.d
@@ -0,0 +1,13 @@
+#ld: -r -T pr29259.t
+#readelf: -Wr
+
+Relocation section .*
+ +Offset +Info +Type .*
+0+00 .*
+#...
+0+20 .*
+#...
+0+40 .*
+#...
+0+60 .*
+#pass
diff --git a/ld/testsuite/ld-elf/pr29259.s b/ld/testsuite/ld-elf/pr29259.s
new file mode 100644
index 00000000000..65fc73fd6d0
--- /dev/null
+++ b/ld/testsuite/ld-elf/pr29259.s
@@ -0,0 +1,14 @@
+ .data
+.L1:
+ .section ".data.1", "aw", %progbits
+ .p2align 5
+ .dc.a .L1
+ .section ".data.2", "aw", %progbits
+ .p2align 5
+ .dc.a .L1
+ .section ".data.3", "aw", %progbits
+ .p2align 5
+ .dc.a .L1
+ .section ".data.4", "aw", %progbits
+ .p2align 5
+ .dc.a .L1
diff --git a/ld/testsuite/ld-elf/pr29259.t b/ld/testsuite/ld-elf/pr29259.t
new file mode 100644
index 00000000000..ed80f8700ca
--- /dev/null
+++ b/ld/testsuite/ld-elf/pr29259.t
@@ -0,0 +1,4 @@
+SECTIONS
+{
+  .data : { *(.data.1) *(.data.4) *(.data.3) *(.data.2) *(.data) }
+}
-- 
2.30.2