Attachment #89027 for bug #114008

Lines 36-42 Link Here

(-)binutils-2.17.50.0.2.old/bfd/Makefile.am (-2 / +2 lines)
36	# need two copies of the executable, one to download and one for the	36	# need two copies of the executable, one to download and one for the
37	# debugger).	37	# debugger).
38	BFD32_LIBS = \	38	BFD32_LIBS = \
39	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo \	39	archive.lo archures.lo bfd.lo bfdio.lo bfdsort.lo bfdwin.lo \
40	cache.lo coffgen.lo corefile.lo \	40	cache.lo coffgen.lo corefile.lo \
41	format.lo init.lo libbfd.lo opncls.lo reloc.lo \	41	format.lo init.lo libbfd.lo opncls.lo reloc.lo \
42	section.lo syms.lo targets.lo hash.lo linker.lo \	42	section.lo syms.lo targets.lo hash.lo linker.lo \
Lines 46-52 Link Here
46	BFD64_LIBS = archive64.lo	46	BFD64_LIBS = archive64.lo
47		47
48	BFD32_LIBS_CFILES = \	48	BFD32_LIBS_CFILES = \
49	archive.c archures.c bfd.c bfdio.c bfdwin.c \	49	archive.c archures.c bfd.c bfdio.c bfdsort.c bfdwin.c \
50	cache.c coffgen.c corefile.c \	50	cache.c coffgen.c corefile.c \
51	format.c init.c libbfd.c opncls.c reloc.c \	51	format.c init.c libbfd.c opncls.c reloc.c \
52	section.c syms.c targets.c hash.c linker.c \	52	section.c syms.c targets.c hash.c linker.c \




	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 bfdsort.lo
am__objects_2 = archive64.lo
am_libbfd_la_OBJECTS = $(am__objects_1) $(am__objects_2)
libbfd_la_OBJECTS = $(am_libbfd_la_OBJECTS)

# 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 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 \


BFD64_LIBS = archive64.lo
BFD32_LIBS_CFILES = \
	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 \

Lines 162-167 Link Here

(-)binutils-2.17.50.0.2.old/bfd/bfd-in.h (+4 lines)
162		162
163	typedef unsigned int flagword; /* 32 bits of flags */	163	typedef unsigned int flagword; /* 32 bits of flags */
164	typedef unsigned char bfd_byte;	164	typedef unsigned char bfd_byte;
		165
		166	typedef int (bfd_qsort_closure_func) (const void , const void , const void );
		167	extern void bfd_qsort (void *base, bfd_size_type nmemb, bfd_size_type size,
		168	bfd_qsort_closure_func cmp, void *closure);
165		169
166	/* File formats. */	170	/* File formats. */
167		171




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

