Fix LTO vs. COFF archives

Avoid scan of symbols on objects in coff archives since we don't need
to do anything special with common symbols.  The scan is quite useless,
and breaks LTO due to slim LTO objects not having symbols available
until after the plugin has claimed them.  Instead we can add objects
based on their archive symbol map.

Also, rip out the archive symbol hash table used by the generic
linker.  Using a hash breaks one feature of unix archive linking;
The first object file in an archive defining any given symbol should
be the object extracted to satisfy that symbol.  What's more a hash
isn't much faster except in pathological cases where object file
ordering causes many scans of the archive.  See the comment which I'm
removing from elf_link_add_archive_symbols.

Finally, tidy elflink.c archive handling a little.

	PR 13557
	* linker.c (struct archive_list, struct archive_hash_entry,
	struct archive_hash_table, archive_hash_newfunc,
	archive_hash_table_init, archive_hash_lookup, archive_hash_allocate,
	archive_hash_table_free): Delete.
	(_bfd_generic_link_add_archive_symbols): Add h and name params to
	checkfn.  Rewrite using a straight-forward scan over archive map.
	(generic_link_check_archive_element_no_collect,
	generic_link_check_archive_element_collect,
	generic_link_check_archive_element): Add h and name params.
	* aoutx.h (aout_link_check_archive_element): Likewise.
	* pdp11.c (aout_link_check_archive_element): Likewise.
	* xcofflink.c (xcoff_link_check_archive_element): Likewise.
	* cofflink.c (coff_link_check_archive_element): Likewise.  Don't
	scan symbols, simply add archive element whenever h is undefined.
	(coff_link_check_ar_symbols): Delete.
	* ecoff.c (read_ext_syms_and_strs): Delete.
	(reread_ext_syms_and_strs): Delete.
	(ecoff_link_check_archive_element): Add h and name param.  Don't
	scan symbols, simply add based on h.  Use ecoff_link_add_object_symbols.
	* elflink.c (elf_link_is_defined_archive_symbol): Don't test
	archive_pass.
	(elf_link_add_archive_symbols): Delete "defined" array, merge
	functionality into "included".  Make "included" a char array.  Don't
	set or test archive_pass.
	* libbfd-in.h (_bfd_generic_link_add_archive_symbols): Update.
	* libbfd.h: Regenerate.

10 files changed, 187 insertions, 560 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index d5defab2..fa976c4 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,33 @@
+2014-08-05  Alan Modra  <amodra@gmail.com>
+
+	PR 13557
+	* linker.c (struct archive_list, struct archive_hash_entry,
+	struct archive_hash_table, archive_hash_newfunc,
+	archive_hash_table_init, archive_hash_lookup, archive_hash_allocate,
+	archive_hash_table_free): Delete.
+	(_bfd_generic_link_add_archive_symbols): Add h and name params to
+	checkfn.  Rewrite using a straight-forward scan over archive map.
+	(generic_link_check_archive_element_no_collect,
+	generic_link_check_archive_element_collect,
+	generic_link_check_archive_element): Add h and name params.
+	* aoutx.h (aout_link_check_archive_element): Likewise.
+	* pdp11.c (aout_link_check_archive_element): Likewise.
+	* xcofflink.c (xcoff_link_check_archive_element): Likewise.
+	* cofflink.c (coff_link_check_archive_element): Likewise.  Don't
+	scan symbols, simply add archive element whenever h is undefined.
+	(coff_link_check_ar_symbols): Delete.
+	* ecoff.c (read_ext_syms_and_strs): Delete.
+	(reread_ext_syms_and_strs): Delete.
+	(ecoff_link_check_archive_element): Add h and name param.  Don't
+	scan symbols, simply add based on h.  Use ecoff_link_add_object_symbols.
+	* elflink.c (elf_link_is_defined_archive_symbol): Don't test
+	archive_pass.
+	(elf_link_add_archive_symbols): Delete "defined" array, merge
+	functionality into "included".  Make "included" a char array.  Don't
+	set or test archive_pass.
+	* libbfd-in.h (_bfd_generic_link_add_archive_symbols): Update.
+	* libbfd.h: Regenerate.
+
 2014-08-01  Takashi Yoshii  <yoshii.takashi@renesas.com>
 
 	PR 10373
