[Bug ld/29259] New: ld -r may create reloc sections with unordered relocs again

[kawada at kmckk dot co.jp]

https://sourceware.org/bugzilla/show_bug.cgi?id=29259

            Bug ID: 29259
           Summary: ld -r may create reloc sections with unordered relocs
                    again
           Product: binutils
           Version: 2.39 (HEAD)
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: ld
          Assignee: unassigned at sourceware dot org
          Reporter: kawada at kmckk dot co.jp
  Target Milestone: ---

Created attachment 14149
  --> https://sourceware.org/bugzilla/attachment.cgi?id=14149&action=edit
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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.