[PATCH v2 1/2] ld: pe: Improve performance of object file exclude symbol directives

[PATCH v2 1/2] ld: pe: Improve performance of object file exclude symbol directives

[Martin Storsjö]

Store the list of excluded symbols in a sorted list, speeding up
checking for duplicates when inserting new entries.

This is done in the same way as is done for exports and imports
(while the previous implementation was done with a linked list,
based on the implementation for aligncomm).

When linking object files with excluded symbols, there can potentially
be very large numbers of excluded symbols (just like builds with
exports can have a large number of exported symbols).

This improves the link performance somewhat, when linking with large
numbers of excluded symbols.

The later actual use of the excluded symbols within pe-dll.c
handles them via an unordered linked list still, though.
---
 ld/deffile.h  |   2 +-
 ld/deffilep.y | 124 ++++++++++++++++++++++++++++++++++++++------------
 ld/pe-dll.c   |   8 ++--
 3 files changed, 99 insertions(+), 35 deletions(-)

diff --git a/ld/deffile.h b/ld/deffile.h
index a247639628e..89ffe9f972e 100644
--- a/ld/deffile.h
+++ b/ld/deffile.h
@@ -62,7 +62,6 @@ typedef struct def_file_aligncomm {
 } def_file_aligncomm;
 
 typedef struct def_file_exclude_symbol {
-  struct def_file_exclude_symbol *next;	/* Chain pointer.  */
   char *symbol_name;		/* Name of excluded symbol.  */
 } def_file_exclude_symbol;
 
@@ -101,6 +100,7 @@ typedef struct def_file {
   def_file_aligncomm *aligncomms;
 
   /* From EXCLUDE_SYMBOLS or embedded directives. */
+  unsigned int num_exclude_symbols, max_exclude_symbols;
   def_file_exclude_symbol *exclude_symbols;
 
 } def_file;
diff --git a/ld/deffilep.y b/ld/deffilep.y
index 27db336e0f5..ed8f0d6719a 100644
--- a/ld/deffilep.y
+++ b/ld/deffilep.y
@@ -32,6 +32,8 @@
 
 #define ROUND_UP(a, b) (((a)+((b)-1))&~((b)-1))
 
