[PATCH v3] gold: Fix non-deterministic behaviour of Mips gold.

[Vladimir Radosavljevic <Vladimir dot Radosavljevic at imgtec dot com>]

I have made a mistake by changing Unoredered_set to std::set. I have fixed this problem by changing hash algorithm for GOT entries,
by adding hash algorithm for symbols that have global GOT entry and for .MIPS.stubs symbols, and by changing type for symbols that have LA25 stubs to std::vector.

Regards,
Vladimir

ChangeLog -

    * mips.cc (Mips_got_entry::hash): Change hash algorithm.
    (class Mips_symbol_hash): New class.
    (Mips_got_info::Global_got_entry_set): New type.
    (Mips_got_info::global_got_symbols): Change return type to
    Global_got_entry_set.
    (Mips_got_info::global_got_symbols_): Change type to
    Global_got_entry_set.
    (Mips_symbol::hash): New method.
    (Mips_output_data_la25_stub::symbols_): Change type to std::vector.
    (Mips_output_data_mips_stubs::Mips_stubs_entry_set): New type.
    (Mips_output_data_mips_stubs::symbols_): Change type to
    Mips_stubs_entry_set.
    (Mips_got_info::add_reloc_only_entries): Change type of iterator
    to Global_got_entry_set.
    (Mips_got_info::count_got_symbols): Likewise.
    (Mips_output_data_la25_stub::create_la25_stub): Use push_back
    for adding entries to symbols_.
    (Mips_output_data_la25_stub::do_write): Change type of iterator
    to std::vector.
    (Mips_output_data_mips_stubs::set_lazy_stub_offsets): Change type
    of iterator to Mips_stubs_entry_set.
    (Mips_output_data_mips_stubs::set_needs_dynsym_value): Likewise.
    (Mips_output_data_mips_stubs::do_write): Likewise.

diff --git a/gold/mips.cc b/gold/mips.cc
index ffaad45..8906cb2 100644
--- a/gold/mips.cc
+++ b/gold/mips.cc
@@ -459,16 +459,13 @@ class Mips_got_entry
   {
     if (this->tls_type_ == GOT_TLS_LDM)
       return this->symndx_ + (1 << 18);
+
     if (this->symndx_ != -1U)
-      {
-        uintptr_t object_id = reinterpret_cast<uintptr_t>(this->object());
-        return this->symndx_ + object_id + this->d.addend;
-      }
-    else
-      {
-        uintptr_t sym_id = reinterpret_cast<uintptr_t>(this->d.sym);
-        return this->symndx_ + sym_id;
-      }
+      return this->symndx_
+          ^ gold::string_hash<char>(this->object()->name().c_str())
+          ^ this->d.addend;
+
+    return this->symndx_ ^ gold::string_hash<char>(this->d.sym->name());
   }
 
   // Return whether this entry is equal to OTHER.
@@ -590,6 +587,17 @@ class Mips_got_entry_eq
   { return e1->equals(e2); }
 };
 
+// Hash for Mips_symbol.
+
+template<int size>
+class Mips_symbol_hash
+{
+ public:
+  size_t
+  operator()(Mips_symbol<size>* sym) const
+  { return sym->hash(); }
+};
+
 // Got_page_range.  This class describes a range of addends: [MIN_ADDEND,
 // MAX_ADDEND].  The instances form a non-overlapping list that is sorted by
 // increasing MIN_ADDEND.
@@ -672,6 +680,10 @@ class Mips_got_info
   typedef Unordered_set<Got_page_entry*,
       Got_page_entry_hash, Got_page_entry_eq> Got_page_entry_set;
 
+  // Unordered set of global GOT entries.
+  typedef Unordered_set<Mips_symbol<size>*,
+      Mips_symbol_hash<size> >  Global_got_entry_set;
+
  public:
   Mips_got_info()
     : local_gotno_(0), page_gotno_(0), global_gotno_(0), reloc_only_gotno_(0),
@@ -851,7 +863,7 @@ class Mips_got_info
   set_tls_ldm_offset(unsigned int tls_ldm_offset)
   { this->tls_ldm_offset_ = tls_ldm_offset; }
 
-  Unordered_set<Mips_symbol<size>*>&
+  Global_got_entry_set&
   global_got_symbols()
   { return this->global_got_symbols_; }
 
