[PATCH 1/8] section-select: Lazily resolve section matches

[PATCH 1/8] section-select: Lazily resolve section matches

[Michael Matz]

and remember the results.  Before this the order of section matching
is basically:

  foreach script-wild-stmt S
    foreach pattern P of S
      foreach inputfile I
        foreach section S of I
	  match S against P
	    if match: do action for S

And this process is done three or four times: for each top-level call to
walk_wild() or wild(), that is: check_input_sections, lang_gc_sections,
lang_find_relro_sections and of course map_input_to_output_sections.

So we iterate over all sections of all files many many times (for each
glob).  Reality is a bit more complicated (some special glob types don't
need the full iteration over all sections, only over all files), but
that's the gist of it.

For future work this shuffles the whole ordering a bit by lazily doing
the matching process and memoizing results, trading a little memory for
a 75% speedup of the overall section selection process.

This lazy resolution introduces a problem with sections added late
that's corrected in the next patch.
---
 ld/ldlang.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ld/ldlang.h | 12 ++++++++
 2 files changed, 99 insertions(+), 1 deletion(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 81a6aeb7a89..c92ebd472f4 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -1072,8 +1072,27 @@ walk_wild_file (lang_wild_statement_type *s,
     }
 }
 
+static lang_statement_union_type *
+new_statement (enum statement_enum type,
+	       size_t size,
+	       lang_statement_list_type *list);
 static void
-walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
+add_matching_callback (lang_wild_statement_type *ptr,
+		       struct wildcard_list *sec,
+		       asection *section,
+		       lang_input_statement_type *file,
+		       void *data ATTRIBUTE_UNUSED)
+{
+  lang_input_matcher_type *new_section;
+  /* Add a section reference to the list.  */
+  new_section = new_stat (lang_input_matcher, &ptr->matching_sections);
+  new_section->section = section;
+  new_section->pattern = sec;
+  new_section->input_stmt = file;
+}
+
+static void
+walk_wild_resolve (lang_wild_statement_type *s)
 {
   const char *file_spec = s->filename;
   char *p;
@@ -1083,6 +1102,66 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
       /* Perform the iteration over all files in the list.  */
       LANG_FOR_EACH_INPUT_STATEMENT (f)
 	{
+	  //printf("XXX   %s\n", f->filename);
+	  walk_wild_file (s, f, add_matching_callback, NULL);
+	}
+    }
+  else if ((p = archive_path (file_spec)) != NULL)
+    {
+      LANG_FOR_EACH_INPUT_STATEMENT (f)
+	{
+	  if (input_statement_is_archive_path (file_spec, p, f))
+	    walk_wild_file (s, f, add_matching_callback, NULL);
+	}
+    }
+  else if (wildcardp (file_spec))
+    {
+      LANG_FOR_EACH_INPUT_STATEMENT (f)
+	{
+	  if (fnmatch (file_spec, f->filename, 0) == 0)
+	    walk_wild_file (s, f, add_matching_callback, NULL);
+	}
+    }
+  else
+    {
+      lang_input_statement_type *f;
+
+      /* Perform the iteration over a single file.  */
+      f = lookup_name (file_spec);
+      if (f)
+	walk_wild_file (s, f, add_matching_callback, NULL);
+    }
+}
+
+static void
+walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
+{
+  const char *file_spec = s->filename;
+  //char *p;
+
+  if (!s->resolved)
+    {
+      //printf("XXX %s\n", file_spec ? file_spec : "<null>");
+      walk_wild_resolve (s);
+      s->resolved = true;
+    }
+
+    {
+      lang_statement_union_type *l;
+      for (l = s->matching_sections.head; l; l = l->header.next)
+	{
+	  (*callback) (s, l->input_matcher.pattern, l->input_matcher.section, l->input_matcher.input_stmt, data);
+	}
+      return;
+    }
+
+#if 0
+  if (file_spec == NULL)
+    {
+      /* Perform the iteration over all files in the list.  */
+      LANG_FOR_EACH_INPUT_STATEMENT (f)
+	{
+	  printf("XXX   %s\n", f->filename);
 	  walk_wild_file (s, f, callback, data);
 	}
     }
@@ -1111,6 +1190,7 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
       if (f)
 	walk_wild_file (s, f, callback, data);
     }
+#endif
 }
 
 /* lang_for_each_statement walks the parse tree and calls the provided
@@ -1982,6 +2062,8 @@ insert_os_after (lang_output_section_statement_type *after)
 	case lang_group_statement_enum:
 	case lang_insert_statement_enum:
 	  continue;
+	case lang_input_matcher_enum:
+	  FAIL ();
 	}
       break;
     }
@@ -4347,6 +4429,8 @@ map_input_to_output_sections
 	  break;
 	case lang_insert_statement_enum:
 	  break;
+	case lang_input_matcher_enum:
+	  FAIL ();
 	}
     }
 }
@@ -8343,6 +8427,8 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt->section_list = section_list;
   new_stmt->keep_sections = keep_sections;
   lang_list_init (&new_stmt->children);
+  new_stmt->resolved = false;
+  lang_list_init (&new_stmt->matching_sections);
   analyze_walk_wild_section_handler (new_stmt);
 }
 
diff --git a/ld/ldlang.h b/ld/ldlang.h
index 713c5282b55..50ad64ce057 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -76,6 +76,7 @@ enum statement_enum
   lang_fill_statement_enum,
   lang_group_statement_enum,
   lang_input_section_enum,
+  lang_input_matcher_enum,
   lang_input_statement_enum,
   lang_insert_statement_enum,
   lang_output_section_statement_enum,
@@ -335,6 +336,14 @@ typedef struct
   void *pattern;
 } lang_input_section_type;
 
+typedef struct
+{
+  lang_statement_header_type header;
+  asection *section;
+  void *pattern;
+  lang_input_statement_type *input_stmt;
+} lang_input_matcher_type;
+
 struct map_symbol_def {
   struct bfd_link_hash_entry *entry;
   struct map_symbol_def *next;
@@ -389,6 +398,8 @@ struct lang_wild_statement_struct
   bool keep_sections;
   lang_statement_list_type children;
   struct name_list *exclude_name_list;
+  lang_statement_list_type matching_sections;
+  bool resolved;
 
   walk_wild_section_handler_t walk_wild_section_handler;
   struct wildcard_list *handler_data[4];
@@ -440,6 +451,7 @@ typedef union lang_statement_union
   lang_fill_statement_type fill_statement;
   lang_group_statement_type group_statement;
   lang_input_section_type input_section;
+  lang_input_matcher_type input_matcher;
   lang_input_statement_type input_statement;
   lang_insert_statement_type insert_statement;
   lang_output_section_statement_type output_section_statement;
-- 
2.36.1

[PATCH 2/8] section-select: Deal with sections added late

[Michael Matz]

at least the check_relocs callback can add input sections (for
creating an dynamic output relocation section).  For those
we need to go through the walk_wild handlers again.  For quick
detection of such new sections we export a new bfd function:
bfd_get_max_section_id and remember that one when resolving a wild
statement.  Any section whose ->id member is higher than that is new.
---

I keep this patch separate (not quashed into the one before) because it 
adds an interface to libbfd, which might be superseded depending on an 
answer to patch 4/8.  And keeping it )and the reversion in 7/8) separate 
makes it easier to throw it out or include it.

 bfd/bfd-in2.h |  2 ++
 bfd/section.c | 19 +++++++++++++++++++
 ld/ldlang.c   | 12 +++++++++++-
 ld/ldlang.h   |  1 +
 4 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h
index 0b071dda1e5..5350ae42b03 100644
--- a/bfd/bfd-in2.h
+++ b/bfd/bfd-in2.h
@@ -1330,6 +1330,8 @@ discarded_section (const asection *sec)
   { 0, NAME, 0, BSF_SECTION_SYM, SECTION }
 #endif
 
+unsigned int bfd_get_max_section_id (void);
+
 void bfd_section_list_clear (bfd *);
 
 asection *bfd_get_section_by_name (bfd *abfd, const char *name);
diff --git a/bfd/section.c b/bfd/section.c
index f73e0345e15..d691bf265ab 100644
--- a/bfd/section.c
+++ b/bfd/section.c
@@ -849,6 +849,25 @@ SUBSECTION
 These are the functions exported by the section handling part of BFD.
 */
 