+#define SYMBOL_LIST_ARRAY_GROW 64
+
 /* Remap normal yacc parser interface names (yyparse, yylex, yyerror, etc),
    as well as gratuitiously global symbol names, so we can have multiple
    yacc generated parsers in ld.  Note that these are only the variables
@@ -440,6 +442,7 @@ void
 def_file_free (def_file *fdef)
 {
   int i;
+  unsigned int ui;
 
   if (!fdef)
     return;
@@ -497,14 +500,11 @@ def_file_free (def_file *fdef)
       free (c);
     }
 
-  while (fdef->exclude_symbols)
+  for (ui = 0; ui < fdef->num_exclude_symbols; ui++)
     {
-      def_file_exclude_symbol *e = fdef->exclude_symbols;
-
-      fdef->exclude_symbols = fdef->exclude_symbols->next;
-      free (e->symbol_name);
-      free (e);
+      free (fdef->exclude_symbols[ui].symbol_name);
     }
+  free (fdef->exclude_symbols);
 
   free (fdef);
 }
@@ -949,6 +949,93 @@ def_file_add_import_at (def_file *fdef,
   return i;
 }
 
+/* Search the position of the identical element, or returns the position
+   of the next higher element. If last valid element is smaller, then MAX
+   is returned. The max parameter indicates the number of elements in the
+   array. On return, *is_ident indicates whether the returned array index
+   points at an element which is identical to the one searched for.  */
+
+static unsigned int
+find_exclude_in_list (def_file_exclude_symbol *b, unsigned int max,
+		      const char *name, bool *is_ident)
+{
+  int e;
+  unsigned int l, r, p;
+
+  *is_ident = false;
+  if (!max)
+    return 0;
+  if ((e = strcmp (b[0].symbol_name, name)) <= 0)
+    {
+      if (!e)
+	*is_ident = true;
+      return 0;
+    }
+  if (max == 1)
+    return 1;
+  if ((e = strcmp (b[max - 1].symbol_name, name)) > 0)
+    return max;
+  else if (!e || max == 2)
+    {
+      if (!e)
+	*is_ident = true;
+      return max - 1;
+    }
+  l = 0; r = max - 1;
+  while (l < r)
+    {
+      p = (l + r) / 2;
+      e = strcmp (b[p].symbol_name, name);
+      if (!e)
+	{
+	  *is_ident = true;
+	  return p;
+	}
+      else if (e < 0)
+	r = p - 1;
+      else if (e > 0)
+	l = p + 1;
+    }
+  if ((e = strcmp (b[l].symbol_name, name)) > 0)
+    ++l;
+  else if (!e)
+    *is_ident = true;
+  return l;
+}
+
+static def_file_exclude_symbol *
+def_file_add_exclude_symbol (def_file *fdef, const char *name)
+{
+  def_file_exclude_symbol *e;
+  unsigned pos;
+  bool is_dup = false;
+
+  pos = find_exclude_in_list (fdef->exclude_symbols, fdef->num_exclude_symbols,
+			      name, &is_dup);
+
+  /* We need to avoid duplicates.  */
+  if (is_dup)
+    return (fdef->exclude_symbols + pos);
+
+  if (fdef->num_exclude_symbols >= fdef->max_exclude_symbols)
+    {
+      fdef->max_exclude_symbols += SYMBOL_LIST_ARRAY_GROW;
+      fdef->exclude_symbols = xrealloc (fdef->exclude_symbols,
+					fdef->max_exclude_symbols * sizeof (def_file_exclude_symbol));
+    }
+
+  e = fdef->exclude_symbols + pos;
+  /* If we're inserting in the middle of the array, we need to move the
+     following elements forward.  */
+  if (pos != fdef->num_exclude_symbols)
+    memmove (&e[1], e, (sizeof (def_file_exclude_symbol) * (fdef->num_exclude_symbols - pos)));
+  /* Wipe the element for use as a new entry.  */
+  memset (e, 0, sizeof (def_file_exclude_symbol));
+  e->symbol_name = xstrdup (name);
+  fdef->num_exclude_symbols++;
+  return e;
+}
+
 struct
 {
   char *param;
@@ -1280,30 +1367,7 @@ def_aligncomm (char *str, int align)
 static void
 def_exclude_symbols (char *str)
 {
-  def_file_exclude_symbol *c, *p;
-
-  p = NULL;
-  c = def->exclude_symbols;
-  while (c != NULL)
-    {
-      int e = strcmp (c->symbol_name, str);
-      if (!e)
-        return;
-      c = (p = c)->next;
-    }
-
-  c = xmalloc (sizeof (def_file_exclude_symbol));
-  c->symbol_name = xstrdup (str);
-  if (!p)
-    {
-      c->next = def->exclude_symbols;
-      def->exclude_symbols = c;
-    }
-  else
-    {
-      c->next = p->next;
-      p->next = c;
-    }
+  def_file_add_exclude_symbol (def, str);
 }
 
 static void
diff --git a/ld/pe-dll.c b/ld/pe-dll.c
index fbf180ec0f2..60584a88571 100644
--- a/ld/pe-dll.c
+++ b/ld/pe-dll.c
@@ -671,6 +671,7 @@ static void
 process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info *info)
 {
   int i, j;
+  unsigned int ui;
   struct bfd_link_hash_entry *blhe;
   bfd *b;
   struct bfd_section *s;
@@ -720,11 +721,10 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info *
 
   if (pe_def_file->exclude_symbols)
     {
-      def_file_exclude_symbol *ac = pe_def_file->exclude_symbols;
-      while (ac)
+      for (ui = 0; ui < pe_def_file->num_exclude_symbols; ui++)
 	{
-	  pe_dll_add_excludes (ac->symbol_name, EXCLUDESYMS);
-	  ac = ac->next;
+	  pe_dll_add_excludes (pe_def_file->exclude_symbols[ui].symbol_name,
+			       EXCLUDESYMS);
 	}
     }
 
-- 
2.25.1

[PATCH v2 2/2] ld: pe: Apply review suggestions on the existing exports/imports arrays

[Martin Storsjö]

Use a separate explicit max_exports/imports field, instead of
deducing it from the number of allocated elements. Use a named
constant for the incremental growth of the array.

Use bool instead of int for boolean values.

Remove an unnecessary if statement/scope in the def_file_free
function.

Add more verbose comments about parameters, and about insertion
into an array of structs.

Generally use unsigned integers for all array indices and sizes.
The num_exports/imports fields are kept as is as signed integers,
since changing them to unsigned would require a disproportionate
amount of changes ti pe-dll.c to avoid comparisons between signed
and unsigned.

Simply use xrealloc instead of a check and xmalloc/xrealloc;
xrealloc can take NULL as the first parameter (and does a similar
check internally). (This wasn't requested in review though,
but noticed while working on the code.)
---
 ld/deffile.h  |   6 +-
 ld/deffilep.y | 157 ++++++++++++++++++++++++--------------------------
 ld/pe-dll.c   |   6 +-
 3 files changed, 83 insertions(+), 86 deletions(-)

diff --git a/ld/deffile.h b/ld/deffile.h
index 89ffe9f972e..9eb08ad83fb 100644
--- a/ld/deffile.h
+++ b/ld/deffile.h
@@ -84,6 +84,7 @@ typedef struct def_file {
 
   /* From the EXPORTS commands.  */
   int num_exports;
+  unsigned int max_exports;
   def_file_export *exports;
 
   /* Used by imports for module names.  */
@@ -91,6 +92,7 @@ typedef struct def_file {
 
   /* From the IMPORTS commands.  */
   int num_imports;
+  unsigned int max_imports;
   def_file_import *imports;
 
   /* From the VERSION command, -1 if not specified.  */
@@ -112,10 +114,10 @@ extern def_file *def_file_parse (const char *, def_file *);
 extern void def_file_free (def_file *);
 extern def_file_export *def_file_add_export (def_file *, const char *,
 					     const char *, int,
-					     const char *, int *);
+					     const char *, bool *);
 extern def_file_import *def_file_add_import (def_file *, const char *,
 					     const char *, int, const char *,
-					     const char *, int *);
+					     const char *, bool *);
 extern int def_file_add_import_from (def_file *fdef,
 				     int num_imports,
 				     const char *name,
diff --git a/ld/deffilep.y b/ld/deffilep.y
index ed8f0d6719a..d7052a63beb 100644
--- a/ld/deffilep.y
+++ b/ld/deffilep.y
@@ -459,29 +459,23 @@ def_file_free (def_file *fdef)
       free (fdef->section_defs);
     }
 
-  if (fdef->exports)
+  for (i = 0; i < fdef->num_exports; i++)
     {
-      for (i = 0; i < fdef->num_exports; i++)
-	{
-	  if (fdef->exports[i].internal_name != fdef->exports[i].name)
-	    free (fdef->exports[i].internal_name);
-	  free (fdef->exports[i].name);
-	  free (fdef->exports[i].its_name);
-	}
-      free (fdef->exports);
+      if (fdef->exports[i].internal_name != fdef->exports[i].name)
+        free (fdef->exports[i].internal_name);
+      free (fdef->exports[i].name);
+      free (fdef->exports[i].its_name);
     }
+  free (fdef->exports);
 
-  if (fdef->imports)
+  for (i = 0; i < fdef->num_imports; i++)
     {
-      for (i = 0; i < fdef->num_imports; i++)
-	{
-	  if (fdef->imports[i].internal_name != fdef->imports[i].name)
-	    free (fdef->imports[i].internal_name);
-	  free (fdef->imports[i].name);
-	  free (fdef->imports[i].its_name);
-	}
-      free (fdef->imports);
+      if (fdef->imports[i].internal_name != fdef->imports[i].name)
+        free (fdef->imports[i].internal_name);
+      free (fdef->imports[i].name);
+      free (fdef->imports[i].its_name);
     }
+  free (fdef->imports);
 
   while (fdef->modules)
     {
@@ -627,22 +621,25 @@ cmp_export_elem (const def_file_export *e, const char *ex_name,
 
 /* Search the position of the identical element, or returns the position
    of the next higher element. If last valid element is smaller, then MAX
-   is returned.  */
+   is returned. The max parameter indicates the number of elements in the
+   array. On return, *is_ident indicates whether the returned array index
+   points at an element which is identical to the one searched for.  */
 
-static int
-find_export_in_list (def_file_export *b, int max,
+static unsigned int
+find_export_in_list (def_file_export *b, unsigned int max,
 		     const char *ex_name, const char *in_name,
-		     const char *its_name, int ord, int *is_ident)
+		     const char *its_name, int ord, bool *is_ident)
 {
-  int e, l, r, p;
+  int e;
+  unsigned int l, r, p;
 
-  *is_ident = 0;
+  *is_ident = false;
   if (!max)
     return 0;
   if ((e = cmp_export_elem (b, ex_name, in_name, its_name, ord)) <= 0)
     {
       if (!e)
-	*is_ident = 1;
+	*is_ident = true;
       return 0;
     }
   if (max == 1)
@@ -652,7 +649,7 @@ find_export_in_list (def_file_export *b, int max,
   else if (!e || max == 2)
     {
       if (!e)
-	*is_ident = 1;
+	*is_ident = true;
       return max - 1;
     }
   l = 0; r = max - 1;
@@ -662,7 +659,7 @@ find_export_in_list (def_file_export *b, int max,
       e = cmp_export_elem (b + p, ex_name, in_name, its_name, ord);
       if (!e)
 	{
-	  *is_ident = 1;
+	  *is_ident = true;
 	  return p;
 	}
       else if (e < 0)
@@ -673,7 +670,7 @@ find_export_in_list (def_file_export *b, int max,
   if ((e = cmp_export_elem (b + l, ex_name, in_name, its_name, ord)) > 0)
     ++l;
   else if (!e)
-    *is_ident = 1;
+    *is_ident = true;
   return l;
 }
 
@@ -683,11 +680,10 @@ def_file_add_export (def_file *fdef,
 		     const char *internal_name,
 		     int ordinal,
 		     const char *its_name,
-		     int *is_dup)
+		     bool *is_dup)
 {
   def_file_export *e;
-  int pos;
-  int max_exports = ROUND_UP(fdef->num_exports, 32);
+  unsigned int pos;
 
   if (internal_name && !external_name)
     external_name = internal_name;
@@ -695,27 +691,27 @@ def_file_add_export (def_file *fdef,
     internal_name = external_name;
 
   /* We need to avoid duplicates.  */
-  *is_dup = 0;
+  *is_dup = false;
   pos = find_export_in_list (fdef->exports, fdef->num_exports,
 		     external_name, internal_name,
 		     its_name, ordinal, is_dup);
 
-  if (*is_dup != 0)
+  if (*is_dup)
     return (fdef->exports + pos);
 
-  if (fdef->num_exports >= max_exports)
+  if ((unsigned)fdef->num_exports >= fdef->max_exports)
     {
-      max_exports = ROUND_UP(fdef->num_exports + 1, 32);
-      if (fdef->exports)
-	fdef->exports = xrealloc (fdef->exports,
-				 max_exports * sizeof (def_file_export));
-      else
-	fdef->exports = xmalloc (max_exports * sizeof (def_file_export));
+      fdef->max_exports += SYMBOL_LIST_ARRAY_GROW;
+      fdef->exports = xrealloc (fdef->exports,
+				fdef->max_exports * sizeof (def_file_export));
     }
 
   e = fdef->exports + pos;
-  if (pos != fdef->num_exports)
+  /* If we're inserting in the middle of the array, we need to move the
+     following elements forward.  */
+  if (pos != (unsigned)fdef->num_exports)
     memmove (&e[1], e, (sizeof (def_file_export) * (fdef->num_exports - pos)));
+  /* Wipe the element for use as a new entry.  */
   memset (e, 0, sizeof (def_file_export));
   e->name = xstrdup (external_name);
   e->internal_name = xstrdup (internal_name);
@@ -772,22 +768,25 @@ cmp_import_elem (const def_file_import *e, const char *ex_name,
 
 /* Search the position of the identical element, or returns the position
    of the next higher element. If last valid element is smaller, then MAX
-   is returned.  */
+   is returned. The max parameter indicates the number of elements in the
+   array. On return, *is_ident indicates whether the returned array index
+   points at an element which is identical to the one searched for.  */
 
-static int
-find_import_in_list (def_file_import *b, int max,
+static unsigned int
+find_import_in_list (def_file_import *b, unsigned int max,
 		     const char *ex_name, const char *in_name,
-		     const char *module, int ord, int *is_ident)
+		     const char *module, int ord, bool *is_ident)
 {
-  int e, l, r, p;
+  int e;
+  unsigned int l, r, p;
 
-  *is_ident = 0;
+  *is_ident = false;
   if (!max)
     return 0;
   if ((e = cmp_import_elem (b, ex_name, in_name, module, ord)) <= 0)
     {
       if (!e)
-	*is_ident = 1;
+	*is_ident = true;
       return 0;
     }
   if (max == 1)
@@ -797,7 +796,7 @@ find_import_in_list (def_file_import *b, int max,
   else if (!e || max == 2)
     {
       if (!e)
-	*is_ident = 1;
+	*is_ident = true;
       return max - 1;
     }
   l = 0; r = max - 1;
@@ -807,7 +806,7 @@ find_import_in_list (def_file_import *b, int max,
       e = cmp_import_elem (b + p, ex_name, in_name, module, ord);
       if (!e)
 	{
-	  *is_ident = 1;
+	  *is_ident = true;
 	  return p;
 	}
       else if (e < 0)
@@ -818,7 +817,7 @@ find_import_in_list (def_file_import *b, int max,
   if ((e = cmp_import_elem (b + l, ex_name, in_name, module, ord)) > 0)
     ++l;
   else if (!e)
-    *is_ident = 1;
+    *is_ident = true;
   return l;
 }
 
@@ -849,33 +848,30 @@ def_file_add_import (def_file *fdef,
 		     int ordinal,
 		     const char *internal_name,
 		     const char *its_name,
-		     int *is_dup)
+		     bool *is_dup)
 {
   def_file_import *i;
-  int pos;
-  int max_imports = ROUND_UP (fdef->num_imports, 16);
+  unsigned int pos;
 
   /* We need to avoid here duplicates.  */
-  *is_dup = 0;
+  *is_dup = false;
   pos = find_import_in_list (fdef->imports, fdef->num_imports,
 			     name,
 			     (!internal_name ? name : internal_name),
 			     module, ordinal, is_dup);
-  if (*is_dup != 0)
+  if (*is_dup)
     return fdef->imports + pos;
 
-  if (fdef->num_imports >= max_imports)
+  if ((unsigned)fdef->num_imports >= fdef->max_imports)
     {
-      max_imports = ROUND_UP (fdef->num_imports+1, 16);
-
-      if (fdef->imports)
-	fdef->imports = xrealloc (fdef->imports,
-				 max_imports * sizeof (def_file_import));
-      else
-	fdef->imports = xmalloc (max_imports * sizeof (def_file_import));
+      fdef->max_imports += SYMBOL_LIST_ARRAY_GROW;
+      fdef->imports = xrealloc (fdef->imports,
+				fdef->max_imports * sizeof (def_file_import));
     }
   i = fdef->imports + pos;
-  if (pos != fdef->num_imports)
+  /* If we're inserting in the middle of the array, we need to move the
+     following elements forward.  */
+  if (pos != (unsigned)fdef->num_imports)
     memmove (i + 1, i, sizeof (def_file_import) * (fdef->num_imports - pos));
 
   fill_in_import (i, name, def_stash_module (fdef, module), ordinal,
@@ -895,36 +891,35 @@ def_file_add_import_from (def_file *fdef,
 			  const char *its_name ATTRIBUTE_UNUSED)
 {
   def_file_import *i;
-  int is_dup;
-  int pos;
-  int max_imports = ROUND_UP (fdef->num_imports, 16);
+  bool is_dup;
+  unsigned int pos;
 
   /* We need to avoid here duplicates.  */
-  is_dup = 0;
+  is_dup = false;
   pos = find_import_in_list (fdef->imports, fdef->num_imports,
 			     name, internal_name ? internal_name : name,
 			     module, ordinal, &is_dup);
-  if (is_dup != 0)
+  if (is_dup)
     return -1;
-  if (fdef->imports && pos != fdef->num_imports)
+  if (fdef->imports && pos != (unsigned)fdef->num_imports)
     {
       i = fdef->imports + pos;
       if (i->module && strcmp (i->module->name, module) == 0)
 	return -1;
     }
 
-  if (fdef->num_imports + num_imports - 1 >= max_imports)
+  if ((unsigned)fdef->num_imports + num_imports - 1 >= fdef->max_imports)
     {
-      max_imports = ROUND_UP (fdef->num_imports + num_imports, 16);
+      fdef->max_imports = fdef->num_imports + num_imports +
+			  SYMBOL_LIST_ARRAY_GROW;
 
-      if (fdef->imports)
-	fdef->imports = xrealloc (fdef->imports,
-				 max_imports * sizeof (def_file_import));
-      else
-	fdef->imports = xmalloc (max_imports * sizeof (def_file_import));
+      fdef->imports = xrealloc (fdef->imports,
+				fdef->max_imports * sizeof (def_file_import));
     }
   i = fdef->imports + pos;
-  if (pos != fdef->num_imports)
+  /* If we're inserting in the middle of the array, we need to move the
+     following elements forward.  */
+  if (pos != (unsigned)fdef->num_imports)
     memmove (i + num_imports, i,
 	     sizeof (def_file_import) * (fdef->num_imports - pos));
 
@@ -1261,7 +1256,7 @@ def_exports (const char *external_name,
 	     const char *its_name)
 {
   def_file_export *dfe;
-  int is_dup = 0;
+  bool is_dup = false;
 
   if (!internal_name && external_name)
     internal_name = external_name;
@@ -1297,7 +1292,7 @@ def_import (const char *internal_name,
 {
   char *buf = 0;
   const char *ext = dllext ? dllext : "dll";
-  int is_dup = 0;
+  bool is_dup = false;
 
   buf = xmalloc (strlen (module) + strlen (ext) + 2);
   sprintf (buf, "%s.%s", module, ext);
diff --git a/ld/pe-dll.c b/ld/pe-dll.c
index 60584a88571..92c33f528c8 100644
--- a/ld/pe-dll.c
+++ b/ld/pe-dll.c
@@ -791,7 +791,7 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info *
 
 		  if (auto_export (b, pe_def_file, sn))
 		    {
-		      int is_dup = 0;
+		      bool is_dup = false;
 		      def_file_export *p;
 
 		      p = def_file_add_export (pe_def_file, sn, 0, -1,
@@ -857,7 +857,7 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info *
 
 	  if (strchr (pe_def_file->exports[i].name, '@'))
 	    {
-	      int is_dup = 1;
+	      bool is_dup = true;
 	      int lead_at = (*pe_def_file->exports[i].name == '@');
 	      char *tmp = xstrdup (pe_def_file->exports[i].name + lead_at);
 
@@ -3579,7 +3579,7 @@ pe_implied_import_dll (const char *filename)
 	 exported in buggy auto-import releases.  */
       if (! startswith (erva + name_rva, "__nm_"))
 	{
-	  int is_dup = 0;
+	  bool is_dup = false;
 	  /* is_data is true if the address is in the data, rdata or bss
 	     segment.  */
 	  is_data =
-- 
2.25.1

Re: [PATCH v2 1/2] ld: pe: Improve performance of object file exclude symbol directives

[Nick Clifton]

Hi Martin,

> Store the list of excluded symbols in a sorted list, speeding up
> checking for duplicates when inserting new entries.

Patch approved - please apply.

Cheers
   Nick

Re: [PATCH v2 2/2] ld: pe: Apply review suggestions on the existing exports/imports arrays

[Nick Clifton]

Hi Martin,

> Use a separate explicit max_exports/imports field, instead of
> deducing it from the number of allocated elements. Use a named
> constant for the incremental growth of the array.

Patch approved - please apply.

Cheers
   Nick

Re: [PATCH v2 1/2] ld: pe: Improve performance of object file exclude symbol directives

[Martin Storsjö]

On Fri, 9 Sep 2022, Nick Clifton wrote:

> Hi Martin,
>
>> Store the list of excluded symbols in a sorted list, speeding up
>> checking for duplicates when inserting new entries.
>
> Patch approved - please apply.

Thanks! Applied both patches now.

// Martin