[patch] A dynsort patch that applies against binutils-2.17.50.0.2

binutils-suse-dynsort.diff (text/plain), 34.83 KB, created by Peter Levine on 2006-06-13 00:26:22 UTC

diff -Naur binutils-2.17.50.0.2.old/bfd/Makefile.am binutils-2.17.50.0.2/bfd/Makefile.am
--- binutils-2.17.50.0.2.old/bfd/Makefile.am	2006-04-29 12:32:56.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/Makefile.am	2006-06-13 03:11:55.000000000 -0400
@@ -36,7 +36,7 @@
 # need two copies of the executable, one to download and one for the
 # debugger).
 BFD32_LIBS = \
-	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo \
+	archive.lo archures.lo bfd.lo bfdio.lo bfdsort.lo bfdwin.lo \
 	cache.lo coffgen.lo corefile.lo \
 	format.lo init.lo libbfd.lo opncls.lo reloc.lo \
 	section.lo syms.lo targets.lo hash.lo linker.lo \
@@ -46,7 +46,7 @@
 BFD64_LIBS = archive64.lo
 
 BFD32_LIBS_CFILES = \
-	archive.c archures.c bfd.c bfdio.c bfdwin.c \
+	archive.c archures.c bfd.c bfdio.c bfdsort.c bfdwin.c \
 	cache.c coffgen.c corefile.c \
 	format.c init.c libbfd.c opncls.c reloc.c \
 	section.c syms.c targets.c hash.c linker.c \
diff -Naur binutils-2.17.50.0.2.old/bfd/Makefile.in binutils-2.17.50.0.2/bfd/Makefile.in
--- binutils-2.17.50.0.2.old/bfd/Makefile.in	2006-04-29 12:32:56.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/Makefile.in	2006-06-13 03:11:55.000000000 -0400
@@ -79,7 +79,7 @@
 	cache.lo coffgen.lo corefile.lo format.lo init.lo libbfd.lo \
 	opncls.lo reloc.lo section.lo syms.lo targets.lo hash.lo \
 	linker.lo srec.lo binary.lo tekhex.lo ihex.lo stabs.lo \
-	stab-syms.lo merge.lo dwarf2.lo simple.lo
+	stab-syms.lo merge.lo dwarf2.lo simple.lo bfdsort.lo
 am__objects_2 = archive64.lo
 am_libbfd_la_OBJECTS = $(am__objects_1) $(am__objects_2)
 libbfd_la_OBJECTS = $(am_libbfd_la_OBJECTS)
@@ -273,7 +273,7 @@
 # need two copies of the executable, one to download and one for the
 # debugger).
 BFD32_LIBS = \
-	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo \
+	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo bfdsort.lo \
 	cache.lo coffgen.lo corefile.lo \
 	format.lo init.lo libbfd.lo opncls.lo reloc.lo \
 	section.lo syms.lo targets.lo hash.lo linker.lo \
@@ -282,7 +282,7 @@
 
 BFD64_LIBS = archive64.lo
 BFD32_LIBS_CFILES = \
-	archive.c archures.c bfd.c bfdio.c bfdwin.c \
+	archive.c archures.c bfd.c bfdio.c bfdwin.c bfdsort.lo \
 	cache.c coffgen.c corefile.c \
 	format.c init.c libbfd.c opncls.c reloc.c \
 	section.c syms.c targets.c hash.c linker.c \
diff -Naur binutils-2.17.50.0.2.old/bfd/bfd-in.h binutils-2.17.50.0.2/bfd/bfd-in.h
--- binutils-2.17.50.0.2.old/bfd/bfd-in.h	2006-05-26 12:34:04.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/bfd-in.h	2006-06-13 03:11:55.000000000 -0400
@@ -162,6 +162,10 @@
 
 typedef unsigned int flagword;	/* 32 bits of flags */
 typedef unsigned char bfd_byte;
+
+typedef int (*bfd_qsort_closure_func) (const void *, const void *, const void *);
+extern void bfd_qsort (void *base, bfd_size_type nmemb, bfd_size_type size,
+		       bfd_qsort_closure_func cmp, void *closure);
 
 /* File formats.  */
 