Lines 338-343 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elf-bfd.h (-4 / +16 lines)
338	{	338	{
339	struct bfd_link_hash_table root;	339	struct bfd_link_hash_table root;
340		340
		341	/* Symbol sort order for final traversal at output. */
		342	unsigned int sorted_size;
		343	struct elf_link_hash_entry **sorted;
		344
341	/* Whether we have created the special dynamic sections required	345	/* Whether we have created the special dynamic sections required
342	when linking against or generating a shared object. */	346	when linking against or generating a shared object. */
343	bfd_boolean dynamic_sections_created;	347	bfd_boolean dynamic_sections_created;
Lines 419-429 Link Here
419	/* Traverse an ELF linker hash table. */	423	/* Traverse an ELF linker hash table. */
420		424
421	#define elf_link_hash_traverse(table, func, info) \	425	#define elf_link_hash_traverse(table, func, info) \
422	(bfd_link_hash_traverse \	426	(_bfd_elf_link_hash_traverse \
423	(&(table)->root, \	427	((table), \
424	(bfd_boolean () (struct bfd_link_hash_entry , void *)) (func), \	428	(bfd_boolean () (struct elf_link_hash_entry , void *)) (func), \
425	(info)))	429	(info)))
426		430
		431	void _bfd_elf_link_hash_traverse
		432	(struct elf_link_hash_table *table,
		433	bfd_boolean (func) (struct elf_link_hash_entry , void *),
		434	void *info);
		435
427	/* Get the ELF linker hash table from a link_info structure. */	436	/* Get the ELF linker hash table from a link_info structure. */
428		437
429	#define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))	438	#define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))
Lines 1470-1475 Link Here
1470		1479
1471	extern unsigned long bfd_elf_hash	1480	extern unsigned long bfd_elf_hash
1472	(const char *);	1481	(const char *);
		1482	extern unsigned long _bfd_elf_ver_hash
		1483	(const char *);
1473		1484
1474	extern bfd_reloc_status_type bfd_elf_generic_reloc	1485	extern bfd_reloc_status_type bfd_elf_generic_reloc
1475	(bfd , arelent , asymbol , void , asection , bfd , char **);	1486	(bfd , arelent , asymbol , void , asection , bfd , char **);
Lines 1487-1492 Link Here
1487	(struct bfd_hash_entry , struct bfd_hash_table , const char *);	1498	(struct bfd_hash_entry , struct bfd_hash_table , const char *);
1488	extern struct bfd_link_hash_table *_bfd_elf_link_hash_table_create	1499	extern struct bfd_link_hash_table *_bfd_elf_link_hash_table_create
1489	(bfd *);	1500	(bfd *);
		1501	extern void _bfd_elf_link_hash_table_free (struct bfd_link_hash_table *);
1490	extern void _bfd_elf_link_hash_copy_indirect	1502	extern void _bfd_elf_link_hash_copy_indirect
1491	(struct bfd_link_info , struct elf_link_hash_entry ,	1503	(struct bfd_link_info , struct elf_link_hash_entry ,
1492	struct elf_link_hash_entry *);	1504	struct elf_link_hash_entry *);
Lines 1618-1624 Link Here
1618	extern bfd_boolean _bfd_elf_strtab_emit	1630	extern bfd_boolean _bfd_elf_strtab_emit
1619	(bfd , struct elf_strtab_hash );	1631	(bfd , struct elf_strtab_hash );
1620	extern void _bfd_elf_strtab_finalize	1632	extern void _bfd_elf_strtab_finalize
1621	(struct elf_strtab_hash *);	1633	(struct elf_strtab_hash *, size_t);
1622		1634
1623	extern bfd_boolean _bfd_elf_discard_section_eh_frame	1635	extern bfd_boolean _bfd_elf_discard_section_eh_frame
1624	(bfd , struct bfd_link_info , asection *,	1636	(bfd , struct bfd_link_info , asection *,

Lines 3735-3742 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elf-m10300.c (-2 / +1 lines)
3735		3735
3736	_bfd_generic_link_hash_table_free	3736	_bfd_generic_link_hash_table_free
3737	((struct bfd_link_hash_table *) ret->static_hash_table);	3737	((struct bfd_link_hash_table *) ret->static_hash_table);
3738	_bfd_generic_link_hash_table_free	3738	_bfd_elf_link_hash_table_free (hash);
3739	((struct bfd_link_hash_table *) ret);
3740	}	3739	}
3741		3740
3742	static unsigned long	3741	static unsigned long

Lines 39-44 Link Here

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

Lines 1588-1593 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elf.c (-1 / +12 lines)
1588	table->tls_size = 0;	1588	table->tls_size = 0;
1589	table->loaded = NULL;	1589	table->loaded = NULL;
1590	table->is_relocatable_executable = FALSE;	1590	table->is_relocatable_executable = FALSE;
		1591	table->sorted = NULL;
		1592	table->sorted_size = 0;
1591		1593
1592	ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc, entsize);	1594	ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc, entsize);
1593	table->root.type = bfd_link_elf_hash_table;	1595	table->root.type = bfd_link_elf_hash_table;
Lines 1617-1622 Link Here
1617	return &ret->root;	1619	return &ret->root;
1618	}	1620	}
1619		1621
		1622	void
		1623	_bfd_elf_link_hash_table_free (struct bfd_link_hash_table *hash)
		1624	{
		1625	struct elf_link_hash_table table = (struct elf_link_hash_table ) hash;
		1626	if (table->sorted)
		1627	free (table->sorted);
		1628	_bfd_generic_link_hash_table_free (hash);
		1629	}
		1630
1620	/* This is a hook for the ELF emulation code in the generic linker to	1631	/* This is a hook for the ELF emulation code in the generic linker to
1621	tell the backend linker what file name to use for the DT_NEEDED	1632	tell the backend linker what file name to use for the DT_NEEDED
1622	entry for a dynamic object. */	1633	entry for a dynamic object. */
Lines 3049-3055 Link Here
3049	_bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);	3060	_bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);
3050	}	3061	}
3051		3062
3052	_bfd_elf_strtab_finalize (elf_shstrtab (abfd));	3063	_bfd_elf_strtab_finalize (elf_shstrtab (abfd), 0);
3053	t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));	3064	t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));
3054		3065
3055	elf_numsections (abfd) = section_number;	3066	elf_numsections (abfd) = section_number;

