2013-04-26 Geoff Pike <gpike@chromium.org>

gold/
	* gold.cc (queue_final_tasks): invoke layout->queue_build_id_tasks().
	* layout.cc (Hash_task): New class.
	(Layout::queue_build_id_tasks): New function.
	(Layout::write_build_id): Handle single-thread portion of build ID
	computation.  (In some cases, all of it is single-threaded.)  Replace
	{sha1,md5}_process_bytes with {sha1,md5}_buffer to get the same
	functionality in fewer lines of code.
	* layout.h (Layout::queue_build_id_tasks): New function declaration.
	* options.h (General_options): make "--build-id" default to tree
	rather than sha1.  Add two new options related to --build-id=tree:
	--build-id-chunk-size-for-treehash and
	--build-id-min-file-size-for-treehash.
	* Makefile.am: add testing of --build-id=tree and related new options
	(these tests will be invoked by "make check").
	* Makefile.in: Regenerate.

7 files changed, 309 insertions, 34 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index 9fd5ded4cf..c7dad99cbd 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,21 @@
+2013-04-26  Geoff Pike  <gpike@chromium.org>
+
+	* gold.cc (queue_final_tasks): invoke layout->queue_build_id_tasks().
+	* layout.cc (Hash_task): New class.
+	(Layout::queue_build_id_tasks): New function.
+	(Layout::write_build_id): Handle single-thread portion of build ID
+	computation.  (In some cases, all of it is single-threaded.)  Replace
+	{sha1,md5}_process_bytes with {sha1,md5}_buffer to get the same
+	functionality in fewer lines of code.
+	* layout.h (Layout::queue_build_id_tasks): New function declaration.
+	* options.h (General_options): make "--build-id" default to tree
+	rather than sha1.  Add two new options related to --build-id=tree:
+	--build-id-chunk-size-for-treehash and
+	--build-id-min-file-size-for-treehash.
+	* Makefile.am: add testing of --build-id=tree and related new options
+	(these tests will be invoked by "make check").
+	* Makefile.in: Regenerate.
+
 2013-04-25  Alan Modra  <amodra@gmail.com>
 
 	* configure.tgt: Add powerpcle and powerpc64le.
diff --git a/gold/Makefile.am b/gold/Makefile.am
index f6ced44c7e..8e2fff1027 100644
--- a/gold/Makefile.am
+++ b/gold/Makefile.am
@@ -269,7 +269,7 @@ ld2_LDFLAGS = -Bgcctestdir2/
 bootstrap-test: ld2
 	rm -f $@
 	echo "#!/bin/sh" > $@
-	echo "cmp ld1 ld2" > $@
+	echo "cmp ld1 ld2" >> $@
 	chmod +x $@
 
 libgold-1-r.o: gcctestdir1/ld libgold.a
@@ -296,11 +296,68 @@ ld2_r_LDFLAGS = -Bgcctestdir2-r/
 bootstrap-test-r: ld2-r
 	rm -f $@
 	echo "#!/bin/sh" > $@
-	echo "cmp ld1-r ld2-r" > $@
+	echo "cmp ld1-r ld2-r" >> $@
 	chmod +x $@
 
 check_PROGRAMS = ld1 ld2 ld1-r ld2-r
 TESTS = bootstrap-test bootstrap-test-r
 
