hash table for bfd sections

[Alan Modra <amodra at bigpond dot net dot au>]

When testing my changes for > 64k ELF sections, I found that assembling
the file generated by the following took over 90 minutes, before
crashing.  Which made debugging rather painful, and probably would mean
no one would want to use that many sections anyway.

#include <stdio.h>

int main (void)
{
  unsigned int i;

  for (i = 0; i < 80000; i++)
    printf (" .section .text.%u,\"ax\",@progbits\nt%u: nop\n", i, i);

  printf (" .data\n");
  for (i = 0; i < 80000; i++)
    printf (" .long t%u\n", i);
}

This patch fixes the main culprit, the scans through the section list
on creating a new bfd section.  There are still a number of other places
that need fixing, most notably _bfd_elf_section_from_bfd_section.

	* bfd.c (struct _bfd): Add section_htab, section_tail.
	* libbfd-in.h (_bfd_delete_bfd): Declare.
	(bfd_section_hash_newfunc): Declare.
	* opncls.c (_bfd_new_bfd): Free memory on failure.  Init
	section_htab and section_tail.
	(_bfd_delete_bfd): New function.
	(bfd_openr): Use it.
	(bfd_fdopenr): Likewise.
	(bfd_openstreamr): Likewise.
	(bfd_openw): Likewise.
	(bfd_close): Likewise.
	(bfd_close_all_done): Likewise.
	(bfd_release): Comment.
	* section.c (struct section_hash_entry): New.
	(bfd_section_hash_newfunc): New function.
	(section_hash_lookup): Define.
	(bfd_section_init): New function, split out from
	bfd_make_section_anyway.
	(bfd_get_section_by_name): Lookup via hash table.
	(bfd_get_unique_section_name): Likewise.
	(bfd_make_section_old_way): Rewrite to use hash table.
	(bfd_make_section_anyway): Likewise.
	(bfd_make_section): Likewise.  Return NULL for attempts to make
	BFD_{ABS,COM,UND,IND}_SECTION_NAME.
	(_bfd_strip_section_from_output): Adjust section_tail if needed.
	* configure.in: Bump bfd version.
	* configure: Regenerate.
	* libbfd.h: Regenerate.
	* bfd-in2.h: Regenerate.

ld/ChangeLog
	* emultempl/elf32.em (gld${EMULATION_NAME}_place_orphan): Adjust
	section_tail when fiddling with section list.
	(gld${EMULATION_NAME}_list_options): Ensure sentences aren't
	broken into separate strings to make translation easier.
	* emultempl/mmo.em (mmo_place_orphan): Adjust section_tail when
	fiddling with section list.
	* emultempl/pe.em (gld_${EMULATION_NAME}_place_orphan): Likewise.

Comments welcome.  I have tweaked the behaviour of bfd_make_section,
so will hold off applying this for a while.

-- 
Alan Modra

Index: bfd/bfd.c
===================================================================
RCS file: /cvs/src/src/bfd/bfd.c,v
retrieving revision 1.27
diff -u -p -r1.27 bfd.c
--- bfd.c	2001/10/30 15:20:02	1.27
+++ bfd.c	2001/12/14 16:01:12
@@ -114,8 +114,14 @@ CODE_FRAGMENT
 .       from happening. *}
 .    boolean output_has_begun;
 .
-.    {* Pointer to linked list of sections*}
-.    struct sec  *sections;
+.    {* A hash table for section names. *}
+.    struct bfd_hash_table section_htab;
+.
+.    {* Pointer to linked list of sections. *}
+.    struct sec *sections;
+.
+.    {* The place where we add to the section list. *}
+.    struct sec **section_tail;
 .
 .    {* The number of sections *}
 .    unsigned int section_count;
