Home Original page

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