diff --git a/bfd/aoutx.h b/bfd/aoutx.h
index 259c2bf..b28d6a1 100644
--- a/bfd/aoutx.h
+++ b/bfd/aoutx.h
@@ -3404,6 +3404,8 @@ aout_link_check_ar_symbols (bfd *abfd,
 static bfd_boolean
 aout_link_check_archive_element (bfd *abfd,
 				 struct bfd_link_info *info,
+				 struct bfd_link_hash_entry *h ATTRIBUTE_UNUSED,
+				 const char *name ATTRIBUTE_UNUSED,
 				 bfd_boolean *pneeded)
 {
   bfd *oldbfd;
diff --git a/bfd/cofflink.c b/bfd/cofflink.c
index d4e3345..8c3f71b 100644
--- a/bfd/cofflink.c
+++ b/bfd/cofflink.c
@@ -29,9 +29,11 @@
 #include "libcoff.h"
 #include "safe-ctype.h"
 
-static bfd_boolean coff_link_add_object_symbols (bfd *abfd, struct bfd_link_info *info);
-static bfd_boolean coff_link_check_archive_element (bfd *abfd, struct bfd_link_info *info, bfd_boolean *pneeded);
-static bfd_boolean coff_link_add_symbols (bfd *abfd, struct bfd_link_info *info);
+static bfd_boolean coff_link_add_object_symbols (bfd *, struct bfd_link_info *);
+static bfd_boolean coff_link_check_archive_element
+  (bfd *, struct bfd_link_info *, struct bfd_link_hash_entry *, const char *,
+   bfd_boolean *);
+static bfd_boolean coff_link_add_symbols (bfd *, struct bfd_link_info *);
 
 /* Return TRUE if SYM is a weak, external symbol.  */
 #define IS_WEAK_EXTERNAL(abfd, sym)			\
@@ -190,74 +192,6 @@ coff_link_add_object_symbols (bfd *abfd, struct bfd_link_info *info)
   return TRUE;
 }
 
-/* Look through the symbols to see if this object file should be
-   included in the link.  */
-
-static bfd_boolean
-coff_link_check_ar_symbols (bfd *abfd,
-			    struct bfd_link_info *info,
-			    bfd_boolean *pneeded,
-			    bfd **subsbfd)
-{
-  bfd_size_type symesz;
-  bfd_byte *esym;
-  bfd_byte *esym_end;
-
-  *pneeded = FALSE;
-
-  symesz = bfd_coff_symesz (abfd);
-  esym = (bfd_byte *) obj_coff_external_syms (abfd);
-  esym_end = esym + obj_raw_syment_count (abfd) * symesz;
-  while (esym < esym_end)
-    {
-      struct internal_syment sym;
-      enum coff_symbol_classification classification;
-
-      bfd_coff_swap_sym_in (abfd, esym, &sym);
-
-      classification = bfd_coff_classify_symbol (abfd, &sym);
-      if (classification == COFF_SYMBOL_GLOBAL
-	  || classification == COFF_SYMBOL_COMMON)
-	{
-	  const char *name;
-	  char buf[SYMNMLEN + 1];
-	  struct bfd_link_hash_entry *h;
-
-	  /* This symbol is externally visible, and is defined by this
-             object file.  */
-	  name = _bfd_coff_internal_syment_name (abfd, &sym, buf);
-	  if (name == NULL)
-	    return FALSE;
-	  h = bfd_link_hash_lookup (info->hash, name, FALSE, FALSE, TRUE);
-
-	  /* Auto import.  */
-	  if (!h
-	      && info->pei386_auto_import
-	      && CONST_STRNEQ (name, "__imp_"))
-	    h = bfd_link_hash_lookup (info->hash, name + 6, FALSE, FALSE, TRUE);
-
-	  /* We are only interested in symbols that are currently
-	     undefined.  If a symbol is currently known to be common,
-	     COFF linkers do not bring in an object file which defines
-	     it.  */
-	  if (h != (struct bfd_link_hash_entry *) NULL
-	      && h->type == bfd_link_hash_undefined)
-	    {
-	      if (!(*info->callbacks
-		    ->add_archive_element) (info, abfd, name, subsbfd))
-		return FALSE;
-	      *pneeded = TRUE;
-	      return TRUE;
-	    }
-	}
-
-      esym += (sym.n_numaux + 1) * symesz;
-    }
-
-  /* We do not need this object file.  */
-  return TRUE;
-}
-
 /* Check a single archive element to see if we need to include it in
    the link.  *PNEEDED is set according to whether this element is
    needed in the link or not.  This is called via
@@ -266,41 +200,23 @@ coff_link_check_ar_symbols (bfd *abfd,
 static bfd_boolean
 coff_link_check_archive_element (bfd *abfd,
 				 struct bfd_link_info *info,
+				 struct bfd_link_hash_entry *h,
+				 const char *name,
 				 bfd_boolean *pneeded)
 {
-  bfd *oldbfd;
-  bfd_boolean needed;
+  *pneeded = FALSE;
 
-  if (!_bfd_coff_get_external_symbols (abfd))
-    return FALSE;
+  /* We are only interested in symbols that are currently undefined.
+     If a symbol is currently known to be common, COFF linkers do not
+     bring in an object file which defines it.  */
+  if (h->type != bfd_link_hash_undefined)
+    return TRUE;
 
-  oldbfd = abfd;
-  if (!coff_link_check_ar_symbols (abfd, info, pneeded, &abfd))
+  if (!(*info->callbacks->add_archive_element) (info, abfd, name, &abfd))
     return FALSE;
+  *pneeded = TRUE;
 
-  needed = *pneeded;
-  if (needed)
-    {
-      /* Potentially, the add_archive_element hook may have set a
-	 substitute BFD for us.  */
-      if (abfd != oldbfd)
-	{
-	  if (!info->keep_memory
-	      && !_bfd_coff_free_symbols (oldbfd))
-	    return FALSE;
-	  if (!_bfd_coff_get_external_symbols (abfd))
-	    return FALSE;
-	}
-      if (!coff_link_add_symbols (abfd, info))
-	return FALSE;
-    }
-
-  if (!info->keep_memory || !needed)
-    {
-      if (!_bfd_coff_free_symbols (abfd))
-	return FALSE;
-    }
-  return TRUE;
+  return coff_link_add_object_symbols (abfd, info);
 }
 
 /* Add all the symbols from an object file to the hash table.  */
diff --git a/bfd/ecoff.c b/bfd/ecoff.c
index cf38e3e..6a9d206 100644
--- a/bfd/ecoff.c
+++ b/bfd/ecoff.c
@@ -3497,171 +3497,29 @@ ecoff_link_add_object_symbols (bfd *abfd, struct bfd_link_info *info)
   return FALSE;
 }
 
