* Makefile.am (BFD32_BACKENDS): Add elf-strtab.lo.

	(BFD32_BACKENDS_CFILES): Add elf-strtab.c.
	(elf-strtab.lo): Add rule.
	* Makefile.in: Rebuilt.
	* configure.in (elf): Add elf-strtab.lo.
	* configure: Rebuilt.
	* elf-bfd.h (elf_strtab_hash): Forward declare.
	(struct elf_link_hash_table): Change dynstr type to
	struct elf_strtab_hash *.
	(struct elf_obj_tdata): Change strtab_ptr type to
	struct elf_strtab_hash *.
	(_bfd_elf_strtab_init, _bfd_elf_strtab_free, _bfd_elf_strtab_add,
	_bfd_elf_strtab_addref, _bfd_elf_strtab_delref,
	_bfd_elf_strtab_clear_all_refs, _bfd_elf_strtab_size,
	_bfd_elf_strtab_offset, _bfd_elf_strtab_emit,
	_bfd_elf_strtab_finalize): New prototypes.
	* elf-strtab.c: New file.
	* elflink.h (elf_link_add_object_symbols): Use _bfd_elf_strtab_add
	and _bfd_elf_strtab_size instead of _bfd_stringtab calls.
	Call _bfd_elf_strtab_delref if DT_NEEDED entry is not needed or
	when forcing dynamic symbol to local.
	(elf_link_create_dynamic_sections): Call
	_bfd_elf_strtab_init instead of elf_stringtab_init.
	(elf_link_record_local_dynamic_symbol): Likewise, change
	dynstr type.  Use _bfd_elf_strtab functions instead of
	_bfd_stringtab calls.
	(size_dynamic_sections): Use _bfd_elf_strtab functions instead of
	_bfd_stringtab calls.  For DT_RUNPATH and Verdaux vda_name fields,
	call _bfd_elf_strtab_addref.  Call elf_finalize_dynstr.
	(elf_adjust_dynstr_offsets, elf_finalize_dynstr): New functions.
	(elf_fix_symbol_flags): Call _bfd_elf_strtab_delref when forcing
	dynamic symbol to local.
	(elf_link_assign_sym_version): Likewise.
	(elf_bfd_final_link): Call _bfd_elf_strtab_emit instead of
	_bfd_stringtab_emit.
	* elflink.c (_bfd_elf_link_record_dynamic_symbol): Change dynstr
	type.  Call _bfd_elf_strtab functions instead of
	_bfd_stringtab functions.
	* elf64-sparc.c (sparc64_elf_size_dynamic_sections): Likewise.
	* elf.c (_bfd_elf_init_reloc_shdr): Likewise.
	(elf_fake_sections): Likewise.
	(assign_section_numbers): Call _bfd_elf_strtab_clear_all_refs
	on shstrtab hash table, call _bfd_elf_strtab_addref on each section
	name in the output.  Call _bfd_elf_strtab_finalize and
	use _bfd_elf_strtab_offset to finalize sh_name section header fields.
	(_bfd_elf_compute_section_file_positions): Use _bfd_elf_strtab_size
	instead of _bfd_stringtab_size.
	(prep_headers): Change shstrtab type.
	Use _bfd_elf_strtab calls instead of _bfd_stringtab calls.

1 files changed, 459 insertions, 0 deletions