+/*
+FUNCTION
+	bfd_get_max_section_id
+
+SYNOPSIS
+	unsigned int bfd_get_max_section_id (void);
+
+DESCRIPTION
+	Returns an internal number representing the maximum value of
+	any SECTION->id member.  Whenever a new section is created that
+	value increases.  It never decreases.
+*/
+
+unsigned int
+bfd_get_max_section_id (void)
+{
+  return _bfd_section_id;
+}
+
 /*
 FUNCTION
 	bfd_section_list_clear
diff --git a/ld/ldlang.c b/ld/ldlang.c
index c92ebd472f4..1e4f3a5ee05 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -374,6 +374,8 @@ walk_wild_consider_section (lang_wild_statement_type *ptr,
 			    callback_t callback,
 			    void *data)
 {
+  if (s->id < ptr->max_section_id)
+    return;
   /* Don't process sections from files which were excluded.  */
   if (walk_wild_file_in_exclude_list (sec->spec.exclude_name_list, file))
     return;
@@ -395,6 +397,9 @@ walk_wild_section_general (lang_wild_statement_type *ptr,
 
   for (s = file->the_bfd->sections; s != NULL; s = s->next)
     {
+      if (s->id < ptr->max_section_id)
+	continue;
+      //printf ("YYY checking %s:%s\n", s->owner->filename, s->name);
       sec = ptr->section_list;
       if (sec == NULL)
 	(*callback) (ptr, sec, s, file, data);
@@ -1139,11 +1144,14 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
   const char *file_spec = s->filename;
   //char *p;
 
-  if (!s->resolved)
+#if 1
+  //if (!s->resolved)
+  if (s->max_section_id < bfd_get_max_section_id ())
     {
       //printf("XXX %s\n", file_spec ? file_spec : "<null>");
       walk_wild_resolve (s);
       s->resolved = true;
+      s->max_section_id = bfd_get_max_section_id ();
     }
 
     {
@@ -1154,6 +1162,7 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
 	}
       return;
     }
+#endif
 
 #if 0
   if (file_spec == NULL)
@@ -8428,6 +8437,7 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt->keep_sections = keep_sections;
   lang_list_init (&new_stmt->children);
   new_stmt->resolved = false;
+  new_stmt->max_section_id = 0;
   lang_list_init (&new_stmt->matching_sections);
   analyze_walk_wild_section_handler (new_stmt);
 }
diff --git a/ld/ldlang.h b/ld/ldlang.h
index 50ad64ce057..8566e022a57 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -400,6 +400,7 @@ struct lang_wild_statement_struct
   struct name_list *exclude_name_list;
   lang_statement_list_type matching_sections;
   bool resolved;
+  unsigned int max_section_id;
 
   walk_wild_section_handler_t walk_wild_section_handler;
   struct wildcard_list *handler_data[4];
-- 
2.36.1

[PATCH 3/8] section-select: Implement a prefix-tree

[Michael Matz]

Now that we have a list of potentially matching sections per wild
statement we can actually pre-fill that one by going once over all input
sections and match their names against a prefix-tree that points to the
potentially matching wild statements.

So instead of looking at all sections names for each glob for each wild
statement we now look at the sections only once and then only check
against those globs that have a possibility of a match at all (usually
only one or two).

This pushes the whole section selection off the profiles.
---
 ld/ldlang.c | 362 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 353 insertions(+), 9 deletions(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 1e4f3a5ee05..06fa541df3a 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -59,6 +59,7 @@
 /* Local variables.  */
 static struct obstack stat_obstack;
 static struct obstack map_obstack;
+static struct obstack pt_obstack;
 
 #define obstack_chunk_alloc xmalloc
 #define obstack_chunk_free free
@@ -210,6 +211,9 @@ name_match (const char *pattern, const char *name)
   return strcmp (pattern, name);
 }
 
+/* Given an analyzed wildcard_spec SPEC, match it against NAME,
+   returns zero on a match, non-zero if there's no match.  */
+
 static int
 spec_match (const struct wildcard_spec *spec, const char *name)
 {
@@ -383,6 +387,63 @@ walk_wild_consider_section (lang_wild_statement_type *ptr,
   (*callback) (ptr, sec, s, file, data);
 }
 
+static void
+walk_wild_section_match (lang_wild_statement_type *ptr,
+			 lang_input_statement_type *file,
+			 asection *s,
+			 callback_t callback,
+			 void *data)
+{
+  struct wildcard_list *sec;
+  const char *file_spec = ptr->filename;
+  char *p;
+
+  /* Check if filenames match.  */
+  if (file_spec == NULL)
+    ;
+  else if ((p = archive_path (file_spec)) != NULL)
+    {
+      if (!input_statement_is_archive_path (file_spec, p, file))
+	return;
+    }
+  else if (wildcardp (file_spec))
+    {
+      if (fnmatch (file_spec, file->filename, 0) != 0)
+	return;
+    }
+  else
+    {
+      lang_input_statement_type *f;
+      /* Perform the iteration over a single file.  */
+      f = lookup_name (file_spec);
+      if (f != file)
+	return;
+    }
+
+  /* Check section name against each wildcard spec.  If there's no
+     wildcard all sections match.  */
+  sec = ptr->section_list;
+  if (sec == NULL)
+    (*callback) (ptr, sec, s, file, data);
+
+  while (sec != NULL)
+    {
+      bool skip = false;
+
+      if (sec->spec.name != NULL)
+	{
+	  const char *sname = bfd_section_name (s);
+
+	  skip = spec_match (&sec->spec, sname) != 0;
+	}
+
+      if (!skip)
+	walk_wild_consider_section (ptr, file, s, sec, callback, data);
+
+      sec = sec->next;
+    }
+}
+
 /* Lowest common denominator routine that can handle everything correctly,
    but slowly.  */
 
@@ -922,6 +983,159 @@ wild_spec_can_overlap (const char *name1, const char *name2)
   return memcmp (name1, name2, min_prefix_len) == 0;
 }
 
