Attachment #78191 for bug #114008




/*
 * 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 (schmidt@ics.uci.edu).

   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 "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;
              }
          }
      }
  }
}

Lines 435-441 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf32-hppa.c (-1 / +1 lines)
435	= (struct elf32_hppa_link_hash_table *) btab;	435	= (struct elf32_hppa_link_hash_table *) btab;
436		436
437	bfd_hash_table_free (&htab->bstab);	437	bfd_hash_table_free (&htab->bstab);
438	_bfd_generic_link_hash_table_free (btab);	438	_bfd_elf_link_hash_table_free (hash);
439	}	439	}
440		440
441	/* Build a name for an entry in the stub hash table. */	441	/* Build a name for an entry in the stub hash table. */

Lines 106-112 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf32-m68hc1x.c (-1 / +1 lines)
106		106
107	bfd_hash_table_free (ret->stub_hash_table);	107	bfd_hash_table_free (ret->stub_hash_table);
108	free (ret->stub_hash_table);	108	free (ret->stub_hash_table);
109	_bfd_generic_link_hash_table_free (hash);	109	_bfd_elf_link_hash_table_free (hash);
110	}	110	}
111		111
112	/* Assorted hash table functions. */	112	/* Assorted hash table functions. */

Lines 3502-3508 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf64-ppc.c (-1 / +1 lines)
3502		3502
3503	bfd_hash_table_free (&ret->stub_hash_table);	3503	bfd_hash_table_free (&ret->stub_hash_table);
3504	bfd_hash_table_free (&ret->branch_hash_table);	3504	bfd_hash_table_free (&ret->branch_hash_table);
3505	_bfd_generic_link_hash_table_free (hash);	3505	_bfd_elf_link_hash_table_free (hash);
3506	}	3506	}
3507		3507
3508	/* Satisfy the ELF linker by filling in some fields in our fake bfd. */	3508	/* Satisfy the ELF linker by filling in some fields in our fake bfd. */

Lines 346-351 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf-bfd.h (-4 / +16 lines)
346	{	346	{
347	struct bfd_link_hash_table root;	347	struct bfd_link_hash_table root;
348		348
		349	/* Symbol sort order for final traversal at output */
		350	unsigned int sorted_size;
		351	struct elf_link_hash_entry **sorted;
		352
349	/* Whether we have created the special dynamic sections required	353	/* Whether we have created the special dynamic sections required
350	when linking against or generating a shared object. */	354	when linking against or generating a shared object. */
351	bfd_boolean dynamic_sections_created;	355	bfd_boolean dynamic_sections_created;
Lines 427-437 Link Here
427	/* Traverse an ELF linker hash table. */	431	/* Traverse an ELF linker hash table. */
428		432
429	#define elf_link_hash_traverse(table, func, info) \	433	#define elf_link_hash_traverse(table, func, info) \
430	(bfd_link_hash_traverse \	434	(_bfd_elf_link_hash_traverse \
431	(&(table)->root, \	435	((table), \
432	(bfd_boolean () (struct bfd_link_hash_entry , void *)) (func), \	436	(bfd_boolean () (struct elf_link_hash_entry , void *)) (func), \
433	(info)))	437	(info)))
434		438
		439	void _bfd_elf_link_hash_traverse
		440	(struct elf_link_hash_table *table,
		441	bfd_boolean (func) (struct elf_link_hash_entry , void *),
		442	void *info);
		443
435	/* Get the ELF linker hash table from a link_info structure. */	444	/* Get the ELF linker hash table from a link_info structure. */
436		445
437	#define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))	446	#define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))
Lines 1460-1465 Link Here
1460		1469
1461	extern unsigned long bfd_elf_hash	1470	extern unsigned long bfd_elf_hash
1462	(const char *);	1471	(const char *);
		1472	extern unsigned long _bfd_elf_ver_hash
		1473	(const char *);
1463		1474
1464	extern bfd_reloc_status_type bfd_elf_generic_reloc	1475	extern bfd_reloc_status_type bfd_elf_generic_reloc
1465	(bfd , arelent , asymbol , void , asection , bfd , char **);	1476	(bfd , arelent , asymbol , void , asection , bfd , char **);
Lines 1477-1482 Link Here
1477	(struct bfd_hash_entry , struct bfd_hash_table , const char *);	1488	(struct bfd_hash_entry , struct bfd_hash_table , const char *);
1478	extern struct bfd_link_hash_table *_bfd_elf_link_hash_table_create	1489	extern struct bfd_link_hash_table *_bfd_elf_link_hash_table_create
1479	(bfd *);	1490	(bfd *);
		1491	extern void _bfd_elf_link_hash_table_free (struct bfd_link_hash_table *);
1480	extern void _bfd_elf_link_hash_copy_indirect	1492	extern void _bfd_elf_link_hash_copy_indirect
1481	(struct bfd_link_info , struct elf_link_hash_entry ,	1493	(struct bfd_link_info , struct elf_link_hash_entry ,
1482	struct elf_link_hash_entry *);	1494	struct elf_link_hash_entry *);
Lines 1605-1611 Link Here
1605	extern bfd_boolean _bfd_elf_strtab_emit	1617	extern bfd_boolean _bfd_elf_strtab_emit
1606	(bfd , struct elf_strtab_hash );	1618	(bfd , struct elf_strtab_hash );
1607	extern void _bfd_elf_strtab_finalize	1619	extern void _bfd_elf_strtab_finalize
1608	(struct elf_strtab_hash *);	1620	(struct elf_strtab_hash *, size_t);
1609		1621
1610	extern bfd_boolean _bfd_elf_discard_section_eh_frame	1622	extern bfd_boolean _bfd_elf_discard_section_eh_frame
1611	(bfd , struct bfd_link_info , asection *,	1623	(bfd , struct bfd_link_info , asection *,

Lines 1579-1584 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf.c (-1 / +12 lines)
1579	table->direct_sec = NULL;	1579	table->direct_sec = NULL;
1580	table->loaded = NULL;	1580	table->loaded = NULL;
1581	table->is_relocatable_executable = FALSE;	1581	table->is_relocatable_executable = FALSE;
		1582	table->sorted = NULL;
		1583	table->sorted_size = 0;
1582		1584
1583	ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc);	1585	ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc);
1584	table->root.type = bfd_link_elf_hash_table;	1586	table->root.type = bfd_link_elf_hash_table;
Lines 1607-1612 Link Here
1607	return &ret->root;	1609	return &ret->root;
1608	}	1610	}
1609		1611
		1612	void
		1613	_bfd_elf_link_hash_table_free (struct bfd_link_hash_table *hash)
		1614	{
		1615	struct elf_link_hash_table table = (struct elf_link_hash_table ) hash;
		1616	if (table->sorted)
		1617	free (table->sorted);
		1618	_bfd_generic_link_hash_table_free (hash);
		1619	}
		1620
