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

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

By using Unordered_set for storing got entries, symbols that have LA25 stubs or .MIPS.stubs, gold for Mips produced different got table order, .Mips.stubs order and LA25 stubs order for the same input files.

Regards,
Vladimir

Changelog -

    * mips.cc (Mips_got_entry::hash): Delete.
    (class Mips_got_entry_hash): Likewise.
    (struct Got_page_entry_hash): Likewise.
    (Mips_got_entry::equals): Change to compare_less.
    (class Mips_got_entry_eq): Change to Mips_got_entry_compare_less.
    (struct Got_page_entry_eq): Change to Got_page_entry_compare_less.
    (Got_entry_set): Change from Unordered_set to std::set.
    (Got_page_entry_set): Likewise.
    (global_got_symbols_): Likewise.
    (Mips_output_data_mips_stubs::symbols_): Likewise.
    (Mips_output_data_la25_stub::symbols_): Likewise.
    (Mips_got_info::record_got_entry): Don't use find before insert.
    (Mips_got_info::record_got_page_entry): Likewise.

Patch - 

 mips.cc |  133 +++++++++++++++++++++++-----------------------------------------
 1 file changed, 48 insertions(+), 85 deletions(-)

diff --git a/gold/mips.cc b/gold/mips.cc
index 6cfe924..561995e 100644
--- a/gold/mips.cc
+++ b/gold/mips.cc
@@ -420,38 +420,24 @@ class Mips_got_entry
   is_for_global_symbol() const
   { return this->symndx_ == -1U; }
 
-  // Return the hash of this entry.
-  size_t
-  hash() const
-  {
-    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 whether this entry is equal to OTHER.
   bool
-  equals(Mips_got_entry<size, big_endian>* other) const
+  compare_less(Mips_got_entry<size, big_endian>* other) const
   {
-    if (this->symndx_ != other->symndx_
-        || this->tls_type_ != other->tls_type_)
-      return false;
+    if (this->symndx_ != other->symndx_)
+      return this->symndx_ < other->symndx_;
+    if (this->tls_type_ != other->tls_type_)
+      return this->tls_type_ < other->tls_type_;
     if (this->tls_type_ == GOT_TLS_LDM)
-      return true;
+      return false;
+
     if (this->symndx_ != -1U)
-      return (this->object() == other->object()
-              && this->d.addend == other->d.addend);
-    else
-      return this->d.sym == other->d.sym;
+    {
+      if (this->object() != other->object())
+        return this->object() < other->object();
+
+      return this->d.addend < other->d.addend;
+    }
+    return this->d.sym < other->d.sym;
   }
 
   // Return input object that needs this GOT entry.
@@ -526,27 +512,16 @@ class Mips_got_entry
   unsigned int shndx_;
 };
 
-// Hash for Mips_got_entry.
-
-template<int size, bool big_endian>
-class Mips_got_entry_hash
-{
- public:
-  size_t
-  operator()(Mips_got_entry<size, big_endian>* entry) const
-  { return entry->hash(); }
-};
-
 // Equality for Mips_got_entry.
 
 template<int size, bool big_endian>
-class Mips_got_entry_eq
+class Mips_got_entry_compare_less
 {
  public:
   bool
   operator()(Mips_got_entry<size, big_endian>* e1,
              Mips_got_entry<size, big_endian>* e2) const
-  { return e1->equals(e2); }
+  { return e1->compare_less(e2); }
 };
 
 // Got_page_range.  This class describes a range of addends: [MIN_ADDEND,
@@ -592,23 +567,17 @@ struct Got_page_entry
   unsigned int num_pages;
 };
 
-// Hash for Got_page_entry.
+// Compare less for Got_page_entry.
 
-struct Got_page_entry_hash
-{
-  size_t
-  operator()(Got_page_entry* entry) const
-  { return reinterpret_cast<uintptr_t>(entry->object) + entry->symndx; }
-};
-
-// Equality for Got_page_entry.
-
-struct Got_page_entry_eq
+struct Got_page_entry_compare_less
 {
   bool
   operator()(Got_page_entry* entry1, Got_page_entry* entry2) const
   {
-    return entry1->object == entry2->object && entry1->symndx == entry2->symndx;
+    if (entry1->object != entry2->object)
+      return entry1->object < entry2->object;
+
+    return entry1->symndx < entry2->symndx;
   }
 };
 
@@ -622,14 +591,13 @@ class Mips_got_info
     Reloc_section;
   typedef Unordered_map<unsigned int, unsigned int> Got_page_offsets;
 
