aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@google.com>2006-11-07 04:40:46 +0000
committerIan Lance Taylor <iant@google.com>2006-11-07 04:40:46 +0000
commitf0641a0b382db7403f04fab3d4e8fac25a2b68af (patch)
tree54a6fb51e4cc45215470f8cb2812534c1fc911b4
parent7c8fe5c4802b8ed8863c41264e0bf77e46d6bdcb (diff)
downloadgdb-f0641a0b382db7403f04fab3d4e8fac25a2b68af.zip
gdb-f0641a0b382db7403f04fab3d4e8fac25a2b68af.tar.gz
gdb-f0641a0b382db7403f04fab3d4e8fac25a2b68af.tar.bz2
Rework stringpool and hash tables so that we always generate the same
output regardless of randomize_va_space.
-rw-r--r--gold/layout.cc27
-rw-r--r--gold/layout.h6
-rw-r--r--gold/object.cc2
-rw-r--r--gold/po/gold.pot10
-rw-r--r--gold/stringpool.cc69
-rw-r--r--gold/stringpool.h51
-rw-r--r--gold/symtab.cc55
-rw-r--r--gold/symtab.h10
8 files changed, 152 insertions, 78 deletions
diff --git a/gold/layout.cc b/gold/layout.cc
index 2bdd11b..e969a80 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -53,7 +53,7 @@ Layout::Layout(const General_options& options)
size_t
Layout::Hash_key::operator()(const Layout::Key& k) const
{
- return reinterpret_cast<size_t>(k.first) + k.second.first + k.second.second;
+ return k.first + k.second.first + k.second.second;
}
// Whether to include this section in the link.
@@ -95,7 +95,7 @@ Layout::find_output_section(const char* name) const
for (Section_name_map::const_iterator p = this->section_name_map_.begin();
p != this->section_name_map_.end();
++p)
- if (strcmp(p->first.first, name) == 0)
+ if (strcmp(p->second->name(), name) == 0)
return p->second;
return NULL;
}
@@ -121,15 +121,15 @@ Layout::find_output_segment(elfcpp::PT type, elfcpp::Elf_Word set,
// and section flags FLAGS.
Output_section*
-Layout::get_output_section(const char* name, elfcpp::Elf_Word type,
- elfcpp::Elf_Xword flags)
+Layout::get_output_section(const char* name, Stringpool::Key name_key,
+ elfcpp::Elf_Word type, elfcpp::Elf_Xword flags)
{
// We should ignore some flags.
flags &= ~ (elfcpp::SHF_INFO_LINK
| elfcpp::SHF_LINK_ORDER
| elfcpp::SHF_GROUP);
- const Key key(name, std::make_pair(type, flags));
+ const Key key(name_key, std::make_pair(type, flags));
const std::pair<Key, Output_section*> v(key, NULL);
std::pair<Section_name_map::iterator, bool> ins(
this->section_name_map_.insert(v));
@@ -167,11 +167,13 @@ Layout::layout(Relobj* object, unsigned int shndx, const char* name,
// FIXME: Handle SHF_OS_NONCONFORMING here.
// Canonicalize the section name.
- name = this->namepool_.add(name, len);
+ Stringpool::Key name_key;
+ name = this->namepool_.add(name, len, &name_key);
// Find the output section. The output section is selected based on
// the section name, type, and flags.
- Output_section* os = this->get_output_section(name, shdr.get_sh_type(),
+ Output_section* os = this->get_output_section(name, name_key,
+ shdr.get_sh_type(),
shdr.get_sh_flags());
// FIXME: Handle SHF_LINK_ORDER somewhere.
@@ -189,9 +191,10 @@ Layout::add_output_section_data(const char* name, elfcpp::Elf_Word type,
Output_section_data* posd)
{
// Canonicalize the name.
- name = this->namepool_.add(name);
+ Stringpool::Key name_key;
+ name = this->namepool_.add(name, &name_key);
- Output_section* os = this->get_output_section(name, type, flags);
+ Output_section* os = this->get_output_section(name, name_key, type, flags);
os->add_output_section_data(posd);
}
@@ -672,12 +675,12 @@ Layout::create_symtab_sections(int size, const Input_objects* input_objects,
this->sympool_.set_string_offsets();
- const char* symtab_name = this->namepool_.add(".symtab");
+ const char* symtab_name = this->namepool_.add(".symtab", NULL);
Output_section* osymtab = new Output_section_symtab(symtab_name,
off - startoff);
this->section_list_.push_back(osymtab);
- const char* strtab_name = this->namepool_.add(".strtab");
+ const char* strtab_name = this->namepool_.add(".strtab", NULL);
Output_section *ostrtab = new Output_section_strtab(strtab_name,
&this->sympool_);
this->section_list_.push_back(ostrtab);
@@ -703,7 +706,7 @@ Layout::create_shstrtab()
// FIXME: We don't need to create a .shstrtab section if we are
// stripping everything.
- const char* name = this->namepool_.add(".shstrtab");
+ const char* name = this->namepool_.add(".shstrtab", NULL);
this->namepool_.set_string_offsets();
diff --git a/gold/layout.h b/gold/layout.h
index bb2b644..fa34617 100644
--- a/gold/layout.h
+++ b/gold/layout.h
@@ -196,8 +196,8 @@ class Layout
// Return the output section for NAME, TYPE and FLAGS.
Output_section*
- get_output_section(const char* name, elfcpp::Elf_Word type,
- elfcpp::Elf_Xword flags);
+ get_output_section(const char* name, Stringpool::Key name_key,
+ elfcpp::Elf_Word type, elfcpp::Elf_Xword flags);
// Create a new Output_section.
Output_section*
@@ -218,7 +218,7 @@ class Layout
// Mapping from input section name/type/flags to output section. We
// use canonicalized strings here.
- typedef std::pair<const char*,
+ typedef std::pair<Stringpool::Key,
std::pair<elfcpp::Elf_Word, elfcpp::Elf_Xword> > Key;
struct Hash_key
diff --git a/gold/object.cc b/gold/object.cc
index 22e89a9..956366c 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -628,7 +628,7 @@ Sized_relobj<size, big_endian>::do_finalize_local_symbols(off_t off,
if (sym.get_st_type() != elfcpp::STT_SECTION)
{
- pool->add(pnames + sym.get_st_name());
+ pool->add(pnames + sym.get_st_name(), NULL);
off += sym_size;
++count;
}
diff --git a/gold/po/gold.pot b/gold/po/gold.pot
index 4f00da4..c88ba7d 100644
--- a/gold/po/gold.pot
+++ b/gold/po/gold.pot
@@ -8,7 +8,7 @@ msgid ""
msgstr ""
"Project-Id-Version: PACKAGE VERSION\n"
"Report-Msgid-Bugs-To: \n"
-"POT-Creation-Date: 2006-11-06 13:40-0800\n"
+"POT-Creation-Date: 2006-11-06 15:58-0800\n"
"PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
"Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
"Language-Team: LANGUAGE <LL@li.org>\n"
@@ -477,22 +477,22 @@ msgstr ""
msgid "%s: %s: unsupported symbol binding %d for symbol %s\n"
msgstr ""
-#: symtab.cc:432
+#: symtab.cc:440
#, c-format
msgid "%s: %s: mixing 32-bit and 64-bit ELF objects\n"
msgstr ""
-#: symtab.cc:449
+#: symtab.cc:457
#, c-format
msgid "%s: %s: bad global symbol name offset %u at %lu\n"
msgstr ""
-#: symtab.cc:865 symtab.cc:1004
+#: symtab.cc:882 symtab.cc:1021
#, c-format
msgid "%s: %s: unsupported symbol section 0x%x\n"
msgstr ""
-#: symtab.cc:1114
+#: symtab.cc:1131
#, c-format
msgid "%s: %s: warning: %s\n"
msgstr ""
diff --git a/gold/stringpool.cc b/gold/stringpool.cc
index b1a2ce2..5b60259 100644
--- a/gold/stringpool.cc
+++ b/gold/stringpool.cc
@@ -14,7 +14,7 @@ namespace gold
{
Stringpool::Stringpool()
- : string_set_(), strings_(), strtab_size_(0)
+ : string_set_(), strings_(), strtab_size_(0), next_index_(1)
{
}
@@ -55,12 +55,18 @@ Stringpool::Stringpool_hash::operator()(const char* s) const
}
// Add a string to the list of canonical strings. Return a pointer to
-// the canonical string.
+// the canonical string. If PKEY is not NULL, set *PKEY to the key.
const char*
-Stringpool::add_string(const char* s)
+Stringpool::add_string(const char* s, Key* pkey)
{
+ // The size we allocate for a new Stringdata.
const size_t buffer_size = 1000;
+ // The amount we multiply the Stringdata index when calculating the
+ // key.
+ const size_t key_mult = 1024;
+ assert(key_mult >= buffer_size);
+
size_t len = strlen(s);
size_t alc;
@@ -81,7 +87,12 @@ Stringpool::add_string(const char* s)
{
char* ret = psd->data + psd->len;
memcpy(ret, s, len + 1);
+
+ if (pkey != NULL)
+ *pkey = psd->index * key_mult + psd->len;
+
psd->len += len + 1;
+
return ret;
}
}
@@ -90,17 +101,24 @@ Stringpool::add_string(const char* s)
psd->alc = alc - sizeof(Stringdata);
memcpy(psd->data, s, len + 1);
psd->len = len + 1;
+ psd->index = this->next_index_;
+ ++this->next_index_;
+
+ if (pkey != NULL)
+ *pkey = psd->index * key_mult;
+
if (front)
this->strings_.push_front(psd);
else
this->strings_.push_back(psd);
+
return psd->data;
}
// Add a string to a string pool.
const char*
-Stringpool::add(const char* s)
+Stringpool::add(const char* s, Key* pkey)
{
// FIXME: This will look up the entry twice in the hash table. The
// problem is that we can't insert S before we canonicalize it. I
@@ -110,33 +128,48 @@ Stringpool::add(const char* s)
String_set_type::const_iterator p = this->string_set_.find(s);
if (p != this->string_set_.end())
- return p->first;
+ {
+ if (pkey != NULL)
+ *pkey = p->second.first;
+ return p->first;
+ }
- const char* ret = this->add_string(s);
- std::pair<const char*, off_t> val(ret, 0);
+ Key k;
+ const char* ret = this->add_string(s, &k);
+
+ const off_t ozero = 0;
+ std::pair<const char*, Val> element(ret, std::make_pair(k, ozero));
std::pair<String_set_type::iterator, bool> ins =
- this->string_set_.insert(val);
+ this->string_set_.insert(element);
assert(ins.second);
+
+ if (pkey != NULL)
+ *pkey = k;
+
return ret;
}
// Add a prefix of a string to a string pool.
const char*
-Stringpool::add(const char* s, size_t len)
+Stringpool::add(const char* s, size_t len, Key* pkey)
{
// FIXME: This implementation should be rewritten when we rewrite
// the hash table to avoid copying.
std::string st(s, len);
- return this->add(st);
+ return this->add(st, pkey);
}
const char*
-Stringpool::find(const char* s) const
+Stringpool::find(const char* s, Key* pkey) const
{
String_set_type::const_iterator p = this->string_set_.find(s);
if (p == this->string_set_.end())
return NULL;
+
+ if (pkey != NULL)
+ *pkey = p->second.first;
+
return p->first;
}
@@ -206,14 +239,14 @@ Stringpool::set_string_offsets()
for (size_t i = 0; i < count; ++i)
{
if (v[i]->first[0] == '\0')
- v[i]->second = 0;
+ v[i]->second.second = 0;
else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
- v[i]->second = (v[i - 1]->second
- + strlen(v[i - 1]->first)
- - strlen(v[i]->first));
+ v[i]->second.second = (v[i - 1]->second.second
+ + strlen(v[i - 1]->first)
+ - strlen(v[i]->first));
else
{
- v[i]->second = offset;
+ v[i]->second.second = offset;
offset += strlen(v[i]->first) + 1;
}
}
@@ -229,7 +262,7 @@ Stringpool::get_offset(const char* s) const
{
String_set_type::const_iterator p = this->string_set_.find(s);
if (p != this->string_set_.end())
- return p->second;
+ return p->second.second;
abort();
}
@@ -244,7 +277,7 @@ Stringpool::write(Output_file* of, off_t offset)
for (String_set_type::const_iterator p = this->string_set_.begin();
p != this->string_set_.end();
++p)
- strcpy(view + p->second, p->first);
+ strcpy(view + p->second.second, p->first);
of->write_output_view(offset, this->strtab_size_, viewu);
}
diff --git a/gold/stringpool.h b/gold/stringpool.h
index 01c71a1..ed549b4 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -17,34 +17,42 @@ class Output_file;
class Stringpool
{
public:
+ // The type of a key into the stringpool. A key value will always
+ // be the same during any run of the linker. The string pointers
+ // may change when using address space randomization. We use key
+ // values in order to get repeatable runs when the value is inserted
+ // into an unordered hash table. Zero is never a valid key.
+ typedef size_t Key;
+
Stringpool();
~Stringpool();
// Add a string to the pool. This returns a canonical permanent
- // pointer to the string.
+ // pointer to the string. If PKEY is not NULL, this sets *PKEY to
+ // the key for the string.
const char*
- add(const char*);
+ add(const char*, Key* pkey);
const char*
- add(const std::string& s)
- { return this->add(s.c_str()); }
+ add(const std::string& s, Key* pkey)
+ { return this->add(s.c_str(), pkey); }
// Add the prefix of a string to the pool.
const char*
- add(const char *, size_t);
+ add(const char *, size_t, Key* pkey);
// If a string is present, return the canonical string. Otherwise,
- // return NULL.
+ // return NULL. If PKEY is not NULL, set *PKEY to the key.
const char*
- find(const char*) const;
+ find(const char*, Key* pkey) const;
// Turn the stringpool into an ELF strtab: determine the offsets of
// all the strings.
void
set_string_offsets();
- // Get the offset of a string.
+ // Get the offset of a string in an ELF strtab.
off_t
get_offset(const char*) const;
@@ -72,13 +80,15 @@ class Stringpool
size_t len;
// Allocated size of buffer.
size_t alc;
+ // Buffer index.
+ unsigned int index;
// Buffer.
char data[1];
};
// Copy a string into the buffers, returning a canonical string.
const char*
- add_string(const char*);
+ add_string(const char*, Key*);
struct Stringpool_hash
{
@@ -96,16 +106,19 @@ class Stringpool
// Return whether s1 is a suffix of s2.
static bool is_suffix(const char* s1, const char* s2);
- // The hash table is a map from string names to offsets. We only
- // use the offsets if we turn this into an ELF strtab section.
+ // The hash table is a map from string names to a pair of Key and
+ // ELF strtab offsets. We only use the offsets if we turn this into
+ // an ELF strtab section.
+
+ typedef std::pair<Key, off_t> Val;
#ifdef HAVE_TR1_UNORDERED_SET
- typedef Unordered_map<const char*, off_t, Stringpool_hash,
+ typedef Unordered_map<const char*, Val, Stringpool_hash,
Stringpool_eq,
- std::allocator<std::pair<const char* const, off_t> >,
+ std::allocator<std::pair<const char* const, Val> >,
true> String_set_type;
#else
- typedef Unordered_map<const char*, off_t, Stringpool_hash,
+ typedef Unordered_map<const char*, Val, Stringpool_hash,
Stringpool_eq> String_set_type;
#endif
@@ -118,9 +131,17 @@ class Stringpool
String_set_type::iterator) const;
};
+ // List of Stringdata structures.
+ typedef std::list<Stringdata*> Stringdata_list;
+
+ // Mapping from const char* to namepool entry.
String_set_type string_set_;
- std::list<Stringdata*> strings_;
+ // List of buffers.
+ Stringdata_list strings_;
+ // Size of ELF strtab.
off_t strtab_size_;
+ // Next Stringdata index.
+ unsigned int next_index_;
};
} // End namespace gold.
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 091144a..054e07f 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -174,8 +174,7 @@ Symbol_table::~Symbol_table()
size_t
Symbol_table::Symbol_table_hash::operator()(const Symbol_table_key& key) const
{
- return (reinterpret_cast<size_t>(key.first)
- ^ reinterpret_cast<size_t>(key.second));
+ return key.first ^ key.second;
}
// The symbol table key equality function. This is only called with
@@ -216,17 +215,20 @@ Symbol_table::resolve_forwards(Symbol* from) const
Symbol*
Symbol_table::lookup(const char* name, const char* version) const
{
- name = this->namepool_.find(name);
+ Stringpool::Key name_key;
+ name = this->namepool_.find(name, &name_key);
if (name == NULL)
return NULL;
+
+ Stringpool::Key version_key = 0;
if (version != NULL)
{
- version = this->namepool_.find(version);
+ version = this->namepool_.find(version, &version_key);
if (version == NULL)
return NULL;
}
- Symbol_table_key key(name, version);
+ Symbol_table_key key(name_key, version_key);
Symbol_table::Symbol_table_type::const_iterator p = this->table_.find(key);
if (p == this->table_.end())
return NULL;
@@ -282,19 +284,24 @@ template<int size, bool big_endian>
Symbol*
Symbol_table::add_from_object(Object* object,
const char *name,
- const char *version, bool def,
+ Stringpool::Key name_key,
+ const char *version,
+ Stringpool::Key version_key,
+ bool def,
const elfcpp::Sym<size, big_endian>& sym)
{
Symbol* const snull = NULL;
std::pair<typename Symbol_table_type::iterator, bool> ins =
- this->table_.insert(std::make_pair(std::make_pair(name, version), snull));
+ this->table_.insert(std::make_pair(std::make_pair(name_key, version_key),
+ snull));
std::pair<typename Symbol_table_type::iterator, bool> insdef =
std::make_pair(this->table_.end(), false);
if (def)
{
- const char* const vnull = NULL;
- insdef = this->table_.insert(std::make_pair(std::make_pair(name, vnull),
+ const Stringpool::Key vnull_key = 0;
+ insdef = this->table_.insert(std::make_pair(std::make_pair(name_key,
+ vnull_key),
snull));
}
@@ -379,7 +386,8 @@ Symbol_table::add_from_object(Object* object,
{
this->table_.erase(insdef.first);
// Inserting insdef invalidated ins.
- this->table_.erase(std::make_pair(name, version));
+ this->table_.erase(std::make_pair(name_key,
+ version_key));
}
return NULL;
}
@@ -477,12 +485,16 @@ Symbol_table::add_from_object(
Symbol* res;
if (ver == NULL)
{
- name = this->namepool_.add(name);
- res = this->add_from_object(object, name, NULL, false, *psym);
+ Stringpool::Key name_key;
+ name = this->namepool_.add(name, &name_key);
+ res = this->add_from_object(object, name, name_key, NULL, 0,
+ false, *psym);
}
else
{
- name = this->namepool_.add(name, ver - name);
+ Stringpool::Key name_key;
+ name = this->namepool_.add(name, ver - name, &name_key);
+
bool def = false;
++ver;
if (*ver == '@')
@@ -490,8 +502,12 @@ Symbol_table::add_from_object(
def = true;
++ver;
}
- ver = this->namepool_.add(ver);
- res = this->add_from_object(object, name, ver, def, *psym);
+
+ Stringpool::Key ver_key;
+ ver = this->namepool_.add(ver, &ver_key);
+
+ res = this->add_from_object(object, name, name_key, ver, ver_key,
+ def, *psym);
}
*sympointers++ = res;
@@ -525,12 +541,13 @@ Symbol_table::define_special_symbol(Target* target, const char* name,
else
{
// Canonicalize NAME.
- name = this->namepool_.add(name);
+ Stringpool::Key name_key;
+ name = this->namepool_.add(name, &name_key);
Symbol* const snull = NULL;
- const char* const vnull = NULL;
+ const Stringpool::Key ver_key = 0;
std::pair<typename Symbol_table_type::iterator, bool> ins =
- this->table_.insert(std::make_pair(std::make_pair(name, vnull),
+ this->table_.insert(std::make_pair(std::make_pair(name_key, ver_key),
snull));
if (!ins.second)
@@ -937,7 +954,7 @@ Symbol_table::sized_finalize(off_t off, Stringpool* pool)
}
sym->set_value(value);
- pool->add(sym->name());
+ pool->add(sym->name(), NULL);
++count;
off += sym_size;
++p;
diff --git a/gold/symtab.h b/gold/symtab.h
index f544e06..6589899 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -683,7 +683,7 @@ class Symbol_table
// Canonicalize a symbol name for use in the hash table.
const char*
canonicalize_name(const char* name)
- { return this->namepool_.add(name); }
+ { return this->namepool_.add(name, NULL); }
// Possibly issue a warning for a reference to SYM at LOCATION which
// is in OBJ.
@@ -718,9 +718,9 @@ class Symbol_table
// Add a symbol.
template<int size, bool big_endian>
Symbol*
- add_from_object(Object*, const char *name,
- const char *version, bool def,
- const elfcpp::Sym<size, big_endian>& sym);
+ add_from_object(Object*, const char *name, Stringpool::Key name_key,
+ const char *version, Stringpool::Key version_key,
+ bool def, const elfcpp::Sym<size, big_endian>& sym);
// Resolve symbols.
template<int size, bool big_endian>
@@ -783,7 +783,7 @@ class Symbol_table
// The type of the symbol hash table.
- typedef std::pair<const char*, const char*> Symbol_table_key;
+ typedef std::pair<Stringpool::Key, Stringpool::Key> Symbol_table_key;
struct Symbol_table_hash
{