1610	/* This is a hook for the ELF emulation code in the generic linker to	1621	/* This is a hook for the ELF emulation code in the generic linker to
1611	tell the backend linker what file name to use for the DT_NEEDED	1622	tell the backend linker what file name to use for the DT_NEEDED
1612	entry for a dynamic object. */	1623	entry for a dynamic object. */
Lines 3005-3011 Link Here
3005	_bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);	3016	_bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);
3006	}	3017	}
3007		3018
3008	_bfd_elf_strtab_finalize (elf_shstrtab (abfd));	3019	_bfd_elf_strtab_finalize (elf_shstrtab (abfd), 0);
3009	t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));	3020	t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));
3010		3021
3011	elf_numsections (abfd) = section_number;	3022	elf_numsections (abfd) = section_number;




  const struct elf_backend_data *bed;
  bfd_byte *extdyn;

  _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);

      return FALSE;
    }
}

/* This function will be called though elf_link_hash_traverse to store
   all hash value of the exported symbols in an array.  */

/*
 * 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)
    {

  /* 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;


     later.  */
  h->u.elf_hash_value = ha;

  if (alc != NULL)
    free (alc);

  return TRUE;
}


  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;
}

 /* Nasty hack to avoid re-running autoconf / touching generated headers */

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);

#include "bfdsort.c"

/*
 * 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 them ... */
  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

	 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);

      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;

    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];
};

  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)

}

static size_t
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;

  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)

    }

  if (bed->s->arch_size == 32)
    {
      r_sym_mask = ~(bfd_vma) 0xff;
      r_sym_shift = 8;
    }
  else
    {
      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)
	  {

	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)
	      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;
	  }

    }

  if (dynamic && info->combreloc && dynobj != NULL)
    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.  */

Lines 3729-3736 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf-m10300.c (-2 / +1 lines)
3729		3729
3730	_bfd_generic_link_hash_table_free	3730	_bfd_generic_link_hash_table_free
3731	((struct bfd_link_hash_table *) ret->static_hash_table);	3731	((struct bfd_link_hash_table *) ret->static_hash_table);
3732	_bfd_generic_link_hash_table_free	3732	_bfd_elf_link_hash_table_free (hash);
3733	((struct bfd_link_hash_table *) ret);
3734	}	3733	}
3735		3734
3736	static unsigned long	3735	static unsigned long

Lines 39-44 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elf-strtab.c (-10 / +63 lines)
39	/* Entry this is a suffix of (if len < 0). */	39	/* Entry this is a suffix of (if len < 0). */
40	struct elf_strtab_hash_entry *suffix;	40	struct elf_strtab_hash_entry *suffix;
41	} u;	41	} u;
		42	long hash_bucket;
42	};	43	};
43		44
44	/* The strtab hash table. */	45	/* The strtab hash table. */
Lines 54-59 Link Here
54	bfd_size_type sec_size;	55	bfd_size_type sec_size;
55	/* Array of pointers to strtab entries. */	56	/* Array of pointers to strtab entries. */
56	struct elf_strtab_hash_entry **array;	57	struct elf_strtab_hash_entry **array;
		58	/* Array of pointers to strtab entries. */
		59	struct elf_strtab_hash_entry **array_sorted;
57	};	60	};
58		61
59	/* Routine to create an entry in a section merge hashtab. */	62	/* Routine to create an entry in a section merge hashtab. */
Lines 117-122 Link Here
117	}	120	}
118		121
119	table->array[0] = NULL;	122	table->array[0] = NULL;
		123	table->array_sorted = NULL;
120		124
121	return table;	125	return table;
122	}	126	}
Lines 128-133 Link Here
128	{	132	{
129	bfd_hash_table_free (&tab->table);	133	bfd_hash_table_free (&tab->table);
130	free (tab->array);	134	free (tab->array);
		135	if (tab->array_sorted)
		136	free (tab->array_sorted);
131	free (tab);	137	free (tab);
132	}	138	}
133		139
Lines 229-234 Link Here
229	_bfd_elf_strtab_emit (register bfd abfd, struct elf_strtab_hash tab)	235	_bfd_elf_strtab_emit (register bfd abfd, struct elf_strtab_hash tab)
230	{	236	{
231	bfd_size_type off = 1, i;	237	bfd_size_type off = 1, i;
		238	struct elf_strtab_hash_entry **array;
		239
		240	if (tab->array_sorted != NULL)
		241	array = tab->array_sorted;
		242	else
		243	array = tab->array;
232		244
233	if (bfd_bwrite ("", 1, abfd) != 1)	245	if (bfd_bwrite ("", 1, abfd) != 1)
234	return FALSE;	246	return FALSE;
Lines 238-249 Link Here
238	register const char *str;	250	register const char *str;
239	register unsigned int len;	251	register unsigned int len;
240		252
241	BFD_ASSERT (tab->array[i]->refcount == 0);	253	BFD_ASSERT (array[i]->refcount == 0);
242	len = tab->array[i]->len;	254	len = array[i]->len;
243	if ((int) len < 0)	255	if ((int) len < 0)
244	continue;	256	continue;
245		257
246	str = tab->array[i]->root.string;	258	str = array[i]->root.string;
247	if (bfd_bwrite (str, len, abfd) != len)	259	if (bfd_bwrite (str, len, abfd) != len)
248	return FALSE;	260	return FALSE;
249		261
Lines 278-283 Link Here
278	return lenA - lenB;	290	return lenA - lenB;
279	}	291	}
280		292
		293	/* sort by hash bucket position */
		294	static int
		295	hash_compare (const void a, const void b)
		296	{
		297	struct elf_strtab_hash_entry A = (struct elf_strtab_hash_entry **) a;
		298	struct elf_strtab_hash_entry B = (struct elf_strtab_hash_entry **) b;
		299
		300	if (A->hash_bucket > B->hash_bucket)
		301	return 1;
		302	if (A->hash_bucket < B->hash_bucket)
		303	return -1;
		304
		305	/* Make qsort faster for lots of identical empty symbols */
		306	if (a > b)
		307	return 1;
		308	if (a < b)
		309	return -1;
		310	return 0;
		311	}
		312
