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]

dynsym/dynstr/relocs sorting speedup #2


Hi there,

        It seems that by sorting dynsym & dynstr and relocations by
(elf_hash % bucketcount) we can easily get a 5%+ speedup for linking.
This is because (for large libraries) a lot of the time we miss the
L1/L2 cache, hence ordering the data in a more predictable fashion helps
substantially.

	In this case for a hash-collision we make walking the chain far less
expensive - walking adjacent memory: this should help arbitrary lookups
of anything. Furthermore - we sort the relocations in the same order
(missing this was making my previous tests look bad). Anyway - the
patch is quite simple, but I'd love some feedback / suggestions for
improvement.

	The patch 'breaks' 3 ld regression tests - this is due to re-sorting
both the relocs & the symbol tables; trivial to fix - but I'd rather get
review first.

	I also created an (updated) standalone test harness to demonstrate the
improvement, just fixup LD path & run 'make test':

        http://www.gnome.org/~michael/dynsort-test.tar.gz

	For this test: ~25% faster
                UnSorted     37ms
                Sorted       28ms

	Of course - cachegrind output is more reliable (condensed):

* L2 data read misses:

do_lookup_x    362k -> 130k
strcmp	       159k -> 53k
_dl_elf_hash   158k -> 147k

* L1 data read misses:

_dl_relocate_obj    1649k -> 587k
do_lookup_x	    923k -> 295k
_dl_elf_hash	    187k -> 162k
strcmp		    216k -> 80k

	Which are nice reductions (without libc, libstdc++ etc. being sorted
etc.).

	Since I was suckered last time by a non-real-world scenario of
super-long buckets, this time I - generated numbers for some other big
libraries too:

	libsvx (alone) - 2% faster [ best of avg 3 runs of 10 each ]
	libvcl (+5 deps) - 4% faster [ best of avg 4 runs of 50 each ]

	Obviously, the more dependents one re-links with this the better life
is, eg. vcl has 27 dependents; so one could wildly extrapolate to it
being somewhat faster if they are all sorted.

        issues / queries:
                * calculates elf hash of strtab symbols again
                        + could we store the elf_link_hash_entry
                          pointer from bfd_elf_record_dynamic_symbol ?
                          where possible to avoid re-calculating that.
                * qsort - has no closure, nasty global variable for
                          bucket count - how should that be fixed ?
                * conditional
                        + the sorting takes some time & space at link
                          time - should it be conditional ?
			+ should we shrink the number of discrete bucket
			  counts, clearly where these match the current
			  library we get a better win [ should we pick 
			  the best count/avg of the deps ? ;-]

        Thoughts appreciated,

        Thanks,

                Michael.

-- 
 michael.meeks@novell.com  <><, Pseudo Engineer, itinerant idiot
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/ChangeLog binutils.current/bfd/ChangeLog
--- binutils-2.16.91.0.4/bfd/ChangeLog	2005-11-13 17:16:34.000000000 +0000
+++ binutils.current/bfd/ChangeLog	2005-12-23 16:14:05.000000000 +0000
@@ -1,3 +1,37 @@
+2005-12-23  Michael Meeks  <michael.meeks@novell.com>
+
+	* elf-strtab.c (_bfd_elf_strtab_init, _bfd_elf_strtab_free):
+	manage the sorted array.
+	(_bfd_elf_strtab_emit): emit .dynstr in sorted order.
+	(_bfd_elf_strtab_finalize, hash_compare): sort .dynstr
+	primarily by elf bucket index.
+
+	* elflink.c (elf_finalize_dynstr): pass bucket count to
+	strtab_finalize.
+	(_bfd_elf_ver_hash): split for re-use from
+	(elf_collect_hash_codes): here.
+	(_bfd_elf_link_hash_traverse): new traversal function:
+	walks sorted array if sorted, else walks the hash as before.
+	(elf_sort_dynsym_hash): qsort method to sort dynsyms
+	(elf_sort_collect_dynsyms): hash walker to collect symbols
+	(_bfd_elf_sort_dynsyms): method - sorts .dynsym section.
+	(bfd_elf_size_dynsym_hash_dynstr): do the .dynsym sort.
+	(elf_link_sort_relocs, elf_link_sort_cmp2): sort relocs
+	primarily by elf bucket index.
+	(bfd_elf_final_link): update reloc sort call.
+
+	* elf.c (_bfd_elf_link_hash_table_init),
+	(_bfd_elf_link_hash_table_free): init & free sorted array.
+	(assign_section_numbers): upd. strtab_finalize call.
+
+	* elf32-m68hc1x.c (m68hc11_elf_bfd_link_hash_table_free),
+	* elf-m10300.c (elf32_mn10300_link_hash_table_free),
+	* elf32-hppa.c (elf32_hppa_link_hash_table_free),
+	* elf64-ppc.c (ppc64_elf_link_hash_table_free),
+	* elf.c (_bfd_elf_link_hash_table_free),
+	* elfxx-target.h: implement elf specific hash free
+	method & re-direct callers to it.
+
 2005-11-11  Nick Clifton  <nickc@redhat.com>
 
 	PR 1150
