gold/output.cc

// output.cc -- manage the output file for gold

// Copyright (C) 2006-2024 Free Software Foundation, Inc.
// Written by Ian Lance Taylor <iant@google.com>.

// This file is part of gold.

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
// MA 02110-1301, USA.

#include "gold.h"

#include <cstdlib>
#include <cstring>
#include <cerrno>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <algorithm>
#include <uchar.h>

#ifdef HAVE_SYS_MMAN_H
#include <sys/mman.h>
#endif

#include "libiberty.h"

#include "dwarf.h"
#include "parameters.h"
#include "object.h"
#include "symtab.h"
#include "reloc.h"
#include "merge.h"
#include "descriptors.h"
#include "layout.h"
#include "output.h"

// For systems without mmap support.
#ifndef HAVE_MMAP
# define mmap gold_mmap
# define munmap gold_munmap
# define mremap gold_mremap
# ifndef MAP_FAILED
#  define MAP_FAILED (reinterpret_cast<void*>(-1))
# endif
# ifndef PROT_READ
#  define PROT_READ 0
# endif
# ifndef PROT_WRITE
#  define PROT_WRITE 0
# endif
# ifndef MAP_PRIVATE
#  define MAP_PRIVATE 0
# endif
# ifndef MAP_ANONYMOUS
#  define MAP_ANONYMOUS 0
# endif
# ifndef MAP_SHARED
#  define MAP_SHARED 0
# endif

# ifndef ENOSYS
#  define ENOSYS EINVAL
# endif

static void *
gold_mmap(void *, size_t, int, int, int, off_t)
{
  errno = ENOSYS;
  return MAP_FAILED;
}

static int
gold_munmap(void *, size_t)
{
  errno = ENOSYS;
  return -1;
}

static void *
gold_mremap(void *, size_t, size_t, int)
{
  errno = ENOSYS;
  return MAP_FAILED;
}

#endif

#if defined(HAVE_MMAP) && !defined(HAVE_MREMAP)
# define mremap gold_mremap
extern "C" void *gold_mremap(void *, size_t, size_t, int);
#endif

// Some BSD systems still use MAP_ANON instead of MAP_ANONYMOUS
#ifndef MAP_ANONYMOUS
# define MAP_ANONYMOUS  MAP_ANON
#endif

#ifndef MREMAP_MAYMOVE
# define MREMAP_MAYMOVE 1
#endif

// Mingw does not have S_ISLNK.
#ifndef S_ISLNK
# define S_ISLNK(mode) 0
#endif

