PATCH COMMITTED: Implement constructor priorities in gold

[Ian Lance Taylor <iant at google dot com>]

Another gcc testsuite failure pointed out that gold did not implement
constructor priorities.  Unfortunately, when I wrote that code for GNU
ld some 10 or 12 years ago, I picked a goofy implementation based on
linker scripts.  Since gold doesn't use a linker script by default,
hacking in the special case support was a pain.  But it seems to be
required in order for constructor priorities to work.  Not that many
people use them anyhow.

The patch includes a test case which I borrowed from gcc.  Since
constructor priorities as attributes were only implemented in gcc
4.3.0, I added a configure test to know when it is OK to run the test.

Ian


2008-03-28  Ian Lance Taylor  <iant@google.com>

	* layout.cc (Layout::layout): If we see an input section with a
	name that needs sorting, set the must_sort flag for the output
	section.
	(Layout::make_output_section): If the name of the output section
	indicates that it might	require sorting, set the may_sort flag.
	* output.h (Output_section::may_sort_attached_input_sections): New
	function.
	(Output_section::set_may_sort_attached_input_sections): New
	function.
	(Output_section::must_sort_attached_input_sections): New
	function.
	(Output_section::set_must_sort_attached_input_sections): New
	function.
	(class Output_section): Declare Input_section_sort_entry.  Define
	Input_section_sort_compare.  Declare
	sort_attached_input_sections.  Add new fields:
	may_sort_attached_input_sections_,
	must_sort_attached_input_sections_,
	attached_input_sections_are_sorted_.
	* output.cc (Output_section::Output_section): Initialize new
	fields.
	(Output_section::add_input_section): Add an entry to
	input_sections_ if may_sort or must_sort are true.
	(Output_section::set_final_data_size): Call
	sort_attached_input_sections if necessary.
	(Output_section::Input_section_sort_entry): Define new class.
	(Output_section::Input_section_sort_compare::operator()): New
	function.
	(Output_section::sort_attached_input_sections): New function.
	* configure.ac: Check whether the compiler supports constructor
	priorities.  Define a CONSTRUCTOR_PRIORITY automake conditional.
	* testsuite/initpri1.c: New file.
	* testsuite/Makefile.am (check_PROGRAMS): Add initpri1 if
	CONSTRUCTOR_PRIORITY.
	(initpri1_SOURCES, initpri1_DEPENDENCIES): New variables.
	(initpri1_LDFLAGS): New variable.
	* configure, Makefile.in, testsuite/Makefile.in: Rebuild.


Index: configure.ac
===================================================================
RCS file: /cvs/src/src/gold/configure.ac,v
retrieving revision 1.25
diff -p -u -r1.25 configure.ac
--- configure.ac	26 Mar 2008 23:36:46 -0000	1.25
+++ configure.ac	28 Mar 2008 22:41:17 -0000
@@ -223,6 +223,14 @@ error
 
 AM_CONDITIONAL(STATIC_TLS, test "$gold_cv_lib_glibc24" = "yes")
 
+dnl Check whether the compiler supports constructor priorities in
+dnl attributes, which were added in gcc 4.3.
+AC_CACHE_CHECK([for constructor priorities], [gold_cv_c_conprio],
+[AC_COMPILE_IFELSE([void f() __attribute__ ((constructor (1)));],
+[gold_cv_c_conprio=yes], [gold_cv_c_conprio=no])])
+
+AM_CONDITIONAL(CONSTRUCTOR_PRIORITY, test "$gold_cv_c_conprio" = "yes")
+
 AM_BINUTILS_WARNINGS
 
 WARN_CXXFLAGS=`echo ${WARN_CFLAGS} | sed -e 's/-Wstrict-prototypes//' -e 's/-Wmissing-prototypes//'`
Index: layout.cc
===================================================================
RCS file: /cvs/src/src/gold/layout.cc,v
retrieving revision 1.95
diff -p -u -r1.95 layout.cc
--- layout.cc	25 Mar 2008 05:11:41 -0000	1.95
+++ layout.cc	28 Mar 2008 22:41:17 -0000
@@ -404,6 +404,17 @@ Layout::layout(Sized_relobj<size, big_en
 	return NULL;
     }
 
