aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@google.com>2007-11-27 06:13:33 +0000
committerIan Lance Taylor <iant@google.com>2007-11-27 06:13:33 +0000
commit4625f782a5e7744937b60b0421de3ff9f55346ec (patch)
tree71c5ade4945fe14b262a793df92330cd377bee09
parent4f0916aa9477fcf9a5c0e1ecd1c127fe370f2a2c (diff)
downloadgdb-4625f782a5e7744937b60b0421de3ff9f55346ec.zip
gdb-4625f782a5e7744937b60b0421de3ff9f55346ec.tar.gz
gdb-4625f782a5e7744937b60b0421de3ff9f55346ec.tar.bz2
Rework merge_map for speed.
-rw-r--r--gold/merge.cc299
-rw-r--r--gold/merge.h32
-rw-r--r--gold/object.h22
3 files changed, 263 insertions, 90 deletions
diff --git a/gold/merge.cc b/gold/merge.cc
index 0c4256b..d8648d6 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -30,31 +30,239 @@
namespace gold
{
-// Class Merge_map::Merge_key_less.
+// For each object with merge sections, we store an Object_merge_map.
+// This is used to map locations in input sections to a merged output
+// section. The output section itself is not recorded here--it can be
+// found in the map_to_output_ field of the Object.
-// Sort the entries in a merge mapping. The key is an input object, a
-// section index in that object, and an offset in that section.
+class Object_merge_map
+{
+ public:
+ Object_merge_map()
+ : first_shnum_(-1U), first_map_(),
+ second_shnum_(-1U), second_map_(),
+ section_merge_maps_()
+ { }
+
+ ~Object_merge_map();
+
+ // Add a mapping for MERGE_MAP, for the bytes from OFFSET to OFFSET
+ // + LENGTH in the input section SHNDX to OUTPUT_OFFSET in the
+ // output section. An OUTPUT_OFFSET of -1 means that the bytes are
+ // discarded.
+ void
+ add_mapping(const Merge_map*, unsigned int shndx, off_t offset, off_t length,
+ off_t output_offset);
+
+ // Get the output offset for an input address in MERGE_MAP. The
+ // input address is at offset OFFSET in section SHNDX. This sets
+ // *OUTPUT_OFFSET to the offset in the output section; this will be
+ // -1 if the bytes are not being copied to the output. This returns
+ // true if the mapping is known, false otherwise.
+ bool
+ get_output_offset(const Merge_map*, unsigned int shndx, off_t offset,
+ off_t *output_offset);
+
+ private:
+ // Map input section offsets to a length and an output section
+ // offset. An output section offset of -1 means that this part of
+ // the input section is being discarded.
+ struct Input_merge_entry
+ {
+ // The offset in the input section.
+ off_t input_offset;
+ // The length.
+ off_t length;
+ // The offset in the output section.
+ off_t output_offset;
+ };
+
+ // A less-than comparison routine for Input_merge_entry.
+ struct Input_merge_compare
+ {
+ bool
+ operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
+ { return i1.input_offset < i2.input_offset; }
+ };
+
+ // A list of entries for a particular section.
+ struct Input_merge_map
+ {
+ // The Merge_map for this section.
+ const Merge_map* merge_map;
+ // The list of mappings.
+ std::vector<Input_merge_entry> entries;
+ // Whether the ENTRIES field is sorted by input_offset.
+ bool sorted;
+
+ Input_merge_map()
+ : merge_map(NULL), entries(), sorted(true)
+ { }
+ };
+
+ // Map input section indices to merge maps.
+ typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;
+
+ // Return a pointer to the Input_merge_map to use for the input
+ // section SHNDX, or NULL.
+ Input_merge_map*
+ get_input_merge_map(unsigned int shndx);
+
+ // Get or make the the Input_merge_map to use for the section SHNDX
+ // with MERGE_MAP.
+ Input_merge_map*
+ get_or_make_input_merge_map(const Merge_map* merge_map, unsigned int shndx);
+
+ // Any given object file will normally only have a couple of input
+ // sections with mergeable contents. So we keep the first two input
+ // section numbers inline, and push any further ones into a map. A
+ // value of -1U in first_shnum_ or second_shnum_ means that we don't
+ // have a corresponding entry.
+ unsigned int first_shnum_;
+ Input_merge_map first_map_;
+ unsigned int second_shnum_;
+ Input_merge_map second_map_;
+ Section_merge_maps section_merge_maps_;
+};
+
+// Destructor.
+
+Object_merge_map::~Object_merge_map()
+{
+ for (Section_merge_maps::iterator p = this->section_merge_maps_.begin();
+ p != this->section_merge_maps_.end();
+ ++p)
+ delete p->second;
+}
+
+// Get the Input_merge_map to use for an input section, or NULL.
+
+Object_merge_map::Input_merge_map*
+Object_merge_map::get_input_merge_map(unsigned int shndx)
+{
+ gold_assert(shndx != -1U);
+ if (shndx == this->first_shnum_)
+ return &this->first_map_;
+ if (shndx == this->second_shnum_)
+ return &this->second_map_;
+ Section_merge_maps::const_iterator p = this->section_merge_maps_.find(shndx);
+ if (p != this->section_merge_maps_.end())
+ return p->second;
+ return NULL;
+}
-inline bool
-Merge_map::Merge_key_less::operator()(const Merge_key& mk1,
- const Merge_key& mk2) const
+// Get or create the Input_merge_map to use for an input section.
+
+Object_merge_map::Input_merge_map*
+Object_merge_map::get_or_make_input_merge_map(const Merge_map* merge_map,
+ unsigned int shndx)
{
- // The order of different objects and different sections doesn't
- // matter. We want to get consistent results across links so we
- // don't use pointer comparison.
- if (mk1.object != mk2.object)
+ Input_merge_map* map = this->get_input_merge_map(shndx);
+ if (map != NULL)
+ {
+ // For a given input section in a given object, every mapping
+ // must be donw with the same Merge_map.
+ gold_assert(map->merge_map == merge_map);
+ return map;
+ }
+
+ // We need to create a new entry.
+ if (this->first_shnum_ == -1U)
{
- // Two different object files can have the same name: if foo.a
- // includes both bar/qux.o and baz/qux.o, then both end up with
- // the name foo.a(qux.o). But it's impossible for two different
- // object files to have both the same name and the same offset.
- if (mk1.object->offset() != mk2.object->offset())
- return mk1.object->offset() < mk2.object->offset();
- return mk1.object->name() < mk2.object->name();
+ this->first_shnum_ = shndx;
+ this->first_map_.merge_map = merge_map;
+ return &this->first_map_;
}
- if (mk1.shndx != mk2.shndx)
- return mk1.shndx < mk2.shndx;
- return mk1.offset < mk2.offset;
+ if (this->second_shnum_ == -1U)
+ {
+ this->second_shnum_ = shndx;
+ this->second_map_.merge_map = merge_map;
+ return &this->second_map_;
+ }
+
+ Input_merge_map* new_map = new Input_merge_map;
+ new_map->merge_map = merge_map;
+ this->section_merge_maps_[shndx] = new_map;
+ return new_map;
+}
+
+// Add a mapping.
+
+void
+Object_merge_map::add_mapping(const Merge_map* merge_map, unsigned int shndx,
+ off_t input_offset, off_t length,
+ off_t output_offset)
+{
+ Input_merge_map* map = this->get_or_make_input_merge_map(merge_map, shndx);
+
+ // Try to merge the new entry in the last one we saw.
+ if (!map->entries.empty())
+ {
+ Input_merge_entry& entry(map->entries.back());
+
+ // If this entry is not in order, we need to sort the vector
+ // before looking anything up.
+ if (input_offset < entry.input_offset + entry.length)
+ {
+ gold_assert(input_offset < entry.input_offset
+ && input_offset + length <= entry.input_offset);
+ map->sorted = false;
+ }
+ else if (entry.input_offset + entry.length == input_offset
+ && (output_offset == -1
+ ? entry.output_offset == -1
+ : entry.output_offset + entry.length == output_offset))
+ {
+ entry.length += length;
+ return;
+ }
+ }
+
+ Input_merge_entry entry;
+ entry.input_offset = input_offset;
+ entry.length = length;
+ entry.output_offset = output_offset;
+ map->entries.push_back(entry);
+}
+
+// Get the output offset for an input address.
+
+bool
+Object_merge_map::get_output_offset(const Merge_map* merge_map,
+ unsigned int shndx, off_t input_offset,
+ off_t *output_offset)
+{
+ Input_merge_map* map = this->get_input_merge_map(shndx);
+ if (map == NULL || map->merge_map != merge_map)
+ return false;
+
+ if (!map->sorted)
+ {
+ std::sort(map->entries.begin(), map->entries.end(),
+ Input_merge_compare());
+ map->sorted = true;
+ }
+
+ Input_merge_entry entry;
+ entry.input_offset = input_offset;
+ std::vector<Input_merge_entry>::const_iterator p =
+ std::lower_bound(map->entries.begin(), map->entries.end(),
+ entry, Input_merge_compare());
+ if (p == map->entries.end() || p->input_offset > input_offset)
+ {
+ if (p == map->entries.begin())
+ return false;
+ --p;
+ gold_assert(p->input_offset <= input_offset);
+ }
+
+ if (input_offset - p->input_offset >= p->length)
+ return false;
+
+ *output_offset = p->output_offset;
+ if (*output_offset != -1)
+ *output_offset += (input_offset - p->input_offset);
+ return true;
}
// Class Merge_map.
@@ -67,18 +275,14 @@ void
Merge_map::add_mapping(Relobj* object, unsigned int shndx,
off_t offset, off_t length, off_t output_offset)
{
- Merge_key mk;
- mk.object = object;
- mk.shndx = shndx;
- mk.offset = offset;
-
- Merge_value mv;
- mv.length = length;
- mv.output_offset = output_offset;
-
- std::pair<Merge_mapping::iterator, bool> ins =
- this->merge_map_.insert(std::make_pair(mk, mv));
- gold_assert(ins.second);
+ Object_merge_map* object_merge_map = object->merge_map();
+ if (object_merge_map == NULL)
+ {
+ object_merge_map = new Object_merge_map();
+ object->set_merge_map(object_merge_map);
+ }
+
+ object_merge_map->add_mapping(this, shndx, offset, length, output_offset);
}
// Return the output offset for an input address. The input address
@@ -90,34 +294,11 @@ bool
Merge_map::get_output_offset(const Relobj* object, unsigned int shndx,
off_t offset, off_t* output_offset) const
{
- Merge_key mk;
- mk.object = object;
- mk.shndx = shndx;
- mk.offset = offset;
- Merge_mapping::const_iterator p = this->merge_map_.lower_bound(mk);
-
- // If MK is not in the map, lower_bound returns the next iterator
- // larger than it.
- if (p == this->merge_map_.end()
- || p->first.object != object
- || p->first.shndx != shndx
- || p->first.offset != offset)
- {
- if (p == this->merge_map_.begin())
- return false;
- --p;
- }
-
- if (p->first.object != object || p->first.shndx != shndx)
- return false;
-
- if (offset - p->first.offset >= p->second.length)
+ Object_merge_map* object_merge_map = object->merge_map();
+ if (object_merge_map == NULL)
return false;
-
- *output_offset = p->second.output_offset;
- if (*output_offset != -1)
- *output_offset += (offset - p->first.offset);
- return true;
+ return object_merge_map->get_output_offset(this, shndx, offset,
+ output_offset);
}
// Class Output_merge_base.
diff --git a/gold/merge.h b/gold/merge.h
index 1f750c5..ad00997 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -32,13 +32,13 @@ namespace gold
{
// This class manages mappings from input sections to offsets in an
-// output section. This is used where input sections are merged.
+// output section. This is used where input sections are merged. The
+// actual data is stored in fields in Object.
class Merge_map
{
public:
Merge_map()
- : merge_map_()
{ }
// Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in the
@@ -57,34 +57,6 @@ class Merge_map
bool
get_output_offset(const Relobj* object, unsigned int shndx, off_t offset,
off_t *output_offset) const;
-
- private:
- // We build a mapping from OBJECT/SHNDX/OFFSET to an offset and
- // length in the output section.
- struct Merge_key
- {
- const Relobj* object;
- unsigned int shndx;
- off_t offset;
- };
-
- struct Merge_key_less
- {
- inline bool
- operator()(const Merge_key&, const Merge_key&) const;
- };
-
- struct Merge_value
- {
- off_t length;
- off_t output_offset;
- };
-
- typedef std::map<Merge_key, Merge_value, Merge_key_less> Merge_mapping;
-
- // A mapping from input object/section/offset to offset in output
- // section.
- Merge_mapping merge_map_;
};
// A general class for SHF_MERGE data, to hold functions shared by
diff --git a/gold/object.h b/gold/object.h
index 6f06fa8..6991d26 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -39,6 +39,7 @@ class Layout;
class Output_section;
class Output_file;
class Dynobj;
+class Object_merge_map;
template<typename Stringpool_char>
class Stringpool_template;
@@ -411,7 +412,10 @@ class Relobj : public Object
{
public:
Relobj(const std::string& name, Input_file* input_file, off_t offset = 0)
- : Object(name, input_file, false, offset)
+ : Object(name, input_file, false, offset),
+ map_to_output_(),
+ object_merge_map_(NULL),
+ relocs_must_follow_section_writes_(false)
{ }
// Read the relocs.
@@ -481,6 +485,19 @@ class Relobj : public Object
relocs_must_follow_section_writes()
{ return this->relocs_must_follow_section_writes_; }
+ // Return the object merge map.
+ Object_merge_map*
+ merge_map() const
+ { return this->object_merge_map_; }
+
+ // Set the object merge map.
+ void
+ set_merge_map(Object_merge_map* object_merge_map)
+ {
+ gold_assert(this->object_merge_map_ == NULL);
+ this->object_merge_map_ = object_merge_map;
+ }
+
protected:
// What we need to know to map an input section to an output
// section. We keep an array of these, one for each input section,
@@ -533,6 +550,9 @@ class Relobj : public Object
private:
// Mapping from input sections to output section.
std::vector<Map_to_output> map_to_output_;
+ // Mappings for merge sections. This is managed by the code in the
+ // Merge_map class.
+ Object_merge_map* object_merge_map_;
// Whether we need to wait for output sections to be written before
// we can apply relocations.
bool relocs_must_follow_section_writes_;