namespace gold
{

// A wrapper around posix_fallocate.  If we don't have posix_fallocate,
// or the --no-posix-fallocate option is set, we try the fallocate
// system call directly.  If that fails, we use ftruncate to set
// the file size and hope that there is enough disk space.

static int
gold_fallocate(int o, off_t offset, off_t len)
{
  if (len <= 0)
    return 0;

#ifdef HAVE_POSIX_FALLOCATE
  if (parameters->options().posix_fallocate())
    {
      int err = ::posix_fallocate(o, offset, len);
      if (err != EINVAL && err != ENOSYS && err != EOPNOTSUPP)
	return err;
    }
#endif // defined(HAVE_POSIX_FALLOCATE)

#ifdef HAVE_FALLOCATE
  {
    errno = 0;
    int err = ::fallocate(o, 0, offset, len);
    if (err < 0 && errno != EINVAL && errno != ENOSYS && errno != EOPNOTSUPP)
      return errno;
  }
#endif // defined(HAVE_FALLOCATE)

  errno = 0;
  if (::ftruncate(o, offset + len) < 0)
    return errno;
  return 0;
}

// Output_data variables.

bool Output_data::allocated_sizes_are_fixed;

// Output_data methods.

Output_data::~Output_data()
{
}

// Return the default alignment for the target size.

uint64_t
Output_data::default_alignment()
{
  return Output_data::default_alignment_for_size(
      parameters->target().get_size());
}

// Return the default alignment for a size--32 or 64.

uint64_t
Output_data::default_alignment_for_size(int size)
{
  if (size == 32)
    return 4;
  else if (size == 64)
    return 8;
  else
    gold_unreachable();
}

// Output_section_header methods.  This currently assumes that the
// segment and section lists are complete at construction time.

Output_section_headers::Output_section_headers(
    const Layout* layout,
    const Layout::Segment_list* segment_list,
    const Layout::Section_list* section_list,
    const Layout::Section_list* unattached_section_list,
    const Stringpool* secnamepool,
    const Output_section* shstrtab_section)
  : layout_(layout),
    segment_list_(segment_list),
    section_list_(section_list),
    unattached_section_list_(unattached_section_list),
    secnamepool_(secnamepool),
    shstrtab_section_(shstrtab_section)
{
}

// Compute the current data size.

off_t
Output_section_headers::do_size() const
{
  // Count all the sections.  Start with 1 for the null section.
  off_t count = 1;
  if (!parameters->options().relocatable())
    {
      for (Layout::Segment_list::const_iterator p =
	     this->segment_list_->begin();
	   p != this->segment_list_->end();
	   ++p)
	if ((*p)->type() == elfcpp::PT_LOAD)
	  count += (*p)->output_section_count();
    }
  else
    {
      for (Layout::Section_list::const_iterator p =
	     this->section_list_->begin();
	   p != this->section_list_->end();
	   ++p)
	if (((*p)->flags() & elfcpp::SHF_ALLOC) != 0)
	  ++count;
    }
  count += this->unattached_section_list_->size();

  const int size = parameters->target().get_size();
  int shdr_size;
  if (size == 32)
    shdr_size = elfcpp::Elf_sizes<32>::shdr_size;
  else if (size == 64)
    shdr_size = elfcpp::Elf_sizes<64>::shdr_size;
  else
    gold_unreachable();

  return count * shdr_size;
}

// Write out the section headers.

void
Output_section_headers::do_write(Output_file* of)
{
  switch (parameters->size_and_endianness())
    {
#ifdef HAVE_TARGET_32_LITTLE
    case Parameters::TARGET_32_LITTLE:
      this->do_sized_write<32, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_32_BIG
    case Parameters::TARGET_32_BIG:
      this->do_sized_write<32, true>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_LITTLE
    case Parameters::TARGET_64_LITTLE:
      this->do_sized_write<64, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_BIG
    case Parameters::TARGET_64_BIG:
      this->do_sized_write<64, true>(of);
      break;
#endif
    default:
      gold_unreachable();
    }
}

template<int size, bool big_endian>
void
Output_section_headers::do_sized_write(Output_file* of)
{
  off_t all_shdrs_size = this->data_size();
  unsigned char* view = of->get_output_view(this->offset(), all_shdrs_size);

  const int shdr_size = elfcpp::Elf_sizes<size>::shdr_size;
  unsigned char* v = view;

  {
    typename elfcpp::Shdr_write<size, big_endian> oshdr(v);
    oshdr.put_sh_name(0);
    oshdr.put_sh_type(elfcpp::SHT_NULL);
    oshdr.put_sh_flags(0);
    oshdr.put_sh_addr(0);
    oshdr.put_sh_offset(0);

    size_t section_count = (this->data_size()
			    / elfcpp::Elf_sizes<size>::shdr_size);
    if (section_count < elfcpp::SHN_LORESERVE)
      oshdr.put_sh_size(0);
    else
      oshdr.put_sh_size(section_count);

    unsigned int shstrndx = this->shstrtab_section_->out_shndx();
    if (shstrndx < elfcpp::SHN_LORESERVE)
      oshdr.put_sh_link(0);
    else
      oshdr.put_sh_link(shstrndx);

    size_t segment_count = this->segment_list_->size();
    oshdr.put_sh_info(segment_count >= elfcpp::PN_XNUM ? segment_count : 0);

    oshdr.put_sh_addralign(0);
    oshdr.put_sh_entsize(0);
  }

  v += shdr_size;

  unsigned int shndx = 1;
  if (!parameters->options().relocatable())
    {
      for (Layout::Segment_list::const_iterator p =
	     this->segment_list_->begin();
	   p != this->segment_list_->end();
	   ++p)
	v = (*p)->write_section_headers<size, big_endian>(this->layout_,
							  this->secnamepool_,
							  v,
							  &shndx);
    }
  else
    {
      for (Layout::Section_list::const_iterator p =
	     this->section_list_->begin();
	   p != this->section_list_->end();
	   ++p)
	{
	  // We do unallocated sections below, except that group
	  // sections have to come first.
	  if (((*p)->flags() & elfcpp::SHF_ALLOC) == 0
	      && (*p)->type() != elfcpp::SHT_GROUP)
	    continue;
	  gold_assert(shndx == (*p)->out_shndx());
	  elfcpp::Shdr_write<size, big_endian> oshdr(v);
	  (*p)->write_header(this->layout_, this->secnamepool_, &oshdr);
	  v += shdr_size;
	  ++shndx;
	}
    }

  for (Layout::Section_list::const_iterator p =
	 this->unattached_section_list_->begin();
       p != this->unattached_section_list_->end();
       ++p)
    {
      // For a relocatable link, we did unallocated group sections
      // above, since they have to come first.
      if ((*p)->type() == elfcpp::SHT_GROUP
	  && parameters->options().relocatable())
	continue;
      gold_assert(shndx == (*p)->out_shndx());
      elfcpp::Shdr_write<size, big_endian> oshdr(v);
      (*p)->write_header(this->layout_, this->secnamepool_, &oshdr);
      v += shdr_size;
      ++shndx;
    }

  of->write_output_view(this->offset(), all_shdrs_size, view);
}

// Output_segment_header methods.

Output_segment_headers::Output_segment_headers(
    const Layout::Segment_list& segment_list)
  : segment_list_(segment_list)
{
  this->set_current_data_size_for_child(this->do_size());
}

void
Output_segment_headers::do_write(Output_file* of)
{
  switch (parameters->size_and_endianness())
    {
#ifdef HAVE_TARGET_32_LITTLE
    case Parameters::TARGET_32_LITTLE:
      this->do_sized_write<32, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_32_BIG
    case Parameters::TARGET_32_BIG:
      this->do_sized_write<32, true>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_LITTLE
    case Parameters::TARGET_64_LITTLE:
      this->do_sized_write<64, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_BIG
    case Parameters::TARGET_64_BIG:
      this->do_sized_write<64, true>(of);
      break;
#endif
    default:
      gold_unreachable();
    }
}

template<int size, bool big_endian>
void
Output_segment_headers::do_sized_write(Output_file* of)
{
  const int phdr_size = elfcpp::Elf_sizes<size>::phdr_size;
  off_t all_phdrs_size = this->segment_list_.size() * phdr_size;
  gold_assert(all_phdrs_size == this->data_size());
  unsigned char* view = of->get_output_view(this->offset(),
					    all_phdrs_size);
  unsigned char* v = view;
  for (Layout::Segment_list::const_iterator p = this->segment_list_.begin();
       p != this->segment_list_.end();
       ++p)
    {
      elfcpp::Phdr_write<size, big_endian> ophdr(v);
      (*p)->write_header(&ophdr);
      v += phdr_size;
    }

  gold_assert(v - view == all_phdrs_size);

  of->write_output_view(this->offset(), all_phdrs_size, view);
}

off_t
Output_segment_headers::do_size() const
{
  const int size = parameters->target().get_size();
  int phdr_size;
  if (size == 32)
    phdr_size = elfcpp::Elf_sizes<32>::phdr_size;
  else if (size == 64)
    phdr_size = elfcpp::Elf_sizes<64>::phdr_size;
  else
    gold_unreachable();

  return this->segment_list_.size() * phdr_size;
}

// Output_file_header methods.

Output_file_header::Output_file_header(Target* target,
				       const Symbol_table* symtab,
				       const Output_segment_headers* osh)
  : target_(target),
    symtab_(symtab),
    segment_header_(osh),
    section_header_(NULL),
    shstrtab_(NULL)
{
  this->set_data_size(this->do_size());
}

// Set the section table information for a file header.

void
Output_file_header::set_section_info(const Output_section_headers* shdrs,
				     const Output_section* shstrtab)
{
  this->section_header_ = shdrs;
  this->shstrtab_ = shstrtab;
}

// Write out the file header.

void
Output_file_header::do_write(Output_file* of)
{
  gold_assert(this->offset() == 0);

  switch (parameters->size_and_endianness())
    {
#ifdef HAVE_TARGET_32_LITTLE
    case Parameters::TARGET_32_LITTLE:
      this->do_sized_write<32, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_32_BIG
    case Parameters::TARGET_32_BIG:
      this->do_sized_write<32, true>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_LITTLE
    case Parameters::TARGET_64_LITTLE:
      this->do_sized_write<64, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_BIG
    case Parameters::TARGET_64_BIG:
      this->do_sized_write<64, true>(of);
      break;
#endif
    default:
      gold_unreachable();
    }
}

// Write out the file header with appropriate size and endianness.

template<int size, bool big_endian>
void
Output_file_header::do_sized_write(Output_file* of)
{
  gold_assert(this->offset() == 0);

  int ehdr_size = elfcpp::Elf_sizes<size>::ehdr_size;
  unsigned char* view = of->get_output_view(0, ehdr_size);
  elfcpp::Ehdr_write<size, big_endian> oehdr(view);

  unsigned char e_ident[elfcpp::EI_NIDENT];
  memset(e_ident, 0, elfcpp::EI_NIDENT);
  e_ident[elfcpp::EI_MAG0] = elfcpp::ELFMAG0;
  e_ident[elfcpp::EI_MAG1] = elfcpp::ELFMAG1;
  e_ident[elfcpp::EI_MAG2] = elfcpp::ELFMAG2;
  e_ident[elfcpp::EI_MAG3] = elfcpp::ELFMAG3;
  if (size == 32)
    e_ident[elfcpp::EI_CLASS] = elfcpp::ELFCLASS32;
  else if (size == 64)
    e_ident[elfcpp::EI_CLASS] = elfcpp::ELFCLASS64;
  else
    gold_unreachable();
  e_ident[elfcpp::EI_DATA] = (big_endian
			      ? elfcpp::ELFDATA2MSB
			      : elfcpp::ELFDATA2LSB);
  e_ident[elfcpp::EI_VERSION] = elfcpp::EV_CURRENT;
  oehdr.put_e_ident(e_ident);

  elfcpp::ET e_type;
  if (parameters->options().relocatable())
    e_type = elfcpp::ET_REL;
  else if (parameters->options().output_is_position_independent())
    e_type = elfcpp::ET_DYN;
  else
    e_type = elfcpp::ET_EXEC;
  oehdr.put_e_type(e_type);

  oehdr.put_e_machine(this->target_->machine_code());
  oehdr.put_e_version(elfcpp::EV_CURRENT);

  oehdr.put_e_entry(this->entry<size>());

  if (this->segment_header_ == NULL)
    oehdr.put_e_phoff(0);
  else
    oehdr.put_e_phoff(this->segment_header_->offset());

  oehdr.put_e_shoff(this->section_header_->offset());
  oehdr.put_e_flags(this->target_->processor_specific_flags());
  oehdr.put_e_ehsize(elfcpp::Elf_sizes<size>::ehdr_size);

  if (this->segment_header_ == NULL)
    {
      oehdr.put_e_phentsize(0);
      oehdr.put_e_phnum(0);
    }
  else
    {
      oehdr.put_e_phentsize(elfcpp::Elf_sizes<size>::phdr_size);
      size_t phnum = (this->segment_header_->data_size()
		      / elfcpp::Elf_sizes<size>::phdr_size);
      if (phnum > elfcpp::PN_XNUM)
	phnum = elfcpp::PN_XNUM;
      oehdr.put_e_phnum(phnum);
    }

  oehdr.put_e_shentsize(elfcpp::Elf_sizes<size>::shdr_size);
  size_t section_count = (this->section_header_->data_size()
			  / elfcpp::Elf_sizes<size>::shdr_size);

  if (section_count < elfcpp::SHN_LORESERVE)
    oehdr.put_e_shnum(this->section_header_->data_size()
		      / elfcpp::Elf_sizes<size>::shdr_size);
  else
    oehdr.put_e_shnum(0);

  unsigned int shstrndx = this->shstrtab_->out_shndx();
  if (shstrndx < elfcpp::SHN_LORESERVE)
    oehdr.put_e_shstrndx(this->shstrtab_->out_shndx());
  else
    oehdr.put_e_shstrndx(elfcpp::SHN_XINDEX);

  // Let the target adjust the ELF header, e.g., to set EI_OSABI in
  // the e_ident field.
  this->target_->adjust_elf_header(view, ehdr_size);

  of->write_output_view(0, ehdr_size, view);
}

// Return the value to use for the entry address.

template<int size>
typename elfcpp::Elf_types<size>::Elf_Addr
Output_file_header::entry()
{
  const bool should_issue_warning = (parameters->options().entry() != NULL
				     && !parameters->options().relocatable()
				     && !parameters->options().shared());
  const char* entry = parameters->entry();
  Symbol* sym = this->symtab_->lookup(entry);

  typename Sized_symbol<size>::Value_type v;
  if (sym != NULL)
    {
      Sized_symbol<size>* ssym;
      ssym = this->symtab_->get_sized_symbol<size>(sym);
      if (!ssym->is_defined() && should_issue_warning)
	gold_warning("entry symbol '%s' exists but is not defined", entry);
      v = ssym->value();
    }
  else
    {
      // We couldn't find the entry symbol.  See if we can parse it as
      // a number.  This supports, e.g., -e 0x1000.
      char* endptr;
      v = strtoull(entry, &endptr, 0);
      if (*endptr != '\0')
	{
	  if (should_issue_warning)
	    gold_warning("cannot find entry symbol '%s'", entry);
	  v = 0;
	}
    }

  return v;
}

// Compute the current data size.

off_t
Output_file_header::do_size() const
{
  const int size = parameters->target().get_size();
  if (size == 32)
    return elfcpp::Elf_sizes<32>::ehdr_size;
  else if (size == 64)
    return elfcpp::Elf_sizes<64>::ehdr_size;
  else
    gold_unreachable();
}

// Output_data_const methods.

void
Output_data_const::do_write(Output_file* of)
{
  of->write(this->offset(), this->data_.data(), this->data_.size());
}

// Output_data_const_buffer methods.

void
Output_data_const_buffer::do_write(Output_file* of)
{
  of->write(this->offset(), this->p_, this->data_size());
}

// Output_section_data methods.

// Record the output section, and set the entry size and such.

void
Output_section_data::set_output_section(Output_section* os)
{
  gold_assert(this->output_section_ == NULL);
  this->output_section_ = os;
  this->do_adjust_output_section(os);
}

// Return the section index of the output section.

unsigned int
Output_section_data::do_out_shndx() const
{
  gold_assert(this->output_section_ != NULL);
  return this->output_section_->out_shndx();
}

// Set the alignment, which means we may need to update the alignment
// of the output section.

void
Output_section_data::set_addralign(uint64_t addralign)
{
  this->addralign_ = addralign;
  if (this->output_section_ != NULL
      && this->output_section_->addralign() < addralign)
    this->output_section_->set_addralign(addralign);
}

// Output_data_strtab methods.

// Set the final data size.

void
Output_data_strtab::set_final_data_size()
{
  this->strtab_->set_string_offsets();
  this->set_data_size(this->strtab_->get_strtab_size());
}

// Write out a string table.

void
Output_data_strtab::do_write(Output_file* of)
{
  this->strtab_->write(of, this->offset());
}

// Output_reloc methods.

// A reloc against a global symbol.

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Symbol* gsym,
    unsigned int type,
    Output_data* od,
    Address address,
    bool is_relative,
    bool is_symbolless,
    bool use_plt_offset)
  : address_(address), local_sym_index_(GSYM_CODE), type_(type),
    is_relative_(is_relative), is_symbolless_(is_symbolless),
    is_section_symbol_(false), use_plt_offset_(use_plt_offset), shndx_(INVALID_CODE)
{
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.gsym = gsym;
  this->u2_.od = od;
  if (dynamic)
    this->set_needs_dynsym_index();
}

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Symbol* gsym,
    unsigned int type,
    Sized_relobj<size, big_endian>* relobj,
    unsigned int shndx,
    Address address,
    bool is_relative,
    bool is_symbolless,
    bool use_plt_offset)
  : address_(address), local_sym_index_(GSYM_CODE), type_(type),
    is_relative_(is_relative), is_symbolless_(is_symbolless),
    is_section_symbol_(false), use_plt_offset_(use_plt_offset), shndx_(shndx)
{
  gold_assert(shndx != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.gsym = gsym;
  this->u2_.relobj = relobj;
  if (dynamic)
    this->set_needs_dynsym_index();
}

// A reloc against a local symbol.

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Sized_relobj<size, big_endian>* relobj,
    unsigned int local_sym_index,
    unsigned int type,
    Output_data* od,
    Address address,
    bool is_relative,
    bool is_symbolless,
    bool is_section_symbol,
    bool use_plt_offset)
  : address_(address), local_sym_index_(local_sym_index), type_(type),
    is_relative_(is_relative), is_symbolless_(is_symbolless),
    is_section_symbol_(is_section_symbol), use_plt_offset_(use_plt_offset),
    shndx_(INVALID_CODE)
{
  gold_assert(local_sym_index != GSYM_CODE
	      && local_sym_index != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.relobj = relobj;
  this->u2_.od = od;
  if (dynamic)
    this->set_needs_dynsym_index();
}

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Sized_relobj<size, big_endian>* relobj,
    unsigned int local_sym_index,
    unsigned int type,
    unsigned int shndx,
    Address address,
    bool is_relative,
    bool is_symbolless,
    bool is_section_symbol,
    bool use_plt_offset)
  : address_(address), local_sym_index_(local_sym_index), type_(type),
    is_relative_(is_relative), is_symbolless_(is_symbolless),
    is_section_symbol_(is_section_symbol), use_plt_offset_(use_plt_offset),
    shndx_(shndx)
{
  gold_assert(local_sym_index != GSYM_CODE
	      && local_sym_index != INVALID_CODE);
  gold_assert(shndx != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.relobj = relobj;
  this->u2_.relobj = relobj;
  if (dynamic)
    this->set_needs_dynsym_index();
}

// A reloc against the STT_SECTION symbol of an output section.

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Output_section* os,
    unsigned int type,
    Output_data* od,
    Address address,
    bool is_relative)
  : address_(address), local_sym_index_(SECTION_CODE), type_(type),
    is_relative_(is_relative), is_symbolless_(is_relative),
    is_section_symbol_(true), use_plt_offset_(false), shndx_(INVALID_CODE)
{
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.os = os;
  this->u2_.od = od;
  if (dynamic)
    this->set_needs_dynsym_index();
  else
    os->set_needs_symtab_index();
}

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    Output_section* os,
    unsigned int type,
    Sized_relobj<size, big_endian>* relobj,
    unsigned int shndx,
    Address address,
    bool is_relative)
  : address_(address), local_sym_index_(SECTION_CODE), type_(type),
    is_relative_(is_relative), is_symbolless_(is_relative),
    is_section_symbol_(true), use_plt_offset_(false), shndx_(shndx)
{
  gold_assert(shndx != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.os = os;
  this->u2_.relobj = relobj;
  if (dynamic)
    this->set_needs_dynsym_index();
  else
    os->set_needs_symtab_index();
}

// An absolute or relative relocation.

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    unsigned int type,
    Output_data* od,
    Address address,
    bool is_relative)
  : address_(address), local_sym_index_(0), type_(type),
    is_relative_(is_relative), is_symbolless_(false),
    is_section_symbol_(false), use_plt_offset_(false), shndx_(INVALID_CODE)
{
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.relobj = NULL;
  this->u2_.od = od;
}

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    unsigned int type,
    Sized_relobj<size, big_endian>* relobj,
    unsigned int shndx,
    Address address,
    bool is_relative)
  : address_(address), local_sym_index_(0), type_(type),
    is_relative_(is_relative), is_symbolless_(false),
    is_section_symbol_(false), use_plt_offset_(false), shndx_(shndx)
{
  gold_assert(shndx != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.relobj = NULL;
  this->u2_.relobj = relobj;
}

// A target specific relocation.

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    unsigned int type,
    void* arg,
    Output_data* od,
    Address address)
  : address_(address), local_sym_index_(TARGET_CODE), type_(type),
    is_relative_(false), is_symbolless_(false),
    is_section_symbol_(false), use_plt_offset_(false), shndx_(INVALID_CODE)
{
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.arg = arg;
  this->u2_.od = od;
}

