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

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

[Vladimir Radosavljevic]

[-- Attachment #1: Type: text/plain, Size: 1519 bytes --]

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.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fix-non-deterministic-behaviour.patch --]
[-- Type: text/x-patch; name="fix-non-deterministic-behaviour.patch", Size: 6476 bytes --]

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;

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

[Cary Coutant]

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

     if (this->symndx_ != -1U)
+      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());

The long expression needs parentheses, and the ^ operator should line
up with the term above it. But I'd suggest something like this
instead:

     size_t ret = this->symndx_ ^ gold::string_hash<char>(this->d.sym->name());
     if (this->symndx_ != -1U)
       ret ^= this->d.addend;
     return ret;

This hash strategy might produce more collisions than you would like,
as small symndx values may cancel out small addends. One approach
would be to shift one or more terms so cancellations are less likely
(see Reloc_stub::hash_value() in aarch64.cc, for example). Another
would be to use iterative_hash() from libiberty.

+  typedef Unordered_set<Mips_symbol<size>*,
+      Mips_symbol_hash<size> >  Global_got_entry_set;

This should be indented to line up. Either of the following would be OK:

   typedef Unordered_set<Mips_symbol<size>*,
                         Mips_symbol_hash<size> >  Global_got_entry_set;

(Second line aligns with "Mips_symbol" above.)

   typedef Unordered_set<Mips_symbol<size>*, Mips_symbol_hash<size> >
       Global_got_entry_set;

(Indented four spaces.)

+  // Unordered set of .MIPS.stubs entries.
+  typedef Unordered_set<Mips_symbol<size>*,
+      Mips_symbol_hash<size> > Mips_stubs_entry_set;

Likewise.

-cary

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

[Vladimir Radosavljevic]

Thanks for review.

> This hash strategy might produce more collisions than you would like,
> as small symndx values may cancel out small addends. One approach
> would be to shift one or more terms so cancellations are less likely
> (see Reloc_stub::hash_value() in aarch64.cc, for example). Another
> would be to use iterative_hash() from libiberty.

I could use hash algorithm like in Reloc_stub::hash_value(), but what do you think about using FNV-1a hash algorithm ?
It would be look like this:

+    size_t name_hash_value = gold::string_hash<char>(
+        (this->symndx_ != -1U)
+         ? this->d.object->name().c_str()
+         : this->d.sym->name());
+
+    uint64_t h = 14695981039346656037ULL; // FNV offset basis.
+    uint64_t prime = 1099511628211ULL;
+    h = (h ^ static_cast<uint64_t>(name_hash_value)) * prime;
+    h = (h ^ static_cast<uint64_t>(this->symndx_)) * prime;
+    h = (h ^ static_cast<uint64_t>(this->addend_)) * prime;
+    return h;

If you are ok with this, do I need to add case for sizeof(size_t) == 4 ?

Regards,
Vladimir

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

[Cary Coutant]

> I could use hash algorithm like in Reloc_stub::hash_value(), but what do you think about using FNV-1a hash algorithm ?
> It would be look like this:
>
> +    size_t name_hash_value = gold::string_hash<char>(
> +        (this->symndx_ != -1U)
> +         ? this->d.object->name().c_str()
> +         : this->d.sym->name());
> +
> +    uint64_t h = 14695981039346656037ULL; // FNV offset basis.
> +    uint64_t prime = 1099511628211ULL;
> +    h = (h ^ static_cast<uint64_t>(name_hash_value)) * prime;
> +    h = (h ^ static_cast<uint64_t>(this->symndx_)) * prime;
> +    h = (h ^ static_cast<uint64_t>(this->addend_)) * prime;
> +    return h;

I think you could get away without that last multiplication.

This is clearly a much better hash than the simple XOR, but adds some
cost to the hash computation. I think libiberty's iterative_hash() is
less expensive and nearly as effective, though.

One or two strategically placed shifts would make the simple XOR
strategy more effective (though not as effective as the more robust
alternatives) at almost no extra cost in hash computation. I'll leave
it to your judgement (or measurement) whether improvement in hash
lookup justifies extra cost in hash computation.

-cary