Lines 464-470 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elf32-hppa.c (-1 / +1 lines)
464	= (struct elf32_hppa_link_hash_table *) btab;	464	= (struct elf32_hppa_link_hash_table *) btab;
465		465
466	bfd_hash_table_free (&htab->bstab);	466	bfd_hash_table_free (&htab->bstab);
467	_bfd_generic_link_hash_table_free (btab);	467	_bfd_elf_link_hash_table_free (btab);
468	}	468	}
469		469
470	/* Build a name for an entry in the stub hash table. */	470	/* Build a name for an entry in the stub hash table. */

Lines 108-114 Link Here

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

Lines 3535-3541 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elf64-ppc.c (-1 / +1 lines)
3535		3535
3536	bfd_hash_table_free (&ret->stub_hash_table);	3536	bfd_hash_table_free (&ret->stub_hash_table);
3537	bfd_hash_table_free (&ret->branch_hash_table);	3537	bfd_hash_table_free (&ret->branch_hash_table);
3538	_bfd_generic_link_hash_table_free (hash);	3538	_bfd_elf_link_hash_table_free (hash);
3539	}	3539	}
3540		3540
3541	/* Satisfy the ELF linker by filling in some fields in our fake bfd. */	3541	/* Satisfy the ELF linker by filling in some fields in our fake bfd. */




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

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

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

    }

  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 210-216 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elfxx-target.h (-1 / +1 lines)
210	#endif	210	#endif
211		211
212	#ifndef bfd_elfNN_bfd_link_hash_table_free	212	#ifndef bfd_elfNN_bfd_link_hash_table_free
213	#define bfd_elfNN_bfd_link_hash_table_free _bfd_generic_link_hash_table_free	213	#define bfd_elfNN_bfd_link_hash_table_free _bfd_elf_link_hash_table_free
214	#endif	214	#endif
215		215
216	#ifdef elf_backend_relocate_section	216	#ifdef elf_backend_relocate_section

Lines 324-329 Link Here

(-)binutils-2.17.50.0.2.old/include/bfdlink.h (+3 lines)
324	/* TRUE if unreferenced sections should be removed. */	324	/* TRUE if unreferenced sections should be removed. */
325	unsigned int gc_sections: 1;	325	unsigned int gc_sections: 1;
326		326
		327	/* TRUE if dynsym/dynstr/relocs should be sorted. */
		328	unsigned int dynsort : 1;
		329
327	/* What to do with unresolved symbols in an object file.	330	/* What to do with unresolved symbols in an object file.
328	When producing executables the default is GENERATE_ERROR.	331	When producing executables the default is GENERATE_ERROR.
329	When producing shared libraries the default is IGNORE. The	332	When producing shared libraries the default is IGNORE. The

Lines 1846-1851 Link Here

(-)binutils-2.17.50.0.2.old/ld/emultempl/elf32.em (+6 lines)
1846	link_info.relro = TRUE;	1846	link_info.relro = TRUE;
1847	else if (strcmp (optarg, "norelro") == 0)	1847	else if (strcmp (optarg, "norelro") == 0)
1848	link_info.relro = FALSE;	1848	link_info.relro = FALSE;
		1849	else if (strcmp (optarg, "dynsort") == 0)
		1850	link_info.dynsort = TRUE;
		1851	else if (strcmp (optarg, "nodynsort") == 0)
		1852	link_info.dynsort = FALSE;
1849	/* What about the other Solaris -z options? FIXME. */	1853	/* What about the other Solaris -z options? FIXME. */
1850	break;	1854	break;
1851	EOF	1855	EOF
Lines 1881-1886 Link Here
1881	fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n"));	1885	fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n"));
1882	fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n"));	1886	fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n"));
1883	fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n"));	1887	fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n"));
		1888	fprintf (file, _(" -z dynsort\t\tSort dynamic link sections\n"));