Index: bfd/libbfd-in.h
===================================================================
RCS file: /cvs/src/src/bfd/libbfd-in.h,v
retrieving revision 1.17
diff -u -p -r1.17 libbfd-in.h
--- libbfd-in.h	2001/11/15 01:34:11	1.17
+++ libbfd-in.h	2001/12/14 16:02:34
@@ -112,6 +112,7 @@ boolean _bfd_compute_and_write_armap PAR
 bfd *_bfd_get_elt_at_filepos PARAMS ((bfd *archive, file_ptr filepos));
 extern bfd *_bfd_generic_get_elt_at_index PARAMS ((bfd *, symindex));
 bfd * _bfd_new_bfd PARAMS ((void));
+void _bfd_delete_bfd PARAMS ((bfd *));
 
 boolean	bfd_false PARAMS ((bfd *ignore));
 boolean	bfd_true PARAMS ((bfd *ignore));
@@ -367,6 +368,10 @@ extern boolean _bfd_dwarf2_find_nearest_
   PARAMS ((bfd *, asection *, asymbol **, bfd_vma, const char **,
 	   const char **, unsigned int *, unsigned int,
 	   PTR *));
+
+/* Create a new section entry.  */
+extern struct bfd_hash_entry *bfd_section_hash_newfunc
+  PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
 
 /* A routine to create entries for a bfd_link_hash_table.  */
 extern struct bfd_hash_entry *_bfd_link_hash_newfunc
Index: bfd/opncls.c
===================================================================
RCS file: /cvs/src/src/bfd/opncls.c,v
retrieving revision 1.5
diff -u -p -r1.5 opncls.c
--- opncls.c	2001/09/18 09:57:25	1.5
+++ opncls.c	2001/12/14 16:02:35
@@ -57,6 +57,7 @@ _bfd_new_bfd ()
   if (nbfd->memory == NULL)
     {
       bfd_set_error (bfd_error_no_memory);
+      free (nbfd);
       return NULL;
     }
 
@@ -65,7 +66,13 @@ _bfd_new_bfd ()
   nbfd->direction = no_direction;
   nbfd->iostream = NULL;
   nbfd->where = 0;
+  if (!bfd_hash_table_init (&nbfd->section_htab, bfd_section_hash_newfunc))
+    {
+      free (nbfd);
+      return NULL;
+    }
   nbfd->sections = (asection *) NULL;
+  nbfd->section_tail = &nbfd->sections;
   nbfd->format = bfd_unknown;
   nbfd->my_archive = (bfd *) NULL;
   nbfd->origin = 0;
@@ -96,6 +103,17 @@ _bfd_new_bfd_contained_in (obfd)
   return nbfd;
 }
 
+/* Delete a BFD.  */
+
+void
+_bfd_delete_bfd (abfd)
+     bfd *abfd;
+{
+  bfd_hash_table_free (&abfd->section_htab);
+  objalloc_free ((struct objalloc *) abfd->memory);
+  free (abfd);
+}
+
 /*
 SECTION
 	Opening and closing BFDs
@@ -135,9 +153,8 @@ bfd_openr (filename, target)
   target_vec = bfd_find_target (target, nbfd);
   if (target_vec == NULL)
     {
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
       bfd_set_error (bfd_error_invalid_target);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -148,8 +165,7 @@ bfd_openr (filename, target)
     {
       /* File didn't exist, or some such */
       bfd_set_error (bfd_error_system_call);
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -216,8 +232,7 @@ bfd_fdopenr (filename, target, fd)
   if (target_vec == NULL)
     {
       bfd_set_error (bfd_error_invalid_target);
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -236,8 +251,7 @@ bfd_fdopenr (filename, target, fd)
 
   if (nbfd->iostream == NULL)
     {
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -259,8 +273,7 @@ bfd_fdopenr (filename, target, fd)
 
   if (! bfd_cache_init (nbfd))
     {
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
   nbfd->opened_once = true;
@@ -299,8 +312,7 @@ bfd_openstreamr (filename, target, strea
   if (target_vec == NULL)
     {
       bfd_set_error (bfd_error_invalid_target);
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -310,8 +322,7 @@ bfd_openstreamr (filename, target, strea
 
   if (! bfd_cache_init (nbfd))
     {
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -358,8 +369,7 @@ bfd_openw (filename, target)
   target_vec = bfd_find_target (target, nbfd);
   if (target_vec == NULL)
     {
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
     }
 
@@ -369,8 +379,7 @@ bfd_openw (filename, target)
   if (bfd_open_file (nbfd) == NULL)
     {
       bfd_set_error (bfd_error_system_call);	/* File not writeable, etc */
-      objalloc_free ((struct objalloc *) nbfd->memory);
-      free (nbfd);
+      _bfd_delete_bfd (nbfd);
       return NULL;
   }
 
@@ -437,8 +446,7 @@ bfd_close (abfd)
 	}
     }
 
-  objalloc_free ((struct objalloc *) abfd->memory);
-  free (abfd);
+  _bfd_delete_bfd (abfd);
 
   return ret;
 }
@@ -492,8 +500,7 @@ bfd_close_all_done (abfd)
 	}
     }
 
-  objalloc_free ((struct objalloc *) abfd->memory);
-  free (abfd);
+  _bfd_delete_bfd (abfd);
 
   return ret;
 }
@@ -680,7 +687,8 @@ bfd_zalloc (abfd, size)
   return res;
 }
 