+# Verify that changing the number of threads doesn't change the
+# treehash computation, by building ld1 and ld3 the same way except
+# for the number of threads.  However, the build ID should change if
+# we change the chunk size for --build-id=tree, so ld4 should be
+# different.  We run the latter test even if multithreading is unavailable,
+# because the treehash can still operate in that mode.
+check_PROGRAMS += ld4
+TESTS += bootstrap-test-treehash-chunksize
+
+gcctestdir3/ld: ld-new
+	test -d gcctestdir3 || mkdir -p gcctestdir3
+	rm -f gcctestdir3/ld
+	(cd gcctestdir3 && $(LN_S) ../ld-new ld)
+
+ld3_SOURCES = $(sources_var)
+ld3_DEPENDENCIES = $(deps_var) gcctestdir3/ld
+ld3_LDADD = $(ldadd_var)
+ld3_LDFLAGS = -Bgcctestdir3/
+
+gcctestdir4/ld: ld-new
+	test -d gcctestdir4 || mkdir -p gcctestdir4
+	rm -f gcctestdir4/ld
+	(cd gcctestdir4 && $(LN_S) ../ld-new ld)
+
+ld4_SOURCES = $(sources_var)
+ld4_DEPENDENCIES = $(deps_var) gcctestdir4/ld
+ld4_LDADD = $(ldadd_var)
+ld4_LDFLAGS = -Bgcctestdir4/
+
+ld1_LDFLAGS += -Wl,--build-id=tree -Wl,--build-id-chunk-size-for-treehash=12345 -Wl,--build-id-min-file-size-for-treehash=0
+ld2_LDFLAGS += -Wl,--build-id=tree -Wl,--build-id-chunk-size-for-treehash=12345 -Wl,--build-id-min-file-size-for-treehash=0
+ld3_LDFLAGS += -Wl,--build-id=tree -Wl,--build-id-chunk-size-for-treehash=12345 -Wl,--build-id-min-file-size-for-treehash=0
+ld4_LDFLAGS += -Wl,--build-id=tree -Wl,--build-id-chunk-size-for-treehash=12346 -Wl,--build-id-min-file-size-for-treehash=0
+
+if THREADS
+
+ld1_LDFLAGS += -Wl,--thread-count=3
+ld2_LDFLAGS += -Wl,--thread-count=3
+ld3_LDFLAGS += -Wl,--thread-count=13
+ld4_LDFLAGS += -Wl,--thread-count=3
+check_PROGRAMS += ld3
+TESTS += bootstrap-test-treehash-chunksize
+
+bootstrap-test-treehash: ld1 ld3
+	rm -f $@
+	echo "#!/bin/sh" > $@
+	echo "cmp ld1 ld3" >> $@
+	chmod +x $@
+
+endif
+
+bootstrap-test-treehash-chunksize: ld1 ld4
+	rm -f $@
+	echo "#!/bin/sh" > $@
+	echo "cmp ld1 ld4 | grep ." >> $@
+	chmod +x $@
+
 endif
 endif
diff --git a/gold/Makefile.in b/gold/Makefile.in
index f12832b17d..5c4c4d6f70 100644
--- a/gold/Makefile.in
+++ b/gold/Makefile.in
@@ -59,7 +59,14 @@ bin_PROGRAMS = dwp$(EXEEXT)
 noinst_PROGRAMS = ld-new$(EXEEXT) incremental-dump$(EXEEXT)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@check_PROGRAMS = ld1$(EXEEXT) \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	ld2$(EXEEXT) ld1-r$(EXEEXT) \
-@GCC_TRUE@@NATIVE_LINKER_TRUE@	ld2-r$(EXEEXT)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	ld2-r$(EXEEXT) ld4$(EXEEXT) \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__EXEEXT_1)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_1 = -Wl,--thread-count=3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_2 = -Wl,--thread-count=3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_3 = -Wl,--thread-count=13
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_4 = -Wl,--thread-count=3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_5 = ld3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__append_6 = bootstrap-test-treehash-chunksize
 subdir = .
 DIST_COMMON = NEWS README ChangeLog $(srcdir)/Makefile.in \
 	$(srcdir)/Makefile.am $(top_srcdir)/configure \
@@ -114,6 +121,8 @@ am_libgold_a_OBJECTS = $(am__objects_1) $(am__objects_2) \
 	$(am__objects_3) $(am__objects_2)
 libgold_a_OBJECTS = $(am_libgold_a_OBJECTS)
 am__installdirs = "$(DESTDIR)$(bindir)"
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@am__EXEEXT_1 =  \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@	ld3$(EXEEXT)
 PROGRAMS = $(bin_PROGRAMS) $(noinst_PROGRAMS)
 am_dwp_OBJECTS = dwp.$(OBJEXT)
 dwp_OBJECTS = $(am_dwp_OBJECTS)