1884	fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n"));	1889	fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n"));
1885	fprintf (file, _(" -z initfirst\t\tMark DSO to be initialized first at runtime\n"));	1890	fprintf (file, _(" -z initfirst\t\tMark DSO to be initialized first at runtime\n"));
1886	fprintf (file, _(" -z interpose\t\tMark object to interpose all DSOs but executable\n"));	1891	fprintf (file, _(" -z interpose\t\tMark object to interpose all DSOs but executable\n"));
Lines 1892-1897 Link Here
1892	fprintf (file, _(" -z nodelete\t\tMark DSO non-deletable at runtime\n"));	1897	fprintf (file, _(" -z nodelete\t\tMark DSO non-deletable at runtime\n"));
1893	fprintf (file, _(" -z nodlopen\t\tMark DSO not available to dlopen\n"));	1898	fprintf (file, _(" -z nodlopen\t\tMark DSO not available to dlopen\n"));
1894	fprintf (file, _(" -z nodump\t\tMark DSO not available to dldump\n"));	1899	fprintf (file, _(" -z nodump\t\tMark DSO not available to dldump\n"));
		1900	fprintf (file, _(" -z nodynsort\t\tDon't sort dynamic link sections\n"));
1895	fprintf (file, _(" -z noexecstack\tMark executable as not requiring executable stack\n"));	1901	fprintf (file, _(" -z noexecstack\tMark executable as not requiring executable stack\n"));
1896	fprintf (file, _(" -z norelro\t\tDon't create RELRO program header\n"));	1902	fprintf (file, _(" -z norelro\t\tDon't create RELRO program header\n"));
1897	fprintf (file, _(" -z now\t\tMark object non-lazy runtime binding\n"));	1903	fprintf (file, _(" -z now\t\tMark object non-lazy runtime binding\n"));

Lines 947-952 Link Here

(-)binutils-2.17.50.0.2.old/ld/ld.texinfo (+6 lines)
947	Disallows undefined symbols in object files. Undefined symbols in	947	Disallows undefined symbols in object files. Undefined symbols in
948	shared libraries are still allowed.	948	shared libraries are still allowed.
949		949
		950	@item dynsort
		951	Sorts dynamic link sections, to reduce cache misses during linking.
		952
950	@item execstack	953	@item execstack
951	Marks the object as requiring executable stack.	954	Marks the object as requiring executable stack.
952		955
Lines 988-993 Link Here
988	@item nodump	991	@item nodump
989	Marks the object can not be dumped by @code{dldump}.	992	Marks the object can not be dumped by @code{dldump}.
990		993
		994	@item nodynsort
		995	Disables dynamic link section sorting.
		996
991	@item noexecstack	997	@item noexecstack
992	Marks the object as not requiring executable stack.	998	Marks the object as not requiring executable stack.
993		999

Lines 316-321 Link Here

(-)binutils-2.17.50.0.2.old/ld/ldmain.c (+1 lines)
316	link_info.relax_pass = 1;	316	link_info.relax_pass = 1;
317	link_info.warn_shared_textrel = FALSE;	317	link_info.warn_shared_textrel = FALSE;
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

Return to bug 114008

Lines 79-85 Link Here

(-)binutils-2.17.50.0.2.old/bfd/Makefile.in (-3 / +3 lines)
79	cache.lo coffgen.lo corefile.lo format.lo init.lo libbfd.lo \	79	cache.lo coffgen.lo corefile.lo format.lo init.lo libbfd.lo \
80	opncls.lo reloc.lo section.lo syms.lo targets.lo hash.lo \	80	opncls.lo reloc.lo section.lo syms.lo targets.lo hash.lo \
81	linker.lo srec.lo binary.lo tekhex.lo ihex.lo stabs.lo \	81	linker.lo srec.lo binary.lo tekhex.lo ihex.lo stabs.lo \
82	stab-syms.lo merge.lo dwarf2.lo simple.lo	82	stab-syms.lo merge.lo dwarf2.lo simple.lo bfdsort.lo
83	am__objects_2 = archive64.lo	83	am__objects_2 = archive64.lo
84	am_libbfd_la_OBJECTS = $(am__objects_1) $(am__objects_2)	84	am_libbfd_la_OBJECTS = $(am__objects_1) $(am__objects_2)
85	libbfd_la_OBJECTS = $(am_libbfd_la_OBJECTS)	85	libbfd_la_OBJECTS = $(am_libbfd_la_OBJECTS)
Lines 273-279 Link Here
273	# need two copies of the executable, one to download and one for the	273	# need two copies of the executable, one to download and one for the
274	# debugger).	274	# debugger).
275	BFD32_LIBS = \	275	BFD32_LIBS = \
276	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo \	276	archive.lo archures.lo bfd.lo bfdio.lo bfdwin.lo bfdsort.lo \
277	cache.lo coffgen.lo corefile.lo \	277	cache.lo coffgen.lo corefile.lo \
278	format.lo init.lo libbfd.lo opncls.lo reloc.lo \	278	format.lo init.lo libbfd.lo opncls.lo reloc.lo \
279	section.lo syms.lo targets.lo hash.lo linker.lo \	279	section.lo syms.lo targets.lo hash.lo linker.lo \
Lines 282-288 Link Here
282		282
283	BFD64_LIBS = archive64.lo	283	BFD64_LIBS = archive64.lo
284	BFD32_LIBS_CFILES = \	284	BFD32_LIBS_CFILES = \
285	archive.c archures.c bfd.c bfdio.c bfdwin.c \	285	archive.c archures.c bfd.c bfdio.c bfdwin.c bfdsort.lo \
286	cache.c coffgen.c corefile.c \	286	cache.c coffgen.c corefile.c \
287	format.c init.c libbfd.c opncls.c reloc.c \	287	format.c init.c libbfd.c opncls.c reloc.c \
288	section.c syms.c targets.c hash.c linker.c \	288	section.c syms.c targets.c hash.c linker.c \

