* PATCH: Use a double section list to speed up linker by 30% @ 2005-05-01 16:57 H. J. Lu 2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu ` (2 more replies) 0 siblings, 3 replies; 14+ messages in thread From: H. J. Lu @ 2005-05-01 16:57 UTC (permalink / raw) To: binutils Linker is very slow on input files with many sections. The 64k section test is only enabled for CRIS. I did a profile. 70% of linker time is spent in lang_check_section_addresses: Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls Ks/call Ks/call name 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1 The main problem is we use a single section list. We have to scan the whole list for anything. In case of address overlap check, we only need to check the previous section. There are many other places in bfd, assembler and linker where a double section list will help. With this patch, I got 30% linker speed up in 64k section test: The old linker: sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total The new linker: sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total The profile data shows: Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup I will work on lang_output_section_find_1 next. I am planning to use a hash table. I hope to enable 64k section on all ELF targets. I know some people have concerns over memory usage. But I will take a faster linker with a bigger memory footprint than a slower linker any day. I am planning to include it in the Linux binutils if it isn't in the FSF binutils. H.J. ---- bfd/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * bfd.c (bfd): Remove section_tail and add section_last. (bfd_preserve): Likewise. (bfd_preserve_save): Likewise. (bfd_preserve_restore): Likewise. * opncls.c (_bfd_new_bfd): Likewise. * linker.c (bfd_new_link_order): Reuse link_order_input. (bfd_new_input_link_order): New. (_bfd_default_link_order): Ignore bfd_input_link_order. * section.c (bfd_section): Add prev. (bfd_section_double_list_remove): New. (bfd_section_list_remove): Updated. (bfd_section_double_list_append): New. (bfd_section_double_list_insert_after): New. (bfd_section_list_insert): Updated. (bfd_section_double_list_insert_before): New. (bfd_section_removed_from_list): Updated. (STD_SECTION): Initialize prev. (bfd_section_init): Updated. (bfd_section_list_clear): Updated. * coffcode.h (coff_compute_section_file_positions): Updated. * xcofflink.c (_bfd_xcoff_bfd_final_link): Updated. * bfd-in2.h: Regenerated. gas/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * write.c (write_object_file): Use bfd_section_double_list_remove to remove sections. ld/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section): Use bfd_section_double_list_remove to remove sections. * ldlang.c (lang_insert_orphan): Likewise. (strip_excluded_or_unused_output_sections): Likewise. (lang_check_section_addresses): Only check the previous section for overlap. --- binutils/bfd/bfd.c.dbl 2005-01-19 09:06:06.000000000 -0800 +++ binutils/bfd/bfd.c 2005-05-01 08:09:56.000000000 -0700 @@ -111,8 +111,8 @@ CODE_FRAGMENT . {* Pointer to linked list of sections. *} . struct bfd_section *sections; . -. {* The place where we add to the section list. *} -. struct bfd_section **section_tail; +. {* The last section on the section list. *} +. struct bfd_section *section_last; . . {* The number of sections. *} . unsigned int section_count; @@ -1390,7 +1390,7 @@ CODE_FRAGMENT . flagword flags; . const struct bfd_arch_info *arch_info; . struct bfd_section *sections; -. struct bfd_section **section_tail; +. struct bfd_section *section_last; . unsigned int section_count; . struct bfd_hash_table section_htab; .}; @@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd preserve->arch_info = abfd->arch_info; preserve->flags = abfd->flags; preserve->sections = abfd->sections; - preserve->section_tail = abfd->section_tail; + preserve->section_last = abfd->section_last; preserve->section_count = abfd->section_count; preserve->section_htab = abfd->section_htab; @@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd abfd->arch_info = &bfd_default_arch_struct; abfd->flags &= BFD_IN_MEMORY; abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; return TRUE; @@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct abfd->flags = preserve->flags; abfd->section_htab = preserve->section_htab; abfd->sections = preserve->sections; - abfd->section_tail = preserve->section_tail; + abfd->section_last = preserve->section_last; abfd->section_count = preserve->section_count; /* bfd_release frees all memory more recently bfd_alloc'd than --- binutils/bfd/coffcode.h.dbl 2005-04-21 10:09:46.000000000 -0700 +++ binutils/bfd/coffcode.h 2005-05-01 08:09:56.000000000 -0700 @@ -3033,11 +3033,12 @@ coff_compute_section_file_positions (bfd /* Rethread the linked list into sorted order; at the same time, assign target_index values. */ target_index = 1; - abfd->sections = section_list[0]; + abfd->sections = NULL; + abfd->section_last = NULL; for (i = 0; i < count; i++) { current = section_list[i]; - current->next = section_list[i + 1]; + bfd_section_double_list_append (abfd, current); /* Later, if the section has zero size, we'll be throwing it away, so we don't want to number it now. Note that having @@ -3056,7 +3057,6 @@ coff_compute_section_file_positions (bfd else current->target_index = target_index++; } - abfd->section_tail = ¤t->next; free (section_list); } --- binutils/bfd/opncls.c.dbl 2005-03-13 21:36:48.000000000 -0800 +++ binutils/bfd/opncls.c 2005-05-01 08:09:56.000000000 -0700 @@ -77,7 +77,7 @@ _bfd_new_bfd (void) return NULL; } nbfd->sections = NULL; - nbfd->section_tail = &nbfd->sections; + nbfd->section_last = NULL; nbfd->format = bfd_unknown; nbfd->my_archive = NULL; nbfd->origin = 0; --- binutils/bfd/section.c.dbl 2005-04-30 15:00:46.000000000 -0700 +++ binutils/bfd/section.c 2005-05-01 08:09:56.000000000 -0700 @@ -164,6 +164,9 @@ CODE_FRAGMENT . {* The next section in the list belonging to the BFD, or NULL. *} . struct bfd_section *next; . +. {* The previous section in the list belonging to the BFD, or NULL. *} +. struct bfd_section *prev; +. . {* The field flags contains attributes of the section. Some . flags are read in from the object file, and some are . synthesized from other information. *} @@ -548,31 +551,87 @@ CODE_FRAGMENT .{* Macros to handle insertion and deletion of a bfd's sections. These . only handle the list pointers, ie. do not adjust section_count, . target_index etc. *} +.#define bfd_section_double_list_remove(ABFD, S) \ +. do \ +. { \ +. asection *_s = S; \ +. asection *_next = _s->next; \ +. asection *_prev = _s->prev; \ +. if (_prev) \ +. _prev->next = _next; \ +. else \ +. (ABFD)->sections = _next; \ +. if (_next) \ +. { \ +. _next->prev = _prev; \ +. _s->next = NULL; \ +. } \ +. else \ +. (ABFD)->section_last = _prev; \ +. } \ +. while (0) .#define bfd_section_list_remove(ABFD, PS) \ +. bfd_section_double_list_remove ((ABFD), *(PS)) +.#define bfd_section_double_list_append(ABFD, S) \ +. do \ +. { \ +. asection *_s = S; \ +. bfd *_abfd = ABFD; \ +. _s->next = NULL; \ +. if (_abfd->section_last) \ +. { \ +. _s->prev = _abfd->section_last; \ +. _abfd->section_last->next = _s; \ +. } \ +. else \ +. _abfd->sections = _s; \ +. _abfd->section_last = _s; \ +. } \ +. while (0) +.#define bfd_section_double_list_insert_after(ABFD, A, S) \ . do \ . { \ -. asection **_ps = PS; \ -. asection *_s = *_ps; \ -. *_ps = _s->next; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = _ps; \ +. asection *_a = A; \ +. asection *_s = S; \ +. if (_a) \ +. { \ +. asection *_next = _a->next; \ +. _s->next = _next; \ +. _s->prev = _a; \ +. _a->next = _s; \ +. if (_next) \ +. _s->next->prev = _s; \ +. else \ +. (ABFD)->section_last = _s; \ +. } \ . else \ -. _s->next = NULL; \ +. bfd_section_double_list_append ((ABFD), (S)); \ . } \ . while (0) -.#define bfd_section_list_insert(ABFD, PS, S) \ +.#define bfd_section_double_list_insert_before(ABFD, B, S) \ . do \ . { \ -. asection **_ps = PS; \ +. asection *_b = B; \ . asection *_s = S; \ -. _s->next = *_ps; \ -. *_ps = _s; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = &_s->next; \ +. if (_b) \ +. { \ +. asection *_prev = _b->prev; \ +. _s->prev = _prev; \ +. _s->next = _b; \ +. _b->prev = _s; \ +. if (_prev) \ +. _prev->next = _s; \ +. else \ +. (ABFD)->sections = _s; \ +. } \ +. else \ +. bfd_section_double_list_append ((ABFD), (S)); \ . } \ . while (0) -.#define bfd_section_removed_from_list(ABFD, S) \ -. ((S)->next == NULL && &(S)->next != (ABFD)->section_tail) +.#define bfd_section_list_insert(ABFD, PS, S) \ +. bfd_section_double_list_insert_before ((ABFD), *(PS), (S)) +.#define bfd_section_removed_from_list(ABFD, S) \ +. ((S)->next == NULL && (S) != (ABFD)->section_last) . */ @@ -604,8 +663,8 @@ static const asymbol global_syms[] = #define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX) \ const asymbol * const SYM = (asymbol *) &global_syms[IDX]; \ asection SEC = \ - /* name, id, index, next, flags, user_set_vma, */ \ - { NAME, IDX, 0, NULL, FLAGS, 0, \ + /* name, id, index, next, prev, flags, user_set_vma, */ \ + { NAME, IDX, 0, NULL, NULL, FLAGS, 0, \ \ /* linker_mark, linker_has_input, gc_mark, segment_mark, */ \ 0, 0, 1, 0, \ @@ -719,8 +778,7 @@ bfd_section_init (bfd *abfd, asection *n section_id++; abfd->section_count++; - *abfd->section_tail = newsect; - abfd->section_tail = &newsect->next; + bfd_section_double_list_append (abfd, newsect); return newsect; } @@ -750,7 +808,7 @@ void bfd_section_list_clear (bfd *abfd) { abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; memset (abfd->section_htab.table, 0, abfd->section_htab.size * sizeof (struct bfd_hash_entry *)); --- binutils/bfd/xcofflink.c.dbl 2005-04-11 08:54:46.000000000 -0700 +++ binutils/bfd/xcofflink.c 2005-05-01 08:09:56.000000000 -0700 @@ -5460,13 +5460,11 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st that needs padding. This requires unlinking and relinking the bfd's section list. */ - st = abfd->section_tail; n = bfd_make_section_anyway (abfd, ".pad"); n->flags = SEC_HAS_CONTENTS; n->alignment_power = 0; - BFD_ASSERT (*st == n); - bfd_section_list_remove (abfd, st); + bfd_section_double_list_remove (abfd, n); bfd_section_list_insert (abfd, op, n); op = &n->next; --- binutils/gas/write.c.dbl 2005-04-27 08:28:38.000000000 -0700 +++ binutils/gas/write.c 2005-05-01 08:09:56.000000000 -0700 @@ -1471,20 +1471,11 @@ write_object_file (void) #ifdef BFD_ASSEMBLER /* Remove the sections created by gas for its own purposes. */ { - asection **seclist; int i; - seclist = &stdoutput->sections; - while (*seclist) - { - if (*seclist == reg_section || *seclist == expr_section) - { - bfd_section_list_remove (stdoutput, seclist); - stdoutput->section_count--; - } - else - seclist = &(*seclist)->next; - } + bfd_section_double_list_remove (stdoutput, reg_section); + bfd_section_double_list_remove (stdoutput, expr_section); + stdoutput->section_count -= 2; i = 0; bfd_map_over_sections (stdoutput, renumber_sections, &i); } --- binutils/ld/emultempl/elf32.em.dbl 2005-04-30 15:00:46.000000000 -0700 +++ binutils/ld/emultempl/elf32.em 2005-05-01 08:09:56.000000000 -0700 @@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section if (os == abs_output_section || os->constraint == -1) continue; s = os->bfd_section; - if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0) + if (s != NULL + && s->size == 0 + && (s->flags & SEC_KEEP) == 0 + && !bfd_section_removed_from_list (output_bfd, s)) { - asection **p; - - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + bfd_section_double_list_remove (output_bfd, s); + output_bfd->section_count--; } } } --- binutils/ld/ldlang.c.dbl 2005-04-30 15:19:33.000000000 -0700 +++ binutils/ld/ldlang.c 2005-05-01 08:58:21.000000000 -0700 @@ -1203,7 +1203,6 @@ lang_insert_orphan (lang_input_statement etree_type *load_base; lang_output_section_statement_type *os; lang_output_section_statement_type **os_tail; - asection **bfd_tail; /* Start building a list of statements for this section. First save the current statement pointer. */ @@ -1257,7 +1256,6 @@ lang_insert_orphan (lang_input_statement os_tail = ((lang_output_section_statement_type **) lang_output_section_statement.tail); - bfd_tail = output_bfd->section_tail; os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL, load_base, 0); @@ -1316,8 +1314,8 @@ lang_insert_orphan (lang_input_statement place->section = &output_bfd->sections; /* Unlink the section. */ - ASSERT (*bfd_tail == snew); - bfd_section_list_remove (output_bfd, bfd_tail); + ASSERT (output_bfd->section_last == snew); + bfd_section_double_list_remove (output_bfd, snew); /* Now tack it back on in the right place. */ bfd_section_list_insert (output_bfd, place->section, snew); @@ -3051,8 +3049,6 @@ strip_excluded_or_unused_output_sections && s->linker_has_input == 0 && (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0))) { - asection **p; - /* We don't set bfd_section to NULL since bfd_section of the used output section may still be used. */ if (unused) @@ -3060,13 +3056,11 @@ strip_excluded_or_unused_output_sections else os->bfd_section = NULL; - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + if (!bfd_section_removed_from_list (output_bfd, s)) + { + bfd_section_double_list_remove (output_bfd, s); + output_bfd->section_count--; + } } } } @@ -3722,7 +3716,7 @@ lang_check_section_addresses (void) /* Once we reach section 's' stop our seach. This prevents two warning messages from being produced, one for 'section A overlaps section B' and one for 'section B overlaps section A'. */ - for (os = output_bfd->sections; os != s; os = os->next) + for (os = s->prev; os != NULL; os = os->prev) { bfd_vma s_start; bfd_vma s_end; @@ -3742,15 +3736,14 @@ lang_check_section_addresses (void) os_end = os_start + TO_ADDR (os->size) - 1; /* Look for an overlap. */ - if ((s_end < os_start) || (s_start > os_end)) - continue; - - einfo ( -_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), - s->name, s_start, s_end, os->name, os_start, os_end); - - /* Once we have found one overlap for this section, - stop looking for others. */ + if (s_end >= os_start && s_start <= os_end) + + einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), + s->name, s_start, s_end, os->name, os_start, os_end); + + /* We only need to check the previous section for overlap. + Once we have found one overlap for this section, stop + looking for others. */ break; } } ^ permalink raw reply [flat|nested] 14+ messages in thread
* PATCH: Use a hash table for 26X linker speedup 2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu @ 2005-05-01 19:09 ` H. J. Lu 2005-05-21 11:05 ` Christian Joensson 2005-05-01 19:48 ` PATCH: Use a double section list to speed up linker by 30% H. J. Lu 2005-05-02 0:52 ` Ben Elliston 2 siblings, 1 reply; 14+ messages in thread From: H. J. Lu @ 2005-05-01 19:09 UTC (permalink / raw) To: binutils On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > Linker is very slow on input files with many sections. The 64k section > test is only enabled for CRIS. I did a profile. 70% of linker time is > spent in lang_check_section_addresses: > > Flat profile: > > Each sample counts as 0.01 seconds. > % cumulative self self total > time seconds seconds calls Ks/call Ks/call name > 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses > 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1 > > The main problem is we use a single section list. We have to scan the > whole list for anything. In case of address overlap check, we only > need to check the previous section. There are many other places in > bfd, assembler and linker where a double section list will help. With > this patch, I got 30% linker speed up in 64k section test: > > The old linker: > > sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total > > The new linker: > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > The profile data shows: > > Flat profile: > > Each sample counts as 0.01 seconds. > % cumulative self self total > time seconds seconds calls s/call s/call name > 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1 > 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup > > I will work on lang_output_section_find_1 next. I am planning to use > a hash table. I hope to enable 64k section on all ELF targets. > This is the patch. I got sh 1 13.39s user 1.28s system 95% cpu 15.431 total vs. sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total That is a 26X speed up. I enabled 64k section test for all ELF targets. H.J. ---- ld/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * ldlang.c (output_statement_hash_entry): New type. (output_statement_table): New variable for hash table. (output_statement_newfunc): New function. (output_statement_table_init): Likewise. (output_statement_table_free): Likewise. (lang_init): Call output_statement_table_init. (lang_finish): Renamed to ... (lang_end): This. (lang_process): Updated. (lang_finish): New function. (lang_output_section_find_1): Use hash table. (lang_output_section_statement_lookup_1): Likewise. * ldlang.h (lang_finish): New. * ldmain.c (main): Call lang_finish. ld/testsuite/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * ld-elf/sec64k.exp: Enabled for all ELF targets. --- ld/ldlang.c.hash 2005-05-01 09:00:10.000000000 -0700 +++ ld/ldlang.c 2005-05-01 12:05:32.000000000 -0700 @@ -863,6 +863,45 @@ lang_add_input_file (const char *name, return new_afile (name, file_type, target, TRUE); } +struct output_statement_hash_entry +{ + struct bfd_hash_entry root; + lang_output_section_statement_type *entry; +}; + +/* The hash table. */ + +static struct bfd_hash_table output_statement_table; + +/* Support routines for the hash table used by lang_output_section_find_1, + initialize the table, fill in an entry and remove the table. */ + +static struct bfd_hash_entry * +output_statement_newfunc (struct bfd_hash_entry *entry ATTRIBUTE_UNUSED, + struct bfd_hash_table *table, + const char *string ATTRIBUTE_UNUSED) +{ + struct output_statement_hash_entry *ret + = bfd_hash_allocate (table, + sizeof (struct output_statement_hash_entry)); + ret->entry = NULL; + return (struct bfd_hash_entry *) ret; +} + +static void +output_statement_table_init (void) +{ + if (! bfd_hash_table_init_n (&output_statement_table, + output_statement_newfunc, 61)) + einfo (_("%P%F: Failed to create hash table\n")); +} + +static void +output_statement_table_free (void) +{ + bfd_hash_table_free (&output_statement_table); +} + /* Build enough state so that the parser can build its tree. */ void @@ -872,6 +911,8 @@ lang_init (void) stat_ptr = &statement_list; + output_statement_table_init (); + lang_list_init (stat_ptr); lang_list_init (&input_file_chain); @@ -898,6 +939,12 @@ lang_init (void) lang_statement_iteration = 0; } +void +lang_finish (void) +{ + output_statement_table_free (); +} + /*---------------------------------------------------------------------- A region is an area of memory declared with the MEMORY { name:org=exp, len=exp ... } @@ -983,16 +1030,28 @@ static lang_output_section_statement_typ lang_output_section_find_1 (const char *const name, int constraint) { lang_output_section_statement_type *lookup; + struct output_statement_hash_entry *entry; + unsigned long hash; - for (lookup = &lang_output_section_statement.head->output_section_statement; - lookup != NULL; - lookup = lookup->next) + entry = ((struct output_statement_hash_entry *) + bfd_hash_lookup (&output_statement_table, name, FALSE, + FALSE)); + if (entry == NULL || (lookup = entry->entry) == NULL) + return NULL; + + hash = entry->root.hash; + do { - if (strcmp (name, lookup->name) == 0 - && lookup->constraint != -1 + if (lookup->constraint != -1 && (constraint == 0 || constraint == lookup->constraint)) return lookup; + entry = (struct output_statement_hash_entry *) entry->root.next; + lookup = entry ? entry->entry : NULL; } + while (entry != NULL + && entry->root.hash == hash + && strcmp (name, lookup->name) == 0); + return NULL; } @@ -1010,6 +1069,8 @@ lang_output_section_statement_lookup_1 ( lookup = lang_output_section_find_1 (name, constraint); if (lookup == NULL) { + struct output_statement_hash_entry *entry; + lookup = new_stat (lang_output_section_statement, stat_ptr); lookup->region = NULL; lookup->lma_region = NULL; @@ -1034,6 +1095,15 @@ lang_output_section_statement_lookup_1 ( lookup->update_dot_tree = NULL; lookup->phdrs = NULL; + entry = ((struct output_statement_hash_entry *) + bfd_hash_lookup (&output_statement_table, name, TRUE, + FALSE)); + if (entry == NULL) + einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"), + name); + + entry->entry = lookup; + lang_statement_append (&lang_output_section_statement, (lang_statement_union_type *) lookup, (lang_statement_union_type **) &lookup->next); @@ -4495,7 +4565,7 @@ lang_set_startof (void) } static void -lang_finish (void) +lang_end (void) { struct bfd_link_hash_entry *h; bfd_boolean warn; @@ -5294,7 +5364,7 @@ lang_process (void) /* Final stuffs. */ ldemul_finish (); - lang_finish (); + lang_end (); } /* EXPORTED TO YACC */ --- ld/ldlang.h.hash 2005-05-01 09:00:10.000000000 -0700 +++ ld/ldlang.h 2005-05-01 11:39:36.000000000 -0700 @@ -449,6 +449,8 @@ extern int lang_statement_iteration; extern void lang_init (void); +extern void lang_finish + (void); extern lang_memory_region_type *lang_memory_region_lookup (const char *const, bfd_boolean); extern lang_memory_region_type *lang_memory_region_default --- ld/ldmain.c.hash 2005-03-16 17:37:00.000000000 -0800 +++ ld/ldmain.c 2005-05-01 11:40:39.000000000 -0700 @@ -474,6 +474,8 @@ main (int argc, char **argv) if (nocrossref_list != NULL) check_nocrossrefs (); + lang_finish (); + /* Even if we're producing relocatable output, some non-fatal errors should be reported in the exit status. (What non-fatal errors, if any, do we want to ignore for relocatable output?) */ --- ld/testsuite/ld-elf/sec64k.exp.hash 2005-03-03 08:56:35.000000000 -0800 +++ ld/testsuite/ld-elf/sec64k.exp 2005-05-01 11:50:34.000000000 -0700 @@ -24,12 +24,6 @@ if ![is_elf_format] { return } -# Per-port excludes, since this test takes an overwhelmingly long time -# currently. -if { ![istarget cris-*-*] } { - return -} - # Test >64k sections, with and without -r. First, create the assembly # files. Have a relocation to another section and one within the local # section. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup 2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu @ 2005-05-21 11:05 ` Christian Joensson 2005-05-27 16:42 ` H. J. Lu 0 siblings, 1 reply; 14+ messages in thread From: Christian Joensson @ 2005-05-21 11:05 UTC (permalink / raw) To: H. J. Lu; +Cc: binutils Whatever happened with this? /ChJ On 5/1/05, H. J. Lu <hjl@lucon.org> wrote: > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > Linker is very slow on input files with many sections. The 64k section > > test is only enabled for CRIS. I did a profile. 70% of linker time is > > spent in lang_check_section_addresses: > > > > Flat profile: > > > > Each sample counts as 0.01 seconds. > > % cumulative self self total > > time seconds seconds calls Ks/call Ks/call name > > 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses > > 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1 > > > > The main problem is we use a single section list. We have to scan the > > whole list for anything. In case of address overlap check, we only > > need to check the previous section. There are many other places in > > bfd, assembler and linker where a double section list will help. With > > this patch, I got 30% linker speed up in 64k section test: > > > > The old linker: > > > > sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total > > > > The new linker: > > > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > > > The profile data shows: > > > > Flat profile: > > > > Each sample counts as 0.01 seconds. > > % cumulative self self total > > time seconds seconds calls s/call s/call name > > 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1 > > 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup > > > > I will work on lang_output_section_find_1 next. I am planning to use > > a hash table. I hope to enable 64k section on all ELF targets. > > > > This is the patch. I got > > sh 1 13.39s user 1.28s system 95% cpu 15.431 total > > vs. > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > That is a 26X speed up. I enabled 64k section test for all ELF targets. > > > H.J. > ---- > ld/ > > 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> > > * ldlang.c (output_statement_hash_entry): New type. > (output_statement_table): New variable for hash table. > (output_statement_newfunc): New function. > (output_statement_table_init): Likewise. > (output_statement_table_free): Likewise. > (lang_init): Call output_statement_table_init. > (lang_finish): Renamed to ... > (lang_end): This. > (lang_process): Updated. > (lang_finish): New function. > (lang_output_section_find_1): Use hash table. > (lang_output_section_statement_lookup_1): Likewise. > > * ldlang.h (lang_finish): New. > > * ldmain.c (main): Call lang_finish. > > ld/testsuite/ > > 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> > > * ld-elf/sec64k.exp: Enabled for all ELF targets. > > --- ld/ldlang.c.hash 2005-05-01 09:00:10.000000000 -0700 > +++ ld/ldlang.c 2005-05-01 12:05:32.000000000 -0700 > @@ -863,6 +863,45 @@ lang_add_input_file (const char *name, > return new_afile (name, file_type, target, TRUE); > } > > +struct output_statement_hash_entry > +{ > + struct bfd_hash_entry root; > + lang_output_section_statement_type *entry; > +}; > + > +/* The hash table. */ > + > +static struct bfd_hash_table output_statement_table; > + > +/* Support routines for the hash table used by lang_output_section_find_1, > + initialize the table, fill in an entry and remove the table. */ > + > +static struct bfd_hash_entry * > +output_statement_newfunc (struct bfd_hash_entry *entry ATTRIBUTE_UNUSED, > + struct bfd_hash_table *table, > + const char *string ATTRIBUTE_UNUSED) > +{ > + struct output_statement_hash_entry *ret > + = bfd_hash_allocate (table, > + sizeof (struct output_statement_hash_entry)); > + ret->entry = NULL; > + return (struct bfd_hash_entry *) ret; > +} > + > +static void > +output_statement_table_init (void) > +{ > + if (! bfd_hash_table_init_n (&output_statement_table, > + output_statement_newfunc, 61)) > + einfo (_("%P%F: Failed to create hash table\n")); > +} > + > +static void > +output_statement_table_free (void) > +{ > + bfd_hash_table_free (&output_statement_table); > +} > + > /* Build enough state so that the parser can build its tree. */ > > void > @@ -872,6 +911,8 @@ lang_init (void) > > stat_ptr = &statement_list; > > + output_statement_table_init (); > + > lang_list_init (stat_ptr); > > lang_list_init (&input_file_chain); > @@ -898,6 +939,12 @@ lang_init (void) > lang_statement_iteration = 0; > } > > +void > +lang_finish (void) > +{ > + output_statement_table_free (); > +} > + > /*---------------------------------------------------------------------- > A region is an area of memory declared with the > MEMORY { name:org=exp, len=exp ... } > @@ -983,16 +1030,28 @@ static lang_output_section_statement_typ > lang_output_section_find_1 (const char *const name, int constraint) > { > lang_output_section_statement_type *lookup; > + struct output_statement_hash_entry *entry; > + unsigned long hash; > > - for (lookup = &lang_output_section_statement.head->output_section_statement; > - lookup != NULL; > - lookup = lookup->next) > + entry = ((struct output_statement_hash_entry *) > + bfd_hash_lookup (&output_statement_table, name, FALSE, > + FALSE)); > + if (entry == NULL || (lookup = entry->entry) == NULL) > + return NULL; > + > + hash = entry->root.hash; > + do > { > - if (strcmp (name, lookup->name) == 0 > - && lookup->constraint != -1 > + if (lookup->constraint != -1 > && (constraint == 0 || constraint == lookup->constraint)) > return lookup; > + entry = (struct output_statement_hash_entry *) entry->root.next; > + lookup = entry ? entry->entry : NULL; > } > + while (entry != NULL > + && entry->root.hash == hash > + && strcmp (name, lookup->name) == 0); > + > return NULL; > } > > @@ -1010,6 +1069,8 @@ lang_output_section_statement_lookup_1 ( > lookup = lang_output_section_find_1 (name, constraint); > if (lookup == NULL) > { > + struct output_statement_hash_entry *entry; > + > lookup = new_stat (lang_output_section_statement, stat_ptr); > lookup->region = NULL; > lookup->lma_region = NULL; > @@ -1034,6 +1095,15 @@ lang_output_section_statement_lookup_1 ( > lookup->update_dot_tree = NULL; > lookup->phdrs = NULL; > > + entry = ((struct output_statement_hash_entry *) > + bfd_hash_lookup (&output_statement_table, name, TRUE, > + FALSE)); > + if (entry == NULL) > + einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"), > + name); > + > + entry->entry = lookup; > + > lang_statement_append (&lang_output_section_statement, > (lang_statement_union_type *) lookup, > (lang_statement_union_type **) &lookup->next); > @@ -4495,7 +4565,7 @@ lang_set_startof (void) > } > > static void > -lang_finish (void) > +lang_end (void) > { > struct bfd_link_hash_entry *h; > bfd_boolean warn; > @@ -5294,7 +5364,7 @@ lang_process (void) > /* Final stuffs. */ > > ldemul_finish (); > - lang_finish (); > + lang_end (); > } > > /* EXPORTED TO YACC */ > --- ld/ldlang.h.hash 2005-05-01 09:00:10.000000000 -0700 > +++ ld/ldlang.h 2005-05-01 11:39:36.000000000 -0700 > @@ -449,6 +449,8 @@ extern int lang_statement_iteration; > > extern void lang_init > (void); > +extern void lang_finish > + (void); > extern lang_memory_region_type *lang_memory_region_lookup > (const char *const, bfd_boolean); > extern lang_memory_region_type *lang_memory_region_default > --- ld/ldmain.c.hash 2005-03-16 17:37:00.000000000 -0800 > +++ ld/ldmain.c 2005-05-01 11:40:39.000000000 -0700 > @@ -474,6 +474,8 @@ main (int argc, char **argv) > if (nocrossref_list != NULL) > check_nocrossrefs (); > > + lang_finish (); > + > /* Even if we're producing relocatable output, some non-fatal errors should > be reported in the exit status. (What non-fatal errors, if any, do we > want to ignore for relocatable output?) */ > --- ld/testsuite/ld-elf/sec64k.exp.hash 2005-03-03 08:56:35.000000000 -0800 > +++ ld/testsuite/ld-elf/sec64k.exp 2005-05-01 11:50:34.000000000 -0700 > @@ -24,12 +24,6 @@ if ![is_elf_format] { > return > } > > -# Per-port excludes, since this test takes an overwhelmingly long time > -# currently. > -if { ![istarget cris-*-*] } { > - return > -} > - > # Test >64k sections, with and without -r. First, create the assembly > # files. Have a relocation to another section and one within the local > # section. > -- Cheers, /ChJ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup 2005-05-21 11:05 ` Christian Joensson @ 2005-05-27 16:42 ` H. J. Lu 2005-05-29 11:16 ` Alan Modra 0 siblings, 1 reply; 14+ messages in thread From: H. J. Lu @ 2005-05-27 16:42 UTC (permalink / raw) To: Christian Joensson; +Cc: binutils On Sat, May 21, 2005 at 08:40:55AM +0200, Christian Joensson wrote: > Whatever happened with this? > > /ChJ > > On 5/1/05, H. J. Lu <hjl@lucon.org> wrote: > > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > > Linker is very slow on input files with many sections. The 64k section > > > test is only enabled for CRIS. I did a profile. 70% of linker time is > > > spent in lang_check_section_addresses: > > > > > > Flat profile: > > > > > > Each sample counts as 0.01 seconds. > > > % cumulative self self total > > > time seconds seconds calls Ks/call Ks/call name > > > 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses > > > 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1 > > > > > > The main problem is we use a single section list. We have to scan the > > > whole list for anything. In case of address overlap check, we only > > > need to check the previous section. There are many other places in > > > bfd, assembler and linker where a double section list will help. With > > > this patch, I got 30% linker speed up in 64k section test: > > > > > > The old linker: > > > > > > sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total > > > > > > The new linker: > > > > > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > > > > > The profile data shows: > > > > > > Flat profile: > > > > > > Each sample counts as 0.01 seconds. > > > % cumulative self self total > > > time seconds seconds calls s/call s/call name > > > 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1 > > > 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup > > > > > > I will work on lang_output_section_find_1 next. I am planning to use > > > a hash table. I hope to enable 64k section on all ELF targets. > > > > > > > This is the patch. I got > > > > sh 1 13.39s user 1.28s system 95% cpu 15.431 total > > > > vs. > > > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > > > That is a 26X speed up. I enabled 64k section test for all ELF targets. > > Here is the updated patch. I have been using this for a while. Is there any objection? H.J. ----- ld/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * ldlang.c (output_statement_hash_entry): New type. (output_statement_table): New variable for hash table. (output_statement_newfunc): New function. (output_statement_table_init): Likewise. (output_statement_table_free): Likewise. (lang_init): Call output_statement_table_init. (lang_finish): Renamed to ... (lang_end): This. (lang_process): Updated. (lang_finish): New function. (lang_output_section_find_1): Use hash table. (lang_output_section_statement_lookup_1): Likewise. * ldlang.h (lang_finish): New. * ldmain.c (main): Call lang_finish. ld/testsuite/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * ld-elf/sec64k.exp: Enabled for all ELF targets. --- ld/ldlang.c.hash 2005-05-11 08:12:08.000000000 -0700 +++ ld/ldlang.c 2005-05-11 09:14:33.000000000 -0700 @@ -864,6 +864,45 @@ lang_add_input_file (const char *name, return new_afile (name, file_type, target, TRUE); } +struct output_statement_hash_entry +{ + struct bfd_hash_entry root; + lang_output_section_statement_type *entry; +}; + +/* The hash table. */ + +static struct bfd_hash_table output_statement_table; + +/* Support routines for the hash table used by lang_output_section_find_1, + initialize the table, fill in an entry and remove the table. */ + +static struct bfd_hash_entry * +output_statement_newfunc (struct bfd_hash_entry *entry ATTRIBUTE_UNUSED, + struct bfd_hash_table *table, + const char *string ATTRIBUTE_UNUSED) +{ + struct output_statement_hash_entry *ret + = bfd_hash_allocate (table, + sizeof (struct output_statement_hash_entry)); + ret->entry = NULL; + return (struct bfd_hash_entry *) ret; +} + +static void +output_statement_table_init (void) +{ + if (! bfd_hash_table_init_n (&output_statement_table, + output_statement_newfunc, 61)) + einfo (_("%P%F: Failed to create hash table\n")); +} + +static void +output_statement_table_free (void) +{ + bfd_hash_table_free (&output_statement_table); +} + /* Build enough state so that the parser can build its tree. */ void @@ -873,6 +912,8 @@ lang_init (void) stat_ptr = &statement_list; + output_statement_table_init (); + lang_list_init (stat_ptr); lang_list_init (&input_file_chain); @@ -899,6 +940,12 @@ lang_init (void) lang_statement_iteration = 0; } +void +lang_finish (void) +{ + output_statement_table_free (); +} + /*---------------------------------------------------------------------- A region is an area of memory declared with the MEMORY { name:org=exp, len=exp ... } @@ -984,18 +1031,30 @@ static lang_output_section_statement_typ lang_output_section_find_1 (const char *const name, int constraint) { lang_output_section_statement_type *lookup; + struct output_statement_hash_entry *entry; + unsigned long hash; - for (lookup = &lang_output_section_statement.head->output_section_statement; - lookup != NULL; - lookup = lookup->next) + entry = ((struct output_statement_hash_entry *) + bfd_hash_lookup (&output_statement_table, name, FALSE, + FALSE)); + if (entry == NULL || (lookup = entry->entry) == NULL) + return NULL; + + hash = entry->root.hash; + do { - if (strcmp (name, lookup->name) == 0 - && lookup->constraint != -1 + if (lookup->constraint != -1 && (constraint == 0 || (constraint == lookup->constraint && constraint != SPECIAL))) return lookup; + entry = (struct output_statement_hash_entry *) entry->root.next; + lookup = entry ? entry->entry : NULL; } + while (entry != NULL + && entry->root.hash == hash + && strcmp (name, lookup->name) == 0); + return NULL; } @@ -1013,6 +1072,8 @@ lang_output_section_statement_lookup_1 ( lookup = lang_output_section_find_1 (name, constraint); if (lookup == NULL) { + struct output_statement_hash_entry *entry; + lookup = new_stat (lang_output_section_statement, stat_ptr); lookup->region = NULL; lookup->lma_region = NULL; @@ -1036,6 +1097,15 @@ lang_output_section_statement_lookup_1 ( lookup->update_dot_tree = NULL; lookup->phdrs = NULL; + entry = ((struct output_statement_hash_entry *) + bfd_hash_lookup (&output_statement_table, name, TRUE, + FALSE)); + if (entry == NULL) + einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"), + name); + + entry->entry = lookup; + lang_statement_append (&lang_output_section_statement, (lang_statement_union_type *) lookup, (lang_statement_union_type **) &lookup->next); @@ -4546,7 +4616,7 @@ lang_set_startof (void) } static void -lang_finish (void) +lang_end (void) { struct bfd_link_hash_entry *h; bfd_boolean warn; @@ -5332,7 +5402,7 @@ lang_process (void) /* Final stuffs. */ lang_mark_used_section (); ldemul_finish (); - lang_finish (); + lang_end (); } /* EXPORTED TO YACC */ --- ld/ldlang.h.hash 2005-05-04 08:52:34.000000000 -0700 +++ ld/ldlang.h 2005-05-11 08:13:47.000000000 -0700 @@ -448,6 +448,8 @@ extern int lang_statement_iteration; extern void lang_init (void); +extern void lang_finish + (void); extern lang_memory_region_type *lang_memory_region_lookup (const char *const, bfd_boolean); extern lang_memory_region_type *lang_memory_region_default --- ld/ldmain.c.hash 2005-05-11 08:12:08.000000000 -0700 +++ ld/ldmain.c 2005-05-11 08:13:47.000000000 -0700 @@ -474,6 +474,8 @@ main (int argc, char **argv) if (nocrossref_list != NULL) check_nocrossrefs (); + lang_finish (); + /* Even if we're producing relocatable output, some non-fatal errors should be reported in the exit status. (What non-fatal errors, if any, do we want to ignore for relocatable output?) */ --- ld/testsuite/ld-elf/sec64k.exp.hash 2005-03-03 08:56:35.000000000 -0800 +++ ld/testsuite/ld-elf/sec64k.exp 2005-05-11 08:13:47.000000000 -0700 @@ -24,12 +24,6 @@ if ![is_elf_format] { return } -# Per-port excludes, since this test takes an overwhelmingly long time -# currently. -if { ![istarget cris-*-*] } { - return -} - # Test >64k sections, with and without -r. First, create the assembly # files. Have a relocation to another section and one within the local # section. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup 2005-05-27 16:42 ` H. J. Lu @ 2005-05-29 11:16 ` Alan Modra 0 siblings, 0 replies; 14+ messages in thread From: Alan Modra @ 2005-05-29 11:16 UTC (permalink / raw) To: H. J. Lu; +Cc: Christian Joensson, binutils On Fri, May 27, 2005 at 09:41:02AM -0700, H. J. Lu wrote: > > > > I will work on lang_output_section_find_1 next. I am planning to use > > > > a hash table. I hope to enable 64k section on all ELF targets. > > Here is the updated patch. I have been using this for a while. Is there > any objection? I think I made this comment before: It seems wasteful to have two hash tables working with virtually the same set of data. We have a section hash table holding output section names, and you're adding another hash table to hold output_section_statement names. I realize the two aren't identical, but all orphans will be in both tables (and it is our orphan section handling that makes the output_section_statement list so long). I'd prefer if you don't commit this patch, at least until I've had time to look at changing orphan section handling. -- Alan Modra IBM OzLabs - Linux Technology Centre ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu 2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu @ 2005-05-01 19:48 ` H. J. Lu 2005-05-02 5:17 ` Alan Modra 2005-05-02 0:52 ` Ben Elliston 2 siblings, 1 reply; 14+ messages in thread From: H. J. Lu @ 2005-05-01 19:48 UTC (permalink / raw) To: binutils On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > Linker is very slow on input files with many sections. The 64k section > test is only enabled for CRIS. I did a profile. 70% of linker time is > spent in lang_check_section_addresses: > > Flat profile: > > Each sample counts as 0.01 seconds. > % cumulative self self total > time seconds seconds calls Ks/call Ks/call name > 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses > 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1 > > The main problem is we use a single section list. We have to scan the > whole list for anything. In case of address overlap check, we only > need to check the previous section. There are many other places in > bfd, assembler and linker where a double section list will help. With > this patch, I got 30% linker speed up in 64k section test: > > The old linker: > > sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total > > The new linker: > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > The profile data shows: > > Flat profile: > > Each sample counts as 0.01 seconds. > % cumulative self self total > time seconds seconds calls s/call s/call name > 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1 > 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup > This is the updated patch to fix build on MIPS and ia64. H.J. --- bfd/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * bfd.c (bfd): Remove section_tail and add section_last. (bfd_preserve): Likewise. (bfd_preserve_save): Likewise. (bfd_preserve_restore): Likewise. * opncls.c (_bfd_new_bfd): Likewise. * elfxx-ia64.c (elfNN_ia64_object_p): Use bfd_section_double_list_remove to remove sections. * section.c (bfd_section): Add prev. (bfd_section_double_list_remove): New. (bfd_section_list_remove): Updated. (bfd_section_double_list_append): New. (bfd_section_double_list_insert_after): New. (bfd_section_list_insert): Updated. (bfd_section_double_list_insert_before): New. (bfd_section_removed_from_list): Updated. (STD_SECTION): Initialize prev. (bfd_section_init): Updated. (bfd_section_list_clear): Updated. * coffcode.h (coff_compute_section_file_positions): Updated. * xcofflink.c (_bfd_xcoff_bfd_final_link): Updated. * ecoff.c (bfd_debug_section): Initialize prev. * bfd-in2.h: Regenerated. gas/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * write.c (write_object_file): Use bfd_section_double_list_remove to remove sections. ld/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section): Use bfd_section_double_list_remove to remove sections. * ldlang.c (lang_insert_orphan): Likewise. (strip_excluded_or_unused_output_sections): Likewise. (lang_check_section_addresses): Only check the previous section for overlap. --- binutils/bfd/bfd.c.dbl 2005-03-17 20:10:19.000000000 -0800 +++ binutils/bfd/bfd.c 2005-05-01 09:00:10.000000000 -0700 @@ -111,8 +111,8 @@ CODE_FRAGMENT . {* Pointer to linked list of sections. *} . struct bfd_section *sections; . -. {* The place where we add to the section list. *} -. struct bfd_section **section_tail; +. {* The last section on the section list. *} +. struct bfd_section *section_last; . . {* The number of sections. *} . unsigned int section_count; @@ -1390,7 +1390,7 @@ CODE_FRAGMENT . flagword flags; . const struct bfd_arch_info *arch_info; . struct bfd_section *sections; -. struct bfd_section **section_tail; +. struct bfd_section *section_last; . unsigned int section_count; . struct bfd_hash_table section_htab; .}; @@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd preserve->arch_info = abfd->arch_info; preserve->flags = abfd->flags; preserve->sections = abfd->sections; - preserve->section_tail = abfd->section_tail; + preserve->section_last = abfd->section_last; preserve->section_count = abfd->section_count; preserve->section_htab = abfd->section_htab; @@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd abfd->arch_info = &bfd_default_arch_struct; abfd->flags &= BFD_IN_MEMORY; abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; return TRUE; @@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct abfd->flags = preserve->flags; abfd->section_htab = preserve->section_htab; abfd->sections = preserve->sections; - abfd->section_tail = preserve->section_tail; + abfd->section_last = preserve->section_last; abfd->section_count = preserve->section_count; /* bfd_release frees all memory more recently bfd_alloc'd than --- binutils/bfd/coffcode.h.dbl 2005-04-21 09:57:50.000000000 -0700 +++ binutils/bfd/coffcode.h 2005-05-01 09:00:10.000000000 -0700 @@ -3033,11 +3033,12 @@ coff_compute_section_file_positions (bfd /* Rethread the linked list into sorted order; at the same time, assign target_index values. */ target_index = 1; - abfd->sections = section_list[0]; + abfd->sections = NULL; + abfd->section_last = NULL; for (i = 0; i < count; i++) { current = section_list[i]; - current->next = section_list[i + 1]; + bfd_section_double_list_append (abfd, current); /* Later, if the section has zero size, we'll be throwing it away, so we don't want to number it now. Note that having @@ -3056,7 +3057,6 @@ coff_compute_section_file_positions (bfd else current->target_index = target_index++; } - abfd->section_tail = ¤t->next; free (section_list); } --- binutils/bfd/ecoff.c.dbl 2005-03-16 09:21:29.000000000 -0800 +++ binutils/bfd/ecoff.c 2005-05-01 12:12:40.000000000 -0700 @@ -52,8 +52,8 @@ /* This stuff is somewhat copied from coffcode.h. */ static asection bfd_debug_section = { - /* name, id, index, next, flags, user_set_vma, */ - "*DEBUG*", 0, 0, NULL, 0, 0, + /* name, id, index, next, prev, flags, user_set_vma, */ + "*DEBUG*", 0, 0, NULL, NULL, 0, 0, /* linker_mark, linker_has_input, gc_mark, segment_mark, */ 0, 0, 0, 0, /* sec_info_type, use_rela_p, has_tls_reloc, has_gp_reloc, */ --- binutils/bfd/elfxx-ia64.c.dbl 2005-04-28 12:00:14.000000000 -0700 +++ binutils/bfd/elfxx-ia64.c 2005-05-01 12:20:07.000000000 -0700 @@ -4885,7 +4885,6 @@ static bfd_boolean elfNN_ia64_object_p (bfd *abfd) { asection *sec; - asection **tail; asection *group, *unwi, *unw; flagword flags; const char *name; @@ -4926,8 +4925,6 @@ elfNN_ia64_object_p (bfd *abfd) strcpy (stpcpy (unw_name, ".gnu.linkonce.ia64unw."), name); unw = bfd_get_section_by_name (abfd, unw_name); - tail = abfd->section_tail; - /* We need to create a fake group section for it and its unwind sections. */ group = bfd_make_section_anyway (abfd, name); @@ -4936,8 +4933,8 @@ elfNN_ia64_object_p (bfd *abfd) return FALSE; /* Move the fake group section to the beginning. */ - BFD_ASSERT (*tail == group); - bfd_section_list_remove (abfd, tail); + BFD_ASSERT (abfd->section_last == group); + bfd_section_double_list_remove (abfd, group); bfd_section_list_insert (abfd, &abfd->sections, group); elf_next_in_group (group) = sec; --- binutils/bfd/opncls.c.dbl 2005-03-09 02:51:55.000000000 -0800 +++ binutils/bfd/opncls.c 2005-05-01 09:00:10.000000000 -0700 @@ -77,7 +77,7 @@ _bfd_new_bfd (void) return NULL; } nbfd->sections = NULL; - nbfd->section_tail = &nbfd->sections; + nbfd->section_last = NULL; nbfd->format = bfd_unknown; nbfd->my_archive = NULL; nbfd->origin = 0; --- binutils/bfd/section.c.dbl 2005-04-12 12:16:43.000000000 -0700 +++ binutils/bfd/section.c 2005-05-01 09:00:10.000000000 -0700 @@ -164,6 +164,9 @@ CODE_FRAGMENT . {* The next section in the list belonging to the BFD, or NULL. *} . struct bfd_section *next; . +. {* The previous section in the list belonging to the BFD, or NULL. *} +. struct bfd_section *prev; +. . {* The field flags contains attributes of the section. Some . flags are read in from the object file, and some are . synthesized from other information. *} @@ -538,31 +541,87 @@ CODE_FRAGMENT .{* Macros to handle insertion and deletion of a bfd's sections. These . only handle the list pointers, ie. do not adjust section_count, . target_index etc. *} +.#define bfd_section_double_list_remove(ABFD, S) \ +. do \ +. { \ +. asection *_s = S; \ +. asection *_next = _s->next; \ +. asection *_prev = _s->prev; \ +. if (_prev) \ +. _prev->next = _next; \ +. else \ +. (ABFD)->sections = _next; \ +. if (_next) \ +. { \ +. _next->prev = _prev; \ +. _s->next = NULL; \ +. } \ +. else \ +. (ABFD)->section_last = _prev; \ +. } \ +. while (0) .#define bfd_section_list_remove(ABFD, PS) \ +. bfd_section_double_list_remove ((ABFD), *(PS)) +.#define bfd_section_double_list_append(ABFD, S) \ +. do \ +. { \ +. asection *_s = S; \ +. bfd *_abfd = ABFD; \ +. _s->next = NULL; \ +. if (_abfd->section_last) \ +. { \ +. _s->prev = _abfd->section_last; \ +. _abfd->section_last->next = _s; \ +. } \ +. else \ +. _abfd->sections = _s; \ +. _abfd->section_last = _s; \ +. } \ +. while (0) +.#define bfd_section_double_list_insert_after(ABFD, A, S) \ . do \ . { \ -. asection **_ps = PS; \ -. asection *_s = *_ps; \ -. *_ps = _s->next; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = _ps; \ +. asection *_a = A; \ +. asection *_s = S; \ +. if (_a) \ +. { \ +. asection *_next = _a->next; \ +. _s->next = _next; \ +. _s->prev = _a; \ +. _a->next = _s; \ +. if (_next) \ +. _s->next->prev = _s; \ +. else \ +. (ABFD)->section_last = _s; \ +. } \ . else \ -. _s->next = NULL; \ +. bfd_section_double_list_append ((ABFD), (S)); \ . } \ . while (0) -.#define bfd_section_list_insert(ABFD, PS, S) \ +.#define bfd_section_double_list_insert_before(ABFD, B, S) \ . do \ . { \ -. asection **_ps = PS; \ +. asection *_b = B; \ . asection *_s = S; \ -. _s->next = *_ps; \ -. *_ps = _s; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = &_s->next; \ +. if (_b) \ +. { \ +. asection *_prev = _b->prev; \ +. _s->prev = _prev; \ +. _s->next = _b; \ +. _b->prev = _s; \ +. if (_prev) \ +. _prev->next = _s; \ +. else \ +. (ABFD)->sections = _s; \ +. } \ +. else \ +. bfd_section_double_list_append ((ABFD), (S)); \ . } \ . while (0) -.#define bfd_section_removed_from_list(ABFD, S) \ -. ((S)->next == NULL && &(S)->next != (ABFD)->section_tail) +.#define bfd_section_list_insert(ABFD, PS, S) \ +. bfd_section_double_list_insert_before ((ABFD), *(PS), (S)) +.#define bfd_section_removed_from_list(ABFD, S) \ +. ((S)->next == NULL && (S) != (ABFD)->section_last) . */ @@ -592,8 +651,8 @@ static const asymbol global_syms[] = #define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX) \ const asymbol * const SYM = (asymbol *) &global_syms[IDX]; \ asection SEC = \ - /* name, id, index, next, flags, user_set_vma, */ \ - { NAME, IDX, 0, NULL, FLAGS, 0, \ + /* name, id, index, next, prev, flags, user_set_vma, */ \ + { NAME, IDX, 0, NULL, NULL, FLAGS, 0, \ \ /* linker_mark, linker_has_input, gc_mark, segment_mark, */ \ 0, 0, 1, 0, \ @@ -705,8 +764,7 @@ bfd_section_init (bfd *abfd, asection *n section_id++; abfd->section_count++; - *abfd->section_tail = newsect; - abfd->section_tail = &newsect->next; + bfd_section_double_list_append (abfd, newsect); return newsect; } @@ -736,7 +794,7 @@ void bfd_section_list_clear (bfd *abfd) { abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; memset (abfd->section_htab.table, 0, abfd->section_htab.size * sizeof (struct bfd_hash_entry *)); --- binutils/bfd/xcofflink.c.dbl 2005-04-11 09:10:29.000000000 -0700 +++ binutils/bfd/xcofflink.c 2005-05-01 12:10:08.000000000 -0700 @@ -5454,19 +5454,17 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st saw_contents = TRUE; else { - asection *n, **st; + asection *n; /* Create a pad section and place it before the section that needs padding. This requires unlinking and relinking the bfd's section list. */ - st = abfd->section_tail; n = bfd_make_section_anyway (abfd, ".pad"); n->flags = SEC_HAS_CONTENTS; n->alignment_power = 0; - BFD_ASSERT (*st == n); - bfd_section_list_remove (abfd, st); + bfd_section_double_list_remove (abfd, n); bfd_section_list_insert (abfd, op, n); op = &n->next; --- binutils/gas/write.c.dbl 2005-04-27 08:28:38.000000000 -0700 +++ binutils/gas/write.c 2005-05-01 08:09:56.000000000 -0700 @@ -1471,20 +1471,11 @@ write_object_file (void) #ifdef BFD_ASSEMBLER /* Remove the sections created by gas for its own purposes. */ { - asection **seclist; int i; - seclist = &stdoutput->sections; - while (*seclist) - { - if (*seclist == reg_section || *seclist == expr_section) - { - bfd_section_list_remove (stdoutput, seclist); - stdoutput->section_count--; - } - else - seclist = &(*seclist)->next; - } + bfd_section_double_list_remove (stdoutput, reg_section); + bfd_section_double_list_remove (stdoutput, expr_section); + stdoutput->section_count -= 2; i = 0; bfd_map_over_sections (stdoutput, renumber_sections, &i); } --- binutils/ld/emultempl/elf32.em.dbl 2005-04-30 15:00:46.000000000 -0700 +++ binutils/ld/emultempl/elf32.em 2005-05-01 08:09:56.000000000 -0700 @@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section if (os == abs_output_section || os->constraint == -1) continue; s = os->bfd_section; - if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0) + if (s != NULL + && s->size == 0 + && (s->flags & SEC_KEEP) == 0 + && !bfd_section_removed_from_list (output_bfd, s)) { - asection **p; - - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + bfd_section_double_list_remove (output_bfd, s); + output_bfd->section_count--; } } } --- binutils/ld/ldlang.c.dbl 2005-04-30 15:19:33.000000000 -0700 +++ binutils/ld/ldlang.c 2005-05-01 08:58:21.000000000 -0700 @@ -1203,7 +1203,6 @@ lang_insert_orphan (lang_input_statement etree_type *load_base; lang_output_section_statement_type *os; lang_output_section_statement_type **os_tail; - asection **bfd_tail; /* Start building a list of statements for this section. First save the current statement pointer. */ @@ -1257,7 +1256,6 @@ lang_insert_orphan (lang_input_statement os_tail = ((lang_output_section_statement_type **) lang_output_section_statement.tail); - bfd_tail = output_bfd->section_tail; os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL, load_base, 0); @@ -1316,8 +1314,8 @@ lang_insert_orphan (lang_input_statement place->section = &output_bfd->sections; /* Unlink the section. */ - ASSERT (*bfd_tail == snew); - bfd_section_list_remove (output_bfd, bfd_tail); + ASSERT (output_bfd->section_last == snew); + bfd_section_double_list_remove (output_bfd, snew); /* Now tack it back on in the right place. */ bfd_section_list_insert (output_bfd, place->section, snew); @@ -3051,8 +3049,6 @@ strip_excluded_or_unused_output_sections && s->linker_has_input == 0 && (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0))) { - asection **p; - /* We don't set bfd_section to NULL since bfd_section of the used output section may still be used. */ if (unused) @@ -3060,13 +3056,11 @@ strip_excluded_or_unused_output_sections else os->bfd_section = NULL; - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + if (!bfd_section_removed_from_list (output_bfd, s)) + { + bfd_section_double_list_remove (output_bfd, s); + output_bfd->section_count--; + } } } } @@ -3722,7 +3716,7 @@ lang_check_section_addresses (void) /* Once we reach section 's' stop our seach. This prevents two warning messages from being produced, one for 'section A overlaps section B' and one for 'section B overlaps section A'. */ - for (os = output_bfd->sections; os != s; os = os->next) + for (os = s->prev; os != NULL; os = os->prev) { bfd_vma s_start; bfd_vma s_end; @@ -3742,15 +3736,14 @@ lang_check_section_addresses (void) os_end = os_start + TO_ADDR (os->size) - 1; /* Look for an overlap. */ - if ((s_end < os_start) || (s_start > os_end)) - continue; - - einfo ( -_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), - s->name, s_start, s_end, os->name, os_start, os_end); - - /* Once we have found one overlap for this section, - stop looking for others. */ + if (s_end >= os_start && s_start <= os_end) + + einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), + s->name, s_start, s_end, os->name, os_start, os_end); + + /* We only need to check the previous section for overlap. + Once we have found one overlap for this section, stop + looking for others. */ break; } } ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-01 19:48 ` PATCH: Use a double section list to speed up linker by 30% H. J. Lu @ 2005-05-02 5:17 ` Alan Modra 2005-05-02 6:14 ` H. J. Lu 0 siblings, 1 reply; 14+ messages in thread From: Alan Modra @ 2005-05-02 5:17 UTC (permalink / raw) To: H. J. Lu; +Cc: binutils On Sun, May 01, 2005 at 12:47:57PM -0700, H. J. Lu wrote: > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > In case of address overlap check, we only > > need to check the previous section. I don't think this is true. > * bfd.c (bfd): Remove section_tail and add section_last. Why did you change this? Using a struct { elt *head; elt **tail; } allows neater list insertion. > (bfd_section_double_list_remove): New. > (bfd_section_list_remove): Updated. I also can't see the sense in both adding new macros and keeping the old ones. -- Alan Modra IBM OzLabs - Linux Technology Centre ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 5:17 ` Alan Modra @ 2005-05-02 6:14 ` H. J. Lu 2005-05-02 6:41 ` Alan Modra 0 siblings, 1 reply; 14+ messages in thread From: H. J. Lu @ 2005-05-02 6:14 UTC (permalink / raw) To: binutils On Mon, May 02, 2005 at 02:47:13PM +0930, Alan Modra wrote: > On Sun, May 01, 2005 at 12:47:57PM -0700, H. J. Lu wrote: > > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > > In case of address overlap check, we only > > > need to check the previous section. > > I don't think this is true. I guess I need to go back until the end of the current section < the start of the section. > > > * bfd.c (bfd): Remove section_tail and add section_last. > > Why did you change this? Using a struct { elt *head; elt **tail; } > allows neater list insertion. I will take another look. > > > (bfd_section_double_list_remove): New. > > (bfd_section_list_remove): Updated. > > I also can't see the sense in both adding new macros and keeping the old > ones. I will remove bfd_section_list_remove. H.J. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 6:14 ` H. J. Lu @ 2005-05-02 6:41 ` Alan Modra 2005-05-02 20:48 ` H. J. Lu 0 siblings, 1 reply; 14+ messages in thread From: Alan Modra @ 2005-05-02 6:41 UTC (permalink / raw) To: H. J. Lu; +Cc: binutils On Sun, May 01, 2005 at 11:14:29PM -0700, H. J. Lu wrote: > On Mon, May 02, 2005 at 02:47:13PM +0930, Alan Modra wrote: > > On Sun, May 01, 2005 at 12:47:57PM -0700, H. J. Lu wrote: > > > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > > > In case of address overlap check, we only > > > > need to check the previous section. > > > > I don't think this is true. > > I guess I need to go back until the end of the current section < > the start of the section. No. A section's address can be specified in a linker script. The order of sections in the output is irrelevant. If you want to fix lang_check_section_addresses properly, then replace the algorithm with one that scales better. For example, build an array of pointers to the output sections, then qsort this array on lma. After doing that you can simply compare adjacent lmas. > > > (bfd_section_double_list_remove): New. > > > (bfd_section_list_remove): Updated. > > > > I also can't see the sense in both adding new macros and keeping the old > > ones. > > I will remove bfd_section_list_remove. Better would be to remove "double_" from the macro names. -- Alan Modra IBM OzLabs - Linux Technology Centre ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 6:41 ` Alan Modra @ 2005-05-02 20:48 ` H. J. Lu 2005-05-03 0:18 ` Alan Modra 0 siblings, 1 reply; 14+ messages in thread From: H. J. Lu @ 2005-05-02 20:48 UTC (permalink / raw) To: binutils On Mon, May 02, 2005 at 04:11:10PM +0930, Alan Modra wrote: > On Sun, May 01, 2005 at 11:14:29PM -0700, H. J. Lu wrote: > > On Mon, May 02, 2005 at 02:47:13PM +0930, Alan Modra wrote: > > > On Sun, May 01, 2005 at 12:47:57PM -0700, H. J. Lu wrote: > > > > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > > > > In case of address overlap check, we only > > > > > need to check the previous section. > > > > > > I don't think this is true. > > > > I guess I need to go back until the end of the current section < > > the start of the section. > > No. A section's address can be specified in a linker script. The order > of sections in the output is irrelevant. If you want to fix > lang_check_section_addresses properly, then replace the algorithm with > one that scales better. For example, build an array of pointers to the > output sections, then qsort this array on lma. After doing that you can > simply compare adjacent lmas. Here is the updated patch. > > > > > (bfd_section_double_list_remove): New. > > > > (bfd_section_list_remove): Updated. > > > > > > I also can't see the sense in both adding new macros and keeping the old > > > ones. > > > > I will remove bfd_section_list_remove. > > Better would be to remove "double_" from the macro names. > "** section_tail" doesn't work since it points to the next field of the last section. I can't get the prev field from that. H.J. ---- bfd/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * bfd.c (bfd): Remove section_tail and add section_last. (bfd_preserve): Likewise. (bfd_preserve_save): Likewise. (bfd_preserve_restore): Likewise. * opncls.c (_bfd_new_bfd): Likewise. * coffcode.h (coff_compute_section_file_positions): Updated. (coff_compute_section_file_positions): Likewise. * elf.c (assign_section_numbers): Likewise. * elf32-i370.c (i370_elf_size_dynamic_sections): Likewise. * elf64-mmix.c (mmix_elf_final_link): Likewise. * elfxx-ia64.c (elfNN_ia64_object_p): Likewise. * elfxx-mips.c (_bfd_mips_elf_link_hash_table_create): Likewise. * sunos.c (sunos_add_dynamic_symbols): Likewise. * xcofflink.c (_bfd_xcoff_bfd_final_link): Likewise. * ecoff.c (bfd_debug_section): Initialize prev. * section.c (bfd_section): Add prev. (bfd_section_list_remove): Updated. (bfd_section_list_append): New. (bfd_section_list_insert_after): New. (bfd_section_list_insert_before): New. (bfd_section_list_insert): Removed. (bfd_section_removed_from_list): Updated. (STD_SECTION): Initialize prev. (bfd_section_init): Updated. (bfd_section_list_clear): Updated. * bfd-in2.h: Regenerated. gas/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * write.c (write_object_file): Use bfd_section_double_list_remove to remove sections. ld/ 2005-05-01 H.J. Lu <hongjiu.lu@intel.com> * emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section): Updated for bfd_section_list_remove change. * ldlang.c (lang_insert_orphan): Likewise. (strip_excluded_or_unused_output_sections): Likewise. (sort_sections_by_lma): New. (lang_check_section_addresses): Sort the sections before checking addresses. --- binutils/bfd/bfd.c.dbl 2005-01-19 09:06:06.000000000 -0800 +++ binutils/bfd/bfd.c 2005-05-02 12:25:36.000000000 -0700 @@ -111,8 +111,8 @@ CODE_FRAGMENT . {* Pointer to linked list of sections. *} . struct bfd_section *sections; . -. {* The place where we add to the section list. *} -. struct bfd_section **section_tail; +. {* The last section on the section list. *} +. struct bfd_section *section_last; . . {* The number of sections. *} . unsigned int section_count; @@ -1390,7 +1390,7 @@ CODE_FRAGMENT . flagword flags; . const struct bfd_arch_info *arch_info; . struct bfd_section *sections; -. struct bfd_section **section_tail; +. struct bfd_section *section_last; . unsigned int section_count; . struct bfd_hash_table section_htab; .}; @@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd preserve->arch_info = abfd->arch_info; preserve->flags = abfd->flags; preserve->sections = abfd->sections; - preserve->section_tail = abfd->section_tail; + preserve->section_last = abfd->section_last; preserve->section_count = abfd->section_count; preserve->section_htab = abfd->section_htab; @@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd abfd->arch_info = &bfd_default_arch_struct; abfd->flags &= BFD_IN_MEMORY; abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; return TRUE; @@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct abfd->flags = preserve->flags; abfd->section_htab = preserve->section_htab; abfd->sections = preserve->sections; - abfd->section_tail = preserve->section_tail; + abfd->section_last = preserve->section_last; abfd->section_count = preserve->section_count; /* bfd_release frees all memory more recently bfd_alloc'd than --- binutils/bfd/coffcode.h.dbl 2005-04-21 10:09:46.000000000 -0700 +++ binutils/bfd/coffcode.h 2005-05-02 12:55:39.000000000 -0700 @@ -1717,7 +1717,6 @@ coff_set_alignment_hook (bfd *abfd, asec { struct internal_scnhdr *hdr = (struct internal_scnhdr *) scnhdr; asection *real_sec; - asection **ps; if ((hdr->s_flags & STYP_OVRFLO) == 0) return; @@ -1729,14 +1728,10 @@ coff_set_alignment_hook (bfd *abfd, asec real_sec->reloc_count = hdr->s_paddr; real_sec->lineno_count = hdr->s_vaddr; - for (ps = &abfd->sections; *ps != NULL; ps = &(*ps)->next) + if (!bfd_section_removed_from_list (abfd, section)) { - if (*ps == section) - { - bfd_section_list_remove (abfd, ps); - --abfd->section_count; - break; - } + bfd_section_list_remove (abfd, section); + --abfd->section_count; } } @@ -3033,11 +3028,12 @@ coff_compute_section_file_positions (bfd /* Rethread the linked list into sorted order; at the same time, assign target_index values. */ target_index = 1; - abfd->sections = section_list[0]; + abfd->sections = NULL; + abfd->section_last = NULL; for (i = 0; i < count; i++) { current = section_list[i]; - current->next = section_list[i + 1]; + bfd_section_list_append (abfd, current); /* Later, if the section has zero size, we'll be throwing it away, so we don't want to number it now. Note that having @@ -3056,7 +3052,6 @@ coff_compute_section_file_positions (bfd else current->target_index = target_index++; } - abfd->section_tail = ¤t->next; free (section_list); } --- binutils/bfd/ecoff.c.dbl 2005-03-16 14:22:39.000000000 -0800 +++ binutils/bfd/ecoff.c 2005-05-02 12:25:36.000000000 -0700 @@ -52,8 +52,8 @@ /* This stuff is somewhat copied from coffcode.h. */ static asection bfd_debug_section = { - /* name, id, index, next, flags, user_set_vma, */ - "*DEBUG*", 0, 0, NULL, 0, 0, + /* name, id, index, next, prev, flags, user_set_vma, */ + "*DEBUG*", 0, 0, NULL, NULL, 0, 0, /* linker_mark, linker_has_input, gc_mark, segment_mark, */ 0, 0, 0, 0, /* sec_info_type, use_rela_p, has_tls_reloc, has_gp_reloc, */ --- binutils/bfd/elf.c.dbl 2005-05-02 12:25:36.000000000 -0700 +++ binutils/bfd/elf.c 2005-05-02 13:32:17.000000000 -0700 @@ -2770,22 +2770,21 @@ assign_section_numbers (bfd *abfd, struc /* SHT_GROUP sections are in relocatable files only. */ if (link_info == NULL || link_info->relocatable) { - asection **secp; + asection *n; /* Put SHT_GROUP sections first. */ - secp = &abfd->sections; - while (*secp) + for (sec = abfd->sections; sec; sec = n) { - d = elf_section_data (*secp); + d = elf_section_data (sec); + n = sec->next; if (d->this_hdr.sh_type == SHT_GROUP) { - if ((*secp)->flags & SEC_LINKER_CREATED) + if (sec->flags & SEC_LINKER_CREATED) { /* Remove the linker created SHT_GROUP sections. */ - bfd_section_list_remove (abfd, secp); + bfd_section_list_remove (abfd, sec); abfd->section_count--; - continue; } else { @@ -2794,8 +2793,6 @@ assign_section_numbers (bfd *abfd, struc d->this_idx = section_number++; } } - - secp = &(*secp)->next; } } --- binutils/bfd/elf32-i370.c.dbl 2005-03-21 09:13:21.000000000 -0800 +++ binutils/bfd/elf32-i370.c 2005-05-02 13:00:58.000000000 -0700 @@ -756,18 +756,12 @@ i370_elf_size_dynamic_sections (output_b if (strip) { - asection **spp; - - for (spp = &s->output_section->owner->sections; - *spp != NULL; - spp = &(*spp)->next) + if (!bfd_section_removed_from_list (s->output_section->owner, + s->output_section)) { - if (*spp == s->output_section) - { - bfd_section_list_remove (s->output_section->owner, spp); - --s->output_section->owner->section_count; - break; - } + bfd_section_list_remove (s->output_section->owner, + s->output_section); + --s->output_section->owner->section_count; } continue; } --- binutils/bfd/elf64-mmix.c.dbl 2005-02-21 11:07:41.000000000 -0800 +++ binutils/bfd/elf64-mmix.c 2005-05-02 12:58:02.000000000 -0700 @@ -2249,7 +2249,6 @@ mmix_elf_final_link (abfd, info) /* We never output a register section, though we create one for temporary measures. Check that nobody entered contents into it. */ asection *reg_section; - asection **secpp; reg_section = bfd_get_section_by_name (abfd, MMIX_REG_SECTION_NAME); @@ -2260,11 +2259,7 @@ mmix_elf_final_link (abfd, info) _bfd_abort (__FILE__, __LINE__, _("Register section has contents\n")); /* Really remove the section. */ - for (secpp = &abfd->sections; - *secpp != reg_section; - secpp = &(*secpp)->next) - ; - bfd_section_list_remove (abfd, secpp); + bfd_section_list_remove (abfd, reg_section); --abfd->section_count; } --- binutils/bfd/elfxx-ia64.c.dbl 2005-05-02 12:25:35.000000000 -0700 +++ binutils/bfd/elfxx-ia64.c 2005-05-02 12:56:26.000000000 -0700 @@ -4923,7 +4923,6 @@ static bfd_boolean elfNN_ia64_object_p (bfd *abfd) { asection *sec; - asection **tail; asection *group, *unwi, *unw; flagword flags; const char *name; @@ -4964,8 +4963,6 @@ elfNN_ia64_object_p (bfd *abfd) strcpy (stpcpy (unw_name, ".gnu.linkonce.ia64unw."), name); unw = bfd_get_section_by_name (abfd, unw_name); - tail = abfd->section_tail; - /* We need to create a fake group section for it and its unwind sections. */ group = bfd_make_section_anyway (abfd, name); @@ -4974,9 +4971,8 @@ elfNN_ia64_object_p (bfd *abfd) return FALSE; /* Move the fake group section to the beginning. */ - BFD_ASSERT (*tail == group); - bfd_section_list_remove (abfd, tail); - bfd_section_list_insert (abfd, &abfd->sections, group); + bfd_section_list_remove (abfd, group); + bfd_section_list_insert_before (abfd, abfd->sections, group); elf_next_in_group (group) = sec; --- binutils/bfd/elfxx-mips.c.dbl 2005-05-02 12:25:35.000000000 -0700 +++ binutils/bfd/elfxx-mips.c 2005-05-02 13:02:08.000000000 -0700 @@ -8902,7 +8902,6 @@ _bfd_mips_elf_link_hash_table_create (bf bfd_boolean _bfd_mips_elf_final_link (bfd *abfd, struct bfd_link_info *info) { - asection **secpp; asection *o; struct bfd_link_order *p; asection *reginfo_sec, *mdebug_sec, *gptab_data_sec, *gptab_bss_sec; @@ -9319,11 +9318,7 @@ _bfd_mips_elf_final_link (bfd *abfd, str o->link_order_head = NULL; /* Really remove the section. */ - for (secpp = &abfd->sections; - *secpp != o; - secpp = &(*secpp)->next) - ; - bfd_section_list_remove (abfd, secpp); + bfd_section_list_remove (abfd, o); --abfd->section_count; continue; --- binutils/bfd/opncls.c.dbl 2005-03-13 21:36:48.000000000 -0800 +++ binutils/bfd/opncls.c 2005-05-02 12:25:36.000000000 -0700 @@ -77,7 +77,7 @@ _bfd_new_bfd (void) return NULL; } nbfd->sections = NULL; - nbfd->section_tail = &nbfd->sections; + nbfd->section_last = NULL; nbfd->format = bfd_unknown; nbfd->my_archive = NULL; nbfd->origin = 0; --- binutils/bfd/section.c.dbl 2005-05-02 12:25:36.000000000 -0700 +++ binutils/bfd/section.c 2005-05-02 12:32:31.000000000 -0700 @@ -164,6 +164,9 @@ CODE_FRAGMENT . {* The next section in the list belonging to the BFD, or NULL. *} . struct bfd_section *next; . +. {* The previous section in the list belonging to the BFD, or NULL. *} +. struct bfd_section *prev; +. . {* The field flags contains attributes of the section. Some . flags are read in from the object file, and some are . synthesized from other information. *} @@ -547,31 +550,73 @@ CODE_FRAGMENT .{* Macros to handle insertion and deletion of a bfd's sections. These . only handle the list pointers, ie. do not adjust section_count, . target_index etc. *} -.#define bfd_section_list_remove(ABFD, PS) \ +.#define bfd_section_list_remove(ABFD, S) \ +. do \ +. { \ +. asection *_s = S; \ +. asection *_next = _s->next; \ +. asection *_prev = _s->prev; \ +. if (_prev) \ +. _prev->next = _next; \ +. else \ +. (ABFD)->sections = _next; \ +. if (_next) \ +. { \ +. _next->prev = _prev; \ +. _s->next = NULL; \ +. } \ +. else \ +. (ABFD)->section_last = _prev; \ +. } \ +. while (0) +.#define bfd_section_list_append(ABFD, S) \ . do \ . { \ -. asection **_ps = PS; \ -. asection *_s = *_ps; \ -. *_ps = _s->next; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = _ps; \ +. asection *_s = S; \ +. bfd *_abfd = ABFD; \ +. _s->next = NULL; \ +. if (_abfd->section_last) \ +. { \ +. _s->prev = _abfd->section_last; \ +. _abfd->section_last->next = _s; \ +. } \ +. else \ +. _abfd->sections = _s; \ +. _abfd->section_last = _s; \ +. } \ +. while (0) +.#define bfd_section_list_insert_after(ABFD, A, S) \ +. do \ +. { \ +. asection *_a = A; \ +. asection *_s = S; \ +. asection *_next = _a->next; \ +. _s->next = _next; \ +. _s->prev = _a; \ +. _a->next = _s; \ +. if (_next) \ +. _s->next->prev = _s; \ . else \ -. _s->next = NULL; \ +. (ABFD)->section_last = _s; \ . } \ . while (0) -.#define bfd_section_list_insert(ABFD, PS, S) \ +.#define bfd_section_list_insert_before(ABFD, B, S) \ . do \ . { \ -. asection **_ps = PS; \ +. asection *_b = B; \ . asection *_s = S; \ -. _s->next = *_ps; \ -. *_ps = _s; \ -. if (_s->next == NULL) \ -. (ABFD)->section_tail = &_s->next; \ +. asection *_prev = _b->prev; \ +. _s->prev = _prev; \ +. _s->next = _b; \ +. _b->prev = _s; \ +. if (_prev) \ +. _prev->next = _s; \ +. else \ +. (ABFD)->sections = _s; \ . } \ . while (0) -.#define bfd_section_removed_from_list(ABFD, S) \ -. ((S)->next == NULL && &(S)->next != (ABFD)->section_tail) +.#define bfd_section_removed_from_list(ABFD, S) \ +. ((S)->next == NULL && (S) != (ABFD)->section_last) . */ @@ -603,8 +648,8 @@ static const asymbol global_syms[] = #define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX) \ const asymbol * const SYM = (asymbol *) &global_syms[IDX]; \ asection SEC = \ - /* name, id, index, next, flags, user_set_vma, */ \ - { NAME, IDX, 0, NULL, FLAGS, 0, \ + /* name, id, index, next, prev, flags, user_set_vma, */ \ + { NAME, IDX, 0, NULL, NULL, FLAGS, 0, \ \ /* linker_mark, linker_has_input, gc_mark, segment_mark, */ \ 0, 0, 1, 0, \ @@ -718,8 +763,7 @@ bfd_section_init (bfd *abfd, asection *n section_id++; abfd->section_count++; - *abfd->section_tail = newsect; - abfd->section_tail = &newsect->next; + bfd_section_list_append (abfd, newsect); return newsect; } @@ -749,7 +793,7 @@ void bfd_section_list_clear (bfd *abfd) { abfd->sections = NULL; - abfd->section_tail = &abfd->sections; + abfd->section_last = NULL; abfd->section_count = 0; memset (abfd->section_htab.table, 0, abfd->section_htab.size * sizeof (struct bfd_hash_entry *)); --- binutils/bfd/sunos.c.dbl 2005-04-11 08:54:43.000000000 -0700 +++ binutils/bfd/sunos.c 2005-05-02 13:29:50.000000000 -0700 @@ -832,7 +832,6 @@ sunos_add_dynamic_symbols (bfd *abfd, bfd *dynobj; struct sunos_dynamic_info *dinfo; unsigned long need; - asection **ps; /* Make sure we have all the required sections. */ if (info->hash->creator == abfd->xvec) @@ -856,12 +855,18 @@ sunos_add_dynamic_symbols (bfd *abfd, want, because that one still implies that the section takes up space in the output file. If this is the first object we have seen, we must preserve the dynamic sections we just created. */ - for (ps = &abfd->sections; *ps != NULL; ) + if (abfd != dynobj) + abfd->sections = NULL; + else { - if (abfd != dynobj || ((*ps)->flags & SEC_LINKER_CREATED) == 0) - bfd_section_list_remove (abfd, ps); - else - ps = &(*ps)->next; + asection *s, *n; + + for (s = abfd->sections; s != NULL; s = n) + { + n = s->next; + if ((s->flags & SEC_LINKER_CREATED) == 0) + bfd_section_list_remove (abfd, s); + } } /* The native linker seems to just ignore dynamic objects when -r is --- binutils/bfd/xcofflink.c.dbl 2005-04-11 08:54:46.000000000 -0700 +++ binutils/bfd/xcofflink.c 2005-05-02 13:16:57.000000000 -0700 @@ -5454,20 +5454,18 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st saw_contents = TRUE; else { - asection *n, **st; + asection *n; /* Create a pad section and place it before the section that needs padding. This requires unlinking and relinking the bfd's section list. */ - st = abfd->section_tail; n = bfd_make_section_anyway (abfd, ".pad"); n->flags = SEC_HAS_CONTENTS; n->alignment_power = 0; - BFD_ASSERT (*st == n); - bfd_section_list_remove (abfd, st); - bfd_section_list_insert (abfd, op, n); + bfd_section_list_remove (abfd, n); + bfd_section_list_insert_before (abfd, *op, n); op = &n->next; saw_contents = FALSE; --- binutils/gas/write.c.dbl 2005-04-27 08:28:38.000000000 -0700 +++ binutils/gas/write.c 2005-05-02 12:34:52.000000000 -0700 @@ -1471,20 +1471,11 @@ write_object_file (void) #ifdef BFD_ASSEMBLER /* Remove the sections created by gas for its own purposes. */ { - asection **seclist; int i; - seclist = &stdoutput->sections; - while (*seclist) - { - if (*seclist == reg_section || *seclist == expr_section) - { - bfd_section_list_remove (stdoutput, seclist); - stdoutput->section_count--; - } - else - seclist = &(*seclist)->next; - } + bfd_section_list_remove (stdoutput, reg_section); + bfd_section_list_remove (stdoutput, expr_section); + stdoutput->section_count -= 2; i = 0; bfd_map_over_sections (stdoutput, renumber_sections, &i); } --- binutils/ld/emultempl/elf32.em.dbl 2005-05-02 12:25:36.000000000 -0700 +++ binutils/ld/emultempl/elf32.em 2005-05-02 12:37:12.000000000 -0700 @@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section if (os == abs_output_section || os->constraint == -1) continue; s = os->bfd_section; - if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0) + if (s != NULL + && s->size == 0 + && (s->flags & SEC_KEEP) == 0 + && !bfd_section_removed_from_list (output_bfd, s)) { - asection **p; - - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + bfd_section_list_remove (output_bfd, s); + output_bfd->section_count--; } } } --- binutils/ld/ldlang.c.dbl 2005-05-02 12:25:36.000000000 -0700 +++ binutils/ld/ldlang.c 2005-05-02 12:52:52.000000000 -0700 @@ -1273,7 +1273,6 @@ lang_insert_orphan (lang_input_statement etree_type *load_base; lang_output_section_statement_type *os; lang_output_section_statement_type **os_tail; - asection **bfd_tail; /* Start building a list of statements for this section. First save the current statement pointer. */ @@ -1327,7 +1326,6 @@ lang_insert_orphan (lang_input_statement os_tail = ((lang_output_section_statement_type **) lang_output_section_statement.tail); - bfd_tail = output_bfd->section_tail; os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL, load_base, 0); @@ -1359,7 +1357,7 @@ lang_insert_orphan (lang_input_statement if (after != NULL && os->bfd_section != NULL) { - asection *snew; + asection *snew, *as; snew = os->bfd_section; @@ -1385,12 +1383,15 @@ lang_insert_orphan (lang_input_statement if (place->section == NULL) place->section = &output_bfd->sections; - /* Unlink the section. */ - ASSERT (*bfd_tail == snew); - bfd_section_list_remove (output_bfd, bfd_tail); + as = *place->section; + if (as != snew && as->prev != snew) + { + /* Unlink the section. */ + bfd_section_list_remove (output_bfd, snew); - /* Now tack it back on in the right place. */ - bfd_section_list_insert (output_bfd, place->section, snew); + /* Now tack it back on in the right place. */ + bfd_section_list_insert_before (output_bfd, as, snew); + } /* Save the end of this list. Further ophans of this type will follow the one we've just added. */ @@ -3119,8 +3120,6 @@ strip_excluded_or_unused_output_sections && s->linker_has_input == 0 && (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0))) { - asection **p; - /* We don't set bfd_section to NULL since bfd_section of the used output section may still be used. */ if (unused) @@ -3128,13 +3127,11 @@ strip_excluded_or_unused_output_sections else os->bfd_section = NULL; - for (p = &output_bfd->sections; *p; p = &(*p)->next) - if (*p == s) - { - bfd_section_list_remove (output_bfd, p); - output_bfd->section_count--; - break; - } + if (!bfd_section_removed_from_list (output_bfd, s)) + { + bfd_section_list_remove (output_bfd, s); + output_bfd->section_count--; + } } } } @@ -3763,6 +3760,22 @@ size_input_section return dot; } +static int +sort_sections_by_lma (const void *arg1, const void *arg2) +{ + const asection *sec1 = *(const asection **) arg1; + const asection *sec2 = *(const asection **) arg2; + + if (bfd_section_lma (sec1->owner, sec1) + < bfd_section_lma (sec2->owner, sec2)) + return -1; + else if (bfd_section_lma (sec1->owner, sec1) + > bfd_section_lma (sec2->owner, sec2)) + return 1; + + return 0; +} + #define IGNORE_SECTION(s) \ ((s->flags & SEC_NEVER_LOAD) != 0 \ || (s->flags & SEC_ALLOC) == 0 \ @@ -3776,52 +3789,62 @@ size_input_section static void lang_check_section_addresses (void) { - asection *s; + asection *s, *os; + asection **sections, **spp; + unsigned int count; + bfd_vma s_start; + bfd_vma s_end; + bfd_vma os_start; + bfd_vma os_end; + bfd_size_type amt; + + if (bfd_count_sections (output_bfd) <= 1) + return; + + amt = bfd_count_sections (output_bfd) * sizeof (asection *); + sections = xmalloc (amt); /* Scan all sections in the output list. */ + count = 0; for (s = output_bfd->sections; s != NULL; s = s->next) { - asection *os; - - /* Ignore sections which are not loaded or which have no contents. */ + /* Only consider loadable sections with real contents. */ if (IGNORE_SECTION (s) || s->size == 0) continue; - /* Once we reach section 's' stop our seach. This prevents two - warning messages from being produced, one for 'section A overlaps - section B' and one for 'section B overlaps section A'. */ - for (os = output_bfd->sections; os != s; os = os->next) - { - bfd_vma s_start; - bfd_vma s_end; - bfd_vma os_start; - bfd_vma os_end; - - /* Only consider loadable sections with real contents. */ - if (IGNORE_SECTION (os) || os->size == 0) - continue; - - /* We must check the sections' LMA addresses not their - VMA addresses because overlay sections can have - overlapping VMAs but they must have distinct LMAs. */ - s_start = bfd_section_lma (output_bfd, s); - os_start = bfd_section_lma (output_bfd, os); - s_end = s_start + TO_ADDR (s->size) - 1; - os_end = os_start + TO_ADDR (os->size) - 1; - - /* Look for an overlap. */ - if ((s_end < os_start) || (s_start > os_end)) - continue; + sections[count] = s; + count++; + } + + if (count <= 1) + return; - einfo ( -_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), - s->name, s_start, s_end, os->name, os_start, os_end); + qsort (sections, (size_t) count, sizeof (asection *), + sort_sections_by_lma); - /* Once we have found one overlap for this section, - stop looking for others. */ - break; - } + spp = sections; + s = *spp++; + s_start = bfd_section_lma (output_bfd, s); + s_end = s_start + TO_ADDR (s->size) - 1; + for (count--; count; count--) + { + /* We must check the sections' LMA addresses not their VMA + addresses because overlay sections can have overlapping VMAs + but they must have distinct LMAs. */ + os = s; + os_start = s_start; + os_end = s_end; + s = *spp++; + s_start = bfd_section_lma (output_bfd, s); + s_end = s_start + TO_ADDR (s->size) - 1; + + /* Look for an overlap. */ + if (s_end >= os_start && s_start <= os_end) + einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"), + s->name, s_start, s_end, os->name, os_start, os_end); } + + free (sections); } /* Make sure the new address is within the region. We explicitly permit the ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 20:48 ` H. J. Lu @ 2005-05-03 0:18 ` Alan Modra 0 siblings, 0 replies; 14+ messages in thread From: Alan Modra @ 2005-05-03 0:18 UTC (permalink / raw) To: H. J. Lu; +Cc: binutils On Mon, May 02, 2005 at 01:48:02PM -0700, H. J. Lu wrote: > "** section_tail" doesn't work since it points to the next field of > the last section. I can't get the prev field from that. Well, you could, but it's a little messy. Your patch looks OK to commit. -- Alan Modra IBM OzLabs - Linux Technology Centre ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu 2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu 2005-05-01 19:48 ` PATCH: Use a double section list to speed up linker by 30% H. J. Lu @ 2005-05-02 0:52 ` Ben Elliston 2005-05-02 17:11 ` H. J. Lu 2005-05-02 18:43 ` Ian Lance Taylor 2 siblings, 2 replies; 14+ messages in thread From: Ben Elliston @ 2005-05-02 0:52 UTC (permalink / raw) To: binutils H. J. Lu wrote: > I know some people have concerns over memory usage. But I will take a > faster linker with a bigger memory footprint than a slower linker any > day. I am planning to include it in the Linux binutils if it isn't in > the FSF binutils. The linker grew a `--reduce-memory-overheads' option that could be used to control such behaviour. Can you make your change conditional on that switch? Ben ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 0:52 ` Ben Elliston @ 2005-05-02 17:11 ` H. J. Lu 2005-05-02 18:43 ` Ian Lance Taylor 1 sibling, 0 replies; 14+ messages in thread From: H. J. Lu @ 2005-05-02 17:11 UTC (permalink / raw) To: Ben Elliston; +Cc: binutils On Mon, May 02, 2005 at 10:51:57AM +1000, Ben Elliston wrote: > H. J. Lu wrote: > > > I know some people have concerns over memory usage. But I will take a > > faster linker with a bigger memory footprint than a slower linker any > > day. I am planning to include it in the Linux binutils if it isn't in > > the FSF binutils. > > The linker grew a `--reduce-memory-overheads' option that could be used to control > such behaviour. Can you make your change conditional on that switch? > I don't think I can choose singly/doubly linked list at run time. H.J. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: PATCH: Use a double section list to speed up linker by 30% 2005-05-02 0:52 ` Ben Elliston 2005-05-02 17:11 ` H. J. Lu @ 2005-05-02 18:43 ` Ian Lance Taylor 1 sibling, 0 replies; 14+ messages in thread From: Ian Lance Taylor @ 2005-05-02 18:43 UTC (permalink / raw) To: Ben Elliston; +Cc: binutils Ben Elliston <bje@au.ibm.com> writes: > H. J. Lu wrote: > > > I know some people have concerns over memory usage. But I will take a > > faster linker with a bigger memory footprint than a slower linker any > > day. I am planning to include it in the Linux binutils if it isn't in > > the FSF binutils. > > The linker grew a `--reduce-memory-overheads' option that could be used to control > such behaviour. Can you make your change conditional on that switch? I didn't notice that when it went in. Should --reduce-memory-overheads imply --no-keep-memory? Ian ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2005-05-29 2:48 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu 2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu 2005-05-21 11:05 ` Christian Joensson 2005-05-27 16:42 ` H. J. Lu 2005-05-29 11:16 ` Alan Modra 2005-05-01 19:48 ` PATCH: Use a double section list to speed up linker by 30% H. J. Lu 2005-05-02 5:17 ` Alan Modra 2005-05-02 6:14 ` H. J. Lu 2005-05-02 6:41 ` Alan Modra 2005-05-02 20:48 ` H. J. Lu 2005-05-03 0:18 ` Alan Modra 2005-05-02 0:52 ` Ben Elliston 2005-05-02 17:11 ` H. J. Lu 2005-05-02 18:43 ` Ian Lance Taylor
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).