Files binutils-2.16.91.0.4/bfd/doc/chew and binutils.current/bfd/doc/chew differ
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf32-hppa.c binutils.current/bfd/elf32-hppa.c
--- binutils-2.16.91.0.4/bfd/elf32-hppa.c	2005-11-13 17:16:34.000000000 +0000
+++ binutils.current/bfd/elf32-hppa.c	2005-12-23 14:06:31.000000000 +0000
@@ -435,7 +435,7 @@
     = (struct elf32_hppa_link_hash_table *) btab;
 
   bfd_hash_table_free (&htab->bstab);
-  _bfd_generic_link_hash_table_free (btab);
+  _bfd_elf_link_hash_table_free (hash);
 }
 
 /* Build a name for an entry in the stub hash table.  */
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf32-m68hc1x.c binutils.current/bfd/elf32-m68hc1x.c
--- binutils-2.16.91.0.4/bfd/elf32-m68hc1x.c	2005-06-22 21:53:34.000000000 +0100
+++ binutils.current/bfd/elf32-m68hc1x.c	2005-12-23 14:07:21.000000000 +0000
@@ -106,7 +106,7 @@
 
   bfd_hash_table_free (ret->stub_hash_table);
   free (ret->stub_hash_table);
-  _bfd_generic_link_hash_table_free (hash);
+  _bfd_elf_link_hash_table_free (hash);
 }
 
 /* Assorted hash table functions.  */
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf32-target.h binutils.current/bfd/elf32-target.h
--- binutils-2.16.91.0.4/bfd/elf32-target.h	2005-12-23 17:12:23.000000000 +0000
+++ binutils.current/bfd/elf32-target.h	2005-12-23 14:51:28.000000000 +0000
@@ -205,7 +205,7 @@
 #endif
 
 #ifndef bfd_elf32_bfd_link_hash_table_free
-#define bfd_elf32_bfd_link_hash_table_free _bfd_generic_link_hash_table_free
+#define bfd_elf32_bfd_link_hash_table_free _bfd_elf_link_hash_table_free
 #endif
 
 #ifdef elf_backend_relocate_section
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf64-ppc.c binutils.current/bfd/elf64-ppc.c
--- binutils-2.16.91.0.4/bfd/elf64-ppc.c	2005-11-13 17:16:34.000000000 +0000
+++ binutils.current/bfd/elf64-ppc.c	2005-12-23 14:04:07.000000000 +0000
@@ -3502,7 +3502,7 @@
 
   bfd_hash_table_free (&ret->stub_hash_table);
   bfd_hash_table_free (&ret->branch_hash_table);