+  // By default the GNU linker sorts input sections whose names match
+  // .ctor.*, .dtor.*, .init_array.*, or .fini_array.*.  The sections
+  // are sorted by name.  This is used to implement constructor
+  // priority ordering.  We are compatible.
+  if (!this->script_options_->saw_sections_clause()
+      && (is_prefix_of(".ctors.", name)
+	  || is_prefix_of(".dtors.", name)
+	  || is_prefix_of(".init_array.", name)
+	  || is_prefix_of(".fini_array.", name)))
+    os->set_must_sort_attached_input_sections();
+
   // FIXME: Handle SHF_LINK_ORDER somewhere.
 
   *off = os->add_input_section(object, shndx, name, shdr, reloc_shndx,
@@ -671,6 +682,16 @@ Layout::make_output_section(const char* 
   else
     this->attach_to_segment(os, flags);
 
+  // The GNU linker by default sorts some sections by priority, so we
+  // do the same.  We need to know that this might happen before we
+  // attach any input sections.
+  if (!this->script_options_->saw_sections_clause()
+      && (strcmp(name, ".ctors") == 0
+	  || strcmp(name, ".dtors") == 0
+	  || strcmp(name, ".init_array") == 0
+	  || strcmp(name, ".fini_array") == 0))
+    os->set_may_sort_attached_input_sections();
+
   return os;
 }
 
Index: output.cc
===================================================================
RCS file: /cvs/src/src/gold/output.cc,v
retrieving revision 1.66
diff -p -u -r1.66 output.cc
--- output.cc	26 Mar 2008 23:36:46 -0000	1.66
+++ output.cc	28 Mar 2008 22:41:17 -0000
@@ -1595,6 +1595,9 @@ Output_section::Output_section(const cha
     found_in_sections_clause_(false),
     has_load_address_(false),
     info_uses_section_index_(false),
+    may_sort_attached_input_sections_(false),
+    must_sort_attached_input_sections_(false),
+    attached_input_sections_are_sorted_(false),
     tls_offset_(0)
 {
   // An unallocated section has no address.  Forcing this means that
@@ -1711,9 +1714,14 @@ Output_section::add_input_section(Sized_
 					+ shdr.get_sh_size());
 
   // We need to keep track of this section if we are already keeping
-  // track of sections, or if we are relaxing.  FIXME: Add test for
+  // 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.  FIXME: Add test for
   // relaxing.
-  if (have_sections_script || !this->input_sections_.empty())
+  if (have_sections_script
+      || !this->input_sections_.empty()
+      || this->may_sort_attached_input_sections()
+      || this->must_sort_attached_input_sections())
     this->input_sections_.push_back(Input_section(object, shndx,
 						  shdr.get_sh_size(),
 						  addralign));
@@ -1943,6 +1951,9 @@ Output_section::set_final_data_size()
       return;
     }
 
+  if (this->must_sort_attached_input_sections())
+    this->sort_attached_input_sections();
+
   uint64_t address = this->address();
   off_t startoff = this->offset();
   off_t off = startoff + this->first_input_offset_;
@@ -1978,6 +1989,239 @@ Output_section::do_set_tls_offset(uint64
   this->tls_offset_ = this->address() - tls_base;
 }
 
+// In a few cases we need to sort the input sections attached to an
+// output section.  This is used to implement the type of constructor
+// priority ordering implemented by the GNU linker, in which the
+// priority becomes part of the section name and the sections are
+// sorted by name.  We only do this for an output section if we see an
+// attached input section matching ".ctor.*", ".dtor.*",
+// ".init_array.*" or ".fini_array.*".
+
+class Output_section::Input_section_sort_entry
+{
+ public:
+  Input_section_sort_entry()
+    : input_section_(), index_(-1U), section_has_name_(false),
+      section_name_()
+  { }
+
+  Input_section_sort_entry(const Input_section& input_section,
+			   unsigned int index)
+    : input_section_(input_section), index_(index),
+      section_has_name_(input_section.is_input_section())
+  {
+    if (this->section_has_name_)
+      {
+	// This is only called single-threaded from Layout::finalize,
+	// so it is OK to lock.  Unfortunately we have no way to pass
+	// in a Task token.
+	const Task* dummy_task = reinterpret_cast<const Task*>(-1);
+	Object* obj = input_section.relobj();
+	Task_lock_obj<Object> tl(dummy_task, obj);
+
+	// This is a slow operation, which should be cached in
+	// Layout::layout if this becomes a speed problem.
+	this->section_name_ = obj->section_name(input_section.shndx());
+      }
+  }
+
+  // Return the Input_section.
+  const Input_section&
+  input_section() const
+  {
+    gold_assert(this->index_ != -1U);
+    return this->input_section_;
+  }
+
+  // The index of this entry in the original list.  This is used to
+  // make the sort stable.
+  unsigned int
+  index() const
+  {
+    gold_assert(this->index_ != -1U);
+    return this->index_;
+  }
+
+  // Whether there is a section name.
+  bool
+  section_has_name() const
+  { return this->section_has_name_; }
+
+  // The section name.
+  const std::string&
+  section_name() const
+  {
+    gold_assert(this->section_has_name_);
+    return this->section_name_;
+  }
+
+  // Return true if the section name is either SECTION_NAME1 or
+  // SECTION_NAME2.
+  bool
+  match_section_name(const char* section_name1, const char* section_name2) const
+  {
+    gold_assert(this->section_has_name_);
+    return (this->section_name_ == section_name1
+	    || this->section_name_ == section_name2);
+  }
+
+  // Return true if PREFIX1 or PREFIX2 is a prefix of the section
+  // name.
+  bool
+  match_section_name_prefix(const char* prefix1, const char* prefix2) const
+  {
+    gold_assert(this->section_has_name_);
+    return (this->section_name_.compare(0, strlen(prefix1), prefix1) == 0
+	    || this->section_name_.compare(0, strlen(prefix2), prefix2) == 0);
+  }
+
+  // Return true if this is for a section named SECTION_NAME1 or
+  // SECTION_NAME2 in 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".  This is to match
+  // crtbegin.o as well as crtbeginS.o without getting confused by
+  // other possibilities.  Overall matching the file name this way is
+  // a dreadful hack, but the GNU linker does it in order to better
+  // support gcc, and we need to be compatible.
+  bool
+  match_section_file(const char* section_name1, const char* section_name2,
+		     const char* match_file_name) const
+  {
+    gold_assert(this->section_has_name_);
+    if (this->section_name_ != section_name1
+	&& this->section_name_ != section_name2)
+      return false;
+    const std::string& file_name(this->input_section_.relobj()->name());
+    const char* base_name = lbasename(file_name.c_str());
+    size_t match_len = strlen(match_file_name);
+    if (strncmp(base_name, match_file_name, match_len) != 0)
+      return false;
+    size_t base_len = strlen(base_name);
+    if (base_len != match_len + 2 && base_len != match_len + 3)
+      return false;
+    return memcmp(base_name + base_len - 2, ".o", 2) == 0;
+  }
+
+ private:
+  // The Input_section we are sorting.
+  Input_section input_section_;
+  // The index of this Input_section in the original list.
+  unsigned int index_;
+  // Whether this Input_section has a section name--it won't if this
+  // is some random Output_section_data.
+  bool section_has_name_;
+  // The section name if there is one.
+  std::string section_name_;
+};
+
+// Return true if S1 should come before S2 in the output section.
+
+bool
+Output_section::Input_section_sort_compare::operator()(
+    const Output_section::Input_section_sort_entry& s1,
+    const Output_section::Input_section_sort_entry& s2) const
+{
+  // We sort all the sections with no names to the end.
+  if (!s1.section_has_name() || !s2.section_has_name())
+    {
+      if (s1.section_has_name())
+	return true;
+      if (s2.section_has_name())
+	return false;
+      return s1.index() < s2.index();
+    }
+
+  // A .ctors or .dtors section from crtbegin.o must come before any
+  // other .ctors* or .dtors* section.
+  bool s1_begin = s1.match_section_file(".ctors", ".dtors", "crtbegin");
+  bool s2_begin = s2.match_section_file(".ctors", ".dtors", "crtbegin");
+  if (s1_begin || s2_begin)
+    {
+      if (!s1_begin)
+	return false;
+      if (!s2_begin)
+	return true;
+      return s1.index() < s2.index();
+    }
+
+  // A .ctors or .dtors section from crtend.o must come after any
+  // other .ctors* or .dtors* section.
+  bool s1_end = s1.match_section_file(".ctors", ".dtors", "crtend");
+  bool s2_end = s2.match_section_file(".ctors", ".dtors", "crtend");
+  if (s1_end || s2_end)
+    {
+      if (!s1_end)
+	return true;
+      if (!s2_end)
+	return false;
+      return s1.index() < s2.index();
+    }
+
+  // A .ctors or .init_array section with a priority precedes a .ctors
+  // or .init_array section without a priority.
+  if (s1.match_section_name_prefix(".ctors.", ".init_array.")
+      && s2.match_section_name(".ctors", ".init_array"))
+    return true;
+  if (s2.match_section_name_prefix(".ctors.", ".init_array.")
+      && s1.match_section_name(".ctors", ".init_array"))
+    return false;
+
+  // A .dtors or .fini_array section with a priority follows a .dtors
+  // or .fini_array section without a priority.
+  if (s1.match_section_name_prefix(".dtors.", ".fini_array.")
+      && s2.match_section_name(".dtors", ".fini_array"))
+    return false;
+  if (s2.match_section_name_prefix(".dtors.", ".fini_array.")
+      && s1.match_section_name(".dtors", ".fini_array"))
+    return true;
+
+  // Otherwise we sort by name.
+  int compare = s1.section_name().compare(s2.section_name());
+  if (compare != 0)
+    return compare < 0;
+
+  // Otherwise we keep the input order.
+  return s1.index() < s2.index();
+}
+
+// Sort the input sections attached to an output section.
+
+void
+Output_section::sort_attached_input_sections()
+{
+  if (this->attached_input_sections_are_sorted_)
+    return;
+
+  // The only thing we know about an input section is the object and
+  // the section index.  We need the section name.  Recomputing this
+  // is slow but this is an unusual case.  If this becomes a speed
+  // problem we can cache the names as required in Layout::layout.
+
+  // We start by building a larger vector holding a copy of each
+  // Input_section, plus its current index in the list and its name.
+  std::vector<Input_section_sort_entry> sort_list;
+
+  unsigned int i = 0;
+  for (Input_section_list::iterator p = this->input_sections_.begin();
+       p != this->input_sections_.end();
+       ++p, ++i)
+    sort_list.push_back(Input_section_sort_entry(*p, i));
+
+  // Sort the input sections.
+  std::sort(sort_list.begin(), sort_list.end(), Input_section_sort_compare());
+
+  // Copy the sorted input sections back to our list.
+  this->input_sections_.clear();
+  for (std::vector<Input_section_sort_entry>::iterator p = sort_list.begin();
+       p != sort_list.end();
+       ++p)
+    this->input_sections_.push_back(p->input_section());
+
+  // Remember that we sorted the input sections, since we might get
+  // called again.
+  this->attached_input_sections_are_sorted_ = true;
+}
+
 // Write the section header to *OSHDR.
 
 template<int size, bool big_endian>
Index: output.h
===================================================================
RCS file: /cvs/src/src/gold/output.h,v
retrieving revision 1.58
diff -p -u -r1.58 output.h
--- output.h	25 Mar 2008 18:37:16 -0000	1.58
+++ output.h	28 Mar 2008 22:41:18 -0000
@@ -1869,6 +1869,32 @@ class Output_section : public Output_dat
     this->dynsym_index_ = index;
   }
 
+  // Return whether the input sections sections attachd to this output
+  // section may require sorting.  This is used to handle constructor
+  // priorities compatibly with GNU ld.
+  bool
+  may_sort_attached_input_sections() const
+  { return this->may_sort_attached_input_sections_; }
+
+  // Record that the input sections attached to this output section
+  // may require sorting.
+  void
+  set_may_sort_attached_input_sections()
+  { this->may_sort_attached_input_sections_ = true; }
+
+  // Return whether the input sections attached to this output section
+  // require sorting.  This is used to handle constructor priorities
+  // compatibly with GNU ld.
+  bool
+  must_sort_attached_input_sections() const
+  { return this->must_sort_attached_input_sections_; }
+
+  // Record that the input sections attached to this output section
+  // require sorting.
+  void
+  set_must_sort_attached_input_sections()
+  { this->must_sort_attached_input_sections_ = true; }
+
   // Return whether this section should be written after all the input
   // sections are complete.
   bool
@@ -2310,6 +2336,17 @@ class Output_section : public Output_dat
 
   typedef std::vector<Input_section> Input_section_list;
 
+  // This class is used to sort the input sections.
+  class Input_section_sort_entry;
+
+  // This is the sort comparison function.
+  struct Input_section_sort_compare
+  {
+    bool
+    operator()(const Input_section_sort_entry&,
+	       const Input_section_sort_entry&) const;
+  };
+
   // Fill data.  This is used to fill in data between input sections.
   // It is also used for data statements (BYTE, WORD, etc.) in linker
   // scripts.  When we have to keep track of the input sections, we
@@ -2360,6 +2397,10 @@ class Output_section : public Output_dat
   add_output_merge_section(Output_section_data* posd, bool is_string,
 			   uint64_t entsize);
 
+  // Sort the attached input sections.
+  void
+  sort_attached_input_sections();
+
   // Most of these fields are only valid after layout.
 
   // The name of the section.  This will point into a Stringpool.
@@ -2443,6 +2484,15 @@ class Output_section : public Output_dat
   // section, false if it means the symbol index of the corresponding
   // section symbol.
   bool info_uses_section_index_ : 1;
+  // True if the input sections attached to this output section may
+  // need sorting.
+  bool may_sort_attached_input_sections_ : 1;
+  // True if the input sections attached to this output section must
+  // be sorted.
+  bool must_sort_attached_input_sections_ : 1;
+  // True if the input sections attached to this output section have
+  // already been sorted.
+  bool attached_input_sections_are_sorted_ : 1;
   // For SHT_TLS sections, the offset of this section relative to the base
   // of the TLS segment.
   uint64_t tls_offset_;
Index: testsuite/Makefile.am
===================================================================
RCS file: /cvs/src/src/gold/testsuite/Makefile.am,v
retrieving revision 1.50
diff -p -u -r1.50 Makefile.am
--- testsuite/Makefile.am	27 Mar 2008 19:57:41 -0000	1.50
+++ testsuite/Makefile.am	28 Mar 2008 22:41:18 -0000
@@ -417,6 +417,16 @@ endif FN_PTRS_IN_SO_WITHOUT_PIC
 endif TLS
 
 
+if CONSTRUCTOR_PRIORITY
+
+check_PROGRAMS += initpri1
+initpri1_SOURCES = initpri1.c
+initpri1_DEPENDENCIES = gcctestdir/ld
+initpri1_LDFLAGS = -Bgcctestdir/
+
+endif
+
+
 # Test --detect-odr-violations
 check_SCRIPTS += debug_msg.sh
 
Index: testsuite/initpri1.c
===================================================================
RCS file: testsuite/initpri1.c
diff -N testsuite/initpri1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/initpri1.c	28 Mar 2008 22:41:18 -0000
@@ -0,0 +1,87 @@
+/* initpri1.c -- test constructor priorities.
+
+   Copyright 2007, 2008 Free Software Foundation, Inc.
+   Copied from the gcc testsuite, where the test was contributed by
+   Mark Mitchell <mark@codesourcery.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.
+
+   This is a test of a common symbol in the main program and a
+   versioned symbol in a shared library.  The common symbol in the
+   main program should override the shared library symbol.  */
+
+#include <stdlib.h>
+
+int i;
+int j;
+
+void c1() __attribute__((constructor (500)));
+void c2() __attribute__((constructor (700)));
+void c3() __attribute__((constructor (600)));
+
+void c1() {
+  if (i++ != 0)
+    abort ();
+}
+
+void c2() {
+  if (i++ != 2)
+    abort ();
+}
+
+void c3() {
+  if (i++ != 1)
+    abort ();
+}
+
+void d1() __attribute__((destructor (500)));
+void d2() __attribute__((destructor (700)));
+void d3() __attribute__((destructor (600)));
+
+void d1() {
+  if (--i != 0)
+    abort ();
+}
+
+void d2() {
+  if (--i != 2)
+    abort ();
+}
+
+void d3() {
+  if (j != 2)
+    abort ();
+  if (--i != 1)
+    abort ();
+}
+
+void cd4() __attribute__((constructor (800), destructor (800)));
+
+void cd4() {
+  if (i != 3)
+    abort ();
+  ++j;
+}
+
+int main () {
+  if (i != 3)
+    return 1;
+  if (j != 1)
+    abort ();
+  return 0;
+}