diff options
| author | Tomoaki Kawada <kawada@kmckk.co.jp> | 2022-06-16 09:54:30 +0000 |
|---|---|---|
| committer | Alan Modra <amodra@gmail.com> | 2022-06-18 20:11:23 +0930 |
| commit | fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4 (patch) | |
| tree | 4122da4e90d8f5897cec0d8719132794548883de /bfd/elflink.c | |
| parent | 3f52a09075e3c62f2150375bb7fca338e7db45e7 (diff) | |
| download | binutils-fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4.zip binutils-fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4.tar.gz binutils-fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4.tar.bz2 | |
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.
Diffstat (limited to 'bfd/elflink.c')
| -rw-r--r-- | bfd/elflink.c | 12 |
1 files changed, 10 insertions, 2 deletions
diff --git a/bfd/elflink.c b/bfd/elflink.c index e4f6df4..dcafac3 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); |