-  _bfd_generic_link_hash_table_free (hash);
+  _bfd_elf_link_hash_table_free (hash);
 }
 
 /* Satisfy the ELF linker by filling in some fields in our fake bfd.  */
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf-bfd.h binutils.current/bfd/elf-bfd.h
--- binutils-2.16.91.0.4/bfd/elf-bfd.h	2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elf-bfd.h	2005-12-23 14:59:54.000000000 +0000
@@ -340,6 +340,10 @@
 {
   struct bfd_link_hash_table root;
 
+  /* Symbol sort order for final traversal at output */
+  unsigned int sorted_size;
+  struct elf_link_hash_entry **sorted;
+
   /* Whether we have created the special dynamic sections required
      when linking against or generating a shared object.  */
   bfd_boolean dynamic_sections_created;
@@ -418,11 +422,16 @@
 /* Traverse an ELF linker hash table.  */
 
 #define elf_link_hash_traverse(table, func, info)			\
-  (bfd_link_hash_traverse						\
-   (&(table)->root,							\
-    (bfd_boolean (*) (struct bfd_link_hash_entry *, void *)) (func),	\
+  (_bfd_elf_link_hash_traverse						\
+   ((table),								\
+    (bfd_boolean (*) (struct elf_link_hash_entry *, void *)) (func),	\
     (info)))
 
+void _bfd_elf_link_hash_traverse
+  (struct elf_link_hash_table *table,
+   bfd_boolean (*func) (struct elf_link_hash_entry *, void *),
+   void *info);
+
 /* Get the ELF linker hash table from a link_info structure.  */
 
 #define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))
@@ -1446,6 +1455,8 @@
 
 extern unsigned long bfd_elf_hash
   (const char *);
+extern unsigned long _bfd_elf_ver_hash
+  (const char *);
 
 extern bfd_reloc_status_type bfd_elf_generic_reloc
   (bfd *, arelent *, asymbol *, void *, asection *, bfd *, char **);
@@ -1463,6 +1474,7 @@
   (struct bfd_hash_entry *, struct bfd_hash_table *, const char *);
 extern struct bfd_link_hash_table *_bfd_elf_link_hash_table_create
   (bfd *);
+extern void _bfd_elf_link_hash_table_free (struct bfd_link_hash_table *);
 extern void _bfd_elf_link_hash_copy_indirect
   (struct bfd_link_info *, struct elf_link_hash_entry *,
    struct elf_link_hash_entry *);
@@ -1593,7 +1605,7 @@
 extern bfd_boolean _bfd_elf_strtab_emit
   (bfd *, struct elf_strtab_hash *);
 extern void _bfd_elf_strtab_finalize
-  (struct elf_strtab_hash *);
+  (struct elf_strtab_hash *, size_t);
 
 extern bfd_boolean _bfd_elf_discard_section_eh_frame
   (bfd *, struct bfd_link_info *, asection *,
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf.c binutils.current/bfd/elf.c
--- binutils-2.16.91.0.4/bfd/elf.c	2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elf.c	2005-12-23 14:04:18.000000000 +0000
@@ -1560,6 +1560,8 @@
   table->tls_size = 0;
   table->loaded = NULL;
   table->is_relocatable_executable = FALSE;
+  table->sorted = NULL;
+  table->sorted_size = 0;
 
   ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc);
   table->root.type = bfd_link_elf_hash_table;
@@ -1588,6 +1590,15 @@
   return &ret->root;
 }
 
+void
+_bfd_elf_link_hash_table_free (struct bfd_link_hash_table *hash)
+{
+  struct elf_link_hash_table *table = (struct elf_link_hash_table *) hash;
+  if (table->sorted)
+    free (table->sorted);
+  _bfd_generic_link_hash_table_free (hash);
+}
+
 /* This is a hook for the ELF emulation code in the generic linker to
    tell the backend linker what file name to use for the DT_NEEDED
    entry for a dynamic object.  */
@@ -2983,7 +2994,7 @@
       _bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);
     }
 
-  _bfd_elf_strtab_finalize (elf_shstrtab (abfd));
+  _bfd_elf_strtab_finalize (elf_shstrtab (abfd), 0);
   t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));
 
   elf_numsections (abfd) = section_number;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elflink.c binutils.current/bfd/elflink.c
--- binutils-2.16.91.0.4/bfd/elflink.c	2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elflink.c	2005-12-23 17:07:52.000000000 +0000
@@ -3007,7 +3007,8 @@
   const struct elf_backend_data *bed;
   bfd_byte *extdyn;
 
-  _bfd_elf_strtab_finalize (dynstr);
+  _bfd_elf_strtab_finalize (dynstr,
+			    elf_hash_table (info)->bucketcount);
   size = _bfd_elf_strtab_size (dynstr);
 
   bed = get_elf_backend_data (dynobj);
@@ -4715,27 +4716,17 @@
       return FALSE;
     }
 }
-
-/* This function will be called though elf_link_hash_traverse to store
-   all hash value of the exported symbols in an array.  */
 
