optimizations for 3x speedup in ld

optimizations for 3x speedup in ld

[Robert O'Callahan]

I work on Mozilla/Firefox and spend a lot of time linking libgklayout.so
(93MB with debug info). I did some work to speed up ld on this workload
and got a 3x improvement. See here for details:
http://weblogs.mozillazine.org/roc/archives/2005/02/optimizing_gnu.html
I've taken some care to make sure that the changes are localized and
there should be absolutely no impact on output (e.g., sections are
processed in exactly the same order as before). I reran the regression
tests and I pass exactly the same set of tests that CVS HEAD passes
(which actually means 4 unexpected failures ... this is x86-64).

So ... how do I push this upstream? Should I submit the patch as an
attachment? It's 69 lines deleted, 458 lines added in ld.h, ldlang.c,
ldlang.h.

Thanks,
Rob

Re: optimizations for 3x speedup in ld

[Nick Clifton]

[-- Attachment #1: Type: text/plain, Size: 929 bytes --]

Hi Rob,

> So ... how do I push this upstream? 

Well we would love to have them.

But first things first - can we accept them ?  In order for us to accept 
them the FSF needs a copyright assignment on file from whomever holds 
the copyright on the patches you are contributing.  (Presumably either 
yourself or the Mozilla Foundation ?)  I had a look but could not see 
such an assignment in my records, so I guess that obtaining one is the 
first step.  (If you do have such an assignment, please could you 
forward a copy of the confirmation email from the FSF to me ?)  I am 
attaching a form to fill out and send off to the FSF to get this process 
started.

> Should I submit the patch as an
> attachment? It's 69 lines deleted, 458 lines added in ld.h, ldlang.c,
> ldlang.h.

Attachments are fine.  Context diffs are great.  A ChangeLog entry to 
accompany the patch and explain what it does is wonderful.

Cheers
   Nick

[-- Attachment #2: future --]
[-- Type: text/plain, Size: 1005 bytes --]

---------------------------------------------------------------------------

request-assign.future:

Please email the following information to fsf-records@gnu.org, and we
will send you the assignment form for your past and future changes.
Please use your full name as the subject line of the message.


[What is the name of the program or package you're contributing to?]


[Did you copy any files or text written by someone else in these changes?
Even if that material is free software, we need to know about it.]


[Do you have an employer who might have a basis to claim to own
your changes?  Do you attend a school which might make such a claim?]


[For the copyright registration, what country are you a citizen of?]


[What year were you born?]


[Please write your email address here.]


[Please write your snail address here.]





[Which files have you changed so far, and which new files have you written
so far?]





---------------------------------------------------------------------------

Re: optimizations for 3x speedup in ld

[Robert O'Callahan]

[-- Attachment #1: Type: text/plain, Size: 2502 bytes --]

On Thu, 2005-02-17 at 16:18 +0000, Nick Clifton wrote:
> Hi Rob,
> 
> > So ... how do I push this upstream? 
> 
> Well we would love to have them.
> 
> But first things first - can we accept them ?  In order for us to accept 
> them the FSF needs a copyright assignment on file from whomever holds 
> the copyright on the patches you are contributing.  (Presumably either 
> yourself or the Mozilla Foundation ?)  I had a look but could not see 
> such an assignment in my records, so I guess that obtaining one is the 
> first step.  (If you do have such an assignment, please could you 
> forward a copy of the confirmation email from the FSF to me ?)  I am 
> attaching a form to fill out and send off to the FSF to get this process 
> started.

I work for Novell so Novell owns the copyright. I'll work on getting a
copyright assignment and get back to you.

> > Should I submit the patch as an
> > attachment? It's 69 lines deleted, 458 lines added in ld.h, ldlang.c,
> > ldlang.h.
> 
> Attachments are fine.  Context diffs are great.  A ChangeLog entry to 
> accompany the patch and explain what it does is wonderful.

I'm attaching the patch so people can see it/test it/comment on it,
keeping in mind this is copyright Novell for now.

Here's a ChangeLog entry:

2005-2-17  Robert O'Callahan  <rocallahan@novell.com>

       * ld.h: lean_user_section_struct, and the lean part of the fat
         struct, are unused. Remove them.
       * ldlang.h: Add optimized walk_wild_section code pointer
         and its parameters to lang_wild_statement_struct.
       * ldlang.c: (init_os) Eliminate initialization of unused
         lean_user_section_structs. 
         (lang_add_wild, analyze_walk_wild_section_handler,
         wild_spec_can_overlap, is_simple_wild) Analyze the parsed
         wildcard_list to determine if it fits any of the patterns we
         have specialized code for.
         (walk_wild_consider_section, walk_wild_section_general,
         walk_wild_section) Break up walk_wild_section into parts
         that can be specialized and parts that are the same across
         specializations.
         (section_iterator_callback, find_section, match_simple_wild)
         New support routines for the specialized code paths.
         (walk_wild_section_specs<N>_wild<M>) Add specialized code for
         a wildcard_list with N non-overlapping specs of which N-M are
         simple strings and M are simple wildcards (simple strings
         followed by a single '*').

Rob

[-- Attachment #2: patch --]
[-- Type: text/x-patch, Size: 28271 bytes --]

Index: ld.h
===================================================================
RCS file: /cvs/src/src/ld/ld.h,v
retrieving revision 1.24
diff -u -t -p -2 -0 -r1.24 ld.h
--- ld.h	4 Oct 2004 16:45:50 -0000	1.24
+++ ld.h	17 Feb 2005 20:02:07 -0000
@@ -71,62 +71,47 @@ typedef enum {
 } sort_type;
 
 extern sort_type sort_section;
 
 struct wildcard_spec {
   const char *name;
   struct name_list *exclude_name_list;
   sort_type sorted;
 };
 
 struct wildcard_list {
   struct wildcard_list *next;
   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)
 
 #define BYTE_SIZE       (1)
 #define SHORT_SIZE      (2)
 #define LONG_SIZE       (4)
 #define QUAD_SIZE       (8)
 
 typedef struct {
   /* 1 => assign space to common symbols even if `relocatable_output'.  */
   bfd_boolean force_common_definition;
 
   /* 1 => do not assign addresses to common symbols.  */
   bfd_boolean inhibit_common_definition;
   bfd_boolean relax;
 
   /* Name of runtime interpreter to invoke.  */
   char *interpreter;
 
   /* Name to give runtime libary from the -soname argument.  */
   char *soname;
Index: ldlang.c
===================================================================
RCS file: /cvs/src/src/ld/ldlang.c,v
retrieving revision 1.171
diff -u -t -p -2 -0 -r1.171 ldlang.c
--- ldlang.c	21 Jan 2005 04:15:58 -0000	1.171
+++ ldlang.c	17 Feb 2005 20:02:09 -0000
@@ -67,43 +67,40 @@ static struct bfd_hash_table lang_define
 /* Forward declarations.  */
 static void exp_init_os (etree_type *);
 static void init_map_userdata (bfd *, asection *, void *);
 static lang_input_statement_type *lookup_name (const char *);
 static bfd_boolean load_symbols (lang_input_statement_type *,
                                  lang_statement_list_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 *,
                                   lang_output_section_statement_type *);
 static void print_statements (void);
 static bfd_boolean lang_one_common (struct bfd_link_hash_entry *, void *);
 static void lang_record_phdrs (void);
 static void lang_do_version_exports_section (void);
 
-typedef void (*callback_t) (lang_wild_statement_type *, struct wildcard_list *,
-                            asection *, lang_input_statement_type *, void *);
-
 /* Exported variables.  */
 lang_output_section_statement_type *abs_output_section;
 lang_statement_list_type lang_output_section_statement;
 lang_statement_list_type *stat_ptr = &statement_list;
 lang_statement_list_type file_chain = { NULL, NULL };
 struct bfd_sym_chain entry_symbol = { NULL, NULL };
 const char *entry_section = ".text";
 bfd_boolean entry_from_cmdline;
 bfd_boolean lang_has_input_file = FALSE;
 bfd_boolean had_output_filename = FALSE;
 bfd_boolean lang_float_flag = FALSE;
 bfd_boolean delete_output_file_on_failure = FALSE;
 struct lang_nocrossrefs *nocrossref_list;
 struct unique_sections *unique_section_list;
 static bfd_boolean ldlang_sysrooted_script = FALSE;
 int lang_statement_iteration = 0;
 
 etree_type *base; /* Relocation base - or null */
 
 /* Return TRUE if the PATTERN argument is a wildcard pattern.
@@ -138,112 +135,504 @@ unique_section_p (const asection *sec)
 
   if (link_info.relocatable
       && sec->owner != NULL
       && bfd_is_group_section (sec->owner, sec))
     return TRUE;
 
   secnam = sec->name;
   for (unam = unique_section_list; unam; unam = unam->next)
     if (wildcardp (unam->name)
         ? fnmatch (unam->name, secnam, 0) == 0
         : strcmp (unam->name, secnam) == 0)
       {
         return TRUE;
       }
 
   return FALSE;
 }
 
 /* Generic traversal routines for finding matching sections.  */
 
+/* Try processing a section against a wildcard. This just calls
+   the callback unless the filename exclusion list is present
+   and excludes the file. It's hardly ever present so this
+   function is very fast. */
+static void
+walk_wild_consider_section (lang_wild_statement_type *ptr,
+                            lang_input_statement_type *file,
+                            asection *s,
+                            struct wildcard_list *sec,
+                            callback_t callback,
+                            void *data)
+{
+  bfd_boolean skip = FALSE;
+  struct name_list *list_tmp;
+
+  /* Don't process sections from files which were
+     excluded.  */
+  for (list_tmp = sec->spec.exclude_name_list;
+       list_tmp;
+       list_tmp = list_tmp->next)
+    {
+      if (wildcardp (list_tmp->name))
+        skip = fnmatch (list_tmp->name, file->filename, 0) == 0;
+      else
+        skip = strcmp (list_tmp->name, file->filename) == 0;
+
+      /* If this file is part of an archive, and the archive is
+         excluded, exclude this file.  */
+      if (! skip && file->the_bfd != NULL
+          && file->the_bfd->my_archive != NULL
+          && file->the_bfd->my_archive->filename != NULL)
+        {
+          if (wildcardp (list_tmp->name))
+            skip = fnmatch (list_tmp->name,
+                            file->the_bfd->my_archive->filename,
+                            0) == 0;
+          else
+            skip = strcmp (list_tmp->name,
+                           file->the_bfd->my_archive->filename) == 0;
+        }
+
+      if (skip)
+        break;
+    }
+
+  if (!skip)
+    (*callback) (ptr, sec, s, file, data);
+}
+
+/* 'Lowest common denominator routine that can handle everything correctly,
+   but slowly. */
 static void
-walk_wild_section (lang_wild_statement_type *ptr,
-                   lang_input_statement_type *file,
-                   callback_t callback,
-                   void *data)
+walk_wild_section_general (lang_wild_statement_type *ptr,
+                           lang_input_statement_type *file,
+                           callback_t callback,
+                           void *data)
 {
   asection *s;
-
-  if (file->just_syms_flag)
-    return;
+  struct wildcard_list *sec;
 
   for (s = file->the_bfd->sections; s != NULL; s = s->next)
     {
-      struct wildcard_list *sec;
-
       sec = ptr->section_list;
       if (sec == NULL)
         (*callback) (ptr, sec, s, file, data);
 
       while (sec != NULL)
         {
           bfd_boolean skip = FALSE;
-          struct name_list *list_tmp;
-
-          /* Don't process sections from files which were
-             excluded.  */
-          for (list_tmp = sec->spec.exclude_name_list;
-               list_tmp;
-               list_tmp = list_tmp->next)
-            {
-              if (wildcardp (list_tmp->name))
-                skip = fnmatch (list_tmp->name, file->filename, 0) == 0;
-              else
-                skip = strcmp (list_tmp->name, file->filename) == 0;
 
-              /* If this file is part of an archive, and the archive is
-                 excluded, exclude this file.  */
-              if (! skip && file->the_bfd != NULL
-                  && file->the_bfd->my_archive != NULL
-                  && file->the_bfd->my_archive->filename != NULL)
-                {
-                  if (wildcardp (list_tmp->name))
-                    skip = fnmatch (list_tmp->name,
-                                    file->the_bfd->my_archive->filename,
-                                    0) == 0;
-                  else
-                    skip = strcmp (list_tmp->name,
-                                   file->the_bfd->my_archive->filename) == 0;
-                }
-
-              if (skip)
-                break;
-            }
-
-          if (!skip && sec->spec.name != NULL)
+          if (sec->spec.name != NULL)
             {
               const char *sname = bfd_get_section_name (file->the_bfd, s);
-
+              
               if (wildcardp (sec->spec.name))
                 skip = fnmatch (sec->spec.name, sname, 0) != 0;
               else
                 skip = strcmp (sec->spec.name, sname) != 0;
             }
 
           if (!skip)
-            (*callback) (ptr, sec, s, file, data);
+            walk_wild_consider_section(ptr, file, s, sec, callback, data);
 
           sec = sec->next;
         }
     }
 }
 
+/* Routines to find a single section given its name. If there's more
+   than one section with that name, we report that. */
+typedef struct
+{
+  asection *found_section;
+  bfd_boolean multiple_sections_found;
+} section_iterator_callback_data;
+
+static bfd_boolean
+section_iterator_callback (bfd *bfd ATTRIBUTE_UNUSED, asection *s, void *data)
+{
+  section_iterator_callback_data* d = data;
+
+  if (d->found_section != NULL)
+    {
+      d->multiple_sections_found = TRUE;
+      return TRUE;
+    }
+
+  d->found_section = s;
+  return FALSE;
+}
+
+static asection *
+find_section(lang_input_statement_type *file,
+             struct wildcard_list *sec,
+             bfd_boolean *multiple_sections_found)
+{
+  section_iterator_callback_data cb_data = { NULL, FALSE };
+  bfd_get_section_by_name_if (file->the_bfd, sec->spec.name, 
+                              section_iterator_callback, &cb_data);
+  *multiple_sections_found = cb_data.multiple_sections_found;
+  return cb_data.found_section;
+}
+
+/* Code for handling simple wildcards without going through fnmatch,
+   which can be expensive because of charset translations etc. */
+
+/* A simple wild is a literal string followed by a single '*',
+   where the literal part is at least 4 characters long. */
+static bfd_boolean
+is_simple_wild (const char *name)
+{
+  size_t literal_len = strlen(name) - 1;
+  return strpbrk (name, "?[") == NULL
+    && strpbrk (name, "*") == name + literal_len
+    && literal_len >= 4;
+}
+
+static bfd_boolean
+match_simple_wild (const char *pattern, const char *name)
+{
+  /* The first four characters of the pattern are guaranteed valid non-wildcard
+     characters. So we can go faster. */
+  if (pattern[0] != name[0] || pattern[1] != name[1] || pattern[2] != name[2]
+      || pattern[3] != name[3])
+    return FALSE;
+
+  pattern += 4;
+  name += 4;
+  while (*pattern != '*')
+    {
+      if (*name != *pattern)
+        return FALSE;
+      ++pattern; ++name;
+    }
+
+  return TRUE;
+}
+
+/* Specialized, optimized routines for handling different kinds of
+   wildcards */
+
+static void
+walk_wild_section_specs1_wild0 (lang_wild_statement_type *ptr,
+                                lang_input_statement_type *file,
+                                callback_t callback,
+                                void *data)
+{
+  /* We can just do a hash lookup for the section with the right name.
+     But if that lookup discovers more than one section with the name
+     (should be rare), we fall back to the general algorithm because
+     we would otherwise have to sort the sections to make sure they
+     get processed in the bfd's order. */
+  bfd_boolean multiple_sections_found;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  asection* s0 = find_section (file, sec0, &multiple_sections_found);
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  if (s0)
+    walk_wild_consider_section (ptr, file, s0, sec0, callback, data);
+}
+
+static void
+walk_wild_section_specs1_wild1 (lang_wild_statement_type *ptr,
+                                lang_input_statement_type *file,
+                                callback_t callback,
+                                void *data)
+{
+  asection *s;
+  struct wildcard_list *wildsec0 = ptr->handler_data[0];
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      const char *sname = bfd_get_section_name (file->the_bfd, s);
+      bfd_boolean skip = !match_simple_wild (wildsec0->spec.name, sname);
+      
+      if (!skip)
+        walk_wild_consider_section(ptr, file, s, wildsec0, callback, data);
+    }
+}
+
+static void
+walk_wild_section_specs2_wild1 (lang_wild_statement_type *ptr,
+                                lang_input_statement_type *file,
+                                callback_t callback,
+                                void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *wildsec1 = ptr->handler_data[1];
+
+  bfd_boolean multiple_sections_found;
+  asection* s0 = find_section (file, sec0, &multiple_sections_found);
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+  /* Note that if the section was not found, s0 is NULL and
+     we'll simply never succeed the 's == s0' test below. */
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      /* Recall that in this code path, a section cannot satisfy more
+         than one spec, so if s == s0 then it cannot match
+         wildspec1. */
+      if (s == s0)
+        walk_wild_consider_section(ptr, file, s, sec0, callback, data);
+      else
+        {
+          const char *sname = bfd_get_section_name (file->the_bfd, s);
+          bfd_boolean skip = !match_simple_wild (wildsec1->spec.name, sname);
+          
+          if (!skip)
+            walk_wild_consider_section(ptr, file, s, wildsec1, callback, data);
+        }
+    }
+}
+
+static void
+walk_wild_section_specs3_wild2 (lang_wild_statement_type *ptr,
+                                lang_input_statement_type *file,
+                                callback_t callback,
+                                void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *wildsec1 = ptr->handler_data[1];
+  struct wildcard_list *wildsec2 = ptr->handler_data[2];
+
+  bfd_boolean multiple_sections_found;
+  asection* s0 = find_section (file, sec0, &multiple_sections_found);
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      if (s == s0)
+        walk_wild_consider_section(ptr, file, s, sec0, callback, data);
+      else
+        {
+          const char *sname = bfd_get_section_name (file->the_bfd, s);
+          bfd_boolean skip = !match_simple_wild (wildsec1->spec.name, sname);
+          
+          if (!skip)
+            walk_wild_consider_section(ptr, file, s, wildsec1, callback, data);
+          else
+            {
+              skip = !match_simple_wild (wildsec2->spec.name, sname);
+              if (!skip)
+                walk_wild_consider_section(ptr, file, s, wildsec2, callback, data);
+            }
+        }
+    }
+}
+
+static void
+walk_wild_section_specs4_wild2 (lang_wild_statement_type *ptr,
+                                lang_input_statement_type *file,
+                                callback_t callback,
+                                void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *sec1 = ptr->handler_data[1];
+  struct wildcard_list *wildsec2 = ptr->handler_data[2];
+  struct wildcard_list *wildsec3 = ptr->handler_data[3];
+
+  bfd_boolean multiple_sections_found;
+  asection* s0 = find_section (file, sec0, &multiple_sections_found);
+  asection* s1;
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  s1 = find_section (file, sec1, &multiple_sections_found);
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      if (s == s0)
+        walk_wild_consider_section(ptr, file, s, sec0, callback, data);
+      else
+        if (s == s1)
+          walk_wild_consider_section(ptr, file, s, sec1, callback, data);
+        else
+          {
+            const char *sname = bfd_get_section_name (file->the_bfd, s);
+            bfd_boolean skip = !match_simple_wild (wildsec2->spec.name, sname);
+            
+            if (!skip)
+              walk_wild_consider_section(ptr, file, s, wildsec2, callback, data);
+            else
+              {
+                skip = !match_simple_wild (wildsec3->spec.name, sname);
+                if (!skip)
+                  walk_wild_consider_section(ptr, file, s, wildsec3, callback, data);
+              }
+          }
+    }
+}
+
+static void
+walk_wild_section (lang_wild_statement_type *ptr,
+                   lang_input_statement_type *file,
+                   callback_t callback,
+                   void *data)
+{
+  if (file->just_syms_flag)
+    return;
+
+  (*ptr->walk_wild_section_handler) (ptr, file, callback, data);
+}
+
+/*
+ * Returns TRUE when name1 is a wildcard spec that might match
+ * something name2 can match. We're conservative: we return FALSE
+ * only if the prefixes of name1 and name2 are different up to the
+ * first wildcard character.
+ */
+static bfd_boolean
+wild_spec_can_overlap (const char *name1, const char *name2)
+{
+  char *prefix1 = strpbrk (name1, "?*[");
+  char *prefix2 = strpbrk (name2, "?*[");
+  /* Note that if there is no wildcard character, then we treat the
+     terminating 0 as part of the prefix. Thus ".text" won't match
+     ".text." or ".text.*", for example. */
+  int prefix1_len = prefix1 != NULL ? (size_t)(prefix1 - name1) : strlen(name1) + 1;
+  int prefix2_len = prefix2 != NULL ? (size_t)(prefix2 - name2) : strlen(name2) + 1;
+  int min_prefix_len = prefix1_len < prefix2_len ? prefix1_len : prefix2_len;
+
+  return memcmp(name1, name2, min_prefix_len) == 0;
+}
+
+/*
+ * Select specialized code to handle various kinds of wildcard
+ * statements.
+ */
+static void
+analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
+{
+  int sec_count = 0;
+  int wild_name_count = 0;
+  struct wildcard_list *sec;
+  int signature;
+  int data_counter;
+  
+  ptr->walk_wild_section_handler = walk_wild_section_general;
+
+  /* Count how many wildcard_specs there are, and how many of those
+     actually use wildcards in the name. Also, bail out if any of the
+     wildcard names are NULL. (Can this actually happen?
+     walk_wild_section used to test for it.) And bail out if any
+     of the wildcards are more complex than a simple string
+     ending in a single '*'. */
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      ++sec_count;
+      if (sec->spec.name == NULL)
+        return;
+      if (wildcardp (sec->spec.name))
+        {
+          ++wild_name_count;
+          if (!is_simple_wild (sec->spec.name))
+            return;
+        }
+    }
+
+  /* The zero-spec case would be easy to optimize but it doesn't
+     happen in practice. Likewise, more than 4 specs doesn't
+     happen in practice. */
+  if (sec_count == 0 || sec_count > 4)
+    return;
+
+  /* Check that no two specs can match the same section */
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      struct wildcard_list *sec2;
+      for (sec2 = sec->next; sec2 != NULL; sec2 = sec2->next)
+        {
+          if (wild_spec_can_overlap (sec->spec.name, sec2->spec.name))
+            return;
+        }
+    }
+
+  signature = (sec_count << 8) + wild_name_count;
+  switch (signature)
+    {
+    case 0x0100:
+      ptr->walk_wild_section_handler = walk_wild_section_specs1_wild0;
+      break;
+    case 0x0101:
+      ptr->walk_wild_section_handler = walk_wild_section_specs1_wild1;
+      break;
+    case 0x0201:
+      ptr->walk_wild_section_handler = walk_wild_section_specs2_wild1;
+      break;
+    case 0x0302:
+      ptr->walk_wild_section_handler = walk_wild_section_specs3_wild2;
+      break;
+    case 0x0402:
+      ptr->walk_wild_section_handler = walk_wild_section_specs4_wild2;
+      break;
+    default:
+      return;
+    }
+
+  /* Now fill the data array with pointers to the specs, first the
+     specs with non-wildcard names, then the specs with wildcard
+     names. It's OK to process the specs in different order from the
+     given order, because we've already determined that no section
+     will match more than one spec. */
+  data_counter = 0;
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      if (!wildcardp (sec->spec.name))
+        {
+          ptr->handler_data[data_counter] = sec;
+          ++data_counter;
+        }
+    }
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      if (wildcardp (sec->spec.name))
+        {
+          ptr->handler_data[data_counter] = sec;
+          ++data_counter;
+        }
+    }
+}
+
 /* Handle a wild statement for a single file F.  */
 
 static void
 walk_wild_file (lang_wild_statement_type *s,
                 lang_input_statement_type *f,
                 callback_t callback,
                 void *data)
 {
   if (f->the_bfd == NULL
       || ! bfd_check_format (f->the_bfd, bfd_archive))
     walk_wild_section (s, f, callback, data);
   else
     {
       bfd *member;
 
       /* This is an archive file.  We must map each member of the
          archive separately.  */
       member = bfd_openr_next_archived_file (f->the_bfd, NULL);
       while (member != NULL)
         {
@@ -1157,65 +1546,65 @@ sort_def_symbol (hash_entry, info)
           /* 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 = 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;
 
   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);
-  memset (new, 0, SECTION_USERDATA_SIZE);
-
   s->bfd_section = bfd_get_section_by_name (output_bfd, s->name);
   if (s->bfd_section == NULL)
     s->bfd_section = bfd_make_section (output_bfd, s->name);
   if (s->bfd_section == NULL)
     {
       einfo (_("%P%F: output format %s cannot represent section called %s\n"),
              output_bfd->xvec->name, s->name);
     }
   s->bfd_section->output_section = s->bfd_section;
 
   /* We initialize an output sections output offset to minus its own
      vma to allow us to output a section through itself.  */
   s->bfd_section->output_offset = 0;
-  get_userdata (s->bfd_section) = new;
+  if (!command_line.reduce_memory_overheads)
+    {
+      fat_section_userdata_type* new = stat_alloc (sizeof (fat_section_userdata_type));
+      memset (new, 0, sizeof (fat_section_userdata_type));
+      get_userdata (s->bfd_section) = new;
+    }
 
   /* If there is a base address, make sure that any sections it might
      mention are initialized.  */
   if (s->addr_tree != NULL)
     exp_init_os (s->addr_tree);
 
   if (s->load_base != NULL)
     exp_init_os (s->load_base);
 }
 
 /* Make sure that all output sections mentioned in an expression are
    initialized.  */
 
 static void
 exp_init_os (etree_type *exp)
 {
   switch (exp->type.node_class)
     {
     case etree_assign:
       exp_init_os (exp->assign.src);
@@ -4908,40 +5297,42 @@ lang_add_wild (struct wildcard_spec *fil
 
   if (filespec != NULL && filespec->name != NULL)
     {
       if (strcmp (filespec->name, "*") == 0)
         filespec->name = NULL;
       else if (! wildcardp (filespec->name))
         lang_has_input_file = TRUE;
     }
 
   new = new_stat (lang_wild_statement, stat_ptr);
   new->filename = NULL;
   new->filenames_sorted = FALSE;
   if (filespec != NULL)
     {
       new->filename = filespec->name;
       new->filenames_sorted = filespec->sorted == by_name;
     }
   new->section_list = section_list;
   new->keep_sections = keep_sections;
   lang_list_init (&new->children);
+
+  analyze_walk_wild_section_handler (new);
 }
 
 void
 lang_section_start (const char *name, etree_type *address,
                     const segment_type *segment)
 {
   lang_address_statement_type *ad;
 
   ad = new_stat (lang_address_statement, stat_ptr);
   ad->section_name = name;
   ad->address = address;
   ad->segment = segment;
 }
 
 /* Set the start symbol to NAME.  CMDLINE is nonzero if this is called
    because of a -e argument on the command line, or zero if this is
    called by ENTRY in a linker script.  Command line arguments take
    precedence.  */
 
 void
Index: ldlang.h
===================================================================
RCS file: /cvs/src/src/ld/ldlang.h,v
retrieving revision 1.43
diff -u -t -p -2 -0 -r1.43 ldlang.h
--- ldlang.h	21 Jan 2005 04:15:58 -0000	1.43
+++ ldlang.h	17 Feb 2005 20:02:09 -0000
@@ -281,49 +281,62 @@ typedef struct lang_input_statement_stru
 
   const char *target;
   bfd_boolean real;
 } lang_input_statement_type;
 
 typedef struct
 {
   lang_statement_header_type header;
   asection *section;
   lang_input_statement_type *ifile;
 
 } lang_input_section_type;
 
 typedef struct
 {
   lang_statement_header_type header;
   asection *section;
   union lang_statement_union *file;
 } lang_afile_asection_pair_statement_type;
 
-typedef struct lang_wild_statement_struct
+typedef struct lang_wild_statement_struct lang_wild_statement_type;
+
+typedef void (*callback_t) (lang_wild_statement_type *, struct wildcard_list *,
+                            asection *, lang_input_statement_type *, void *);
+
+typedef void (*walk_wild_section_handler_t) (lang_wild_statement_type *,
+                                             lang_input_statement_type *,
+                                             callback_t callback,
+                                             void *data);
+
+struct lang_wild_statement_struct
 {
   lang_statement_header_type header;
   const char *filename;
   bfd_boolean filenames_sorted;
   struct wildcard_list *section_list;
   bfd_boolean keep_sections;
   lang_statement_list_type children;
-} lang_wild_statement_type;
+
+  walk_wild_section_handler_t walk_wild_section_handler;
+  struct wildcard_list *handler_data[4];
+};
 
 typedef struct lang_address_statement_struct
 {
   lang_statement_header_type header;
   const char *section_name;
   union etree_union *address;
   const segment_type *segment;
 } lang_address_statement_type;
 
 typedef struct
 {
   lang_statement_header_type header;
   bfd_vma output_offset;
   size_t size;
   asection *output_section;
   fill_type *fill;
 } lang_padding_statement_type;
 
 /* A group statement collects a set of libraries together.  The
    libraries are searched multiple times, until no new undefined

Re: optimizations for 3x speedup in ld

[Ian Lance Taylor]

Robert O'Callahan <rocallahan@novell.com> writes:

> I work for Novell so Novell owns the copyright. I'll work on getting a
> copyright assignment and get back to you.

Novell has a blanket copyright assignment for the binutils, so if you
are a regular employee doing work for hire (as you probably are) then
no further assignment is needed.

Ian

Re: optimizations for 3x speedup in ld

[Robert O'Callahan]

On Thu, 2005-02-17 at 16:34 -0500, Ian Lance Taylor wrote:
> Robert O'Callahan <rocallahan@novell.com> writes:
> 
> > I work for Novell so Novell owns the copyright. I'll work on getting a
> > copyright assignment and get back to you.
> 
> Novell has a blanket copyright assignment for the binutils, so if you
> are a regular employee doing work for hire (as you probably are) then
> no further assignment is needed.

Yes, I am. Cool!

Rob

Re: optimizations for 3x speedup in ld

[Nick Clifton]

Hi Rob,

> I'm attaching the patch so people can see it/test it/comment on it,
> keeping in mind this is copyright Novell for now.

I have had a look over the patch - it certainly does improve the link 
times.  There were a few small issues with regard to formatting and 
comment layout, but nothing serious.  So provided that Novell want to 
contribute the code we will be very happy to accept it.

Please could you check with Novell management to make sure that it is OK 
for you to contribute the patch and if so, please let us know.

Cheers
   Nick

PS.  I had a thought that might improve the speed of the 
walk_wildcard_consider_section() function.  What if you removed the 
duplicate test of wildcardp (list_tmp->name) ?  eg:

static void
walk_wild_consider_section (lang_wild_statement_type *ptr,
                             lang_input_statement_type *file,
                             asection *s,
                             struct wildcard_list *sec,
                             callback_t callback,
                             void *data)
{
   struct name_list *list_tmp;

   /* Don't process sections from files which were excluded.  */
   for (list_tmp = sec->spec.exclude_name_list;
        list_tmp;
        list_tmp = list_tmp->next)
     {
       bfd_boolean skip;
       typedef int (*cmp_fn) (const char *, const char *, int);
       cmp_fn cmp;

       cmp = wildcardp (list_tmp->name) ? fnmatch : (cmp_fn) strcmp;

       skip = cmp (list_tmp->name, file->filename, 0) == 0;

       /* If this file is part of an archive, and the
	 archive is excluded, exclude this file.  */
       if (! skip
	  && file->the_bfd != NULL
           && file->the_bfd->my_archive != NULL
           && file->the_bfd->my_archive->filename != NULL)
	skip = cmp (list_tmp->name,
		    file->the_bfd->my_archive->filename, 0) == 0;

       if (skip)
         return;
     }

   callback (ptr, sec, s, file, data);
}

Re: optimizations for 3x speedup in ld

[Robert O'Callahan]

On Fri, 2005-02-18 at 16:09 +0000, Nick Clifton wrote:
> > I'm attaching the patch so people can see it/test it/comment on it,
> > keeping in mind this is copyright Novell for now.
> 
> I have had a look over the patch - it certainly does improve the link 
> times.  There were a few small issues with regard to formatting and 
> comment layout, but nothing serious.  So provided that Novell want to 
> contribute the code we will be very happy to accept it.
> 
> Please could you check with Novell management to make sure that it is OK 
> for you to contribute the patch and if so, please let us know.

Yep, working on it.

> PS.  I had a thought that might improve the speed of the 
> walk_wildcard_consider_section() function.  What if you removed the 
> duplicate test of wildcardp (list_tmp->name) ?  eg:

Sure, you could do that. I didn't put any effort into optimizing that
code because very few wildcard statements have exclusion lists, so it
doesn't really matter.

Rob

Re: optimizations for 3x speedup in ld

[Jakub Jelinek]

On Fri, Feb 18, 2005 at 09:37:49AM +1300, Robert O'Callahan wrote:
> I'm attaching the patch so people can see it/test it/comment on it,
> keeping in mind this is copyright Novell for now.

What happened with this patch?
Is this stuck because of code assignment (Ian's mail suggested Novell
has blanket copyright assignment for binutils), or because of the
requested formatting changes etc.?

The patch as is doesn't apply cleanly to current CVS binutils,
so I took it, make it apply, fixed whatever formatting issues I found out
and changed a few things I spotted.

Here is the result:

2005-03-29  Jakub Jelinek  <jakub@redhat.com>

	* ldlang.c: Formatting.
	(walk_wild_consider_section): Remember return value from wildcardp.
	(is_simple_wild): Use strcspn instead of 2 strpbrk calls and strlen.
	(wild_spec_can_overlap): Use strcspn instead of strpbrk and strlen.

2005-02-17  Robert O'Callahan  <rocallahan@novell.com>

	* ld.h (lean_section_userdata_type): Remove.
	(fat_section_userdata_type): Remove file field.
	(SECTION_USERDATA_SIZE): Remove.
	* ldlang.c (init_os): Eliminate initialization of unused
	lean_section_userdata_type.

	* ldlang.h (callback_t, walk_wild_section_handler_t): New
	typedefs.
	(struct lang_wild_statement_struct): Add walk_wild_section_handler
	and handler_data fields.
	* ldlang.c (callback_t): Removed.
	(walk_wild_consider_section, walk_wild_section_general,
	section_iterator_callback, find_section, is_simple_wild,
	match_simple_wild, walk_wild_section_specs1_wild0,
	walk_wild_section_specs1_wild1, walk_wild_section_specs2_wild1,
	walk_wild_section_specs3_wild2, walk_wild_section_specs4_wild2,
	wild_spec_can_overlap, analyze_walk_wild_section_handler): New
	functions.
	(lang_add_wild): Call analyze_walk_wild_section_handler.
	(walk_wild_section): Renamed to walk_wild_section_general and
	created a wrapper function.
	(section_iterator_callback_data): New typedef.

--- ld/ld.h	16 Mar 2005 21:52:42 -0000	1.26
+++ ld/ld.h	29 Mar 2005 13:02:02 -0000
@@ -1,6 +1,6 @@
 /* ld.h -- general linker header file
    Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
-   2001, 2002, 2003, 2004
+   2001, 2002, 2003, 2004, 2005
    Free Software Foundation, Inc.
 
    This file is part of GLD, the Gnu Linker.
@@ -89,28 +89,15 @@ struct map_symbol_def {
   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)
 
 #define BYTE_SIZE	(1)
--- ld/ldlang.c	18 Mar 2005 13:56:26 -0000	1.176
+++ ld/ldlang.c	29 Mar 2005 13:02:03 -0000
@@ -84,9 +84,6 @@ static bfd_boolean lang_one_common (stru
 static void lang_record_phdrs (void);
 static void lang_do_version_exports_section (void);
 
-typedef void (*callback_t) (lang_wild_statement_type *, struct wildcard_list *,
-			    asection *, lang_input_statement_type *, void *);
-
 /* Exported variables.  */
 lang_output_section_statement_type *abs_output_section;
 lang_statement_list_type lang_output_section_statement;
@@ -155,21 +152,71 @@ unique_section_p (const asection *sec)
 
 /* Generic traversal routines for finding matching sections.  */
 
+/* Try processing a section against a wildcard.  This just calls
+   the callback unless the filename exclusion list is present
+   and excludes the file.  It's hardly ever present so this
+   function is very fast.  */
+
+static void
+walk_wild_consider_section (lang_wild_statement_type *ptr,
+			    lang_input_statement_type *file,
+			    asection *s,
+			    struct wildcard_list *sec,
+			    callback_t callback,
+			    void *data)
+{
+  bfd_boolean skip = FALSE;
+  struct name_list *list_tmp;
+
+  /* Don't process sections from files which were
+     excluded.  */
+  for (list_tmp = sec->spec.exclude_name_list;
+       list_tmp;
+       list_tmp = list_tmp->next)
+    {
+      bfd_boolean is_wildcard = wildcardp (list_tmp->name);
+      if (is_wildcard)
+	skip = fnmatch (list_tmp->name, file->filename, 0) == 0;
+      else
+	skip = strcmp (list_tmp->name, file->filename) == 0;
+
+      /* If this file is part of an archive, and the archive is
+	 excluded, exclude this file.  */
+      if (! skip && file->the_bfd != NULL
+	  && file->the_bfd->my_archive != NULL
+	  && file->the_bfd->my_archive->filename != NULL)
+	{
+	  if (is_wildcard)
+	    skip = fnmatch (list_tmp->name,
+			    file->the_bfd->my_archive->filename,
+			    0) == 0;
+	  else
+	    skip = strcmp (list_tmp->name,
+			   file->the_bfd->my_archive->filename) == 0;
+	}
+
+      if (skip)
+	break;
+    }
+
+  if (!skip)
+    (*callback) (ptr, sec, s, file, data);
+}
+
+/* Lowest common denominator routine that can handle everything correctly,
+   but slowly.  */
+
 static void
-walk_wild_section (lang_wild_statement_type *ptr,
-		   lang_input_statement_type *file,
-		   callback_t callback,
-		   void *data)
+walk_wild_section_general (lang_wild_statement_type *ptr,
+			   lang_input_statement_type *file,
+			   callback_t callback,
+			   void *data)
 {
   asection *s;
-
-  if (file->just_syms_flag)
-    return;
+  struct wildcard_list *sec;
 
   for (s = file->the_bfd->sections; s != NULL; s = s->next)
     {
-      struct wildcard_list *sec;
-
       sec = ptr->section_list;
       if (sec == NULL)
 	(*callback) (ptr, sec, s, file, data);
@@ -177,39 +224,8 @@ walk_wild_section (lang_wild_statement_t
       while (sec != NULL)
 	{
 	  bfd_boolean skip = FALSE;
-	  struct name_list *list_tmp;
 
-	  /* Don't process sections from files which were
-	     excluded.  */
-	  for (list_tmp = sec->spec.exclude_name_list;
-	       list_tmp;
-	       list_tmp = list_tmp->next)
-	    {
-	      if (wildcardp (list_tmp->name))
-		skip = fnmatch (list_tmp->name, file->filename, 0) == 0;
-	      else
-		skip = strcmp (list_tmp->name, file->filename) == 0;
-
-	      /* If this file is part of an archive, and the archive is
-		 excluded, exclude this file.  */
-	      if (! skip && file->the_bfd != NULL
-		  && file->the_bfd->my_archive != NULL
-		  && file->the_bfd->my_archive->filename != NULL)
-		{
-		  if (wildcardp (list_tmp->name))
-		    skip = fnmatch (list_tmp->name,
-				    file->the_bfd->my_archive->filename,
-				    0) == 0;
-		  else
-		    skip = strcmp (list_tmp->name,
-				   file->the_bfd->my_archive->filename) == 0;
-		}
-
-	      if (skip)
-		break;
-	    }
-
-	  if (!skip && sec->spec.name != NULL)
+	  if (sec->spec.name != NULL)
 	    {
 	      const char *sname = bfd_get_section_name (file->the_bfd, s);
 
@@ -220,13 +236,381 @@ walk_wild_section (lang_wild_statement_t
 	    }
 
 	  if (!skip)
-	    (*callback) (ptr, sec, s, file, data);
+	    walk_wild_consider_section (ptr, file, s, sec, callback, data);
 
 	  sec = sec->next;
 	}
     }
 }
 
+/* Routines to find a single section given its name.  If there's more
+   than one section with that name, we report that.  */
+
+typedef struct
+{
+  asection *found_section;
+  bfd_boolean multiple_sections_found;
+} section_iterator_callback_data;
+
+static bfd_boolean
+section_iterator_callback (bfd *bfd ATTRIBUTE_UNUSED, asection *s, void *data)
+{
+  section_iterator_callback_data *d = data;
+
+  if (d->found_section != NULL)
+    {
+      d->multiple_sections_found = TRUE;
+      return TRUE;
+    }
+
+  d->found_section = s;
+  return FALSE;
+}
+
+static asection *
+find_section (lang_input_statement_type *file,
+	      struct wildcard_list *sec,
+	      bfd_boolean *multiple_sections_found)
+{
+  section_iterator_callback_data cb_data = { NULL, FALSE };
+
+  bfd_get_section_by_name_if (file->the_bfd, sec->spec.name, 
+			      section_iterator_callback, &cb_data);
+  *multiple_sections_found = cb_data.multiple_sections_found;
+  return cb_data.found_section;
+}
+
+/* Code for handling simple wildcards without going through fnmatch,
+   which can be expensive because of charset translations etc.  */
+
+/* A simple wild is a literal string followed by a single '*',
+   where the literal part is at least 4 characters long.  */
+
+static bfd_boolean
+is_simple_wild (const char *name)
+{
+  size_t len = strcspn (name, "*?[");
+  return len >= 4 && name[len] == '*' && name[len + 1] == '\0';
+}
+
+static bfd_boolean
+match_simple_wild (const char *pattern, const char *name)
+{
+  /* The first four characters of the pattern are guaranteed valid
+     non-wildcard characters.  So we can go faster.  */
+  if (pattern[0] != name[0] || pattern[1] != name[1]
+      || pattern[2] != name[2] || pattern[3] != name[3])
+    return FALSE;
+
+  pattern += 4;
+  name += 4;
+  while (*pattern != '*')
+    if (*name++ != *pattern++)
+      return FALSE;
+
+  return TRUE;
+}
+
+/* Specialized, optimized routines for handling different kinds of
+   wildcards */
+
+static void
+walk_wild_section_specs1_wild0 (lang_wild_statement_type *ptr,
+				lang_input_statement_type *file,
+				callback_t callback,
+				void *data)
+{
+  /* We can just do a hash lookup for the section with the right name.
+     But if that lookup discovers more than one section with the name
+     (should be rare), we fall back to the general algorithm because
+     we would otherwise have to sort the sections to make sure they
+     get processed in the bfd's order.  */
+  bfd_boolean multiple_sections_found;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  asection *s0 = find_section (file, sec0, &multiple_sections_found);
+
+  if (multiple_sections_found)
+    walk_wild_section_general (ptr, file, callback, data);
+  else if (s0)
+    walk_wild_consider_section (ptr, file, s0, sec0, callback, data);
+}
+
+static void
+walk_wild_section_specs1_wild1 (lang_wild_statement_type *ptr,
+				lang_input_statement_type *file,
+				callback_t callback,
+				void *data)
+{
+  asection *s;
+  struct wildcard_list *wildsec0 = ptr->handler_data[0];
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      const char *sname = bfd_get_section_name (file->the_bfd, s);
+      bfd_boolean skip = !match_simple_wild (wildsec0->spec.name, sname);
+
+      if (!skip)
+	walk_wild_consider_section (ptr, file, s, wildsec0, callback, data);
+    }
+}
+
+static void
+walk_wild_section_specs2_wild1 (lang_wild_statement_type *ptr,
+				lang_input_statement_type *file,
+				callback_t callback,
+				void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *wildsec1 = ptr->handler_data[1];
+  bfd_boolean multiple_sections_found;
+  asection *s0 = find_section (file, sec0, &multiple_sections_found);
+
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  /* Note that if the section was not found, s0 is NULL and
+     we'll simply never succeed the s == s0 test below.  */
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      /* Recall that in this code path, a section cannot satisfy more
+	 than one spec, so if s == s0 then it cannot match
+	 wildspec1.  */
+      if (s == s0)
+	walk_wild_consider_section (ptr, file, s, sec0, callback, data);
+      else
+	{
+	  const char *sname = bfd_get_section_name (file->the_bfd, s);
+	  bfd_boolean skip = !match_simple_wild (wildsec1->spec.name, sname);
+
+	  if (!skip)
+	    walk_wild_consider_section (ptr, file, s, wildsec1, callback,
+					data);
+	}
+    }
+}
+
+static void
+walk_wild_section_specs3_wild2 (lang_wild_statement_type *ptr,
+				lang_input_statement_type *file,
+				callback_t callback,
+				void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *wildsec1 = ptr->handler_data[1];
+  struct wildcard_list *wildsec2 = ptr->handler_data[2];
+  bfd_boolean multiple_sections_found;
+  asection *s0 = find_section (file, sec0, &multiple_sections_found);
+
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      if (s == s0)
+	walk_wild_consider_section (ptr, file, s, sec0, callback, data);
+      else
+	{
+	  const char *sname = bfd_get_section_name (file->the_bfd, s);
+	  bfd_boolean skip = !match_simple_wild (wildsec1->spec.name, sname);
+
+	  if (!skip)
+	    walk_wild_consider_section (ptr, file, s, wildsec1, callback, data);
+	  else
+	    {
+	      skip = !match_simple_wild (wildsec2->spec.name, sname);
+	      if (!skip)
+		walk_wild_consider_section (ptr, file, s, wildsec2, callback,
+					    data);
+	    }
+	}
+    }
+}
+
+static void
+walk_wild_section_specs4_wild2 (lang_wild_statement_type *ptr,
+				lang_input_statement_type *file,
+				callback_t callback,
+				void *data)
+{
+  asection *s;
+  struct wildcard_list *sec0 = ptr->handler_data[0];
+  struct wildcard_list *sec1 = ptr->handler_data[1];
+  struct wildcard_list *wildsec2 = ptr->handler_data[2];
+  struct wildcard_list *wildsec3 = ptr->handler_data[3];
+  bfd_boolean multiple_sections_found;
+  asection *s0 = find_section (file, sec0, &multiple_sections_found), *s1;
+
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  s1 = find_section (file, sec1, &multiple_sections_found);
+  if (multiple_sections_found)
+    {
+      walk_wild_section_general (ptr, file, callback, data);
+      return;
+    }
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      if (s == s0)
+	walk_wild_consider_section (ptr, file, s, sec0, callback, data);
+      else
+	if (s == s1)
+	  walk_wild_consider_section (ptr, file, s, sec1, callback, data);
+	else
+	  {
+	    const char *sname = bfd_get_section_name (file->the_bfd, s);
+	    bfd_boolean skip = !match_simple_wild (wildsec2->spec.name,
+						   sname);
+
+	    if (!skip)
+	      walk_wild_consider_section (ptr, file, s, wildsec2, callback,
+					  data);
+	    else
+	      {
+		skip = !match_simple_wild (wildsec3->spec.name, sname);
+		if (!skip)
+		  walk_wild_consider_section (ptr, file, s, wildsec3,
+					      callback, data);
+	      }
+	  }
+    }
+}
+
+static void
+walk_wild_section (lang_wild_statement_type *ptr,
+		   lang_input_statement_type *file,
+		   callback_t callback,
+		   void *data)
+{
+  if (file->just_syms_flag)
+    return;
+
+  (*ptr->walk_wild_section_handler) (ptr, file, callback, data);
+}
+
+/* Returns TRUE when name1 is a wildcard spec that might match
+   something name2 can match.  We're conservative: we return FALSE
+   only if the prefixes of name1 and name2 are different up to the
+   first wildcard character.  */
+
+static bfd_boolean
+wild_spec_can_overlap (const char *name1, const char *name2)
+{
+  size_t prefix1_len = strcspn (name1, "?*[");
+  size_t prefix2_len = strcspn (name2, "?*[");
+  size_t min_prefix_len;
+
+  /* Note that if there is no wildcard character, then we treat the
+     terminating 0 as part of the prefix.  Thus ".text" won't match
+     ".text." or ".text.*", for example.  */
+  if (name1[prefix1_len] == '\0')
+    prefix1_len++;
+  if (name2[prefix2_len] == '\0')
+    prefix2_len++;
+
+  min_prefix_len = prefix1_len < prefix2_len ? prefix1_len : prefix2_len;
+
+  return memcmp (name1, name2, min_prefix_len) == 0;
+}
+
+/* Select specialized code to handle various kinds of wildcard
+   statements.  */
+
+static void
+analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
+{
+  int sec_count = 0;
+  int wild_name_count = 0;
+  struct wildcard_list *sec;
+  int signature;
+  int data_counter;
+
+  ptr->walk_wild_section_handler = walk_wild_section_general;
+
+  /* Count how many wildcard_specs there are, and how many of those
+     actually use wildcards in the name.  Also, bail out if any of the
+     wildcard names are NULL. (Can this actually happen?
+     walk_wild_section used to test for it.)  And bail out if any
+     of the wildcards are more complex than a simple string
+     ending in a single '*'.  */
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      ++sec_count;
+      if (sec->spec.name == NULL)
+	return;
+      if (wildcardp (sec->spec.name))
+	{
+	  ++wild_name_count;
+	  if (!is_simple_wild (sec->spec.name))
+	    return;
+	}
+    }
+
+  /* The zero-spec case would be easy to optimize but it doesn't
+     happen in practice.  Likewise, more than 4 specs doesn't
+     happen in practice.  */
+  if (sec_count == 0 || sec_count > 4)
+    return;
+
+  /* Check that no two specs can match the same section.  */
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    {
+      struct wildcard_list *sec2;
+      for (sec2 = sec->next; sec2 != NULL; sec2 = sec2->next)
+	{
+	  if (wild_spec_can_overlap (sec->spec.name, sec2->spec.name))
+	    return;
+	}
+    }
+
+  signature = (sec_count << 8) + wild_name_count;
+  switch (signature)
+    {
+    case 0x0100:
+      ptr->walk_wild_section_handler = walk_wild_section_specs1_wild0;
+      break;
+    case 0x0101:
+      ptr->walk_wild_section_handler = walk_wild_section_specs1_wild1;
+      break;
+    case 0x0201:
+      ptr->walk_wild_section_handler = walk_wild_section_specs2_wild1;
+      break;
+    case 0x0302:
+      ptr->walk_wild_section_handler = walk_wild_section_specs3_wild2;
+      break;
+    case 0x0402:
+      ptr->walk_wild_section_handler = walk_wild_section_specs4_wild2;
+      break;
+    default:
+      return;
+    }
+
+  /* Now fill the data array with pointers to the specs, first the
+     specs with non-wildcard names, then the specs with wildcard
+     names.  It's OK to process the specs in different order from the
+     given order, because we've already determined that no section
+     will match more than one spec.  */
+  data_counter = 0;
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    if (!wildcardp (sec->spec.name))
+      ptr->handler_data[data_counter++] = sec;
+  for (sec = ptr->section_list; sec != NULL; sec = sec->next)
+    if (wildcardp (sec->spec.name))
+      ptr->handler_data[data_counter++] = sec;
+}
+
 /* Handle a wild statement for a single file F.  */
 
 static void