+\f
+/* Sections are matched against wildcard statements via a prefix tree.
+   The prefix tree holds prefixes of all matching patterns (up to the first
+   wildcard character), and the wild statement from which those patterns
+   came.  When matching a section name against the tree we're walking through
+   the tree character by character.  Each statement we hit is one that
+   potentially matches.  This is checked by actually going through the
+   (glob) matching routines.
+
+   When the section name turns out to actually match we record that section
+   in the wild statements list of matching sections.  */
+
+/* A prefix can be matched by multiple statement, so we need a list of them.  */
+struct wild_stmt_list
+{
+  lang_wild_statement_type *stmt;
+  struct wild_stmt_list *next;
+};
+
+/* The prefix tree itself.  */
+struct prefixtree
+{
+  /* The list of all children (linked via .next).  */
+  struct prefixtree *child;
+  struct prefixtree *next;
+  /* This tree node is responsible for the prefix of parent plus 'c'.  */
+  char c;
+  /* The statements that potentially can match this prefix.  */
+  struct wild_stmt_list *stmt;
+};
+
+/* We always have a root node in the prefix tree.  It corresponds to the
+   empty prefix.  E.g. a glob like "*" would sit in this root.  */
+static struct prefixtree the_root, *ptroot = &the_root;
+
+/* Given a prefix tree in *TREE, corresponding to prefix P, find or
+   INSERT the tree node corresponding to prefix P+C.  */
+
+static struct prefixtree *
+get_prefix_tree (struct prefixtree **tree, char c, bool insert)
+{
+  struct prefixtree *t;
+  for (t = *tree; t; t = t->next)
+    if (t->c == c)
+      return t;
+  if (!insert)
+    return NULL;
+  t = (struct prefixtree *) obstack_alloc (&pt_obstack, sizeof *t);
+  t->child = NULL;
+  t->next = *tree;
+  t->c = c;
+  t->stmt = NULL;
+  *tree = t;
+  return t;
+}
+
+/* Add STMT to the set of statements that can be matched by the prefix
+   corresponding to prefix tree T.  */
+
+static void
+pt_add_stmt (struct prefixtree *t, lang_wild_statement_type *stmt)
+{
+  struct wild_stmt_list *sl, **psl;
+  sl = (struct wild_stmt_list *) obstack_alloc (&pt_obstack, sizeof *sl);
+  sl->stmt = stmt;
+  sl->next = NULL;
+  psl = &t->stmt;
+  while (*psl)
+    psl = &(*psl)->next;
+  *psl = sl;
+}
+
+/* Insert STMT into the global prefix tree.  */
+
+static void
+insert_prefix_tree (lang_wild_statement_type *stmt)
+{
+  struct wildcard_list *sec;
+  struct prefixtree **pt = &ptroot, *t;
+  struct wild_stmt_list *sl, **psl;
+
+  if (!stmt->section_list)
+    {
+      /* If we have no section_list (no wildcards in the wild STMT),
+         then every section name will match, so add this to the root.  */
+      pt_add_stmt (ptroot, stmt);
+      return;
+    }
+
+  for (sec = stmt->section_list; sec; sec = sec->next)
+    {
+      const char *name = sec->spec.name ? sec->spec.name : "";
+      char c;
+      pt = &ptroot;
+      t = ptroot;
+      for (; (c = *name); name++)
+	{
+	  if (c == '*' || c == '[' || c == '?')
+	    break;
+	  t = get_prefix_tree (&t->child, c, true);
+	}
+      /* If we hit a glob character, the matching prefix is what we saw
+         until now.  If we hit the end of pattern (hence it's no glob) then
+	 we can do better: we only need to record a match when a section name
+	 completely matches, not merely a prefix, so record the trailing 0
+	 as well.  */
+      if (!c)
+	t = get_prefix_tree (&t->child, 0, true);
+      else if (!t)
+	abort();
+      sl = (struct wild_stmt_list *) xmalloc (sizeof *sl);
+      sl->stmt = stmt;
+      sl->next = NULL;
+      psl = &t->stmt;
+      while (*psl)
+	psl = &(*psl)->next;
+      *psl = sl;
+    }
+}
+
+/* Dump T indented by INDENT spaces.  */
+
+static void
+debug_prefix_tree_rec (struct prefixtree *t, int indent)
+{
+  for (; t; t = t->next)
+    {
+      struct wild_stmt_list *sl;
+      printf ("%*s %c", indent, "", t->c);
+      for (sl = t->stmt; sl; sl = sl->next)
+	{
+	  struct wildcard_list *curr;
+	  printf (" %p ", sl->stmt);
+	  for (curr = sl->stmt->section_list; curr; curr = curr->next)
+	    printf ("%s ", curr->spec.name ? curr->spec.name : "*");
+	}
+      printf ("\n");
+      debug_prefix_tree_rec (t->child, indent + 2);
+    }
+}
+
+/* Dump the global prefix tree.  */
+
+static void
+debug_prefix_tree (void)
+{
+  debug_prefix_tree_rec (ptroot, 2);
+}
+
+/* Like strcspn() but start to look from the end to beginning of
+   S.  Returns the length of the suffix of S consisting entirely
+   of characters not in REJECT.  */
+
 static size_t
 rstrcspn (const char *s, const char *reject)
 {
@@ -936,8 +1150,8 @@ rstrcspn (const char *s, const char *reject)
   return sufflen;
 }
 
-/* Select specialized code to handle various kinds of wildcard
-   statements.  */
+/* Analyze the wildcards in wild statement PTR to setup various
+   things for quick matching.  */
 
 static void
 analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
@@ -969,6 +1183,8 @@ analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
 	sec->spec.namelen = sec->spec.prefixlen = sec->spec.suffixlen = 0;
     }
 
+  insert_prefix_tree (ptr);
+
   /* 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?
@@ -1077,6 +1293,9 @@ walk_wild_file (lang_wild_statement_type *s,
     }
 }
 
+static bool check_resolve = false;
+static unsigned int old_max_section_id = 0;
+
 static lang_statement_union_type *
 new_statement (enum statement_enum type,
 	       size_t size,
@@ -1088,12 +1307,119 @@ add_matching_callback (lang_wild_statement_type *ptr,
 		       lang_input_statement_type *file,
 		       void *data ATTRIBUTE_UNUSED)
 {
-  lang_input_matcher_type *new_section;
-  /* Add a section reference to the list.  */
-  new_section = new_stat (lang_input_matcher, &ptr->matching_sections);
-  new_section->section = section;
-  new_section->pattern = sec;
-  new_section->input_stmt = file;
+  if (check_resolve)
+    {
+      if (0)
+	{
+	  lang_statement_union_type *l;
+	  for (l = ptr->matching_sections.head; l; l = l->header.next)
+	    {
+	      if (section == l->input_matcher.section
+		  && sec == l->input_matcher.pattern
+		  && file == l->input_matcher.input_stmt)
+		break;
+	    }
+	  if (!l)
+	    abort();
+	}
+    }
+  else
+    {
+      lang_input_matcher_type *new_section;
+      /* Add a section reference to the list.  */
+      new_section = new_stat (lang_input_matcher, &ptr->matching_sections);
+      new_section->section = section;
+      new_section->pattern = sec;
+      new_section->input_stmt = file;
+    }
+}
+
+/* Match all sections from FILE against the global prefix tree,
+   and record them into each wild statement that has a match.  */
+
+static void
+resolve_wild_sections (lang_input_statement_type *file)
+{
+  asection *s;
+
+  if (file->flags.just_syms)
+    return;
+
+  for (s = file->the_bfd->sections; s != NULL; s = s->next)
+    {
+      const char *sname = bfd_section_name (s);
+      char c;
+      struct prefixtree **pt = &ptroot, *t = *pt;
+      if (old_max_section_id && s->id < old_max_section_id)
+	continue;
+      //printf (" YYY consider %s of %s\n", sname, file->the_bfd->filename);
+      do
+	{
+	  if (!t)
+	    break;
+	  if (t->stmt)
+	    {
+	      struct wild_stmt_list *sl;
+	      for (sl = t->stmt; sl; sl = sl->next)
+		{
+		  walk_wild_section_match (sl->stmt, file, s, add_matching_callback, NULL);
+		  //printf ("   ZZZ maybe place into %p\n", sl->stmt);
+		}
+	    }
+	  c = *sname++;
+	  t = get_prefix_tree (&t->child, c, false);
+	}
+      while (c && t);
+      if (t && t->stmt)
+	{
+	  struct wild_stmt_list *sl;
+	  for (sl = t->stmt; sl; sl = sl->next)
+	    {
+	      walk_wild_section_match (sl->stmt, file, s, add_matching_callback, NULL);
+	      //printf ("   ZZZ maybe place into %p\n", sl->stmt);
+	    }
+	}
+    }
+}
+
+/* Match all sections from all input files against the global prefix tree.  */
+
+static void
+resolve_wilds (void)
+{
+  check_resolve = false;
+  LANG_FOR_EACH_INPUT_STATEMENT (f)
+    {
+      //printf("XXX   %s\n", f->filename);
+      /* XXX if (walk_wild_file_in_exclude_list (s->exclude_name_list, f))
+	return;*/
+
+      if (f->the_bfd == NULL
+	  || !bfd_check_format (f->the_bfd, bfd_archive))
+	resolve_wild_sections (f);
+      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)
+	    {
+	      /* When lookup_name is called, it will call the add_symbols
+		 entry point for the archive.  For each element of the
+		 archive which is included, BFD will call ldlang_add_file,
+		 which will set the usrdata field of the member to the
+		 lang_input_statement.  */
+	      if (bfd_usrdata (member) != NULL)
+		resolve_wild_sections (bfd_usrdata (member));
+
+	      member = bfd_openr_next_archived_file (f->the_bfd, member);
+	    }
+	}
+    }
+  old_max_section_id = bfd_get_max_section_id ();
+  check_resolve = true;
 }
 
 static void