-/* Factored out from ecoff_link_check_archive_element.  */
-
-static bfd_boolean
-read_ext_syms_and_strs (HDRR **symhdr, bfd_size_type *external_ext_size,
-	bfd_size_type *esize, void **external_ext, char **ssext, bfd *abfd,
-	const struct ecoff_backend_data * const backend)
-{
-  if (! ecoff_slurp_symbolic_header (abfd))
-    return FALSE;
-
-  /* If there are no symbols, we don't want it.  */
-  if (bfd_get_symcount (abfd) == 0)
-    return TRUE;
-
-  *symhdr = &ecoff_data (abfd)->debug_info.symbolic_header;
-
-  *external_ext_size = backend->debug_swap.external_ext_size;
-  *esize = (*symhdr)->iextMax * *external_ext_size;
-  *external_ext = bfd_malloc (*esize);
-  if (*external_ext == NULL && *esize != 0)
-    return FALSE;
-
-  if (bfd_seek (abfd, (file_ptr) (*symhdr)->cbExtOffset, SEEK_SET) != 0
-      || bfd_bread (*external_ext, *esize, abfd) != *esize)
-    return FALSE;
-
-  *ssext = (char *) bfd_malloc ((bfd_size_type) (*symhdr)->issExtMax);
-  if (*ssext == NULL && (*symhdr)->issExtMax != 0)
-    return FALSE;
-
-  if (bfd_seek (abfd, (file_ptr) (*symhdr)->cbSsExtOffset, SEEK_SET) != 0
-      || (bfd_bread (*ssext, (bfd_size_type) (*symhdr)->issExtMax, abfd)
-	  != (bfd_size_type) (*symhdr)->issExtMax))
-    return FALSE;
-  return TRUE;
-}
-
-static bfd_boolean
-reread_ext_syms_and_strs (HDRR **symhdr, bfd_size_type *external_ext_size,
-	bfd_size_type *esize, void **external_ext, char **ssext, bfd *abfd,
-	const struct ecoff_backend_data * const backend)
-{
-  if (*external_ext != NULL)
-    free (*external_ext);
-  *external_ext = NULL;
-  if (*ssext != NULL)
-    free (*ssext);
-  *ssext = NULL;
-  return read_ext_syms_and_strs (symhdr, external_ext_size, esize,
-				external_ext, ssext, abfd, backend);
-}
-
 /* This is called if we used _bfd_generic_link_add_archive_symbols
    because we were not dealing with an ECOFF archive.  */
 
 static bfd_boolean
 ecoff_link_check_archive_element (bfd *abfd,
 				  struct bfd_link_info *info,
+				  struct bfd_link_hash_entry *h,
+				  const char *name,
 				  bfd_boolean *pneeded)
 {
-  const struct ecoff_backend_data * const backend = ecoff_backend (abfd);
-  void (* const swap_ext_in) (bfd *, void *, EXTR *)
-    = backend->debug_swap.swap_ext_in;
-  HDRR *symhdr;
-  bfd_size_type external_ext_size = 0;
-  void * external_ext = NULL;
-  bfd_size_type esize = 0;
-  char *ssext = NULL;
-  char *ext_ptr;
-  char *ext_end;
-
   *pneeded = FALSE;
 
-  /* Read in the external symbols and external strings.  */
-  if (!read_ext_syms_and_strs (&symhdr, &external_ext_size, &esize,
-	&external_ext, &ssext, abfd, backend))
-    goto error_return;
-
-  /* If there are no symbols, we don't want it.  */
-  if (bfd_get_symcount (abfd) == 0)
-    goto successful_return;
-
-  /* Look through the external symbols to see if they define some
-     symbol that is currently undefined.  */
-  ext_ptr = (char *) external_ext;
-  ext_end = ext_ptr + esize;
-  for (; ext_ptr < ext_end; ext_ptr += external_ext_size)
-    {
-      EXTR esym;
-      bfd_boolean def;
-      const char *name;
-      bfd *oldbfd;
-      struct bfd_link_hash_entry *h;
-
-      (*swap_ext_in) (abfd, (void *) ext_ptr, &esym);
-
-      /* See if this symbol defines something.  */
-      if (esym.asym.st != stGlobal
-	  && esym.asym.st != stLabel
-	  && esym.asym.st != stProc)
-	continue;
-
-      switch (esym.asym.sc)
-	{
-	case scText:
-	case scData:
-	case scBss:
-	case scAbs:
-	case scSData:
-	case scSBss:
-	case scRData:
-	case scCommon:
-	case scSCommon:
-	case scInit:
-	case scFini:
-	case scRConst:
-	  def = TRUE;
-	  break;
-	default:
-	  def = FALSE;
-	  break;
-	}
-
-      if (! def)
-	continue;
-
-      name = ssext + esym.asym.iss;
-      h = bfd_link_hash_lookup (info->hash, name, FALSE, FALSE, TRUE);
-
-      /* Unlike the generic linker, we do not pull in elements because
-	 of common symbols.  */
-      if (h == NULL
-	  || h->type != bfd_link_hash_undefined)
-	continue;
-
-      /* Include this element.  */
-      oldbfd = abfd;
-      if (!(*info->callbacks
-	    ->add_archive_element) (info, abfd, name, &abfd))
-	goto error_return;
-      /* Potentially, the add_archive_element hook may have set a
-	 substitute BFD for us.  */
-      if (abfd != oldbfd
-	  && !reread_ext_syms_and_strs (&symhdr, &external_ext_size, &esize,
-					&external_ext, &ssext, abfd, backend))
-	goto error_return;
-      if (! ecoff_link_add_externals (abfd, info, external_ext, ssext))
-	goto error_return;
+  /* Unlike the generic linker, we do not pull in elements because
+     of common symbols.  */
+  if (h->type != bfd_link_hash_undefined)
+    return TRUE;
 
-      *pneeded = TRUE;
-      goto successful_return;
-    }
+  /* Include this element.  */
+  if (!(*info->callbacks->add_archive_element) (info, abfd, name, &abfd))
+    return FALSE;
+  *pneeded = TRUE;
 
- successful_return:
-  if (external_ext != NULL)
-    free (external_ext);
-  if (ssext != NULL)
-    free (ssext);
-  return TRUE;
- error_return:
-  if (external_ext != NULL)
-    free (external_ext);
-  if (ssext != NULL)
-    free (ssext);
-  return FALSE;
+  return ecoff_link_add_object_symbols (abfd, info);
 }
 
 /* Add the symbols from an archive file to the global hash table.
diff --git a/bfd/elflink.c b/bfd/elflink.c
index f8a2208..69a87a6 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -2931,13 +2931,6 @@ elf_link_is_defined_archive_symbol (bfd * abfd, carsym * symdef)
   if (! bfd_check_format (abfd, bfd_object))
     return FALSE;
 
-  /* If we have already included the element containing this symbol in the
-     link then we do not need to include it again.  Just claim that any symbol
-     it contains is not a definition, so that our caller will not decide to
-     (re)include this element.  */
-  if (abfd->archive_pass)
-    return FALSE;
-
   /* Select the appropriate symbol table.  */
   if ((abfd->flags & DYNAMIC) == 0 || elf_dynsymtab (abfd) == 0)
     hdr = &elf_tdata (abfd)->symtab_hdr;