-  // Unordered set of GOT entries.
-  typedef Unordered_set<Mips_got_entry<size, big_endian>*,
-      Mips_got_entry_hash<size, big_endian>,
-      Mips_got_entry_eq<size, big_endian> > Got_entry_set;
+  // Ordered set of GOT entries.
+  typedef std::set<Mips_got_entry<size, big_endian>*,
+      Mips_got_entry_compare_less<size, big_endian> > Got_entry_set;
 
-  // Unordered set of GOT page entries.
-  typedef Unordered_set<Got_page_entry*,
-      Got_page_entry_hash, Got_page_entry_eq> Got_page_entry_set;
+  // Ordered set of GOT page entries.
+  typedef std::set<Got_page_entry*,
+      Got_page_entry_compare_less> Got_page_entry_set;
 
  public:
   Mips_got_info()
@@ -809,7 +777,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>*>&
+  std::set<Mips_symbol<size>*>&
   global_got_symbols()
   { return this->global_got_symbols_; }
 
@@ -864,10 +832,10 @@ 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_;
-  // A hash table holding GOT entries.
+  std::set<Mips_symbol<size>*> global_got_symbols_;
+  // A set holding GOT entries.
   Got_entry_set got_entries_;
-  // A hash table of GOT page entries.
+  // A set of GOT page entries.
   Got_page_entry_set got_page_entries_;
   // The offset of first GOT page entry for this GOT.
   unsigned int got_page_offset_start_;
@@ -2251,7 +2219,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::set<Mips_symbol<size>*> symbols_;
 };
 
 // A class to handle the PLT data.
@@ -2573,7 +2541,7 @@ class Mips_output_data_mips_stubs : public Output_section_data
   do_write(Output_file*);
 
   // .MIPS.stubs symbols
-  Unordered_set<Mips_symbol<size>*> symbols_;
+  std::set<Mips_symbol<size>*> symbols_;
   // Number of entries in dynamic symbol table.
   unsigned int dynsym_count_;
   // Whether the stub offsets are set.
@@ -4810,16 +4778,12 @@ Mips_got_info<size, big_endian>::record_got_entry(
     Mips_got_entry<size, big_endian>* entry,
     Mips_relobj<size, big_endian>* object)
 {
-  if (this->got_entries_.find(entry) == this->got_entries_.end())
-    this->got_entries_.insert(entry);
+  this->got_entries_.insert(entry);
 
   // Create the GOT entry for the OBJECT's GOT.
   Mips_got_info<size, big_endian>* g = object->get_or_create_got_info();
-  Mips_got_entry<size, big_endian>* entry2 =
-    new Mips_got_entry<size, big_endian>(*entry);
 
-  if (g->got_entries_.find(entry2) == g->got_entries_.end())
-    g->got_entries_.insert(entry2);
+  g->got_entries_.insert(entry);
 }
 
 // Record that OBJECT has a page relocation against symbol SYMNDX and
@@ -4838,13 +4802,12 @@ Mips_got_info<size, big_endian>::record_got_page_entry(
 
   // Find the Got_page_entry for this symbol.
   Got_page_entry* entry = new Got_page_entry(object, symndx);
-  typename Got_page_entry_set::iterator it =
-    this->got_page_entries_.find(entry);
-  if (it != this->got_page_entries_.end())
-    entry = *it;
-  else
+  std::pair<Got_page_entry_set::iterator, bool> new_entry =
     this->got_page_entries_.insert(entry);
 
+  if (!new_entry.second)
+    entry = *new_entry.first;
+
   // Add the same entry to the OBJECT's GOT.
   Got_page_entry* entry2 = NULL;
   Mips_got_info<size, big_endian>* g2 = object->get_or_create_got_info();
@@ -5086,7 +5049,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 std::set<Mips_symbol<size>*>::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -5265,7 +5228,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 std::set<Mips_symbol<size>*>::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -5634,7 +5597,7 @@ Mips_output_data_got<size, big_endian>::do_write(Output_file* of)
   this->got_view_ = oview;
 
   // Write lazy stub addresses.
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->master_got_info_->global_got_symbols().begin();
        p != this->master_got_info_->global_got_symbols().end();
        ++p)
@@ -5651,7 +5614,7 @@ Mips_output_data_got<size, big_endian>::do_write(Output_file* of)
     }
 
   // Add +1 to GGA_NONE nonzero MIPS16 and microMIPS entries.
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->master_got_info_->global_got_symbols().begin();
        p != this->master_got_info_->global_got_symbols().end();
        ++p)
@@ -6104,7 +6067,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::set<Mips_symbol<size>*>::iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p)
@@ -6903,7 +6866,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 std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p, offset += stub_size)
@@ -6918,7 +6881,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 std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;
@@ -6942,7 +6905,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 std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;