@@ -1138,6 +1464,9 @@ walk_wild_resolve (lang_wild_statement_type *s)
     }
 }
 
+/* For each input section that matches wild statement S calls
+   CALLBACK with DATA.  */
+
 static void
 walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
 {
@@ -1149,7 +1478,7 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
   if (s->max_section_id < bfd_get_max_section_id ())
     {
       //printf("XXX %s\n", file_spec ? file_spec : "<null>");
-      walk_wild_resolve (s);
+      //walk_wild_resolve (s);
       s->resolved = true;
       s->max_section_id = bfd_get_max_section_id ();
     }
@@ -1505,6 +1834,7 @@ void
 lang_init (void)
 {
   obstack_begin (&stat_obstack, 1000);
+  obstack_init (&pt_obstack);
 
   stat_ptr = &statement_list;
 
@@ -8273,6 +8603,11 @@ lang_process (void)
   /* Size up the common data.  */
   lang_common ();
 
+  if (0)
+    debug_prefix_tree ();
+
+  resolve_wilds ();
+
   /* Remove unreferenced sections if asked to.  */
   lang_gc_sections ();
 
@@ -8283,6 +8618,8 @@ lang_process (void)
 
   ldemul_after_check_relocs ();
 
+  resolve_wilds ();
+
   /* Update wild statements in case the user gave --sort-section.
      Note how the option might have come after the linker script and
      so couldn't have been set when the wild statements were created.  */
@@ -8440,6 +8777,13 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt->max_section_id = 0;
   lang_list_init (&new_stmt->matching_sections);
   analyze_walk_wild_section_handler (new_stmt);
+  if (0)
+    {
+      printf ("wild %s(", new_stmt->filename ? new_stmt->filename : "*");
+      for (curr = new_stmt->section_list; curr; curr = curr->next)
+	printf ("%s ", curr->spec.name ? curr->spec.name : "*");
+      printf (")\n");
+    }
 }
 
 void
-- 
2.36.1

[PATCH 4/8] section-select: Completely rebuild matches

[Michael Matz]

this resets all section matches before updating for newly created
sections (i.e. completely rebuilds the matches).  This fixes powerpc
"TOC opt" tests that shows a difference in section order: originally
.got of "linker stubs" comes before .toc (both placed into the same
.got output section due to ".got {*(.got .toc)}".  But .got of linker
stubs is created later, and in the second run of resolve_wilds is
appended to the list, hence is then coming after .toc (which was added
already in the earlier resolve_wilds run).  So order swapped ->
test fails.

The result would still work, and it's unclear if the documented
meaning of multiple section selectors applies to lazily generated
sections like here as well.  For now lets reinstate old behaviour and
simply always completely rebuild the matching sections.

(Note: the reset lists aren't freed or reused)
---

Alan: can you please take a look at the problem mentioned above?  Without 
this patch the "TOC opt" tests fails on powerpc because two sections are 
swapped.  But it's not quite clear if lazily added sections (.got of 
"linker stubs") are also bound to the documented behaviour of multiple 
globs in a single wild statement.

The result with the changed section order would continue to work, and if 
we could decide that that's okay the section resolution wouldn't have to 
rebuild stuff from scratch, roughly halving the time for it.

In that case I wouldn't patch 7/8 to remove the libbfd interface to get 
the max section id and instead use it for early outs.  Sections that are 
generated late and lazy would then always be appended to their matching 
wild statement.


Ciao,
Michael.

 ld/ldlang.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 06fa541df3a..57432700a18 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -8400,6 +8400,26 @@ lang_propagate_lma_regions (void)
     }
 }
 