@@ -146,6 +155,14 @@ ld2_LINK = $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(ld2_LDFLAGS) \
 ld2_r_OBJECTS = $(am_ld2_r_OBJECTS)
 ld2_r_LINK = $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(ld2_r_LDFLAGS) \
 	$(LDFLAGS) -o $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@am_ld3_OBJECTS = $(am__objects_4)
+ld3_OBJECTS = $(am_ld3_OBJECTS)
+ld3_LINK = $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(ld3_LDFLAGS) \
+	$(LDFLAGS) -o $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@am_ld4_OBJECTS = $(am__objects_4)
+ld4_OBJECTS = $(am_ld4_OBJECTS)
+ld4_LINK = $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(ld4_LDFLAGS) \
+	$(LDFLAGS) -o $@
 DEFAULT_INCLUDES = -I.@am__isrc@
 depcomp = $(SHELL) $(top_srcdir)/../depcomp
 am__depfiles_maybe = depfiles
@@ -165,7 +182,7 @@ YLWRAP = $(top_srcdir)/../ylwrap
 SOURCES = $(libgold_a_SOURCES) $(dwp_SOURCES) \
 	$(incremental_dump_SOURCES) $(ld_new_SOURCES) \
 	$(EXTRA_ld_new_SOURCES) $(ld1_SOURCES) $(ld1_r_SOURCES) \
-	$(ld2_SOURCES) $(ld2_r_SOURCES)
+	$(ld2_SOURCES) $(ld2_r_SOURCES) $(ld3_SOURCES) $(ld4_SOURCES)
 RECURSIVE_TARGETS = all-recursive check-recursive dvi-recursive \
 	html-recursive info-recursive install-data-recursive \
 	install-dvi-recursive install-exec-recursive \
@@ -550,11 +567,19 @@ POTFILES = $(CCFILES) $(HFILES) $(TARGETSOURCES)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_SOURCES = $(sources_var)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_DEPENDENCIES = $(deps_var) gcctestdir1/ld
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_LDADD = $(ldadd_var)
-@GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_LDFLAGS = -Bgcctestdir1/
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_LDFLAGS = -Bgcctestdir1/ \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id=tree \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-chunk-size-for-treehash=12345 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-min-file-size-for-treehash=0 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__append_1)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_SOURCES = $(sources_var)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_DEPENDENCIES = $(deps_var) gcctestdir2/ld
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_LDADD = $(ldadd_var)
-@GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_LDFLAGS = -Bgcctestdir2/
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_LDFLAGS = -Bgcctestdir2/ \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id=tree \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-chunk-size-for-treehash=12345 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-min-file-size-for-treehash=0 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__append_2)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_r_SOURCES = $(sources_var)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_r_DEPENDENCIES = libgold-1-r.o $(deps_var) gcctestdir1/ld
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld1_r_LDADD = libgold-1-r.o $(ldadd_var)
@@ -563,7 +588,25 @@ POTFILES = $(CCFILES) $(HFILES) $(TARGETSOURCES)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_r_DEPENDENCIES = libgold-2-r.o $(deps_var) gcctestdir2-r/ld
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_r_LDADD = libgold-2-r.o $(ldadd_var)
 @GCC_TRUE@@NATIVE_LINKER_TRUE@ld2_r_LDFLAGS = -Bgcctestdir2-r/
-@GCC_TRUE@@NATIVE_LINKER_TRUE@TESTS = bootstrap-test bootstrap-test-r
+@GCC_TRUE@@NATIVE_LINKER_TRUE@TESTS = bootstrap-test bootstrap-test-r \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	bootstrap-test-treehash-chunksize \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__append_6)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld3_SOURCES = $(sources_var)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld3_DEPENDENCIES = $(deps_var) gcctestdir3/ld
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld3_LDADD = $(ldadd_var)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld3_LDFLAGS = -Bgcctestdir3/ \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id=tree \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-chunk-size-for-treehash=12345 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-min-file-size-for-treehash=0 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__append_3)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld4_SOURCES = $(sources_var)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld4_DEPENDENCIES = $(deps_var) gcctestdir4/ld
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld4_LDADD = $(ldadd_var)
+@GCC_TRUE@@NATIVE_LINKER_TRUE@ld4_LDFLAGS = -Bgcctestdir4/ \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id=tree \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-chunk-size-for-treehash=12346 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	-Wl,--build-id-min-file-size-for-treehash=0 \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(am__append_4)
 all: config.h
 	$(MAKE) $(AM_MAKEFLAGS) all-recursive
 
