* 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ 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; 21+ 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] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-19 0:59 ` Paul Brook
@ 2005-10-19 15:39 ` Nick Clifton
0 siblings, 0 replies; 21+ messages in thread
From: Nick Clifton @ 2005-10-19 15:39 UTC (permalink / raw)
To: Paul Brook; +Cc: binutils
Hi Paul,
> It's still quite slow with this patch.
> unrecord_section_with_arm_elf_section_data has the same problem.
Good point.
> The attached patch uses the cache for this as well, and avoids leaving
> last_entry pointing a free'd object.
Also a very good point.
I have applied your patch together with an extra comment describing why
we set last_found to entry->prev, since I felt that it was not entirely
obvious.
Cheers
Nick
> 2005-10-19 Paul Brook <paul@codesourcery.com>
>
> * elf32-arm.c (find_arm_elf_section_entry): New function.
> (get_arm_elf_section_data,
> unrecord_section_with_arm_elf_section_data): Use it.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-04 7:23 ` Nick Clifton
@ 2005-10-19 0:59 ` Paul Brook
2005-10-19 15:39 ` Nick Clifton
0 siblings, 1 reply; 21+ messages in thread
From: Paul Brook @ 2005-10-19 0:59 UTC (permalink / raw)
To: binutils; +Cc: Nick Clifton
[-- Attachment #1: Type: text/plain, Size: 702 bytes --]
> bfd/ChangeLog
> 2005-10-04 Nick Clifton <nickc@redhat.com>
>
> * elf32-arm.c (get_arm_elf_section_data): Cache the last pointer
> matched so that the typical case of scanning for the previous
> section to last one can be handled quickly.
It's still quite slow with this patch.
unrecord_section_with_arm_elf_section_data has the same problem.
The attached patch uses the cache for this as well, and avoids leaving
last_entry pointing a a free'd object.
Tested with cross to arm-none-eabi.
Ok?
Paul
2005-10-19 Paul Brook <paul@codesourcery.com>
* elf32-arm.c (find_arm_elf_section_entry): New function.
(get_arm_elf_section_data,
unrecord_section_with_arm_elf_section_data): Use it.
[-- Attachment #2: patch.64ksec_speedup --]
[-- Type: text/x-diff, Size: 2868 bytes --]
Index: bfd/elf32-arm.c
===================================================================
RCS file: /var/cvsroot/src-cvs/src/bfd/elf32-arm.c,v
retrieving revision 1.58
diff -u -p -r1.58 elf32-arm.c
--- bfd/elf32-arm.c 8 Oct 2005 17:07:15 -0000 1.58
+++ bfd/elf32-arm.c 19 Oct 2005 00:16:11 -0000
@@ -7311,8 +7311,8 @@ record_section_with_arm_elf_section_data
sections_with_arm_elf_section_data = entry;
}
-static _arm_elf_section_data *
-get_arm_elf_section_data (asection * sec)
+static struct section_list *
+find_arm_elf_section_entry (asection * sec)
{
struct section_list * entry;
static struct section_list * last_entry = NULL;
@@ -7321,27 +7321,37 @@ get_arm_elf_section_data (asection * sec
to the sections_with_arm_elf_section_data list in forward order and
then looked up here in backwards order. This makes a real difference
to the ld-srec/sec64k.exp linker test. */
+ entry = sections_with_arm_elf_section_data;
if (last_entry != NULL)
{
if (last_entry->sec == sec)
- return elf32_arm_section_data (sec);
-
- if (last_entry->prev != NULL
- && last_entry->prev->sec == sec)
- {
- last_entry = last_entry->prev;
- return elf32_arm_section_data (sec);
- }
+ entry = last_entry;
+ else if (last_entry->next != NULL
+ && last_entry->next->sec == sec)
+ entry = last_entry->next;
}
-
- for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
+
+ for (; entry; entry = entry->next)
if (entry->sec == sec)
- {
- last_entry = entry;
- return elf32_arm_section_data (sec);
- }
+ break;
+
+ if (entry)
+ last_entry = entry->prev;
+
+ return entry;
+}
+
+static _arm_elf_section_data *
+get_arm_elf_section_data (asection * sec)
+{
+ struct section_list * entry;
+
+ entry = find_arm_elf_section_entry (sec);
- return NULL;
+ if (entry)
+ return elf32_arm_section_data (entry->sec);
+ else
+ return NULL;
}
static void
@@ -7349,18 +7359,18 @@ unrecord_section_with_arm_elf_section_da
{
struct section_list * entry;
- for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
- if (entry->sec == sec)
- {
- if (entry->prev != NULL)
- entry->prev->next = entry->next;
- if (entry->next != NULL)
- entry->next->prev = entry->prev;
- if (entry == sections_with_arm_elf_section_data)
- sections_with_arm_elf_section_data = entry->next;
- free (entry);
- break;
- }
+ entry = find_arm_elf_section_entry (sec);
+
+ if (entry)
+ {
+ if (entry->prev != NULL)
+ entry->prev->next = entry->next;
+ if (entry->next != NULL)
+ entry->next->prev = entry->prev;
+ if (entry == sections_with_arm_elf_section_data)
+ sections_with_arm_elf_section_data = entry->next;
+ free (entry);
+ }
}
/* Called for each symbol. Builds a section map based on mapping symbols.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-01 1:45 ` Paul Brook
@ 2005-10-04 7:23 ` Nick Clifton
2005-10-19 0:59 ` Paul Brook
0 siblings, 1 reply; 21+ messages in thread
From: Nick Clifton @ 2005-10-04 7:23 UTC (permalink / raw)
To: Paul Brook; +Cc: binutils, Alan Modra, hjl
Hi Paul,
>> * ld-elf/sec64k.exp: Enabled for all ELF targets.
> On an arm-none-eabi cross this test takes about 8 minutes to run on my
> machine. This is about 25 times longer than the whole of the rest of the
> binutils+gas+gdb testsuites put together.
> We should probably figure out what causing this slowness. Until that happens,
> the patch below disable the test on arm targets.
> Ok?
Better I think to find out the cause of the slow down. I did this - it is
the get_arm_elf_section_data() function in elf32-arm.c, which is repeatedly
scanning over a list of ~64K entries trying to match up section
pointers. Since I wrote this function I felt obliged to try to fix it
and I am committing the patch below which does improve things. It is
not the best fix (which would be to use a hash function), but it does
help by noticing that the typical usage is to add sections to the list
in forwards order and then scan for them in backwards order.
Cheers
Nick
bfd/ChangeLog
2005-10-04 Nick Clifton <nickc@redhat.com>
* elf32-arm.c (get_arm_elf_section_data): Cache the last pointer
matched so that the typical case of scanning for the previous
section to last one can be handled quickly.
Index: bfd/elf32-arm.c
===================================================================
RCS file: /cvs/src/src/bfd/elf32-arm.c,v
retrieving revision 1.55
diff -c -3 -p -r1.55 elf32-arm.c
*** bfd/elf32-arm.c 9 Sep 2005 13:10:01 -0000 1.55
--- bfd/elf32-arm.c 4 Oct 2005 07:18:12 -0000
*************** static _arm_elf_section_data *
*** 6563,6572 ****
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! return elf32_arm_section_data (sec);
return NULL;
}
--- 6563,6594 ----
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
+ static struct section_list * last_entry = NULL;
+ /* This is a short cut for the typical case where the sections are added
+ to the sections_with_arm_elf_section_data list in forward order and
+ then looked up here in backwards order. This makes a real difference
+ to the ld-srec/sec64k.exp linker test. */
+ if (last_entry != NULL)
+ {
+ if (last_entry->sec == sec)
+ return elf32_arm_section_data (sec);
+
+ if (last_entry->prev != NULL
+ && last_entry->prev->sec == sec)
+ {
+ last_entry = last_entry->prev;
+ return elf32_arm_section_data (sec);
+ }
+ }
+
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! {
! last_entry = entry;
! return elf32_arm_section_data (sec);
! }
!
return NULL;
}
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-30 15:47 ` Nick Clifton
@ 2005-10-01 1:45 ` Paul Brook
2005-10-04 7:23 ` Nick Clifton
0 siblings, 1 reply; 21+ messages in thread
From: Paul Brook @ 2005-10-01 1:45 UTC (permalink / raw)
To: binutils; +Cc: Nick Clifton, Alan Modra, hjl
[-- Attachment #1: Type: text/plain, Size: 826 bytes --]
> ld/testsuite/
> 2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
>
> * ld-elf/sec64k.exp: Enabled for all ELF targets.
On an arm-none-eabi cross this test takes about 8 minutes to run on my
machine. This is about 25 times longer than the whole of the rest of the
binutils+gas+gdb testsuites put together.
Tests run on a 2GHz amd64, ie. not a slow machine.
A native i386 linker completes the test in a more reasonable time (~20
seconds), so this looks like an arm specific problem.
We should probably figure out what causing this slowness. Until that happens,
the patch below disable the test on arm targets.
Ok?
I'll file a bug in bugzilla to remind me/us that there's something slow in the
arm linker.
Paul
2005-10-01 Paul Brook <paul@codesourcery.com>
* ld-elf/sec64k.exp: Skip test on arm targets (too slow).
[-- Attachment #2: patch.arm_sec64k --]
[-- Type: text/x-diff, Size: 685 bytes --]
Index: ld/testsuite/ld-elf/sec64k.exp
===================================================================
RCS file: /var/cvsroot/src-cvs/src/ld/testsuite/ld-elf/sec64k.exp,v
retrieving revision 1.7
diff -u -p -r1.7 sec64k.exp
--- ld/testsuite/ld-elf/sec64k.exp 30 Sep 2005 17:45:54 -0000 1.7
+++ ld/testsuite/ld-elf/sec64k.exp 1 Oct 2005 01:38:20 -0000
@@ -24,6 +24,11 @@ if ![is_elf_format] {
return
}
+# For some reason this is painfully slow on arm targets, so skip it.
+if { [istarget arm*-*-*] } {
+ 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] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-30 7:31 ` Alan Modra
@ 2005-09-30 15:47 ` Nick Clifton
2005-10-01 1:45 ` Paul Brook
0 siblings, 1 reply; 21+ messages in thread
From: Nick Clifton @ 2005-09-30 15:47 UTC (permalink / raw)
To: Alan Modra; +Cc: Steven Bosscher, binutils, hjl
Hi H.J.
Just to make this explicit:
> Alan Modra wrote:
>>Can anyone tell what happened to this linker speedup patch?
>>http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
>
> I looked at rearranging the orphan code so that this wouldn't be
> necessary, and found I needed to pull apart half the linker. So I left
> that job for a rainy day. Since I haven't provided a more elegant
> solution, I suppose HJ's patch ought to go in.
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.
Approved - please apply.
Cheers
Nick
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-29 16:46 PATCH: Use a hash table for 26X linker speedup Steven Bosscher
@ 2005-09-30 7:31 ` Alan Modra
2005-09-30 15:47 ` Nick Clifton
0 siblings, 1 reply; 21+ messages in thread
From: Alan Modra @ 2005-09-30 7:31 UTC (permalink / raw)
To: Steven Bosscher; +Cc: binutils, hjl
On Thu, Sep 29, 2005 at 04:23:05PM +0200, Steven Bosscher wrote:
> Can anyone tell what happened to this linker speedup patch?
> http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
I looked at rearranging the orphan code so that this wouldn't be
necessary, and found I needed to pull apart half the linker. So I left
that job for a rainy day. Since I haven't provided a more elegant
solution, I suppose HJ's patch ought to go in.
--
Alan Modra
IBM OzLabs - Linux Technology Centre
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
@ 2005-09-29 16:46 Steven Bosscher
2005-09-30 7:31 ` Alan Modra
0 siblings, 1 reply; 21+ messages in thread
From: Steven Bosscher @ 2005-09-29 16:46 UTC (permalink / raw)
To: binutils; +Cc: amodra, hjl
Hi,
Can anyone tell what happened to this linker speedup patch?
http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
Gr.
Steven
^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2005-10-19 15:39 UTC | newest]
Thread overview: 21+ 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
2005-09-29 16:46 PATCH: Use a hash table for 26X linker speedup Steven Bosscher
2005-09-30 7:31 ` Alan Modra
2005-09-30 15:47 ` Nick Clifton
2005-10-01 1:45 ` Paul Brook
2005-10-04 7:23 ` Nick Clifton
2005-10-19 0:59 ` Paul Brook
2005-10-19 15:39 ` Nick Clifton
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).