[PATCH][GOLD] Make string offset assignment independent of implementation of unordered map elements order.

[Doug Kwan (關振德)]

Hi,

    Currently Stringpool_template::set_string_offsets transverse an
unordered map and assign string offsets for unoptimized string pools.
The ordered of elements in an unordered map depends on many things
like the version of STL used and the with of size_t.   This leads to
different outputs generated from the same input.  This patch fixes
this problem by assigning strings offsets in the order strings are
inserted into a string pool.    The patch was tested on both x86_64
Linux and ARM Linux natively.

-Doug

2010-03-13  Doug Kwan  <dougkwan@google.com>

        * stringpool.cc (Stringpool_template::set_string_offsets): Set
        string offsets in the order strings are inserted.
        * stringpool.h (Chunked_vector::Chunked_vector): Initialize data
        member size_.
        (Chunked_vector::clear): Clear size_.
        (Chunked_vector::reserve): Call reserve method of all Element_vectors.
        (Chunked_vector::size): Return size_.
        (Chunked_vector::push_back): Use size_ to find insert position.
        (Chunked_vector::size_): New data member.
-------------- next part --------------
Index: gold/stringpool.cc
===================================================================
RCS file: /cvs/src/src/gold/stringpool.cc,v
retrieving revision 1.30
diff -u -u -p -r1.30 stringpool.cc
--- gold/stringpool.cc	21 Oct 2009 08:08:41 -0000	1.30
+++ gold/stringpool.cc	13 Mar 2010 22:49:25 -0000
@@ -390,19 +390,47 @@ Stringpool_template<Stringpool_char>::se
   // take the time to sort when the user asks for heavy optimization.
   if (!this->optimize_)
     {
+      // We do not want offset assignment to depend on implementation of
+      // unordered_map.  So we go over the keys twice.  We first compute
+      // the sizes of strings.  Then we assign offests in the order strings
+      // are inserted.
+      size_t key_count = this->key_to_offset_.size();
+      gold_assert(this->string_set_.size() == key_count);
+      const section_offset_type no_size = 0;
+      const section_offset_type zero_null_size = -1;
+      std::vector<section_offset_type> key_to_size(key_count, no_size);
+
       for (typename String_set_type::iterator curr = this->string_set_.begin();
            curr != this->string_set_.end();
            curr++)
         {
-	  section_offset_type* poff = &this->key_to_offset_[curr->second - 1];
+	  section_offset_type size;
           if (this->zero_null_ && curr->first.string[0] == 0)
-            *poff = 0;
+            size = zero_null_size;
           else
             {
-              *poff = offset;
-              offset += (curr->first.length + 1) * charsize;
+	      size = (curr->first.length + 1) * charsize;
+	      gold_assert(size > 0);
             }
+	  key_to_size[curr->second - 1 ] = size;
         }
+
+      for (size_t i = 0; i < key_count; ++i)
+	{
+	  section_offset_type string_size = key_to_size[i];
+	  section_offset_type string_offset;
+	  if (string_size > 0)
+	    {
+	      string_offset = offset;
+	      offset += string_size;
+	    }
+	  else
+	    {
+	      gold_assert(string_size == zero_null_size);
+	      string_offset = 0;
+	    }
+	  this->key_to_offset_[i] = string_offset;
+	}
     }
   else
     {
Index: gold/stringpool.h
===================================================================
RCS file: /cvs/src/src/gold/stringpool.h,v
retrieving revision 1.23
diff -u -u -p -r1.23 stringpool.h
--- gold/stringpool.h	23 Jun 2009 07:04:10 -0000	1.23
+++ gold/stringpool.h	13 Mar 2010 22:49:25 -0000
@@ -77,48 +77,50 @@ class Chunked_vector
 {
  public:
   Chunked_vector()
-    : chunks_()
+    : chunks_(), size_(0)
   { }
 
   // Clear the elements.
   void
   clear()
-  { this->chunks_.clear(); }
+  {
+    this->chunks_.clear();
+    this->size_ = 0;
+  }
 
   // Reserve elements.
   void
   reserve(unsigned int n)
   {
-    n += chunk_size - 1;
-    while (n >= chunk_size)
+    if (n > this->chunks_.size() * chunk_size)
       {
-	this->chunks_.push_back(Element_vector());
-	this->chunks_.back().reserve(chunk_size);
-	n -= chunk_size;
+	this->chunks_.resize((n + chunk_size - 1) / chunk_size);
+	// We need to call reserve() of all chunks since changing
+	// this->chunks_ casues Element_vectors to be copied.  The
+	// reserved capacity of an Element_vector may be lost in copying.
+	for (size_t i = 0; i < this->chunks_.size(); ++i)
+	  this->chunks_[i].reserve(chunk_size);
       }
   }
 
   // Get the number of elements.
   size_t
   size() const
-  {
-    if (this->chunks_.empty())
-      return 0;
-    else
-      return ((this->chunks_.size() - 1) * chunk_size
-	      + this->chunks_.back().size());
-  }
+  { return this->size_; }
 
   // Push a new element on the back of the vector.
   void
   push_back(const Element& element)
   {
-    if (this->chunks_.empty() || this->chunks_.back().size() == chunk_size)
+    size_t chunk_index = this->size_ / chunk_size;
+    if (chunk_index >= this->chunks_.size())
       {
 	this->chunks_.push_back(Element_vector());
 	this->chunks_.back().reserve(chunk_size);
+	gold_assert(chunk_index < this->chunks_.size());
       }
-    this->chunks_.back().push_back(element);
+    this->chunks_[chunk_index].push_back(element);
+    this->size_++;
   }
 
   // Return a reference to an entry in the vector.
@@ -137,6 +139,7 @@ class Chunked_vector
   typedef std::vector<Element_vector> Chunk_vector;
 
   Chunk_vector chunks_;
+  size_t size_;
 };