diff -Naur binutils-2.17.50.0.2.old/bfd/bfdsort.c binutils-2.17.50.0.2/bfd/bfdsort.c
--- binutils-2.17.50.0.2.old/bfd/bfdsort.c	1969-12-31 19:00:00.000000000 -0500
+++ binutils-2.17.50.0.2/bfd/bfdsort.c	2006-06-13 03:11:55.000000000 -0400
@@ -0,0 +1,255 @@
+/*
+ * This module copied from glibc/stdlib/qsort.c & adapted,
+ * in order to add support for a closure argument.
+ */
+
+/* Copyright (C) 1991,1992,1996,1997,1999,2004 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+   Written by Douglas C. Schmidt ([e-mail]).
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+/* If you consider tuning this algorithm, you should consult first:
+   Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
+   Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
+
+#include "bfd.h"
+#include "sysdep.h"
+
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size)						      \
+  do									      \
+    {									      \
+      register bfd_size_type __size = (size);				      \
+      register char *__a = (a), *__b = (b);				      \
+      do								      \
+	{								      \
+	  char __tmp = *__a;						      \
+	  *__a++ = *__b;						      \
+	  *__b++ = __tmp;						      \
+	} while (--__size > 0);						      \
+    } while (0)
+
+/* Discontinue quicksort algorithm when partition gets below this size.
+   This particular magic number was chosen to work best on a Sun 4/260. */
+#define MAX_THRESH 4
+
+/* Stack node declarations used to store unfulfilled partition obligations. */
+typedef struct
+  {
+    char *lo;
+    char *hi;
+  } stack_node;
+
+/* The next 4 #defines implement a very fast in-line stack abstraction. */
+/* The stack needs log (total_elements) entries (we could even subtract
+   log(MAX_THRESH)).  Since total_elements has type size_t, we get as
+   upper bound for log (total_elements):
+   bits per byte (CHAR_BIT) * sizeof(size_t).  */
+#define STACK_SIZE	(8 * sizeof(bfd_size_type))
+#define PUSH(low, high)	do { top->lo = (low); top->hi = (high); \
+				     ++top; } while (0)
+#define	POP(low, high)	do { --top; low = top->lo; \
+				     high = top->hi; } while (0)
+#define	STACK_NOT_EMPTY	(stack < top)
+
+
+/* Order size using quicksort.  This implementation incorporates
+   four optimizations discussed in Sedgewick:
+
+   1. Non-recursive, using an explicit stack of pointer that store the
+      next array partition to sort.  To save time, this maximum amount
+      of space required to store an array of SIZE_MAX is allocated on the
+      stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
+      only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
+      Pretty cheap, actually.
+
+   2. Chose the pivot element using a median-of-three decision tree.
+      This reduces the probability of selecting a bad pivot value and
+      eliminates certain extraneous comparisons.
+
+   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
+      insertion sort to order the MAX_THRESH items within each partition.
+      This is a big win, since insertion sort is faster for small, mostly
+      sorted array segments.
+
+   4. The larger of the two sub-partitions is always pushed onto the
+      stack first, with the algorithm then concentrating on the
+      smaller partition.  This *guarantees* no more than log (total_elems)
+      stack size is needed (actually O(1) in this case)!  */
+
+void
+bfd_qsort (void *pbase, bfd_size_type total_elems, bfd_size_type size,
+	   bfd_qsort_closure_func cmp, void *closure)
+{
+  register char *base_ptr = (char *) pbase;
+
+  const bfd_size_type max_thresh = MAX_THRESH * size;
+
+  if (total_elems == 0)
+    /* Avoid lossage with unsigned arithmetic below.  */
+    return;
+
+  if (total_elems > MAX_THRESH)
+    {
+      char *lo = base_ptr;
+      char *hi = &lo[size * (total_elems - 1)];
+      stack_node stack[STACK_SIZE];
+      stack_node *top = stack;
+
+      PUSH (NULL, NULL);
+
+      while (STACK_NOT_EMPTY)
+        {
+          char *left_ptr;
+          char *right_ptr;
+
+	  /* Select median value from among LO, MID, and HI. Rearrange
+	     LO and HI so the three values are sorted. This lowers the
+	     probability of picking a pathological pivot value and
+	     skips a comparison for both the LEFT_PTR and RIGHT_PTR in
+	     the while loops. */
+
+	  char *mid = lo + size * ((hi - lo) / size >> 1);
+
+	  if ((*cmp) ((void *) mid, (void *) lo, closure) < 0)
+	    SWAP (mid, lo, size);
+	  if ((*cmp) ((void *) hi, (void *) mid, closure) < 0)
+	    SWAP (mid, hi, size);
+	  else
+	    goto jump_over;
+	  if ((*cmp) ((void *) mid, (void *) lo, closure) < 0)
+	    SWAP (mid, lo, size);
+	jump_over:;
+
+	  left_ptr  = lo + size;
+	  right_ptr = hi - size;
+
+	  /* Here's the famous ``collapse the walls'' section of quicksort.
+	     Gotta like those tight inner loops!  They are the main reason
+	     that this algorithm runs much faster than others. */
+	  do
+	    {
+	      while ((*cmp) ((void *) left_ptr, (void *) mid, closure) < 0)
+		left_ptr += size;
+
+	      while ((*cmp) ((void *) mid, (void *) right_ptr, closure) < 0)
+		right_ptr -= size;
+
+	      if (left_ptr < right_ptr)
+		{
+		  SWAP (left_ptr, right_ptr, size);
+		  if (mid == left_ptr)
+		    mid = right_ptr;
+		  else if (mid == right_ptr)
+		    mid = left_ptr;
+		  left_ptr += size;
+		  right_ptr -= size;
+		}
+	      else if (left_ptr == right_ptr)
+		{
+		  left_ptr += size;
+		  right_ptr -= size;
+		  break;
+		}
+	    }
+	  while (left_ptr <= right_ptr);
+
+          /* Set up pointers for next iteration.  First determine whether
+             left and right partitions are below the threshold size.  If so,
+             ignore one or both.  Otherwise, push the larger partition's
+             bounds on the stack and continue sorting the smaller one. */
+
+          if ((bfd_size_type) (right_ptr - lo) <= max_thresh)
+            {
+              if ((bfd_size_type) (hi - left_ptr) <= max_thresh)
+		/* Ignore both small partitions. */
+                POP (lo, hi);
+              else
+		/* Ignore small left partition. */
+                lo = left_ptr;
+            }
+          else if ((bfd_size_type) (hi - left_ptr) <= max_thresh)
+	    /* Ignore small right partition. */
+            hi = right_ptr;
+          else if ((right_ptr - lo) > (hi - left_ptr))
+            {
+	      /* Push larger left partition indices. */
+              PUSH (lo, right_ptr);
+              lo = left_ptr;
+            }
+          else
+            {
+	      /* Push larger right partition indices. */
+              PUSH (left_ptr, hi);
+              hi = right_ptr;
+            }
+        }
+    }
+
+  /* Once the BASE_PTR array is partially sorted by quicksort the rest
+     is completely sorted using insertion sort, since this is efficient
+     for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+     of the array to sort, and END_PTR points at the very last element in
+     the array (*not* one beyond it!). */
+
+#define min(x, y) ((x) < (y) ? (x) : (y))
+
+  {
+    char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+    char *tmp_ptr = base_ptr;
+    char *thresh = min(end_ptr, base_ptr + max_thresh);
+    register char *run_ptr;
+
+    /* Find smallest element in first threshold and place it at the
+       array's beginning.  This is the smallest array element,
+       and the operation speeds up insertion sort's inner loop. */
+
+    for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
+      if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, closure) < 0)
+        tmp_ptr = run_ptr;
+
+    if (tmp_ptr != base_ptr)
+      SWAP (tmp_ptr, base_ptr, size);
+
+    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
+
+    run_ptr = base_ptr + size;
+    while ((run_ptr += size) <= end_ptr)
+      {
+	tmp_ptr = run_ptr - size;
+	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, closure) < 0)
+	  tmp_ptr -= size;
+
+	tmp_ptr += size;
+        if (tmp_ptr != run_ptr)
+          {
+            char *trav;
+
+	    trav = run_ptr + size;
+	    while (--trav >= run_ptr)
+              {
+                char c = *trav;
+                char *hi, *lo;
+
+                for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
+                  *hi = *lo;
+                *hi = c;
+              }
+          }
+      }
+  }
+}
diff -Naur binutils-2.17.50.0.2.old/bfd/elf-bfd.h binutils-2.17.50.0.2/bfd/elf-bfd.h
--- binutils-2.17.50.0.2.old/bfd/elf-bfd.h	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elf-bfd.h	2006-06-13 03:11:55.000000000 -0400
@@ -338,6 +338,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;
@@ -419,11 +423,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))
@@ -1470,6 +1479,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 **);
@@ -1487,6 +1498,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 *);
@@ -1618,7 +1630,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 -Naur binutils-2.17.50.0.2.old/bfd/elf-m10300.c binutils-2.17.50.0.2/bfd/elf-m10300.c
--- binutils-2.17.50.0.2.old/bfd/elf-m10300.c	2006-03-17 20:13:54.000000000 -0500
+++ binutils-2.17.50.0.2/bfd/elf-m10300.c	2006-06-13 03:11:55.000000000 -0400
@@ -3735,8 +3735,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 -Naur binutils-2.17.50.0.2.old/bfd/elf-strtab.c binutils-2.17.50.0.2/bfd/elf-strtab.c
--- binutils-2.17.50.0.2.old/bfd/elf-strtab.c	2006-03-17 20:13:54.000000000 -0500
+++ binutils-2.17.50.0.2/bfd/elf-strtab.c	2006-06-13 03:11:55.000000000 -0400
@@ -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.  */
@@ -118,6 +121,7 @@
     }
 
   table->array[0] = NULL;