@@ -1175,17 +1559,12 @@ sort_def_symbol (hash_entry, info)
 static void
 init_os (lang_output_section_statement_type *s)
 {
-  lean_section_userdata_type *new;
-
   if (s->bfd_section != NULL)
     return;
 
   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);
-  memset (new, 0, SECTION_USERDATA_SIZE);
-
   s->bfd_section = bfd_get_section_by_name (output_bfd, s->name);
   if (s->bfd_section == NULL)
     s->bfd_section = bfd_make_section (output_bfd, s->name);
@@ -1199,7 +1578,14 @@ init_os (lang_output_section_statement_t
   /* We initialize an output sections output offset to minus its own
      vma to allow us to output a section through itself.  */
   s->bfd_section->output_offset = 0;
-  get_userdata (s->bfd_section) = new;
+  if (!command_line.reduce_memory_overheads)
+    {
+      fat_section_userdata_type *new
+	= stat_alloc (sizeof (fat_section_userdata_type));
+      memset (new, 0, sizeof (fat_section_userdata_type));
+      get_userdata (s->bfd_section) = new;
+    }
+
 
   /* If there is a base address, make sure that any sections it might
      mention are initialized.  */
@@ -4939,6 +5325,7 @@ lang_add_wild (struct wildcard_spec *fil
   new->section_list = section_list;
   new->keep_sections = keep_sections;
   lang_list_init (&new->children);
+  analyze_walk_wild_section_handler (new);
 }
 
 void
--- ld/ldlang.h	3 Mar 2005 11:51:58 -0000	1.44
+++ ld/ldlang.h	29 Mar 2005 13:02:03 -0000
@@ -298,7 +298,17 @@ typedef struct
   union lang_statement_union *file;
 } lang_afile_asection_pair_statement_type;
 