@@ -698,6 +741,12 @@ ld2$(EXEEXT): $(ld2_OBJECTS) $(ld2_DEPENDENCIES)
 ld2-r$(EXEEXT): $(ld2_r_OBJECTS) $(ld2_r_DEPENDENCIES) 
 	@rm -f ld2-r$(EXEEXT)
 	$(ld2_r_LINK) $(ld2_r_OBJECTS) $(ld2_r_LDADD) $(LIBS)
+ld3$(EXEEXT): $(ld3_OBJECTS) $(ld3_DEPENDENCIES) 
+	@rm -f ld3$(EXEEXT)
+	$(ld3_LINK) $(ld3_OBJECTS) $(ld3_LDADD) $(LIBS)
+ld4$(EXEEXT): $(ld4_OBJECTS) $(ld4_DEPENDENCIES) 
+	@rm -f ld4$(EXEEXT)
+	$(ld4_LINK) $(ld4_OBJECTS) $(ld4_LDADD) $(LIBS)
 
 mostlyclean-compile:
 	-rm -f *.$(OBJEXT)
@@ -1089,6 +1138,8 @@ bootstrap-test.log: bootstrap-test
 	@p='bootstrap-test'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
 bootstrap-test-r.log: bootstrap-test-r
 	@p='bootstrap-test-r'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
+bootstrap-test-treehash-chunksize.log: bootstrap-test-treehash-chunksize
+	@p='bootstrap-test-treehash-chunksize'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
 .test.log:
 	@p='$<'; $(am__check_pre) $(TEST_LOG_COMPILE) "$$tst" $(am__check_post)
 @am__EXEEXT_TRUE@.test$(EXEEXT).log:
@@ -1285,7 +1336,7 @@ po/POTFILES.in: @MAINT@ Makefile
 @GCC_TRUE@@NATIVE_LINKER_TRUE@bootstrap-test: ld2
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	rm -f $@
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "#!/bin/sh" > $@
-@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "cmp ld1 ld2" > $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "cmp ld1 ld2" >> $@
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	chmod +x $@
 
 @GCC_TRUE@@NATIVE_LINKER_TRUE@libgold-1-r.o: gcctestdir1/ld libgold.a
@@ -1302,7 +1353,29 @@ po/POTFILES.in: @MAINT@ Makefile
 @GCC_TRUE@@NATIVE_LINKER_TRUE@bootstrap-test-r: ld2-r
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	rm -f $@
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "#!/bin/sh" > $@
-@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "cmp ld1-r ld2-r" > $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "cmp ld1-r ld2-r" >> $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	chmod +x $@
+
+@GCC_TRUE@@NATIVE_LINKER_TRUE@gcctestdir3/ld: ld-new
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	test -d gcctestdir3 || mkdir -p gcctestdir3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	rm -f gcctestdir3/ld
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	(cd gcctestdir3 && $(LN_S) ../ld-new ld)
+
+@GCC_TRUE@@NATIVE_LINKER_TRUE@gcctestdir4/ld: ld-new
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	test -d gcctestdir4 || mkdir -p gcctestdir4
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	rm -f gcctestdir4/ld
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	(cd gcctestdir4 && $(LN_S) ../ld-new ld)
+
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@bootstrap-test-treehash: ld1 ld3
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@	rm -f $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@	echo "#!/bin/sh" > $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@	echo "cmp ld1 ld3" >> $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@@THREADS_TRUE@	chmod +x $@
+
+@GCC_TRUE@@NATIVE_LINKER_TRUE@bootstrap-test-treehash-chunksize: ld1 ld4
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	rm -f $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "#!/bin/sh" > $@
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	echo "cmp ld1 ld4 | grep ." >> $@
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	chmod +x $@
 
 # Tell versions [3.59,3.63) of GNU make to not export all variables.
