* archive.cc (Archive::include_member): Adjust call to

	report_object.
	(Add_archive_symbols::run): Track argument serial numbers.
	(Lib_group::include_member): Likewise.
	(Add_lib_group_symbols::run): Adjust call to report_archive_begin.
	* archive.h (Incremental_archive_entry::Archive_member):
	Initialize arg_serial_.
	(Archive_member::arg_serial_): New data member.
	* dynobj.cc (Dynobj::Dynobj): Allow input_file_ to be NULL.
	(Sized_dynobj::do_add_symbols): Track symbols when doing an
	incremental link.
	(Sized_dynobj::do_for_all_local_got_entries): New function.
	* dynobj.h: (Sized_dynobj::do_for_all_local_got_entries): New
	function.
	* fileread.cc (get_mtime): New function.
	* fileread.h (get_mtime): New function.
	* gold.cc (queue_initial_tasks): Check for incremental update.
	(process_incremental_input): New function.
	(queue_middle_tasks): Don't force valid target for incremental
	update.
	* incremental-dump.cc (find_input_containing_global): Adjust
	size of symbol info entry.
	(dump_incremental_inputs): Dump argument serial number and
	in_system_directory flag; bias shndx by 1; print symbol names
	when dumping per-file symbol lists; use new symbol info readers.
	* incremental.cc
	(Output_section_incremental_inputs:update_data_size): New function.
	(Sized_incremental_binary::setup_readers): Setup input readers
	for each input file; build maps for files added from libraries
	and scripts.
	(Sized_incremental_binary::check_input_args): New function.
	(Sized_incremental_binary::do_check_inputs): Build map of argument
	serial numbers to input arguments.
	(Sized_incremental_binary::do_file_has_changed): Rename
	do_file_is_unchanged to this; compare file modification times.
	(Sized_incremental_binary::do_init_layout): New function.
	(Sized_incremental_binary::do_reserve_layout): New function.
	(Sized_incremental_binary::do_get_input_reader): Remove.
	(Sized_incremental_binary::get_symtab_view): New function.
	(Incremental_checker::can_incrementally_link_output_file): Remove.
	(Incremental_inputs::report_command_line): Exclude --debug options.
	(Incremental_inputs::report_archive_begin): Add parameter; track
	argument serial numbers; don't put input file entry for archive
	before archive members.
	(Incremental_inputs::report_archive_end): Put input file entry
	for archive after archive members.
	(Incremental_inputs::report_object): Add parameter; track argument
	serial numbers and in_system_directory flag.
	(Incremental_inputs::report_script): Add parameter; track argument
	serial numbers.
	(Output_section_incremental_inputs::set_final_data_size): Adjust
	size of symbol info entry; check for forwarding symbols.
	(Output_section_incremental_inputs::write_input_files): Write
	in_system_directory flag and argument serial number.
	(Output_section_incremental_inputs::write_info_blocks): Map section
	indices between incremental info and original input file; store
	input section index for each symbol.
	(class Local_got_offset_visitor): Derive from Got_offset_list::Visitor;
	change operator() to visit().
	(class Global_got_offset_visitor): Likewise.
	(class Global_symbol_visitor_got_plt):
	(Output_section_incremental_inputs::write_got_plt): Use new visitor
	classes.
	(Sized_incr_relobj::Sized_incr_relobj): New constructor.
	(Sized_incr_relobj::do_read_symbols): New function.
	(Sized_incr_relobj::do_layout): New function.
	(Sized_incr_relobj::do_layout_deferred_sections): New function.
	(Sized_incr_relobj::do_add_symbols): New function.
	(Sized_incr_relobj::do_should_include_member): New function.
	(Sized_incr_relobj::do_for_all_global_symbols): New function.
	(Sized_incr_relobj::do_for_all_local_got_entries): New function.
	(Sized_incr_relobj::do_section_size): New function.
	(Sized_incr_relobj::do_section_name): New function.
	(Sized_incr_relobj::do_section_contents): New function.
	(Sized_incr_relobj::do_section_flags): New function.
	(Sized_incr_relobj::do_section_entsize): New function.
	(Sized_incr_relobj::do_section_address): New function.
	(Sized_incr_relobj::do_section_type): New function.
	(Sized_incr_relobj::do_section_link): New function.
	(Sized_incr_relobj::do_section_info): New function.
	(Sized_incr_relobj::do_section_addralign): New function.
	(Sized_incr_relobj::do_initialize_xindex): New function.
	(Sized_incr_relobj::do_get_global_symbol_counts): New function.
	(Sized_incr_relobj::do_read_relocs): New function.
	(Sized_incr_relobj::do_gc_process_relocs): New function.
	(Sized_incr_relobj::do_scan_relocs): New function.
	(Sized_incr_relobj::do_count_local_symbols): New function.
	(Sized_incr_relobj::do_finalize_local_symbols): New function.
	(Sized_incr_relobj::do_set_local_dynsym_indexes): New function.
	(Sized_incr_relobj::do_set_local_dynsym_offset): New function.
	(Sized_incr_relobj::do_relocate): New function.
	(Sized_incr_relobj::do_set_section_offset): New function.
	(Sized_incr_dynobj::Sized_incr_dynobj): New function.
	(Sized_incr_dynobj::do_read_symbols): New function.
	(Sized_incr_dynobj::do_layout): New function.
	(Sized_incr_dynobj::do_add_symbols): New function.
	(Sized_incr_dynobj::do_should_include_member): New function.
	(Sized_incr_dynobj::do_for_all_global_symbols): New function.
	(Sized_incr_dynobj::do_for_all_local_got_entries): New function.
	(Sized_incr_dynobj::do_section_size): New function.
	(Sized_incr_dynobj::do_section_name): New function.
	(Sized_incr_dynobj::do_section_contents): New function.
	(Sized_incr_dynobj::do_section_flags): New function.
	(Sized_incr_dynobj::do_section_entsize): New function.
	(Sized_incr_dynobj::do_section_address): New function.
	(Sized_incr_dynobj::do_section_type): New function.
	(Sized_incr_dynobj::do_section_link): New function.
	(Sized_incr_dynobj::do_section_info): New function.
	(Sized_incr_dynobj::do_section_addralign): New function.
	(Sized_incr_dynobj::do_initialize_xindex): New function.
	(Sized_incr_dynobj::do_get_global_symbol_counts): New function.
	(make_sized_incremental_object): New function.
	(Incremental_library::copy_unused_symbols): New function.
	(Incremental_library::do_for_all_unused_symbols): New function.
	* incremental.h (enum Incremental_input_flags): New type.
	(class Incremental_checker): Remove.
	(Incremental_input_entry::Incremental_input_entry): Add argument
	serial number.
	(Incremental_input_entry::arg_serial): New function.
	(Incremental_input_entry::set_is_in_system_directory): New function.
	(Incremental_input_entry::is_in_system_directory): New function.
	(Incremental_input_entry::arg_serial_): New data member.
	(Incremental_input_entry::is_in_system_directory_): New data member.
	(class Script_info): Move here from script.h.
	(Script_info::Script_info): Add filename parameter.
	(Script_info::filename): New function.
	(Script_info::filename_): New data member.
	(Incremental_script_entry::Incremental_script_entry): Add argument
	serial number.
	(Incremental_object_entry::Incremental_object_entry): Likewise.
	(Incremental_object_entry::add_input_section): Build list of input
	sections with map to original shndx.
	(Incremental_object_entry::get_input_section_index): New function.
	(Incremental_object_entry::shndx_): New data member.
	(Incremental_object_entry::name_key_): Rename; adjust all refs.
	(Incremental_object_entry::sh_size_): Rename; adjust all refs.
	(Incremental_archive_entry::Incremental_archive_entry): Add argument
	serial number.
	(Incremental_inputs::report_archive_begin): Likewise.
	(Incremental_inputs::report_object): Likewise.
	(Incremental_inputs::report_script): Likewise.
	(class Incremental_global_symbol_reader): New class.
	(Incremental_input_entry_reader::Incremental_input_entry_reader): Read
	and store flags and input file type.
	(Incremental_input_entry_reader::arg_serial): New function.
	(Incremental_input_entry_reader::type): Extract type from flags.
	(Incremental_input_entry_reader::is_in_system_directory): New function.
	(Incremental_input_entry_reader::get_input_section_count): Call
	accessor function for type.
	(Incremental_input_entry_reader::get_symbol_offset): Call accessor
	function for type; adjust size of global symbol entry.
	(Incremental_input_entry_reader::get_global_symbol_count): Call
	accessor function for type.
	(Incremental_input_entry_reader::get_object_count): Likewise.
	(Incremental_input_entry_reader::get_object_offset): Likewise.
	(Incremental_input_entry_reader::get_member_count): Likewise.
	(Incremental_input_entry_reader::get_unused_symbol_count): Likewise.
	(Incremental_input_entry_reader::get_member_offset): Likewise.
	(Incremental_input_entry_reader::get_unused_symbol): Likewise.
	(Incremental_input_entry_reader::Global_symbol_info): Remove.
	(Incremental_input_entry_reader::get_global_symbol_info): Remove.
	(Incremental_input_entry_reader::get_global_symbol_reader): New
	function.
	(Incremental_input_entry_reader::get_output_symbol_index): New
	function.
	(Incremental_input_entry_reader::type_): Remove.
	(Incremental_input_entry_reader::flags_): New data member.
	(Incremental_inputs_reader::input_file_offset): New function.
	(Incremental_inputs_reader::input_file_index): New function.
	(Incremental_inputs_reader::input_file): Call input_file_offset.
	(Incremental_inputs_reader::input_file_at_offset): New function.
	(Incremental_relocs_reader::get_r_type): Reformat.
	(Incremental_relocs_reader::get_r_shndx): Reformat.
	(Incremental_relocs_reader::get_r_offset): Reformat.
	(Incremental_relocs_reader::data): New function.
	(Incremental_binary::Incremental_binary): Initialize new data members.
	(Incremental_binary::check_inputs): Add cmdline parameter.
	(Incremental_binary::file_is_unchanged): Remove.
	(Input_reader::arg_serial): New function.
	(Input_reader::get_unused_symbol_count): New function.
	(Input_reader::get_unused_symbol): New function.
	(Input_reader::do_arg_serial): New function.
	(Input_reader::do_get_unused_symbol_count): New function.
	(Input_reader::do_get_unused_symbol): New function.
	(Incremental_binary::input_file_count): New function.
	(Incremental_binary::get_input_reader): Change signature to use
	index instead of filename.
	(Incremental_binary::file_has_changed): New function.
	(Incremental_binary::get_input_argument): New function.
	(Incremental_binary::get_library): New function.
	(Incremental_binary::get_script_info): New function.
	(Incremental_binary::init_layout): New function.
	(Incremental_binary::reserve_layout): New function.
	(Incremental_binary::output_file): New function.
	(Incremental_binary::do_check_inputs): New function.
	(Incremental_binary::do_file_is_unchanged): Remove.
	(Incremental_binary::do_file_has_changed): New function.
	(Incremental_binary::do_init_layout): New function.
	(Incremental_binary::do_reserve_layout): New function.
	(Incremental_binary::do_input_file_count): New function.
	(Incremental_binary::do_get_input_reader): Change signature.
	(Incremental_binary::input_args_map_): New data member.
	(Incremental_binary::library_map_): New data member.
	(Incremental_binary::script_map_): New data member.
	(Sized_incremental_binary::Sized_incremental_binary): Initialize
	new data members.
	(Sized_incremental_binary::output_section): New function.
	(Sized_incremental_binary::inputs_reader): Add const.
	(Sized_incremental_binary::symtab_reader): Add const.
	(Sized_incremental_binary::relocs_reader): Add const.
	(Sized_incremental_binary::got_plt_reader): Add const.
	(Sized_incremental_binary::get_symtab_view): New function.
	(Sized_incremental_binary::Inputs_reader): New typedef.
	(Sized_incremental_binary::Input_entry_reader): New typedef.
	(Sized_incremental_binary::do_check_inputs): Add cmdline parameter.
	(Sized_incremental_binary::do_file_is_unchanged): Remove.
	(Sized_incremental_binary::do_file_has_changed): New function.
	(Sized_incremental_binary::do_init_layout): New function.
	(Sized_incremental_binary::do_reserve_layout): New function.
	(Sized_input_reader::Inputs_reader): Remove.
	(Sized_input_reader::Input_entry_reader): Remove.
	(Sized_input_reader::do_arg_serial): New function.
	(Sized_input_reader::do_get_unused_symbol_count): New function.
	(Sized_input_reader::do_get_unused_symbol): New function.
	(Sized_incremental_binary::do_input_file_count): New function.
	(Sized_incremental_binary::do_get_input_reader): Change signature;
	use index instead of filename.
	(Sized_incremental_binary::section_map_): New data member.
	(Sized_incremental_binary::input_entry_readers_): New data member.
	(class Sized_incr_relobj): New class.
	(class Sized_incr_dynobj): New class.
	(make_sized_incremental_object): New function.
	(class Incremental_library): New class.
	* layout.cc (Free_list::num_lists): New static data member.
	(Free_list::num_nodes): New static data member.
	(Free_list::num_removes): New static data member.
	(Free_list::num_remove_visits): New static data member.
	(Free_list::num_allocates): New static data member.
	(Free_list::num_allocate_visits): New static data member.
	(Free_list::init): New function.
	(Free_list::remove): New function.
	(Free_list::allocate): New function.
	(Free_list::dump): New function.
	(Free_list::print_stats): New function.
	(Layout_task_runner::run): Resize output file for incremental updates.
	(Layout::Layout): Initialize new data members.
	(Layout::set_incremental_base): New function.
	(Layout::init_fixed_output_section): New function.
	(Layout::layout_eh_frame): Do not build .eh_frame_hdr section for
	incremental updates.
	(Layout::create_gold_note): Do not create gold note section for
	incremental updates.
	(Layout::set_segment_offsets): Do not recalculate RELRO alignment
	for incremental updates.
	(Layout::set_section_offsets): For incremental updates, allocate space
	from free list.
	(Layout::create_symtab_sections): Layout with offsets relative to
	start of section; for incremental updates, allocate space from free
	list.
	(Layout::create_shdrs): For incremental updates, allocate space from
	free list.
	(Layout::finish_dynamic_section): For incremental updates, do not
	check --as-needed (fixed in subsequent patch).
	* layout.h (class Free_list): New class.
	(Layout::set_incremental_base): New function.
	(Layout::incremental_base): New function.
	(Layout::init_fixed_output_section): New function.
	(Layout::allocate): New function.
	(Layout::incremental_base_): New data member.
	(Layout::free_list_): New data member.
	* main.cc (main): Print Free_list statistics.
	* object.cc (Relobj::finalize_incremental_relocs): Add
	clear_counts parameter; clear counts only when clear_counts is set.
	(Sized_relobj::Sized_relobj): Initialize new base class.
	(Sized_relobj::do_layout): Don't report special sections.
	(Sized_relobj::do_for_all_local_got_entries): New function.
	(Sized_relobj::write_local_symbols): Add symtab_off parameter; add
	symtab_off to all symbol table offsets.
	(Sized_relobj::do_get_global_symbol_counts): Add typename keyword.
	* object.h (class Got_offset_list): Move to top of file.
	(Object::Object): Allow case where input_file == NULL.
	(Object::~Object): Likewise.
	(Object::input_file): Assert that input_file != NULL.
	(Object::lock): Allow case where input_file == NULL.
	(Object::unlock): Likewise.
	(Object::is_locked): Likewise.
	(Object::token): Likewise.
	(Object::release): Likewise.
	(Object::is_incremental): New function.
	(Object::get_mtime): New function.
	(Object::for_all_local_got_entries): New function.
	(Object::clear_view_cache_marks): Allow case where input_file == NULL.
	(Object::set_is_in_system_directory): New function.
	(Object::is_in_system_directory): New function.
	(Object::do_is_incremental): New function.
	(Object::do_get_mtime): New function.
	(Object::do_for_all_local_got_entries): New function.
	(Object::is_in_system_directory_): New data member.
	(Relobj::finalize_incremental_relocs): Add clear_counts parameter.
	(class Sized_relobj_base): New class.
	(class Sized_relobj): Derive from Sized_relobj_base.
	(class Sized_relobj::Symbols): Redeclare from base class.
	(class Sized_relobj::local_got_offset_list): Remove.
	(class Sized_relobj::Output_sections): Redeclare from base class.
	(class Sized_relobj::do_for_all_local_got_entries): New function.
	(class Sized_relobj::write_local_symbols): Add offset parameter.
	(class Sized_relobj::local_symbol_offset_): Update comment.
	(class Sized_relobj::local_dynsym_offset_): Update comment.
	* options.cc (Input_arguments::add_file): Remove const.
	* options.h (Input_file_argument::Input_file_argument):
	Initialize arg_serial_ (all constructors).
	(Input_file_argument::set_arg_serial): New function.
	(Input_file_argument::arg_serial): New function.
	(Input_file_argument::arg_serial_): New data member.
	(Input_arguments::Input_arguments): Initialize file_count_.
	(Input_arguments::add_file): Remove const.
	(Input_arguments::number_of_input_files): New function.
	(Input_arguments::file_count_): New data member.
	(Command_line::number_of_input_files): Call
	Input_arguments::number_of_input_files.
	* output.cc (Output_segment_headers::Output_segment_headers):
	Set current size.
	(Output_section::Input_section::current_data_size): New function.
	(Output_section::Output_section): Initialize new data members.
	(Output_section::add_input_section): Don't do merge sections for
	an incremental link; allocate space from free list for an
	incremental update.
	(Output_section::add_output_section_data): Allocate space from
	free list for an incremental update.
	(Output_section::update_data_size): New function.
	(Output_section::set_fixed_layout): New function.
	(Output_section::reserve): New function.
	(Output_segment::set_section_addresses): Remove const.
	(Output_segment::set_section_list_addresses): Remove const; allocate
	space from free list for an incremental update.
	(Output_segment::set_offset): Adjust size of RELRO segment for an
	incremental update.
	* output.h (Output_data::current_data_size): Move here from
	child classes.
	(Output_data::pre_finalize_data_size): New function.
	(Output_data::update_data_size): New function.
	(Output_section_headers::update_data_size): new function.
	(Output_section_data_build::current_data_size): Move to Output_data.
	(Output_data_strtab::update_data_size): New function.
	(Output_section::current_data_size): Move to Output_data.
	(Output_section::set_fixed_layout): New function.
	(Output_section::has_fixed_layout): New function.
	(Output_section::reserve): New function.
	(Output_section::update_data_size): New function.
	(Output_section::has_fixed_layout_): New data member.
	(Output_section::free_list_): New data member.
	(Output_segment::set_section_addresses): Remove const.
	(Output_segment::set_section_list_addresses): Remove const.
	* plugin.cc (Sized_pluginobj::do_for_all_local_got_entries):
	New function.
	* plugin.h (Sized_pluginobj::do_for_all_local_got_entries):
	New function.
	* readsyms.cc (Read_symbols::do_read_symbols): Add library
	parameter when calling Add_symbols constructor; store argument
	serial number for members of a lib group.
	(Add_symbols::locks): Allow case where token == NULL.
	(Add_symbols::run): Report libraries denoted by --start-lib/--end-lib.
	(Read_member::~Read_member): New function.
	(Read_member::is_runnable): New function.
	(Read_member::locks): New function.
	(Read_member::run): New function.
	(Check_script::~Check_script): New function.
	(Check_script::is_runnable): New function.
	(Check_script::locks): New function.
	(Check_script::run): New function.
	(Check_library::~Check_library): New function.
	(Check_library::is_runnable): New function.
	(Check_library::locks): New function.
	(Check_library::run): New function.
	* readsyms.h (Add_symbols::Add_symbols): Add library parameter.
	(Add_symbols::library_): New data member.
	(class Read_member): New class.
	(class Check_script): New class.
	(class Check_library): New class.
	* reloc.cc (Read_relocs::is_runnable): Allow case where
	token == NULL.
	(Read_relocs::locks): Likewise.
	(Scan_relocs::locks): Likewise.
	(Relocate_task::locks): Likewise.
	(Sized_relobj::do_scan_relocs): Tell finalize_incremental_relocs
	to clear counters.
	(Sized_relobj::incremental_relocs_scan): Fix comment.
	(Sized_relobj::do_relocate): Pass output file offset to
	write_local_symbols.
	(Sized_relobj::incremental_relocs_write_reltype): Use reloc_size
	from class declaration.
	* script.cc (read_input_script): Allocate Script_info; pass
	argument serial number to report_script.
	* script.h (class Script_info): Move to incremental.h.
	* symtab.cc (Symbol_table::add_from_incrobj): New function.
	* symtab.h (Symbol_table::add_from_incrobj): New function.
	(Symbol_table::set_file_offset): New function.