+static void
+reset_one_wild (lang_statement_union_type *statement)
+{
+  if (statement->header.type == lang_wild_statement_enum)
+    {
+      lang_wild_statement_type *stmt = &statement->wild_statement;
+      stmt->resolved = false;
+      stmt->max_section_id = 0;
+      /* XXX Leaks? */
+      lang_list_init (&stmt->matching_sections);
+    }
+}
+
+static void
+reset_resolved_wilds (void)
+{
+  lang_for_each_statement (reset_one_wild);
+  old_max_section_id = 0;
+}
+
 void
 lang_process (void)
 {
@@ -8618,6 +8638,7 @@ lang_process (void)
 
   ldemul_after_check_relocs ();
 
+  reset_resolved_wilds ();
   resolve_wilds ();
 
   /* Update wild statements in case the user gave --sort-section.
-- 
2.36.1

[PATCH 5/8] section-select: Remove unused code

[Michael Matz]

walk_wild_file, hence walk_wild_section and walk_wild_section_handler
aren't called with the prefix tree.  Hence initialization of the latter
and all potential special cases for it aren't used anymore.  That also
removes the need to handler_data[] and some associated helper functions.
So, remove all of that.
---
 ld/ldlang.c | 506 +---------------------------------------------------
 ld/ldlang.h |   2 -
 2 files changed, 5 insertions(+), 503 deletions(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 57432700a18..3748bf9bec9 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -444,83 +444,6 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
     }
 }
 
-/* Lowest common denominator routine that can handle everything correctly,
-   but slowly.  */
-
-static void
-walk_wild_section_general (lang_wild_statement_type *ptr,
-			   lang_input_statement_type *file,
-			   callback_t callback,
-			   void *data)
-{
-  asection *s;
-  struct wildcard_list *sec;
-
-  for (s = file->the_bfd->sections; s != NULL; s = s->next)
-    {
-      if (s->id < ptr->max_section_id)
-	continue;
-      //printf ("YYY checking %s:%s\n", s->owner->filename, s->name);
-      sec = ptr->section_list;
-      if (sec == NULL)
-	(*callback) (ptr, sec, s, file, data);
-
-      while (sec != NULL)
-	{
-	  bool skip = false;
-
-	  if (sec->spec.name != NULL)
-	    {
-	      const char *sname = bfd_section_name (s);
-
-	      skip = spec_match (&sec->spec, sname) != 0;
-	    }
-
-	  if (!skip)
-	    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;
-  bool multiple_sections_found;
-} section_iterator_callback_data;
-
-static bool
-section_iterator_callback (bfd *abfd ATTRIBUTE_UNUSED, asection *s, void *data)
-{
-  section_iterator_callback_data *d = (section_iterator_callback_data *) 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,
-	      bool *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;
-}
-
 /* Return the numerical value of the init_priority attribute from
    section name NAME.  */
 
@@ -768,221 +691,6 @@ output_section_callback_tree_to_list (lang_wild_statement_type *ptr,
   free (tree);
 }
 
-/* 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.  */
-  bool 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_section_name (s);
-      bool skip = !match_simple_wild (wildsec0->spec.name, sname);
-      //bool skip = !!spec_match (&wildsec0->spec, 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];
-  bool 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_section_name (s);
-	  bool skip = !match_simple_wild (wildsec1->spec.name, sname);
-	  //bool skip = !!spec_match (&wildsec1->spec, 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];
-  bool 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_section_name (s);
-	  bool 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];
-  bool 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_section_name (s);
-	    bool 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->flags.just_syms)
-    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 bool
-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;
-}
-
 \f
 /* Sections are matched against wildcard statements via a prefix tree.
    The prefix tree holds prefixes of all matching patterns (up to the first
@@ -1156,17 +864,8 @@ rstrcspn (const char *s, const char *reject)
 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;
-  ptr->handler_data[0] = NULL;
-  ptr->handler_data[1] = NULL;
-  ptr->handler_data[2] = NULL;
-  ptr->handler_data[3] = NULL;
+
   ptr->tree = NULL;
   ptr->rightmost = &ptr->tree;
 
@@ -1184,113 +883,6 @@ analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
     }
 
   insert_prefix_tree (ptr);
-
-  /* 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
-walk_wild_file (lang_wild_statement_type *s,
-		lang_input_statement_type *f,
-		callback_t callback,
-		void *data)
-{
-  if (walk_wild_file_in_exclude_list (s->exclude_name_list, f))
-    return;
-
-  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)
-	{
-	  /* When lookup_name is called, it will call the add_symbols
-	     entry point for the archive.  For each element of the
-	     archive which is included, BFD will call ldlang_add_file,
-	     which will set the usrdata field of the member to the
-	     lang_input_statement.  */
-	  if (bfd_usrdata (member) != NULL)
-	    walk_wild_section (s, bfd_usrdata (member), callback, data);
-
-	  member = bfd_openr_next_archived_file (f->the_bfd, member);
-	}
-    }
 }
 
 static bool check_resolve = false;
@@ -1422,113 +1014,25 @@ resolve_wilds (void)
   check_resolve = true;
 }
 
-static void
-walk_wild_resolve (lang_wild_statement_type *s)
-{
-  const char *file_spec = s->filename;
-  char *p;
-
-  if (file_spec == NULL)
-    {
-      /* Perform the iteration over all files in the list.  */
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  //printf("XXX   %s\n", f->filename);
-	  walk_wild_file (s, f, add_matching_callback, NULL);
-	}
-    }
-  else if ((p = archive_path (file_spec)) != NULL)
-    {
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  if (input_statement_is_archive_path (file_spec, p, f))
-	    walk_wild_file (s, f, add_matching_callback, NULL);
-	}
-    }
-  else if (wildcardp (file_spec))
-    {
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  if (fnmatch (file_spec, f->filename, 0) == 0)
-	    walk_wild_file (s, f, add_matching_callback, NULL);
-	}
-    }
-  else
-    {
-      lang_input_statement_type *f;
-
-      /* Perform the iteration over a single file.  */
-      f = lookup_name (file_spec);
-      if (f)
-	walk_wild_file (s, f, add_matching_callback, NULL);
-    }
-}
-
 /* For each input section that matches wild statement S calls
    CALLBACK with DATA.  */
 
 static void
 walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
 {
-  const char *file_spec = s->filename;
-  //char *p;
+  lang_statement_union_type *l;
 
-#if 1
-  //if (!s->resolved)
   if (s->max_section_id < bfd_get_max_section_id ())
     {
-      //printf("XXX %s\n", file_spec ? file_spec : "<null>");
-      //walk_wild_resolve (s);
+      //printf("XXX %s\n", s->filename ? s->filename : "<null>");
       s->resolved = true;
       s->max_section_id = bfd_get_max_section_id ();
     }
 
+  for (l = s->matching_sections.head; l; l = l->header.next)
     {
-      lang_statement_union_type *l;
-      for (l = s->matching_sections.head; l; l = l->header.next)
-	{
-	  (*callback) (s, l->input_matcher.pattern, l->input_matcher.section, l->input_matcher.input_stmt, data);
-	}
-      return;
-    }
-#endif
-
-#if 0
-  if (file_spec == NULL)
-    {
-      /* Perform the iteration over all files in the list.  */
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  printf("XXX   %s\n", f->filename);
-	  walk_wild_file (s, f, callback, data);
-	}
-    }
-  else if ((p = archive_path (file_spec)) != NULL)
-    {
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  if (input_statement_is_archive_path (file_spec, p, f))
-	    walk_wild_file (s, f, callback, data);
-	}
-    }
-  else if (wildcardp (file_spec))
-    {
-      LANG_FOR_EACH_INPUT_STATEMENT (f)
-	{
-	  if (fnmatch (file_spec, f->filename, 0) == 0)
-	    walk_wild_file (s, f, callback, data);
-	}
+      (*callback) (s, l->input_matcher.pattern, l->input_matcher.section, l->input_matcher.input_stmt, data);
     }
-  else
-    {
-      lang_input_statement_type *f;
-
-      /* Perform the iteration over a single file.  */
-      f = lookup_name (file_spec);
-      if (f)
-	walk_wild_file (s, f, callback, data);
-    }
-#endif
 }
 
 /* lang_for_each_statement walks the parse tree and calls the provided
diff --git a/ld/ldlang.h b/ld/ldlang.h
index 8566e022a57..09c43611a22 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -402,8 +402,6 @@ struct lang_wild_statement_struct
   bool resolved;
   unsigned int max_section_id;
 
-  walk_wild_section_handler_t walk_wild_section_handler;
-  struct wildcard_list *handler_data[4];
   lang_section_bst_type *tree, **rightmost;
   struct flag_info *section_flag_list;
 };
-- 
2.36.1

[PATCH 6/8] section-select: Cleanup

[Michael Matz]

more cleanups, removing useless callbacks, inlining some things,
removing check_resolved and stmt->resolved.
---
 ld/ldlang.c | 157 ++++++++++++++++------------------------------------
 ld/ldlang.h |   1 -
 2 files changed, 49 insertions(+), 109 deletions(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 3748bf9bec9..18d10531d51 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -81,6 +81,9 @@ static void exp_init_os (etree_type *);
 static lang_input_statement_type *lookup_name (const char *);
 static void insert_undefined (const char *);
 static bool sort_def_symbol (struct bfd_link_hash_entry *, void *);
+static lang_statement_union_type *new_statement (enum statement_enum type,
+						size_t size,
+						lang_statement_list_type *list);
 static void print_statement (lang_statement_union_type *,
 			     lang_output_section_statement_type *);
 static void print_statement_list (lang_statement_union_type *,
@@ -365,39 +368,43 @@ walk_wild_file_in_exclude_list (struct name_list *exclude_list,
   return false;
 }
 
-/* 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 unsigned int old_max_section_id = 0;
+
+/* Add SECTION (from input FILE) to the list of matching sections
+   within PTR (the matching wildcard is SEC).  */
 
 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)