@@ -4928,20 +4921,8 @@ _bfd_elf_archive_symbol_lookup (bfd *abfd,
 }
 
 /* Add symbols from an ELF archive file to the linker hash table.  We
-   don't use _bfd_generic_link_add_archive_symbols because of a
-   problem which arises on UnixWare.  The UnixWare libc.so is an
-   archive which includes an entry libc.so.1 which defines a bunch of
-   symbols.  The libc.so archive also includes a number of other
-   object files, which also define symbols, some of which are the same
-   as those defined in libc.so.1.  Correct linking requires that we
-   consider each object file in turn, and include it if it defines any
-   symbols we need.  _bfd_generic_link_add_archive_symbols does not do
-   this; it looks through the list of undefined symbols, and includes
-   any object file which defines them.  When this algorithm is used on
-   UnixWare, it winds up pulling in libc.so.1 early and defining a
-   bunch of symbols.  This means that some of the other objects in the
-   archive are not included in the link, which is incorrect since they
-   precede libc.so.1 in the archive.
+   don't use _bfd_generic_link_add_archive_symbols because we need to
+   handle versioned symbols.
 
    Fortunately, ELF archive handling is simpler than that done by
    _bfd_generic_link_add_archive_symbols, which has to allow for a.out
@@ -4956,8 +4937,7 @@ static bfd_boolean
 elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
 {
   symindex c;
-  bfd_boolean *defined = NULL;
-  bfd_boolean *included = NULL;
+  unsigned char *included = NULL;
   carsym *symdefs;
   bfd_boolean loop;
   bfd_size_type amt;
@@ -4981,11 +4961,10 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
   if (c == 0)
     return TRUE;
   amt = c;
-  amt *= sizeof (bfd_boolean);
-  defined = (bfd_boolean *) bfd_zmalloc (amt);
-  included = (bfd_boolean *) bfd_zmalloc (amt);
-  if (defined == NULL || included == NULL)
-    goto error_return;
+  amt *= sizeof (*included);
+  included = (unsigned char *) bfd_zmalloc (amt);
+  if (included == NULL)
+    return FALSE;
 
   symdefs = bfd_ardata (abfd)->symdefs;
   bed = get_elf_backend_data (abfd);
@@ -5010,7 +4989,7 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
 	  struct bfd_link_hash_entry *undefs_tail;
 	  symindex mark;
 
-	  if (defined[i] || included[i])
+	  if (included[i])
 	    continue;
 	  if (symdef->file_offset == last)
 	    {
@@ -5045,7 +5024,8 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
 	  else if (h->root.type != bfd_link_hash_undefined)
 	    {
 	      if (h->root.type != bfd_link_hash_undefweak)
-		defined[i] = TRUE;
+		/* Symbol must be defined.  Don't check it again.  */
+		included[i] = TRUE;
 	      continue;
 	    }
 
@@ -5057,16 +5037,6 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
 	  if (! bfd_check_format (element, bfd_object))
 	    goto error_return;
 
-	  /* Doublecheck that we have not included this object
-	     already--it should be impossible, but there may be
-	     something wrong with the archive.  */
-	  if (element->archive_pass != 0)
-	    {
-	      bfd_set_error (bfd_error_bad_value);
-	      goto error_return;
-	    }
-	  element->archive_pass = 1;
-
 	  undefs_tail = info->hash->undefs_tail;
 
 	  if (!(*info->callbacks
@@ -5104,14 +5074,11 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
     }
   while (loop);
 
-  free (defined);
   free (included);
 
   return TRUE;
 
  error_return:
-  if (defined != NULL)
-    free (defined);
   if (included != NULL)
     free (included);
   return FALSE;
diff --git a/bfd/libbfd-in.h b/bfd/libbfd-in.h
index 03dbd0a..5eb06c3 100644
--- a/bfd/libbfd-in.h
+++ b/bfd/libbfd-in.h
@@ -603,7 +603,9 @@ extern bfd_boolean _bfd_generic_link_add_symbols_collect
 /* Generic archive add symbol routine.  */
 extern bfd_boolean _bfd_generic_link_add_archive_symbols
   (bfd *, struct bfd_link_info *,
-   bfd_boolean (*) (bfd *, struct bfd_link_info *, bfd_boolean *));
+   bfd_boolean (*) (bfd *, struct bfd_link_info *,
+		    struct bfd_link_hash_entry *, const char *,
+		    bfd_boolean *));
 
 /* Forward declaration to avoid prototype errors.  */
 typedef struct bfd_link_hash_entry _bfd_link_hash_entry;
