Re: RFC: [PATCH] PR ld/18028: 32-bit ld runs out of memory when linking 32-bit clang with debug info

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Fri, Feb 27, 2015 at 8:35 PM, Alan Modra <amodra@gmail.com> wrote:
> On Fri, Feb 27, 2015 at 04:10:54PM -0800, H.J. Lu wrote:
>> I compared the time of linking cc1plus in GCC 5 on Linux/x86-64
>> with 24 GB RAM:
>
> The numbers you or I get are irrelevant.  We both have fast modern
> machines and a modern operating system that caches disk reads.  The
> whole world isn't Linux.
>

Here is a different approach.  I keep track of allocated memory in bfd
and disable bfd cache when total allocated memory > 2GB on 32-bit
hosts. The run-time overhead of linking cc1plus in GCC 5 is

before:

[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/build-i686-linux/ld/ld-new `cat xx`
4.34user 0.40system 0:04.76elapsed 99%CPU (0avgtext+0avgdata 339700maxresident)k
0inputs+182664outputs (0major+189286minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/build-i686-linux/ld/ld-new `cat xx`
4.33user 0.39system 0:04.73elapsed 99%CPU (0avgtext+0avgdata 339680maxresident)k
0inputs+182664outputs (0major+189293minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/build-i686-linux/ld/ld-new `cat xx`
4.46user 0.38system 0:04.85elapsed 99%CPU (0avgtext+0avgdata 339708maxresident)k
0inputs+182664outputs (0major+189699minor)pagefaults 0swaps

after:

[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/release/usr/local/bin/ld  `cat xx`
4.36user 0.37system 0:04.74elapsed 99%CPU (0avgtext+0avgdata 339780maxresident)k
0inputs+182664outputs (0major+189080minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/release/usr/local/bin/ld  `cat xx`
4.36user 0.41system 0:04.78elapsed 99%CPU (0avgtext+0avgdata 339764maxresident)k
0inputs+182664outputs (0major+189001minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/release/usr/local/bin/ld  `cat xx`
4.38user 0.39system 0:04.78elapsed 99%CPU (0avgtext+0avgdata 339720maxresident)k
0inputs+182664outputs (0major+188950minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$ /bin/time
/export/build/gnu/binutils-32bit/release/usr/local/bin/ld  `cat xx`
4.39user 0.38system 0:04.78elapsed 99%CPU (0avgtext+0avgdata 339764maxresident)k
0inputs+182664outputs (0major+188986minor)pagefaults 0swaps
[hjl@gnu-mic-2 gcc]$

Difference is very small.

-- 
H.J.

From fef8138022873e34fc3655ae365558557c9a7cab Mon Sep 17 00:00:00 2001
From: "H.J. Lu" <hjl.tools@gmail.com>
Date: Fri, 20 Mar 2015 11:25:15 -0700
Subject: [PATCH] Limit memory size to half of address space

When link_info.keep_memory is TRUE, linker caches the relocation
information and symbol tables of input files in memory.  On 32-bit
hosts, linker runs out of 32-bit virtual memory on input files with many
relocations.  This patch limits the allocated memory size to half of
the address space for 32-bit hosts.

bfd/

	PR ld/18028
	* bfd-in.h (_bfd_link_keep_memory): New.
	* bfd-in2.h: Regenerated.
	* bfd.c (bfd): Add alloc_size.
	* elf-bfd.h (_bfd_elf_link_info_read_relocs): New.
	* elf32-i386.c (elf_i386_convert_mov_to_lea): Call
	_bfd_elf_link_info_read_relocs instead of
	_bfd_elf_link_read_relocs.  Use _bfd_link_keep_memory.  Update
	cache_size.
	* elf64-x86-64.c (elf_x86_64_convert_mov_to_lea): Call
	_bfd_elf_link_info_read_relocs instead of
	_bfd_elf_link_read_relocs.  Use _bfd_link_keep_memory.  Update
	cache_size.
	* elflink.c (_bfd_elf_link_read_relocs): Renamed to ...
	(_bfd_elf_link_info_read_relocs): This.  Update cache_size.
	(_bfd_elf_link_read_relocs): New.
	(elf_link_add_object_symbols): Call _bfd_elf_link_info_read_relocs
	instead of _bfd_elf_link_read_relocs.
	(elf_link_input_bfd): Likewise.
	(elf_gc_sweep): Likewise.
	(bfd_elf_final_link): Update cache_size.
	(init_reloc_cookie): Update cache_size.  Call
	_bfd_elf_link_info_read_relocs instead of
	_bfd_elf_link_read_relocs.
	(link_info_ok): New.
	(elf_gc_smash_unused_vtentry_relocs): Updated.  Call
	_bfd_elf_link_info_read_relocs instead of
	_bfd_elf_link_read_relocs.
	(bfd_elf_gc_sections): Use link_info_ok.  Pass &link_info_ok
	to elf_gc_smash_unused_vtentry_relocs.
	* linker.c (_bfd_link_keep_memory): New.
	* opncls.c (bfd_alloc): Update alloc_size.

include/

	PR ld/18028
	* bfdlink.h (bfd_link_info): Add cache_size and max_alloc_size.

ld/

	PR ld/18028
	* ldmain.c: Include "bfd_stdint.h".
	(main): Set link_info.max_alloc_size to half of the address space.
---
 bfd/bfd-in.h       |  2 ++
 bfd/bfd-in2.h      |  5 +++
 bfd/bfd.c          |  3 ++
 bfd/elf-bfd.h      |  3 ++
 bfd/elf32-i386.c   |  9 +++---
 bfd/elf64-x86-64.c |  9 +++---
 bfd/elflink.c      | 90 ++++++++++++++++++++++++++++++++++++++++--------------
 bfd/linker.c       | 33 ++++++++++++++++++++
 bfd/opncls.c       |  2 ++
 include/bfdlink.h  |  7 +++++
 ld/ldmain.c        |  3 ++
 11 files changed, 135 insertions(+), 31 deletions(-)

diff --git a/bfd/bfd-in.h b/bfd/bfd-in.h
index cbd0465..ed3ee9a 100644
--- a/bfd/bfd-in.h
+++ b/bfd/bfd-in.h
@@ -564,6 +564,8 @@ struct bfd_section_already_linked;
 struct bfd_elf_version_tree;
 #endif
 
+extern bfd_boolean _bfd_link_keep_memory (struct bfd_link_info *);
+
 extern bfd_boolean bfd_section_already_linked_table_init (void);
 extern void bfd_section_already_linked_table_free (void);
 extern bfd_boolean _bfd_handle_already_linked
diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h
index e170dd9..427987a 100644
--- a/bfd/bfd-in2.h
+++ b/bfd/bfd-in2.h
@@ -571,6 +571,8 @@ struct bfd_section_already_linked;
 struct bfd_elf_version_tree;
 #endif
 
+extern bfd_boolean _bfd_link_keep_memory (struct bfd_link_info *);
+
 extern bfd_boolean bfd_section_already_linked_table_init (void);
 extern void bfd_section_already_linked_table_free (void);
 extern bfd_boolean _bfd_handle_already_linked
@@ -6483,6 +6485,9 @@ struct bfd
      be used only for archive elements.  */
   int archive_pass;
 
+  /* The total size of memory from bfd_alloc.  */
+  bfd_size_type alloc_size;
+
   /* Stuff only useful for object files:
      The start address.  */
   bfd_vma start_address;
diff --git a/bfd/bfd.c b/bfd/bfd.c
index 5ae5eca..30dc262 100644
--- a/bfd/bfd.c
+++ b/bfd/bfd.c
@@ -245,6 +245,9 @@ CODE_FRAGMENT
 .     be used only for archive elements.  *}
 .  int archive_pass;
 .
+.  {* The total size of memory from bfd_alloc.  *}
+.  bfd_size_type alloc_size;
+.
 .  {* Stuff only useful for object files:
 .     The start address.  *}
 .  bfd_vma start_address;
diff --git a/bfd/elf-bfd.h b/bfd/elf-bfd.h
index 13c32e0..985c46e 100644
--- a/bfd/elf-bfd.h
+++ b/bfd/elf-bfd.h
@@ -2031,6 +2031,9 @@ extern char *_bfd_elfcore_strndup
 
 extern Elf_Internal_Rela *_bfd_elf_link_read_relocs
   (bfd *, asection *, void *, Elf_Internal_Rela *, bfd_boolean);
+extern Elf_Internal_Rela *_bfd_elf_link_info_read_relocs
+  (bfd *, struct bfd_link_info *, asection *, void *, Elf_Internal_Rela *,
+   bfd_boolean);
 
 extern bfd_boolean _bfd_elf_link_output_relocs
   (bfd *, asection *, Elf_Internal_Shdr *, Elf_Internal_Rela *,
diff --git a/bfd/elf32-i386.c b/bfd/elf32-i386.c
index 52f4d33..31c23aa 100644
--- a/bfd/elf32-i386.c
+++ b/bfd/elf32-i386.c
@@ -2653,9 +2653,9 @@ elf_i386_convert_mov_to_lea (bfd *abfd, asection *sec,
   symtab_hdr = &elf_tdata (abfd)->symtab_hdr;
 
   /* Load the relocations for this section.  */
-  internal_relocs = (_bfd_elf_link_read_relocs
-		     (abfd, sec, NULL, (Elf_Internal_Rela *) NULL,
-		      link_info->keep_memory));
+  internal_relocs = (_bfd_elf_link_info_read_relocs
+		     (abfd, link_info, sec, NULL, NULL,
+		      _bfd_link_keep_memory (link_info)));
   if (internal_relocs == NULL)
     return FALSE;
 
@@ -2741,12 +2741,13 @@ elf_i386_convert_mov_to_lea (bfd *abfd, asection *sec,
   if (contents != NULL
       && elf_section_data (sec)->this_hdr.contents != contents)
     {
-      if (!changed_contents && !link_info->keep_memory)
+      if (!changed_contents && !_bfd_link_keep_memory (link_info))
 	free (contents);
       else
 	{
 	  /* Cache the section contents for elf_link_input_bfd.  */
 	  elf_section_data (sec)->this_hdr.contents = contents;
+	  link_info->cache_size += sec->size;
 	}
     }
 
diff --git a/bfd/elf64-x86-64.c b/bfd/elf64-x86-64.c
index 74d1d06..d2a3c47 100644
--- a/bfd/elf64-x86-64.c
+++ b/bfd/elf64-x86-64.c
@@ -2903,9 +2903,9 @@ elf_x86_64_convert_mov_to_lea (bfd *abfd, asection *sec,
   symtab_hdr = &elf_tdata (abfd)->symtab_hdr;
 
   /* Load the relocations for this section.  */
-  internal_relocs = (_bfd_elf_link_read_relocs
-		     (abfd, sec, NULL, (Elf_Internal_Rela *) NULL,
-		      link_info->keep_memory));
+  internal_relocs = (_bfd_elf_link_info_read_relocs
+		     (abfd, link_info, sec, NULL, NULL,
+		      _bfd_link_keep_memory (link_info)));
   if (internal_relocs == NULL)
     return FALSE;
 
@@ -2992,12 +2992,13 @@ elf_x86_64_convert_mov_to_lea (bfd *abfd, asection *sec,
   if (contents != NULL
       && elf_section_data (sec)->this_hdr.contents != contents)
     {
-      if (!changed_contents && !link_info->keep_memory)
+      if (!changed_contents && !_bfd_link_keep_memory (link_info))
 	free (contents);
       else
 	{
 	  /* Cache the section contents for elf_link_input_bfd.  */
 	  elf_section_data (sec)->this_hdr.contents = contents;
+	  link_info->cache_size += sec->size;
 	}
     }
 
diff --git a/bfd/elflink.c b/bfd/elflink.c
index f93293b..9bb32d7 100644
--- a/bfd/elflink.c
+++ b/bfd/elflink.c
@@ -2162,14 +2162,16 @@ elf_link_read_relocs_from_section (bfd *abfd,
    according to the KEEP_MEMORY argument.  If O has two relocation
    sections (both REL and RELA relocations), then the REL_HDR
    relocations will appear first in INTERNAL_RELOCS, followed by the
-   RELA_HDR relocations.  */
+   RELA_HDR relocations.  If INFO isn't NULL and KEEP_MEMORY is TRUE,
+   update cache_size.  */
 
 Elf_Internal_Rela *
-_bfd_elf_link_read_relocs (bfd *abfd,
-			   asection *o,
-			   void *external_relocs,
-			   Elf_Internal_Rela *internal_relocs,
-			   bfd_boolean keep_memory)
+_bfd_elf_link_info_read_relocs (bfd *abfd,
+				struct bfd_link_info *info,
+				asection *o,
+				void *external_relocs,
+				Elf_Internal_Rela *internal_relocs,
+				bfd_boolean keep_memory)
 {
   void *alloc1 = NULL;
   Elf_Internal_Rela *alloc2 = NULL;
@@ -2190,7 +2192,11 @@ _bfd_elf_link_read_relocs (bfd *abfd,
       size = o->reloc_count;
       size *= bed->s->int_rels_per_ext_rel * sizeof (Elf_Internal_Rela);
       if (keep_memory)
-	internal_relocs = alloc2 = (Elf_Internal_Rela *) bfd_alloc (abfd, size);
+	{
+	  internal_relocs = alloc2 = (Elf_Internal_Rela *) bfd_alloc (abfd, size);
+	  if (info)
+	    info->cache_size += size;
+	}
       else
 	internal_relocs = alloc2 = (Elf_Internal_Rela *) bfd_malloc (size);
       if (internal_relocs == NULL)
@@ -2256,6 +2262,22 @@ _bfd_elf_link_read_relocs (bfd *abfd,
   return NULL;
 }
 
+/* This is similar to _bfd_elf_link_info_read_relocs, except for that
+   NULL is passed to _bfd_elf_link_info_read_relocs for pointer to
+   struct bfd_link_info.  */
+
+Elf_Internal_Rela *
+_bfd_elf_link_read_relocs (bfd *abfd,
+			   asection *o,
+			   void *external_relocs,
+			   Elf_Internal_Rela *internal_relocs,
+			   bfd_boolean keep_memory)
+{
+  return _bfd_elf_link_info_read_relocs (abfd, NULL, o, external_relocs,
+					 internal_relocs, keep_memory);
+
+}
+
 /* Compute the size of, and allocate space for, REL_HDR which is the
    section header for a section containing relocations for O.  */
 
@@ -4806,8 +4828,10 @@ error_free_dyn:
 	      || bfd_is_abs_section (o->output_section))
 	    continue;
 
-	  internal_relocs = _bfd_elf_link_read_relocs (abfd, o, NULL, NULL,
-						       info->keep_memory);
+	  internal_relocs = _bfd_elf_link_info_read_relocs (abfd, info,
+							    o, NULL,
+							    NULL,
+							    _bfd_link_keep_memory (info));
 	  if (internal_relocs == NULL)
 	    goto error_return;
 
@@ -9717,8 +9741,10 @@ elf_link_input_bfd (struct elf_final_link_info *flinfo, bfd *input_bfd)
 
 	  /* Get the swapped relocs.  */
 	  internal_relocs
-	    = _bfd_elf_link_read_relocs (input_bfd, o, flinfo->external_relocs,
-					 flinfo->internal_relocs, FALSE);
+	    = _bfd_elf_link_info_read_relocs (input_bfd, flinfo->info, o,
+					      flinfo->external_relocs,
+					      flinfo->internal_relocs,
+					      FALSE);
 	  if (internal_relocs == NULL
 	      && o->reloc_count > 0)
 	    return FALSE;
@@ -10902,13 +10928,14 @@ bfd_elf_final_link (bfd *abfd, struct bfd_link_info *info)
 
   /* Allocate a buffer to hold swapped out symbols.  This is to avoid
      continuously seeking to the right position in the file.  */
-  if (! info->keep_memory || max_sym_count < 20)
+  if (! _bfd_link_keep_memory (info) || max_sym_count < 20)
     flinfo.symbuf_size = 20;
   else
     flinfo.symbuf_size = max_sym_count;
   amt = flinfo.symbuf_size;
   amt *= bed->s->sizeof_sym;
   flinfo.symbuf = (bfd_byte *) bfd_malloc (amt);
+  info->cache_size += amt;
   if (flinfo.symbuf == NULL)
     goto error_return;
   if (elf_numsections (abfd) > (SHN_LORESERVE & 0xFFFF))
@@ -11695,8 +11722,12 @@ init_reloc_cookie (struct elf_reloc_cookie *cookie,
 	  info->callbacks->einfo (_("%P%X: can not read symbols: %E\n"));
 	  return FALSE;
 	}
-      if (info->keep_memory)
-	symtab_hdr->contents = (bfd_byte *) cookie->locsyms;
+      if (_bfd_link_keep_memory (info) )
+	{
+	  symtab_hdr->contents = (bfd_byte *) cookie->locsyms;
+	  info->cache_size += (cookie->locsymcount
+			       * sizeof (Elf_External_Sym_Shndx));
+	}
     }
   return TRUE;
 }
@@ -11733,8 +11764,9 @@ init_reloc_cookie_rels (struct elf_reloc_cookie *cookie,
     {
       bed = get_elf_backend_data (abfd);
 
-      cookie->rels = _bfd_elf_link_read_relocs (abfd, sec, NULL, NULL,
-						info->keep_memory);
+      cookie->rels = _bfd_elf_link_info_read_relocs (abfd, info, sec,
+						     NULL, NULL,
+						     _bfd_link_keep_memory (info));
       if (cookie->rels == NULL)
 	return FALSE;
       cookie->rel = cookie->rels;
@@ -12202,8 +12234,9 @@ elf_gc_sweep (bfd *abfd, struct bfd_link_info *info)
 	      bfd_boolean r;
 
 	      internal_relocs
-		= _bfd_elf_link_read_relocs (o->owner, o, NULL, NULL,
-					     info->keep_memory);
+		= _bfd_elf_link_info_read_relocs (o->owner, info, o,
+						  NULL, NULL,
+						  _bfd_link_keep_memory (info));
 	      if (internal_relocs == NULL)
 		return FALSE;
 
@@ -12288,14 +12321,21 @@ elf_gc_propagate_vtable_entries_used (struct elf_link_hash_entry *h, void *okp)
   return TRUE;
 }
 
+struct link_info_ok
+{
+  struct bfd_link_info *info;
+  bfd_boolean ok;
+};
+
 static bfd_boolean
-elf_gc_smash_unused_vtentry_relocs (struct elf_link_hash_entry *h, void *okp)
+elf_gc_smash_unused_vtentry_relocs (struct elf_link_hash_entry *h, void *ptr)
 {
   asection *sec;
   bfd_vma hstart, hend;
   Elf_Internal_Rela *relstart, *relend, *rel;
   const struct elf_backend_data *bed;
   unsigned int log_file_align;
+  struct link_info_ok *info = (struct link_info_ok *) ptr;
 
   /* Take care of both those symbols that do not describe vtables as
      well as those that are not loaded.  */
@@ -12309,9 +12349,10 @@ elf_gc_smash_unused_vtentry_relocs (struct elf_link_hash_entry *h, void *okp)
   hstart = h->root.u.def.value;
   hend = hstart + h->size;
 
-  relstart = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL, TRUE);
+  relstart = _bfd_elf_link_info_read_relocs (sec->owner, info->info,
+					     sec, NULL, NULL, TRUE);
   if (!relstart)
-    return *(bfd_boolean *) okp = FALSE;
+    return info->ok = FALSE;
   bed = get_elf_backend_data (sec->owner);
   log_file_align = bed->s->log_file_align;
 
@@ -12397,6 +12438,7 @@ bfd_elf_gc_sections (bfd *abfd, struct bfd_link_info *info)
   elf_gc_mark_hook_fn gc_mark_hook;
   const struct elf_backend_data *bed = get_elf_backend_data (abfd);
   struct elf_link_hash_table *htab;
+  struct link_info_ok info_ok;
 
   if (!bed->can_gc_sections
       || !is_elf_hash_table (info->hash))
@@ -12433,8 +12475,10 @@ bfd_elf_gc_sections (bfd *abfd, struct bfd_link_info *info)
     return FALSE;
 
   /* Kill the vtable relocations that were not used.  */
-  elf_link_hash_traverse (htab, elf_gc_smash_unused_vtentry_relocs, &ok);
-  if (!ok)
+  info_ok.info = info;
+  info_ok.ok = TRUE;
+  elf_link_hash_traverse (htab, elf_gc_smash_unused_vtentry_relocs, &info_ok);
+  if (!info_ok.ok)
     return FALSE;
 
   /* Mark dynamically referenced symbols.  */
diff --git a/bfd/linker.c b/bfd/linker.c
index dec6d1d..479b028 100644
--- a/bfd/linker.c
+++ b/bfd/linker.c
@@ -3303,3 +3303,36 @@ bfd_hide_sym_by_version (struct bfd_elf_version_tree *verdefs,
   bfd_find_version_for_sym (verdefs, sym_name, &hidden);
   return hidden;
 }
+
+bfd_boolean
+_bfd_link_keep_memory (struct bfd_link_info * info)
+{
+  bfd *abfd;
+  bfd_size_type size;
+
+  if (!info->keep_memory || !info->max_alloc_size)
+    return FALSE;
+
+  /* Keep allocated memory size below limit only for 32-bit hosts.  */
+  if (sizeof (void *) > 4)
+    return TRUE;
+
+  abfd = info->input_bfds;
+  size = info->cache_size;
+  do
+    {
+      if (size >= info->max_alloc_size)
+	{
+	  /* Over the limit.  Reduce the memory usage.  */
+	  info->max_alloc_size = 0;
+	  return FALSE;
+	}
+      if (!abfd)
+	break;
+      size += abfd->alloc_size;
+      abfd = abfd->link.next;
+    }
+  while (1);
+
+  return TRUE;
+}
diff --git a/bfd/opncls.c b/bfd/opncls.c
index f0f2e64..a783848 100644
--- a/bfd/opncls.c
+++ b/bfd/opncls.c
@@ -958,6 +958,8 @@ bfd_alloc (bfd *abfd, bfd_size_type size)
   ret = objalloc_alloc ((struct objalloc *) abfd->memory, ul_size);
   if (ret == NULL)
     bfd_set_error (bfd_error_no_memory);
+  else
+    abfd->alloc_size += size;
   return ret;
 }
 
diff --git a/include/bfdlink.h b/include/bfdlink.h
index 6a02a3c..a99e3ba 100644
--- a/include/bfdlink.h
+++ b/include/bfdlink.h
@@ -544,6 +544,13 @@ struct bfd_link_info
 
   /* The version information.  */
   struct bfd_elf_version_tree *version_info;
+
+  /* Size of cache.  Backend can use it to keep strace cache size.   */
+  bfd_size_type cache_size;
+
+  /* The maximum size of allocated memory.  Backend can use cache_size
+     and and max_alloc_size to decide if keep_memory should be honored.  */
+  bfd_size_type max_alloc_size;
 };
 
 /* This structures holds a set of callback functions.  These are called
diff --git a/ld/ldmain.c b/ld/ldmain.c
index 6674a80..be85295 100644
--- a/ld/ldmain.c
+++ b/ld/ldmain.c
@@ -21,6 +21,7 @@
 
 #include "sysdep.h"
 #include "bfd.h"
+#include "bfd_stdint.h"
 #include "safe-ctype.h"
 #include "libiberty.h"
 #include "progress.h"
@@ -275,6 +276,8 @@ main (int argc, char **argv)
 
   link_info.allow_undefined_version = TRUE;
   link_info.keep_memory = TRUE;
+  /* Limit the allocated memory size to half of the address space.  */
+  link_info.max_alloc_size = ((uintptr_t) (void *) -1) / 2;
   link_info.combreloc = TRUE;
   link_info.strip_discarded = TRUE;
   link_info.emit_hash = TRUE;
-- 
1.9.3