Bug 29259

Summary: ld -r may create reloc sections with unordered relocs again
Product: binutils Reporter: Tomoaki Kawada <kawada>
Component: ldAssignee: Alan Modra <amodra>
Status: RESOLVED FIXED    
Severity: normal    
Priority: P2    
Version: 2.39   
Target Milestone: 2.39   
Host: Target:
Build: Last reconfirmed: 2022-06-18 00:00:00
Attachments: Proposed patch

Description Tomoaki Kawada 2022-06-17 02:42:52 UTC
Created attachment 14149 [details]
Proposed patch

The optimization to the relocation entry sorting algorithm introduced in
commit bca6d0e31 can lead to incorrect (unsorted) outputs in rare
circumstances.

The symptoms include a link warning about `.eh_frame_hdr` not being created
(similar to bug #16345) and a C++ exception causing abort instead of being
caught by an exception handler.

Reproducer:

    #!/bin/sh
    cat > test.ld <<EOF
    SECTIONS {
        .text : {
            KEEP(*(.text.1));
            KEEP(*(.text.4));
            KEEP(*(.text.3));
            KEEP(*(.text.2));
        }
    }
    EOF
    ${AS:-as} -o test.o <<EOF
        .text
    .L1:
        .word 0
        .section ".text.1", "ax", %progbits
    .L2:
        .dc.a .L1
        .section ".text.2", "ax", %progbits
        .dc.a .L1
        .section ".text.3", "ax", %progbits
        .dc.a .L1
        .section ".text.4", "ax", %progbits
        .dc.a .L1
    EOF
    ${LD:-ld} -o test2.o test.o -r -q -T test.ld
    ${READELF:-readelf} -r test2.o
        
The above script outputs reloc entries out-of-order:

    Relocation section '.rela.text' at offset 0x118 contains 4 entries:
      Offset          Info           Type           Sym. Value    Sym. Name + Addend
    000000000000  000100000001 R_X86_64_64       0000000000000000 .text + 20
    000000000010  000100000001 R_X86_64_64       0000000000000000 .text + 20
    000000000008  000100000001 R_X86_64_64       0000000000000000 .text + 20
    000000000018  000100000001 R_X86_64_64       0000000000000000 .text + 20

The problem is that the current algorithm incorrectly assembles "runs" from
unsorted entries and inserted them to an already-sorted prefix, breaking the
loop invariants of insertion sort. The attached patch fixes the problem by
adding a check to ensure that only sorted entries are included in the runs.
Comment 1 cvs-commit@gcc.gnu.org 2022-06-18 10:43:50 UTC
The master branch has been updated by Alan Modra <amodra@sourceware.org>:

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.
Comment 2 Alan Modra 2022-06-18 10:46:13 UTC
Fixed for 2.39