-static bfd_boolean
-elf_collect_hash_codes (struct elf_link_hash_entry *h, void *data)
+/*
+ * Compute the elf hash value of the name ignoring the version.
+ */
+unsigned long
+_bfd_elf_ver_hash (const char *name)
 {
-  unsigned long **valuep = data;
-  const char *name;
   char *p;
   unsigned long ha;
   char *alc = NULL;
 
-  if (h->root.type == bfd_link_hash_warning)
-    h = (struct elf_link_hash_entry *) h->root.u.i.link;
-
-  /* Ignore indirect symbols.  These are added by the versioning code.  */
-  if (h->dynindx == -1)
-    return TRUE;
-
-  name = h->root.root.string;
   p = strchr (name, ELF_VER_CHR);
   if (p != NULL)
     {
@@ -4748,6 +4739,31 @@
   /* Compute the hash value.  */
   ha = bfd_elf_hash (name);
 
+  if (alc != NULL)
+    free (alc);
+
+  return ha;
+}
+
+
+/* This function will be called though elf_link_hash_traverse to store
+   all hash value of the exported symbols in an array.  */
+
+static bfd_boolean
+elf_collect_hash_codes (struct elf_link_hash_entry *h, void *data)
+{
+  unsigned long **valuep = data;
+  unsigned long ha;
+
+  if (h->root.type == bfd_link_hash_warning)
+    h = (struct elf_link_hash_entry *) h->root.u.i.link;
+
+  /* Ignore indirect symbols.  These are added by the versioning code.  */
+  if (h->dynindx == -1)
+    return TRUE;
+
+  ha = _bfd_elf_ver_hash (h->root.root.string);
+
   /* Store the found hash value in the array given as the argument.  */
   *(*valuep)++ = ha;
 
@@ -4755,9 +4771,6 @@
      later.  */
   h->u.elf_hash_value = ha;
 
-  if (alc != NULL)
-    free (alc);
-
   return TRUE;
 }
 
@@ -4920,6 +4933,124 @@
   return best_size;
 }
 
+void _bfd_elf_link_hash_traverse
+  (struct elf_link_hash_table *table,
+   bfd_boolean (*func) (struct elf_link_hash_entry *, void *),
+   void *info)
+{
+  if (!table->sorted)
+    bfd_link_hash_traverse						\
+      (&(table)->root,							\
+       (bfd_boolean (*) (struct bfd_link_hash_entry *, void *)) (func),	\
+       (info));
+  else
+    {
+      unsigned int i;
+      for (i = 0; i < table->sorted_size; i++)
+        {
+          if (! func (table->sorted[i], info))
+	    return;
+	}
+    }
+}
+
+/* Where is the qsort closure ? */
+static size_t give_me_a_bucket_count = 0;
+
+/* Sort by elf hash value % buckets  */
+static int
+elf_sort_dynsym_hash (const void *arg1, const void *arg2)
+{
+  size_t h1_bucket, h2_bucket;
+  const struct elf_link_hash_entry *h1;
+  const struct elf_link_hash_entry *h2;
+
+  h1 = *(const struct elf_link_hash_entry **) arg1;
+  h2 = *(const struct elf_link_hash_entry **) arg2;
+
+  h1_bucket = h1->u.elf_hash_value % give_me_a_bucket_count;
+  h2_bucket = h2->u.elf_hash_value % give_me_a_bucket_count;
+
+  if (h1_bucket > h2_bucket)
+    return 1;
+  if (h1_bucket < h2_bucket)
+    return -1;
+
+  return 0;
+}
+
+struct elf_dynsym_sort_info
+{
+  bfd_boolean  do_dynsym;
+  unsigned int alloc_size;
+  unsigned int sorted_size;
+  struct elf_link_hash_entry **sorted_syms;
+};
+
+/* collect sym entries into an array for later sorting */
+static bfd_boolean
+elf_sort_collect_dynsyms (struct elf_link_hash_entry *h, void *data)
+{
+  struct elf_dynsym_sort_info *sinfo = data;
+
+  if ((sinfo->do_dynsym && h->dynindx < 0) ||
+      (!sinfo->do_dynsym && h->dynindx >= 0))
+    return TRUE;
+
+  if (sinfo->sorted_size >= sinfo->alloc_size)
+    {
+      sinfo->alloc_size *= 2;
+      /* FIXME: need to free this data too ... */
+      sinfo->sorted_syms = bfd_realloc (sinfo->sorted_syms,
+					 sizeof (struct elf_link_hash_entry *) *
+					 sinfo->alloc_size);
+    }
+  sinfo->sorted_syms [sinfo->sorted_size++] = h;
+
+  return TRUE;
+}
+
+/*
+ * Sort the exported elf symbols by elf_hash % bucketcount to
+ * improve run-time linker cache behavior. Subsequent
+ * elf_link_hash_traverse calls will reflect this new order.
+ */
+static bfd_boolean
+_bfd_elf_sort_dynsyms (struct bfd_link_info *info)
+{
+  struct elf_dynsym_sort_info sinfo;
+
+  sinfo.alloc_size = 8;
+  sinfo.sorted_syms = bfd_malloc (sizeof (struct elf_link_hash_entry *) *
+				  sinfo.alloc_size);
+  if (!sinfo.sorted_syms)
+    return FALSE;
+
+  sinfo.sorted_size = 0;
+
+  /* append dynsyms for sorting */
+  sinfo.do_dynsym = TRUE;
+  elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+  /* sort them ... */
+  if (!getenv ("DONT_SORT_SYMS")) {
+	  give_me_a_bucket_count = elf_hash_table (info)->bucketcount;
+	  qsort (sinfo.sorted_syms, sinfo.sorted_size,
+		 sizeof (struct elf_link_hash_entry *),
+		 elf_sort_dynsym_hash);
+  }
+
+  /* append everything else */
+  sinfo.do_dynsym = FALSE;
+  elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+  /* freed in _bfd_elf_link_hash_table_free */
+  elf_hash_table (info)->sorted = sinfo.sorted_syms;
+  elf_hash_table (info)->sorted_size = sinfo.sorted_size;
+
+  return TRUE;
+}
+
 /* Set up the sizes and contents of the ELF dynamic sections.  This is
    called by the ELF linker emulation before_allocation routine.  We
    must set the sizes of the sections before the linker sets the
@@ -5686,6 +5817,7 @@
 	 section symbol for each output section, which come first.
 	 Next come all of the back-end allocated local dynamic syms,
 	 followed by the rest of the global symbols.  */