Line 0 Link Here

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

Lines 2945-2951 Link Here

(-)binutils-2.17.50.0.2.old/bfd/elflink.c (-23 / +207 lines)
2945	const struct elf_backend_data *bed;	2945	const struct elf_backend_data *bed;
2946	bfd_byte *extdyn;	2946	bfd_byte *extdyn;
2947		2947
2948	_bfd_elf_strtab_finalize (dynstr);	2948	_bfd_elf_strtab_finalize (dynstr, info->dynsort ?
		2949	elf_hash_table (info)->bucketcount : 0);
2949	size = _bfd_elf_strtab_size (dynstr);	2950	size = _bfd_elf_strtab_size (dynstr);
2950		2951
2951	bed = get_elf_backend_data (dynobj);	2952	bed = get_elf_backend_data (dynobj);
Lines 4745-4771 Link Here
4745	return FALSE;	4746	return FALSE;
4746	}	4747	}
4747	}	4748	}
4748
4749	/* This function will be called though elf_link_hash_traverse to store
4750	all hash value of the exported symbols in an array. */
4751		4749
4752	static bfd_boolean	4750	/* Compute the elf hash value of the name ignoring the version. */
4753	elf_collect_hash_codes (struct elf_link_hash_entry h, void data)	4751	unsigned long
		4752	_bfd_elf_ver_hash (const char *name)