+  table->array_sorted = NULL;
 
   return table;
 }
@@ -129,6 +133,8 @@
 {
   bfd_hash_table_free (&tab->table);
   free (tab->array);
+  if (tab->array_sorted)
+    free (tab->array_sorted);
   free (tab);
 }
 
@@ -230,6 +236,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;
@@ -239,12 +251,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;
 
@@ -279,6 +291,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)
@@ -294,9 +326,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;
@@ -362,15 +393,38 @@
 	}
     }
 
-alloc_failure:
-  if (array)
-    free (array);
+  if (bucket_count != 0)
+    {
+      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;
@@ -383,7 +437,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 -Naur binutils-2.17.50.0.2.old/bfd/elf.c binutils-2.17.50.0.2/bfd/elf.c
--- binutils-2.17.50.0.2.old/bfd/elf.c	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elf.c	2006-06-13 03:11:55.000000000 -0400
@@ -1588,6 +1588,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, entsize);
   table->root.type = bfd_link_elf_hash_table;
@@ -1617,6 +1619,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.  */
@@ -3049,7 +3060,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 -Naur binutils-2.17.50.0.2.old/bfd/elf32-hppa.c binutils-2.17.50.0.2/bfd/elf32-hppa.c
--- binutils-2.17.50.0.2.old/bfd/elf32-hppa.c	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elf32-hppa.c	2006-06-13 03:11:55.000000000 -0400
@@ -464,7 +464,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 (btab);
 }
 
 /* Build a name for an entry in the stub hash table.  */