template<bool dynamic, int size, bool big_endian>
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::Output_reloc(
    unsigned int type,
    void* arg,
    Sized_relobj<size, big_endian>* relobj,
    unsigned int shndx,
    Address address)
  : address_(address), local_sym_index_(TARGET_CODE), type_(type),
    is_relative_(false), is_symbolless_(false),
    is_section_symbol_(false), use_plt_offset_(false), shndx_(shndx)
{
  gold_assert(shndx != INVALID_CODE);
  // this->type_ is a bitfield; make sure TYPE fits.
  gold_assert(this->type_ == type);
  this->u1_.arg = arg;
  this->u2_.relobj = relobj;
}

// Record that we need a dynamic symbol index for this relocation.

template<bool dynamic, int size, bool big_endian>
void
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::
set_needs_dynsym_index()
{
  if (this->is_symbolless_)
    return;
  switch (this->local_sym_index_)
    {
    case INVALID_CODE:
      gold_unreachable();

    case GSYM_CODE:
      this->u1_.gsym->set_needs_dynsym_entry();
      break;

    case SECTION_CODE:
      this->u1_.os->set_needs_dynsym_index();
      break;

    case TARGET_CODE:
      // The target must take care of this if necessary.
      break;

    case 0:
      break;

    default:
      {
	const unsigned int lsi = this->local_sym_index_;
	Sized_relobj_file<size, big_endian>* relobj =
	    this->u1_.relobj->sized_relobj();
	gold_assert(relobj != NULL);
	if (!this->is_section_symbol_)
	  relobj->set_needs_output_dynsym_entry(lsi);
	else
	  relobj->output_section(lsi)->set_needs_dynsym_index();
      }
      break;
    }
}

// Get the symbol index of a relocation.

template<bool dynamic, int size, bool big_endian>
unsigned int
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::get_symbol_index()
  const
{
  unsigned int index;
  if (this->is_symbolless_)
    return 0;
  switch (this->local_sym_index_)
    {
    case INVALID_CODE:
      gold_unreachable();

    case GSYM_CODE:
      if (this->u1_.gsym == NULL)
	index = 0;
      else if (dynamic)
	index = this->u1_.gsym->dynsym_index();
      else
	index = this->u1_.gsym->symtab_index();
      break;

    case SECTION_CODE:
      if (dynamic)
	index = this->u1_.os->dynsym_index();
      else
	index = this->u1_.os->symtab_index();
      break;

    case TARGET_CODE:
      index = parameters->target().reloc_symbol_index(this->u1_.arg,
						      this->type_);
      break;

    case 0:
      // Relocations without symbols use a symbol index of 0.
      index = 0;
      break;

    default:
      {
	const unsigned int lsi = this->local_sym_index_;
	Sized_relobj_file<size, big_endian>* relobj =
	    this->u1_.relobj->sized_relobj();
	gold_assert(relobj != NULL);
	if (!this->is_section_symbol_)
	  {
	    if (dynamic)
	      index = relobj->dynsym_index(lsi);
	    else
	      index = relobj->symtab_index(lsi);
	  }
	else
	  {
	    Output_section* os = relobj->output_section(lsi);
	    gold_assert(os != NULL);
	    if (dynamic)
	      index = os->dynsym_index();
	    else
	      index = os->symtab_index();
	  }
      }
      break;
    }
  gold_assert(index != -1U);
  return index;
}

// For a local section symbol, get the address of the offset ADDEND
// within the input section.

template<bool dynamic, int size, bool big_endian>
typename elfcpp::Elf_types<size>::Elf_Addr
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::
  local_section_offset(Addend addend) const
{
  gold_assert(this->local_sym_index_ != GSYM_CODE
	      && this->local_sym_index_ != SECTION_CODE
	      && this->local_sym_index_ != TARGET_CODE
	      && this->local_sym_index_ != INVALID_CODE
	      && this->local_sym_index_ != 0
	      && this->is_section_symbol_);
  const unsigned int lsi = this->local_sym_index_;
  Output_section* os = this->u1_.relobj->output_section(lsi);
  gold_assert(os != NULL);
  Address offset = this->u1_.relobj->get_output_section_offset(lsi);
  if (offset != invalid_address)
    return offset + addend;
  // This is a merge section.
  Sized_relobj_file<size, big_endian>* relobj =
      this->u1_.relobj->sized_relobj();
  gold_assert(relobj != NULL);
  offset = os->output_address(relobj, lsi, addend);
  gold_assert(offset != invalid_address);
  return offset;
}

// Get the output address of a relocation.

template<bool dynamic, int size, bool big_endian>
typename elfcpp::Elf_types<size>::Elf_Addr
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::get_address() const
{
  Address address = this->address_;
  if (this->shndx_ != INVALID_CODE)
    {
      Output_section* os = this->u2_.relobj->output_section(this->shndx_);
      gold_assert(os != NULL);
      Address off = this->u2_.relobj->get_output_section_offset(this->shndx_);
      if (off != invalid_address)
	address += os->address() + off;
      else
	{
	  Sized_relobj_file<size, big_endian>* relobj =
	      this->u2_.relobj->sized_relobj();
	  gold_assert(relobj != NULL);
	  address = os->output_address(relobj, this->shndx_, address);
	  gold_assert(address != invalid_address);
	}
    }
  else if (this->u2_.od != NULL)
    address += this->u2_.od->address();
  return address;
}

// Write out the offset and info fields of a Rel or Rela relocation
// entry.

template<bool dynamic, int size, bool big_endian>
template<typename Write_rel>
void
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::write_rel(
    Write_rel* wr) const
{
  wr->put_r_offset(this->get_address());
  unsigned int sym_index = this->get_symbol_index();
  wr->put_r_info(elfcpp::elf_r_info<size>(sym_index, this->type_));
}

// Write out a Rel relocation.

template<bool dynamic, int size, bool big_endian>
void
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::write(
    unsigned char* pov) const
{
  elfcpp::Rel_write<size, big_endian> orel(pov);
  this->write_rel(&orel);
}

// Get the value of the symbol referred to by a Rel relocation.

template<bool dynamic, int size, bool big_endian>
typename elfcpp::Elf_types<size>::Elf_Addr
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::symbol_value(
    Addend addend) const
{
  if (this->local_sym_index_ == GSYM_CODE)
    {
      const Sized_symbol<size>* sym;
      sym = static_cast<const Sized_symbol<size>*>(this->u1_.gsym);
      if (this->use_plt_offset_ && sym->has_plt_offset())
	return parameters->target().plt_address_for_global(sym);
      else
	return sym->value() + addend;
    }
  if (this->local_sym_index_ == SECTION_CODE)
    {
      gold_assert(!this->use_plt_offset_);
      return this->u1_.os->address() + addend;
    }
  gold_assert(this->local_sym_index_ != TARGET_CODE
	      && this->local_sym_index_ != INVALID_CODE
	      && this->local_sym_index_ != 0
	      && !this->is_section_symbol_);
  const unsigned int lsi = this->local_sym_index_;
  Sized_relobj_file<size, big_endian>* relobj =
      this->u1_.relobj->sized_relobj();
  gold_assert(relobj != NULL);
  if (this->use_plt_offset_)
    return parameters->target().plt_address_for_local(relobj, lsi);
  const Symbol_value<size>* symval = relobj->local_symbol(lsi);
  return symval->value(relobj, addend);
}

// Reloc comparison.  This function sorts the dynamic relocs for the
// benefit of the dynamic linker.  First we sort all relative relocs
// to the front.  Among relative relocs, we sort by output address.
// Among non-relative relocs, we sort by symbol index, then by output
// address.

template<bool dynamic, int size, bool big_endian>
int
Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::
  compare(const Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>& r2)
    const
{
  if (this->is_relative_)
    {
      if (!r2.is_relative_)
	return -1;
      // Otherwise sort by reloc address below.
    }
  else if (r2.is_relative_)
    return 1;
  else
    {
      unsigned int sym1 = this->get_symbol_index();
      unsigned int sym2 = r2.get_symbol_index();
      if (sym1 < sym2)
	return -1;
      else if (sym1 > sym2)
	return 1;
      // Otherwise sort by reloc address.
    }

  section_offset_type addr1 = this->get_address();
  section_offset_type addr2 = r2.get_address();
  if (addr1 < addr2)
    return -1;
  else if (addr1 > addr2)
    return 1;

  // Final tie breaker, in order to generate the same output on any
  // host: reloc type.
  unsigned int type1 = this->type_;
  unsigned int type2 = r2.type_;
  if (type1 < type2)
    return -1;
  else if (type1 > type2)
    return 1;

  // These relocs appear to be exactly the same.
  return 0;
}

// Write out a Rela relocation.