4754	{	4753	{
4755	unsigned long **valuep = data;
4756	const char *name;
4757	char *p;	4754	char *p;
4758	unsigned long ha;	4755	unsigned long ha;
4759	char *alc = NULL;	4756	char *alc = NULL;
4760		4757
4761	if (h->root.type == bfd_link_hash_warning)
4762	h = (struct elf_link_hash_entry *) h->root.u.i.link;
4763
4764	/* Ignore indirect symbols. These are added by the versioning code. */
4765	if (h->dynindx == -1)
4766	return TRUE;
4767
4768	name = h->root.root.string;
4769	p = strchr (name, ELF_VER_CHR);	4758	p = strchr (name, ELF_VER_CHR);
4770	if (p != NULL)	4759	if (p != NULL)
4771	{	4760	{
Lines 4778-4783 Link Here
4778	/* Compute the hash value. */	4767	/* Compute the hash value. */
4779	ha = bfd_elf_hash (name);	4768	ha = bfd_elf_hash (name);
4780		4769
		4770	if (alc != NULL)
		4771	free (alc);
		4772
		4773	return ha;
		4774	}
		4775
		4776
		4777	/* This function will be called though elf_link_hash_traverse to store
		4778	all hash value of the exported symbols in an array. */
		4779
		4780	static bfd_boolean
		4781	elf_collect_hash_codes (struct elf_link_hash_entry h, void data)
		4782	{
		4783	unsigned long **valuep = data;
		4784	unsigned long ha;
		4785
		4786	if (h->root.type == bfd_link_hash_warning)
		4787	h = (struct elf_link_hash_entry *) h->root.u.i.link;
		4788
		4789	/* Ignore indirect symbols. These are added by the versioning code. */
		4790	if (h->dynindx == -1)
		4791	return TRUE;
		4792
		4793	ha = _bfd_elf_ver_hash (h->root.root.string);
		4794
4781	/* Store the found hash value in the array given as the argument. */	4795	/* Store the found hash value in the array given as the argument. */
4782	(valuep)++ = ha;	4796	(valuep)++ = ha;
4783		4797
Lines 4785-4793 Link Here
4785	later. */	4799	later. */
4786	h->u.elf_hash_value = ha;	4800	h->u.elf_hash_value = ha;
4787		4801
4788	if (alc != NULL)
4789	free (alc);
4790
4791	return TRUE;	4802	return TRUE;
4792	}	4803	}
4793		4804
Lines 4950-4955 Link Here
4950	return best_size;	4961	return best_size;
4951	}	4962	}
4952		4963
		4964	void _bfd_elf_link_hash_traverse
		4965	(struct elf_link_hash_table *table,
		4966	bfd_boolean (func) (struct elf_link_hash_entry , void *),
		4967	void *info)
		4968	{
		4969	if (!table->sorted)
		4970	bfd_link_hash_traverse
		4971	(&(table)->root,
		4972	(bfd_boolean () (struct bfd_link_hash_entry , void *)) (func),
		4973	(info));
		4974	else
		4975	{
		4976	unsigned int i;
		4977	for (i = 0; i < table->sorted_size; i++)
		4978	{
		4979	if (! func (table->sorted[i], info))
		4980	return;
		4981	}
		4982	}
		4983	}
		4984
		4985	/* Sort by elf hash value % buckets. */
		4986	static int
		4987	elf_sort_dynsym_hash (const void arg1, const void arg2,
		4988	const void *closure)
		4989	{
		4990	size_t h1_bucket, h2_bucket;
		4991	const struct elf_link_hash_entry *h1;
		4992	const struct elf_link_hash_entry *h2;
		4993	const bfd_size_type *bucketcount;
		4994
		4995	h1 = (const struct elf_link_hash_entry *) arg1;
		4996	h2 = (const struct elf_link_hash_entry *) arg2;
		4997	bucketcount = closure;
		4998
		4999	h1_bucket = h1->u.elf_hash_value % *bucketcount;
		5000	h2_bucket = h2->u.elf_hash_value % *bucketcount;
		5001
		5002	if (h1_bucket > h2_bucket)
		5003	return 1;
		5004	if (h1_bucket < h2_bucket)
		5005	return -1;
		5006
		5007	return 0;
		5008	}
		5009
		5010	struct elf_dynsym_sort_info
		5011	{
		5012	bfd_boolean do_dynsym;
		5013	unsigned int alloc_size;
		5014	unsigned int sorted_size;
		5015	struct elf_link_hash_entry **sorted_syms;
		5016	};
		5017
		5018	/* collect sym entries into an array for later sorting. */
		5019	static bfd_boolean
		5020	elf_sort_collect_dynsyms (struct elf_link_hash_entry h, void data)
		5021	{
		5022	struct elf_dynsym_sort_info *sinfo = data;
		5023
		5024	if ((sinfo->do_dynsym && h->dynindx < 0)
		5025	\|\| (!sinfo->do_dynsym && h->dynindx >= 0))
		5026	return TRUE;
		5027
5028	if (sinfo->sorted_size >= sinfo->alloc_size)
5029	{
5030	sinfo->alloc_size *= 2;
5031	/* FIXME: need to free this data too ... */
5032	sinfo->sorted_syms = bfd_realloc
5033	(sinfo->sorted_syms,
5034	sizeof (struct elf_link_hash_entry )
5035	sinfo->alloc_size);
5036	}
5037	sinfo->sorted_syms [sinfo->sorted_size++] = h;
5038
5039	return TRUE;
5040	}
5041
5042	/*
5043	* Sort the exported elf symbols by elf_hash % bucketcount to
5044	* improve run-time linker cache behavior. Subsequent
5045	* elf_link_hash_traverse calls will reflect this new order.
5046	*/
5047	static bfd_boolean
5048	_bfd_elf_sort_dynsyms (struct bfd_link_info *info)
5049	{
5050	bfd_size_type bucketcount;
5051	struct elf_dynsym_sort_info sinfo;
5052
5053	sinfo.alloc_size = 8;
5054	sinfo.sorted_syms = bfd_malloc (sizeof (struct elf_link_hash_entry )
5055	sinfo.alloc_size);
5056	if (!sinfo.sorted_syms)
5057	return FALSE;
5058
5059	sinfo.sorted_size = 0;
5060
5061	/* append dynsyms for sorting. */
5062	sinfo.do_dynsym = TRUE;
5063	elf_link_hash_traverse (elf_hash_table (info),
5064	elf_sort_collect_dynsyms, &sinfo);
5065
5066	/* sort. */
5067	bucketcount = elf_hash_table (info)->bucketcount;
5068	bfd_qsort (sinfo.sorted_syms, sinfo.sorted_size,
5069	sizeof (struct elf_link_hash_entry *),
5070	elf_sort_dynsym_hash,
5071	&bucketcount);
5072
5073	/* append everything else. */
5074	sinfo.do_dynsym = FALSE;
5075	elf_link_hash_traverse (elf_hash_table (info),
5076	elf_sort_collect_dynsyms, &sinfo);
5077
5078	/* freed in _bfd_elf_link_hash_table_free. */
5079	elf_hash_table (info)->sorted = sinfo.sorted_syms;
5080	elf_hash_table (info)->sorted_size = sinfo.sorted_size;
5081
5082	return TRUE;
5083	}
5084
4953	/* Set up the sizes and contents of the ELF dynamic sections. This is	5085	/* Set up the sizes and contents of the ELF dynamic sections. This is
4954	called by the ELF linker emulation before_allocation routine. We	5086	called by the ELF linker emulation before_allocation routine. We
4955	must set the sizes of the sections before the linker sets the	5087	must set the sizes of the sections before the linker sets the
Lines 5716-5721 Link Here
5716	section symbol for each output section, which come first.	5848	section symbol for each output section, which come first.
5717	Next come all of the back-end allocated local dynamic syms,	5849	Next come all of the back-end allocated local dynamic syms,
5718	followed by the rest of the global symbols. */	5850	followed by the rest of the global symbols. */
		5851	/* To sort these optimally we need the correct bucketcount. */