281	static inline int	313	static inline int
282	is_suffix (const struct elf_strtab_hash_entry *A,	314	is_suffix (const struct elf_strtab_hash_entry *A,
283	const struct elf_strtab_hash_entry *B)	315	const struct elf_strtab_hash_entry *B)
Lines 293-301 Link Here
293		325
294	/* This function assigns final string table offsets for used strings,	326	/* This function assigns final string table offsets for used strings,
295	merging strings matching suffixes of longer strings if possible. */	327	merging strings matching suffixes of longer strings if possible. */
296
297	void	328	void
298	_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)	329	_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab, size_t bucket_count)
299	{	330	{
300	struct elf_strtab_hash_entry array, a, *e;	331	struct elf_strtab_hash_entry array, a, *e;
301	bfd_size_type size, amt;	332	bfd_size_type size, amt;
Lines 361-375 Link Here
361	}	392	}
362	}	393	}
363		394
364	alloc_failure:	395	if (bucket_count != 0)
365	if (array)	396	{
366	free (array);	397	array[0] = NULL;
		398	for (i = 1; i < tab->size; ++i)
		399	{
		400	e = tab->array[i];
		401	array[i] = e;
		402
		403	if (e->len > 0)
		404	{
		405	e->hash_bucket = _bfd_elf_ver_hash (e->root.string);
		406	e->hash_bucket %= bucket_count;
		407	}
		408	else
		409	e->hash_bucket = 0;
		410	}
		411	qsort (array + 1, tab->size - 1, sizeof (struct elf_strtab_hash_entry *), hash_compare);
		412	tab->array_sorted = array;
		413	}
		414	else
		415	{
		416	free (array);
		417	alloc_failure:
		418	array = tab->array;
		419	}
367		420
368	/* Assign positions to the strings we want to keep. */	421	/* Assign positions to the strings we want to keep. */
369	size = 1;	422	size = 1;
370	for (i = 1; i < tab->size; ++i)	423	for (i = 1; i < tab->size; ++i)
371	{	424	{
372	e = tab->array[i];	425	e = array[i];
373	if (e->refcount && e->len > 0)	426	if (e->refcount && e->len > 0)
374	{	427	{
375	e->u.index = size;	428	e->u.index = size;
Lines 382-388 Link Here
382	/* Adjust the rest. */	435	/* Adjust the rest. */
383	for (i = 1; i < tab->size; ++i)	436	for (i = 1; i < tab->size; ++i)
384	{	437	{
385	e = tab->array[i];	438	e = array[i];
386	if (e->refcount && e->len < 0)	439	if (e->refcount && e->len < 0)
387	e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);	440	e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
388	}	441	}

Lines 205-211 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elfxx-target.h (-1 / +1 lines)
205	#endif	205	#endif
206		206
207	#ifndef bfd_elfNN_bfd_link_hash_table_free	207	#ifndef bfd_elfNN_bfd_link_hash_table_free
208	#define bfd_elfNN_bfd_link_hash_table_free _bfd_generic_link_hash_table_free	208	#define bfd_elfNN_bfd_link_hash_table_free _bfd_elf_link_hash_table_free
209	#endif	209	#endif
210		210
211	#ifdef elf_backend_relocate_section	211	#ifdef elf_backend_relocate_section

Lines 342-347 Link Here

(-)binutils-2.16.91.0.5.orig/include/bfdlink.h (+3 lines)
342	/* TRUE if unreferenced sections should be removed. */	342	/* TRUE if unreferenced sections should be removed. */
343	unsigned int gc_sections: 1;	343	unsigned int gc_sections: 1;
344		344
		345	/* TRUE if dynsym/dynstr/relocs should be sorted */
		346	unsigned int dynsort : 1;
		347
345	/* What to do with unresolved symbols in an object file.	348	/* What to do with unresolved symbols in an object file.
346	When producing executables the default is GENERATE_ERROR.	349	When producing executables the default is GENERATE_ERROR.
347	When producing shared libraries the default is IGNORE. The	350	When producing shared libraries the default is IGNORE. The

Lines 1782-1787 Link Here

(-)binutils-2.16.91.0.5.orig/ld/emultempl/elf32.em (+6 lines)
1782	link_info.relro = TRUE;	1782	link_info.relro = TRUE;
1783	else if (strcmp (optarg, "norelro") == 0)	1783	else if (strcmp (optarg, "norelro") == 0)
1784	link_info.relro = FALSE;	1784	link_info.relro = FALSE;
		1785	else if (strcmp (optarg, "dynsort") == 0)
		1786	link_info.dynsort = TRUE;
		1787	else if (strcmp (optarg, "nodynsort") == 0)
		1788	link_info.dynsort = FALSE;
1785	/* What about the other Solaris -z options? FIXME. */	1789	/* What about the other Solaris -z options? FIXME. */
1786	break;	1790	break;
1787	EOF	1791	EOF
Lines 1817-1822 Link Here
1817	fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n"));	1821	fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n"));
1818	fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n"));	1822	fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n"));
1819	fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n"));	1823	fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n"));
		1824	fprintf (file, _(" -z dynsort\t\tSort dynamic link sections\n"));