+      /* To sort these optimally we need the correct bucketcount */
 
       dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,
 						    &section_sym_count);
@@ -5756,6 +5888,15 @@
       for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)
 	if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))
 	  return FALSE;
+
+      /* Sort .dynsym to accelerate runtime linking */
+      { /* FIXME - make this conditional (?) */
+        if (!_bfd_elf_sort_dynsyms (info))
+          return FALSE;
+	/* reflect the new sorting order */
+	_bfd_elf_link_renumber_dynsyms (output_bfd, info,
+					&section_sym_count);
+      }
     }
 
   return TRUE;
@@ -5892,6 +6033,7 @@
     bfd_vma sym_mask;
   } u;
   enum elf_reloc_type_class type;
+  unsigned long elf_bucket;
   /* We use this as an array of size int_rels_per_ext_rel.  */
   Elf_Internal_Rela rela[1];
 };
@@ -5928,6 +6070,10 @@
   const struct elf_link_sort_rela *b = B;
   int copya, copyb;
 
+  if (a->elf_bucket < b->elf_bucket)
+    return -1;
+  if (a->elf_bucket > b->elf_bucket)
+    return 1;
   if (a->u.offset < b->u.offset)
     return -1;
   if (a->u.offset > b->u.offset)
@@ -5946,8 +6092,9 @@
 }
 
 static size_t
-elf_link_sort_relocs (bfd *abfd, struct bfd_link_info *info, asection **psec)
+elf_link_sort_relocs (bfd *abfd, struct elf_final_link_info *finfo, asection **psec)
 {
+  struct bfd_link_info *info = finfo->info;
   asection *reldyn;
   bfd_size_type count, size;
   size_t i, ret, sort_elt, ext_size;
@@ -5959,6 +6106,8 @@
   void (*swap_out) (bfd *, const Elf_Internal_Rela *, bfd_byte *);
   struct bfd_link_order *lo;
   bfd_vma r_sym_mask;
+  int r_sym_shift;
+  int do_sort_relocs = !getenv ("DONT_SORT_RELOCS");
 
   reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");
   if (reldyn == NULL || reldyn->size == 0)
@@ -6000,15 +6149,29 @@
     }
 
   if (bed->s->arch_size == 32)