-/* Free a block allocated for a BFD.  */
+/* Free a block allocated for a BFD.
+   Note:  Also frees all more recently allocated blocks!  */
 
 void
 bfd_release (abfd, block)
Index: bfd/section.c
===================================================================
RCS file: /cvs/src/src/bfd/section.c,v
retrieving revision 1.41
diff -u -p -r1.41 section.c
--- section.c	2001/11/19 15:35:38	1.41
+++ section.c	2001/12/14 16:02:36
@@ -629,6 +629,92 @@ STD_SECTION (bfd_abs_section, 0, bfd_abs
 STD_SECTION (bfd_ind_section, 0, bfd_ind_symbol, BFD_IND_SECTION_NAME, 3);
 #undef STD_SECTION
 
+struct section_hash_entry
+{
+  struct bfd_hash_entry root;
+  asection section;
+};
+
+/* Initialize an entry in the section hash table.  */
+
+struct bfd_hash_entry *
+bfd_section_hash_newfunc (entry, table, string)
+     struct bfd_hash_entry *entry;
+     struct bfd_hash_table *table;
+     const char *string;
+{
+  /* Allocate the structure if it has not already been allocated by a
+     subclass.  */
+  if (entry == NULL)
+    {
+      entry = bfd_hash_allocate (table, sizeof (struct section_hash_entry));
+      if (entry == NULL)
+	return entry;
+    }
+
+  /* Call the allocation method of the superclass.  */
+  entry = bfd_hash_newfunc (entry, table, string);
+  if (entry != NULL)
+    {
+      memset ((PTR) &((struct section_hash_entry *) entry)->section,
+	      0, sizeof (asection));
+    }
+
+  return entry;
+}
+
+#define section_hash_lookup(table, string, create, copy) \
+  ((struct section_hash_entry *) \
+   bfd_hash_lookup ((table), (string), (create), (copy)))
+
+/* Initializes a new section.  NEWSECT->NAME is already set.  */
+
+static asection *bfd_section_init PARAMS ((bfd *, asection *));
+
+static asection *
+bfd_section_init (abfd, newsect)
+     bfd *abfd;
+     asection *newsect;
+{
+  static int section_id = 0x10;  /* id 0 to 3 used by STD_SECTION.  */
+
+  newsect->id = section_id;
+  newsect->index = abfd->section_count;
+  newsect->flags = SEC_NO_FLAGS;
+
+  newsect->userdata = NULL;
+  newsect->contents = NULL;
+  newsect->next = (asection *) NULL;
+  newsect->relocation = (arelent *) NULL;
+  newsect->reloc_count = 0;
+  newsect->line_filepos = 0;
+  newsect->owner = abfd;
+  newsect->comdat = NULL;
+
+  /* Create a symbol whose only job is to point to this section.  This
+     is useful for things like relocs which are relative to the base
+     of a section.  */
+  newsect->symbol = bfd_make_empty_symbol (abfd);
+  if (newsect->symbol == NULL)
+    return NULL;
+
+  newsect->symbol->name = newsect->name;
+  newsect->symbol->value = 0;
+  newsect->symbol->section = newsect;
+  newsect->symbol->flags = BSF_SECTION_SYM;
+
+  newsect->symbol_ptr_ptr = &newsect->symbol;
+
+  if (! BFD_SEND (abfd, _new_section_hook, (abfd, newsect)))
+    return NULL;
+
+  section_id++;
+  abfd->section_count++;
+  *abfd->section_tail = newsect;
+  abfd->section_tail = &newsect->next;
+  return newsect;
+}
+
 /*
 DOCDD
 INODE
@@ -662,11 +748,12 @@ bfd_get_section_by_name (abfd, name)
      bfd *abfd;
      const char *name;
 {
-  asection *sect;
+  struct section_hash_entry *sh;
 
-  for (sect = abfd->sections; sect != NULL; sect = sect->next)
-    if (!strcmp (sect->name, name))
-      return sect;
+  sh = section_hash_lookup (&abfd->section_htab, name, false, false);
+  if (sh != NULL)
+    return &sh->section;
+
   return NULL;
 }
 
@@ -713,7 +800,7 @@ bfd_get_unique_section_name (abfd, templ
 	abort ();
       sprintf (sname + len, ".%d", num++);
     }
-  while (bfd_get_section_by_name (abfd, sname) != NULL);
+  while (section_hash_lookup (&abfd->section_htab, sname, false, false));
 
   if (count != NULL)
     *count = num;
@@ -750,12 +837,40 @@ bfd_make_section_old_way (abfd, name)
      bfd *abfd;
      const char *name;
 {
-  asection *sec = bfd_get_section_by_name (abfd, name);
-  if (sec == (asection *) NULL)
+  struct section_hash_entry *sh;
+  asection *newsect;
+
+  if (abfd->output_has_begun)
     {
-      sec = bfd_make_section (abfd, name);
+      bfd_set_error (bfd_error_invalid_operation);
+      return NULL;
     }
-  return sec;
+
+  if (strcmp (name, BFD_ABS_SECTION_NAME) == 0)
+    return bfd_abs_section_ptr;
+
+  if (strcmp (name, BFD_COM_SECTION_NAME) == 0)
+    return bfd_com_section_ptr;
+
+  if (strcmp (name, BFD_UND_SECTION_NAME) == 0)
+    return bfd_und_section_ptr;
+
+  if (strcmp (name, BFD_IND_SECTION_NAME) == 0)
+    return bfd_ind_section_ptr;
+
+  sh = section_hash_lookup (&abfd->section_htab, name, true, false);
+  if (sh == NULL)
+    return NULL;
+
+  newsect = &sh->section;
+  if (newsect->name != NULL)
+    {
+      /* Section already exists.  */
+      return newsect;
+    }
+
+  newsect->name = name;
+  return bfd_section_init (abfd, newsect);
 }
 
 /*
@@ -780,67 +895,33 @@ bfd_make_section_anyway (abfd, name)
      bfd *abfd;
      const char *name;
 {
-  static int section_id = 0x10;  /* id 0 to 3 used by STD_SECTION.  */
+  struct section_hash_entry *sh;
   asection *newsect;
