Subversion Repositories open8_urisc

// layout.h -- lay out output file sections for gold  -*- C++ -*-

// Copyright 2006, 2007, 2008, 2009, 2010, 2011 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.

#ifndef GOLD_LAYOUT_H

#define GOLD_LAYOUT_H

#include <cstring>

#include <list>

#include <map>

#include <string>

#include <utility>

#include <vector>

#include "script.h"

#include "workqueue.h"

#include "object.h"

#include "dynobj.h"

#include "stringpool.h"

namespace gold

{

class General_options;

class Incremental_inputs;

class Incremental_binary;

class Input_objects;

class Mapfile;

class Symbol_table;

class Output_section_data;

class Output_section;

class Output_section_headers;

class Output_segment_headers;

class Output_file_header;

class Output_segment;

class Output_data;

class Output_data_reloc_generic;

class Output_data_dynamic;

class Output_symtab_xindex;

class Output_reduced_debug_abbrev_section;

class Output_reduced_debug_info_section;

class Eh_frame;

class Target;

struct Timespec;

// Return TRUE if SECNAME is the name of a compressed debug section.

extern bool

is_compressed_debug_section(const char* secname);

// Maintain a list of free space within a section, segment, or file.

// Used for incremental update links.

class Free_list

{

 public:

  struct Free_list_node

  {

    Free_list_node(off_t start, off_t end)

      : start_(start), end_(end)

    { }

    off_t start_;

    off_t end_;

  };

  typedef std::list<Free_list_node>::const_iterator Const_iterator;

  Free_list()

    : list_(), last_remove_(list_.begin()), extend_(false), length_(0),

      min_hole_(0)

  { }

  // Initialize the free list for a section of length LEN.

  // If EXTEND is true, free space may be allocated past the end.

  void

  init(off_t len, bool extend);

  // Set the minimum hole size that is allowed when allocating

  // from the free list.

  void

  set_min_hole_size(off_t min_hole)

  { this->min_hole_ = min_hole; }

  // Remove a chunk from the free list.

  void

  remove(off_t start, off_t end);

  // Allocate a chunk of space from the free list of length LEN,

  // with alignment ALIGN, and minimum offset MINOFF.

  off_t

  allocate(off_t len, uint64_t align, off_t minoff);

  // Return an iterator for the beginning of the free list.

  Const_iterator

  begin() const

  { return this->list_.begin(); }

  // Return an iterator for the end of the free list.

  Const_iterator

  end() const

  { return this->list_.end(); }

  // Dump the free list (for debugging).

  void

  dump();

  // Print usage statistics.

  static void

  print_stats();

 private:

  typedef std::list<Free_list_node>::iterator Iterator;

  // The free list.

  std::list<Free_list_node> list_;

  // The last node visited during a remove operation.

  Iterator last_remove_;

  // Whether we can extend past the original length.

  bool extend_;

  // The total length of the section, segment, or file.

  off_t length_;

  // The minimum hole size allowed.  When allocating from the free list,

  // we must not leave a hole smaller than this.

  off_t min_hole_;

  // Statistics:

  // The total number of free lists used.

  static unsigned int num_lists;

  // The total number of free list nodes used.

  static unsigned int num_nodes;

  // The total number of calls to Free_list::remove.

  static unsigned int num_removes;

  // The total number of nodes visited during calls to Free_list::remove.

  static unsigned int num_remove_visits;

  // The total number of calls to Free_list::allocate.

  static unsigned int num_allocates;

  // The total number of nodes visited during calls to Free_list::allocate.

  static unsigned int num_allocate_visits;

};

// This task function handles mapping the input sections to output

// sections and laying them out in memory.

class Layout_task_runner : public Task_function_runner

{

 public:

  // OPTIONS is the command line options, INPUT_OBJECTS is the list of

  // input objects, SYMTAB is the symbol table, LAYOUT is the layout

  // object.

  Layout_task_runner(const General_options& options,

                     const Input_objects* input_objects,

                     Symbol_table* symtab,

                     Target* target,

                     Layout* layout,

                     Mapfile* mapfile)

    : options_(options), input_objects_(input_objects), symtab_(symtab),

      target_(target), layout_(layout), mapfile_(mapfile)

  { }

  // Run the operation.

  void

  run(Workqueue*, const Task*);

 private:

  Layout_task_runner(const Layout_task_runner&);