5719		5852
5720	dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,	5853	dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,
5721	&section_sym_count);	5854	&section_sym_count);
Lines 5786-5791 Link Here
5786	for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)	5919	for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)
5787	if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))	5920	if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))
5788	return FALSE;	5921	return FALSE;
		5922
		5923	/* Sort .dynsym to accelerate runtime linking. */
		5924	if (info->dynsort)
		5925	{
		5926	if (!_bfd_elf_sort_dynsyms (info))
		5927	return FALSE;
		5928
		5929	/* renumber to reflect the new sorting order. */
		5930	_bfd_elf_link_renumber_dynsyms (output_bfd, info,
		5931	&section_sym_count);
		5932	}
5789	}	5933	}
5790		5934
5791	return TRUE;	5935	return TRUE;
Lines 5922-5927 Link Here
5922	bfd_vma sym_mask;	6066	bfd_vma sym_mask;
5923	} u;	6067	} u;
5924	enum elf_reloc_type_class type;	6068	enum elf_reloc_type_class type;
		6069	unsigned long elf_bucket;
5925	/* We use this as an array of size int_rels_per_ext_rel. */	6070	/* We use this as an array of size int_rels_per_ext_rel. */
5926	Elf_Internal_Rela rela[1];	6071	Elf_Internal_Rela rela[1];
5927	};	6072	};
Lines 5958-5963 Link Here
5958	const struct elf_link_sort_rela *b = B;	6103	const struct elf_link_sort_rela *b = B;
5959	int copya, copyb;	6104	int copya, copyb;
5960		6105
		6106	if (a->elf_bucket < b->elf_bucket)
		6107	return -1;
		6108	if (a->elf_bucket > b->elf_bucket)
		6109	return 1;
5961	if (a->u.offset < b->u.offset)	6110	if (a->u.offset < b->u.offset)
5962	return -1;	6111	return -1;
5963	if (a->u.offset > b->u.offset)	6112	if (a->u.offset > b->u.offset)
Lines 5976-5983 Link Here
5976	}	6125	}
5977		6126
5978	static size_t	6127	static size_t
5979	elf_link_sort_relocs (bfd abfd, struct bfd_link_info info, asection **psec)	6128	elf_link_sort_relocs (bfd abfd, struct elf_final_link_info finfo,
		6129	asection **psec)