1820	fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n"));	1825	fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n"));
1821	fprintf (file, _(" -z execheap\t\tMark executable as requiring executable heap\n"));	1826	fprintf (file, _(" -z execheap\t\tMark executable as requiring executable heap\n"));
1822	fprintf (file, _(" -z initfirst\t\tMark DSO to be initialized first at runtime\n"));	1827	fprintf (file, _(" -z initfirst\t\tMark DSO to be initialized first at runtime\n"));
Lines 1829-1834 Link Here
1829	fprintf (file, _(" -z nodelete\t\tMark DSO non-deletable at runtime\n"));	1834	fprintf (file, _(" -z nodelete\t\tMark DSO non-deletable at runtime\n"));
1830	fprintf (file, _(" -z nodlopen\t\tMark DSO not available to dlopen\n"));	1835	fprintf (file, _(" -z nodlopen\t\tMark DSO not available to dlopen\n"));
1831	fprintf (file, _(" -z nodump\t\tMark DSO not available to dldump\n"));	1836	fprintf (file, _(" -z nodump\t\tMark DSO not available to dldump\n"));
		1837	fprintf (file, _(" -z nodynsort\t\tDon't sort dynamic link sections\n"));
1832	fprintf (file, _(" -z noexecstack\tMark executable as not requiring executable stack\n"));	1838	fprintf (file, _(" -z noexecstack\tMark executable as not requiring executable stack\n"));
1833	fprintf (file, _(" -z noexecheap\tMark executable as not requiring executable heap\n"));	1839	fprintf (file, _(" -z noexecheap\tMark executable as not requiring executable heap\n"));
1834	fprintf (file, _(" -z norelro\t\tDon't create RELRO program header\n"));	1840	fprintf (file, _(" -z norelro\t\tDon't create RELRO program header\n"));

Lines 316-321 Link Here

(-)binutils-2.16.91.0.5.orig/ld/ldmain.c (+1 lines)
316	link_info.need_relax_finalize = FALSE;	316	link_info.need_relax_finalize = FALSE;
317	link_info.warn_shared_textrel = TRUE;	317	link_info.warn_shared_textrel = TRUE;
318	link_info.gc_sections = FALSE;	318	link_info.gc_sections = FALSE;
		319	link_info.dynsort = FALSE;
319		320
320	ldfile_add_arch ("");	321	ldfile_add_arch ("");
321		322

Lines 933-938 Link Here

(-)binutils-2.16.91.0.5.orig/ld/ld.texinfo (+6 lines)
933	Disallows undefined symbols in object files. Undefined symbols in	933	Disallows undefined symbols in object files. Undefined symbols in
934	shared libraries are still allowed.	934	shared libraries are still allowed.
935		935
		936	@item dynsort
		937	Sorts dynamic link sections, to reduce cache misses during linking.
		938
936	@item execstack	939	@item execstack
937	Marks the object as requiring executable stack.	940	Marks the object as requiring executable stack.
938		941
Lines 974-979 Link Here
974	@item nodump	977	@item nodump
975	Marks the object can not be dumped by @code{dldump}.	978	Marks the object can not be dumped by @code{dldump}.
976		979
		980	@item nodynsort
		981	Disables dynamic link section sorting.
		982
977	@item noexecstack	983	@item noexecstack
978	Marks the object as not requiring executable stack.	984	Marks the object as not requiring executable stack.
979		985

Return to bug 114008

Line 0 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/bfdsort.c (+252 lines)
		1	/*
		2	* This module copied from glibc/stdlib/qsort.c & adapted,
		3	* in order to add support for a closure argument.
		4	*/
		5
		6	/* Copyright (C) 1991,1992,1996,1997,1999,2004 Free Software Foundation, Inc.
		7	This file is part of the GNU C Library.
		8	Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
		9
		10	The GNU C Library is free software; you can redistribute it and/or
		11	modify it under the terms of the GNU Lesser General Public
		12	License as published by the Free Software Foundation; either
		13	version 2.1 of the License, or (at your option) any later version.
		14
		15	The GNU C Library is distributed in the hope that it will be useful,
		16	but WITHOUT ANY WARRANTY; without even the implied warranty of
		17	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
		18	Lesser General Public License for more details.
		19
		20	You should have received a copy of the GNU Lesser General Public
		21	License along with the GNU C Library; if not, write to the Free
		22	Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
		23	02111-1307 USA. */
		24
		25	/* If you consider tuning this algorithm, you should consult first:
		26	Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
		27	Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
		28
		29	#include "sysdep.h"
		30
		31	/* Byte-wise swap two items of size SIZE. */
		32	#define SWAP(a, b, size) \
		33	do \
		34	{ \
		35	register bfd_size_type __size = (size); \
		36	register char __a = (a), __b = (b); \
		37	do \
		38	{ \
		39	char __tmp = *__a; \
		40	__a++ = __b; \
		41	*__b++ = __tmp; \
		42	} while (--__size > 0); \
		43	} while (0)
		44
		45	/* Discontinue quicksort algorithm when partition gets below this size.
		46	This particular magic number was chosen to work best on a Sun 4/260. */
		47	#define MAX_THRESH 4
		48
		49	/* Stack node declarations used to store unfulfilled partition obligations. */
		50	typedef struct
		51	{
		52	char *lo;
		53	char *hi;
		54	} stack_node;
		55
		56	/* The next 4 #defines implement a very fast in-line stack abstraction. */
		57	/* The stack needs log (total_elements) entries (we could even subtract
		58	log(MAX_THRESH)). Since total_elements has type size_t, we get as
		59	upper bound for log (total_elements):
		60	bits per byte (CHAR_BIT) * sizeof(size_t). */
		61	#define STACK_SIZE (8 * sizeof(bfd_size_type))
		62	#define PUSH(low, high) do { top->lo = (low); top->hi = (high); ++top; } while (0)
		63	#define POP(low, high) do { --top; low = top->lo; high = top->hi; } while (0)
		64	#define STACK_NOT_EMPTY (stack < top)
