This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch ld]: Improve speed for import-table resolving for aliases


Hi,

patch improves for large import-tables the link-time speed on alias-matching.

ChangeLog

2012-03-09  Kai Tietz  <ktietz@redhat.com>
	    Pascal Obry  <pascal@obry.net>

	* pe-dll.c (found_sym): New static variable.
	(undef_count): Likewise.
	(key_value): New structure.
	(undef_sort_cmp): Compare routine for qsort/bsearch.
	(pe_find_cdecl_alias_match): Add new argument.
	(pe_undef_alias_cdecl_match): Removed.
	(pe_undef_count): New helper routine.
	(pe_create_undef_table): Likewise.
	(pe_process_import_defs): Use pe_create_undef_table and
	new pe_undef_alias_cdecl_match function.

Patch tested for i686-w64-mingw32, x86_64-w32-mingw32, and
i686-pc-cygwin.  Ok for apply?

Regards,
Kai

Index: pe-dll.c
===================================================================
RCS file: /cvs/src/src/ld/pe-dll.c,v
retrieving revision 1.141
diff -u -p -r1.141 pe-dll.c
--- pe-dll.c	19 Feb 2012 21:18:08 -0000	1.141
+++ pe-dll.c	9 Mar 2012 19:18:36 -0000
@@ -2817,36 +2817,160 @@ pe_dll_generate_implib (def_file *def, c
     }
 }

-static struct bfd_link_hash_entry *found_sym;
+static int undef_count = 0;
+
+struct key_value
+{
+  char *key;
+  const char *oname;
+};
+
+struct key_value *udef_table;
+
+static int undef_sort_cmp (const void *l1, const void *r1)
+{
+  const struct key_value *l = l1;
+  const struct key_value *r = r1;
+
+  return strcmp (l->key, r->key);
+}
+
+static struct bfd_link_hash_entry *
+pe_find_cdecl_alias_match (struct bfd_link_info *linfo, char *name)
+{
+  struct bfd_link_hash_entry *h = NULL;
+  struct key_value *kv;
+  struct key_value key;
+  char *at, *lname = (char *) alloca (strlen (name) + 3);
+
+  strcpy (lname, name);
+
+  at = strchr (lname + (lname[0] == '@'), '@');
+  if (at)
+    at[1] = 0;
+
+  key.key = lname;
+  kv = bsearch (&key, udef_table, undef_count, sizeof (struct key_value),
+		undef_sort_cmp);
+
+  if (kv)
+    {
+      h = bfd_link_hash_lookup (linfo->hash, kv->oname, FALSE, FALSE, FALSE);
+      if (h->type == bfd_link_hash_undefined)
+        return h;
+    }
+  if (lname[0] == '?')
+    return NULL;
+  if (at || lname[0] == '@')
+    {
+      if (lname[0] == '@')
+        {
+	  if (pe_details->underscored)
+	    lname[0] = '_';
+	  else
+	    strcpy (lname, lname + 1);
+	  key.key = lname;
+	  kv = bsearch (&key, udef_table, undef_count,
+			sizeof (struct key_value), undef_sort_cmp);
+	  if (kv)
+	    {
+	      h = bfd_link_hash_lookup (linfo->hash, kv->oname, FALSE, FALSE, FALSE);
+	      if (h->type == bfd_link_hash_undefined)
+		return h;
+	    }
+	}
+      if (at)
+        *strchr (lname, '@') = 0;
+      key.key = lname;
+      kv = bsearch (&key, udef_table, undef_count,
+		    sizeof (struct key_value), undef_sort_cmp);
+      if (kv)
+	{
+	  h = bfd_link_hash_lookup (linfo->hash, kv->oname, FALSE, FALSE, FALSE);
+	  if (h->type == bfd_link_hash_undefined)
+	    return h;
+	}
+      return NULL;
+    }
+
+  strcat (lname, "@");
+  key.key = lname;
+  kv = bsearch (&key, udef_table, undef_count,
+		sizeof (struct key_value), undef_sort_cmp);
+
+  if (kv)
+    {
+      h = bfd_link_hash_lookup (linfo->hash, kv->oname, FALSE, FALSE, FALSE);
+      if (h->type == bfd_link_hash_undefined)
+	return h;
+    }
+
+  if (lname[0] == '_' && pe_details->underscored)
+    lname[0] = '@';
+  else
+    {
+      memmove (lname + 1, lname, strlen (lname) + 1);
+      lname[0] = '@';
+    }
+  key.key = lname;
+
+  kv = bsearch (&key, udef_table, undef_count,
+		sizeof (struct key_value), undef_sort_cmp);
+
+  if (kv)
+    {
+      h = bfd_link_hash_lookup (linfo->hash, kv->oname, FALSE, FALSE, FALSE);
+      if (h->type == bfd_link_hash_undefined)
+        return h;
+    }
+
+  return NULL;
+}
+
+static bfd_boolean
+pe_undef_count (struct bfd_link_hash_entry *h ATTRIBUTE_UNUSED,
+                void *inf ATTRIBUTE_UNUSED)
+{
+  if (h->type == bfd_link_hash_undefined)
+    undef_count++;
+  return TRUE;
+}

 static bfd_boolean