-  asection **prev = &abfd->sections;
-  asection *sect = abfd->sections;
 
   if (abfd->output_has_begun)
     {
       bfd_set_error (bfd_error_invalid_operation);
       return NULL;
     }
-
-  while (sect)
-    {
-      prev = &sect->next;
-      sect = sect->next;
-    }
 
-  newsect = (asection *) bfd_zalloc (abfd, (bfd_size_type) sizeof (asection));
-  if (newsect == NULL)
+  sh = section_hash_lookup (&abfd->section_htab, name, true, false);
+  if (sh == NULL)
     return NULL;
-
-  newsect->name = name;
-  newsect->id = section_id;
-  newsect->index = abfd->section_count;
-  newsect->flags = SEC_NO_FLAGS;
-
-  newsect->userdata = NULL;
-  newsect->contents = NULL;
-  newsect->next = (asection *) NULL;
-  newsect->relocation = (arelent *) NULL;
-  newsect->reloc_count = 0;
-  newsect->line_filepos = 0;
-  newsect->owner = abfd;
-  newsect->comdat = NULL;
-
-  /* Create a symbol whos only job is to point to this section. This is
-     useful for things like relocs which are relative to the base of a
-     section.  */
-  newsect->symbol = bfd_make_empty_symbol (abfd);
-  if (newsect->symbol == NULL)
-    {
-      bfd_release (abfd, newsect);
-      return NULL;
-    }
-  newsect->symbol->name = name;
-  newsect->symbol->value = 0;
-  newsect->symbol->section = newsect;
-  newsect->symbol->flags = BSF_SECTION_SYM;
 
