Aaron Miller wrote:
> Hi All,
>
> I was experiencing ~8 minute linking times for a large C++ application
> I have been working on when running -current on amd64. It turns out
> that the decade-old version of ld in the OpenBSD source tree has a bug
> that causes quadratic complexity for some linking operations when
> debug symbols are present. I found a patch from 2006 in a mailing list
> archive that fixes this; I adapted it to work with OpenBSD by editing
> files that are normally regenerated (I couldn't figure out how to do
> automatically regenerate them).
>
> Here is the original patch:
> https://sourceware.org/ml/binutils/2006-08/msg00334.html
>
> I have rebuilt the kernel and system with this ld and everything runs
> identically to the system linked with the unpatched ld.
>
> Please test this and let me know if this could get into the tree, and
> if not, what changes I need to make. Thanks!
Interesting!
About the autogenerated files: it looks you already made the additions
to bfd/linker.c, bfd/targets.c and bfd/libbfd.h that should end up
in bfd-in2.h and libbfd-in.h.
To regenerate them, make sure you first did a "make obj" in the root of
your source tree. Then run "make depend" from gnu/usr.bin. Afterwards,
to to gnu/usr.bin/binutils-2.17/obj/bfd and run "make headers".
headers". That did the trick for me.
PS: It appears that gmail mangled your diff. It does not apply cleanly
here. You probably need to use a different mail client or try sending the
diff as a plain text attachment. Can you please resend an un-mangled
diff?
> Index: bfd/bfd-in2.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/bfd-in2.h,v
> retrieving revision 1.4
> diff -u -p -r1.4 bfd-in2.h
> --- bfd/bfd-in2.h 25 May 2015 14:56:26 -0000 1.4
> +++ bfd/bfd-in2.h 17 Apr 2016 05:14:15 -0000
> @@ -5068,7 +5068,7 @@ typedef struct bfd_target
>
> /* Check if SEC has been already linked during a reloceatable or
> final link. */
> - void (*_section_already_linked) (bfd *, struct bfd_section *);
> + void (*_section_already_linked) (bfd *, struct bfd_section *,
> struct bfd_link_info *);
>
> /* Routines to handle dynamic symbols and relocs. */
> #define BFD_JUMP_TABLE_DYNAMIC(NAME) \
> @@ -5128,10 +5128,10 @@ bfd_boolean bfd_link_split_section (bfd
> #define bfd_link_split_section(abfd, sec) \
> BFD_SEND (abfd, _bfd_link_split_section, (abfd, sec))
>
> -void bfd_section_already_linked (bfd *abfd, asection *sec);
> +void bfd_section_already_linked (bfd *abfd, asection *sec, struct
> bfd_link_info *);
>
> -#define bfd_section_already_linked(abfd, sec) \
> - BFD_SEND (abfd, _section_already_linked, (abfd, sec))
> +#define bfd_section_already_linked(abfd, sec, info) \
> + BFD_SEND (abfd, _section_already_linked, (abfd, sec, info))
>
> /* Extracted from simple.c. */
> bfd_byte *bfd_simple_get_relocated_section_contents
> Index: bfd/elf-bfd.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/elf-bfd.h,v
> retrieving revision 1.4
> diff -u -p -r1.4 elf-bfd.h
> --- bfd/elf-bfd.h 25 Aug 2015 02:24:49 -0000 1.4
> +++ bfd/elf-bfd.h 17 Apr 2016 05:14:16 -0000
> @@ -1371,6 +1371,9 @@ struct elf_obj_tdata
>
> /* Used to determine if we are creating an executable. */
> bfd_boolean executable;
> +
> + /* Symbol buffer. */
> + Elf_Internal_Sym *symbuf;
> };
>
> #define elf_tdata(bfd) ((bfd) -> tdata.elf_obj_data)
> @@ -1503,11 +1506,11 @@ extern bfd_boolean _bfd_elf_match_sectio
> extern bfd_boolean bfd_elf_is_group_section
> (bfd *, const struct bfd_section *);
> extern void _bfd_elf_section_already_linked
> - (bfd *, struct bfd_section *);
> + (bfd *, struct bfd_section *, struct bfd_link_info *);
> extern void bfd_elf_set_group_contents
> (bfd *, asection *, void *);
> extern asection *_bfd_elf_check_kept_section
> - (asection *);
> + (asection *, struct bfd_link_info *);
> extern void _bfd_elf_link_just_syms
> (asection *, struct bfd_link_info *);
> extern bfd_boolean _bfd_elf_copy_private_header_data
> @@ -1703,7 +1706,7 @@ extern bfd_boolean _bfd_elf_symbol_refs_
> (struct elf_link_hash_entry *, struct bfd_link_info *, bfd_boolean);
>
> extern bfd_boolean bfd_elf_match_symbols_in_sections
> - (asection *sec1, asection *sec2);
> + (asection *, asection *, struct bfd_link_info *);
>
> extern bfd_boolean _bfd_elf_setup_sections
> (bfd *);
> Index: bfd/elf.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/elf.c,v
> retrieving revision 1.7
> diff -u -p -r1.7 elf.c
> --- bfd/elf.c 13 Jan 2015 20:05:43 -0000 1.7
> +++ bfd/elf.c 17 Apr 2016 05:14:18 -0000
> @@ -3101,7 +3101,7 @@ assign_section_numbers (bfd *abfd, struc
> s, s->owner);
> /* Point to the kept section if it has the same
> size as the discarded one. */
> - kept = _bfd_elf_check_kept_section (s);
> + kept = _bfd_elf_check_kept_section (s, link_info);
> if (kept == NULL)
> {
> bfd_set_error (bfd_error_bad_value);
> @@ -8674,7 +8674,8 @@ elf_sym_name_compare (const void *arg1,
> symbols. */
>
> bfd_boolean
> -bfd_elf_match_symbols_in_sections (asection *sec1, asection *sec2)
> +bfd_elf_match_symbols_in_sections (asection *sec1, asection *sec2,
> + struct bfd_link_info *info)
> {
> bfd *bfd1, *bfd2;
> const struct elf_backend_data *bed1, *bed2;
> @@ -8732,21 +8733,37 @@ bfd_elf_match_symbols_in_sections (asect
> if (symcount1 == 0 || symcount2 == 0)
> return FALSE;
>
> - isymbuf1 = bfd_elf_get_elf_syms (bfd1, hdr1, symcount1, 0,
> - NULL, NULL, NULL);
> - isymbuf2 = bfd_elf_get_elf_syms (bfd2, hdr2, symcount2, 0,
> - NULL, NULL, NULL);
> -
> result = FALSE;
> - if (isymbuf1 == NULL || isymbuf2 == NULL)
> - goto done;
> + isymbuf1 = elf_tdata (bfd1)->symbuf;
> + isymbuf2 = elf_tdata (bfd2)->symbuf;
>
> - /* Sort symbols by binding and section. Global definitions are at
> - the beginning. */
> - qsort (isymbuf1, symcount1, sizeof (Elf_Internal_Sym),
> - elf_sort_elf_symbol);
> - qsort (isymbuf2, symcount2, sizeof (Elf_Internal_Sym),
> - elf_sort_elf_symbol);
> + if (isymbuf1 == NULL)
> + {
> + isymbuf1 = bfd_elf_get_elf_syms (bfd1, hdr1, symcount1, 0,
> + NULL, NULL, NULL);
> + if (isymbuf1 == NULL)
> + goto done;
> + /* Sort symbols by binding and section. Global definitions are at
> + the beginning. */
> + qsort (isymbuf1, symcount1, sizeof (Elf_Internal_Sym),
> + elf_sort_elf_symbol);
> + if (!info->reduce_memory_overheads)
> + elf_tdata (bfd1)->symbuf = isymbuf1;
> + }
> +
> + if (isymbuf2 == NULL)
> + {
> + isymbuf2 = bfd_elf_get_elf_syms (bfd2, hdr2, symcount2, 0,
> + NULL, NULL, NULL);
> + if (isymbuf2 == NULL)
> + goto done;
> + /* Sort symbols by binding and section. Global definitions are at
> + the beginning. */
> + qsort (isymbuf2, symcount2, sizeof (Elf_Internal_Sym),
> + elf_sort_elf_symbol);
> + if (!info->reduce_memory_overheads)
> + elf_tdata (bfd2)->symbuf = isymbuf2;
> + }
>
> /* Count definitions in the section. */
> count1 = 0;
> @@ -8830,10 +8847,13 @@ done:
> free (symtable1);
> if (symtable2)
> free (symtable2);
> - if (isymbuf1)
> - free (isymbuf1);
> - if (isymbuf2)
> - free (isymbuf2);
> + if (info->reduce_memory_overheads)
> + {
> + if (isymbuf1)
> + free (isymbuf1);
> + if (isymbuf2)
> + free (isymbuf2);
> + }
>
> return result;
> }
> Index: bfd/elflink.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/elflink.c,v
> retrieving revision 1.12
> diff -u -p -r1.12 elflink.c
> --- bfd/elflink.c 28 Nov 2015 11:32:33 -0000 1.12
> +++ bfd/elflink.c 17 Apr 2016 05:14:20 -0000
> @@ -6766,14 +6766,15 @@ _bfd_elf_default_action_discarded (asect
> /* Find a match between a section and a member of a section group. */
>
> static asection *
> -match_group_member (asection *sec, asection *group)
> +match_group_member (asection *sec, asection *group,
> + struct bfd_link_info *info)
> {
> asection *first = elf_next_in_group (group);
> asection *s = first;
>
> while (s != NULL)
> {
> - if (bfd_elf_match_symbols_in_sections (s, sec))
> + if (bfd_elf_match_symbols_in_sections (s, sec, info))
> return s;
>
> s = elf_next_in_group (s);
> @@ -6789,7 +6790,7 @@ match_group_member (asection *sec, asect
> NULL. */
>
> asection *
> -_bfd_elf_check_kept_section (asection *sec)
> +_bfd_elf_check_kept_section (asection *sec, struct bfd_link_info *info)
> {
> asection *kept;
>
> @@ -6797,7 +6798,7 @@ _bfd_elf_check_kept_section (asection *s
> if (kept != NULL)
> {
> if (elf_sec_group (sec) != NULL)
> - kept = match_group_member (sec, kept);
> + kept = match_group_member (sec, kept, info);
> if (kept != NULL && sec->size != kept->size)
> kept = NULL;
> }
> @@ -7150,7 +7151,8 @@ elf_link_input_bfd (struct elf_final_lin
> {
> asection *kept;
>
> - kept = _bfd_elf_check_kept_section (sec);
> + kept = _bfd_elf_check_kept_section (sec,
> + finfo->info);
> if (kept != NULL)
> {
> *ps = kept;
> @@ -8280,6 +8282,15 @@ bfd_elf_final_link (bfd *abfd, struct bf
> }
> }
>
> + /* Free symbol buffer if needed. */
> + if (!info->reduce_memory_overheads)
> + {
> + for (sub = info->input_bfds; sub != NULL; sub = sub->link_next)
> + if (elf_tdata (sub)->symbuf)
> + free (elf_tdata (sub)->symbuf);
> + }
> +
> +
> /* Output any global symbols that got converted to local in a
> version script or due to symbol visibility. We do this in a
> separate step since ELF requires all local symbols to appear
> @@ -9724,7 +9735,8 @@ bfd_elf_discard_info (bfd *output_bfd, s
> }
>
> void
> -_bfd_elf_section_already_linked (bfd *abfd, struct bfd_section * sec)
> +_bfd_elf_section_already_linked (bfd *abfd, struct bfd_section *sec,
> + struct bfd_link_info *info)
> {
> flagword flags;
> const char *name, *p;
> @@ -9890,7 +9902,8 @@ _bfd_elf_section_already_linked (bfd *ab
> if ((l->sec->flags & SEC_GROUP) == 0
> && bfd_coff_get_comdat_section (l->sec->owner, l->sec) == NULL
> && bfd_elf_match_symbols_in_sections (l->sec,
> - elf_next_in_group (sec)))
> + elf_next_in_group (sec),
> + info))
> {
> elf_next_in_group (sec)->output_section = bfd_abs_section_ptr;
> elf_next_in_group (sec)->kept_section = l->sec;
> @@ -9911,7 +9924,7 @@ _bfd_elf_section_already_linked (bfd *ab
>
> if (first != NULL
> && elf_next_in_group (first) == first
> - && bfd_elf_match_symbols_in_sections (first, sec))
> + && bfd_elf_match_symbols_in_sections (first, sec, info))
> {
> sec->output_section = bfd_abs_section_ptr;
> sec->kept_section = l->sec;
> Index: bfd/libbfd-in.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/libbfd-in.h,v
> retrieving revision 1.3
> diff -u -p -r1.3 libbfd-in.h
> --- bfd/libbfd-in.h 10 May 2015 20:41:19 -0000 1.3
> +++ bfd/libbfd-in.h 17 Apr 2016 05:14:20 -0000
> @@ -408,7 +408,7 @@ extern bfd_boolean _bfd_generic_set_sect
> #define _bfd_nolink_bfd_link_split_section \
> ((bfd_boolean (*) (bfd *, struct bfd_section *)) bfd_false)
> #define _bfd_nolink_section_already_linked \
> - ((void (*) (bfd *, struct bfd_section *)) bfd_void)
> + ((void (*) (bfd *, struct bfd_section *, struct bfd_link_info *)) bfd_void)
>
> /* Routines to use for BFD_JUMP_TABLE_DYNAMIC for targets which do not
> have dynamic symbols or relocs. Use BFD_JUMP_TABLE_DYNAMIC
> @@ -522,7 +522,7 @@ extern bfd_boolean _bfd_generic_link_spl
> (bfd *, struct bfd_section *);
>
> extern void _bfd_generic_section_already_linked
> - (bfd *, struct bfd_section *);
> + (bfd *, struct bfd_section *, struct bfd_link_info *);
>
> /* Generic reloc_link_order processing routine. */
> extern bfd_boolean _bfd_generic_reloc_link_order
> Index: bfd/libbfd.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/libbfd.h,v
> retrieving revision 1.4
> diff -u -p -r1.4 libbfd.h
> --- bfd/libbfd.h 25 May 2015 14:56:26 -0000 1.4
> +++ bfd/libbfd.h 17 Apr 2016 05:14:21 -0000
> @@ -413,7 +413,7 @@ extern bfd_boolean _bfd_generic_set_sect
> #define _bfd_nolink_bfd_link_split_section \
> ((bfd_boolean (*) (bfd *, struct bfd_section *)) bfd_false)
> #define _bfd_nolink_section_already_linked \
> - ((void (*) (bfd *, struct bfd_section *)) bfd_void)
> + ((void (*) (bfd *, struct bfd_section *, struct bfd_link_info *)) bfd_void)
>
> /* Routines to use for BFD_JUMP_TABLE_DYNAMIC for targets which do not
> have dynamic symbols or relocs. Use BFD_JUMP_TABLE_DYNAMIC
> @@ -527,7 +527,7 @@ extern bfd_boolean _bfd_generic_link_spl
> (bfd *, struct bfd_section *);
>
> extern void _bfd_generic_section_already_linked
> - (bfd *, struct bfd_section *);
> + (bfd *, struct bfd_section *, struct bfd_link_info *);
>
> /* Generic reloc_link_order processing routine. */
> extern bfd_boolean _bfd_generic_reloc_link_order
> Index: bfd/linker.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/linker.c,v
> retrieving revision 1.1.1.1
> diff -u -p -r1.1.1.1 linker.c
> --- bfd/linker.c 24 Apr 2011 20:14:42 -0000 1.1.1.1
> +++ bfd/linker.c 17 Apr 2016 05:14:22 -0000
> @@ -2877,14 +2877,15 @@ FUNCTION
> bfd_section_already_linked
>
> SYNOPSIS
> - void bfd_section_already_linked (bfd *abfd, asection *sec);
> + void bfd_section_already_linked (bfd *abfd, asection *sec,
> + struct bfd_link_info *info);
>
> DESCRIPTION
> Check if @var{sec} has been already linked during a reloceatable
> or final link.
>
> -.#define bfd_section_already_linked(abfd, sec) \
> -. BFD_SEND (abfd, _section_already_linked, (abfd, sec))
> +.#define bfd_section_already_linked(abfd, sec, info) \
> +. BFD_SEND (abfd, _section_already_linked, (abfd, sec, info))
> .
>
> */
> @@ -2970,7 +2971,8 @@ bfd_section_already_linked_table_free (v
> /* This is used on non-ELF inputs. */
>
> void
> -_bfd_generic_section_already_linked (bfd *abfd, asection *sec)
> +_bfd_generic_section_already_linked (bfd *abfd, asection *sec,
> + struct bfd_link_info *info
> ATTRIBUTE_UNUSED)
> {
> flagword flags;
> const char *name;
> Index: bfd/targets.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/bfd/targets.c,v
> retrieving revision 1.3
> diff -u -p -r1.3 targets.c
> --- bfd/targets.c 6 Apr 2015 18:30:22 -0000 1.3
> +++ bfd/targets.c 17 Apr 2016 05:14:22 -0000
> @@ -481,7 +481,8 @@ BFD_JUMP_TABLE macros.
> .
> . {* Check if SEC has been already linked during a reloceatable or
> . final link. *}
> -. void (*_section_already_linked) (bfd *, struct bfd_section *);
> +. void (*_section_already_linked) (bfd *, struct bfd_section *,
> +. struct bfd_link_info *);
> .
> . {* Routines to handle dynamic symbols and relocs. *}
> .#define BFD_JUMP_TABLE_DYNAMIC(NAME) \
> Index: include/bfdlink.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/include/bfdlink.h,v
> retrieving revision 1.3
> diff -u -p -r1.3 bfdlink.h
> --- include/bfdlink.h 25 Aug 2015 02:24:50 -0000 1.3
> +++ include/bfdlink.h 17 Apr 2016 05:14:23 -0000
> @@ -324,6 +324,11 @@ struct bfd_link_info
> /* TRUE if unreferenced sections should be removed. */
> unsigned int gc_sections: 1;
>
> + /* If TRUE reduce memory overheads, at the expense of speed. This will
> + cause map file generation to use an O(N^2) algorithm and disable
> + caching ELF symbol buffer. */
> + unsigned int reduce_memory_overheads: 1;
> +
> /* What to do with unresolved symbols in an object file.
> When producing executables the default is GENERATE_ERROR.
> When producing shared libraries the default is IGNORE. The
> Index: ld/ld.h
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/ld/ld.h,v
> retrieving revision 1.2
> diff -u -p -r1.2 ld.h
> --- ld/ld.h 24 Apr 2011 20:19:25 -0000 1.2
> +++ ld/ld.h 17 Apr 2016 05:14:23 -0000
> @@ -200,11 +200,6 @@ typedef struct {
> behaviour of the linker. The new default behaviour is to reject such
> input files. */
> bfd_boolean accept_unknown_input_arch;
> -
> - /* If TRUE reduce memory overheads, at the expense of speed.
> - This will cause map file generation to use an O(N^2) algorithm. */
> - bfd_boolean reduce_memory_overheads;
> -
> } args_type;
>
> extern args_type command_line;
> Index: ld/ldlang.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/ld/ldlang.c,v
> retrieving revision 1.3
> diff -u -p -r1.3 ldlang.c
> --- ld/ldlang.c 25 Aug 2015 02:24:50 -0000 1.3
> +++ ld/ldlang.c 17 Apr 2016 05:14:24 -0000
> @@ -1670,7 +1670,7 @@ lang_map (void)
>
> fprintf (config.map_file, _("\nLinker script and memory map\n\n"));
>
> - if (! command_line.reduce_memory_overheads)
> + if (! link_info.reduce_memory_overheads)
> {
> obstack_begin (&map_obstack, 1000);
> for (p = link_info.input_bfds; p != (bfd *) NULL; p = p->link_next)
> @@ -1746,7 +1746,7 @@ init_os (lang_output_section_statement_t
> }
> s->bfd_section->output_section = s->bfd_section;
> s->bfd_section->output_offset = 0;
> - if (!command_line.reduce_memory_overheads)
> + if (!link_info.reduce_memory_overheads)
> {
> fat_section_userdata_type *new
> = stat_alloc (sizeof (fat_section_userdata_type));
> @@ -1840,7 +1840,7 @@ section_already_linked (bfd *abfd, asect
> }
>
> if (!(abfd->flags & DYNAMIC))
> - bfd_section_already_linked (abfd, sec);
> + bfd_section_already_linked (abfd, sec, &link_info);
> }
>
> /* The wild routines.
> @@ -3564,7 +3564,7 @@ print_input_section (asection *i)
>
> if (i->output_section != NULL && i->output_section->owner ==
> output_bfd)
> {
> - if (command_line.reduce_memory_overheads)
> + if (link_info.reduce_memory_overheads)
> bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
> else
> print_all_symbols (i);
> Index: ld/ldmain.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/ld/ldmain.c,v
> retrieving revision 1.7
> diff -u -p -r1.7 ldmain.c
> --- ld/ldmain.c 13 Nov 2015 16:14:37 -0000 1.7
> +++ ld/ldmain.c 17 Apr 2016 05:14:25 -0000
> @@ -261,7 +261,6 @@ main (int argc, char **argv)
> command_line.warn_mismatch = TRUE;
> command_line.check_section_addresses = TRUE;
> command_line.accept_unknown_input_arch = FALSE;
> - command_line.reduce_memory_overheads = FALSE;
>
> sort_section = none;
>
> @@ -325,6 +324,7 @@ main (int argc, char **argv)
> link_info.relax_pass = 1;
> link_info.warn_shared_textrel = FALSE;
> link_info.gc_sections = FALSE;
> + link_info.reduce_memory_overheads = FALSE;
>
> ldfile_add_arch ("");
>
> Index: ld/lexsup.c
> ===================================================================
> RCS file: /cvs/src/gnu/usr.bin/binutils-2.17/ld/lexsup.c,v
> retrieving revision 1.7
> diff -u -p -r1.7 lexsup.c
> --- ld/lexsup.c 25 Aug 2015 02:24:50 -0000 1.7
> +++ ld/lexsup.c 17 Apr 2016 05:14:25 -0000
> @@ -1350,7 +1350,7 @@ parse_args (unsigned argc, char **argv)
> break;
>
> case OPTION_REDUCE_MEMORY_OVERHEADS:
> - command_line.reduce_memory_overheads = TRUE;
> + link_info.reduce_memory_overheads = TRUE;
> if (config.hash_table_size == 0)
> config.hash_table_size = 1021;
> break;
>