  Layout_task_runner& operator=(const Layout_task_runner&);

  const General_options& options_;

  const Input_objects* input_objects_;

  Symbol_table* symtab_;

  Target* target_;

  Layout* layout_;

  Mapfile* mapfile_;

};

// This class holds information about the comdat group or

// .gnu.linkonce section that will be kept for a given signature.

class Kept_section

{

 private:

  // For a comdat group, we build a mapping from the name of each

  // section in the group to the section index and the size in object.

  // When we discard a group in some other object file, we use this

  // map to figure out which kept section the discarded section is

  // associated with.  We then use that mapping when processing relocs

  // against discarded sections.

  struct Comdat_section_info

  {

    // The section index.

    unsigned int shndx;

    // The section size.

    uint64_t size;

    Comdat_section_info(unsigned int a_shndx, uint64_t a_size)

      : shndx(a_shndx), size(a_size)

    { }

  };

  // Most comdat groups have only one or two sections, so we use a

  // std::map rather than an Unordered_map to optimize for that case

  // without paying too heavily for groups with more sections.

  typedef std::map<std::string, Comdat_section_info> Comdat_group;

 public:

  Kept_section()

    : object_(NULL), shndx_(0), is_comdat_(false), is_group_name_(false)

  { this->u_.linkonce_size = 0; }

  // We need to support copies for the signature map in the Layout

  // object, but we should never copy an object after it has been

  // marked as a comdat section.

  Kept_section(const Kept_section& k)

    : object_(k.object_), shndx_(k.shndx_), is_comdat_(false),

      is_group_name_(k.is_group_name_)

  {

    gold_assert(!k.is_comdat_);

    this->u_.linkonce_size = 0;

  }

  ~Kept_section()

  {

    if (this->is_comdat_)

      delete this->u_.group_sections;

  }

  // The object where this section lives.

  Relobj*

  object() const

  { return this->object_; }

  // Set the object.

  void

  set_object(Relobj* object)

  {

    gold_assert(this->object_ == NULL);

    this->object_ = object;

  }

  // The section index.

  unsigned int

  shndx() const

  { return this->shndx_; }

  // Set the section index.

  void

  set_shndx(unsigned int shndx)

  {

    gold_assert(this->shndx_ == 0);

    this->shndx_ = shndx;

  }

  // Whether this is a comdat group.

  bool

  is_comdat() const

  { return this->is_comdat_; }

  // Set that this is a comdat group.

  void

  set_is_comdat()

  {

    gold_assert(!this->is_comdat_);

    this->is_comdat_ = true;

    this->u_.group_sections = new Comdat_group();

  }

  // Whether this is associated with the name of a group or section

  // rather than the symbol name derived from a linkonce section.

  bool

  is_group_name() const

  { return this->is_group_name_; }

  // Note that this represents a comdat group rather than a single

  // linkonce section.

  void

  set_is_group_name()

  { this->is_group_name_ = true; }

  // Add a section to the group list.

  void

  add_comdat_section(const std::string& name, unsigned int shndx,

                     uint64_t size)

  {

    gold_assert(this->is_comdat_);

    Comdat_section_info sinfo(shndx, size);

    this->u_.group_sections->insert(std::make_pair(name, sinfo));

  }

  // Look for a section name in the group list, and return whether it

  // was found.  If found, returns the section index and size.

  bool

  find_comdat_section(const std::string& name, unsigned int* pshndx,

                      uint64_t* psize) const

  {

    gold_assert(this->is_comdat_);

    Comdat_group::const_iterator p = this->u_.group_sections->find(name);

    if (p == this->u_.group_sections->end())

      return false;

    *pshndx = p->second.shndx;

    *psize = p->second.size;

    return true;

  }

  // If there is only one section in the group list, return true, and

  // return the section index and size.

  bool

  find_single_comdat_section(unsigned int* pshndx, uint64_t* psize) const

  {

    gold_assert(this->is_comdat_);

    if (this->u_.group_sections->size() != 1)

      return false;

    Comdat_group::const_iterator p = this->u_.group_sections->begin();

    *pshndx = p->second.shndx;

    *psize = p->second.size;

    return true;

  }

  // Return the size of a linkonce section.

  uint64_t

  linkonce_size() const

  {

    gold_assert(!this->is_comdat_);

    return this->u_.linkonce_size;

  }