template<bool dynamic, int size, bool big_endian>
void
Output_reloc<elfcpp::SHT_RELA, dynamic, size, big_endian>::write(
    unsigned char* pov) const
{
  elfcpp::Rela_write<size, big_endian> orel(pov);
  this->rel_.write_rel(&orel);
  Addend addend = this->addend_;
  if (this->rel_.is_target_specific())
    addend = parameters->target().reloc_addend(this->rel_.target_arg(),
					       this->rel_.type(), addend);
  else if (this->rel_.is_symbolless())
    addend = this->rel_.symbol_value(addend);
  else if (this->rel_.is_local_section_symbol())
    addend = this->rel_.local_section_offset(addend);
  orel.put_r_addend(addend);
}

// Output_data_reloc_base methods.

// Adjust the output section.

template<int sh_type, bool dynamic, int size, bool big_endian>
void
Output_data_reloc_base<sh_type, dynamic, size, big_endian>
    ::do_adjust_output_section(Output_section* os)
{
  if (sh_type == elfcpp::SHT_REL)
    os->set_entsize(elfcpp::Elf_sizes<size>::rel_size);
  else if (sh_type == elfcpp::SHT_RELA)
    os->set_entsize(elfcpp::Elf_sizes<size>::rela_size);
  else
    gold_unreachable();

  // A STT_GNU_IFUNC symbol may require a IRELATIVE reloc when doing a
  // static link.  The backends will generate a dynamic reloc section
  // to hold this.  In that case we don't want to link to the dynsym
  // section, because there isn't one.
  if (!dynamic)
    os->set_should_link_to_symtab();
  else if (parameters->doing_static_link())
    ;
  else
    os->set_should_link_to_dynsym();
}

// Standard relocation writer, which just calls Output_reloc::write().

template<int sh_type, bool dynamic, int size, bool big_endian>
struct Output_reloc_writer
{
  typedef Output_reloc<sh_type, dynamic, size, big_endian> Output_reloc_type;
  typedef std::vector<Output_reloc_type> Relocs;

  static void
  write(typename Relocs::const_iterator p, unsigned char* pov)
  { p->write(pov); }
};

// Write out relocation data.

template<int sh_type, bool dynamic, int size, bool big_endian>
void
Output_data_reloc_base<sh_type, dynamic, size, big_endian>::do_write(
    Output_file* of)
{
  typedef Output_reloc_writer<sh_type, dynamic, size, big_endian> Writer;
  this->do_write_generic<Writer>(of);
}

// Class Output_relocatable_relocs.

template<int sh_type, int size, bool big_endian>
void
Output_relocatable_relocs<sh_type, size, big_endian>::set_final_data_size()
{
  this->set_data_size(this->rr_->output_reloc_count()
		      * Reloc_types<sh_type, size, big_endian>::reloc_size);
}

// class Output_data_group.

template<int size, bool big_endian>
Output_data_group<size, big_endian>::Output_data_group(
    Sized_relobj_file<size, big_endian>* relobj,
    section_size_type entry_count,
    elfcpp::Elf_Word flags,
    std::vector<unsigned int>* input_shndxes)
  : Output_section_data(entry_count * 4, 4, false),
    relobj_(relobj),
    flags_(flags)
{
  this->input_shndxes_.swap(*input_shndxes);
}

// Write out the section group, which means translating the section
// indexes to apply to the output file.

template<int size, bool big_endian>
void
Output_data_group<size, big_endian>::do_write(Output_file* of)
{
  const off_t off = this->offset();
  const section_size_type oview_size =
    convert_to_section_size_type(this->data_size());
  unsigned char* const oview = of->get_output_view(off, oview_size);

  elfcpp::Elf_Word* contents = reinterpret_cast<elfcpp::Elf_Word*>(oview);
  elfcpp::Swap<32, big_endian>::writeval(contents, this->flags_);
  ++contents;

  for (std::vector<unsigned int>::const_iterator p =
	 this->input_shndxes_.begin();
       p != this->input_shndxes_.end();
       ++p, ++contents)
    {
      Output_section* os = this->relobj_->output_section(*p);

      unsigned int output_shndx;
      if (os != NULL)
	output_shndx = os->out_shndx();
      else
	{
	  this->relobj_->error(_("section group retained but "
				 "group element discarded"));
	  output_shndx = 0;
	}

      elfcpp::Swap<32, big_endian>::writeval(contents, output_shndx);
    }

  size_t wrote = reinterpret_cast<unsigned char*>(contents) - oview;
  gold_assert(wrote == oview_size);

  of->write_output_view(off, oview_size, oview);

  // We no longer need this information.
  this->input_shndxes_.clear();
}

// Output_data_got::Got_entry methods.

// Write out the entry.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::Got_entry::write(
    Output_data_got_base* got,
    unsigned int got_indx,
    unsigned char* pov) const
{
  Valtype val = 0;

  switch (this->local_sym_index_)
    {
    case GSYM_CODE:
      {
	// If the symbol is resolved locally, we need to write out the
	// link-time value, which will be relocated dynamically by a
	// RELATIVE relocation.
	Symbol* gsym = this->u_.gsym;
	if (this->use_plt_or_tls_offset_ && gsym->has_plt_offset())
	  val = parameters->target().plt_address_for_global(gsym);
	else
	  {
	    switch (parameters->size_and_endianness())
	      {
#if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_32_BIG)
	      case Parameters::TARGET_32_LITTLE:
	      case Parameters::TARGET_32_BIG:
		{
		  // This cast is ugly.  We don't want to put a
		  // virtual method in Symbol, because we want Symbol
		  // to be as small as possible.
		  Sized_symbol<32>::Value_type v;
		  v = static_cast<Sized_symbol<32>*>(gsym)->value();
		  val = convert_types<Valtype, Sized_symbol<32>::Value_type>(v);
		}
		break;
#endif
#if defined(HAVE_TARGET_64_LITTLE) || defined(HAVE_TARGET_64_BIG)
	      case Parameters::TARGET_64_LITTLE:
	      case Parameters::TARGET_64_BIG:
		{
		  Sized_symbol<64>::Value_type v;
		  v = static_cast<Sized_symbol<64>*>(gsym)->value();
		  val = convert_types<Valtype, Sized_symbol<64>::Value_type>(v);
		}
		break;
#endif
	      default:
		gold_unreachable();
	      }
	    // If this is a GOT entry for a known value global symbol,
	    // then the value should include the addend.  If the value
	    // is not known leave the value as zero; The GOT entry
	    // will be set by a dynamic relocation.
	    if (this->addend_ && gsym->final_value_is_known())
	      val += this->addend_;
	    if (this->use_plt_or_tls_offset_
		&& gsym->type() == elfcpp::STT_TLS)
	      val += parameters->target().tls_offset_for_global(gsym,
								got, got_indx,
								this->addend_);
	  }
      }
      break;

    case CONSTANT_CODE:
      val = this->u_.constant;
      break;

    case RESERVED_CODE:
      // If we're doing an incremental update, don't touch this GOT entry.
      if (parameters->incremental_update())
	return;
      val = this->u_.constant;
      break;

    default:
      {
	const Relobj* object = this->u_.object;
	const unsigned int lsi = this->local_sym_index_;
	bool is_tls = object->local_is_tls(lsi);
	if (this->use_plt_or_tls_offset_ && !is_tls)
	  val = parameters->target().plt_address_for_local(object, lsi);
	else
	  {
	    uint64_t lval = object->local_symbol_value(lsi, this->addend_);
	    val = convert_types<Valtype, uint64_t>(lval);
	    if (this->use_plt_or_tls_offset_ && is_tls)
	      val += parameters->target().tls_offset_for_local(object, lsi,
							       got, got_indx,
							       this->addend_);
	  }
      }
      break;
    }

  elfcpp::Swap<got_size, big_endian>::writeval(pov, val);
}

// Output_data_got methods.

// Add an entry for a global symbol to the GOT.  This returns true if
// this is a new GOT entry, false if the symbol already had a GOT
// entry.

template<int got_size, bool big_endian>
bool
Output_data_got<got_size, big_endian>::add_global(Symbol* gsym,
						  unsigned int got_type,
						  uint64_t addend)
{
  if (gsym->has_got_offset(got_type, addend))
    return false;

  unsigned int got_offset = this->add_got_entry(Got_entry(gsym, false, addend));
  gsym->set_got_offset(got_type, got_offset, addend);
  return true;
}

// Like add_global, but use the PLT offset.

template<int got_size, bool big_endian>
bool
Output_data_got<got_size, big_endian>::add_global_plt(Symbol* gsym,
						      unsigned int got_type,
						      uint64_t addend)
{
  if (gsym->has_got_offset(got_type, addend))
    return false;

  unsigned int got_offset = this->add_got_entry(Got_entry(gsym, true, addend));
  gsym->set_got_offset(got_type, got_offset, addend);
  return true;
}

// Add an entry for a global symbol to the GOT, and add a dynamic
// relocation of type R_TYPE for the GOT entry.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::add_global_with_rel(
    Symbol* gsym,
    unsigned int got_type,
    Output_data_reloc_generic* rel_dyn,
    unsigned int r_type,
    uint64_t addend)
{
  if (gsym->has_got_offset(got_type, addend))
    return;

  unsigned int got_offset = this->add_got_entry(Got_entry());
  gsym->set_got_offset(got_type, got_offset, addend);
  rel_dyn->add_global_generic(gsym, r_type, this, got_offset, addend);
}

// Add a pair of entries for a global symbol to the GOT, and add
// dynamic relocations of type R_TYPE_1 and R_TYPE_2, respectively.
// If R_TYPE_2 == 0, add the second entry with no relocation.
template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::add_global_pair_with_rel(
    Symbol* gsym,
    unsigned int got_type,
    Output_data_reloc_generic* rel_dyn,
    unsigned int r_type_1,
    unsigned int r_type_2,
    uint64_t addend)
{
  if (gsym->has_got_offset(got_type, addend))
    return;

  unsigned int got_offset = this->add_got_entry_pair(Got_entry(), Got_entry());
  gsym->set_got_offset(got_type, got_offset, addend);
  rel_dyn->add_global_generic(gsym, r_type_1, this, got_offset, addend);

  if (r_type_2 != 0)
    rel_dyn->add_global_generic(gsym, r_type_2, this,
				got_offset + got_size / 8, addend);
}

// Add an entry for a local symbol plus ADDEND to the GOT.  This returns
// true if this is a new GOT entry, false if the symbol already has a GOT
// entry.

template<int got_size, bool big_endian>
bool
Output_data_got<got_size, big_endian>::add_local(
    Relobj* object,
    unsigned int symndx,
    unsigned int got_type,
    uint64_t addend)
{
  if (object->local_has_got_offset(symndx, got_type, addend))
    return false;

  unsigned int got_offset = this->add_got_entry(Got_entry(object, symndx,
							  false, addend));
  object->set_local_got_offset(symndx, got_type, got_offset, addend);
  return true;
}

// Like add_local, but use the PLT offset.

template<int got_size, bool big_endian>
bool
Output_data_got<got_size, big_endian>::add_local_plt(
    Relobj* object,
    unsigned int symndx,
    unsigned int got_type,
    uint64_t addend)
{
  if (object->local_has_got_offset(symndx, got_type, addend))
    return false;

  unsigned int got_offset = this->add_got_entry(Got_entry(object, symndx,
							  true, addend));
  object->set_local_got_offset(symndx, got_type, got_offset, addend);
  return true;
}

