Rework stringpool and hash tables so that we always generate the same

output regardless of randomize_va_space.

8 files changed, 152 insertions, 78 deletions

diff --git a/gold/layout.cc b/gold/layout.cc
index 2bdd11b477..e969a806a0 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -53,7 +53,7 @@ Layout::Layout(const General_options& options)
 size_t
 Layout::Hash_key::operator()(const Layout::Key& k) const
 {
- return reinterpret_cast<size_t>(k.first) + k.second.first + k.second.second;
+ return k.first + k.second.first + k.second.second;
 }
 
 // Whether to include this section in the link.
@@ -95,7 +95,7 @@ Layout::find_output_section(const char* name) const
   for (Section_name_map::const_iterator p = this->section_name_map_.begin();
        p != this->section_name_map_.end();
        ++p)
-    if (strcmp(p->first.first, name) == 0)
+    if (strcmp(p->second->name(), name) == 0)
       return p->second;
   return NULL;
 }
@@ -121,15 +121,15 @@ Layout::find_output_segment(elfcpp::PT type, elfcpp::Elf_Word set,
 // and section flags FLAGS.
 
 Output_section*
-Layout::get_output_section(const char* name, elfcpp::Elf_Word type,
-			   elfcpp::Elf_Xword flags)
+Layout::get_output_section(const char* name, Stringpool::Key name_key,
+			   elfcpp::Elf_Word type, elfcpp::Elf_Xword flags)
 {
   // We should ignore some flags.
   flags &= ~ (elfcpp::SHF_INFO_LINK
 	      | elfcpp::SHF_LINK_ORDER
 	      | elfcpp::SHF_GROUP);
 
-  const Key key(name, std::make_pair(type, flags));
+  const Key key(name_key, std::make_pair(type, flags));
   const std::pair<Key, Output_section*> v(key, NULL);
   std::pair<Section_name_map::iterator, bool> ins(
     this->section_name_map_.insert(v));
@@ -167,11 +167,13 @@ Layout::layout(Relobj* object, unsigned int shndx, const char* name,
   // FIXME: Handle SHF_OS_NONCONFORMING here.
 
   // Canonicalize the section name.
-  name = this->namepool_.add(name, len);
+  Stringpool::Key name_key;
+  name = this->namepool_.add(name, len, &name_key);
 
   // Find the output section.  The output section is selected based on
   // the section name, type, and flags.
-  Output_section* os = this->get_output_section(name, shdr.get_sh_type(),
+  Output_section* os = this->get_output_section(name, name_key,
+						shdr.get_sh_type(),
 						shdr.get_sh_flags());
 
   // FIXME: Handle SHF_LINK_ORDER somewhere.
@@ -189,9 +191,10 @@ Layout::add_output_section_data(const char* name, elfcpp::Elf_Word type,
 				Output_section_data* posd)
 {
   // Canonicalize the name.
-  name = this->namepool_.add(name);
+  Stringpool::Key name_key;
+  name = this->namepool_.add(name, &name_key);
 
-  Output_section* os = this->get_output_section(name, type, flags);
+  Output_section* os = this->get_output_section(name, name_key, type, flags);
   os->add_output_section_data(posd);
 }
 
@@ -672,12 +675,12 @@ Layout::create_symtab_sections(int size, const Input_objects* input_objects,
 
   this->sympool_.set_string_offsets();
 
-  const char* symtab_name = this->namepool_.add(".symtab");
+  const char* symtab_name = this->namepool_.add(".symtab", NULL);
   Output_section* osymtab = new Output_section_symtab(symtab_name,
 						      off - startoff);
   this->section_list_.push_back(osymtab);
 
-  const char* strtab_name = this->namepool_.add(".strtab");
+  const char* strtab_name = this->namepool_.add(".strtab", NULL);
   Output_section *ostrtab = new Output_section_strtab(strtab_name,
 						      &this->sympool_);
   this->section_list_.push_back(ostrtab);
@@ -703,7 +706,7 @@ Layout::create_shstrtab()
   // FIXME: We don't need to create a .shstrtab section if we are
   // stripping everything.
 
-  const char* name = this->namepool_.add(".shstrtab");
+  const char* name = this->namepool_.add(".shstrtab", NULL);
 
   this->namepool_.set_string_offsets();
 
diff --git a/gold/layout.h b/gold/layout.h
index bb2b644bd6..fa34617a3b 100644
--- a/gold/layout.h
+++ b/gold/layout.h
@@ -196,8 +196,8 @@ class Layout
 
   // Return the output section for NAME, TYPE and FLAGS.
   Output_section*
-  get_output_section(const char* name, elfcpp::Elf_Word type,
-		     elfcpp::Elf_Xword flags);
+  get_output_section(const char* name, Stringpool::Key name_key,
+		     elfcpp::Elf_Word type, elfcpp::Elf_Xword flags);
 
   // Create a new Output_section.
   Output_section*
@@ -218,7 +218,7 @@ class Layout
   // Mapping from input section name/type/flags to output section.  We
   // use canonicalized strings here.
 
-  typedef std::pair<const char*,
+  typedef std::pair<Stringpool::Key,
 		    std::pair<elfcpp::Elf_Word, elfcpp::Elf_Xword> > Key;
 
   struct Hash_key
diff --git a/gold/object.cc b/gold/object.cc
index 22e89a9604..956366cdf0 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -628,7 +628,7 @@ Sized_relobj<size, big_endian>::do_finalize_local_symbols(off_t off,
 
       if (sym.get_st_type() != elfcpp::STT_SECTION)
 	{
-	  pool->add(pnames + sym.get_st_name());
+	  pool->add(pnames + sym.get_st_name(), NULL);
 	  off += sym_size;
 	  ++count;
 	}
diff --git a/gold/po/gold.pot b/gold/po/gold.pot
index 4f00da433c..c88ba7dd7f 100644
--- a/gold/po/gold.pot
+++ b/gold/po/gold.pot
@@ -8,7 +8,7 @@ msgid ""
 msgstr ""
 "Project-Id-Version: PACKAGE VERSION\n"
 "Report-Msgid-Bugs-To: \n"
-"POT-Creation-Date: 2006-11-06 13:40-0800\n"
+"POT-Creation-Date: 2006-11-06 15:58-0800\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
@@ -477,22 +477,22 @@ msgstr ""
 msgid "%s: %s: unsupported symbol binding %d for symbol %s\n"
 msgstr ""
 
-#: symtab.cc:432
+#: symtab.cc:440
 #, c-format
 msgid "%s: %s: mixing 32-bit and 64-bit ELF objects\n"
 msgstr ""
 
-#: symtab.cc:449
+#: symtab.cc:457
 #, c-format
 msgid "%s: %s: bad global symbol name offset %u at %lu\n"
 msgstr ""
 
-#: symtab.cc:865 symtab.cc:1004
+#: symtab.cc:882 symtab.cc:1021
 #, c-format
 msgid "%s: %s: unsupported symbol section 0x%x\n"
 msgstr ""
 
-#: symtab.cc:1114
+#: symtab.cc:1131
 #, c-format
 msgid "%s: %s: warning: %s\n"
 msgstr ""
diff --git a/gold/stringpool.cc b/gold/stringpool.cc
index b1a2ce2433..5b60259a20 100644
--- a/gold/stringpool.cc
+++ b/gold/stringpool.cc
@@ -14,7 +14,7 @@ namespace gold
 {
 
 Stringpool::Stringpool()
-  : string_set_(), strings_(), strtab_size_(0)
+  : string_set_(), strings_(), strtab_size_(0), next_index_(1)
 {
 }
 
@@ -55,12 +55,18 @@ Stringpool::Stringpool_hash::operator()(const char* s) const
 }
 
 // Add a string to the list of canonical strings.  Return a pointer to
-// the canonical string.
+// the canonical string.  If PKEY is not NULL, set *PKEY to the key.
 
 const char*
-Stringpool::add_string(const char* s)
+Stringpool::add_string(const char* s, Key* pkey)
 {
+  // The size we allocate for a new Stringdata.
   const size_t buffer_size = 1000;
+  // The amount we multiply the Stringdata index when calculating the
+  // key.
+  const size_t key_mult = 1024;
+  assert(key_mult >= buffer_size);
+
   size_t len = strlen(s);
 
   size_t alc;
@@ -81,7 +87,12 @@ Stringpool::add_string(const char* s)
 	{
 	  char* ret = psd->data + psd->len;
 	  memcpy(ret, s, len + 1);
+
+	  if (pkey != NULL)
+	    *pkey = psd->index * key_mult + psd->len;
+
 	  psd->len += len + 1;
+
 	  return ret;
 	}
     }
@@ -90,17 +101,24 @@ Stringpool::add_string(const char* s)
   psd->alc = alc - sizeof(Stringdata);
   memcpy(psd->data, s, len + 1);
   psd->len = len + 1;
+  psd->index = this->next_index_;
+  ++this->next_index_;
+
+  if (pkey != NULL)
+    *pkey = psd->index * key_mult;
+
   if (front)
     this->strings_.push_front(psd);
   else
     this->strings_.push_back(psd);
+
   return psd->data;
 }
 
 // Add a string to a string pool.
 
 const char*
-Stringpool::add(const char* s)
+Stringpool::add(const char* s, Key* pkey)
 {
   // FIXME: This will look up the entry twice in the hash table.  The
   // problem is that we can't insert S before we canonicalize it.  I
@@ -110,33 +128,48 @@ Stringpool::add(const char* s)
 
   String_set_type::const_iterator p = this->string_set_.find(s);
   if (p != this->string_set_.end())
-    return p->first;
+    {
+      if (pkey != NULL)
+	*pkey = p->second.first;
+      return p->first;
+    }
 
-  const char* ret = this->add_string(s);
-  std::pair<const char*, off_t> val(ret, 0);
+  Key k;
+  const char* ret = this->add_string(s, &k);
+
+  const off_t ozero = 0;
+  std::pair<const char*, Val> element(ret, std::make_pair(k, ozero));
   std::pair<String_set_type::iterator, bool> ins =
-    this->string_set_.insert(val);
+    this->string_set_.insert(element);
   assert(ins.second);
+
+  if (pkey != NULL)
+    *pkey = k;
+
   return ret;
 }
 
 // Add a prefix of a string to a string pool.
 
 const char*
-Stringpool::add(const char* s, size_t len)
+Stringpool::add(const char* s, size_t len, Key* pkey)
 {
   // FIXME: This implementation should be rewritten when we rewrite
   // the hash table to avoid copying.
   std::string st(s, len);
-  return this->add(st);
+  return this->add(st, pkey);
 }
 
 const char*
-Stringpool::find(const char* s) const
+Stringpool::find(const char* s, Key* pkey) const
 {
   String_set_type::const_iterator p = this->string_set_.find(s);
   if (p == this->string_set_.end())
     return NULL;
+
+  if (pkey != NULL)
+    *pkey = p->second.first;
+
   return p->first;
 }
 
@@ -206,14 +239,14 @@ Stringpool::set_string_offsets()
   for (size_t i = 0; i < count; ++i)
     {
       if (v[i]->first[0] == '\0')
-	v[i]->second = 0;
+	v[i]->second.second = 0;
       else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
-	v[i]->second = (v[i - 1]->second
-			+ strlen(v[i - 1]->first)
-			- strlen(v[i]->first));
+	v[i]->second.second = (v[i - 1]->second.second
+			       + strlen(v[i - 1]->first)
+			       - strlen(v[i]->first));
       else
 	{
-	  v[i]->second = offset;
+	  v[i]->second.second = offset;
 	  offset += strlen(v[i]->first) + 1;
 	}
     }
@@ -229,7 +262,7 @@ Stringpool::get_offset(const char* s) const
 {
   String_set_type::const_iterator p = this->string_set_.find(s);
   if (p != this->string_set_.end())
-    return p->second;
+    return p->second.second;
   abort();
 }
 
@@ -244,7 +277,7 @@ Stringpool::write(Output_file* of, off_t offset)
   for (String_set_type::const_iterator p = this->string_set_.begin();
        p != this->string_set_.end();
        ++p)
-    strcpy(view + p->second, p->first);
+    strcpy(view + p->second.second, p->first);
   of->write_output_view(offset, this->strtab_size_, viewu);
 }
 
diff --git a/gold/stringpool.h b/gold/stringpool.h
index 01c71a1355..ed549b4890 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -17,34 +17,42 @@ class Output_file;
 class Stringpool
 {
  public:
+  // The type of a key into the stringpool.  A key value will always
+  // be the same during any run of the linker.  The string pointers
+  // may change when using address space randomization.  We use key
+  // values in order to get repeatable runs when the value is inserted
+  // into an unordered hash table.  Zero is never a valid key.
+  typedef size_t Key;
+
   Stringpool();
 
   ~Stringpool();
 
   // Add a string to the pool.  This returns a canonical permanent
-  // pointer to the string.
+  // pointer to the string.  If PKEY is not NULL, this sets *PKEY to
+  // the key for the string.
   const char*
-  add(const char*);
+  add(const char*, Key* pkey);
 
   const char*
-  add(const std::string& s)
-  { return this->add(s.c_str()); }
+  add(const std::string& s, Key* pkey)
+  { return this->add(s.c_str(), pkey); }
 
   // Add the prefix of a string to the pool.
   const char*
-  add(const char *, size_t);
+  add(const char *, size_t, Key* pkey);
 
   // If a string is present, return the canonical string.  Otherwise,
-  // return NULL.
+  // return NULL.  If PKEY is not NULL, set *PKEY to the key.
   const char*
-  find(const char*) const;
+  find(const char*, Key* pkey) const;
 
   // Turn the stringpool into an ELF strtab: determine the offsets of
   // all the strings.
   void
   set_string_offsets();
 
-  // Get the offset of a string.
+  // Get the offset of a string in an ELF strtab.
   off_t
   get_offset(const char*) const;
 
@@ -72,13 +80,15 @@ class Stringpool
     size_t len;
     // Allocated size of buffer.
     size_t alc;
+    // Buffer index.
+    unsigned int index;
     // Buffer.
     char data[1];
   };
 
   // Copy a string into the buffers, returning a canonical string.
   const char*
-  add_string(const char*);
+  add_string(const char*, Key*);
 
   struct Stringpool_hash
   {
@@ -96,16 +106,19 @@ class Stringpool
   // Return whether s1 is a suffix of s2.
   static bool is_suffix(const char* s1, const char* s2);
 
-  // The hash table is a map from string names to offsets.  We only
-  // use the offsets if we turn this into an ELF strtab section.
+  // The hash table is a map from string names to a pair of Key and
+  // ELF strtab offsets.  We only use the offsets if we turn this into
+  // an ELF strtab section.
+
+  typedef std::pair<Key, off_t> Val;
 
 #ifdef HAVE_TR1_UNORDERED_SET
-  typedef Unordered_map<const char*, off_t, Stringpool_hash,
+  typedef Unordered_map<const char*, Val, Stringpool_hash,
 			Stringpool_eq,
-			std::allocator<std::pair<const char* const, off_t> >,
+			std::allocator<std::pair<const char* const, Val> >,
 			true> String_set_type;
 #else
-  typedef Unordered_map<const char*, off_t, Stringpool_hash,
+  typedef Unordered_map<const char*, Val, Stringpool_hash,
 			Stringpool_eq> String_set_type;
 #endif
 
@@ -118,9 +131,17 @@ class Stringpool
 	       String_set_type::iterator) const;
   };
 
+  // List of Stringdata structures.
+  typedef std::list<Stringdata*> Stringdata_list;
+
+  // Mapping from const char* to namepool entry.
   String_set_type string_set_;
-  std::list<Stringdata*> strings_;
+  // List of buffers.
+  Stringdata_list strings_;
+  // Size of ELF strtab.
   off_t strtab_size_;
+  // Next Stringdata index.
+  unsigned int next_index_;
 };
 
 } // End namespace gold.
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 091144a75c..054e07fba5 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -174,8 +174,7 @@ Symbol_table::~Symbol_table()
 size_t
 Symbol_table::Symbol_table_hash::operator()(const Symbol_table_key& key) const
 {
-  return (reinterpret_cast<size_t>(key.first)
-	  ^ reinterpret_cast<size_t>(key.second));
+  return key.first ^ key.second;
 }
 
 // The symbol table key equality function.  This is only called with
@@ -216,17 +215,20 @@ Symbol_table::resolve_forwards(Symbol* from) const
 Symbol*
 Symbol_table::lookup(const char* name, const char* version) const
 {
-  name = this->namepool_.find(name);
+  Stringpool::Key name_key;
+  name = this->namepool_.find(name, &name_key);
   if (name == NULL)
     return NULL;
+
+  Stringpool::Key version_key = 0;
   if (version != NULL)
     {
-      version = this->namepool_.find(version);
+      version = this->namepool_.find(version, &version_key);
       if (version == NULL)
 	return NULL;
     }
 
-  Symbol_table_key key(name, version);
+  Symbol_table_key key(name_key, version_key);
   Symbol_table::Symbol_table_type::const_iterator p = this->table_.find(key);
   if (p == this->table_.end())
     return NULL;
@@ -282,19 +284,24 @@ template<int size, bool big_endian>
 Symbol*
 Symbol_table::add_from_object(Object* object,
 			      const char *name,
-			      const char *version, bool def,
+			      Stringpool::Key name_key,
+			      const char *version,
+			      Stringpool::Key version_key,
+			      bool def,
 			      const elfcpp::Sym<size, big_endian>& sym)
 {
   Symbol* const snull = NULL;
   std::pair<typename Symbol_table_type::iterator, bool> ins =
-    this->table_.insert(std::make_pair(std::make_pair(name, version), snull));
+    this->table_.insert(std::make_pair(std::make_pair(name_key, version_key),
+				       snull));
 
   std::pair<typename Symbol_table_type::iterator, bool> insdef =
     std::make_pair(this->table_.end(), false);
   if (def)
     {
-      const char* const vnull = NULL;
-      insdef = this->table_.insert(std::make_pair(std::make_pair(name, vnull),
+      const Stringpool::Key vnull_key = 0;
+      insdef = this->table_.insert(std::make_pair(std::make_pair(name_key,
+								 vnull_key),
 						  snull));
     }
 
@@ -379,7 +386,8 @@ Symbol_table::add_from_object(Object* object,
 		    {
 		      this->table_.erase(insdef.first);
 		      // Inserting insdef invalidated ins.
-		      this->table_.erase(std::make_pair(name, version));
+		      this->table_.erase(std::make_pair(name_key,
+							version_key));
 		    }
 		  return NULL;
 		}
@@ -477,12 +485,16 @@ Symbol_table::add_from_object(
       Symbol* res;
       if (ver == NULL)
 	{
-	  name = this->namepool_.add(name);
-	  res = this->add_from_object(object, name, NULL, false, *psym);
+	  Stringpool::Key name_key;
+	  name = this->namepool_.add(name, &name_key);
+	  res = this->add_from_object(object, name, name_key, NULL, 0,
+				      false, *psym);
 	}
       else
 	{
-	  name = this->namepool_.add(name, ver - name);
+	  Stringpool::Key name_key;
+	  name = this->namepool_.add(name, ver - name, &name_key);
+
 	  bool def = false;
 	  ++ver;
 	  if (*ver == '@')
@@ -490,8 +502,12 @@ Symbol_table::add_from_object(
 	      def = true;
 	      ++ver;
 	    }
-	  ver = this->namepool_.add(ver);
-	  res = this->add_from_object(object, name, ver, def, *psym);
+
+	  Stringpool::Key ver_key;
+	  ver = this->namepool_.add(ver, &ver_key);
+
+	  res = this->add_from_object(object, name, name_key, ver, ver_key,
+				      def, *psym);
 	}
 
       *sympointers++ = res;
@@ -525,12 +541,13 @@ Symbol_table::define_special_symbol(Target* target, const char* name,
   else
     {
       // Canonicalize NAME.
-      name = this->namepool_.add(name);
+      Stringpool::Key name_key;
+      name = this->namepool_.add(name, &name_key);
 
       Symbol* const snull = NULL;
-      const char* const vnull = NULL;
+      const Stringpool::Key ver_key = 0;
       std::pair<typename Symbol_table_type::iterator, bool> ins =
-	this->table_.insert(std::make_pair(std::make_pair(name, vnull),
+	this->table_.insert(std::make_pair(std::make_pair(name_key, ver_key),
 					   snull));
 
       if (!ins.second)
@@ -937,7 +954,7 @@ Symbol_table::sized_finalize(off_t off, Stringpool* pool)
 	}
 
       sym->set_value(value);
-      pool->add(sym->name());
+      pool->add(sym->name(), NULL);
       ++count;
       off += sym_size;
       ++p;
diff --git a/gold/symtab.h b/gold/symtab.h
index f544e0664d..65898990c8 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -683,7 +683,7 @@ class Symbol_table
   // Canonicalize a symbol name for use in the hash table.
   const char*
   canonicalize_name(const char* name)
-  { return this->namepool_.add(name); }
+  { return this->namepool_.add(name, NULL); }
 
   // Possibly issue a warning for a reference to SYM at LOCATION which
   // is in OBJ.
@@ -718,9 +718,9 @@ class Symbol_table
   // Add a symbol.
   template<int size, bool big_endian>
   Symbol*
-  add_from_object(Object*, const char *name,
-		  const char *version, bool def,
-		  const elfcpp::Sym<size, big_endian>& sym);
+  add_from_object(Object*, const char *name, Stringpool::Key name_key,
+		  const char *version, Stringpool::Key version_key,
+		  bool def, const elfcpp::Sym<size, big_endian>& sym);
 
   // Resolve symbols.
   template<int size, bool big_endian>
@@ -783,7 +783,7 @@ class Symbol_table
 
   // The type of the symbol hash table.
 
-  typedef std::pair<const char*, const char*> Symbol_table_key;
+  typedef std::pair<Stringpool::Key, Stringpool::Key> Symbol_table_key;
 
   struct Symbol_table_hash
   {