-    r_sym_mask = ~(bfd_vma) 0xff;
+    {
+      r_sym_mask = ~(bfd_vma) 0xff;
+      r_sym_shift = 8;
+    }
   else
-    r_sym_mask = ~(bfd_vma) 0xffffffff;
+    {
+      r_sym_mask = ~(bfd_vma) 0xffffffff;
+      r_sym_shift = 32;
+    }
 
   for (lo = reldyn->map_head.link_order; lo != NULL; lo = lo->next)
     if (lo->type == bfd_indirect_link_order)
       {
 	bfd_byte *erel, *erelend;
 	asection *o = lo->u.indirect.section;
+	int base_offset = -1;
+	int base_max = 0;
+
+	if (elf_hash_table (info)->sorted_size > 0)
+	  {
+	    base_offset = elf_hash_table (info)->sorted[0]->dynindx;
+	    base_max = base_offset + elf_hash_table (info)->sorted_size;
+	  }
 
 	if (o->contents == NULL && o->size != 0)
 	  {
@@ -6023,10 +6186,25 @@
 	p = sort + o->output_offset / ext_size * sort_elt;
 	while (erel < erelend)
 	  {
+	    long dyn_idx;
+	    size_t bucketcount = elf_hash_table (info)->bucketcount;
 	    struct elf_link_sort_rela *s = (struct elf_link_sort_rela *) p;
 	    (*swap_in) (abfd, erel, s->rela);
 	    s->type = (*bed->elf_backend_reloc_type_class) (s->rela);
 	    s->u.sym_mask = r_sym_mask;
+	    
+	    if (s->type != reloc_class_relative)
+	      dyn_idx = s->rela->r_info >> r_sym_shift;
+	    else
+	      dyn_idx = -1;
+
+	    if (do_sort_relocs &&
+		base_offset >= 0 &&
+		dyn_idx < base_max && dyn_idx >= base_offset)
+	      s->elf_bucket = elf_hash_table (info)->sorted [dyn_idx - base_offset]->u.elf_hash_value % bucketcount;
+	    else
+	      s->elf_bucket = 0;
+				       
 	    p += sort_elt;
 	    erel += ext_size;
 	  }
@@ -8426,7 +8604,7 @@
     }
 
   if (dynamic && info->combreloc && dynobj != NULL)
-    relativecount = elf_link_sort_relocs (abfd, info, &reldyn);
+    relativecount = elf_link_sort_relocs (abfd, &finfo, &reldyn);
 
   /* If we are linking against a dynamic object, or generating a
      shared library, finish up the dynamic linking information.  */
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf-m10300.c binutils.current/bfd/elf-m10300.c
--- binutils-2.16.91.0.4/bfd/elf-m10300.c	2005-11-13 17:16:34.000000000 +0000
+++ binutils.current/bfd/elf-m10300.c	2005-12-23 14:06:10.000000000 +0000
@@ -3729,8 +3729,7 @@
 
   _bfd_generic_link_hash_table_free
     ((struct bfd_link_hash_table *) ret->static_hash_table);
-  _bfd_generic_link_hash_table_free
-    ((struct bfd_link_hash_table *) ret);
+  _bfd_elf_link_hash_table_free (hash);
 }
 
 static unsigned long
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf-strtab.c binutils.current/bfd/elf-strtab.c
--- binutils-2.16.91.0.4/bfd/elf-strtab.c	2005-05-10 23:46:41.000000000 +0100
+++ binutils.current/bfd/elf-strtab.c	2005-12-23 17:07:50.000000000 +0000
@@ -39,6 +39,7 @@
     /* Entry this is a suffix of (if len < 0).  */
     struct elf_strtab_hash_entry *suffix;
   } u;
+  long hash_bucket;
 };
 
 /* The strtab hash table.  */
@@ -54,6 +55,8 @@
   bfd_size_type sec_size;
   /* Array of pointers to strtab entries.  */
   struct elf_strtab_hash_entry **array;
+  /* Array of pointers to strtab entries.  */
+  struct elf_strtab_hash_entry **array_sorted;
 };
 
 /* Routine to create an entry in a section merge hashtab.  */
@@ -117,6 +120,7 @@
     }
 
   table->array[0] = NULL;