// Add an entry for a local symbol plus ADDEND to the GOT, and add a dynamic
// relocation of type R_TYPE for the GOT entry.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::add_local_with_rel(
    Relobj* object,
    unsigned int symndx,
    unsigned int got_type,
    Output_data_reloc_generic* rel_dyn,
    unsigned int r_type,
    uint64_t addend)
{
  if (object->local_has_got_offset(symndx, got_type, addend))
    return;

  unsigned int got_offset = this->add_got_entry(Got_entry());
  object->set_local_got_offset(symndx, got_type, got_offset, addend);
  rel_dyn->add_local_generic(object, symndx, r_type, this, got_offset,
                             addend);
}

// Add a pair of entries for a local symbol plus ADDEND to the GOT, and add
// a dynamic relocation of type R_TYPE using the section symbol of
// the output section to which input section SHNDX maps, on the first.
// The first got entry will have a value of zero, the second the
// value of the local symbol.
template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::add_local_pair_with_rel(
    Relobj* object,
    unsigned int symndx,
    unsigned int shndx,
    unsigned int got_type,
    Output_data_reloc_generic* rel_dyn,
    unsigned int r_type,
    uint64_t addend)
{
  if (object->local_has_got_offset(symndx, got_type, addend))
    return;

  unsigned int got_offset =
      this->add_got_entry_pair(Got_entry(),
			       Got_entry(object, symndx, false, addend));
  object->set_local_got_offset(symndx, got_type, got_offset, addend);
  Output_section* os = object->output_section(shndx);
  rel_dyn->add_output_section_generic(os, r_type, this, got_offset, addend);
}

// Add a pair of entries for a local symbol to the GOT, and add
// a dynamic relocation of type R_TYPE using STN_UNDEF on the first.
// The first got entry will have a value of zero, the second the
// value of the local symbol offset by Target::tls_offset_for_local.
template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::add_local_tls_pair(
    Relobj* object,
    unsigned int symndx,
    unsigned int got_type,
    Output_data_reloc_generic* rel_dyn,
    unsigned int r_type,
    uint64_t addend)
{
  if (object->local_has_got_offset(symndx, got_type, addend))
    return;

  unsigned int got_offset
    = this->add_got_entry_pair(Got_entry(),
			       Got_entry(object, symndx, true, addend));
  object->set_local_got_offset(symndx, got_type, got_offset, addend);
  rel_dyn->add_local_generic(object, 0, r_type, this, got_offset, addend);
}

// Reserve a slot in the GOT for a local symbol or the second slot of a pair.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::reserve_local(
    unsigned int i,
    Relobj* object,
    unsigned int sym_index,
    unsigned int got_type,
    uint64_t addend)
{
  this->do_reserve_slot(i);
  object->set_local_got_offset(sym_index, got_type, this->got_offset(i), addend);
}

// Reserve a slot in the GOT for a global symbol.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::reserve_global(
    unsigned int i,
    Symbol* gsym,
    unsigned int got_type,
    uint64_t addend)
{
  this->do_reserve_slot(i);
  gsym->set_got_offset(got_type, this->got_offset(i), addend);
}

// Write out the GOT.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::do_write(Output_file* of)
{
  const int add = got_size / 8;

  const off_t off = this->offset();
  const off_t oview_size = this->data_size();
  unsigned char* const oview = of->get_output_view(off, oview_size);

  unsigned char* pov = oview;
  for (unsigned int i = 0; i < this->entries_.size(); ++i)
    {
      this->entries_[i].write(this, i, pov);
      pov += add;
    }

  gold_assert(pov - oview == oview_size);

  of->write_output_view(off, oview_size, oview);

  // We no longer need the GOT entries.
  this->entries_.clear();
}

// Create a new GOT entry and return its offset.

template<int got_size, bool big_endian>
unsigned int
Output_data_got<got_size, big_endian>::add_got_entry(Got_entry got_entry)
{
  if (!this->is_data_size_valid())
    {
      this->entries_.push_back(got_entry);
      this->set_got_size();
      return this->last_got_offset();
    }
  else
    {
      // For an incremental update, find an available slot.
      off_t got_offset = this->free_list_.allocate(got_size / 8,
						   got_size / 8, 0);
      if (got_offset == -1)
	gold_fallback(_("out of patch space (GOT);"
			" relink with --incremental-full"));
      unsigned int got_index = got_offset / (got_size / 8);
      gold_assert(got_index < this->entries_.size());
      this->entries_[got_index] = got_entry;
      return static_cast<unsigned int>(got_offset);
    }
}

// Create a pair of new GOT entries and return the offset of the first.

template<int got_size, bool big_endian>
unsigned int
Output_data_got<got_size, big_endian>::add_got_entry_pair(
    Got_entry got_entry_1,
    Got_entry got_entry_2)
{
  if (!this->is_data_size_valid())
    {
      unsigned int got_offset;
      this->entries_.push_back(got_entry_1);
      got_offset = this->last_got_offset();
      this->entries_.push_back(got_entry_2);
      this->set_got_size();
      return got_offset;
    }
  else
    {
      // For an incremental update, find an available pair of slots.
      off_t got_offset = this->free_list_.allocate(2 * got_size / 8,
						   got_size / 8, 0);
      if (got_offset == -1)
	gold_fallback(_("out of patch space (GOT);"
			" relink with --incremental-full"));
      unsigned int got_index = got_offset / (got_size / 8);
      gold_assert(got_index < this->entries_.size());
      this->entries_[got_index] = got_entry_1;
      this->entries_[got_index + 1] = got_entry_2;
      return static_cast<unsigned int>(got_offset);
    }
}

// Replace GOT entry I with a new value.

template<int got_size, bool big_endian>
void
Output_data_got<got_size, big_endian>::replace_got_entry(
    unsigned int i,
    Got_entry got_entry)
{
  gold_assert(i < this->entries_.size());
  this->entries_[i] = got_entry;
}

// Output_data_dynamic::Dynamic_entry methods.

// Write out the entry.

template<int size, bool big_endian>
void
Output_data_dynamic::Dynamic_entry::write(
    unsigned char* pov,
    const Stringpool* pool) const
{
  typename elfcpp::Elf_types<size>::Elf_WXword val;
  switch (this->offset_)
    {
    case DYNAMIC_NUMBER:
      val = this->u_.val;
      break;

    case DYNAMIC_SECTION_SIZE:
      val = this->u_.od->data_size();
      if (this->od2 != NULL)
	val += this->od2->data_size();
      break;

    case DYNAMIC_SYMBOL:
      {
	const Sized_symbol<size>* s =
	  static_cast<const Sized_symbol<size>*>(this->u_.sym);
	val = s->value();
      }
      break;

    case DYNAMIC_STRING:
      val = pool->get_offset(this->u_.str);
      break;

    case DYNAMIC_CUSTOM:
      val = parameters->target().dynamic_tag_custom_value(this->tag_);
      break;

    default:
      val = this->u_.od->address() + this->offset_;
      break;
    }

  elfcpp::Dyn_write<size, big_endian> dw(pov);
  dw.put_d_tag(this->tag_);
  dw.put_d_val(val);
}

// Output_data_dynamic methods.

// Adjust the output section to set the entry size.

void
Output_data_dynamic::do_adjust_output_section(Output_section* os)
{
  if (parameters->target().get_size() == 32)
    os->set_entsize(elfcpp::Elf_sizes<32>::dyn_size);
  else if (parameters->target().get_size() == 64)
    os->set_entsize(elfcpp::Elf_sizes<64>::dyn_size);
  else
    gold_unreachable();
}

// Get a dynamic entry offset.

unsigned int
Output_data_dynamic::get_entry_offset(elfcpp::DT tag) const
{
  int dyn_size;

  if (parameters->target().get_size() == 32)
    dyn_size = elfcpp::Elf_sizes<32>::dyn_size;
  else if (parameters->target().get_size() == 64)
    dyn_size = elfcpp::Elf_sizes<64>::dyn_size;
  else
    gold_unreachable();

  for (size_t i = 0; i < entries_.size(); ++i)
    if (entries_[i].tag() == tag)
      return i * dyn_size;

  return -1U;
}

// Set the final data size.

void
Output_data_dynamic::set_final_data_size()
{
  // Add the terminating entry if it hasn't been added.
  // Because of relaxation, we can run this multiple times.
  if (this->entries_.empty() || this->entries_.back().tag() != elfcpp::DT_NULL)
    {
      int extra = parameters->options().spare_dynamic_tags();
      for (int i = 0; i < extra; ++i)
	this->add_constant(elfcpp::DT_NULL, 0);
      this->add_constant(elfcpp::DT_NULL, 0);
    }

  int dyn_size;
  if (parameters->target().get_size() == 32)
    dyn_size = elfcpp::Elf_sizes<32>::dyn_size;
  else if (parameters->target().get_size() == 64)
    dyn_size = elfcpp::Elf_sizes<64>::dyn_size;
  else
    gold_unreachable();
  this->set_data_size(this->entries_.size() * dyn_size);
}

// Write out the dynamic entries.

void
Output_data_dynamic::do_write(Output_file* of)
{
  switch (parameters->size_and_endianness())
    {
#ifdef HAVE_TARGET_32_LITTLE
    case Parameters::TARGET_32_LITTLE:
      this->sized_write<32, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_32_BIG
    case Parameters::TARGET_32_BIG:
      this->sized_write<32, true>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_LITTLE
    case Parameters::TARGET_64_LITTLE:
      this->sized_write<64, false>(of);
      break;
#endif
#ifdef HAVE_TARGET_64_BIG
    case Parameters::TARGET_64_BIG:
      this->sized_write<64, true>(of);
      break;
#endif
    default:
      gold_unreachable();
    }
}

template<int size, bool big_endian>
void
Output_data_dynamic::sized_write(Output_file* of)
{
  const int dyn_size = elfcpp::Elf_sizes<size>::dyn_size;

  const off_t offset = this->offset();
  const off_t oview_size = this->data_size();
  unsigned char* const oview = of->get_output_view(offset, oview_size);

  unsigned char* pov = oview;
  for (typename Dynamic_entries::const_iterator p = this->entries_.begin();
       p != this->entries_.end();
       ++p)
    {
      p->write<size, big_endian>(pov, this->pool_);
      pov += dyn_size;
    }

  gold_assert(pov - oview == oview_size);

  of->write_output_view(offset, oview_size, oview);

  // We no longer need the dynamic entries.
  this->entries_.clear();
}

// Class Output_symtab_xindex.

void
Output_symtab_xindex::do_write(Output_file* of)
{
  const off_t offset = this->offset();
  const off_t oview_size = this->data_size();
  unsigned char* const oview = of->get_output_view(offset, oview_size);

  memset(oview, 0, oview_size);

  if (parameters->target().is_big_endian())
    this->endian_do_write<true>(oview);
  else
    this->endian_do_write<false>(oview);

  of->write_output_view(offset, oview_size, oview);

  // We no longer need the data.
  this->entries_.clear();
}