65
66
67	/* Order size using quicksort. This implementation incorporates
68	four optimizations discussed in Sedgewick:
69
70	1. Non-recursive, using an explicit stack of pointer that store the
71	next array partition to sort. To save time, this maximum amount
72	of space required to store an array of SIZE_MAX is allocated on the
73	stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
74	only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
75	Pretty cheap, actually.
76
77	2. Chose the pivot element using a median-of-three decision tree.
78	This reduces the probability of selecting a bad pivot value and
79	eliminates certain extraneous comparisons.
80
81	3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
82	insertion sort to order the MAX_THRESH items within each partition.
83	This is a big win, since insertion sort is faster for small, mostly
84	sorted array segments.
85
86	4. The larger of the two sub-partitions is always pushed onto the
87	stack first, with the algorithm then concentrating on the
88	smaller partition. This guarantees no more than log (total_elems)
89	stack size is needed (actually O(1) in this case)! */
90
91	void
92	bfd_qsort (void *pbase, bfd_size_type total_elems, bfd_size_type size,
93	bfd_qsort_closure_func cmp, void *closure)
94	{
95	register char base_ptr = (char ) pbase;
96
97	const bfd_size_type max_thresh = MAX_THRESH * size;
98
99	if (total_elems == 0)
100	/* Avoid lossage with unsigned arithmetic below. */
101	return;
102
103	if (total_elems > MAX_THRESH)
104	{
105	char *lo = base_ptr;
106	char hi = &lo[size (total_elems - 1)];
107	stack_node stack[STACK_SIZE];
108	stack_node *top = stack;
109
110	PUSH (NULL, NULL);
111
112	while (STACK_NOT_EMPTY)
113	{
114	char *left_ptr;
115	char *right_ptr;
116
117	/* Select median value from among LO, MID, and HI. Rearrange
118	LO and HI so the three values are sorted. This lowers the
119	probability of picking a pathological pivot value and
120	skips a comparison for both the LEFT_PTR and RIGHT_PTR in
121	the while loops. */
122
123	char mid = lo + size ((hi - lo) / size >> 1);
124
125	if ((cmp) ((void ) mid, (void *) lo, closure) < 0)
126	SWAP (mid, lo, size);
127	if ((cmp) ((void ) hi, (void *) mid, closure) < 0)
128	SWAP (mid, hi, size);
129	else
130	goto jump_over;
131	if ((cmp) ((void ) mid, (void *) lo, closure) < 0)
132	SWAP (mid, lo, size);
133	jump_over:;
134
135	left_ptr = lo + size;
136	right_ptr = hi - size;
137
138	/* Here's the famous ``collapse the walls'' section of quicksort.
139	Gotta like those tight inner loops! They are the main reason
140	that this algorithm runs much faster than others. */
141	do
142	{
143	while ((cmp) ((void ) left_ptr, (void *) mid, closure) < 0)
144	left_ptr += size;
145
146	while ((cmp) ((void ) mid, (void *) right_ptr, closure) < 0)
147	right_ptr -= size;
148
149	if (left_ptr < right_ptr)
150	{
151	SWAP (left_ptr, right_ptr, size);
152	if (mid == left_ptr)
153	mid = right_ptr;
154	else if (mid == right_ptr)
155	mid = left_ptr;
156	left_ptr += size;
157	right_ptr -= size;
158	}
159	else if (left_ptr == right_ptr)
160	{
161	left_ptr += size;
162	right_ptr -= size;
163	break;
164	}
165	}
166	while (left_ptr <= right_ptr);
167
168	/* Set up pointers for next iteration. First determine whether
169	left and right partitions are below the threshold size. If so,
170	ignore one or both. Otherwise, push the larger partition's
171	bounds on the stack and continue sorting the smaller one. */
172
173	if ((bfd_size_type) (right_ptr - lo) <= max_thresh)
174	{
175	if ((bfd_size_type) (hi - left_ptr) <= max_thresh)
176	/* Ignore both small partitions. */
177	POP (lo, hi);
178	else
179	/* Ignore small left partition. */
180	lo = left_ptr;
181	}
182	else if ((bfd_size_type) (hi - left_ptr) <= max_thresh)
183	/* Ignore small right partition. */
184	hi = right_ptr;
185	else if ((right_ptr - lo) > (hi - left_ptr))
186	{
187	/* Push larger left partition indices. */
188	PUSH (lo, right_ptr);
189	lo = left_ptr;
190	}
191	else
192	{
193	/* Push larger right partition indices. */
194	PUSH (left_ptr, hi);
195	hi = right_ptr;
196	}
197	}
198	}
199
200	/* Once the BASE_PTR array is partially sorted by quicksort the rest
201	is completely sorted using insertion sort, since this is efficient
202	for partitions below MAX_THRESH size. BASE_PTR points to the beginning
203	of the array to sort, and END_PTR points at the very last element in
204	the array (not one beyond it!). */
205
206	#define min(x, y) ((x) < (y) ? (x) : (y))
207
208	{
209	char const end_ptr = &base_ptr[size (total_elems - 1)];
210	char *tmp_ptr = base_ptr;
211	char *thresh = min(end_ptr, base_ptr + max_thresh);
212	register char *run_ptr;
213
214	/* Find smallest element in first threshold and place it at the
215	array's beginning. This is the smallest array element,
216	and the operation speeds up insertion sort's inner loop. */
217
218	for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
219	if ((cmp) ((void ) run_ptr, (void *) tmp_ptr, closure) < 0)
220	tmp_ptr = run_ptr;
221
222	if (tmp_ptr != base_ptr)
223	SWAP (tmp_ptr, base_ptr, size);
224
225	/* Insertion sort, running from left-hand-side up to right-hand-side. */
226
227	run_ptr = base_ptr + size;
228	while ((run_ptr += size) <= end_ptr)
229	{
230	tmp_ptr = run_ptr - size;
231	while ((cmp) ((void ) run_ptr, (void *) tmp_ptr, closure) < 0)
232	tmp_ptr -= size;
233
234	tmp_ptr += size;
235	if (tmp_ptr != run_ptr)
236	{
237	char *trav;
238
239	trav = run_ptr + size;
240	while (--trav >= run_ptr)
241	{
242	char c = *trav;
243	char hi, lo;
244
245	for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
246	hi = lo;
247	*hi = c;
248	}
249	}
250	}
251	}
252	}