diff --git a/gold/gold.cc b/gold/gold.cc
index d26dc2e6f5..4de9289b4d 100644
--- a/gold/gold.cc
+++ b/gold/gold.cc
@@ -874,6 +874,9 @@ queue_final_tasks(const General_options& options,
       final_blocker = new_final_blocker;
     }
 
+  // Create tasks for tree-style build ID computation, if necessary.
+  final_blocker = layout->queue_build_id_tasks(workqueue, final_blocker, of);
+
   // Queue a task to close the output file.  This will be blocked by
   // FINAL_BLOCKER.
   workqueue->queue(new Task_function(new Close_task_runner(&options, layout,
diff --git a/gold/layout.cc b/gold/layout.cc
index 13f57cb82f..b593acdb0b 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -236,6 +236,54 @@ Free_list::print_stats()
 	  program_name, Free_list::num_allocate_visits);
 }
 
+// A Hash_task computes the MD5 checksum of an array of char.
+// It has a blocker on either side (i.e., the task cannot run until
+// the first is unblocked, and it unblocks the second after running).
+
+class Hash_task : public Task
+{
+ public:
+  Hash_task(const unsigned char* src,
+            size_t size,
+            unsigned char* dst,
+            Task_token* build_id_blocker,
+            Task_token* final_blocker)
+    : src_(src), size_(size), dst_(dst), build_id_blocker_(build_id_blocker),
+      final_blocker_(final_blocker)
+  { }
+
+  void
+  run(Workqueue*)
+  { md5_buffer(reinterpret_cast<const char*>(src_), size_, dst_); }
+
+  Task_token*
+  is_runnable();
+
+  // Unblock FINAL_BLOCKER_ when done.
+  void
+  locks(Task_locker* tl)
+  { tl->add(this, this->final_blocker_); }
+
+  std::string
+  get_name() const
+  { return "Hash_task"; }
+
+ private:
+  const unsigned char* const src_;
+  const size_t size_;
+  unsigned char* const dst_;
+  Task_token* const build_id_blocker_;
+  Task_token* const final_blocker_;
+};
+
+Task_token*
+Hash_task::is_runnable()
+{
+  if (this->build_id_blocker_->is_blocked())
+    return this->build_id_blocker_;
+  return NULL;
+}
+
 // Layout::Relaxation_debug_check methods.
 
 // Check that sections and special data are in reset states.
@@ -398,6 +446,9 @@ Layout::Layout(int number_of_input_files, Script_options* script_options)
     eh_frame_hdr_section_(NULL),
     gdb_index_data_(NULL),
     build_id_note_(NULL),
+    array_of_hashes_(NULL),
+    size_of_array_of_hashes_(0),
+    input_view_(NULL),
     debug_abbrev_(NULL),
     debug_info_(NULL),
     group_signatures_(),
@@ -2924,7 +2975,7 @@ Layout::create_build_id()
   std::string desc;
   if (strcmp(style, "md5") == 0)
     descsz = 128 / 8;
-  else if (strcmp(style, "sha1") == 0)
+  else if ((strcmp(style, "sha1") == 0) || (strcmp(style, "tree") == 0))
     descsz = 160 / 8;
   else if (strcmp(style, "uuid") == 0)
     {
@@ -5212,9 +5263,53 @@ Layout::write_sections_after_input_sections(Output_file* of)
   this->section_headers_->write(of);
 }
 
-// If the build ID requires computing a checksum, do so here, and
-// write it out.  We compute a checksum over the entire file because
-// that is simplest.
+// Build IDs can be computed as a "flat" sha1 or md5 of a string of bytes,
+// or as a "tree" where each chunk of the string is hashed and then those
+// hashes are put into a (much smaller) string which is hashed with sha1.
+// We compute a checksum over the entire file because that is simplest.
+
+Task_token*
+Layout::queue_build_id_tasks(Workqueue* workqueue, Task_token* build_id_blocker,
+                             Output_file* of)
+{
+  const size_t filesize = (this->output_file_size() <= 0 ? 0
+                           : static_cast<size_t>(this->output_file_size()));
+  if (this->build_id_note_ != NULL
+      && strcmp(parameters->options().build_id(), "tree") == 0
+      && parameters->options().build_id_chunk_size_for_treehash() > 0
+      && filesize > 0
+      && (filesize >=
+          parameters->options().build_id_min_file_size_for_treehash()))
+    {
+      static const size_t MD5_OUTPUT_SIZE_IN_BYTES = 16;
+      const size_t chunk_size =
+          parameters->options().build_id_chunk_size_for_treehash();
+      const size_t num_hashes = ((filesize - 1) / chunk_size) + 1;
+      Task_token* post_hash_tasks_blocker = new Task_token(true);
+      post_hash_tasks_blocker->add_blockers(num_hashes);
+      this->size_of_array_of_hashes_ = num_hashes * MD5_OUTPUT_SIZE_IN_BYTES;
+      const unsigned char* src = of->get_input_view(0, filesize);
+      this->input_view_ = src;
+      unsigned char *dst = new unsigned char[this->size_of_array_of_hashes_];
+      this->array_of_hashes_ = dst;
+      for (size_t i = 0, src_offset = 0; i < num_hashes;
+           i++, dst += MD5_OUTPUT_SIZE_IN_BYTES, src_offset += chunk_size)
+        {
+          size_t size = std::min(chunk_size, filesize - src_offset);
+          workqueue->queue(new Hash_task(src + src_offset,
+                                         size,
+                                         dst,
+                                         build_id_blocker,
+                                         post_hash_tasks_blocker));
+        }
+      return post_hash_tasks_blocker;
+    }
+  return build_id_blocker;
+}
+
+// If a tree-style build ID was requested, the parallel part of that computation
+// is already done, and the final hash-of-hashes is computed here.  For other
+// types of build IDs, all the work is done here.
 
 void
 Layout::write_build_id(Output_file* of) const
@@ -5222,34 +5317,39 @@ Layout::write_build_id(Output_file* of) const
   if (this->build_id_note_ == NULL)
     return;
 
-  const unsigned char* iv = of->get_input_view(0, this->output_file_size_);
-
   unsigned char* ov = of->get_output_view(this->build_id_note_->offset(),
-					  this->build_id_note_->data_size());
+                                          this->build_id_note_->data_size());
 