template<bool big_endian>
void
Output_symtab_xindex::endian_do_write(unsigned char* const oview)
{
  for (Xindex_entries::const_iterator p = this->entries_.begin();
       p != this->entries_.end();
       ++p)
    {
      unsigned int symndx = p->first;
      gold_assert(static_cast<off_t>(symndx) * 4 < this->data_size());
      elfcpp::Swap<32, big_endian>::writeval(oview + symndx * 4, p->second);
    }
}

// Output_fill_debug_info methods.

// Return the minimum size needed for a dummy compilation unit header.

size_t
Output_fill_debug_info::do_minimum_hole_size() const
{
  // Compile unit header fields: unit_length, version, debug_abbrev_offset,
  // address_size.
  const size_t len = 4 + 2 + 4 + 1;
  // For type units, add type_signature, type_offset.
  if (this->is_debug_types_)
    return len + 8 + 4;
  return len;
}

// Write a dummy compilation unit header to fill a hole in the
// .debug_info or .debug_types section.

void
Output_fill_debug_info::do_write(Output_file* of, off_t off, size_t len) const
{
  gold_debug(DEBUG_INCREMENTAL, "fill_debug_info(%08lx, %08lx)",
	     static_cast<long>(off), static_cast<long>(len));

  gold_assert(len >= this->do_minimum_hole_size());

  unsigned char* const oview = of->get_output_view(off, len);
  unsigned char* pov = oview;

  // Write header fields: unit_length, version, debug_abbrev_offset,
  // address_size.
  if (this->is_big_endian())
    {
      elfcpp::Swap_unaligned<32, true>::writeval(pov, len - 4);
      elfcpp::Swap_unaligned<16, true>::writeval(pov + 4, this->version);
      elfcpp::Swap_unaligned<32, true>::writeval(pov + 6, 0);
    }
  else
    {
      elfcpp::Swap_unaligned<32, false>::writeval(pov, len - 4);
      elfcpp::Swap_unaligned<16, false>::writeval(pov + 4, this->version);
      elfcpp::Swap_unaligned<32, false>::writeval(pov + 6, 0);
    }
  pov += 4 + 2 + 4;
  *pov++ = 4;

  // For type units, the additional header fields -- type_signature,
  // type_offset -- can be filled with zeroes.

  // Fill the remainder of the free space with zeroes.  The first
  // zero should tell the consumer there are no DIEs to read in this
  // compilation unit.
  if (pov < oview + len)
    memset(pov, 0, oview + len - pov);

  of->write_output_view(off, len, oview);
}

// Output_fill_debug_line methods.

// Return the minimum size needed for a dummy line number program header.

size_t
Output_fill_debug_line::do_minimum_hole_size() const
{
  // Line number program header fields: unit_length, version, header_length,
  // minimum_instruction_length, default_is_stmt, line_base, line_range,
  // opcode_base, standard_opcode_lengths[], include_directories, filenames.
  const size_t len = 4 + 2 + 4 + this->header_length;
  return len;
}

// Write a dummy line number program header to fill a hole in the
// .debug_line section.

void
Output_fill_debug_line::do_write(Output_file* of, off_t off, size_t len) const
{
  gold_debug(DEBUG_INCREMENTAL, "fill_debug_line(%08lx, %08lx)",
	     static_cast<long>(off), static_cast<long>(len));

  gold_assert(len >= this->do_minimum_hole_size());

  unsigned char* const oview = of->get_output_view(off, len);
  unsigned char* pov = oview;

  // Write header fields: unit_length, version, header_length,
  // minimum_instruction_length, default_is_stmt, line_base, line_range,
  // opcode_base, standard_opcode_lengths[], include_directories, filenames.
  // We set the header_length field to cover the entire hole, so the
  // line number program is empty.
  if (this->is_big_endian())
    {
      elfcpp::Swap_unaligned<32, true>::writeval(pov, len - 4);
      elfcpp::Swap_unaligned<16, true>::writeval(pov + 4, this->version);
      elfcpp::Swap_unaligned<32, true>::writeval(pov + 6, len - (4 + 2 + 4));
    }
  else
    {
      elfcpp::Swap_unaligned<32, false>::writeval(pov, len - 4);
      elfcpp::Swap_unaligned<16, false>::writeval(pov + 4, this->version);
      elfcpp::Swap_unaligned<32, false>::writeval(pov + 6, len - (4 + 2 + 4));
    }
  pov += 4 + 2 + 4;
  *pov++ = 1;	// minimum_instruction_length
  *pov++ = 0;	// default_is_stmt
  *pov++ = 0;	// line_base
  *pov++ = 5;	// line_range
  *pov++ = 13;	// opcode_base
  *pov++ = 0;	// standard_opcode_lengths[1]
  *pov++ = 1;	// standard_opcode_lengths[2]
  *pov++ = 1;	// standard_opcode_lengths[3]
  *pov++ = 1;	// standard_opcode_lengths[4]
  *pov++ = 1;	// standard_opcode_lengths[5]
  *pov++ = 0;	// standard_opcode_lengths[6]
  *pov++ = 0;	// standard_opcode_lengths[7]
  *pov++ = 0;	// standard_opcode_lengths[8]
  *pov++ = 1;	// standard_opcode_lengths[9]
  *pov++ = 0;	// standard_opcode_lengths[10]
  *pov++ = 0;	// standard_opcode_lengths[11]
  *pov++ = 1;	// standard_opcode_lengths[12]
  *pov++ = 0;	// include_directories (empty)
  *pov++ = 0;	// filenames (empty)

  // Some consumers don't check the header_length field, and simply
  // start reading the line number program immediately following the
  // header.  For those consumers, we fill the remainder of the free
  // space with DW_LNS_set_basic_block opcodes.  These are effectively
  // no-ops: the resulting line table program will not create any rows.
  if (pov < oview + len)
    memset(pov, elfcpp::DW_LNS_set_basic_block, oview + len - pov);

  of->write_output_view(off, len, oview);
}

// Output_section::Input_section methods.

// Return the current data size.  For an input section we store the size here.
// For an Output_section_data, we have to ask it for the size.

off_t
Output_section::Input_section::current_data_size() const
{
  if (this->is_input_section())
    return this->u1_.data_size;
  else
    {
      this->u2_.posd->pre_finalize_data_size();
      return this->u2_.posd->current_data_size();
    }
}

// Return the data size.  For an input section we store the size here.
// For an Output_section_data, we have to ask it for the size.

off_t
Output_section::Input_section::data_size() const
{
  if (this->is_input_section())
    return this->u1_.data_size;
  else
    return this->u2_.posd->data_size();
}

// Return the object for an input section.

Relobj*
Output_section::Input_section::relobj() const
{
  if (this->is_input_section())
    return this->u2_.object;
  else if (this->is_merge_section())
    {
      gold_assert(this->u2_.pomb->first_relobj() != NULL);
      return this->u2_.pomb->first_relobj();
    }
  else if (this->is_relaxed_input_section())
    return this->u2_.poris->relobj();
  else
    gold_unreachable();
}

// Return the input section index for an input section.

unsigned int
Output_section::Input_section::shndx() const
{
  if (this->is_input_section())
    return this->shndx_;
  else if (this->is_merge_section())
    {
      gold_assert(this->u2_.pomb->first_relobj() != NULL);
      return this->u2_.pomb->first_shndx();
    }
  else if (this->is_relaxed_input_section())
    return this->u2_.poris->shndx();
  else
    gold_unreachable();
}

// Set the address and file offset.

void
Output_section::Input_section::set_address_and_file_offset(
    uint64_t address,
    off_t file_offset,
    off_t section_file_offset)
{
  if (this->is_input_section())
    this->u2_.object->set_section_offset(this->shndx_,
					 file_offset - section_file_offset);
  else
    this->u2_.posd->set_address_and_file_offset(address, file_offset);
}

// Reset the address and file offset.

void
Output_section::Input_section::reset_address_and_file_offset()
{
  if (!this->is_input_section())
    this->u2_.posd->reset_address_and_file_offset();
}

// Finalize the data size.

void
Output_section::Input_section::finalize_data_size()
{
  if (!this->is_input_section())
    this->u2_.posd->finalize_data_size();
}

// Try to turn an input offset into an output offset.  We want to
// return the output offset relative to the start of this
// Input_section in the output section.

inline bool
Output_section::Input_section::output_offset(
    const Relobj* object,
    unsigned int shndx,
    section_offset_type offset,
    section_offset_type* poutput) const
{
  if (!this->is_input_section())
    return this->u2_.posd->output_offset(object, shndx, offset, poutput);
  else
    {
      if (this->shndx_ != shndx || this->u2_.object != object)
	return false;
      *poutput = offset;
      return true;
    }
}

// Write out the data.  We don't have to do anything for an input
// section--they are handled via Object::relocate--but this is where
// we write out the data for an Output_section_data.

void
Output_section::Input_section::write(Output_file* of)
{
  if (!this->is_input_section())
    this->u2_.posd->write(of);
}

// Write the data to a buffer.  As for write(), we don't have to do
// anything for an input section.

void
Output_section::Input_section::write_to_buffer(unsigned char* buffer)
{
  if (!this->is_input_section())
    this->u2_.posd->write_to_buffer(buffer);
}

// Print to a map file.

void
Output_section::Input_section::print_to_mapfile(Mapfile* mapfile) const
{
  switch (this->shndx_)
    {
    case OUTPUT_SECTION_CODE:
    case MERGE_DATA_SECTION_CODE:
    case MERGE_STRING_SECTION_CODE:
      this->u2_.posd->print_to_mapfile(mapfile);
      break;

    case RELAXED_INPUT_SECTION_CODE:
      {
	Output_relaxed_input_section* relaxed_section =
	  this->relaxed_input_section();
	mapfile->print_input_section(relaxed_section->relobj(),
				     relaxed_section->shndx());
      }
      break;
    default:
      mapfile->print_input_section(this->u2_.object, this->shndx_);
      break;
    }
}

// Output_section methods.

// Construct an Output_section.  NAME will point into a Stringpool.

Output_section::Output_section(const char* name, elfcpp::Elf_Word type,
			       elfcpp::Elf_Xword flags)
  : name_(name),
    addralign_(0),
    entsize_(0),
    load_address_(0),
    link_section_(NULL),
    link_(0),
    info_section_(NULL),
    info_symndx_(NULL),
    info_(0),
    type_(type),
    flags_(flags),
    order_(ORDER_INVALID),
    out_shndx_(-1U),
    symtab_index_(0),
    dynsym_index_(0),
    input_sections_(),
    first_input_offset_(0),
    fills_(),
    postprocessing_buffer_(NULL),
    needs_symtab_index_(false),
    needs_dynsym_index_(false),
    should_link_to_symtab_(false),
    should_link_to_dynsym_(false),
    after_input_sections_(false),
    requires_postprocessing_(false),
    found_in_sections_clause_(false),
    has_load_address_(false),
    info_uses_section_index_(false),
    input_section_order_specified_(false),
    may_sort_attached_input_sections_(false),
    must_sort_attached_input_sections_(false),
    attached_input_sections_are_sorted_(false),
    is_relro_(false),
    is_small_section_(false),
    is_large_section_(false),
    generate_code_fills_at_write_(false),
    is_entsize_zero_(false),
    section_offsets_need_adjustment_(false),
    is_noload_(false),
    always_keeps_input_sections_(false),
    has_fixed_layout_(false),
    is_patch_space_allowed_(false),
    is_unique_segment_(false),
    tls_offset_(0),
    extra_segment_flags_(0),
    segment_alignment_(0),
    checkpoint_(NULL),
    lookup_maps_(new Output_section_lookup_maps),
    free_list_(),
    free_space_fill_(NULL),
    patch_space_(0),
    reloc_section_(NULL)
{
  // An unallocated section has no address.  Forcing this means that
  // we don't need special treatment for symbols defined in debug
  // sections.
  if ((flags & elfcpp::SHF_ALLOC) == 0)
    this->set_address(0);
}

