This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
PATCH: Use a double section list to speed up linker by 30%
- From: "H. J. Lu" <hjl at lucon dot org>
- To: binutils at sources dot redhat dot com
- Date: Sun, 1 May 2005 09:57:07 -0700
- Subject: PATCH: Use a double section list to speed up linker by 30%
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;
}
}