diff --git a/bfd/libbfd.h b/bfd/libbfd.h
index 3cca8c9..f759a0a 100644
--- a/bfd/libbfd.h
+++ b/bfd/libbfd.h
@@ -608,7 +608,9 @@ extern bfd_boolean _bfd_generic_link_add_symbols_collect
 /* Generic archive add symbol routine.  */
 extern bfd_boolean _bfd_generic_link_add_archive_symbols
   (bfd *, struct bfd_link_info *,
-   bfd_boolean (*) (bfd *, struct bfd_link_info *, bfd_boolean *));
+   bfd_boolean (*) (bfd *, struct bfd_link_info *,
+		    struct bfd_link_hash_entry *, const char *,
+		    bfd_boolean *));
 
 /* Forward declaration to avoid prototype errors.  */
 typedef struct bfd_link_hash_entry _bfd_link_hash_entry;
diff --git a/bfd/linker.c b/bfd/linker.c
index 5ad7988..a31e473 100644
--- a/bfd/linker.c
+++ b/bfd/linker.c
@@ -229,28 +229,16 @@ SUBSUBSECTION
 @findex _bfd_generic_link_add_archive_symbols
 	In most cases the work of looking through the symbols in the
 	archive should be done by the
-	<<_bfd_generic_link_add_archive_symbols>> function.  This
-	function builds a hash table from the archive symbol table and
-	looks through the list of undefined symbols to see which
-	elements should be included.
+	<<_bfd_generic_link_add_archive_symbols>> function.
 	<<_bfd_generic_link_add_archive_symbols>> is passed a function
 	to call to make the final decision about adding an archive
 	element to the link and to do the actual work of adding the
-	symbols to the linker hash table.
-
-	The function passed to
-	<<_bfd_generic_link_add_archive_symbols>> must read the
-	symbols of the archive element and decide whether the archive
-	element should be included in the link.  If the element is to
+	symbols to the linker hash table.  If the element is to
 	be included, the <<add_archive_element>> linker callback
 	routine must be called with the element as an argument, and
 	the element's symbols must be added to the linker hash table
 	just as though the element had itself been passed to the
-	<<_bfd_link_add_symbols>> function.  The <<add_archive_element>>
-	callback has the option to indicate that it would like to
-	replace the element archive with a substitute BFD, in which
-	case it is the symbols of that substitute BFD that must be
-	added to the linker hash table instead.
+	<<_bfd_link_add_symbols>> function.
 
 	When the a.out <<_bfd_link_add_symbols>> function receives an
 	archive, it calls <<_bfd_generic_link_add_archive_symbols>>
@@ -419,11 +407,14 @@ static bfd_boolean generic_link_add_object_symbols
 static bfd_boolean generic_link_add_symbols
   (bfd *, struct bfd_link_info *, bfd_boolean);
 static bfd_boolean generic_link_check_archive_element_no_collect
-  (bfd *, struct bfd_link_info *, bfd_boolean *);
+  (bfd *, struct bfd_link_info *, struct bfd_link_hash_entry *, const char *,
+   bfd_boolean *);
 static bfd_boolean generic_link_check_archive_element_collect
-  (bfd *, struct bfd_link_info *, bfd_boolean *);
+  (bfd *, struct bfd_link_info *, struct bfd_link_hash_entry *, const char *,
+   bfd_boolean *);
 static bfd_boolean generic_link_check_archive_element
-  (bfd *, struct bfd_link_info *, bfd_boolean *, bfd_boolean);
+  (bfd *, struct bfd_link_info *, struct bfd_link_hash_entry *, const char *,
+   bfd_boolean *, bfd_boolean);
 static bfd_boolean generic_link_add_symbol_list
   (bfd *, struct bfd_link_info *, bfd_size_type count, asymbol **,
    bfd_boolean);
@@ -917,138 +908,32 @@ generic_link_add_object_symbols (bfd *abfd,
   return generic_link_add_symbol_list (abfd, info, symcount, outsyms, collect);
 }
 