diff -Naur binutils-2.17.50.0.2.old/bfd/elf32-m68hc1x.c binutils-2.17.50.0.2/bfd/elf32-m68hc1x.c
--- binutils-2.17.50.0.2.old/bfd/elf32-m68hc1x.c	2006-03-17 20:13:54.000000000 -0500
+++ binutils-2.17.50.0.2/bfd/elf32-m68hc1x.c	2006-06-13 03:11:55.000000000 -0400
@@ -108,7 +108,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 -Naur binutils-2.17.50.0.2.old/bfd/elf64-ppc.c binutils-2.17.50.0.2/bfd/elf64-ppc.c
--- binutils-2.17.50.0.2.old/bfd/elf64-ppc.c	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elf64-ppc.c	2006-06-13 03:11:55.000000000 -0400
@@ -3535,7 +3535,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 -Naur binutils-2.17.50.0.2.old/bfd/elflink.c binutils-2.17.50.0.2/bfd/elflink.c
--- binutils-2.17.50.0.2.old/bfd/elflink.c	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elflink.c	2006-06-13 03:11:55.000000000 -0400
@@ -2945,7 +2945,8 @@
   const struct elf_backend_data *bed;
   bfd_byte *extdyn;
 
-  _bfd_elf_strtab_finalize (dynstr);
+  _bfd_elf_strtab_finalize (dynstr, info->dynsort ?
+			    elf_hash_table (info)->bucketcount : 0);
   size = _bfd_elf_strtab_size (dynstr);
 
   bed = get_elf_backend_data (dynobj);