+add_matching_section (lang_wild_statement_type *ptr,
+		      struct wildcard_list *sec,
+		      asection *section,
+		      lang_input_statement_type *file)
 {
-  if (s->id < ptr->max_section_id)
-    return;
-  /* Don't process sections from files which were excluded.  */
-  if (walk_wild_file_in_exclude_list (sec->spec.exclude_name_list, file))
-    return;
-
-  (*callback) (ptr, sec, s, file, data);
+  lang_input_matcher_type *new_section;
+  /* Add a section reference to the list.  */
+  new_section = new_stat (lang_input_matcher, &ptr->matching_sections);
+  new_section->section = section;
+  new_section->pattern = sec;
+  new_section->input_stmt = file;
 }
 
+/* Process section S (from input file FILE) in relation to wildcard
+   statement PTR.  We already know that a prefix of the name of S matches
+   some wildcard in PTR's wildcard list.  Here we check if the filename
+   matches as well (if it's specified) and if any of the wildcards in fact
+   does match.  */
+
 static void
 walk_wild_section_match (lang_wild_statement_type *ptr,
 			 lang_input_statement_type *file,
-			 asection *s,
-			 callback_t callback,
-			 void *data)
+			 asection *s)
 {
   struct wildcard_list *sec;
   const char *file_spec = ptr->filename;
   char *p;
 
+  if (s->id < ptr->max_section_id)
+    return;
+
   /* Check if filenames match.  */
   if (file_spec == NULL)
     ;
@@ -424,23 +431,21 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
      wildcard all sections match.  */
   sec = ptr->section_list;
   if (sec == NULL)
-    (*callback) (ptr, sec, s, file, data);
-
-  while (sec != NULL)
+    add_matching_section (ptr, sec, s, file);
+  else
     {
-      bool skip = false;
-
-      if (sec->spec.name != NULL)
+      const char *sname = bfd_section_name (s);
+      for (; sec != NULL; sec = sec->next)
 	{
-	  const char *sname = bfd_section_name (s);
+	  if (sec->spec.name != NULL
+	      && spec_match (&sec->spec, sname) != 0)
+	    continue;
 
-	  skip = spec_match (&sec->spec, sname) != 0;
+	  /* Don't process sections from files which were excluded.  */
+	  if (!walk_wild_file_in_exclude_list (sec->spec.exclude_name_list,
+					       file))
+	    add_matching_section (ptr, sec, s, file);
 	}
-
-      if (!skip)
-	walk_wild_consider_section (ptr, file, s, sec, callback, data);
-
-      sec = sec->next;
     }
 }
 
@@ -769,8 +774,7 @@ static void
 insert_prefix_tree (lang_wild_statement_type *stmt)
 {
   struct wildcard_list *sec;
-  struct prefixtree **pt = &ptroot, *t;
-  struct wild_stmt_list *sl, **psl;
+  struct prefixtree *t;
 
   if (!stmt->section_list)
     {
@@ -782,9 +786,8 @@ insert_prefix_tree (lang_wild_statement_type *stmt)
 
   for (sec = stmt->section_list; sec; sec = sec->next)
     {
-      const char *name = sec->spec.name ? sec->spec.name : "";
+      const char *name = sec->spec.name ? sec->spec.name : "*";
       char c;
-      pt = &ptroot;
       t = ptroot;
       for (; (c = *name); name++)
 	{
@@ -799,15 +802,7 @@ insert_prefix_tree (lang_wild_statement_type *stmt)
 	 as well.  */
       if (!c)
 	t = get_prefix_tree (&t->child, 0, true);
-      else if (!t)
-	abort();
-      sl = (struct wild_stmt_list *) xmalloc (sizeof *sl);
-      sl->stmt = stmt;
-      sl->next = NULL;
-      psl = &t->stmt;
-      while (*psl)
-	psl = &(*psl)->next;
-      *psl = sl;
+      pt_add_stmt (t, stmt);
     }
 }
 
@@ -885,47 +880,6 @@ analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
   insert_prefix_tree (ptr);
 }
 
-static bool check_resolve = false;
-static unsigned int old_max_section_id = 0;
-
-static lang_statement_union_type *
-new_statement (enum statement_enum type,
-	       size_t size,
-	       lang_statement_list_type *list);
-static void
-add_matching_callback (lang_wild_statement_type *ptr,
-		       struct wildcard_list *sec,
-		       asection *section,
-		       lang_input_statement_type *file,
-		       void *data ATTRIBUTE_UNUSED)
-{
-  if (check_resolve)
-    {
-      if (0)
-	{
-	  lang_statement_union_type *l;
-	  for (l = ptr->matching_sections.head; l; l = l->header.next)
-	    {
-	      if (section == l->input_matcher.section
-		  && sec == l->input_matcher.pattern
-		  && file == l->input_matcher.input_stmt)
-		break;
-	    }
-	  if (!l)
-	    abort();
-	}
-    }
-  else
-    {
-      lang_input_matcher_type *new_section;
-      /* Add a section reference to the list.  */
-      new_section = new_stat (lang_input_matcher, &ptr->matching_sections);
-      new_section->section = section;
-      new_section->pattern = sec;
-      new_section->input_stmt = file;
-    }
-}
-
 /* Match all sections from FILE against the global prefix tree,
    and record them into each wild statement that has a match.  */
 
@@ -940,37 +894,28 @@ resolve_wild_sections (lang_input_statement_type *file)
   for (s = file->the_bfd->sections; s != NULL; s = s->next)
     {
       const char *sname = bfd_section_name (s);
-      char c;
-      struct prefixtree **pt = &ptroot, *t = *pt;
+      char c = 1;
+      struct prefixtree *t = ptroot;
       if (old_max_section_id && s->id < old_max_section_id)
 	continue;
       //printf (" YYY consider %s of %s\n", sname, file->the_bfd->filename);
       do
 	{
-	  if (!t)
-	    break;
 	  if (t->stmt)
 	    {
 	      struct wild_stmt_list *sl;
 	      for (sl = t->stmt; sl; sl = sl->next)
 		{
-		  walk_wild_section_match (sl->stmt, file, s, add_matching_callback, NULL);
+		  walk_wild_section_match (sl->stmt, file, s);
 		  //printf ("   ZZZ maybe place into %p\n", sl->stmt);
 		}
 	    }
+	  if (!c)
+	    break;
 	  c = *sname++;
 	  t = get_prefix_tree (&t->child, c, false);
 	}
-      while (c && t);
-      if (t && t->stmt)
-	{
-	  struct wild_stmt_list *sl;
-	  for (sl = t->stmt; sl; sl = sl->next)
-	    {
-	      walk_wild_section_match (sl->stmt, file, s, add_matching_callback, NULL);
-	      //printf ("   ZZZ maybe place into %p\n", sl->stmt);
-	    }
-	}
+      while (t);
     }
 }
 
@@ -979,7 +924,6 @@ resolve_wild_sections (lang_input_statement_type *file)
 static void
 resolve_wilds (void)
 {
-  check_resolve = false;
   LANG_FOR_EACH_INPUT_STATEMENT (f)
     {
       //printf("XXX   %s\n", f->filename);
@@ -1011,7 +955,6 @@ resolve_wilds (void)
 	}
     }
   old_max_section_id = bfd_get_max_section_id ();
