patch / RFD: speed up linker map file generation

patch / RFD: speed up linker map file generation

[Joern Rennecke]

The linker map file generation has quadratic time complexity, because for
every input section, it goes through the entire hash table to look for
symbols defined in that section.  A customer found that ld takes seven times
as long with map file generation enabled as without.
The problem of finding the list of symbols defined in every section can be
solved in linear time by going through the hash table once and put each
defined symbol into a linked list associated with the section the symbol
is defined in.
To avoid reversing the output, I use a list head / tail setup.
(Although the traversal of a hash table seems arbitrary, it is still done in
 a specific order, and preserving that order allows to use diff in a
 meaningful way.)
These are put as new fields into the user_section_struct.
Initially, I thought I could just map over the input bfds and initialize
all the userdata fields of the input sections, but it turns out this misses
some sections; there are even some where userdata has already been set
but without the map_symbol_def_tail initialization, so presumambly this
must be an output section?

I'm also not quite sure where we stand with memory consumption vs. speed.
The linear time algorithm needs two pointers per hash table entry to
form the linear lists.  The hash table entries appear to be the size of five
pointers, and the overhead with objalloc_alloc / obstacks should be
negligible.  Thus, it appears the memory used by defined symbols will grow
by 40% when creating a map file with the linear time algorithm.
So, should the linear time algotithm be the only one, on the grounds that
quadratic time tendstu hurt you much sooner than the 40% memory increase?
Or should there be an option to use the old algorithm for people who simply
can't create enough swap for the linker to create a map file with the new
algorithm, but are prepared to wait a few hours for the result?
I've put the new code in guarded with if (1) for now so that a flag set
by an option could be used if we want implement such an option.

2004-05-05  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.
	* ldlang.c (map_obstack): New static variable.
	(init_map_userdata, print_all_symbols, sort_def_symbol): New functions.
	(lang_map): Initialize lists of defined symbols for each section.
	(print_input_section): Use print_all_symbols.

diff -pu orig-dir/ld.h ./ld.h
--- orig-dir/ld.h	Wed May  5 13:13:33 2004
+++ ./ld.h	Wed May  5 14:45:02 2004
@@ -78,10 +78,19 @@ struct wildcard_list {
   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 {
-  /* Pointer to the section where this data will go */
+  /* 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)
diff -pu orig-dir/ldlang.c ./ldlang.c
--- orig-dir/ldlang.c	Wed May  5 13:13:25 2004
+++ ./ldlang.c	Wed May  5 15:50:30 2004
@@ -46,6 +46,7 @@
 
 /* Locals variables.  */
 static struct obstack stat_obstack;
+static struct obstack map_obstack;
 
 #define obstack_chunk_alloc xmalloc
 #define obstack_chunk_free free
@@ -78,6 +79,8 @@ static void init_os
   PARAMS ((lang_output_section_statement_type *));
 static void exp_init_os
   PARAMS ((etree_type *));
+static void init_map_userdata
+  PARAMS ((bfd *, asection *, PTR));
 static void section_already_linked
   PARAMS ((bfd *, asection *, PTR));
 static struct bfd_hash_entry *already_linked_newfunc
@@ -127,6 +130,10 @@ static void print_input_statement
   PARAMS ((lang_input_statement_type *));
 static bfd_boolean print_one_symbol
   PARAMS ((struct bfd_link_hash_entry *, PTR));
+static void print_all_symbols
+  PARAMS ((asection *));
+static bfd_boolean sort_def_symbol
+  PARAMS ((struct bfd_link_hash_entry *, PTR));
 static void print_input_section
   PARAMS ((lang_input_section_type *));
 static void print_fill_statement
@@ -829,6 +836,7 @@ void
 lang_map ()
 {
   lang_memory_region_type *m;
+  bfd *p;
 
   minfo (_("\nMemory Configuration\n\n"));
   fprintf (config.map_file, "%-16s %-18s %-18s %s\n",
@@ -876,9 +884,59 @@ lang_map ()
 
   fprintf (config.map_file, _("\nLinker script and memory map\n\n"));
 
+  if (1)
+    {
+      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;
+     PTR 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) = (PTR) 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;
+     PTR 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?  */
+	  /* 1st 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
@@ -2357,7 +2415,7 @@ print_input_statement (statm)
 }
 
 /* Print all symbols defined in a particular section.  This is called
-   via bfd_link_hash_traverse.  */
+   via bfd_link_hash_traverse, or by print_all_symbols.  */
 
 static bfd_boolean
 print_one_symbol (hash_entry, ptr)
@@ -2385,6 +2443,18 @@ print_one_symbol (hash_entry, ptr)
   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, (PTR) sec);
+}
+
 /* Print information about an input section to the map file.  */
 
 static void
@@ -2438,7 +2508,10 @@ print_input_section (in)
 	      minfo (_("%W (size before relaxing)\n"), i->_raw_size);
 	    }
 
-	  bfd_link_hash_traverse (link_info.hash, print_one_symbol, (PTR) i);
+	  if (1)
+	    print_all_symbols (i);
+	  else
+	    bfd_link_hash_traverse (link_info.hash, print_one_symbol, (PTR) i);
 
 	  print_dot = i->output_section->vma + i->output_offset + size / opb;
 	}

Re: patch / RFD: speed up linker map file generation

[Nick Clifton]