-pe_undef_alias_cdecl_match (struct bfd_link_hash_entry *h, void *inf)
+pe_undef_fill (struct bfd_link_hash_entry *h, void *inf ATTRIBUTE_UNUSED)
 {
-  int sl;
-  char *string = inf;
-  const char *hs = h->root.string;
-
-  sl = strlen (string);
-  if (h->type == bfd_link_hash_undefined
-      && ((*hs == '@' && (!pe_details->underscored || *string == '_')
-	   && strncmp (hs + 1, string + (pe_details->underscored != 0),
-		       sl - (pe_details->underscored != 0)) == 0)
-	  || strncmp (hs, string, sl) == 0)
-      && h->root.string[sl] == '@')
+  if (h->type == bfd_link_hash_undefined)
     {
-      found_sym = h;
-      return FALSE;
+      char *at;
+
+      udef_table[undef_count].key = xstrdup (h->root.string);
+      at = strchr (udef_table[undef_count].key
+		   + (udef_table[undef_count].key[0] == '@'), '@');
+      if (at)
+        at[1] = 0;
+      udef_table[undef_count].oname = h->root.string;
+      undef_count++;
     }
   return TRUE;
 }

-static struct bfd_link_hash_entry *
-pe_find_cdecl_alias_match (char *name)
+static void
+pe_create_undef_table (void)
 {
-  found_sym = 0;
-  bfd_link_hash_traverse (link_info.hash, pe_undef_alias_cdecl_match,
-			  (char *) name);
-  return found_sym;
+  undef_count = 0;
+
+  /* count undefined symbols */
+
+  bfd_link_hash_traverse (link_info.hash, pe_undef_count, "");
+
+  /* create and fill the corresponding table */
+  udef_table = xmalloc (undef_count * sizeof (struct key_value));
+
+  undef_count = 0;
+  bfd_link_hash_traverse (link_info.hash, pe_undef_fill, "");
+
+  /* sort items */
+  qsort (udef_table, undef_count, sizeof (struct key_value), undef_sort_cmp);
 }

 static void
@@ -2878,6 +3002,8 @@ pe_process_import_defs (bfd *output_bfd,

   imp = pe_def_file->imports;

+  pe_create_undef_table ();
+
   for (module = pe_def_file->modules; module; module = module->next)
     {
       int do_this_dll = 0;
@@ -2903,6 +3029,8 @@ pe_process_import_defs (bfd *output_bfd,
 	  char *name = xmalloc (len + 2 + 6);
 	  bfd_boolean include_jmp_stub = FALSE;
 	  bfd_boolean is_cdecl = FALSE;
+	  bfd_boolean is_undef = FALSE;
+
 	  if (!lead_at && strchr (imp[i].internal_name, '@') == NULL)
 	      is_cdecl = TRUE;

@@ -2926,20 +3054,27 @@ pe_process_import_defs (bfd *output_bfd,

 	      blhe = bfd_link_hash_lookup (linfo->hash, name,
 					   FALSE, FALSE, FALSE);
+	      if (blhe)
+	        is_undef = (blhe->type == bfd_link_hash_undefined);
 	    }
 	  else
-	    include_jmp_stub = TRUE;
+	    {
+	      include_jmp_stub = TRUE;
+	      is_undef = (blhe->type == bfd_link_hash_undefined);
+	    }

-	  if (is_cdecl && !blhe)
+	  if (is_cdecl && (!blhe || (blhe && blhe->type != bfd_link_hash_undefined)))
 	    {
 	      sprintf (name, "%s%s",U (""), imp[i].internal_name);
-	      blhe = pe_find_cdecl_alias_match (name);
+	      blhe = pe_find_cdecl_alias_match (linfo, name);
 	      include_jmp_stub = TRUE;
+	      if (blhe)
+	        is_undef = (blhe->type == bfd_link_hash_undefined);
 	    }

 	  free (name);

-	  if (blhe && blhe->type == bfd_link_hash_undefined)
+	  if (is_undef)
 	    {
 	      bfd *one;
 	      /* We do.  */
@@ -2970,6 +3105,13 @@ pe_process_import_defs (bfd *output_bfd,

       free (dll_symname);
     }
+
+  while (undef_count)
+    {
+      --undef_count;
+      free (udef_table[undef_count].key);
+    }
+  free (udef_table);
 }

 /* We were handed a *.DLL file.  Parse it and turn it into a set of


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]