patch / RFD: speed up linker map file generation
Joern Rennecke
joern.rennecke@superh.com
Wed May 19 12:23:00 GMT 2004
> Great - there a few more minor things that need fixing:
>
> * The new switch should be documented in ld.texinfo. This entry also
> ought to mention that it may enable other tweaks to the linker's
> behaviour in the future.
>
> * A new feature like this should be mentioned in the ld/NEWS file as
> well.
>
> * You are still adding two extra fields to user_section_struct, even
> if --reduce-memory-overheads is enabled. It would be better I think if
> you had two different structures, one with the extra fields, and then
> altered the get_userdata() macro and the init_os() function to select
> the right one depending upon the command line switch.
Fixed thus:
2004-05-19 J"orn Rennecke <joern.rennecke@superh.com>
* NEWS: Mention new linker map file generation and the
--reduce-memory-overheads option.
* ld.texinfo: Document --reduce-memory-overheads option.
* ld.h (map_symbol_def): New struct.
(struct user_section_struct, section_userdata_type): Rename to:
(struct lean_user_section_struct, lean_section_userdata_type).
(struct fat_user_section_struct, fat_section_userdata_type): New.
(SECTION_USERDATA_SIZE): Define.
(args_type): New member reduce_memory_overheads.
* ldlang.c (map_obstack): New static variable.
(init_map_userdata, print_all_symbols, sort_def_symbol): New functions.
(lang_map): Unless command_line.reduce_memory_overheads is set,
initialize lists of defined symbols for each section.
(print_input_section): Unless command_line.reduce_memory_overheads
is set, use print_all_symbols.
(init_os): Use lean_section_userdata_type / SECTION_USERDATA_SIZE.
* ldmain.c (main): Initialize command_line.reduce_memory_overheads.
* lexsup.c (enum option_values): Add OPTION_REDUCE_MEMORY_OVERHEADS.
(ld_options): Add entry for --reduce-memory-overheads.
(parse_args): Handle OPTION_REDUCE_MEMORY_OVERHEADS.
Index: NEWS
===================================================================
RCS file: /cvs/src/src/ld/NEWS,v
retrieving revision 1.45
diff -p -r1.45 NEWS
*** NEWS 7 May 2004 15:17:57 -0000 1.45
--- NEWS 19 May 2004 12:14:37 -0000
***************
*** 1,5 ****
--- 1,11 ----
-*- text -*-
+ * Linker map files are now generated with an O(N) algorithm for finding symbols
+ that are defined in each section. This uses about 40% more memory for
+ symbols than the old O(N^2) algorithm. You can use the new
+ --reduce-memory-overheads option to select the old algorithm; this option
+ might also be used in the future to select similar tradeoffs.
+
* New PE --large-address-aware option to indicate executables support virtual
addresses greater than 2 gigabytes.
Index: ld.h
===================================================================
RCS file: /cvs/src/src/ld/ld.h,v
retrieving revision 1.21
diff -p -r1.21 ld.h
*** ld.h 28 Jun 2003 05:28:54 -0000 1.21
--- ld.h 19 May 2004 12:14:37 -0000
*************** struct wildcard_list {
*** 78,88 ****
struct wildcard_spec spec;
};
/* Extra information we hold on sections */
! typedef struct user_section_struct {
! /* Pointer to the section where this data will go */
struct lang_input_statement_struct *file;
! } section_userdata_type;
#define get_userdata(x) ((x)->userdata)
--- 78,109 ----
struct wildcard_spec spec;
};
+ struct map_symbol_def {
+ struct bfd_link_hash_entry *entry;
+ struct map_symbol_def *next;
+ };
+
/* Extra information we hold on sections */
! typedef struct lean_user_section_struct {
! /* For output sections: pointer to the section where this data will go. */
! struct lang_input_statement_struct *file;
! } lean_section_userdata_type;
!
! /* The initial part of fat_user_section_struct has to be idential with
! lean_user_section_struct. */
! typedef struct fat_user_section_struct {
! /* For output sections: pointer to the section where this data will go. */
struct lang_input_statement_struct *file;
! /* For input sections, when writing a map file: head / tail of a linked
! list of hash table entries for symbols defined in this section. */
! struct map_symbol_def *map_symbol_def_head;
! struct map_symbol_def **map_symbol_def_tail;
! } fat_section_userdata_type;
!
! #define SECTION_USERDATA_SIZE \
! (command_line.reduce_memory_overheads \
! ? sizeof (lean_section_userdata_type) \
! : sizeof (fat_section_userdata_type))
#define get_userdata(x) ((x)->userdata)
*************** typedef struct {
*** 153,158 ****
--- 174,183 ----
behaviour of the linker. The new default behaviour is to reject such
input files. */
bfd_boolean accept_unknown_input_arch;
+
+ /* If TRUE reduce memory overheads, at the expense of speed.
+ This will cause map file generation to use an O(N^2) algorithm. */
+ bfd_boolean reduce_memory_overheads;
} args_type;
Index: ld.texinfo
===================================================================
RCS file: /cvs/src/src/ld/ld.texinfo,v
retrieving revision 1.113
diff -p -r1.113 ld.texinfo
*** ld.texinfo 7 May 2004 15:17:57 -0000 1.113
--- ld.texinfo 19 May 2004 12:14:37 -0000
*************** If you specify @option{--disable-new-dta
*** 1734,1739 ****
--- 1734,1747 ----
created. By default, the new dynamic tags are not created. Note that
those options are only available for ELF systems.
+ @kindex --reduce-memory-overheads
+ @item --reduce-memory-overheads
+ This option reduces memory requirements at ld runtime, at the expense of
+ linking speed. This was introduced to to select the old O(n^2) algorithm
+ for link map file generation, rather than the new O(n) algorithm which uses
+ about 40% more memory for symbol storage. It may be also be used for
+ similar such tradeoffs in the future.
+
@end table
@c man end
Index: ldlang.c
===================================================================
RCS file: /cvs/src/src/ld/ldlang.c,v
retrieving revision 1.145
diff -p -r1.145 ldlang.c
*** ldlang.c 11 May 2004 17:08:34 -0000 1.145
--- ldlang.c 19 May 2004 12:14:38 -0000
***************
*** 47,52 ****
--- 47,53 ----
/* Locals variables. */
static struct obstack stat_obstack;
+ static struct obstack map_obstack;
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
*************** static struct bfd_hash_table lang_define
*** 65,70 ****
--- 66,72 ----
/* Forward declarations. */
static void exp_init_os (etree_type *);
+ static void init_map_userdata (bfd *, asection *, void *);
static bfd_boolean wildcardp (const char *);
static lang_input_statement_type *lookup_name (const char *);
static bfd_boolean load_symbols (lang_input_statement_type *,
*************** static bfd_boolean load_symbols (lang_in
*** 72,77 ****
--- 74,81 ----
static struct bfd_hash_entry *lang_definedness_newfunc
(struct bfd_hash_entry *, struct bfd_hash_table *, const char *);
static void insert_undefined (const char *);
+ static void print_all_symbols (asection *);
+ static bfd_boolean sort_def_symbol (struct bfd_link_hash_entry *, void *);
static void print_statement (lang_statement_union_type *,
lang_output_section_statement_type *);
static void print_statement_list (lang_statement_union_type *,
*************** void
*** 673,678 ****
--- 677,683 ----
lang_map (void)
{
lang_memory_region_type *m;
+ bfd *p;
minfo (_("\nMemory Configuration\n\n"));
fprintf (config.map_file, "%-16s %-18s %-18s %s\n",
*************** lang_map (void)
*** 718,732 ****
fprintf (config.map_file, _("\nLinker script and memory map\n\n"));
print_statements ();
}
/* Initialize an output section. */
static void
init_os (lang_output_section_statement_type *s)
{
! section_userdata_type *new;
if (s->bfd_section != NULL)
return;
--- 723,788 ----
fprintf (config.map_file, _("\nLinker script and memory map\n\n"));
+ if (! command_line.reduce_memory_overheads)
+ {
+ obstack_begin (&map_obstack, 1000);
+ for (p = link_info.input_bfds; p != (bfd *) NULL; p = p->link_next)
+ bfd_map_over_sections (p, init_map_userdata, 0);
+ bfd_link_hash_traverse (link_info.hash, sort_def_symbol, 0);
+ }
print_statements ();
}
+ static void
+ init_map_userdata (abfd, sec, data)
+ bfd *abfd ATTRIBUTE_UNUSED;
+ asection *sec;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ fat_section_userdata_type *new_data
+ = ((fat_section_userdata_type *) (stat_alloc
+ (sizeof (fat_section_userdata_type))));
+
+ ASSERT (get_userdata (sec) == NULL);
+ get_userdata (sec) = new_data;
+ new_data->map_symbol_def_tail = &new_data->map_symbol_def_head;
+ }
+
+ static bfd_boolean
+ sort_def_symbol (hash_entry, info)
+ struct bfd_link_hash_entry *hash_entry;
+ void *info ATTRIBUTE_UNUSED;
+ {
+ if (hash_entry->type == bfd_link_hash_defined
+ || hash_entry->type == bfd_link_hash_defweak)
+ {
+ struct fat_user_section_struct *ud;
+ struct map_symbol_def *def;
+
+ ud = get_userdata (hash_entry->u.def.section);
+ if (! ud)
+ {
+ /* ??? What do we have to do to initialize this beforehand? */
+ /* The first time we get here is bfd_abs_section... */
+ init_map_userdata (0, hash_entry->u.def.section, 0);
+ ud = get_userdata (hash_entry->u.def.section);
+ }
+ else if (!ud->map_symbol_def_tail)
+ ud->map_symbol_def_tail = &ud->map_symbol_def_head;
+ def = (struct map_symbol_def *) obstack_alloc (&map_obstack, sizeof *def);
+ def->entry = hash_entry;
+ *ud->map_symbol_def_tail = def;
+ ud->map_symbol_def_tail = &def->next;
+ }
+ return TRUE;
+ }
+
/* Initialize an output section. */
static void
init_os (lang_output_section_statement_type *s)
{
! lean_section_userdata_type *new;
if (s->bfd_section != NULL)
return;
*************** init_os (lang_output_section_statement_t
*** 734,740 ****
if (strcmp (s->name, DISCARD_SECTION_NAME) == 0)
einfo (_("%P%F: Illegal use of `%s' section\n"), DISCARD_SECTION_NAME);
! new = stat_alloc (sizeof (section_userdata_type));
s->bfd_section = bfd_get_section_by_name (output_bfd, s->name);
if (s->bfd_section == NULL)
--- 790,796 ----
if (strcmp (s->name, DISCARD_SECTION_NAME) == 0)
einfo (_("%P%F: Illegal use of `%s' section\n"), DISCARD_SECTION_NAME);
! new = stat_alloc (SECTION_USERDATA_SIZE);
s->bfd_section = bfd_get_section_by_name (output_bfd, s->name);
if (s->bfd_section == NULL)
*************** print_input_statement (lang_input_statem
*** 2275,2281 ****
}
/* Print all symbols defined in a particular section. This is called
! via bfd_link_hash_traverse. */
static bfd_boolean
print_one_symbol (struct bfd_link_hash_entry *hash_entry, void *ptr)
--- 2331,2337 ----
}
/* Print all symbols defined in a particular section. This is called
! via bfd_link_hash_traverse, or by print_all_symbols. */
static bfd_boolean
print_one_symbol (struct bfd_link_hash_entry *hash_entry, void *ptr)
*************** print_one_symbol (struct bfd_link_hash_e
*** 2301,2306 ****
--- 2357,2374 ----
return TRUE;
}
+ static void
+ print_all_symbols (sec)
+ asection *sec;
+ {
+ struct fat_user_section_struct *ud = get_userdata (sec);
+ struct map_symbol_def *def;
+
+ *ud->map_symbol_def_tail = 0;
+ for (def = ud->map_symbol_def_head; def; def = def->next)
+ print_one_symbol (def->entry, sec);
+ }
+
/* Print information about an input section to the map file. */
static void
*************** print_input_section (lang_input_section_
*** 2353,2359 ****
minfo (_("%W (size before relaxing)\n"), i->_raw_size);
}
! bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
print_dot = (i->output_section->vma + i->output_offset
+ TO_ADDR (size));
--- 2421,2430 ----
minfo (_("%W (size before relaxing)\n"), i->_raw_size);
}
! if (command_line.reduce_memory_overheads)
! bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
! else
! print_all_symbols (i);
print_dot = (i->output_section->vma + i->output_offset
+ TO_ADDR (size));
Index: ldmain.c
===================================================================
RCS file: /cvs/src/src/ld/ldmain.c,v
retrieving revision 1.80
diff -p -r1.80 ldmain.c
*** ldmain.c 11 May 2004 17:08:34 -0000 1.80
--- ldmain.c 19 May 2004 12:14:39 -0000
*************** main (int argc, char **argv)
*** 274,279 ****
--- 274,280 ----
command_line.warn_mismatch = TRUE;
command_line.check_section_addresses = TRUE;
command_line.accept_unknown_input_arch = FALSE;
+ command_line.reduce_memory_overheads = FALSE;
/* We initialize DEMANGLING based on the environment variable
COLLECT_NO_DEMANGLE. The gcc collect2 program will demangle the
Index: lexsup.c
===================================================================
RCS file: /cvs/src/src/ld/lexsup.c,v
retrieving revision 1.72
diff -p -r1.72 lexsup.c
*** lexsup.c 20 Mar 2004 23:16:43 -0000 1.72
--- lexsup.c 19 May 2004 12:14:39 -0000
*************** enum option_values
*** 142,148 ****
OPTION_PIE,
OPTION_UNRESOLVED_SYMBOLS,
OPTION_WARN_UNRESOLVED_SYMBOLS,
! OPTION_ERROR_UNRESOLVED_SYMBOLS
};
/* The long options. This structure is used for both the option
--- 142,149 ----
OPTION_PIE,
OPTION_UNRESOLVED_SYMBOLS,
OPTION_WARN_UNRESOLVED_SYMBOLS,
! OPTION_ERROR_UNRESOLVED_SYMBOLS,
! OPTION_REDUCE_MEMORY_OVERHEADS
};
/* The long options. This structure is used for both the option
*************** static const struct ld_option ld_options
*** 445,451 ****
{ {"no-as-needed", no_argument, NULL, OPTION_NO_AS_NEEDED},
'\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES },
{ {"wrap", required_argument, NULL, OPTION_WRAP},
! '\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES }
};
#define OPTION_COUNT ARRAY_SIZE (ld_options)
--- 446,454 ----
{ {"no-as-needed", no_argument, NULL, OPTION_NO_AS_NEEDED},
'\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES },
{ {"wrap", required_argument, NULL, OPTION_WRAP},
! '\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES },
! { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS},
! '\0', NULL, N_("reduce memory overheads, possibly taking much longer"), TWO_DASHES },
};
#define OPTION_COUNT ARRAY_SIZE (ld_options)
*************** parse_args (unsigned argc, char **argv)
*** 1220,1225 ****
--- 1223,1231 ----
case OPTION_FINI:
link_info.fini_function = optarg;
+ break;
+ case OPTION_REDUCE_MEMORY_OVERHEADS:
+ command_line.reduce_memory_overheads = TRUE;
break;
}
}
More information about the Binutils
mailing list