5980	{	6130	{
		6131	struct bfd_link_info *info = finfo->info;
5981	asection *reldyn;	6132	asection *reldyn;
5982	bfd_size_type count, size;	6133	bfd_size_type count, size;
5983	size_t i, ret, sort_elt, ext_size;	6134	size_t i, ret, sort_elt, ext_size;
Lines 5989-5994 Link Here
5989	void (swap_out) (bfd , const Elf_Internal_Rela , bfd_byte );	6140	void (swap_out) (bfd , const Elf_Internal_Rela , bfd_byte );
5990	struct bfd_link_order *lo;	6141	struct bfd_link_order *lo;
5991	bfd_vma r_sym_mask;	6142	bfd_vma r_sym_mask;
		6143	int r_sym_shift;
5992		6144
5993	reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");	6145	reldyn = bfd_get_section_by_name (abfd, ".rela.dyn");
5994	if (reldyn == NULL \|\| reldyn->size == 0)	6146	if (reldyn == NULL \|\| reldyn->size == 0)
Lines 6030-6044 Link Here
6030	}	6182	}
6031		6183
6032	if (bed->s->arch_size == 32)	6184	if (bed->s->arch_size == 32)
6033	r_sym_mask = ~(bfd_vma) 0xff;	6185	{
		6186	r_sym_mask = ~(bfd_vma) 0xff;
		6187	r_sym_shift = 8;
		6188	}
6034	else	6189	else
6035	r_sym_mask = ~(bfd_vma) 0xffffffff;	6190	{
		6191	r_sym_mask = ~(bfd_vma) 0xffffffff;
		6192	r_sym_shift = 32;
		6193	}
6036		6194
6037	for (lo = reldyn->map_head.link_order; lo != NULL; lo = lo->next)	6195	for (lo = reldyn->map_head.link_order; lo != NULL; lo = lo->next)
6038	if (lo->type == bfd_indirect_link_order)	6196	if (lo->type == bfd_indirect_link_order)
6039	{	6197	{
6040	bfd_byte erel, erelend;	6198	bfd_byte erel, erelend;
6041	asection *o = lo->u.indirect.section;	6199	asection *o = lo->u.indirect.section;
		6200	int base_offset = -1;
		6201	int base_max = 0;
		6202
		6203	if (elf_hash_table (info)->sorted_size > 0)
		6204	{
		6205	base_offset = elf_hash_table (info)->sorted[0]->dynindx;
		6206	base_max = base_offset + elf_hash_table (info)->sorted_size;
		6207	}
6042		6208
6043	if (o->contents == NULL && o->size != 0)	6209	if (o->contents == NULL && o->size != 0)
6044	{	6210	{
Lines 6053-6062 Link Here
6053	p = sort + o->output_offset / ext_size * sort_elt;	6219	p = sort + o->output_offset / ext_size * sort_elt;
6054	while (erel < erelend)	6220	while (erel < erelend)
6055	{	6221	{
		6222	long dyn_idx;
		6223	size_t bucketcount = elf_hash_table (info)->bucketcount;
6056	struct elf_link_sort_rela s = (struct elf_link_sort_rela ) p;	6224	struct elf_link_sort_rela s = (struct elf_link_sort_rela ) p;
6057	(*swap_in) (abfd, erel, s->rela);	6225	(*swap_in) (abfd, erel, s->rela);
6058	s->type = (*bed->elf_backend_reloc_type_class) (s->rela);	6226	s->type = (*bed->elf_backend_reloc_type_class) (s->rela);
6059	s->u.sym_mask = r_sym_mask;	6227	s->u.sym_mask = r_sym_mask;
		6228
		6229	if (s->type != reloc_class_relative)
		6230	dyn_idx = s->rela->r_info >> r_sym_shift;
		6231	else
		6232	dyn_idx = -1;
		6233
		6234	if (info->dynsort && base_offset >= 0
		6235	&& dyn_idx < base_max && dyn_idx >= base_offset)
		6236	{
		6237	struct elf_link_hash_entry *ent;
		6238	ent = elf_hash_table (info)->sorted [dyn_idx - base_offset];
		6239	s->elf_bucket = ent->u.elf_hash_value % bucketcount;
		6240	}
		6241	else
		6242	s->elf_bucket = 0;
		6243
6060	p += sort_elt;	6244	p += sort_elt;
6061	erel += ext_size;	6245	erel += ext_size;
6062	}	6246	}
Lines 8493-8499 Link Here
8493	}	8677	}
8494		8678
8495	if (dynamic && info->combreloc && dynobj != NULL)	8679	if (dynamic && info->combreloc && dynobj != NULL)
8496	relativecount = elf_link_sort_relocs (abfd, info, &reldyn);	8680	relativecount = elf_link_sort_relocs (abfd, &finfo, &reldyn);
8497		8681
8498	/* If we are linking against a dynamic object, or generating a	8682	/* If we are linking against a dynamic object, or generating a
8499	shared library, finish up the dynamic linking information. */	8683	shared library, finish up the dynamic linking information. */