  // Set the size of a linkonce section.

  void

  set_linkonce_size(uint64_t size)

  {

    gold_assert(!this->is_comdat_);

    this->u_.linkonce_size = size;

  }

 private:

  // No assignment.

  Kept_section& operator=(const Kept_section&);

  // The object containing the comdat group or .gnu.linkonce section.

  Relobj* object_;

  // Index of the group section for comdats and the section itself for

  // .gnu.linkonce.

  unsigned int shndx_;

  // True if this is for a comdat group rather than a .gnu.linkonce

  // section.

  bool is_comdat_;

  // The Kept_sections are values of a mapping, that maps names to

  // them.  This field is true if this struct is associated with the

  // name of a comdat or .gnu.linkonce, false if it is associated with

  // the name of a symbol obtained from the .gnu.linkonce.* name

  // through some heuristics.

  bool is_group_name_;

  union

  {

    // If the is_comdat_ field is true, this holds a map from names of

    // the sections in the group to section indexes in object_ and to

    // section sizes.

    Comdat_group* group_sections;

    // If the is_comdat_ field is false, this holds the size of the

    // single section.

    uint64_t linkonce_size;

  } u_;

};

// The ordering for output sections.  This controls how output

// sections are ordered within a PT_LOAD output segment.

enum Output_section_order

{

  // Unspecified.  Used for non-load segments.  Also used for the file

  // and segment headers.

  ORDER_INVALID,

  // The PT_INTERP section should come first, so that the dynamic

  // linker can pick it up quickly.

  ORDER_INTERP,

  // Loadable read-only note sections come next so that the PT_NOTE

  // segment is on the first page of the executable.

  ORDER_RO_NOTE,

  // Put read-only sections used by the dynamic linker early in the

  // executable to minimize paging.

  ORDER_DYNAMIC_LINKER,

  // Put reloc sections used by the dynamic linker after other

  // sections used by the dynamic linker; otherwise, objcopy and strip

  // get confused.

  ORDER_DYNAMIC_RELOCS,

  // Put the PLT reloc section after the other dynamic relocs;

  // otherwise, prelink gets confused.

  ORDER_DYNAMIC_PLT_RELOCS,

  // The .init section.

  ORDER_INIT,

  // The PLT.

  ORDER_PLT,

  // The regular text sections.

  ORDER_TEXT,

  // The .fini section.

  ORDER_FINI,

  // The read-only sections.

  ORDER_READONLY,

  // The exception frame sections.

  ORDER_EHFRAME,

  // The TLS sections come first in the data section.

  ORDER_TLS_DATA,

  ORDER_TLS_BSS,

  // Local RELRO (read-only after relocation) sections come before

  // non-local RELRO sections.  This data will be fully resolved by

  // the prelinker.

  ORDER_RELRO_LOCAL,

  // Non-local RELRO sections are grouped together after local RELRO

  // sections.  All RELRO sections must be adjacent so that they can

  // all be put into a PT_GNU_RELRO segment.

  ORDER_RELRO,

  // We permit marking exactly one output section as the last RELRO

  // section.  We do this so that the read-only GOT can be adjacent to

  // the writable GOT.

  ORDER_RELRO_LAST,

  // Similarly, we permit marking exactly one output section as the

  // first non-RELRO section.

  ORDER_NON_RELRO_FIRST,

  // The regular data sections come after the RELRO sections.

  ORDER_DATA,

  // Large data sections normally go in large data segments.

  ORDER_LARGE_DATA,

  // Group writable notes so that we can have a single PT_NOTE

  // segment.

  ORDER_RW_NOTE,

  // The small data sections must be at the end of the data sections,

  // so that they can be adjacent to the small BSS sections.

  ORDER_SMALL_DATA,

  // The BSS sections start here.

  // The small BSS sections must be at the start of the BSS sections,

  // so that they can be adjacent to the small data sections.

  ORDER_SMALL_BSS,

  // The regular BSS sections.

  ORDER_BSS,

  // The large BSS sections come after the other BSS sections.

  ORDER_LARGE_BSS,

  // Maximum value.

  ORDER_MAX

};

// This class handles the details of laying out input sections.

class Layout

{

 public:

  Layout(int number_of_input_files, Script_options*);

  ~Layout()

  {

    delete this->relaxation_debug_check_;

    delete this->segment_states_;

  }