-/* We build a hash table of all symbols defined in an archive.  */
-
-/* An archive symbol may be defined by multiple archive elements.
-   This linked list is used to hold the elements.  */
-
-struct archive_list
-{
-  struct archive_list *next;
-  unsigned int indx;
-};
-
-/* An entry in an archive hash table.  */
-
-struct archive_hash_entry
-{
-  struct bfd_hash_entry root;
-  /* Where the symbol is defined.  */
-  struct archive_list *defs;
-};
-
-/* An archive hash table itself.  */
-
-struct archive_hash_table
-{
-  struct bfd_hash_table table;
-};
-
-/* Create a new entry for an archive hash table.  */
-
-static struct bfd_hash_entry *
-archive_hash_newfunc (struct bfd_hash_entry *entry,
-		      struct bfd_hash_table *table,
-		      const char *string)
-{
-  struct archive_hash_entry *ret = (struct archive_hash_entry *) entry;
-
-  /* Allocate the structure if it has not already been allocated by a
-     subclass.  */
-  if (ret == NULL)
-    ret = (struct archive_hash_entry *)
-        bfd_hash_allocate (table, sizeof (struct archive_hash_entry));
-  if (ret == NULL)
-    return NULL;
-
-  /* Call the allocation method of the superclass.  */
-  ret = ((struct archive_hash_entry *)
-	 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
-
-  if (ret)
-    {
-      /* Initialize the local fields.  */
-      ret->defs = NULL;
-    }
-
-  return &ret->root;
-}
-
-/* Initialize an archive hash table.  */
-
-static bfd_boolean
-archive_hash_table_init
-  (struct archive_hash_table *table,
-   struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
-				      struct bfd_hash_table *,
-				      const char *),
-   unsigned int entsize)
-{
-  return bfd_hash_table_init (&table->table, newfunc, entsize);
-}
-
-/* Look up an entry in an archive hash table.  */
-
-#define archive_hash_lookup(t, string, create, copy) \
-  ((struct archive_hash_entry *) \
-   bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
-
-/* Allocate space in an archive hash table.  */
-
-#define archive_hash_allocate(t, size) bfd_hash_allocate (&(t)->table, (size))
-
-/* Free an archive hash table.  */
-
-#define archive_hash_table_free(t) bfd_hash_table_free (&(t)->table)
-
 /* Generic function to add symbols from an archive file to the global
    hash file.  This function presumes that the archive symbol table
    has already been read in (this is normally done by the
-   bfd_check_format entry point).  It looks through the undefined and
-   common symbols and searches the archive symbol table for them.  If
-   it finds an entry, it includes the associated object file in the
-   link.
-
-   The old linker looked through the archive symbol table for
-   undefined symbols.  We do it the other way around, looking through
-   undefined symbols for symbols defined in the archive.  The
-   advantage of the newer scheme is that we only have to look through
-   the list of undefined symbols once, whereas the old method had to
-   re-search the symbol table each time a new object file was added.
-
-   The CHECKFN argument is used to see if an object file should be
-   included.  CHECKFN should set *PNEEDED to TRUE if the object file
-   should be included, and must also call the bfd_link_info
-   add_archive_element callback function and handle adding the symbols
-   to the global hash table.  CHECKFN must notice if the callback
-   indicates a substitute BFD, and arrange to add those symbols instead
-   if it does so.  CHECKFN should only return FALSE if some sort of
-   error occurs.
-
-   For some formats, such as a.out, it is possible to look through an
-   object file but not actually include it in the link.  The
-   archive_pass field in a BFD is used to avoid checking the symbols
-   of an object files too many times.  When an object is included in
-   the link, archive_pass is set to -1.  If an object is scanned but
-   not included, archive_pass is set to the pass number.  The pass
-   number is incremented each time a new object file is included.  The
-   pass number is used because when a new object file is included it
-   may create new undefined symbols which cause a previously examined
-   object file to be included.  */
+   bfd_check_format entry point).  It looks through the archive symbol
+   table for symbols that are undefined or common in the linker global
+   symbol hash table.  When one is found, the CHECKFN argument is used
+   to see if an object file should be included.  This allows targets
+   to customize common symbol behaviour.  CHECKFN should set *PNEEDED
+   to TRUE if the object file should be included, and must also call
+   the bfd_link_info add_archive_element callback function and handle
+   adding the symbols to the global hash table.  CHECKFN must notice
+   if the callback indicates a substitute BFD, and arrange to add
+   those symbols instead if it does so.  CHECKFN should only return
+   FALSE if some sort of error occurs.  */
 
 bfd_boolean
 _bfd_generic_link_add_archive_symbols
   (bfd *abfd,
    struct bfd_link_info *info,
-   bfd_boolean (*checkfn) (bfd *, struct bfd_link_info *, bfd_boolean *))
+   bfd_boolean (*checkfn) (bfd *, struct bfd_link_info *,
+			   struct bfd_link_hash_entry *, const char *,
+			   bfd_boolean *))
 {
-  carsym *arsyms;
-  carsym *arsym_end;
-  register carsym *arsym;
-  int pass;
-  struct archive_hash_table arsym_hash;
-  unsigned int indx;
-  struct bfd_link_hash_entry **pundef;
+  bfd_boolean loop;
+  bfd_size_type amt;
+  unsigned char *included;
 
   if (! bfd_has_map (abfd))
     {
@@ -1059,148 +944,103 @@ _bfd_generic_link_add_archive_symbols
       return FALSE;
     }
 
-  arsyms = bfd_ardata (abfd)->symdefs;
-  arsym_end = arsyms + bfd_ardata (abfd)->symdef_count;
-
-  /* In order to quickly determine whether an symbol is defined in
-     this archive, we build a hash table of the symbols.  */
-  if (! archive_hash_table_init (&arsym_hash, archive_hash_newfunc,
-				 sizeof (struct archive_hash_entry)))
+  amt = bfd_ardata (abfd)->symdef_count;
+  if (amt == 0)
+    return TRUE;
+  amt *= sizeof (*included);
+  included = (unsigned char *) bfd_zmalloc (amt);
+  if (included == NULL)
     return FALSE;
-  for (arsym = arsyms, indx = 0; arsym < arsym_end; arsym++, indx++)
-    {
-      struct archive_hash_entry *arh;
-      struct archive_list *l, **pp;
-
-      arh = archive_hash_lookup (&arsym_hash, arsym->name, TRUE, FALSE);
-      if (arh == NULL)
-	goto error_return;
-      l = ((struct archive_list *)
-	   archive_hash_allocate (&arsym_hash, sizeof (struct archive_list)));
-      if (l == NULL)
-	goto error_return;
-      l->indx = indx;
-      for (pp = &arh->defs; *pp != NULL; pp = &(*pp)->next)
-	;
-      *pp = l;
-      l->next = NULL;
-    }
-
-  /* The archive_pass field in the archive itself is used to
-     initialize PASS, sine we may search the same archive multiple
-     times.  */
-  pass = abfd->archive_pass + 1;
 
-  /* New undefined symbols are added to the end of the list, so we
-     only need to look through it once.  */
-  pundef = &info->hash->undefs;
-  while (*pundef != NULL)
+  do
     {
-      struct bfd_link_hash_entry *h;
-      struct archive_hash_entry *arh;
-      struct archive_list *l;
-
-      h = *pundef;
-
-      /* When a symbol is defined, it is not necessarily removed from
-	 the list.  */
-      if (h->type != bfd_link_hash_undefined
-	  && h->type != bfd_link_hash_common)
+      carsym *arsyms;
+      carsym *arsym_end;
+      carsym *arsym;
+      unsigned int indx;
+      file_ptr last_ar_offset = -1;
+      bfd_boolean needed = FALSE;
+      bfd *element = NULL;
+
+      loop = FALSE;
+      arsyms = bfd_ardata (abfd)->symdefs;
+      arsym_end = arsyms + bfd_ardata (abfd)->symdef_count;
+      for (arsym = arsyms, indx = 0; arsym < arsym_end; arsym++, indx++)
 	{
-	  /* Remove this entry from the list, for general cleanliness
-	     and because we are going to look through the list again
-	     if we search any more libraries.  We can't remove the
-	     entry if it is the tail, because that would lose any
-	     entries we add to the list later on (it would also cause
-	     us to lose track of whether the symbol has been
-	     referenced).  */
-	  if (*pundef != info->hash->undefs_tail)
-	    *pundef = (*pundef)->u.undef.next;
-	  else
-	    pundef = &(*pundef)->u.undef.next;
-	  continue;
-	}
-
-      /* Look for this symbol in the archive symbol map.  */
-      arh = archive_hash_lookup (&arsym_hash, h->root.string, FALSE, FALSE);
-      if (arh == NULL)
-	{
-	  /* If we haven't found the exact symbol we're looking for,
-	     let's look for its import thunk */
-	  if (info->pei386_auto_import)
-	    {
-	      bfd_size_type amt = strlen (h->root.string) + 10;
-	      char *buf = (char *) bfd_malloc (amt);
-	      if (buf == NULL)
-		return FALSE;
+	  struct bfd_link_hash_entry *h;
+	  struct bfd_link_hash_entry *undefs_tail;
 
-	      sprintf (buf, "__imp_%s", h->root.string);
-	      arh = archive_hash_lookup (&arsym_hash, buf, FALSE, FALSE);
-	      free(buf);
-	    }
-	  if (arh == NULL)
+	  if (included[indx])
+	    continue;
+	  if (needed && arsym->file_offset == last_ar_offset)
 	    {
-	      pundef = &(*pundef)->u.undef.next;
+	      included[indx] = 1;
 	      continue;
 	    }
-	}
-      /* Look at all the objects which define this symbol.  */
-      for (l = arh->defs; l != NULL; l = l->next)
-	{
-	  bfd *element;
-	  bfd_boolean needed;
-
-	  /* If the symbol has gotten defined along the way, quit.  */
-	  if (h->type != bfd_link_hash_undefined
-	      && h->type != bfd_link_hash_common)
-	    break;
 
-	  element = bfd_get_elt_at_index (abfd, l->indx);
-	  if (element == NULL)
-	    goto error_return;
+	  h = bfd_link_hash_lookup (info->hash, arsym->name,
+				    FALSE, FALSE, TRUE);
 
-	  /* If we've already included this element, or if we've
-	     already checked it on this pass, continue.  */
-	  if (element->archive_pass == -1
-	      || element->archive_pass == pass)
+	  if (h == NULL
+	      && info->pei386_auto_import
+	      && CONST_STRNEQ (arsym->name, "__imp_"))
+	    h = bfd_link_hash_lookup (info->hash, arsym->name + 6,
+				      FALSE, FALSE, TRUE);
+	  if (h == NULL)
 	    continue;
 
-	  /* If we can't figure this element out, just ignore it.  */
-	  if (! bfd_check_format (element, bfd_object))
+	  if (h->type != bfd_link_hash_undefined
+	      && h->type != bfd_link_hash_common)
 	    {
-	      element->archive_pass = -1;
+	      if (h->type != bfd_link_hash_undefweak)
+		/* Symbol must be defined.  Don't check it again.  */
+		included[indx] = 1;
 	      continue;
 	    }
 
+	  if (last_ar_offset != arsym->file_offset)
+	    {
+	      last_ar_offset = arsym->file_offset;
+	      element = _bfd_get_elt_at_filepos (abfd, last_ar_offset);
+	      if (element == NULL
+		  || !bfd_check_format (element, bfd_object))
+		goto error_return;
+	    }
+
+	  undefs_tail = info->hash->undefs_tail;
+
 	  /* CHECKFN will see if this element should be included, and
 	     go ahead and include it if appropriate.  */
-	  if (! (*checkfn) (element, info, &needed))
+	  if (! (*checkfn) (element, info, h, arsym->name, &needed))
 	    goto error_return;
 
-	  if (! needed)
-	    element->archive_pass = pass;
-	  else
+	  if (needed)
 	    {
-	      element->archive_pass = -1;
+	      unsigned int mark;
 
-	      /* Increment the pass count to show that we may need to
-		 recheck object files which were already checked.  */
-	      ++pass;
+	      /* Look backward to mark all symbols from this object file
+		 which we have already seen in this pass.  */
+	      mark = indx;
+	      do
+		{
+		  included[mark] = 1;
+		  if (mark == 0)
+		    break;
+		  --mark;
+		}
+	      while (arsyms[mark].file_offset == last_ar_offset);
+
+	      if (undefs_tail != info->hash->undefs_tail)
+		loop = TRUE;
 	    }
 	}
+    } while (loop);
 
-      pundef = &(*pundef)->u.undef.next;
-    }
-
-  archive_hash_table_free (&arsym_hash);
-
-  /* Save PASS in case we are called again.  */
-  abfd->archive_pass = pass;
-
+  free (included);
   return TRUE;
 
  error_return:
