From 443aa5f05edb58fc1774f926e9259b7c5a180926 Mon Sep 17 00:00:00 2001 From: Alan Modra Date: Tue, 21 Dec 2021 01:09:13 +1030 Subject: [PATCH] gas reloc sorting In some cases, eg. riscv_pre_output_hook, gas generates out-of-order relocations. Various places in the linker assume relocs are sorted by increasing r_offset, which is normally the case. Provide GAS_SORT_RELOCS to handle unsorted relocs. bfd/ PR 28709 * elf32-nds32.c (nds32_insertion_sort): Make static. * elf32-nds32.h (nds32_insertion_sort): Delete declaration. gas/ PR 28709 * write.c (write_relocs): Implement reloc sorting by r_offset when GAS_SORT_RELOCS. * config/tc-nds32.c (compar_relent, nds32_set_section_relocs): Delete. * config/tc-nds32.h (nds32_set_section_relocs): Don't declare. (SET_SECTION_RELOCS): Don't define. (GAS_SORT_RELOCS): Define. * config/tc-riscv.h (GAS_SORT_RELOCS): Define. --- bfd/elf32-nds32.c | 2 +- bfd/elf32-nds32.h | 2 -- gas/config/tc-nds32.c | 39 --------------------------------------- gas/config/tc-nds32.h | 3 +-- gas/config/tc-riscv.h | 1 + gas/write.c | 29 ++++++++++++++++++++++++++++- 6 files changed, 31 insertions(+), 45 deletions(-) diff --git a/bfd/elf32-nds32.c b/bfd/elf32-nds32.c index 5b43ca97803..56d1d39181c 100644 --- a/bfd/elf32-nds32.c +++ b/bfd/elf32-nds32.c @@ -2522,7 +2522,7 @@ nds32_put_trampoline (void *contents, const unsigned long *template, /* nds32_insertion_sort sorts an array with nmemb elements of size size. This prototype is the same as qsort (). */ -void +static void nds32_insertion_sort (void *base, size_t nmemb, size_t size, int (*compar) (const void *lhs, const void *rhs)) { diff --git a/bfd/elf32-nds32.h b/bfd/elf32-nds32.h index 0f496361555..0bf16974421 100644 --- a/bfd/elf32-nds32.h +++ b/bfd/elf32-nds32.h @@ -95,8 +95,6 @@ extern int elf32_nds32_check_relax_group (bfd *, asection *); extern int elf32_nds32_unify_relax_group (bfd *, asection *); extern int nds32_elf_unify_tls_model (bfd *, asection *, bfd_byte *, struct bfd_link_info *); -extern void nds32_insertion_sort -(void *, size_t, size_t, int (*) (const void *, const void *)); extern int nds32_convert_32_to_16 (bfd *, uint32_t, uint16_t *, int *); extern int nds32_convert_16_to_32 (bfd *, uint16_t, uint32_t *); diff --git a/gas/config/tc-nds32.c b/gas/config/tc-nds32.c index 0ab436c5f19..228afa616c9 100644 --- a/gas/config/tc-nds32.c +++ b/gas/config/tc-nds32.c @@ -7537,45 +7537,6 @@ nds32_allow_local_subtract (expressionS *expr_l ATTRIBUTE_UNUSED, return false; } -/* Sort relocation by address. - - We didn't use qsort () in stdlib, because quick-sort is not a stable - sorting algorithm. Relocations at the same address (r_offset) must keep - their relative order. For example, RELAX_ENTRY must be the very first - relocation entry. - - Currently, this function implements insertion-sort. */ - -static int -compar_relent (const void *lhs, const void *rhs) -{ - const arelent **l = (const arelent **) lhs; - const arelent **r = (const arelent **) rhs; - - if ((*l)->address > (*r)->address) - return 1; - else if ((*l)->address == (*r)->address) - return 0; - else - return -1; -} - -/* SET_SECTION_RELOCS () - - Although this macro is originally used to set a relocation for each section, - we use it to sort relocations in the same section by the address of the - relocation. */ - -void -nds32_set_section_relocs (asection *sec ATTRIBUTE_UNUSED, - arelent **relocs, unsigned int n) -{ - if (n <= 1) - return; - - nds32_insertion_sort (relocs, n, sizeof (*relocs), compar_relent); -} - long nds32_pcrel_from_section (fixS *fixP, segT sec ATTRIBUTE_UNUSED) { diff --git a/gas/config/tc-nds32.h b/gas/config/tc-nds32.h index da7e38c0094..85a1adb8eed 100644 --- a/gas/config/tc-nds32.h +++ b/gas/config/tc-nds32.h @@ -88,7 +88,6 @@ extern void nds32_frob_file_before_fix (void); extern void elf_nds32_final_processing (void); extern int nds32_validate_fix_sub (struct fix *, segT); extern int nds32_force_relocation (struct fix *); -extern void nds32_set_section_relocs (asection *, arelent ** , unsigned int); /* Fill in rs_align_code fragments. TODO: Review this. */ extern void nds32_handle_align (fragS *); @@ -110,7 +109,7 @@ extern void tc_nds32_frame_initial_instructions (void); || TC_FORCE_RELOCATION (FIX)) #define TC_FORCE_RELOCATION(fix) nds32_force_relocation (fix) #define TC_VALIDATE_FIX_SUB(FIX,SEG) nds32_validate_fix_sub (FIX,SEG) -#define SET_SECTION_RELOCS(sec, relocs, n) nds32_set_section_relocs (sec, relocs, n) +#define GAS_SORT_RELOCS 1 /* Values passed to md_apply_fix don't include the symbol value. */ #define MD_APPLY_SYM_VALUE(FIX) 0 #define HANDLE_ALIGN(f) nds32_handle_align (f) diff --git a/gas/config/tc-riscv.h b/gas/config/tc-riscv.h index fbe5e765042..1ca02c0bbc6 100644 --- a/gas/config/tc-riscv.h +++ b/gas/config/tc-riscv.h @@ -78,6 +78,7 @@ extern int riscv_parse_long_option (const char *); #define md_pre_output_hook riscv_pre_output_hook () extern void riscv_pre_output_hook (void); +#define GAS_SORT_RELOCS 1 /* Let the linker resolve all the relocs due to relaxation. */ #define tc_fix_adjustable(fixp) 0 diff --git a/gas/write.c b/gas/write.c index e2c7bf29249..eaa9d21068f 100644 --- a/gas/write.c +++ b/gas/write.c @@ -1315,7 +1315,34 @@ write_relocs (bfd *abfd ATTRIBUTE_UNUSED, asection *sec, } r = r->next; } - relocs[n++] = *reloc; +#ifdef GAS_SORT_RELOCS + if (n != 0 && (*reloc)->address < relocs[n - 1]->address) + { + size_t lo = 0; + size_t hi = n - 1; + bfd_vma look = (*reloc)->address; + while (lo < hi) + { + size_t mid = (lo + hi) / 2; + if (relocs[mid]->address > look) + hi = mid; + else + { + lo = mid + 1; + if (relocs[mid]->address == look) + break; + } + } + while (lo < hi && relocs[lo]->address == look) + lo++; + memmove (relocs + lo + 1, relocs + lo, + (n - lo) * sizeof (*relocs)); + n++; + relocs[lo] = *reloc; + } + else +#endif + relocs[n++] = *reloc; install_reloc (sec, *reloc, fixp->fx_frag, fixp->fx_file, fixp->fx_line); #ifndef RELOC_EXPANSION_POSSIBLE -- 2.30.2