Output_section::~Output_section()
{
  delete this->checkpoint_;
}

// Set the entry size.

void
Output_section::set_entsize(uint64_t v)
{
  if (this->is_entsize_zero_)
    ;
  else if (this->entsize_ == 0)
    this->entsize_ = v;
  else if (this->entsize_ != v)
    {
      this->entsize_ = 0;
      this->is_entsize_zero_ = 1;
    }
}

// Add the input section SHNDX, with header SHDR, named SECNAME, in
// OBJECT, to the Output_section.  RELOC_SHNDX is the index of a
// relocation section which applies to this section, or 0 if none, or
// -1U if more than one.  Return the offset of the input section
// within the output section.  Return -1 if the input section will
// receive special handling.  In the normal case we don't always keep
// track of input sections for an Output_section.  Instead, each
// Object keeps track of the Output_section for each of its input
// sections.  However, if HAVE_SECTIONS_SCRIPT is true, we do keep
// track of input sections here; this is used when SECTIONS appears in
// a linker script.

template<int size, bool big_endian>
off_t
Output_section::add_input_section(Layout* layout,
				  Sized_relobj_file<size, big_endian>* object,
				  unsigned int shndx,
				  const char* secname,
				  const elfcpp::Shdr<size, big_endian>& shdr,
				  unsigned int reloc_shndx,
				  bool have_sections_script)
{
  section_size_type input_section_size = shdr.get_sh_size();
  section_size_type uncompressed_size;
  elfcpp::Elf_Xword addralign = shdr.get_sh_addralign();
  if (object->section_is_compressed(shndx, &uncompressed_size,
				    &addralign))
    input_section_size = uncompressed_size;

  if ((addralign & (addralign - 1)) != 0)
    {
      object->error(_("invalid alignment %lu for section \"%s\""),
		    static_cast<unsigned long>(addralign), secname);
      addralign = 1;
    }

  if (addralign > this->addralign_)
    this->addralign_ = addralign;

  typename elfcpp::Elf_types<size>::Elf_WXword sh_flags = shdr.get_sh_flags();
  uint64_t entsize = shdr.get_sh_entsize();

  // .debug_str is a mergeable string section, but is not always so
  // marked by compilers.  Mark manually here so we can optimize.
  if (strcmp(secname, ".debug_str") == 0)
    {
      sh_flags |= (elfcpp::SHF_MERGE | elfcpp::SHF_STRINGS);
      entsize = 1;
    }

  this->update_flags_for_input_section(sh_flags);
  this->set_entsize(entsize);

  // If this is a SHF_MERGE section, we pass all the input sections to
  // a Output_data_merge.  We don't try to handle relocations for such
  // a section.  We don't try to handle empty merge sections--they
  // mess up the mappings, and are useless anyhow.
  // FIXME: Need to handle merge sections during incremental update.
  if ((sh_flags & elfcpp::SHF_MERGE) != 0
      && reloc_shndx == 0
      && shdr.get_sh_size() > 0
      && !parameters->incremental())
    {
      // Keep information about merged input sections for rebuilding fast
      // lookup maps if we have sections-script or we do relaxation.
      bool keeps_input_sections = (this->always_keeps_input_sections_
				   || have_sections_script
				   || parameters->target().may_relax());

      if (this->add_merge_input_section(object, shndx, sh_flags, entsize,
					addralign, keeps_input_sections))
	{
	  // Tell the relocation routines that they need to call the
	  // output_offset method to determine the final address.
	  return -1;
	}
    }

  off_t offset_in_section;

  if (this->has_fixed_layout())
    {
      // For incremental updates, find a chunk of unused space in the section.
      offset_in_section = this->free_list_.allocate(input_section_size,
						    addralign, 0);
      if (offset_in_section == -1)
	gold_fallback(_("out of patch space in section %s; "
			"relink with --incremental-full"),
		      this->name());
      return offset_in_section;
    }

  offset_in_section = this->current_data_size_for_child();
  off_t aligned_offset_in_section = align_address(offset_in_section,
						  addralign);
  this->set_current_data_size_for_child(aligned_offset_in_section
					+ input_section_size);

  // Determine if we want to delay code-fill generation until the output
  // section is written.  When the target is relaxing, we want to delay fill
  // generating to avoid adjusting them during relaxation.  Also, if we are
  // sorting input sections we must delay fill generation.
  if (!this->generate_code_fills_at_write_
      && !have_sections_script
      && (sh_flags & elfcpp::SHF_EXECINSTR) != 0
      && parameters->target().has_code_fill()
      && (parameters->target().may_relax()
	  || layout->is_section_ordering_specified()))
    {
      gold_assert(this->fills_.empty());
      this->generate_code_fills_at_write_ = true;
    }

  if (aligned_offset_in_section > offset_in_section
      && !this->generate_code_fills_at_write_
      && !have_sections_script
      && (sh_flags & elfcpp::SHF_EXECINSTR) != 0
      && parameters->target().has_code_fill())
    {
      // We need to add some fill data.  Using fill_list_ when
      // possible is an optimization, since we will often have fill
      // sections without input sections.
      off_t fill_len = aligned_offset_in_section - offset_in_section;
      if (this->input_sections_.empty())
	this->fills_.push_back(Fill(offset_in_section, fill_len));
      else
	{
	  std::string fill_data(parameters->target().code_fill(fill_len));
	  Output_data_const* odc = new Output_data_const(fill_data, 1);
	  this->input_sections_.push_back(Input_section(odc));
	}
    }

  // We need to keep track of this section if we are already keeping
  // track of sections, or if we are relaxing.  Also, if this is a
  // section which requires sorting, or which may require sorting in
  // the future, we keep track of the sections.  If the
  // --section-ordering-file option is used to specify the order of
  // sections, we need to keep track of sections.
  if (this->always_keeps_input_sections_
      || have_sections_script
      || !this->input_sections_.empty()
      || this->may_sort_attached_input_sections()
      || this->must_sort_attached_input_sections()
      || parameters->options().user_set_Map()
      || parameters->target().may_relax()
      || layout->is_section_ordering_specified())
    {
      Input_section isecn(object, shndx, input_section_size, addralign);
      /* If section ordering is requested by specifying a ordering file,
	 using --section-ordering-file, match the section name with
	 a pattern.  */
      if (parameters->options().section_ordering_file())
	{
	  unsigned int section_order_index =
	    layout->find_section_order_index(std::string(secname));
	  if (section_order_index != 0)
	    {
	      isecn.set_section_order_index(section_order_index);
	      this->set_input_section_order_specified();
	    }
	}
      this->input_sections_.push_back(isecn);
    }

  return aligned_offset_in_section;
}

// Add arbitrary data to an output section.

void
Output_section::add_output_section_data(Output_section_data* posd)
{
  Input_section inp(posd);
  this->add_output_section_data(&inp);

  if (posd->is_data_size_valid())
    {
      off_t offset_in_section;
      if (this->has_fixed_layout())
	{
	  // For incremental updates, find a chunk of unused space.
	  offset_in_section = this->free_list_.allocate(posd->data_size(),
							posd->addralign(), 0);
	  if (offset_in_section == -1)
	    gold_fallback(_("out of patch space in section %s; "
			    "relink with --incremental-full"),
			  this->name());
	  // Finalize the address and offset now.
	  uint64_t addr = this->address();
	  off_t offset = this->offset();
	  posd->set_address_and_file_offset(addr + offset_in_section,
					    offset + offset_in_section);
	}
      else
	{
	  offset_in_section = this->current_data_size_for_child();
	  off_t aligned_offset_in_section = align_address(offset_in_section,
							  posd->addralign());
	  this->set_current_data_size_for_child(aligned_offset_in_section
						+ posd->data_size());
	}
    }
  else if (this->has_fixed_layout())
    {
      // For incremental updates, arrange for the data to have a fixed layout.
      // This will mean that additions to the data must be allocated from
      // free space within the containing output section.
      uint64_t addr = this->address();
      posd->set_address(addr);
      posd->set_file_offset(0);
      // FIXME: This should eventually be unreachable.
      // gold_unreachable();
    }
}

// Add a relaxed input section.

void
Output_section::add_relaxed_input_section(Layout* layout,
					  Output_relaxed_input_section* poris,
					  const std::string& name)
{
  Input_section inp(poris);

  // If the --section-ordering-file option is used to specify the order of
  // sections, we need to keep track of sections.
  if (layout->is_section_ordering_specified())
    {
      unsigned int section_order_index =
	layout->find_section_order_index(name);
      if (section_order_index != 0)
	{
	  inp.set_section_order_index(section_order_index);
	  this->set_input_section_order_specified();
	}
    }

  this->add_output_section_data(&inp);
  if (this->lookup_maps_->is_valid())
    this->lookup_maps_->add_relaxed_input_section(poris->relobj(),
						  poris->shndx(), poris);

  // For a relaxed section, we use the current data size.  Linker scripts
  // get all the input sections, including relaxed one from an output
  // section and add them back to the same output section to compute the
  // output section size.  If we do not account for sizes of relaxed input
  // sections, an output section would be incorrectly sized.
  off_t offset_in_section = this->current_data_size_for_child();
  off_t aligned_offset_in_section = align_address(offset_in_section,
						  poris->addralign());
  this->set_current_data_size_for_child(aligned_offset_in_section
					+ poris->current_data_size());
}

// Add arbitrary data to an output section by Input_section.

void
Output_section::add_output_section_data(Input_section* inp)
{
  if (this->input_sections_.empty())
    this->first_input_offset_ = this->current_data_size_for_child();

  this->input_sections_.push_back(*inp);

  uint64_t addralign = inp->addralign();
  if (addralign > this->addralign_)
    this->addralign_ = addralign;

  inp->set_output_section(this);
}

// Add a merge section to an output section.

void
Output_section::add_output_merge_section(Output_section_data* posd,
					 bool is_string, uint64_t entsize)
{
  Input_section inp(posd, is_string, entsize);
  this->add_output_section_data(&inp);
}

// Add an input section to a SHF_MERGE section.