1 files changed, 359 insertions, 31 deletions

diff --git a/gold/layout.cc b/gold/layout.cc
index 63b9e0d..26ac130d 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -55,6 +55,168 @@
 namespace gold
 {
 
+// Class Free_list.
+
+// The total number of free lists used.
+unsigned int Free_list::num_lists = 0;
+// The total number of free list nodes used.
+unsigned int Free_list::num_nodes = 0;
+// The total number of calls to Free_list::remove.
+unsigned int Free_list::num_removes = 0;
+// The total number of nodes visited during calls to Free_list::remove.
+unsigned int Free_list::num_remove_visits = 0;
+// The total number of calls to Free_list::allocate.
+unsigned int Free_list::num_allocates = 0;
+// The total number of nodes visited during calls to Free_list::allocate.
+unsigned int Free_list::num_allocate_visits = 0;
+
+// Initialize the free list.  Creates a single free list node that
+// describes the entire region of length LEN.  If EXTEND is true,
+// allocate() is allowed to extend the region beyond its initial
+// length.
+
+void
+Free_list::init(off_t len, bool extend)
+{
+  this->list_.push_front(Free_list_node(0, len));
+  this->last_remove_ = this->list_.begin();
+  this->extend_ = extend;
+  this->length_ = len;
+  ++Free_list::num_lists;
+  ++Free_list::num_nodes;
+}
+
+// Remove a chunk from the free list.  Because we start with a single
+// node that covers the entire section, and remove chunks from it one
+// at a time, we do not need to coalesce chunks or handle cases that
+// span more than one free node.  We expect to remove chunks from the
+// free list in order, and we expect to have only a few chunks of free
+// space left (corresponding to files that have changed since the last
+// incremental link), so a simple linear list should provide sufficient
+// performance.
+
+void
+Free_list::remove(off_t start, off_t end)
+{
+  if (start == end)
+    return;
+  gold_assert(start < end);
+
+  ++Free_list::num_removes;
+
+  Iterator p = this->last_remove_;
+  if (p->start_ > start)
+    p = this->list_.begin();
+
+  for (; p != this->list_.end(); ++p)
+    {
+      ++Free_list::num_remove_visits;
+      // Find a node that wholly contains the indicated region.
+      if (p->start_ <= start && p->end_ >= end)
+	{
+	  // Case 1: the indicated region spans the whole node.
+	  // Add some fuzz to avoid creating tiny free chunks.
+	  if (p->start_ + 3 >= start && p->end_ <= end + 3)
+	    p = this->list_.erase(p);
+	  // Case 2: remove a chunk from the start of the node.
+	  else if (p->start_ + 3 >= start)
+	    p->start_ = end;
+	  // Case 3: remove a chunk from the end of the node.
+	  else if (p->end_ <= end + 3)
+	    p->end_ = start;
+	  // Case 4: remove a chunk from the middle, and split
+	  // the node into two.
+	  else
+	    {
+	      Free_list_node newnode(p->start_, start);
+	      p->start_ = end;
+	      this->list_.insert(p, newnode);
+	      ++Free_list::num_nodes;
+	    }
+	  this->last_remove_ = p;
+	  return;
+	}
+    }
+
+  // Did not find a node containing the given chunk.  This could happen
+  // because a small chunk was already removed due to the fuzz.
+  gold_debug(DEBUG_INCREMENTAL,
+	     "Free_list::remove(%d,%d) not found",
+	     static_cast<int>(start), static_cast<int>(end));
+}
+
+// Allocate a chunk of size LEN from the free list.  Returns -1ULL
+// if a sufficiently large chunk of free space is not found.
+// We use a simple first-fit algorithm.
+
+off_t
+Free_list::allocate(off_t len, uint64_t align, off_t minoff)
+{
+  gold_debug(DEBUG_INCREMENTAL,
+  	     "Free_list::allocate(%08lx, %d, %08lx)",
+  	     static_cast<long>(len), static_cast<int>(align),
+  	     static_cast<long>(minoff));
+  if (len == 0)
+    return align_address(minoff, align);
+
+  ++Free_list::num_allocates;
+
+  for (Iterator p = this->list_.begin(); p != this->list_.end(); ++p)
+    {
+      ++Free_list::num_allocate_visits;
+      off_t start = p->start_ > minoff ? p->start_ : minoff;
+      start = align_address(start, align);
+      off_t end = start + len;
+      if (end <= p->end_)
+	{
+	  if (p->start_ + 3 >= start && p->end_ <= end + 3)
+	    this->list_.erase(p);
+	  else if (p->start_ + 3 >= start)
+	    p->start_ = end;
+	  else if (p->end_ <= end + 3)
+	    p->end_ = start;
+	  else
+	    {
+	      Free_list_node newnode(p->start_, start);
+	      p->start_ = end;
+	      this->list_.insert(p, newnode);
+	      ++Free_list::num_nodes;
+	    }
+	  return start;
+	}
+    }
+  return -1;
+}
+
+// Dump the free list (for debugging).
+void
+Free_list::dump()
+{
+  gold_info("Free list:\n     start      end   length\n");
+  for (Iterator p = this->list_.begin(); p != this->list_.end(); ++p)
+    gold_info("  %08lx %08lx %08lx", static_cast<long>(p->start_),
+	      static_cast<long>(p->end_),
+	      static_cast<long>(p->end_ - p->start_));
+}
+
+// Print the statistics for the free lists.
+void
+Free_list::print_stats()
+{
+  fprintf(stderr, _("%s: total free lists: %u\n"),
+          program_name, Free_list::num_lists);
+  fprintf(stderr, _("%s: total free list nodes: %u\n"),
+          program_name, Free_list::num_nodes);
+  fprintf(stderr, _("%s: calls to Free_list::remove: %u\n"),
+          program_name, Free_list::num_removes);
+  fprintf(stderr, _("%s: nodes visited: %u\n"),
+          program_name, Free_list::num_remove_visits);
+  fprintf(stderr, _("%s: calls to Free_list::allocate: %u\n"),
+          program_name, Free_list::num_allocates);
+  fprintf(stderr, _("%s: nodes visited: %u\n"),
+          program_name, Free_list::num_allocate_visits);
+}
+
 // Layout::Relaxation_debug_check methods.
 
 // Check that sections and special data are in reset states.
@@ -150,10 +312,19 @@ Layout_task_runner::run(Workqueue* workqueue, const Task* task)
       this->layout_->print_to_mapfile(this->mapfile_);
     }
 