diff --git a/bfd/elf-strtab.c b/bfd/elf-strtab.c
new file mode 100644
index 0000000..59a25a5
--- /dev/null
+++ b/bfd/elf-strtab.c
@@ -0,0 +1,459 @@
+/* ELF strtab with GC and suffix merging support.
+   Copyright 2001 Free Software Foundation, Inc.
+   Written by Jakub Jelinek <jakub@redhat.com>.
+
+This file is part of BFD, the Binary File Descriptor library.
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+This program 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 General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#include "bfd.h"
+#include "sysdep.h"
+#include "libbfd.h"
+#include "elf-bfd.h"
+#include "hashtab.h"
+
+/* An entry in the strtab hash table.  */
+
+struct elf_strtab_hash_entry
+{
+  struct bfd_hash_entry root;
+  /* Length of this entry.  */
+  unsigned int len;
+  unsigned int refcount;
+  union {
+    /* Index within the merged section.  */
+    bfd_size_type index;
+    /* Entry this is a suffix of (if len is 0).  */
+    struct elf_strtab_hash_entry *suffix;
+  } u;
+};
+
+/* The strtab hash table.  */
+
+struct elf_strtab_hash
+{
+  struct bfd_hash_table table;
+  /* Next available index.  */
+  bfd_size_type size;
+  /* Number of array entries alloced.  */
+  bfd_size_type alloced;
+  /* Final strtab size.  */
+  bfd_size_type sec_size;
+  /* Array of pointers to strtab entries.  */
+  struct elf_strtab_hash_entry **array;
+};
+
+static struct bfd_hash_entry *elf_strtab_hash_newfunc
+  PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
+static int cmplengthentry PARAMS ((const PTR, const PTR));
+static int last4_eq PARAMS ((const PTR, const PTR));
+static int last_eq PARAMS ((const PTR, const PTR));
+
+/* Routine to create an entry in a section merge hashtab.  */
+
+static struct bfd_hash_entry *
+elf_strtab_hash_newfunc (entry, table, string)
+     struct bfd_hash_entry *entry;
+     struct bfd_hash_table *table;
+     const char *string;
+{
+  struct elf_strtab_hash_entry *ret = (struct elf_strtab_hash_entry *) entry;
+
+  /* Allocate the structure if it has not already been allocated by a
+     subclass.  */
+  if (ret == (struct elf_strtab_hash_entry *) NULL)
+    ret = ((struct elf_strtab_hash_entry *)
+	   bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)));
+  if (ret == (struct elf_strtab_hash_entry *) NULL)
+    return NULL;
+
+  /* Call the allocation method of the superclass.  */
+  ret = ((struct elf_strtab_hash_entry *)
+	 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
+
+  if (ret)
+    {
+      /* Initialize the local fields.  */
+      ret->u.index = -1;
+      ret->refcount = 0;
+      ret->len = 0;
+    }
+
+  return (struct bfd_hash_entry *)ret;
+}
+
+/* Create a new hash table.  */
+
+struct elf_strtab_hash *
+_bfd_elf_strtab_init ()
+{
+  struct elf_strtab_hash *table;
+  bfd_size_type amt = sizeof (struct elf_strtab_hash);
+
+  table = (struct elf_strtab_hash *) bfd_malloc (amt);
+  if (table == NULL)
+    return NULL;
+
+  if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
+    {
+      free (table);
+      return NULL;
+    }
+
+  table->sec_size = 0;
+  table->size = 1;
+  table->alloced = 64;
+  amt = sizeof (struct elf_strtab_hasn_entry *);
+  table->array = (struct elf_strtab_hash_entry **)
+		 bfd_malloc (table->alloced * amt);
+  if (table->array == NULL)
+    {
+      free (table);
+      return NULL;
+    }
+
+  table->array[0] = NULL;
+
+  return table;
+}
+
+/* Free a strtab.  */
+
+void
+_bfd_elf_strtab_free (tab)
+     struct elf_strtab_hash *tab;
+{
+  bfd_hash_table_free (&tab->table);
+  free (tab->array);
+  free (tab);
+}
+
+/* Get the index of an entity in a hash table, adding it if it is not
+   already present.  */
+
+bfd_size_type
+_bfd_elf_strtab_add (tab, str, copy)
+     struct elf_strtab_hash *tab;
+     const char *str;
+     boolean copy;
+{
+  register struct elf_strtab_hash_entry *entry;
+
+  /* We handle this specially, since we don't want to do refcounting
+     on it.  */
+  if (*str == '\0')
+    return 0;
+
+  BFD_ASSERT (tab->sec_size == 0);
+  entry = (struct elf_strtab_hash_entry *)
+	  bfd_hash_lookup (&tab->table, str, true, copy);
+
+  if (entry == NULL)
+    return (bfd_size_type) -1;
+
+  entry->refcount++;
+  if (entry->len == 0)
+    {
+      entry->len = strlen (str) + 1;
+      if (tab->size == tab->alloced)
+	{
+	  bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
+	  tab->alloced *= 2;
+	  tab->array = (struct elf_strtab_hash_entry **)
+		       bfd_realloc (tab->array, tab->alloced * amt);
+	  if (tab->array == NULL)
+	    return (bfd_size_type) -1;
+	}
+
+      entry->u.index = tab->size++;
+      tab->array[entry->u.index] = entry;
+    }
+  return entry->u.index;
+}
+
+void
+_bfd_elf_strtab_addref (tab, idx)
+     struct elf_strtab_hash *tab;
+     bfd_size_type idx;
+{
+  if (idx == 0 || idx == (bfd_size_type) -1)
+    return;
+  BFD_ASSERT (tab->sec_size == 0);
+  BFD_ASSERT (idx < tab->size);
+  ++tab->array[idx]->refcount;
+}
+
+void
+_bfd_elf_strtab_delref (tab, idx)
+     struct elf_strtab_hash *tab;
+     bfd_size_type idx;
+{
+  if (idx == 0 || idx == (bfd_size_type) -1)
+    return;
+  BFD_ASSERT (tab->sec_size == 0);
+  BFD_ASSERT (idx < tab->size);
+  BFD_ASSERT (tab->array[idx]->refcount > 0);
+  --tab->array[idx]->refcount;
+}
+
+void
+_bfd_elf_strtab_clear_all_refs (tab)
+     struct elf_strtab_hash *tab;
+{
+  bfd_size_type idx;
+
+  for (idx = 1; idx < tab->size; ++idx)
+    tab->array[idx]->refcount = 0;
+}
+
+bfd_size_type
+_bfd_elf_strtab_size (tab)
+     struct elf_strtab_hash *tab;
+{
+  return tab->sec_size ? tab->sec_size : tab->size;
+}
+
+bfd_size_type
+_bfd_elf_strtab_offset (tab, idx)
+     struct elf_strtab_hash *tab;
+     bfd_size_type idx;
+{
+  struct elf_strtab_hash_entry *entry;
+
+  if (idx == 0)
+    return 0;
+  BFD_ASSERT (idx < tab->size);
+  BFD_ASSERT (tab->sec_size);
+  entry = tab->array[idx];
+  BFD_ASSERT (entry->refcount > 0);
+  entry->refcount--;
+  return tab->array[idx]->u.index;
+}
+
+boolean
+_bfd_elf_strtab_emit (abfd, tab)
+     register bfd *abfd;
+     struct elf_strtab_hash *tab;
+{
+  bfd_size_type off = 1, i;
+
+  if (bfd_bwrite ("", 1, abfd) != 1)
+    return false;
+
+  for (i = 1; i < tab->size; ++i)
+    {
+      register const char *str;
+      register size_t len;
+
+      str = tab->array[i]->root.string;
+      len = tab->array[i]->len;
+      BFD_ASSERT (tab->array[i]->refcount == 0);
+      if (len == 0)
+	continue;
+
+      if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
+	return false;
+
+      off += len;
+    }
+
+  BFD_ASSERT (off == tab->sec_size);
+  return true;
+}
+
+/* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
+
+static int
+cmplengthentry (a, b)
+     const PTR a;
+     const PTR b;
+{
+  struct elf_strtab_hash_entry * A = *(struct elf_strtab_hash_entry **) a;
+  struct elf_strtab_hash_entry * B = *(struct elf_strtab_hash_entry **) b;
+
+  if (A->len < B->len)
+    return 1;
+  else if (A->len > B->len)
+    return -1;
+
+  return memcmp (A->root.string, B->root.string, A->len);
+}
+
+static int
+last4_eq (a, b)
+     const PTR a;
+     const PTR b;
+{
+  struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
+  struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
+
+  if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
+      != 0)
+    /* This was a hashtable collision.  */
+    return 0;
+
+  if (A->len <= B->len)
+    /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
+       not to be equal by the hash table.  */
+    return 0;
+
+  return memcmp (A->root.string + (A->len - B->len),
+		 B->root.string, B->len - 5) == 0;
+}
+
+static int
+last_eq (a, b)
+     const PTR a;
+     const PTR b;
+{
+  struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
+  struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
+
+  if (B->len >= 5)
+    /* Longer strings are just pushed into the hash table,
+       they'll be used when looking up for very short strings.  */
+    return 0;
+
+  if (memcmp (A->root.string + A->len - 2, B->root.string + B->len - 2, 1)
+      != 0)
+    /* This was a hashtable collision.  */
+    return 0;
+
+  if (A->len <= B->len)
+    /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
+       not to be equal by the hash table.  */
+    return 0;
+
+  return memcmp (A->root.string + (A->len - B->len),
+		 B->root.string, B->len - 2) == 0;
+}
+
+/* This function assigns final string table offsets for used strings,
+   merging strings matching suffixes of longer strings if possible.  */
+
+void
+_bfd_elf_strtab_finalize (tab)
+     struct elf_strtab_hash *tab;
+{
+  struct elf_strtab_hash_entry **array, **a, **end, *e;
+  htab_t lasttab = NULL, last4tab = NULL;
+  bfd_size_type size, amt, i;
+
+  /* Now sort the strings by length, longest first.  */
+  array = NULL;
+  amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
+  array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
+  if (array == NULL)
+    goto alloc_failure;
+
+  for (i = 1, a = array; i < tab->size; ++i)
+    if (tab->array[i]->refcount)
+      *a++ = tab->array[i];
+    else
+      tab->array[i]->len = 0;
+
+  size = a - array;
+
+  qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
+
+  last4tab = htab_create (size * 4, NULL, last4_eq, NULL);
+  lasttab = htab_create (size * 4, NULL, last_eq, NULL);
+  if (lasttab == NULL || last4tab == NULL)
+    goto alloc_failure;
+
+  /* Now insert the strings into hash tables (strings with last 4 characters
+     and strings with last character equal), look for longer strings which
+     we're suffix of.  */
+  for (a = array, end = array + size; a < end; a++)
+    {
+      register hashval_t hash;
+      unsigned int c;
+      unsigned int i;
+      const unsigned char *s;
+      PTR *p;
+
+      e = *a;
+      if (e->len > 4)
+	{
+	  s = e->root.string + e->len - 1;
+	  hash = 0;
+	  for (i = 0; i < 4; i++)
+	    {
+	      c = *--s;
+	      hash += c + (c << 17);
+	      hash ^= hash >> 2;
+	    }
+	  p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
+	  if (p == NULL)
+	    goto alloc_failure;
+	  if (*p)
+	    {
+	      struct elf_strtab_hash_entry *ent;
+
+	      ent = (struct elf_strtab_hash_entry *) *p;
+	      e->u.suffix = ent;
+	      e->len = 0;
+	      continue;
+	    }
+	  else
+	    *p = (PTR) e;
+	}
+      c = (unsigned char) e->root.string[e->len - 1];
+      p = htab_find_slot_with_hash (lasttab, e, c, INSERT);
+      if (p == NULL)
+	goto alloc_failure;
+      if (*p)
+	{
+	  struct elf_strtab_hash_entry *ent;
+
+	  ent = (struct elf_strtab_hash_entry *) *p;
+	  e->u.suffix = ent;
+	  e->len = 0;
+	}
+      else
+	*p = (PTR) e;
+    }
+
+alloc_failure:
+  if (array)
+    free (array);
+  if (lasttab)
+    htab_delete (lasttab);
+  if (last4tab)
+    htab_delete (last4tab);
+
+  /* Now assign positions to the strings we want to keep.  */
+  size = 1;
+  for (i = 1; i < tab->size; ++i)
+    {
+      e = tab->array[i];
+      if (e->refcount && e->len)
+	{
+	  e->u.index = size;
+	  size += e->len;
+	}
+    }
+
+  tab->sec_size = size;
+
+  /* And now adjust the rest.  */
+  for (i = 1; i < tab->size; ++i)
+    {
+      e = tab->array[i];
+      if (e->refcount && ! e->len)
+	e->u.index = e->u.suffix->u.index
+		     + (e->u.suffix->len - strlen (e->root.string) - 1);
+    }
+}