@@ -4745,27 +4746,15 @@
       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)
     {
@@ -4778,6 +4767,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;
 
@@ -4785,9 +4799,6 @@
      later.  */
   h->u.elf_hash_value = ha;
 
-  if (alc != NULL)
-    free (alc);
-
   return TRUE;
 }
 
@@ -4950,6 +4961,127 @@
   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;
+	}
+    }
+}
+
+/* Sort by elf hash value % buckets.  */
+static int
+elf_sort_dynsym_hash (const void *arg1, const void *arg2,
+		       const void *closure)
+{
+  size_t h1_bucket, h2_bucket;
+  const struct elf_link_hash_entry *h1;
+  const struct elf_link_hash_entry *h2;
+  const bfd_size_type *bucketcount;
+
+  h1 = *(const struct elf_link_hash_entry **) arg1;
+  h2 = *(const struct elf_link_hash_entry **) arg2;
+  bucketcount = closure;
+
+  h1_bucket = h1->u.elf_hash_value % *bucketcount;
+  h2_bucket = h2->u.elf_hash_value % *bucketcount;
+
+  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)
+{
+  bfd_size_type bucketcount;
+  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.  */
+  bucketcount = elf_hash_table (info)->bucketcount;
+  bfd_qsort (sinfo.sorted_syms, sinfo.sorted_size,
+	     sizeof (struct elf_link_hash_entry *),
+	     elf_sort_dynsym_hash,
+	     &bucketcount);
+
+  /* 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
@@ -5716,6 +5848,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);
@@ -5786,6 +5919,17 @@
       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.  */
+      if (info->dynsort)
+	{
+	  if (!_bfd_elf_sort_dynsyms (info))
+	    return FALSE;
+
+	  /* renumber to reflect the new sorting order.  */
+	  _bfd_elf_link_renumber_dynsyms (output_bfd, info,
+					&section_sym_count);
+	}
     }
 
   return TRUE;
@@ -5922,6 +6066,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];
 };
@@ -5958,6 +6103,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)
@@ -5976,8 +6125,10 @@
 }
 
 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;
@@ -5989,6 +6140,7 @@
   void (*swap_out) (bfd *, const Elf_Internal_Rela *, bfd_byte *);
   struct bfd_link_order *lo;
   bfd_vma r_sym_mask;
+  int r_sym_shift;
 
   reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");
   if (reldyn == NULL || reldyn->size == 0)
@@ -6030,15 +6182,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)
 	  {
@@ -6053,10 +6219,28 @@
 	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 (info->dynsort && base_offset >= 0
+		&& dyn_idx < base_max && dyn_idx >= base_offset)
+	      {
+	        struct elf_link_hash_entry *ent;
+	        ent = elf_hash_table (info)->sorted [dyn_idx - base_offset];
+	        s->elf_bucket = ent->u.elf_hash_value % bucketcount;
+	      }
+	    else
+	      s->elf_bucket = 0;
+				       
 	    p += sort_elt;
 	    erel += ext_size;
 	  }
@@ -8493,7 +8677,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 -Naur binutils-2.17.50.0.2.old/bfd/elfxx-target.h binutils-2.17.50.0.2/bfd/elfxx-target.h
--- binutils-2.17.50.0.2.old/bfd/elfxx-target.h	2006-05-26 12:34:05.000000000 -0400
+++ binutils-2.17.50.0.2/bfd/elfxx-target.h	2006-06-13 03:11:55.000000000 -0400
@@ -210,7 +210,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
diff -Naur binutils-2.17.50.0.2.old/include/bfdlink.h binutils-2.17.50.0.2/include/bfdlink.h
--- binutils-2.17.50.0.2.old/include/bfdlink.h	2006-04-29 12:32:58.000000000 -0400
+++ binutils-2.17.50.0.2/include/bfdlink.h	2006-06-13 03:11:55.000000000 -0400
@@ -324,6 +324,9 @@
   /* TRUE if unreferenced sections should be removed.  */
   unsigned int gc_sections: 1;
 