-typedef struct lang_wild_statement_struct
+typedef struct lang_wild_statement_struct lang_wild_statement_type;
+
+typedef void (*callback_t) (lang_wild_statement_type *, struct wildcard_list *,
+			    asection *, lang_input_statement_type *, void *);
+
+typedef void (*walk_wild_section_handler_t) (lang_wild_statement_type *,
+					     lang_input_statement_type *,
+					     callback_t callback,
+					     void *data);
+
+struct lang_wild_statement_struct
 {
   lang_statement_header_type header;
   const char *filename;
@@ -306,7 +316,10 @@ typedef struct lang_wild_statement_struc
   struct wildcard_list *section_list;
   bfd_boolean keep_sections;
   lang_statement_list_type children;
-} lang_wild_statement_type;
+
+  walk_wild_section_handler_t walk_wild_section_handler;
+  struct wildcard_list *handler_data[4];
+};
 
 typedef struct lang_address_statement_struct
 {


	Jakub

Re: optimizations for 3x speedup in ld

[Robert O'Callahan]

On Tue, 2005-03-29 at 15:53 +0200, Jakub Jelinek wrote:
> On Fri, Feb 18, 2005 at 09:37:49AM +1300, Robert O'Callahan wrote:
> > I'm attaching the patch so people can see it/test it/comment on it,
> > keeping in mind this is copyright Novell for now.
> 
> What happened with this patch?
> Is this stuck because of code assignment (Ian's mail suggested Novell
> has blanket copyright assignment for binutils), or because of the
> requested formatting changes etc.?

I have mailed a copyright assignment form to the FSF. They should
receive it any day now. Once they receive it, in combination with
Novell's blanket disclaimer of copyright in binutils (signed by David
Wilkes and on file with the FSF) someone should be able to check the
patch in.

> The patch as is doesn't apply cleanly to current CVS binutils,
> so I took it, make it apply, fixed whatever formatting issues I found out
> and changed a few things I spotted.

Your changes look good.

Rob

Re: optimizations for 3x speedup in ld

[Nick Clifton]

Hi Jakub, Hi Robert,

> 2005-03-29  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* ldlang.c: Formatting.
> 	(walk_wild_consider_section): Remember return value from wildcardp.
> 	(is_simple_wild): Use strcspn instead of 2 strpbrk calls and strlen.
> 	(wild_spec_can_overlap): Use strcspn instead of strpbrk and strlen.
> 
> 2005-02-17  Robert O'Callahan  <rocallahan@novell.com>
> 
> 	* ld.h (lean_section_userdata_type): Remove.
> 	(fat_section_userdata_type): Remove file field.
> 	(SECTION_USERDATA_SIZE): Remove.
> 	* ldlang.c (init_os): Eliminate initialization of unused
> 	lean_section_userdata_type.
> 
> 	* ldlang.h (callback_t, walk_wild_section_handler_t): New
> 	typedefs.
> 	(struct lang_wild_statement_struct): Add walk_wild_section_handler
> 	and handler_data fields.
> 	* ldlang.c (callback_t): Removed.
> 	(walk_wild_consider_section, walk_wild_section_general,
> 	section_iterator_callback, find_section, is_simple_wild,
> 	match_simple_wild, walk_wild_section_specs1_wild0,
> 	walk_wild_section_specs1_wild1, walk_wild_section_specs2_wild1,
> 	walk_wild_section_specs3_wild2, walk_wild_section_specs4_wild2,
> 	wild_spec_can_overlap, analyze_walk_wild_section_handler): New
> 	functions.
> 	(lang_add_wild): Call analyze_walk_wild_section_handler.
> 	(walk_wild_section): Renamed to walk_wild_section_general and
> 	created a wrapper function.
> 	(section_iterator_callback_data): New typedef.

Sorry for the delay.  This patch is now approved (for the mainline), 
please apply.

Cheers
   Nick