[PATCH][GOLD] Make string offset assignment independent of implementation of unordered map elements order.
Doug Kwan (關振德)
dougkwan@google.com
Mon Mar 15 22:17:00 GMT 2010
Hi Ian,
Here is an updated patch. We may get incorrect offset if
Stringpool_template::set_no_zero_null is set after the first offset is
assigned. Currently set_no_zero_null is only used by merged string
section and is called before any strings are inserted. So it should
be okay. The patch was tested on x86_64 and ARM Linux.
-Doug
2010-03-15 Doug Kwan <dougkwan@google.com>
* stringpool.cc (Stringpool_template::Stringpool_template): Initialize
offset_.
(Stringpool_template::new_key_offset): New method.
(Stringpool_template::add_string): Assign offsets when adding new
strings.
(Stringpool_template::set_string_offsets): Do not set string offsets
when not optimizing.
* 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.
(Stringpool_template::new_key_offset): New method declaration.
(Stringpool_template::offset_): New data member.
2010/3/14 Doug Kwan (關振德) <dougkwan@google.com>:
> 2010/3/14 Ian Lance Taylor <iant@google.com>:
>
>> The stringpool code is pretty time intensive for the linker, so I'm
>> not thrilled about walking the hash table twice. When not optimizing,
>> I think we can actually calculate key_to_offset_ as we add strings to
>> the table. That's even better, since we can eliminate the hash table
>> walk. How does that sound?
>
> That's better. I can submit another patch.
>
> -Doug
>
-------------- 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 15 Mar 2010 20:30:23 -0000
@@ -36,7 +36,8 @@ namespace gold
template<typename Stringpool_char>
Stringpool_template<Stringpool_char>::Stringpool_template()
: string_set_(), key_to_offset_(), strings_(), strtab_size_(0),
- zero_null_(true), optimize_(false)
+ zero_null_(true), optimize_(false),
+ offset_(zero_null_ ? sizeof(Stringpool_char) : 0)
{
if (parameters->options_valid() && parameters->options().optimize() >= 2)
this->optimize_ = true;
@@ -232,6 +233,24 @@ Stringpool_template<Stringpool_char>::ad
return this->add_with_length(s, string_length(s), copy, pkey);
}
+// Add a new key offset entry.
+
+template<typename Stringpool_char>
+void
+Stringpool_template<Stringpool_char>::new_key_offset(const Stringpool_char* s,
+ size_t length)
+{
+ section_offset_type offset;
+ if (this->zero_null_ && s[0] == 0)
+ offset = 0;
+ else
+ {
+ offset = this->offset_;
+ this->offset_ += (length + 1) * sizeof(Stringpool_char);
+ }
+ this->key_to_offset_.push_back(offset);
+}
+
template<typename Stringpool_char>
const Stringpool_char*
Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
@@ -259,7 +278,7 @@ Stringpool_template<Stringpool_char>::ad
{
// We just added the string. The key value has now been
// used.
- this->key_to_offset_.push_back(0);
+ this->new_key_offset(s, length);
}
else
{
@@ -285,7 +304,7 @@ Stringpool_template<Stringpool_char>::ad
return p->first.string;
}
- this->key_to_offset_.push_back(0);
+ this->new_key_offset(s, length);
hk.string = this->add_string(s, length);
// The contents of the string stay the same, so we don't need to
@@ -390,19 +409,8 @@ Stringpool_template<Stringpool_char>::se
// take the time to sort when the user asks for heavy optimization.
if (!this->optimize_)
{
- 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];
- if (this->zero_null_ && curr->first.string[0] == 0)
- *poff = 0;
- else
- {
- *poff = offset;
- offset += (curr->first.length + 1) * charsize;
- }
- }
+ // If we are not optimizing, the offsets are already assigned.
+ offset = this->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 15 Mar 2010 20:30:23 -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_;
};
@@ -282,6 +285,10 @@ class Stringpool_template
char data[1];
};
+ // Add a new key offset entry.
+ void
+ new_key_offset(const Stringpool_char*, size_t);
+
// Copy a string into the buffers, returning a canonical string.
const Stringpool_char*
add_string(const Stringpool_char*, size_t);
@@ -372,6 +379,8 @@ class Stringpool_template
bool zero_null_;
// Whether to optimize the string table.
bool optimize_;
+ // offset of the next string.
+ section_offset_type offset_;
};
// The most common type of Stringpool.
More information about the Binutils
mailing list