public inbox for binutils-cvs@sourceware.org
help / color / mirror / Atom feed
* [binutils-gdb] Fix the sorting algorithm for reloc entries
@ 2022-06-18 10:43 Alan Modra
  0 siblings, 0 replies; only message in thread
From: Alan Modra @ 2022-06-18 10:43 UTC (permalink / raw)
  To: bfd-cvs

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4

commit fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4
Author: Tomoaki Kawada <kawada@kmckk.co.jp>
Date:   Thu Jun 16 09:54:30 2022 +0000

    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.

Diff:
---
 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(-)

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) }
+}


^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2022-06-18 10:43 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-18 10:43 [binutils-gdb] Fix the sorting algorithm for reloc entries Alan Modra

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).