Lines 3021-3027 Link Here

(-)binutils-2.16.91.0.5.orig/bfd/elflink.c (-23 / +208 lines)
3021	const struct elf_backend_data *bed;	3021	const struct elf_backend_data *bed;
3022	bfd_byte *extdyn;	3022	bfd_byte *extdyn;
3023		3023
3024	_bfd_elf_strtab_finalize (dynstr);	3024	_bfd_elf_strtab_finalize (dynstr, info->dynsort ?
		3025	elf_hash_table (info)->bucketcount : 0);
3025	size = _bfd_elf_strtab_size (dynstr);	3026	size = _bfd_elf_strtab_size (dynstr);
3026		3027
3027	bed = get_elf_backend_data (dynobj);	3028	bed = get_elf_backend_data (dynobj);
Lines 4777-4803 Link Here
4777	return FALSE;	4778	return FALSE;
4778	}	4779	}
4779	}	4780	}
4780
4781	/* This function will be called though elf_link_hash_traverse to store
4782	all hash value of the exported symbols in an array. */
4783		4781
4784	static bfd_boolean	4782	/*
4785	elf_collect_hash_codes (struct elf_link_hash_entry h, void data)	4783	* Compute the elf hash value of the name ignoring the version.
		4784	*/
		4785	unsigned long
		4786	_bfd_elf_ver_hash (const char *name)