Hi Joern,

   Sorry for the long delay in replaying to this email. :-(

Thanks very much fir developing this patch.  I think that it is 
definitely a good idea.

> I'm also not quite sure where we stand with memory consumption vs. speed.
> The linear time algorithm needs two pointers per hash table entry to
> form the linear lists.  The hash table entries appear to be the size of five
> pointers, and the overhead with objalloc_alloc / obstacks should be
> negligible.  Thus, it appears the memory used by defined symbols will grow
> by 40% when creating a map file with the linear time algorithm.
> So, should the linear time algorithm be the only one, on the grounds that
> quadratic time tends to hurt you much sooner than the 40% memory increase?
> Or should there be an option to use the old algorithm for people who simply
> can't create enough swap for the linker to create a map file with the new
> algorithm, but are prepared to wait a few hours for the result?

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.

A few, minor, comments on the patch:

> +  /* For output sections: pointer to the section where this data will go */

Comment formatting: Please could we have a full stop and a couple of 
spaces at the end of the comments ?  (I know that the comments that you 
are replacing did not have this, but that should be no reason not to 
follow the guidelines).

> +static void init_map_userdata
> +  PARAMS ((bfd *, asection *, PTR));

Were are using ISO C now so we do not need to use the PARAMS() macro.

Cheers
   Nick

Re: patch / RFD: speed up linker map file generation

[Joern Rennecke]

> 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;
  	}
      }

Re: patch / RFD: speed up linker map file generation

[Nick Clifton]

Hi Joern,

> I have merged my patch into the mainline from Sunday and implemented your
> suggestions.

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.

Cheers
   Nick

Re: patch / RFD: speed up linker map file generation

[Joern Rennecke]

> 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;
  	}
      }

Re: patch / RFD: speed up linker map file generation

[Nick Clifton]

Hi Joern,


> 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.

Approved - please apply - and thanks very much for developing this patch.

Cheers
    Nick

Re: patch / RFD: speed up linker map file generation

[Ben Elliston]

Nick Clifton <nickc@redhat.com> writes:

> 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.

There are plenty of applications that detect the amount of available
working memory and adjust their behaviour accordingly.  Can't the
linker do the same?  It seems unfortunate that we mere humans must
instruct the program to do something that it can probably figure out
better itself.

Ben

Re: patch / RFD: speed up linker map file generation

[Ian Lance Taylor]

Ben Elliston <bje@au.ibm.com> writes:

> Nick Clifton <nickc@redhat.com> writes:
> 
> > 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.

Note that the linker also has the --no-keep-memory option.  I don't
sure why we need a separate --reduce-memory-overheads option, although
I concede that --no-keep-memory is probably not the best name.

> There are plenty of applications that detect the amount of available
> working memory and adjust their behaviour accordingly.  Can't the
> linker do the same?  It seems unfortunate that we mere humans must
> instruct the program to do something that it can probably figure out
> better itself.

We would need a semi-portable way of figuring out how much space we
could reasonably allocate.  Given that, it's a mere matter of
programming.

(Simply running along casually until malloc returns NULL causes
massive thrashing along the way.)

Ian

Re: patch / RFD: speed up linker map file generation

[Daniel Jacobowitz]

On Tue, Jun 08, 2004 at 10:25:06PM -0400, Ian Lance Taylor wrote:
> We would need a semi-portable way of figuring out how much space we
> could reasonably allocate.  Given that, it's a mere matter of
> programming.

Conveniently, it's in libiberty :)  Or a close enough approximation,
anyway; GCC uses it to dynamically size the GC parameters.

-- 
Daniel Jacobowitz

Re: patch / RFD: speed up linker map file generation

[Ian Lance Taylor]

Daniel Jacobowitz <drow@false.org> writes:

> On Tue, Jun 08, 2004 at 10:25:06PM -0400, Ian Lance Taylor wrote:
> > We would need a semi-portable way of figuring out how much space we
> > could reasonably allocate.  Given that, it's a mere matter of
> > programming.
> 
> Conveniently, it's in libiberty :)  Or a close enough approximation,
> anyway; GCC uses it to dynamically size the GC parameters.

Cool, I didn't know about that one.

Ian

Re: patch / RFD: speed up linker map file generation

[Hans-Peter Nilsson]

On Tue, 9 Jun 2004, Ben Elliston wrote:
> Nick Clifton <nickc@redhat.com> writes:
> There are plenty of applications that detect the amount of available
> working memory and adjust their behaviour accordingly.  Can't the
> linker do the same?  It seems unfortunate that we mere humans must
> instruct the program to do something that it can probably figure out
> better itself.

When/if you or Someone Else adds this feature, pretty please
also remember to add some kind of parameter-dump option and
option to explicitly set the parameter(s), for sake of
repeatability when debugging memory-allocation-related bugs.
(Like with GCC.)

brgds, H-P

Re: patch / RFD: speed up linker map file generation

[Nick Clifton]

Hi Ben,

> There are plenty of applications that detect the amount of available
> working memory and adjust their behaviour accordingly.  Can't the
> linker do the same?

Yes - in fact this would definitely be a good idea.

> It seems unfortunate that we mere humans must
> instruct the program to do something that it can probably figure out
> better itself.

I still believe that we need the command line switches to override the 
linker's behaviour in order to control it in special situations.  eg 
when the user doe snot want the linker to use all of the available memory.

Cheers
   Nick