bool
Output_section::add_merge_input_section(Relobj* object, unsigned int shndx,
					uint64_t flags, uint64_t entsize,
					uint64_t addralign,
					bool keeps_input_sections)
{
  // We cannot merge sections with entsize == 0.
  if (entsize == 0)
    return false;

  bool is_string = (flags & elfcpp::SHF_STRINGS) != 0;

  // We cannot restore merged input section states.
  gold_assert(this->checkpoint_ == NULL);

  // Look up merge sections by required properties.
  // Currently, we only invalidate the lookup maps in script processing
  // and relaxation.  We should not have done either when we reach here.
  // So we assume that the lookup maps are valid to simply code.
  gold_assert(this->lookup_maps_->is_valid());
  Merge_section_properties msp(is_string, entsize, addralign);
  Output_merge_base* pomb = this->lookup_maps_->find_merge_section(msp);
  bool is_new = false;
  if (pomb != NULL)
    {
      gold_assert(pomb->is_string() == is_string
		  && pomb->entsize() == entsize
		  && pomb->addralign() == addralign);
    }
  else
    {
      // Create a new Output_merge_data or Output_merge_string_data.
      if (!is_string)
	pomb = new Output_merge_data(entsize, addralign);
      else
	{
	  switch (entsize)
	    {
	    case 1:
	      pomb = new Output_merge_string<char>(addralign);
	      break;
	    case 2:
	      pomb = new Output_merge_string<char16_t>(addralign);
	      break;
	    case 4:
	      pomb = new Output_merge_string<char32_t>(addralign);
	      break;
	    default:
	      return false;
	    }
	}
      // If we need to do script processing or relaxation, we need to keep
      // the original input sections to rebuild the fast lookup maps.
      if (keeps_input_sections)
	pomb->set_keeps_input_sections();
      is_new = true;
    }

  if (pomb->add_input_section(object, shndx))
    {
      // Add new merge section to this output section and link merge
      // section properties to new merge section in map.
      if (is_new)
	{
	  this->add_output_merge_section(pomb, is_string, entsize);
	  this->lookup_maps_->add_merge_section(msp, pomb);
	}

      return true;
    }
  else
    {
      // If add_input_section failed, delete new merge section to avoid
      // exporting empty merge sections in Output_section::get_input_section.
      if (is_new)
	delete pomb;
      return false;
    }
}

// Build a relaxation map to speed up relaxation of existing input sections.
// Look up to the first LIMIT elements in INPUT_SECTIONS.

void
Output_section::build_relaxation_map(
  const Input_section_list& input_sections,
  size_t limit,
  Relaxation_map* relaxation_map) const
{
  for (size_t i = 0; i < limit; ++i)
    {
      const Input_section& is(input_sections[i]);
      if (is.is_input_section() || is.is_relaxed_input_section())
	{
	  Section_id sid(is.relobj(), is.shndx());
	  (*relaxation_map)[sid] = i;
	}
    }
}

// Convert regular input sections in INPUT_SECTIONS into relaxed input
// sections in RELAXED_SECTIONS.  MAP is a prebuilt map from section id
// indices of INPUT_SECTIONS.

void
Output_section::convert_input_sections_in_list_to_relaxed_sections(
  const std::vector<Output_relaxed_input_section*>& relaxed_sections,
  const Relaxation_map& map,
  Input_section_list* input_sections)
{
  for (size_t i = 0; i < relaxed_sections.size(); ++i)
    {
      Output_relaxed_input_section* poris = relaxed_sections[i];
      Section_id sid(poris->relobj(), poris->shndx());
      Relaxation_map::const_iterator p = map.find(sid);
      gold_assert(p != map.end());
      gold_assert((*input_sections)[p->second].is_input_section());

      // Remember section order index of original input section
      // if it is set.  Copy it to the relaxed input section.
      unsigned int soi =
	(*input_sections)[p->second].section_order_index();
      (*input_sections)[p->second] = Input_section(poris);
      (*input_sections)[p->second].set_section_order_index(soi);
    }
}

// Convert regular input sections into relaxed input sections. RELAXED_SECTIONS
// is a vector of pointers to Output_relaxed_input_section or its derived
// classes.  The relaxed sections must correspond to existing input sections.

void
Output_section::convert_input_sections_to_relaxed_sections(
  const std::vector<Output_relaxed_input_section*>& relaxed_sections)
{
  gold_assert(parameters->target().may_relax());

  // We want to make sure that restore_states does not undo the effect of
  // this.  If there is no checkpoint active, just search the current
  // input section list and replace the sections there.  If there is
  // a checkpoint, also replace the sections there.

  // By default, we look at the whole list.
  size_t limit = this->input_sections_.size();

  if (this->checkpoint_ != NULL)
    {
      // Replace input sections with relaxed input section in the saved
      // copy of the input section list.
      if (this->checkpoint_->input_sections_saved())
	{
	  Relaxation_map map;
	  this->build_relaxation_map(
		    *(this->checkpoint_->input_sections()),
		    this->checkpoint_->input_sections()->size(),
		    &map);
	  this->convert_input_sections_in_list_to_relaxed_sections(
		    relaxed_sections,
		    map,
		    this->checkpoint_->input_sections());
	}
      else
	{
	  // We have not copied the input section list yet.  Instead, just
	  // look at the portion that would be saved.
	  limit = this->checkpoint_->input_sections_size();
	}
    }

  // Convert input sections in input_section_list.
  Relaxation_map map;
  this->build_relaxation_map(this->input_sections_, limit, &map);
  this->convert_input_sections_in_list_to_relaxed_sections(
	    relaxed_sections,
	    map,
	    &this->input_sections_);

  // Update fast look-up map.
  if (this->lookup_maps_->is_valid())
    for (size_t i = 0; i < relaxed_sections.size(); ++i)
      {
	Output_relaxed_input_section* poris = relaxed_sections[i];
	this->lookup_maps_->add_relaxed_input_section(poris->relobj(),
						      poris->shndx(), poris);
      }
}

// Update the output section flags based on input section flags.

void
Output_section::update_flags_for_input_section(elfcpp::Elf_Xword flags)
{
  // If we created the section with SHF_ALLOC clear, we set the
  // address.  If we are now setting the SHF_ALLOC flag, we need to
  // undo that.
  if ((this->flags_ & elfcpp::SHF_ALLOC) == 0
      && (flags & elfcpp::SHF_ALLOC) != 0)
    this->mark_address_invalid();

  this->flags_ |= (flags
		   & (elfcpp::SHF_WRITE
		      | elfcpp::SHF_ALLOC
		      | elfcpp::SHF_EXECINSTR));

  if ((flags & elfcpp::SHF_MERGE) == 0)
    this->flags_ &=~ elfcpp::SHF_MERGE;
  else
    {
      if (this->current_data_size_for_child() == 0)
	this->flags_ |= elfcpp::SHF_MERGE;
    }

  if ((flags & elfcpp::SHF_STRINGS) == 0)
    this->flags_ &=~ elfcpp::SHF_STRINGS;
  else
    {
      if (this->current_data_size_for_child() == 0)
	this->flags_ |= elfcpp::SHF_STRINGS;
    }
}

// Find the merge section into which an input section with index SHNDX in
// OBJECT has been added.  Return NULL if none found.

const Output_section_data*
Output_section::find_merge_section(const Relobj* object,
				   unsigned int shndx) const
{
  return object->find_merge_section(shndx);
}

// Build the lookup maps for relaxed sections.  This needs
// to be declared as a const method so that it is callable with a const
// Output_section pointer.  The method only updates states of the maps.

void
Output_section::build_lookup_maps() const
{
  this->lookup_maps_->clear();
  for (Input_section_list::const_iterator p = this->input_sections_.begin();
       p != this->input_sections_.end();
       ++p)
    {
      if (p->is_relaxed_input_section())
	{
	  Output_relaxed_input_section* poris = p->relaxed_input_section();
	  this->lookup_maps_->add_relaxed_input_section(poris->relobj(),
							poris->shndx(), poris);
	}
    }
}

// Find an relaxed input section corresponding to an input section
// in OBJECT with index SHNDX.

const Output_relaxed_input_section*
Output_section::find_relaxed_input_section(const Relobj* object,
					   unsigned int shndx) const
{
  if (!this->lookup_maps_->is_valid())
    this->build_lookup_maps();
  return this->lookup_maps_->find_relaxed_input_section(object, shndx);
}

// Given an address OFFSET relative to the start of input section
// SHNDX in OBJECT, return whether this address is being included in
// the final link.  This should only be called if SHNDX in OBJECT has
// a special mapping.

bool
Output_section::is_input_address_mapped(const Relobj* object,
					unsigned int shndx,
					off_t offset) const
{
  // Look at the Output_section_data_maps first.
  const Output_section_data* posd = this->find_merge_section(object, shndx);
  if (posd == NULL)
    posd = this->find_relaxed_input_section(object, shndx);

  if (posd != NULL)
    {
      section_offset_type output_offset;
      bool found = posd->output_offset(object, shndx, offset, &output_offset);
      // By default we assume that the address is mapped. See comment at the
      // end.
      if (!found)
        return true;
      return output_offset != -1;
    }

  // Fall back to the slow look-up.
  for (Input_section_list::const_iterator p = this->input_sections_.begin();
       p != this->input_sections_.end();
       ++p)
    {
      section_offset_type output_offset;
      if (p->output_offset(object, shndx, offset, &output_offset))
	return output_offset != -1;
    }

  // By default we assume that the address is mapped.  This should
  // only be called after we have passed all sections to Layout.  At
  // that point we should know what we are discarding.
  return true;
}

// Given an address OFFSET relative to the start of input section
// SHNDX in object OBJECT, return the output offset relative to the
// start of the input section in the output section.  This should only
// be called if SHNDX in OBJECT has a special mapping.

section_offset_type
Output_section::output_offset(const Relobj* object, unsigned int shndx,
			      section_offset_type offset) const
{
  // This can only be called meaningfully when we know the data size
  // of this.
  gold_assert(this->is_data_size_valid());

  // Look at the Output_section_data_maps first.
  const Output_section_data* posd = this->find_merge_section(object, shndx);
  if (posd == NULL)
    posd = this->find_relaxed_input_section(object, shndx);
  if (posd != NULL)
    {
      section_offset_type output_offset;
      bool found = posd->output_offset(object, shndx, offset, &output_offset);
      gold_assert(found);
      return output_offset;
    }

  // Fall back to the slow look-up.
  for (Input_section_list::const_iterator p = this->input_sections_.begin();
       p != this->input_sections_.end();
       ++p)
    {
      section_offset_type output_offset;
      if (p->output_offset(object, shndx, offset, &output_offset))
	return output_offset;
    }
  gold_unreachable();
}

// Return the output virtual address of OFFSET relative to the start
// of input section SHNDX in object OBJECT.

uint64_t
Output_section::output_address(const Relobj* object, unsigned int shndx,
			       off_t offset) const
{
  uint64_t addr = this->address() + this->first_input_offset_;

  // Look at the Output_section_data_maps first.
  const Output_section_data* posd = this->find_merge_section(object, shndx);
  if (posd == NULL)
    posd = this->find_relaxed_input_section(object, shndx);
  if (posd != NULL && posd->is_address_valid())
    {
      section_offset_type output_offset;
      bool found = posd->output_offset(object, shndx, offset, &output_offset);
      gold_assert(found);
      return posd->address() + output_offset;
    }

  // Fall back to the slow look-up.
  for (Input_section_list::const_iterator p = this->input_sections_.begin();
       p != this->input_sections_.end();
       ++p)
    {
      addr = align_address(addr, p->addralign());
      section_offset_type output_offset;
      if (p->output_offset(object, shndx, offset, &output_offset))
	{
	  if (output_offset == -1)
	    return