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

7 files changed, 149 insertions, 9 deletions

diff --git a/ld/ChangeLog b/ld/ChangeLog
index a96006a..38bbbe7 100644
--- a/ld/ChangeLog
+++ b/ld/ChangeLog
@@ -1,3 +1,26 @@
+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.
+
 2004-05-19  Jakub Jelinek  <jakub@redhat.com>
 
 	* ldgram.y (sect_constraint): New.
diff --git a/ld/NEWS b/ld/NEWS
index cec229b..a33c6dc 100644
--- a/ld/NEWS
+++ b/ld/NEWS
@@ -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.
 
diff --git a/ld/ld.h b/ld/ld.h
index dde4cfe..1061c35 100644
--- a/ld/ld.h
+++ b/ld/ld.h
@@ -78,11 +78,32 @@ 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 */
+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;
-} section_userdata_type;
+  /* 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)
 
@@ -154,6 +175,10 @@ typedef struct {
      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;
 
 extern args_type command_line;
diff --git a/ld/ld.texinfo b/ld/ld.texinfo
index ceaecd1..b78d1b0 100644
--- a/ld/ld.texinfo
+++ b/ld/ld.texinfo
@@ -1734,6 +1734,14 @@ If you specify @option{--disable-new-dtags}, no new dynamic tags will be
 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
diff --git a/ld/ldlang.c b/ld/ldlang.c
index 8bbf041..a19b46a 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -47,6 +47,7 @@
 
 /* Locals variables.  */
 static struct obstack stat_obstack;
+static struct obstack map_obstack;
 
 #define obstack_chunk_alloc xmalloc
 #define obstack_chunk_free free
@@ -65,6 +66,7 @@ static struct bfd_hash_table lang_definedness_table;
 
 /* 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 *,
@@ -72,6 +74,8 @@ static bfd_boolean load_symbols (lang_input_statement_type *,
 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 *,
@@ -688,6 +692,7 @@ void
 lang_map (void)
 {
   lang_memory_region_type *m;
+  bfd *p;
 
   minfo (_("\nMemory Configuration\n\n"));
   fprintf (config.map_file, "%-16s %-18s %-18s %s\n",
@@ -733,15 +738,66 @@ lang_map (void)
 
   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)
 {
-  section_userdata_type *new;
+  lean_section_userdata_type *new;
 
   if (s->bfd_section != NULL)
     return;
@@ -749,7 +805,7 @@ init_os (lang_output_section_statement_type *s)
   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));
+  new = stat_alloc (SECTION_USERDATA_SIZE);
 
   s->bfd_section = bfd_get_section_by_name (output_bfd, s->name);
   if (s->bfd_section == NULL)
@@ -2367,7 +2423,7 @@ print_input_statement (lang_input_statement_type *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 (struct bfd_link_hash_entry *hash_entry, void *ptr)
@@ -2393,6 +2449,18 @@ print_one_symbol (struct bfd_link_hash_entry *hash_entry, void *ptr)
   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
@@ -2445,7 +2513,10 @@ print_input_section (lang_input_section_type *in)
 	      minfo (_("%W (size before relaxing)\n"), i->_raw_size);
 	    }
 
-	  bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
+	  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));
diff --git a/ld/ldmain.c b/ld/ldmain.c
index eb036b0..f3df44f 100644
--- a/ld/ldmain.c
+++ b/ld/ldmain.c
@@ -274,6 +274,7 @@ main (int argc, char **argv)
   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
diff --git a/ld/lexsup.c b/ld/lexsup.c
index b377bd4..fcca4d3 100644
--- a/ld/lexsup.c
+++ b/ld/lexsup.c
@@ -142,7 +142,8 @@ enum option_values
   OPTION_PIE,
   OPTION_UNRESOLVED_SYMBOLS,
   OPTION_WARN_UNRESOLVED_SYMBOLS,
-  OPTION_ERROR_UNRESOLVED_SYMBOLS
+  OPTION_ERROR_UNRESOLVED_SYMBOLS,
+  OPTION_REDUCE_MEMORY_OVERHEADS
 };
 
 /* The long options.  This structure is used for both the option
@@ -445,7 +446,9 @@ static const struct ld_option ld_options[] =
   { {"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 }
+      '\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)
@@ -1221,6 +1224,9 @@ parse_args (unsigned argc, char **argv)
 	case OPTION_FINI:
 	  link_info.fini_function = optarg;
 	  break;
+	case OPTION_REDUCE_MEMORY_OVERHEADS:
+	  command_line.reduce_memory_overheads = TRUE;
+	  break;
 	}
     }