-  newsect->symbol_ptr_ptr = &newsect->symbol;
-
-  if (BFD_SEND (abfd, _new_section_hook, (abfd, newsect)) != true)
+  newsect = &sh->section;
+  if (newsect->name != NULL)
     {
-      bfd_release (abfd, newsect);
-      return NULL;
+      /* We are making a section of the same name.  It can't go in
+	 section_htab without generating a unique section name and
+	 that would be pointless;  We don't need to traverse the
+	 hash table.  */
+      newsect = (asection *) bfd_zalloc (abfd, sizeof (asection));
+      if (newsect == NULL)
+	return NULL;
     }
 
-  section_id++;
-  abfd->section_count++;
-  *prev = newsect;
-  return newsect;
+  newsect->name = name;
+  return bfd_section_init (abfd, newsect);
 }
 
 /*
@@ -862,35 +943,34 @@ bfd_make_section (abfd, name)
      bfd *abfd;
      const char *name;
 {
-  asection *sect = abfd->sections;
+  struct section_hash_entry *sh;
+  asection *newsect;
 
-  if (strcmp (name, BFD_ABS_SECTION_NAME) == 0)
-    {
-      return bfd_abs_section_ptr;
-    }
-  if (strcmp (name, BFD_COM_SECTION_NAME) == 0)
-    {
-      return bfd_com_section_ptr;
-    }
-  if (strcmp (name, BFD_UND_SECTION_NAME) == 0)
+  if (abfd->output_has_begun)
     {
-      return bfd_und_section_ptr;
+      bfd_set_error (bfd_error_invalid_operation);
+      return NULL;
     }
 
-  if (strcmp (name, BFD_IND_SECTION_NAME) == 0)
-    {
-      return bfd_ind_section_ptr;
-    }
+  if (strcmp (name, BFD_ABS_SECTION_NAME) == 0
+      || strcmp (name, BFD_COM_SECTION_NAME) == 0
+      || strcmp (name, BFD_UND_SECTION_NAME) == 0
+      || strcmp (name, BFD_IND_SECTION_NAME) == 0)
+    return NULL;
 
-  while (sect)
+  sh = section_hash_lookup (&abfd->section_htab, name, true, false);
+  if (sh == NULL)
+    return NULL;
+
+  newsect = &sh->section;
+  if (newsect->name != NULL)
     {
-      if (!strcmp (sect->name, name))
-	return NULL;
-      sect = sect->next;
+      /* Section already exists.  */
+      return newsect;
     }
 