+  /* TRUE if dynsym/dynstr/relocs should be sorted.  */
+  unsigned int dynsort : 1;
+
   /* What to do with unresolved symbols in an object file.
      When producing executables the default is GENERATE_ERROR.
      When producing shared libraries the default is IGNORE.  The
diff -Naur binutils-2.17.50.0.2.old/ld/emultempl/elf32.em binutils-2.17.50.0.2/ld/emultempl/elf32.em
--- binutils-2.17.50.0.2.old/ld/emultempl/elf32.em	2006-04-29 12:32:58.000000000 -0400
+++ binutils-2.17.50.0.2/ld/emultempl/elf32.em	2006-06-13 03:16:15.000000000 -0400
@@ -1846,6 +1846,10 @@
 	link_info.relro = TRUE;
       else if (strcmp (optarg, "norelro") == 0)
 	link_info.relro = FALSE;
+      else if (strcmp (optarg, "dynsort") == 0)
+	link_info.dynsort = TRUE;
+      else if (strcmp (optarg, "nodynsort") == 0)
+	link_info.dynsort = FALSE;
       /* What about the other Solaris -z options? FIXME.  */
       break;
 EOF
@@ -1881,6 +1885,7 @@
   fprintf (file, _("  --eh-frame-hdr\tCreate .eh_frame_hdr section\n"));
   fprintf (file, _("  -z combreloc\t\tMerge dynamic relocs into one section and sort\n"));
   fprintf (file, _("  -z defs\t\tReport unresolved symbols in object files.\n"));
+  fprintf (file, _("  -z dynsort\t\tSort dynamic link sections\n"));
   fprintf (file, _("  -z execstack\t\tMark executable as requiring executable stack\n"));
   fprintf (file, _("  -z initfirst\t\tMark DSO to be initialized first at runtime\n"));
   fprintf (file, _("  -z interpose\t\tMark object to interpose all DSOs but executable\n"));
@@ -1892,6 +1897,7 @@
   fprintf (file, _("  -z nodelete\t\tMark DSO non-deletable at runtime\n"));
   fprintf (file, _("  -z nodlopen\t\tMark DSO not available to dlopen\n"));
   fprintf (file, _("  -z nodump\t\tMark DSO not available to dldump\n"));
+  fprintf (file, _("  -z nodynsort\t\tDon't sort dynamic link sections\n"));
   fprintf (file, _("  -z noexecstack\tMark executable as not requiring executable stack\n"));
   fprintf (file, _("  -z norelro\t\tDon't create RELRO program header\n"));
   fprintf (file, _("  -z now\t\tMark object non-lazy runtime binding\n"));
diff -Naur binutils-2.17.50.0.2.old/ld/ld.texinfo binutils-2.17.50.0.2/ld/ld.texinfo
--- binutils-2.17.50.0.2.old/ld/ld.texinfo	2006-05-26 12:34:07.000000000 -0400
+++ binutils-2.17.50.0.2/ld/ld.texinfo	2006-06-13 03:11:55.000000000 -0400
@@ -947,6 +947,9 @@
 Disallows undefined symbols in object files.  Undefined symbols in
 shared libraries are still allowed.
 
+@item dynsort
+Sorts dynamic link sections, to reduce cache misses during linking.
+
 @item execstack
 Marks the object as requiring executable stack.
 
@@ -988,6 +991,9 @@
 @item nodump
 Marks the object can not be dumped by @code{dldump}.
 
+@item nodynsort
+Disables dynamic link section sorting.
+
 @item noexecstack
 Marks the object as not requiring executable stack.
 
diff -Naur binutils-2.17.50.0.2.old/ld/ldmain.c binutils-2.17.50.0.2/ld/ldmain.c
--- binutils-2.17.50.0.2.old/ld/ldmain.c	2006-04-29 12:32:58.000000000 -0400
+++ binutils-2.17.50.0.2/ld/ldmain.c	2006-06-13 03:11:55.000000000 -0400
@@ -316,6 +316,7 @@
   link_info.relax_pass = 1;
   link_info.warn_shared_textrel = FALSE;
   link_info.gc_sections = FALSE;
+  link_info.dynsort = FALSE;
 
   ldfile_add_arch ("");