-  const char* style = parameters->options().build_id();
-  if (strcmp(style, "sha1") == 0)
+  if (this->array_of_hashes_ == NULL)
     {
-      sha1_ctx ctx;
-      sha1_init_ctx(&ctx);
-      sha1_process_bytes(iv, this->output_file_size_, &ctx);
-      sha1_finish_ctx(&ctx, ov);
+      const size_t output_file_size = this->output_file_size();
+      const unsigned char* iv = of->get_input_view(0, output_file_size);
+      const char* style = parameters->options().build_id();
+
+      // If we get here with style == "tree" then the output must be
+      // too small for chunking, and we use SHA-1 in that case.
+      if ((strcmp(style, "sha1") == 0) || (strcmp(style, "tree") == 0))
+        sha1_buffer(reinterpret_cast<const char*>(iv), output_file_size, ov);
+      else if (strcmp(style, "md5") == 0)
+        md5_buffer(reinterpret_cast<const char*>(iv), output_file_size, ov);
+      else
+        gold_unreachable();
+
+      of->free_input_view(0, output_file_size, iv);
     }
-  else if (strcmp(style, "md5") == 0)
+  else
     {
-      md5_ctx ctx;
-      md5_init_ctx(&ctx);
-      md5_process_bytes(iv, this->output_file_size_, &ctx);
-      md5_finish_ctx(&ctx, ov);
+      // Non-overlapping substrings of the output file have been hashed.
+      // Compute SHA-1 hash of the hashes.
+      sha1_buffer(reinterpret_cast<const char*>(this->array_of_hashes_),
+                  this->size_of_array_of_hashes_, ov);
+      delete[] this->array_of_hashes_;
+      of->free_input_view(0, this->output_file_size(), this->input_view_);
     }
