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! 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;