+  table->array_sorted = NULL;
 
   return table;
 }
@@ -128,6 +132,8 @@
 {
   bfd_hash_table_free (&tab->table);
   free (tab->array);
+  if (tab->array_sorted)
+    free (tab->array_sorted);
   free (tab);
 }
 
@@ -229,6 +235,12 @@
 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 {
   bfd_size_type off = 1, i;
+  struct elf_strtab_hash_entry **array;
+
+  if (tab->array_sorted != NULL)
+    array = tab->array_sorted;
+  else
+    array = tab->array;
 
   if (bfd_bwrite ("", 1, abfd) != 1)
     return FALSE;
@@ -238,12 +250,12 @@
       register const char *str;
       register unsigned int len;
 
-      BFD_ASSERT (tab->array[i]->refcount == 0);
-      len = tab->array[i]->len;
+      BFD_ASSERT (array[i]->refcount == 0);
+      len = array[i]->len;
       if ((int) len < 0)
 	continue;
 
-      str = tab->array[i]->root.string;
+      str = array[i]->root.string;
       if (bfd_bwrite (str, len, abfd) != len)
 	return FALSE;
 
@@ -278,6 +290,26 @@
   return lenA - lenB;
 }
 
+/* sort by hash bucket position */
+static int
+hash_compare (const void *a, const void *b)
+{
+  struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
+  struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
+
+  if (A->hash_bucket > B->hash_bucket)
+    return 1;
+  if (A->hash_bucket < B->hash_bucket)
+    return -1;
+
+  /* Make qsort faster for lots of identical empty symbols */
+  if (a > b)
+    return 1;
+  if (a < b)
+    return -1;
+  return 0;
+}
+
 static inline int
 is_suffix (const struct elf_strtab_hash_entry *A,
 	   const struct elf_strtab_hash_entry *B)
@@ -293,9 +325,8 @@
 
 /* This function assigns final string table offsets for used strings,
    merging strings matching suffixes of longer strings if possible.  */
-
 void
-_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
+_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab, size_t bucket_count)
 {
   struct elf_strtab_hash_entry **array, **a, *e;
   bfd_size_type size, amt;
@@ -361,15 +392,37 @@
 	}
     }
 
-alloc_failure:
-  if (array)
-    free (array);
+  if (bucket_count && !getenv ("DONT_SORT_SYMS"))
+    {
+      array[0] = NULL;
+      for (i = 1; i < tab->size; ++i)
+	{
+	  e = tab->array[i];
+	  array[i] = e;
+
+	  if (e->len > 0)
+	    {
+	      e->hash_bucket = _bfd_elf_ver_hash (e->root.string);
+	      e->hash_bucket %= bucket_count;
+	    }
+	  else
+	    e->hash_bucket = 0;
+	}
+      qsort (array + 1, tab->size - 1, sizeof (struct elf_strtab_hash_entry *), hash_compare);
+      tab->array_sorted = array;
+    }
+  else
+    {
+      free (array);
+ alloc_failure:
+      array = tab->array;
+    }
 
   /* Assign positions to the strings we want to keep.  */
   size = 1;
   for (i = 1; i < tab->size; ++i)
     {
-      e = tab->array[i];
+      e = array[i];
       if (e->refcount && e->len > 0)
 	{
 	  e->u.index = size;
@@ -382,7 +435,7 @@
   /* Adjust the rest.  */
   for (i = 1; i < tab->size; ++i)
     {
-      e = tab->array[i];
+      e = array[i];
       if (e->refcount && e->len < 0)
 	e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
     }
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elfxx-target.h binutils.current/bfd/elfxx-target.h
--- binutils-2.16.91.0.4/bfd/elfxx-target.h	2005-08-22 20:27:41.000000000 +0100
+++ binutils.current/bfd/elfxx-target.h	2005-12-23 14:06:51.000000000 +0000
@@ -205,7 +205,7 @@
 #endif
 
 #ifndef bfd_elfNN_bfd_link_hash_table_free
-#define bfd_elfNN_bfd_link_hash_table_free _bfd_generic_link_hash_table_free
+#define bfd_elfNN_bfd_link_hash_table_free _bfd_elf_link_hash_table_free
 #endif
 
 #ifdef elf_backend_relocate_section

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