This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
Re: patch / RFD: speed up linker map file generation
- From: Joern Rennecke <joern dot rennecke at superh dot com>
- To: nickc at redhat dot com (Nick Clifton)
- Cc: joern dot rennecke at superh dot com (Joern Rennecke), binutils at sources dot redhat dot com
- Date: Tue, 18 May 2004 16:06:08 +0100 (BST)
- Subject: Re: patch / RFD: speed up linker map file generation
> There should definitely be an option. There are users who run these
> tools on small machines who will want the old behaviour. I would
> suggest making it a generalised switch (eg --reduce-memory-overheads)
> that can be used to trigger other (as yet unimplemented) tweaks to the
> linker's behaviour.
I have merged my patch into the mainline from Sunday and implemented your
suggestions.
2004-05-18 J"orn Rennecke <joern.rennecke@superh.com>
* ld.h (map_symbol_def): New struct.
(struct user_section_struct): New members map_symbol_def_head
and map_symbol_def_tail.
(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.
* 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: 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 18 May 2004 15:02:27 -0000
*************** struct wildcard_list {
*** 78,87 ****
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,96 ----
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 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;
} section_userdata_type;
#define get_userdata(x) ((x)->userdata)
*************** typedef struct {
*** 153,158 ****
--- 162,171 ----
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: 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 18 May 2004 15:02:27 -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,726 ****
--- 723,781 ----
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;
+ {
+ section_userdata_type *new_data
+ = ((section_userdata_type *) stat_alloc (sizeof (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 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
*************** 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)
--- 2330,2336 ----
}
/* 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 ****
--- 2356,2373 ----
return TRUE;
}
+ static void
+ print_all_symbols (sec)
+ asection *sec;
+ {
+ struct 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));
--- 2420,2429 ----
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 18 May 2004 15:02:27 -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 18 May 2004 15:02:28 -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;
}
}