From bca6d0e3195217576b39fa1205469e1d578b386a Mon Sep 17 00:00:00 2001 From: Alan Modra Date: Wed, 16 Sep 2015 18:07:03 +0930 Subject: [PATCH] Fix slowdown in ld -r for most common case of out-of-order relocs I chose insertion sort since relocs are mostly sorted, but there is a common case we can handle better; A run of relocs put out of order due to not linking input files in order. PR 18867 * elflink.c (elf_link_adjust_relocs): Modify insertion sort to insert a run. Return status in case of malloc failure. Adjust callers. --- bfd/ChangeLog | 7 ++++++ bfd/elflink.c | 66 +++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 58 insertions(+), 15 deletions(-) diff --git a/bfd/ChangeLog b/bfd/ChangeLog index fb809a3aad9..a99c2e0bad4 100644 --- a/bfd/ChangeLog +++ b/bfd/ChangeLog @@ -1,3 +1,10 @@ +2015-09-16 Alan Modra + + PR 18867 + * elflink.c (elf_link_adjust_relocs): Modify insertion sort to + insert a run. Return status in case of malloc failure. + Adjust callers. + 2015-09-15 Max Filippov * elf32-xtensa.c (elf_xtensa_be_plt_entry) diff --git a/bfd/elflink.c b/bfd/elflink.c index 4f867004097..8659099df0d 100644 --- a/bfd/elflink.c +++ b/bfd/elflink.c @@ -8193,7 +8193,7 @@ ext64b_r_offset (const void *p) referenced must be updated. Update all the relocations found in RELDATA. */ -static void +static bfd_boolean elf_link_adjust_relocs (bfd *abfd, struct bfd_elf_section_reloc_data *reldata, bfd_boolean sort) @@ -8259,7 +8259,7 @@ elf_link_adjust_relocs (bfd *abfd, bfd_vma r_off; size_t elt_size; bfd_byte *base, *end, *p, *loc; - bfd_byte buf[sizeof (Elf64_External_Rela)]; + bfd_byte *buf = NULL; if (bed->s->arch_size == 32) { @@ -8282,12 +8282,12 @@ elf_link_adjust_relocs (bfd *abfd, abort (); } - /* Must use a stable sort here. Insertion sort, since the - relocs are mostly sorted already. */ + /* Must use a stable sort here. A modified insertion sort, + since the relocs are mostly sorted already. */ elt_size = reldata->hdr->sh_entsize; base = reldata->hdr->contents; end = base + count * elt_size; - if (elt_size > sizeof (buf)) + if (elt_size > sizeof (Elf64_External_Rela)) abort (); /* Ensure the first element is lowest. This acts as a sentinel, @@ -8307,12 +8307,13 @@ elf_link_adjust_relocs (bfd *abfd, /* Don't just swap *base and *loc as that changes the order of the original base[0] and base[1] if they happen to have the same r_offset. */ - memcpy (buf, loc, elt_size); + bfd_byte onebuf[sizeof (Elf64_External_Rela)]; + memcpy (onebuf, loc, elt_size); memmove (base + elt_size, base, loc - base); - memcpy (base, buf, elt_size); + memcpy (base, onebuf, elt_size); } - for (p = base + elt_size; (p += elt_size) < end; ) + for (p = base + elt_size; p < end; ) { /* base to p is sorted, *p is next to insert. */ r_off = (*ext_r_off) (p); @@ -8323,15 +8324,48 @@ elf_link_adjust_relocs (bfd *abfd, loc += elt_size; if (loc != p) { - memcpy (buf, p, elt_size); - memmove (loc + elt_size, loc, p - loc); - memcpy (loc, buf, elt_size); + /* Chances are there is a run of relocs to insert here, + from one of more input files. Files are not always + linked in order due to the way elf_link_input_bfd is + called. See pr17666. */ + size_t sortlen = p - loc; + bfd_vma r_off2 = (*ext_r_off) (loc); + size_t runlen = elt_size; + 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; + if (buf == NULL) + { + buf = bfd_malloc (buf_size); + if (buf == NULL) + return FALSE; + } + if (runlen < sortlen) + { + memcpy (buf, p, runlen); + memmove (loc + runlen, loc, sortlen); + memcpy (loc, buf, runlen); + } + else + { + memcpy (buf, loc, sortlen); + memmove (loc, p, runlen); + memcpy (loc + runlen, buf, sortlen); + } + p += runlen; } + else + p += elt_size; } /* Hashes are no longer valid. */ free (reldata->hashes); reldata->hashes = NULL; + free (buf); } + return TRUE; } struct elf_link_sort_rela @@ -11577,10 +11611,12 @@ bfd_elf_final_link (bfd *abfd, struct bfd_link_info *info) continue; sort = bed->sort_relocs_p == NULL || (*bed->sort_relocs_p) (o); - if (esdo->rel.hdr != NULL) - elf_link_adjust_relocs (abfd, &esdo->rel, sort); - if (esdo->rela.hdr != NULL) - elf_link_adjust_relocs (abfd, &esdo->rela, sort); + if (esdo->rel.hdr != NULL + && !elf_link_adjust_relocs (abfd, &esdo->rel, sort)) + return FALSE; + if (esdo->rela.hdr != NULL + && !elf_link_adjust_relocs (abfd, &esdo->rela, sort)) + return FALSE; /* Set the reloc_count field to 0 to prevent write_relocs from trying to swap the relocs out itself. */ -- 2.30.2