-  check_resolve = true;
 }
 
 /* For each input section that matches wild statement S calls
@@ -1025,13 +968,13 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
   if (s->max_section_id < bfd_get_max_section_id ())
     {
       //printf("XXX %s\n", s->filename ? s->filename : "<null>");
-      s->resolved = true;
       s->max_section_id = bfd_get_max_section_id ();
     }
 
   for (l = s->matching_sections.head; l; l = l->header.next)
     {
-      (*callback) (s, l->input_matcher.pattern, l->input_matcher.section, l->input_matcher.input_stmt, data);
+      (*callback) (s, l->input_matcher.pattern, l->input_matcher.section,
+		   l->input_matcher.input_stmt, data);
     }
 }
 
@@ -7910,7 +7853,6 @@ reset_one_wild (lang_statement_union_type *statement)
   if (statement->header.type == lang_wild_statement_enum)
     {
       lang_wild_statement_type *stmt = &statement->wild_statement;
-      stmt->resolved = false;
       stmt->max_section_id = 0;
       /* XXX Leaks? */
       lang_list_init (&stmt->matching_sections);
@@ -8298,7 +8240,6 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt->section_list = section_list;
   new_stmt->keep_sections = keep_sections;
   lang_list_init (&new_stmt->children);
-  new_stmt->resolved = false;
   new_stmt->max_section_id = 0;
   lang_list_init (&new_stmt->matching_sections);
   analyze_walk_wild_section_handler (new_stmt);
diff --git a/ld/ldlang.h b/ld/ldlang.h
index 09c43611a22..5d9d2447f1c 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -399,7 +399,6 @@ struct lang_wild_statement_struct
   lang_statement_list_type children;
   struct name_list *exclude_name_list;
   lang_statement_list_type matching_sections;
-  bool resolved;
   unsigned int max_section_id;
 
   lang_section_bst_type *tree, **rightmost;
-- 
2.36.1

[PATCH 7/8] section-select: Remove bfd_max_section_id again

[Michael Matz]

since we reset the whole matching state completely we don't
need the already-seen early-outs anymore.
---

Depending on how 4/8 is decided this patch might not land in the tree in 
the end, as without rebuilding the whole matchings from scratch the 
early-outs remain useful,


Ciao,
Michael.

 bfd/bfd-in2.h |  2 --
 bfd/section.c | 19 -------------------
 ld/ldlang.c   | 19 +------------------
 ld/ldlang.h   |  1 -
 4 files changed, 1 insertion(+), 40 deletions(-)

diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h
index 5350ae42b03..0b071dda1e5 100644
--- a/bfd/bfd-in2.h
+++ b/bfd/bfd-in2.h
@@ -1330,8 +1330,6 @@ discarded_section (const asection *sec)
   { 0, NAME, 0, BSF_SECTION_SYM, SECTION }
 #endif
 
-unsigned int bfd_get_max_section_id (void);
-
 void bfd_section_list_clear (bfd *);
 
 asection *bfd_get_section_by_name (bfd *abfd, const char *name);
diff --git a/bfd/section.c b/bfd/section.c
index d691bf265ab..f73e0345e15 100644
--- a/bfd/section.c
+++ b/bfd/section.c
@@ -849,25 +849,6 @@ SUBSECTION
 These are the functions exported by the section handling part of BFD.
 */
 
-/*
-FUNCTION
-	bfd_get_max_section_id
-
-SYNOPSIS
-	unsigned int bfd_get_max_section_id (void);
-
-DESCRIPTION
-	Returns an internal number representing the maximum value of
-	any SECTION->id member.  Whenever a new section is created that
-	value increases.  It never decreases.
-*/
-
-unsigned int
-bfd_get_max_section_id (void)
-{
-  return _bfd_section_id;
-}
-
 /*
 FUNCTION
 	bfd_section_list_clear
diff --git a/ld/ldlang.c b/ld/ldlang.c
index 18d10531d51..abaa9916256 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -368,8 +368,6 @@ walk_wild_file_in_exclude_list (struct name_list *exclude_list,
   return false;
 }
 
-static unsigned int old_max_section_id = 0;
-
 /* Add SECTION (from input FILE) to the list of matching sections
    within PTR (the matching wildcard is SEC).  */
 
@@ -402,9 +400,6 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
   const char *file_spec = ptr->filename;
   char *p;
 
-  if (s->id < ptr->max_section_id)
-    return;
-
   /* Check if filenames match.  */
   if (file_spec == NULL)
     ;
@@ -896,8 +891,6 @@ resolve_wild_sections (lang_input_statement_type *file)
       const char *sname = bfd_section_name (s);
       char c = 1;
       struct prefixtree *t = ptroot;
-      if (old_max_section_id && s->id < old_max_section_id)
-	continue;
       //printf (" YYY consider %s of %s\n", sname, file->the_bfd->filename);
       do
 	{
@@ -954,7 +947,6 @@ resolve_wilds (void)
 	    }
 	}
     }
-  old_max_section_id = bfd_get_max_section_id ();
 }
 
 /* For each input section that matches wild statement S calls
@@ -965,12 +957,7 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data)
 {
   lang_statement_union_type *l;
 
-  if (s->max_section_id < bfd_get_max_section_id ())
-    {
-      //printf("XXX %s\n", s->filename ? s->filename : "<null>");
-      s->max_section_id = bfd_get_max_section_id ();
-    }
-
+  //printf("XXX %s\n", s->filename ? s->filename : "<null>");
   for (l = s->matching_sections.head; l; l = l->header.next)
     {
       (*callback) (s, l->input_matcher.pattern, l->input_matcher.section,
@@ -7853,8 +7840,6 @@ reset_one_wild (lang_statement_union_type *statement)
   if (statement->header.type == lang_wild_statement_enum)
     {
       lang_wild_statement_type *stmt = &statement->wild_statement;
-      stmt->max_section_id = 0;
-      /* XXX Leaks? */
       lang_list_init (&stmt->matching_sections);
     }
 }
@@ -7863,7 +7848,6 @@ static void
 reset_resolved_wilds (void)
 {
   lang_for_each_statement (reset_one_wild);
-  old_max_section_id = 0;
 }
 
 void
@@ -8240,7 +8224,6 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt->section_list = section_list;
   new_stmt->keep_sections = keep_sections;
   lang_list_init (&new_stmt->children);
-  new_stmt->max_section_id = 0;
   lang_list_init (&new_stmt->matching_sections);
   analyze_walk_wild_section_handler (new_stmt);
   if (0)
diff --git a/ld/ldlang.h b/ld/ldlang.h
index 5d9d2447f1c..b92a7bb9d96 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -399,7 +399,6 @@ struct lang_wild_statement_struct
   lang_statement_list_type children;
   struct name_list *exclude_name_list;
   lang_statement_list_type matching_sections;
-  unsigned int max_section_id;
 
   lang_section_bst_type *tree, **rightmost;
   struct flag_info *section_flag_list;
-- 
2.36.1

[PATCH 8/8] section-select: Fix exclude-file-3

[Michael Matz]

this testcase wasn't correctly testing everything, it passed, even
though sections from an excluded file were included.  Fixing this
reveals a problem in the new section selector.  This fixes that as
well.
---
 ld/ldlang.c                                | 7 ++++---
 ld/testsuite/ld-scripts/exclude-file-3.map | 4 +++-
 2 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index abaa9916256..4e9b93a83a7 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -422,6 +422,10 @@ walk_wild_section_match (lang_wild_statement_type *ptr,
 	return;
     }
 