-  archive_hash_table_free (&arsym_hash);
+  free (included);
   return FALSE;
 }
 
@@ -1210,12 +1050,14 @@ _bfd_generic_link_add_archive_symbols
    for finding them.  */
 
 static bfd_boolean
-generic_link_check_archive_element_no_collect (
-					       bfd *abfd,
+generic_link_check_archive_element_no_collect (bfd *abfd,
 					       struct bfd_link_info *info,
+					       struct bfd_link_hash_entry *h,
+					       const char *name,
 					       bfd_boolean *pneeded)
 {
-  return generic_link_check_archive_element (abfd, info, pneeded, FALSE);
+  return generic_link_check_archive_element (abfd, info, h, name, pneeded,
+					     FALSE);
 }
 
 /* See if we should include an archive element.  This version is used
@@ -1225,9 +1067,12 @@ generic_link_check_archive_element_no_collect (
 static bfd_boolean
 generic_link_check_archive_element_collect (bfd *abfd,
 					    struct bfd_link_info *info,
+					    struct bfd_link_hash_entry *h,
+					    const char *name,
 					    bfd_boolean *pneeded)
 {
-  return generic_link_check_archive_element (abfd, info, pneeded, TRUE);
+  return generic_link_check_archive_element (abfd, info, h, name, pneeded,
+					     TRUE);
 }
 
 /* See if we should include an archive element.  Optionally collect
@@ -1236,6 +1081,8 @@ generic_link_check_archive_element_collect (bfd *abfd,
 static bfd_boolean
 generic_link_check_archive_element (bfd *abfd,
 				    struct bfd_link_info *info,
+				    struct bfd_link_hash_entry *h,
+				    const char *name ATTRIBUTE_UNUSED,
 				    bfd_boolean *pneeded,
 				    bfd_boolean collect)
 {
@@ -1251,7 +1098,6 @@ generic_link_check_archive_element (bfd *abfd,
   for (; pp < ppend; pp++)
     {
       asymbol *p;
-      struct bfd_link_hash_entry *h;
 
       p = *pp;
 
diff --git a/bfd/pdp11.c b/bfd/pdp11.c
index 8999af2..8bce865 100644
--- a/bfd/pdp11.c
+++ b/bfd/pdp11.c
@@ -251,7 +251,7 @@ HOWTO( 1,	       0,  1,  16,  TRUE,  0, complain_overflow_signed,0,"DISP16",	TRU
 #define TABLE_SIZE(TABLE)	(sizeof(TABLE)/sizeof(TABLE[0]))
 
 
-static bfd_boolean aout_link_check_archive_element (bfd *, struct bfd_link_info *, bfd_boolean *);
+static bfd_boolean aout_link_check_archive_element (bfd *, struct bfd_link_info *, struct bfd_link_hash_entry *, const char *, bfd_boolean *);
 static bfd_boolean aout_link_add_object_symbols    (bfd *, struct bfd_link_info *);
 static bfd_boolean aout_link_add_symbols           (bfd *, struct bfd_link_info *);
 static bfd_boolean aout_link_write_symbols         (struct aout_final_link_info *, bfd *);
@@ -2679,6 +2679,8 @@ aout_link_check_ar_symbols (bfd *abfd,
 static bfd_boolean
 aout_link_check_archive_element (bfd *abfd,
 				 struct bfd_link_info *info,
+				 struct bfd_link_hash_entry *h ATTRIBUTE_UNUSED,
+				 const char *name ATTRIBUTE_UNUSED,
 				 bfd_boolean *pneeded)
 {
   bfd *oldbfd;
diff --git a/bfd/xcofflink.c b/bfd/xcofflink.c
index 67e1c52..1ca9c2e 100644
--- a/bfd/xcofflink.c
+++ b/bfd/xcofflink.c
@@ -2384,6 +2384,8 @@ xcoff_link_check_ar_symbols (bfd *abfd,
 static bfd_boolean
 xcoff_link_check_archive_element (bfd *abfd,
 				  struct bfd_link_info *info,
+				  struct bfd_link_hash_entry *h ATTRIBUTE_UNUSED,
+				  const char *name ATTRIBUTE_UNUSED,
 				  bfd_boolean *pneeded)
 {
   bfd_boolean keep_syms_p;
@@ -2463,7 +2465,7 @@ _bfd_xcoff_bfd_link_add_symbols (bfd *abfd, struct bfd_link_info *info)
 		bfd_boolean needed;
 
 		if (! xcoff_link_check_archive_element (member, info,
-							&needed))
+							NULL, NULL, &needed))
 		  return FALSE;
 		if (needed)
 		  member->archive_pass = -1;