4786	{	4787	{
4787	unsigned long **valuep = data;
4788	const char *name;
4789	char *p;	4788	char *p;
4790	unsigned long ha;	4789	unsigned long ha;
4791	char *alc = NULL;	4790	char *alc = NULL;
4792		4791
4793	if (h->root.type == bfd_link_hash_warning)
4794	h = (struct elf_link_hash_entry *) h->root.u.i.link;
4795
4796	/* Ignore indirect symbols. These are added by the versioning code. */
4797	if (h->dynindx == -1)
4798	return TRUE;
4799
4800	name = h->root.root.string;
4801	p = strchr (name, ELF_VER_CHR);	4792	p = strchr (name, ELF_VER_CHR);
4802	if (p != NULL)	4793	if (p != NULL)
4803	{	4794	{
Lines 4810-4815 Link Here
4810	/* Compute the hash value. */	4801	/* Compute the hash value. */
4811	ha = bfd_elf_hash (name);	4802	ha = bfd_elf_hash (name);
4812		4803
		4804	if (alc != NULL)
		4805	free (alc);
		4806
		4807	return ha;
		4808	}
		4809
		4810
		4811	/* This function will be called though elf_link_hash_traverse to store
		4812	all hash value of the exported symbols in an array. */
		4813
		4814	static bfd_boolean
		4815	elf_collect_hash_codes (struct elf_link_hash_entry h, void data)
		4816	{
		4817	unsigned long **valuep = data;
		4818	unsigned long ha;
		4819
		4820	if (h->root.type == bfd_link_hash_warning)
		4821	h = (struct elf_link_hash_entry *) h->root.u.i.link;
		4822
		4823	/* Ignore indirect symbols. These are added by the versioning code. */
		4824	if (h->dynindx == -1)
		4825	return TRUE;
		4826
		4827	ha = _bfd_elf_ver_hash (h->root.root.string);
		4828
4813	/* Store the found hash value in the array given as the argument. */	4829	/* Store the found hash value in the array given as the argument. */
4814	(valuep)++ = ha;	4830	(valuep)++ = ha;
4815		4831
Lines 4817-4825 Link Here
4817	later. */	4833	later. */
4818	h->u.elf_hash_value = ha;	4834	h->u.elf_hash_value = ha;
4819		4835
4820	if (alc != NULL)
4821	free (alc);
4822
4823	return TRUE;	4836	return TRUE;
4824	}	4837	}
4825		4838
Lines 4982-4987 Link Here
4982	return best_size;	4995	return best_size;
4983	}	4996	}
4984		4997
		4998	void _bfd_elf_link_hash_traverse
		4999	(struct elf_link_hash_table *table,
		5000	bfd_boolean (func) (struct elf_link_hash_entry , void *),
		5001	void *info)
		5002	{
		5003	if (!table->sorted)
		5004	bfd_link_hash_traverse \
		5005	(&(table)->root, \
		5006	(bfd_boolean () (struct bfd_link_hash_entry , void *)) (func), \
		5007	(info));
		5008	else
		5009	{
		5010	unsigned int i;
		5011	for (i = 0; i < table->sorted_size; i++)
		5012	{
		5013	if (! func (table->sorted[i], info))
		5014	return;
		5015	}
		5016	}
		5017	}
		5018
		5019	/* Sort by elf hash value % buckets */
		5020	static int
		5021	elf_sort_dynsym_hash (const void arg1, const void arg2, const void *closure)
		5022	{
		5023	size_t h1_bucket, h2_bucket;
		5024	const struct elf_link_hash_entry *h1;
		5025	const struct elf_link_hash_entry *h2;
		5026	const bfd_size_type *bucketcount;
		5027
		5028	h1 = (const struct elf_link_hash_entry *) arg1;
		5029	h2 = (const struct elf_link_hash_entry *) arg2;
		5030	bucketcount = closure;
		5031
		5032	h1_bucket = h1->u.elf_hash_value % *bucketcount;
		5033	h2_bucket = h2->u.elf_hash_value % *bucketcount;
		5034
		5035	if (h1_bucket > h2_bucket)
		5036	return 1;
		5037	if (h1_bucket < h2_bucket)
		5038	return -1;
		5039
		5040	return 0;
		5041	}
		5042
		5043	struct elf_dynsym_sort_info
		5044	{
		5045	bfd_boolean do_dynsym;
		5046	unsigned int alloc_size;
		5047	unsigned int sorted_size;
		5048	struct elf_link_hash_entry **sorted_syms;
		5049	};
		5050
		5051	/* collect sym entries into an array for later sorting */
		5052	static bfd_boolean
		5053	elf_sort_collect_dynsyms (struct elf_link_hash_entry h, void data)
		5054	{
		5055	struct elf_dynsym_sort_info *sinfo = data;
		5056
		5057	if ((sinfo->do_dynsym && h->dynindx < 0) \|\|
		5058	(!sinfo->do_dynsym && h->dynindx >= 0))
		5059	return TRUE;
		5060
		5061	if (sinfo->sorted_size >= sinfo->alloc_size)
5062	{
5063	sinfo->alloc_size *= 2;
5064	/* FIXME: need to free this data too ... */
5065	sinfo->sorted_syms = bfd_realloc (sinfo->sorted_syms,
5066	sizeof (struct elf_link_hash_entry )
5067	sinfo->alloc_size);
5068	}
5069	sinfo->sorted_syms [sinfo->sorted_size++] = h;
5070
5071	return TRUE;
5072	}
5073
5074	/* Nasty hack to avoid re-running autoconf / touching generated headers */
5075
5076	typedef int(bfd_qsort_closure_func)(const void , const void , const void );
5077	extern void bfd_qsort (void *base, bfd_size_type nmemb, bfd_size_type size,
5078	bfd_qsort_closure_func cmp, void *closure);
5079
5080	#include "bfdsort.c"
5081
5082	/*
5083	* Sort the exported elf symbols by elf_hash % bucketcount to
5084	* improve run-time linker cache behavior. Subsequent
5085	* elf_link_hash_traverse calls will reflect this new order.
5086	*/
5087	static bfd_boolean
5088	_bfd_elf_sort_dynsyms (struct bfd_link_info *info)
5089	{
5090	bfd_size_type bucketcount;
5091	struct elf_dynsym_sort_info sinfo;
5092
5093	sinfo.alloc_size = 8;
5094	sinfo.sorted_syms = bfd_malloc (sizeof (struct elf_link_hash_entry )
5095	sinfo.alloc_size);
5096	if (!sinfo.sorted_syms)
5097	return FALSE;
5098
5099	sinfo.sorted_size = 0;
5100
5101	/* append dynsyms for sorting */
5102	sinfo.do_dynsym = TRUE;
5103	elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
5104
5105	/* sort them ... */
5106	bucketcount = elf_hash_table (info)->bucketcount;
5107	bfd_qsort (sinfo.sorted_syms, sinfo.sorted_size,
5108	sizeof (struct elf_link_hash_entry *),
5109	elf_sort_dynsym_hash,
5110	&bucketcount);
5111
5112	/* append everything else */
5113	sinfo.do_dynsym = FALSE;
5114	elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
5115
5116	/* freed in _bfd_elf_link_hash_table_free */
5117	elf_hash_table (info)->sorted = sinfo.sorted_syms;
5118	elf_hash_table (info)->sorted_size = sinfo.sorted_size;
5119
5120	return TRUE;
5121	}
5122
4985	/* Set up the sizes and contents of the ELF dynamic sections. This is	5123	/* Set up the sizes and contents of the ELF dynamic sections. This is
4986	called by the ELF linker emulation before_allocation routine. We	5124	called by the ELF linker emulation before_allocation routine. We
4987	must set the sizes of the sections before the linker sets the	5125	must set the sizes of the sections before the linker sets the
Lines 5766-5771 Link Here
5766	section symbol for each output section, which come first.	5904	section symbol for each output section, which come first.
5767	Next come all of the back-end allocated local dynamic syms,	5905	Next come all of the back-end allocated local dynamic syms,
5768	followed by the rest of the global symbols. */	5906	followed by the rest of the global symbols. */
		5907	/* To sort these optimally we need the correct bucketcount */
5769		5908
5770	dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,	5909	dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,
5771	&section_sym_count);	5910	&section_sym_count);
Lines 5872-5877 Link Here
5872	for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)	6011	for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)
5873	if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))	6012	if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))
5874	return FALSE;	6013	return FALSE;
		6014
		6015	/* Sort .dynsym to accelerate runtime linking */
		6016	if (info->dynsort)
		6017	{
		6018	if (!_bfd_elf_sort_dynsyms (info))
		6019	return FALSE;
		6020
		6021	/* renumber to reflect the new sorting order */
		6022	_bfd_elf_link_renumber_dynsyms (output_bfd, info,
		6023	&section_sym_count);
		6024	}
5875	}	6025	}
5876		6026
5877	return TRUE;	6027	return TRUE;
Lines 6012-6017 Link Here
6012	bfd_vma sym_mask;	6162	bfd_vma sym_mask;
6013	} u;	6163	} u;
6014	enum elf_reloc_type_class type;	6164	enum elf_reloc_type_class type;
		6165	unsigned long elf_bucket;