-  /* The name is not already used; go ahead and make a new section.  */
-  return bfd_make_section_anyway (abfd, name);
+  newsect->name = name;
+  return bfd_section_init (abfd, newsect);
 }
 
 /*
@@ -1278,6 +1358,8 @@ _bfd_strip_section_from_output (info, s)
 	if (*spp == os)
 	  {
 	    *spp = os->next;
+	    if (os->next == NULL)
+	      os->owner->section_tail = spp;
 	    os->owner->section_count--;
 	    break;
 	  }
Index: ld/emultempl/elf32.em
===================================================================
RCS file: /cvs/src/src/ld/emultempl/elf32.em,v
retrieving revision 1.68
diff -u -p -r1.68 elf32.em
--- elf32.em	2001/12/13 11:09:34	1.68
+++ elf32.em	2001/12/14 16:02:47
@@ -1274,10 +1274,14 @@ gld${EMULATION_NAME}_place_orphan (file,
 	  for (pps = &output_bfd->sections; *pps != snew; pps = &(*pps)->next)
 	    ;
 	  *pps = snew->next;
+	  if (snew->next == NULL)
+	    snew->owner->section_tail = pps;
 
 	  /* Now tack it on to the "place->os" section list.  */
 	  snew->next = *place->section;
 	  *place->section = snew;
+	  if (snew->next == NULL)
+	    snew->owner->section_tail = &snew->next;
 	}
 
       /* Save the end of this list.  Further ophans of this type will
@@ -1598,8 +1602,7 @@ cat >>e${EMULATION_NAME}.c <<EOF
   fprintf (file, _("  -z nodlopen\t\tMark DSO not available to dlopen\n"));
   fprintf (file, _("  -z nodump\t\tMark DSO not available to dldump\n"));
   fprintf (file, _("  -z now\t\tMark object non-lazy runtime binding\n"));
-  fprintf (file, _("  -z origin\t\tMark object requiring immediate \$ORIGIN processing\n"));
-  fprintf (file, _("\t\t\t  at runtime\n"));
+  fprintf (file, _("  -z origin\t\tMark object requiring immediate \$ORIGIN processing\n\t\t\t  at runtime\n"));
   fprintf (file, _("  -z KEYWORD\t\tIgnored for Solaris compatibility\n"));
 EOF
 fi
Index: ld/emultempl/mmo.em
===================================================================
RCS file: /cvs/src/src/ld/emultempl/mmo.em,v
retrieving revision 1.1
diff -u -p -r1.1 mmo.em
--- mmo.em	2001/10/30 15:20:11	1.1
+++ mmo.em	2001/12/14 16:02:48
@@ -163,10 +163,14 @@ mmo_place_orphan (file, s)
       for (pps = &output_bfd->sections; *pps != snew; pps = &(*pps)->next)
 	;
       *pps = snew->next;
+      if (snew->next == NULL)
+	snew->owner->section_tail = pps;
 
       /* Now tack it on to the "place->os" section list.  */
       snew->next = *place->section;
       *place->section = snew;
+      if (snew->next == NULL)
+	snew->owner->section_tail = &snew->next;
     }
   place->section = &snew->next;	/* Save the end of this list.  */
 
Index: ld/emultempl/pe.em
===================================================================
RCS file: /cvs/src/src/ld/emultempl/pe.em,v
retrieving revision 1.56
diff -u -p -r1.56 pe.em
--- pe.em	2001/12/11 18:31:57	1.56
+++ pe.em	2001/12/14 16:02:49
@@ -1691,10 +1691,14 @@ gld_${EMULATION_NAME}_place_orphan (file
 		   pps = &(*pps)->next)
 		;
 	      *pps = snew->next;
+	      if (snew->next == NULL)
+		snew->owner->section_tail = pps;
 
 	      /* Now tack it on to the "place->os" section list.  */
 	      snew->next = *place->section;
 	      *place->section = snew;
+	      if (snew->next == NULL)
+		snew->owner->section_tail = &snew->next;
 	    }
 
 	  /* Save the end of this list.  Further ophans of this type will