  // For incremental links, record the base file to be modified.

  void

  set_incremental_base(Incremental_binary* base);

  Incremental_binary*

  incremental_base()

  { return this->incremental_base_; }

  // 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*

  init_fixed_output_section(const char*, elfcpp::Shdr<size, big_endian>&);

  // Given an input section SHNDX, named NAME, with data in SHDR, from

  // the object file OBJECT, return the output section where this

  // input section should go.  RELOC_SHNDX is the index of a

  // relocation section which applies to this section, or 0 if none,

  // or -1U if more than one.  RELOC_TYPE is the type of the

  // relocation section if there is one.  Set *OFFSET to the offset

  // within the output section.

  template<int size, bool big_endian>

  Output_section*

  layout(Sized_relobj_file<size, big_endian> *object, unsigned int shndx,

         const char* name, const elfcpp::Shdr<size, big_endian>& shdr,

         unsigned int reloc_shndx, unsigned int reloc_type, off_t* offset);

  bool

  is_section_ordering_specified()

  { return this->section_ordering_specified_; }

  void

  set_section_ordering_specified()

  { this->section_ordering_specified_ = true; }

  // For incremental updates, allocate a block of memory from the

  // free list.  Find a block starting at or after MINOFF.

  off_t

  allocate(off_t len, uint64_t align, off_t minoff)

  { return this->free_list_.allocate(len, align, minoff); }

  unsigned int

  find_section_order_index(const std::string&);

  // Read the sequence of input sections from the file specified with

  // linker option --section-ordering-file.

  void

  read_layout_from_file();

  // Layout an input reloc section when doing a relocatable link.  The

  // section is RELOC_SHNDX in OBJECT, with data in SHDR.

  // DATA_SECTION is the reloc section to which it refers.  RR is the

  // relocatable information.

  template<int size, bool big_endian>

  Output_section*

  layout_reloc(Sized_relobj_file<size, big_endian>* object,

               unsigned int reloc_shndx,

               const elfcpp::Shdr<size, big_endian>& shdr,

               Output_section* data_section,

               Relocatable_relocs* rr);

  // Layout a group section when doing a relocatable link.

  template<int size, bool big_endian>

  void

  layout_group(Symbol_table* symtab,

               Sized_relobj_file<size, big_endian>* object,

               unsigned int group_shndx,

               const char* group_section_name,

               const char* signature,

               const elfcpp::Shdr<size, big_endian>& shdr,

               elfcpp::Elf_Word flags,

               std::vector<unsigned int>* shndxes);

  // Like layout, only for exception frame sections.  OBJECT is an

  // object file.  SYMBOLS is the contents of the symbol table

  // section, with size SYMBOLS_SIZE.  SYMBOL_NAMES is the contents of

  // the symbol name section, with size SYMBOL_NAMES_SIZE.  SHNDX is a

  // .eh_frame section in OBJECT.  SHDR is the section header.

  // RELOC_SHNDX is the index of a relocation section which applies to

  // this section, or 0 if none, or -1U if more than one.  RELOC_TYPE

  // is the type of the relocation section if there is one.  This

  // returns the output section, and sets *OFFSET to the offset.

  template<int size, bool big_endian>

  Output_section*

  layout_eh_frame(Sized_relobj_file<size, big_endian>* object,

                  const unsigned char* symbols,

                  off_t symbols_size,

                  const unsigned char* symbol_names,

                  off_t symbol_names_size,

                  unsigned int shndx,

                  const elfcpp::Shdr<size, big_endian>& shdr,

                  unsigned int reloc_shndx, unsigned int reloc_type,

                  off_t* offset);

  // Add .eh_frame information for a PLT.  The FDE must start with a

  // 4-byte PC-relative reference to the start of the PLT, followed by

  // a 4-byte size of PLT.

  void

  add_eh_frame_for_plt(Output_data* plt, const unsigned char* cie_data,

                       size_t cie_length, const unsigned char* fde_data,

                       size_t fde_length);

  // Handle a GNU stack note.  This is called once per input object

  // file.  SEEN_GNU_STACK is true if the object file has a

  // .note.GNU-stack section.  GNU_STACK_FLAGS is the section flags

  // from that section if there was one.

  void

  layout_gnu_stack(bool seen_gnu_stack, uint64_t gnu_stack_flags,

                   const Object*);