6015	/* We use this as an array of size int_rels_per_ext_rel. */	6166	/* We use this as an array of size int_rels_per_ext_rel. */
6016	Elf_Internal_Rela rela[1];	6167	Elf_Internal_Rela rela[1];
6017	};	6168	};
Lines 6048-6053 Link Here
6048	const struct elf_link_sort_rela *b = B;	6199	const struct elf_link_sort_rela *b = B;
6049	int copya, copyb;	6200	int copya, copyb;
6050		6201
		6202	if (a->elf_bucket < b->elf_bucket)
		6203	return -1;
		6204	if (a->elf_bucket > b->elf_bucket)
		6205	return 1;
6051	if (a->u.offset < b->u.offset)	6206	if (a->u.offset < b->u.offset)
6052	return -1;	6207	return -1;
6053	if (a->u.offset > b->u.offset)	6208	if (a->u.offset > b->u.offset)
Lines 6066-6073 Link Here
6066	}	6221	}
6067		6222
6068	static size_t	6223	static size_t
6069	elf_link_sort_relocs (bfd abfd, struct bfd_link_info info, asection **psec)	6224	elf_link_sort_relocs (bfd abfd, struct elf_final_link_info finfo, asection **psec)
6070	{	6225	{
		6226	struct bfd_link_info *info = finfo->info;
6071	asection *reldyn;	6227	asection *reldyn;
6072	bfd_size_type count, size;	6228	bfd_size_type count, size;
6073	size_t i, ret, sort_elt, ext_size;	6229	size_t i, ret, sort_elt, ext_size;
Lines 6079-6084 Link Here
6079	void (swap_out) (bfd , const Elf_Internal_Rela , bfd_byte );	6235	void (swap_out) (bfd , const Elf_Internal_Rela , bfd_byte );
6080	struct bfd_link_order *lo;	6236	struct bfd_link_order *lo;
6081	bfd_vma r_sym_mask;	6237	bfd_vma r_sym_mask;
		6238	int r_sym_shift;
6082		6239
6083	reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");	6240	reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");
6084	if (reldyn == NULL \|\| reldyn->size == 0)	6241	if (reldyn == NULL \|\| reldyn->size == 0)
Lines 6120-6134 Link Here
6120	}	6277	}
6121		6278
6122	if (bed->s->arch_size == 32)	6279	if (bed->s->arch_size == 32)
6123	r_sym_mask = ~(bfd_vma) 0xff;	6280	{
		6281	r_sym_mask = ~(bfd_vma) 0xff;
		6282	r_sym_shift = 8;
		6283	}
6124	else	6284	else
6125	r_sym_mask = ~(bfd_vma) 0xffffffff;	6285	{
		6286	r_sym_mask = ~(bfd_vma) 0xffffffff;
		6287	r_sym_shift = 32;
		6288	}
6126		6289
6127	for (lo = reldyn->map_head.link_order; lo != NULL; lo = lo->next)	6290	for (lo = reldyn->map_head.link_order; lo != NULL; lo = lo->next)
6128	if (lo->type == bfd_indirect_link_order)	6291	if (lo->type == bfd_indirect_link_order)
6129	{	6292	{
6130	bfd_byte erel, erelend;	6293	bfd_byte erel, erelend;
6131	asection *o = lo->u.indirect.section;	6294	asection *o = lo->u.indirect.section;
		6295	int base_offset = -1;
		6296	int base_max = 0;
		6297
		6298	if (elf_hash_table (info)->sorted_size > 0)
		6299	{
		6300	base_offset = elf_hash_table (info)->sorted[0]->dynindx;
		6301	base_max = base_offset + elf_hash_table (info)->sorted_size;
		6302	}
6132		6303
6133	if (o->contents == NULL && o->size != 0)	6304	if (o->contents == NULL && o->size != 0)
6134	{	6305	{
Lines 6143-6152 Link Here
6143	p = sort + o->output_offset / ext_size * sort_elt;	6314	p = sort + o->output_offset / ext_size * sort_elt;
6144	while (erel < erelend)	6315	while (erel < erelend)
6145	{	6316	{
		6317	long dyn_idx;
		6318	size_t bucketcount = elf_hash_table (info)->bucketcount;
6146	struct elf_link_sort_rela s = (struct elf_link_sort_rela ) p;	6319	struct elf_link_sort_rela s = (struct elf_link_sort_rela ) p;
6147	(*swap_in) (abfd, erel, s->rela);	6320	(*swap_in) (abfd, erel, s->rela);
6148	s->type = (*bed->elf_backend_reloc_type_class) (s->rela);	6321	s->type = (*bed->elf_backend_reloc_type_class) (s->rela);
6149	s->u.sym_mask = r_sym_mask;	6322	s->u.sym_mask = r_sym_mask;
		6323
		6324	if (s->type != reloc_class_relative)
		6325	dyn_idx = s->rela->r_info >> r_sym_shift;
		6326	else
		6327	dyn_idx = -1;
		6328
		6329	if (info->dynsort && base_offset >= 0 &&
		6330	dyn_idx < base_max && dyn_idx >= base_offset)
		6331	s->elf_bucket = elf_hash_table (info)->sorted [dyn_idx - base_offset]->u.elf_hash_value % bucketcount;
		6332	else
		6333	s->elf_bucket = 0;
		6334
6150	p += sort_elt;	6335	p += sort_elt;
6151	erel += ext_size;	6336	erel += ext_size;
6152	}	6337	}
Lines 8612-8618 Link Here
8612	}	8797	}
8613		8798
8614	if (dynamic && info->combreloc && dynobj != NULL)	8799	if (dynamic && info->combreloc && dynobj != NULL)
8615	relativecount = elf_link_sort_relocs (abfd, info, &reldyn);	8800	relativecount = elf_link_sort_relocs (abfd, &finfo, &reldyn);
8616		8801
8617	/* If we are linking against a dynamic object, or generating a	8802	/* If we are linking against a dynamic object, or generating a
8618	shared library, finish up the dynamic linking information. */	8803	shared library, finish up the dynamic linking information. */