-  else
-    gold_unreachable();
 
   of->write_output_view(this->build_id_note_->offset(),
 			this->build_id_note_->data_size(),
 			ov);
-
-  of->free_input_view(0, this->output_file_size_, iv);
 }
 
 // Write out a binary file.  This is called after the link is
@@ -5439,12 +5539,14 @@ Write_after_input_sections_task::run(Workqueue*)
 
 // Close_task_runner methods.
 
-// Run the task--close the file.
+// Finish up the build ID computation, if necessary, and write a binary file,
+// if necessary.  Then close the output file.
 
 void
 Close_task_runner::run(Workqueue*, const Task*)
 {
-  // If we need to compute a checksum for the BUILD if, we do so here.
+  // At this point the multi-threaded part of the build ID computation,
+  // if any, is done.  See queue_build_id_tasks().
   this->layout_->write_build_id(this->of_);
 
   // If we've been asked to create a binary file, we do so here.
diff --git a/gold/layout.h b/gold/layout.h
index 6da9607504..1743869288 100644
--- a/gold/layout.h
+++ b/gold/layout.h
@@ -892,6 +892,13 @@ class Layout
 			  const Output_data_reloc_generic* dyn_rel,
 			  bool add_debug, bool dynrel_includes_plt);
 
+  // If a treehash is necessary to compute the build ID, then queue
+  // the necessary tasks and return a blocker that will unblock when
+  // they finish.  Otherwise return BUILD_ID_BLOCKER.
+  Task_token*
+  queue_build_id_tasks(Workqueue* workqueue, Task_token* build_id_blocker,
+                       Output_file* of);
+
   // Compute and write out the build ID if needed.
   void
   write_build_id(Output_file*) const;
@@ -1354,6 +1361,12 @@ class Layout
   Gdb_index* gdb_index_data_;
   // The space for the build ID checksum if there is one.
   Output_section_data* build_id_note_;
+  // Temporary storage for tree hash of build ID.
+  unsigned char* array_of_hashes_;
+  // Size of array_of_hashes_ (in bytes).
+  size_t size_of_array_of_hashes_;
+  // Input view for computing tree hash of build ID.  Freed in write_build_id().
+  const unsigned char* input_view_;
   // The output section containing dwarf abbreviations
   Output_reduced_debug_abbrev_section* debug_abbrev_;
   // The output section containing the dwarf debug info tree
diff --git a/gold/options.h b/gold/options.h
index 66fcf3eec6..75dbee5daa 100644
--- a/gold/options.h
+++ b/gold/options.h
@@ -678,10 +678,19 @@ class General_options
   DEFINE_bool(Bsymbolic_functions, options::ONE_DASH, '\0', false,
 	      N_("Bind defined function symbols locally"), NULL);
 
-  DEFINE_optional_string(build_id, options::TWO_DASHES, '\0', "sha1",
+  DEFINE_optional_string(build_id, options::TWO_DASHES, '\0', "tree",
 			 N_("Generate build ID note"),
 			 N_("[=STYLE]"));
 
+  DEFINE_uint64(build_id_chunk_size_for_treehash,
+                options::TWO_DASHES, '\0', 2 << 20,
+                N_("Chunk size for '--build-id=tree'"), N_("SIZE"));
+
+  DEFINE_uint64(build_id_min_file_size_for_treehash, options::TWO_DASHES,
+                '\0', 40 << 20,
+                N_("Minimum output file size for '--build-id=tree' to work"
+                   " differently than '--build-id=sha1'"), N_("SIZE"));
+
   DEFINE_bool(check_sections, options::TWO_DASHES, '\0', true,
 	      N_("Check segment addresses for overlaps (default)"),
 	      N_("Do not check segment addresses for overlaps"));