+  /* If filename is excluded we're done.  */
+  if (walk_wild_file_in_exclude_list (ptr->exclude_name_list, file))
+    return;
+
   /* Check section name against each wildcard spec.  If there's no
      wildcard all sections match.  */
   sec = ptr->section_list;
@@ -920,9 +924,6 @@ resolve_wilds (void)
   LANG_FOR_EACH_INPUT_STATEMENT (f)
     {
       //printf("XXX   %s\n", f->filename);
-      /* XXX if (walk_wild_file_in_exclude_list (s->exclude_name_list, f))
-	return;*/
-
       if (f->the_bfd == NULL
 	  || !bfd_check_format (f->the_bfd, bfd_archive))
 	resolve_wild_sections (f);
diff --git a/ld/testsuite/ld-scripts/exclude-file-3.map b/ld/testsuite/ld-scripts/exclude-file-3.map
index 389d1708c90..255182030ca 100644
--- a/ld/testsuite/ld-scripts/exclude-file-3.map
+++ b/ld/testsuite/ld-scripts/exclude-file-3.map
@@ -3,5 +3,7 @@
  EXCLUDE_FILE\(\*-b\.o\) \*\(\.data \.data\.\*\)
  \.data +0x[0-9a-f]+ +0x[0-9a-f]+ tmpdir/exclude-file-a\.o
  \.data\.1 +0x[0-9a-f]+ +0x[0-9a-f]+ tmpdir/exclude-file-a\.o
+#failif
+.*data +0x[0-9a-f]+ +0x[0-9a-f]+ .*exclude-file-b.*
 
-#...
\ No newline at end of file
+#...
-- 
2.36.1

Re: [PATCH 4/8] section-select: Completely rebuild matches

[Alan Modra]

On Fri, Nov 25, 2022 at 04:55:12PM +0000, Michael Matz via Binutils wrote:
> this resets all section matches before updating for newly created
> sections (i.e. completely rebuilds the matches).  This fixes powerpc
> "TOC opt" tests that shows a difference in section order: originally
> .got of "linker stubs" comes before .toc (both placed into the same
> .got output section due to ".got {*(.got .toc)}".  But .got of linker
> stubs is created later, and in the second run of resolve_wilds is
> appended to the list, hence is then coming after .toc (which was added
> already in the earlier resolve_wilds run).  So order swapped ->
> test fails.

That's a problem.  The got header is created in the .got of "linker
stubs", and code setting the value of .TOC. assumes that the header
will be located first in the .got output section.  This ties in with
where ld.so expects to find the header too.

-- 
Alan Modra
Australia Development Lab, IBM

Re: [PATCH 4/8] section-select: Completely rebuild matches

[Michael Matz]

Hello,

On Mon, 28 Nov 2022, Alan Modra wrote:

> On Fri, Nov 25, 2022 at 04:55:12PM +0000, Michael Matz via Binutils wrote:
> > this resets all section matches before updating for newly created
> > sections (i.e. completely rebuilds the matches).  This fixes powerpc
> > "TOC opt" tests that shows a difference in section order: originally
> > .got of "linker stubs" comes before .toc (both placed into the same
> > .got output section due to ".got {*(.got .toc)}".  But .got of linker
> > stubs is created later, and in the second run of resolve_wilds is
> > appended to the list, hence is then coming after .toc (which was added
> > already in the earlier resolve_wilds run).  So order swapped ->
> > test fails.
> 
> That's a problem.  The got header is created in the .got of "linker
> stubs", and code setting the value of .TOC. assumes that the header
> will be located first in the .got output section.  This ties in with
> where ld.so expects to find the header too.

I see.  But then why is the testcase (and linker script?) not using

  .got { *(.got) *(.toc) }

?  The way it's written right now means "for each file, first its .got 
then its .toc, intermixed", i.e. file1.got, file1.toc, file2.got, 
file2.toc ...  And it seems a bit fuzzy to speak about "files" for the 
artificial generated pseudo files like "linker stubs".

(Just to be clear: rebuilding all matches also solves this problem)


Ciao,
Michael.

Re: [PATCH 4/8] section-select: Completely rebuild matches

[Alan Modra]

On Mon, Nov 28, 2022 at 02:24:30PM +0000, Michael Matz wrote:
> Hello,
> 
> On Mon, 28 Nov 2022, Alan Modra wrote:
> 
> > On Fri, Nov 25, 2022 at 04:55:12PM +0000, Michael Matz via Binutils wrote:
> > > this resets all section matches before updating for newly created
> > > sections (i.e. completely rebuilds the matches).  This fixes powerpc
> > > "TOC opt" tests that shows a difference in section order: originally
> > > .got of "linker stubs" comes before .toc (both placed into the same
> > > .got output section due to ".got {*(.got .toc)}".  But .got of linker
> > > stubs is created later, and in the second run of resolve_wilds is
> > > appended to the list, hence is then coming after .toc (which was added
> > > already in the earlier resolve_wilds run).  So order swapped ->
> > > test fails.
> > 
> > That's a problem.  The got header is created in the .got of "linker
> > stubs", and code setting the value of .TOC. assumes that the header
> > will be located first in the .got output section.  This ties in with
> > where ld.so expects to find the header too.
> 
> I see.  But then why is the testcase (and linker script?) not using
> 
>   .got { *(.got) *(.toc) }
> 
> ?  The way it's written right now means "for each file, first its .got 
> then its .toc, intermixed", i.e. file1.got, file1.toc, file2.got, 
> file2.toc ...

Yes.  That's the way we want it.  When linking small model code with a
total GOT/TOC of over 64k, the linker splits the TOC into multiple
pieces with r2 adjusting stubs inserted on calls between files that
use different pieces of the TOC.  That scheme wouldn't work if a
file's .got entries were placed in a different piece of the TOC to the
file's .toc entries.

-- 
Alan Modra
Australia Development Lab, IBM

Re: [PATCH 4/8] section-select: Completely rebuild matches

[Michael Matz]

Hey,

On Tue, 29 Nov 2022, Alan Modra wrote:

> > > That's a problem.  The got header is created in the .got of "linker
> > > stubs", and code setting the value of .TOC. assumes that the header
> > > will be located first in the .got output section.  This ties in with
> > > where ld.so expects to find the header too.
> > 
> > I see.  But then why is the testcase (and linker script?) not using
> > 
> >   .got { *(.got) *(.toc) }
> > 
> > ?  The way it's written right now means "for each file, first its .got 
> > then its .toc, intermixed", i.e. file1.got, file1.toc, file2.got, 
> > file2.toc ...
> 
> Yes.  That's the way we want it.  When linking small model code with a
> total GOT/TOC of over 64k, the linker splits the TOC into multiple
> pieces with r2 adjusting stubs inserted on calls between files that
> use different pieces of the TOC.  That scheme wouldn't work if a
> file's .got entries were placed in a different piece of the TOC to the
> file's .toc entries.

Ah, nifty.  Something like that occurred to me yesterday as well, and 
either way, rewriting the linker script like above wouldn't have helped 
this problem anyway, as long as "linker stubs".got would have been created 
late it would always have been placed at the end of the list.

Although one could pedantically argue that those late-created sections 
being placed at the end would indeed conform to "as they are found in the 
linker input", I won't belabor that point.  Complete rebuilding it is, 
performance-wise it's a wash :)


Ciao,
Michael.