-  Output_file* of = new Output_file(parameters->options().output_file_name());
-  if (this->options_.oformat_enum() != General_options::OBJECT_FORMAT_ELF)
-    of->set_is_temporary();
-  of->open(file_size);
+  Output_file* of;
+  if (this->layout_->incremental_base() == NULL)
+    {
+      of = new Output_file(parameters->options().output_file_name());
+      if (this->options_.oformat_enum() != General_options::OBJECT_FORMAT_ELF)
+	of->set_is_temporary();
+      of->open(file_size);
+    }
+  else
+    {
+      of = this->layout_->incremental_base()->output_file();
+      of->resize(file_size);
+    }
 
   // Queue up the final set of tasks.
   gold::queue_final_tasks(this->options_, this->input_objects_,
@@ -207,7 +378,9 @@ Layout::Layout(int number_of_input_files, Script_options* script_options)
     record_output_section_data_from_script_(false),
     script_output_section_data_list_(),
     segment_states_(NULL),
-    relaxation_debug_check_(NULL)
+    relaxation_debug_check_(NULL),
+    incremental_base_(NULL),
+    free_list_()
 {
   // Make space for more than enough segments for a typical file.
   // This is just for efficiency--it's OK if we wind up needing more.
@@ -226,6 +399,15 @@ Layout::Layout(int number_of_input_files, Script_options* script_options)
   this->namepool_.set_optimize();
 }
 
+// For incremental links, record the base file to be modified.
+
+void
+Layout::set_incremental_base(Incremental_binary* base)
+{
+  this->incremental_base_ = base;
+  this->free_list_.init(base->output_file()->filesize(), true);
+}
+
 // Hash a key we use to look up an output section mapping.
 
 size_t
@@ -639,6 +821,41 @@ Layout::choose_output_section(const Relobj* relobj, const char* name,
   return this->get_output_section(name, name_key, type, flags, order, is_relro);
 }
 
+// For incremental links, record the initial fixed layout of a section
+// from the base file, and return a pointer to the Output_section.
+
+template<int size, bool big_endian>
+Output_section*
+Layout::init_fixed_output_section(const char* name,
+				  elfcpp::Shdr<size, big_endian>& shdr)
+{
+  unsigned int sh_type = shdr.get_sh_type();
+
+  // We preserve the layout of PROGBITS, NOBITS, and NOTE sections.
+  // All others will be created from scratch and reallocated.
+  if (sh_type != elfcpp::SHT_PROGBITS
+      && sh_type != elfcpp::SHT_NOBITS
+      && sh_type != elfcpp::SHT_NOTE)
+    return NULL;
+
+  typename elfcpp::Elf_types<size>::Elf_Addr sh_addr = shdr.get_sh_addr();
+  typename elfcpp::Elf_types<size>::Elf_Off sh_offset = shdr.get_sh_offset();
+  typename elfcpp::Elf_types<size>::Elf_WXword sh_size = shdr.get_sh_size();
+  typename elfcpp::Elf_types<size>::Elf_WXword sh_flags = shdr.get_sh_flags();
+  typename elfcpp::Elf_types<size>::Elf_WXword sh_addralign =
+      shdr.get_sh_addralign();
+
+  // Make the output section.
+  Stringpool::Key name_key;
+  name = this->namepool_.add(name, true, &name_key);
+  Output_section* os = this->get_output_section(name, name_key, sh_type,
+  						sh_flags, ORDER_INVALID, false);
+  os->set_fixed_layout(sh_addr, sh_offset, sh_size, sh_addralign);
+  if (sh_type != elfcpp::SHT_NOBITS)
+    this->free_list_.remove(sh_offset, sh_offset + sh_size);
+  return os;
+}
+
 // Return the output section to use for input section SHNDX, with name
 // NAME, with header HEADER, from object OBJECT.  RELOC_SHNDX is the
 // index of a relocation section which applies to this section, or 0
@@ -869,7 +1086,9 @@ Layout::layout_eh_frame(Sized_relobj<size, big_endian>* object,
       this->eh_frame_section_ = os;
       this->eh_frame_data_ = new Eh_frame();
 
-      if (parameters->options().eh_frame_hdr())
+      // For incremental linking, we do not optimize .eh_frame sections
+      // or create a .eh_frame_hdr section.
+      if (parameters->options().eh_frame_hdr() && !parameters->incremental())
 	{
 	  Output_section* hdr_os =
 	    this->choose_output_section(NULL, ".eh_frame_hdr",
@@ -901,14 +1120,15 @@ Layout::layout_eh_frame(Sized_relobj<size, big_endian>* object,
 
   gold_assert(this->eh_frame_section_ == os);
 
-  if (this->eh_frame_data_->add_ehframe_input_section(object,
-						      symbols,
-						      symbols_size,
-						      symbol_names,
-						      symbol_names_size,
-						      shndx,
-						      reloc_shndx,
-						      reloc_type))
+  if (!parameters->incremental()
+      && this->eh_frame_data_->add_ehframe_input_section(object,
+							 symbols,
+							 symbols_size,
+							 symbol_names,
+							 symbol_names_size,
+							 shndx,
+							 reloc_shndx,
+							 reloc_type))
     {
       os->update_flags_for_input_section(shdr.get_sh_flags());
 
@@ -2147,7 +2367,8 @@ Layout::create_note(const char* name, int note_type,
 void
 Layout::create_gold_note()
 {
-  if (parameters->options().relocatable())
+  if (parameters->options().relocatable()
+      || parameters->incremental_update())
     return;
 
   std::string desc = std::string("gold ") + gold::get_version_string();
@@ -2709,7 +2930,10 @@ Layout::set_segment_offsets(const Target* target, Output_segment* load_seg,
 	  // aligned so that the relro data ends at a page boundary,
 	  // we do not try to realign it.
 
-	  if (!are_addresses_set && !has_relro && aligned_addr != addr)
+	  if (!are_addresses_set
+	      && !has_relro
+	      && aligned_addr != addr
+	      && !parameters->incremental_update())
 	    {
 	      uint64_t first_off = (common_pagesize
 				    - (aligned_addr
@@ -2826,6 +3050,9 @@ Layout::set_relocatable_section_offsets(Output_data* file_header,
 off_t
 Layout::set_section_offsets(off_t off, Layout::Section_offset_pass pass)
 {
+  off_t startoff = off;
+  off_t maxoff = off;
+
   for (Section_list::iterator p = this->unattached_section_list_.begin();
        p != this->unattached_section_list_.end();
        ++p)
@@ -2857,16 +3084,53 @@ Layout::set_section_offsets(off_t off, Layout::Section_offset_pass pass)
                    || (*p)->type() != elfcpp::SHT_STRTAB))
         continue;
 
-      off = align_address(off, (*p)->addralign());
-      (*p)->set_file_offset(off);
-      (*p)->finalize_data_size();
+      if (!parameters->incremental_update())
+	{
+	  off = align_address(off, (*p)->addralign());
+	  (*p)->set_file_offset(off);
+	  (*p)->finalize_data_size();
+	}
+      else
+	{
+	  // Incremental update: allocate file space from free list.
+	  (*p)->pre_finalize_data_size();
+	  off_t current_size = (*p)->current_data_size();
+	  off = this->allocate(current_size, (*p)->addralign(), startoff);
+	  if (off == -1)
+	    {
+	      if (is_debugging_enabled(DEBUG_INCREMENTAL))
+	        this->free_list_.dump();
+	      gold_assert((*p)->output_section() != NULL);
+	      gold_fatal(_("out of patch space for section %s; "
+			   "relink with --incremental-full"),
+			 (*p)->output_section()->name());
+	    }
+	  (*p)->set_file_offset(off);
+	  (*p)->finalize_data_size();
+	  if ((*p)->data_size() > current_size)
+	    {
+	      gold_assert((*p)->output_section() != NULL);
+	      gold_fatal(_("%s: section changed size; "
+			   "relink with --incremental-full"),
+			 (*p)->output_section()->name());
+	    }
+	  gold_debug(DEBUG_INCREMENTAL,
+		     "set_section_offsets: %08lx %08lx %s",
+		     static_cast<long>(off),
+		     static_cast<long>((*p)->data_size()),
+		     ((*p)->output_section() != NULL
+		      ? (*p)->output_section()->name() : "(special)"));
+	}
+
       off += (*p)->data_size();
+      if (off > maxoff)
+        maxoff = off;
 
       // At this point the name must be set.
       if (pass != STRTAB_AFTER_POSTPROCESSING_SECTIONS_PASS)
 	this->namepool_.add((*p)->name(), false, NULL);
     }
-  return off;
+  return maxoff;
 }
 
 // Set the section indexes of all the sections not associated with a
@@ -2980,9 +3244,8 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
   else
     gold_unreachable();
 
-  off_t off = *poff;
-  off = align_address(off, align);
-  off_t startoff = off;
+  // Compute file offsets relative to the start of the symtab section.
+  off_t off = 0;
 
   // Save space for the dummy symbol at the start of the section.  We
   // never bother to write this out--it will just be left as zero.
@@ -3015,7 +3278,7 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
     }
 
   unsigned int local_symcount = local_symbol_index;
-  gold_assert(static_cast<off_t>(local_symcount * symsize) == off - startoff);
+  gold_assert(static_cast<off_t>(local_symcount * symsize) == off);
 
   off_t dynoff;
   size_t dyn_global_index;
@@ -3036,6 +3299,7 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
 		  == this->dynsym_section_->data_size() - locsize);
     }
 
+  off_t global_off = off;
   off = symtab->finalize(off, dynoff, dyn_global_index, dyncount,
 			 &this->sympool_, &local_symcount);
 
@@ -3050,8 +3314,7 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
 							  false);
       this->symtab_section_ = osymtab;
 
-      Output_section_data* pos = new Output_data_fixed_space(off - startoff,
-							     align,
+      Output_section_data* pos = new Output_data_fixed_space(off, align,
 							     "** symtab");
       osymtab->add_output_section_data(pos);
 
@@ -3071,7 +3334,7 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
 				      elfcpp::SHT_SYMTAB_SHNDX, 0,
 				      ORDER_INVALID, false);
 
-	  size_t symcount = (off - startoff) / symsize;
+	  size_t symcount = off / symsize;
 	  this->symtab_xindex_ = new Output_symtab_xindex(symcount);
 
 	  osymtab_xindex->add_output_section_data(this->symtab_xindex_);
@@ -3097,13 +3360,30 @@ Layout::create_symtab_sections(const Input_objects* input_objects,
       Output_section_data* pstr = new Output_data_strtab(&this->sympool_);
       ostrtab->add_output_section_data(pstr);
 
-      osymtab->set_file_offset(startoff);
+      off_t symtab_off;
+      if (!parameters->incremental_update())
+	symtab_off = align_address(*poff, align);
+      else
+	{
+	  symtab_off = this->allocate(off, align, *poff);
+          if (off == -1)
+	    gold_fatal(_("out of patch space for symbol table; "
+		         "relink with --incremental-full"));
+	  gold_debug(DEBUG_INCREMENTAL,
+		     "create_symtab_sections: %08lx %08lx .symtab",
+		     static_cast<long>(symtab_off),
+		     static_cast<long>(off));
+	}
+
+      symtab->set_file_offset(symtab_off + global_off);
+      osymtab->set_file_offset(symtab_off);
       osymtab->finalize_data_size();
       osymtab->set_link_section(ostrtab);
       osymtab->set_info(local_symcount);
       osymtab->set_entsize(symsize);
 
-      *poff = off;
+      if (symtab_off + off > *poff)
+	*poff = symtab_off + off;
     }
 }
 
@@ -3150,10 +3430,25 @@ Layout::create_shdrs(const Output_section* shstrtab_section, off_t* poff)
 				      &this->unattached_section_list_,
 				      &this->namepool_,
 				      shstrtab_section);
-  off_t off = align_address(*poff, oshdrs->addralign());
+  off_t off;
+  if (!parameters->incremental_update())
+    off = align_address(*poff, oshdrs->addralign());
+  else
+    {
+      oshdrs->pre_finalize_data_size();
+      off = this->allocate(oshdrs->data_size(), oshdrs->addralign(), *poff);
+      if (off == -1)
+	  gold_fatal(_("out of patch space for section header table; "
+		       "relink with --incremental-full"));
+      gold_debug(DEBUG_INCREMENTAL,
+		 "create_shdrs: %08lx %08lx (section header table)",
+		 static_cast<long>(off),
+		 static_cast<long>(off + oshdrs->data_size()));
+    }
   oshdrs->set_address_and_file_offset(0, off);
   off += oshdrs->data_size();
-  *poff = off;
+  if (off > *poff)
+    *poff = off;
   this->section_headers_ = oshdrs;
 }
 
@@ -3667,6 +3962,7 @@ Layout::finish_dynamic_section(const Input_objects* input_objects,
        ++p)
     {
       if (!(*p)->is_needed()
+	  && !(*p)->is_incremental()
 	  && (*p)->input_file()->options().as_needed())
 	{
 	  // This dynamic object was linked with --as-needed, but it
@@ -4424,6 +4720,38 @@ Close_task_runner::run(Workqueue*, const Task*)
 #ifdef HAVE_TARGET_32_LITTLE
 template
 Output_section*
+Layout::init_fixed_output_section<32, false>(
+    const char* name,
+    elfcpp::Shdr<32, false>& shdr);
+#endif
+
+#ifdef HAVE_TARGET_32_BIG
+template
+Output_section*
+Layout::init_fixed_output_section<32, true>(
+    const char* name,
+    elfcpp::Shdr<32, true>& shdr);
+#endif
+
+#ifdef HAVE_TARGET_64_LITTLE
+template
+Output_section*
+Layout::init_fixed_output_section<64, false>(
+    const char* name,
+    elfcpp::Shdr<64, false>& shdr);
+#endif
+
+#ifdef HAVE_TARGET_64_BIG
+template
+Output_section*
+Layout::init_fixed_output_section<64, true>(
+    const char* name,
+    elfcpp::Shdr<64, true>& shdr);
+#endif
+
+#ifdef HAVE_TARGET_32_LITTLE
+template
+Output_section*
 Layout::layout<32, false>(Sized_relobj<32, false>* object, unsigned int shndx,
 			  const char* name,
 			  const elfcpp::Shdr<32, false>& shdr,