@@ -906,7 +918,7 @@ class Mips_got_info
   // The offset of TLS LDM entry for this GOT.
   unsigned int tls_ldm_offset_;
   // All symbols that have global GOT entry.
-  Unordered_set<Mips_symbol<size>*> global_got_symbols_;
+  Global_got_entry_set global_got_symbols_;
   // A hash table holding GOT entries.
   Got_entry_set got_entries_;
   // A hash table of GOT page entries.
@@ -1284,6 +1296,13 @@ class Mips_symbol : public Sized_symbol<size>
   set_applied_secondary_got_fixup()
   { this->applied_secondary_got_fixup_ = true; }
 
+  // Return the hash of this symbol.
+  size_t
+  hash() const
+  {
+    return gold::string_hash<char>(this->name());
+  }
+
  private:
   // Whether the symbol needs MIPS16 fn_stub.  This is true if this symbol
   // appears in any relocs other than a 16 bit call.
@@ -2302,7 +2321,7 @@ class Mips_output_data_la25_stub : public Output_section_data
   do_write(Output_file*);
 
   // Symbols that have LA25 stubs.
-  Unordered_set<Mips_symbol<size>*> symbols_;
+  std::vector<Mips_symbol<size>*> symbols_;
 };
 
 // MIPS-specific relocation writer.
@@ -2577,6 +2596,10 @@ class Mips_output_data_mips_stubs : public Output_section_data
 {
   typedef typename elfcpp::Elf_types<size>::Elf_Addr Mips_address;
 
+  // Unordered set of .MIPS.stubs entries.
+  typedef Unordered_set<Mips_symbol<size>*,
+      Mips_symbol_hash<size> > Mips_stubs_entry_set;
+
  public:
    Mips_output_data_mips_stubs(Target_mips<size, big_endian>* target)
      : Output_section_data(size == 32 ? 4 : 8), symbols_(), dynsym_count_(-1U),
@@ -2683,7 +2706,7 @@ class Mips_output_data_mips_stubs : public Output_section_data
   do_write(Output_file*);
 
   // .MIPS.stubs symbols
-  Unordered_set<Mips_symbol<size>*> symbols_;
+  Mips_stubs_entry_set symbols_;
   // Number of entries in dynamic symbol table.
   unsigned int dynsym_count_;
   // Whether the stub offsets are set.
@@ -5573,7 +5596,7 @@ void
 Mips_got_info<size, big_endian>::add_reloc_only_entries(
     Mips_output_data_got<size, big_endian>* got)
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename Global_got_entry_set::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -5757,7 +5780,7 @@ template<int size, bool big_endian>
 void
 Mips_got_info<size, big_endian>::count_got_symbols(Symbol_table* symtab)
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename Global_got_entry_set::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -6635,7 +6658,7 @@ Mips_output_data_la25_stub<size, big_endian>::create_la25_stub(
   if (!gsym->has_la25_stub())
     {
       gsym->set_la25_stub_offset(this->symbols_.size() * 16);
-      this->symbols_.insert(gsym);
+      this->symbols_.push_back(gsym);
       this->create_stub_symbol(gsym, symtab, target, 16);
     }
 }
@@ -6679,7 +6702,7 @@ Mips_output_data_la25_stub<size, big_endian>::do_write(Output_file* of)
     convert_to_section_size_type(this->data_size());
   unsigned char* const oview = of->get_output_view(offset, oview_size);
 
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::vector<Mips_symbol<size>*>::iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p)
@@ -7478,7 +7501,7 @@ Mips_output_data_mips_stubs<size, big_endian>::set_lazy_stub_offsets()
 
   unsigned int stub_size = this->stub_size();
   unsigned int offset = 0;
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename Mips_stubs_entry_set::const_iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p, offset += stub_size)
@@ -7493,7 +7516,7 @@ template<int size, bool big_endian>
 void
 Mips_output_data_mips_stubs<size, big_endian>::set_needs_dynsym_value()
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename Mips_stubs_entry_set::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;
@@ -7517,7 +7540,7 @@ Mips_output_data_mips_stubs<size, big_endian>::do_write(Output_file* of)
   bool big_stub = this->dynsym_count_ > 0x10000;
 
   unsigned char* pov = oview;
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename Mips_stubs_entry_set::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;