  // Add an Output_section_data to the layout.  This is used for

  // special sections like the GOT section.  ORDER is where the

  // section should wind up in the output segment.  IS_RELRO is true

  // for relro sections.

  Output_section*

  add_output_section_data(const char* name, elfcpp::Elf_Word type,

                          elfcpp::Elf_Xword flags,

                          Output_section_data*, Output_section_order order,

                          bool is_relro);

  // Increase the size of the relro segment by this much.

  void

  increase_relro(unsigned int s)

  { this->increase_relro_ += s; }

  // Create dynamic sections if necessary.

  void

  create_initial_dynamic_sections(Symbol_table*);

  // Define __start and __stop symbols for output sections.

  void

  define_section_symbols(Symbol_table*);

  // Create automatic note sections.

  void

  create_notes();

  // Create sections for linker scripts.

  void

  create_script_sections()

  { this->script_options_->create_script_sections(this); }

  // Define symbols from any linker script.

  void

  define_script_symbols(Symbol_table* symtab)

  { this->script_options_->add_symbols_to_table(symtab); }

  // Define symbols for group signatures.

  void

  define_group_signatures(Symbol_table*);

  // Return the Stringpool used for symbol names.

  const Stringpool*

  sympool() const

  { return &this->sympool_; }

  // Return the Stringpool used for dynamic symbol names and dynamic

  // tags.

  const Stringpool*

  dynpool() const

  { return &this->dynpool_; }

  // Return the .dynamic output section.  This is only valid after the

  // layout has been finalized.

  Output_section*

  dynamic_section() const

  { return this->dynamic_section_; }

  // Return the symtab_xindex section used to hold large section

  // indexes for the normal symbol table.

  Output_symtab_xindex*

  symtab_xindex() const

  { return this->symtab_xindex_; }

  // Return the dynsym_xindex section used to hold large section

  // indexes for the dynamic symbol table.

  Output_symtab_xindex*

  dynsym_xindex() const

  { return this->dynsym_xindex_; }

  // Return whether a section is a .gnu.linkonce section, given the

  // section name.

  static inline bool

  is_linkonce(const char* name)

  { return strncmp(name, ".gnu.linkonce", sizeof(".gnu.linkonce") - 1) == 0; }

  // Whether we have added an input section.

  bool

  have_added_input_section() const

  { return this->have_added_input_section_; }

  // Return true if a section is a debugging section.

  static inline bool

  is_debug_info_section(const char* name)

  {

    // Debugging sections can only be recognized by name.

    return (strncmp(name, ".debug", sizeof(".debug") - 1) == 0

            || strncmp(name, ".zdebug", sizeof(".zdebug") - 1) == 0

            || strncmp(name, ".gnu.linkonce.wi.",

                       sizeof(".gnu.linkonce.wi.") - 1) == 0

            || strncmp(name, ".line", sizeof(".line") - 1) == 0

            || strncmp(name, ".stab", sizeof(".stab") - 1) == 0);

  }

  // Return true if RELOBJ is an input file whose base name matches

  // FILE_NAME.  The base name must have an extension of ".o", and

  // must be exactly FILE_NAME.o or FILE_NAME, one character, ".o".

  static bool

  match_file_name(const Relobj* relobj, const char* file_name);

  // Return whether section SHNDX in RELOBJ is a .ctors/.dtors section

  // with more than one word being mapped to a .init_array/.fini_array

  // section.

  bool

  is_ctors_in_init_array(Relobj* relobj, unsigned int shndx) const;

  // Check if a comdat group or .gnu.linkonce section with the given

  // NAME is selected for the link.  If there is already a section,

  // *KEPT_SECTION is set to point to the signature and the function

  // returns false.  Otherwise, OBJECT, SHNDX,IS_COMDAT, and

  // IS_GROUP_NAME are recorded for this NAME in the layout object,

  // *KEPT_SECTION is set to the internal copy and the function return

  // false.

  bool

  find_or_add_kept_section(const std::string& name, Relobj* object,

                           unsigned int shndx, bool is_comdat,

                           bool is_group_name, Kept_section** kept_section);

  // Finalize the layout after all the input sections have been added.

  off_t

  finalize(const Input_objects*, Symbol_table*, Target*, const Task*);

  // Return whether any sections require postprocessing.

  bool

  any_postprocessing_sections() const

  { return this->any_postprocessing_sections_; }