* [patch/rfc][pr17902] GC unused parts of mergeable sections
@ 2015-02-03 16:11 Rafael Espíndola
2015-02-05 15:26 ` Rafael Espíndola
0 siblings, 1 reply; 5+ messages in thread
From: Rafael Espíndola @ 2015-02-03 16:11 UTC (permalink / raw)
To: Binutils; +Cc: Cary Coutant, Nico Weber
[-- Attachment #1: Type: text/plain, Size: 730 bytes --]
Attached is an incomplete patch for removing unused parts of mergeable sections.
It uses the walk over relocations done by --gc-sections to collect
which offsets in a mergeable section are used. It then stores that
information in a (section -> offset set) map in Relobj.
The map is then used by other parts of the linker to avoid including
them in the output. In the patch, only strings is implemented.
The obvious missing parts are marked with a FIXME (and it is missing a
test). For now it would be nice to just know if I am going on the
right direction or if there is a better place to plug in this
optimization.
I tested it when linking chrome and it cuts the rodata section from
6985174 to 6852054 bytes.
Cheers,
Rafael
[-- Attachment #2: t.patch --]
[-- Type: text/x-patch, Size: 6575 bytes --]
diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..634bda9 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -68,6 +68,21 @@ Garbage_collection::do_transitive_closure()
}
}
this->worklist_ready();
+ for (Sections_reachable::iterator I = this->referenced_list().begin(),
+ E = this->referenced_list().end();
+ I != E; ++I) {
+ Atom_reachable &atoms = this->atom_reloc_map()[*I];
+ for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+ I2 != E2; ++I2) {
+ const Atom &atom = *I2;
+ const Section_id id = atom.first;
+ Object* obj = id.first;
+ unsigned int sec_num = id.second;
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ r_obj->referenced_offsets()[sec_num].insert(atom.second);
+ }
+ }
}
} // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index 2db7cb9..fe0ca70 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -58,6 +58,16 @@ class Garbage_collection
// Different object files can have cident sections with the same name.
typedef std::map<std::string, Sections_reachable> Cident_section_map;
+ typedef std::pair<Section_id, uint64_t> Atom;
+ struct Atom_hash {
+ size_t operator()(const Atom &a) const {
+ const Section_id &s = a.first;
+ return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+ }
+ };
+ typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+ typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
Garbage_collection()
: is_worklist_ready_(false)
{ }
@@ -72,6 +82,10 @@ class Garbage_collection
section_reloc_map()
{ return this->section_reloc_map_; }
+ Atom_ref&
+ atom_reloc_map()
+ { return this->atom_reloc_map_; }
+
Worklist_type&
worklist()
{ return this->work_list_; }
@@ -116,6 +130,17 @@ class Garbage_collection
p->second.insert(dst_id);
}
+ void add_reference_to_merge_section(Object *src_object,
+ unsigned int src_shndx,
+ Object *dst_object,
+ unsigned int dst_shndx, uint64_t offset) {
+ add_reference(src_object, src_shndx, dst_object, dst_shndx);
+ Section_id src_id(src_object, src_shndx);
+ Section_id dst_id(dst_object, dst_shndx);
+ Atom atom(dst_id, offset);
+ this->atom_reloc_map_[src_id].insert(atom);
+ }
+
private:
Worklist_type work_list_;
@@ -123,6 +148,8 @@ class Garbage_collection
Section_ref section_reloc_map_;
Sections_reachable referenced_list_;
Cident_section_map cident_sections_;
+
+ Atom_ref atom_reloc_map_;
};
// Data to pass between successive invocations of do_layout
@@ -238,6 +265,10 @@ gc_process_relocs(
typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
Address dst_off;
+ // If the relocation points to a section, this includes the addend.
+ // Otherwise it doesn't.
+ Address gc_ref_off;
+
if (r_sym < local_count)
{
gold_assert(plocal_syms != NULL);
@@ -247,7 +278,10 @@ gc_process_relocs(
bool is_ordinary;
dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
dst_obj = src_obj;
- dst_off = lsym.get_st_value() + addend;
+ gc_ref_off = dst_off = lsym.get_st_value();
+ dst_off += addend;
+ if (lsym.get_st_type() == elfcpp::STT_SECTION)
+ gc_ref_off += addend;
if (is_icf_tracked)
{
@@ -300,6 +334,7 @@ gc_process_relocs(
}
dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
dst_off += addend;
+ gc_ref_off = dst_off;
// When doing safe folding, check to see if this relocation is that
// of a function pointer being taken.
@@ -351,7 +386,14 @@ gc_process_relocs(
}
if (parameters->options().gc_sections())
{
- symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+ Garbage_collection* gc = symtab->gc();
+ uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+ if (dst_flags & elfcpp::SHF_MERGE)
+ gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+ dst_indx, gc_ref_off);
+ else
+ gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
parameters->sized_target<size, big_endian>()
->gc_add_reference(symtab, src_obj, src_indx,
dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index 269e6bf..fc5f5e0 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -574,10 +574,18 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
!= init_align_modulo))
has_misaligned_strings = true;
- Stringpool::Key key;
- this->stringpool_.add_with_length(p, len, true, &key);
-
- merged_strings.push_back(Merged_string(i, key));
+ uintptr_t offset =
+ reinterpret_cast<uintptr_t>(p) - reinterpret_cast<uintptr_t>(pdata);
+
+ // FIXME: we have to handle an offset in [p, p + len).
+ // FIXME: handle the non-gc case
+ if (((object->section_flags(shndx) & elfcpp::SHF_ALLOC) == 0) ||
+ object->referenced_offsets()[shndx].count(offset)) {
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
+
+ merged_strings.push_back(Merged_string(i, key));
+ }
p += len + 1;
i += (len + 1) * sizeof(Char_type);
}
diff --git a/gold/object.h b/gold/object.h
index cce6c8c..202c949 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -322,6 +322,8 @@ class Object
{
public:
typedef std::vector<Symbol*> Symbols;
+ typedef Unordered_set<uint64_t> Offsets_reachable;
+ typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
// NAME is the name of the object as we would report it to the user
// (e.g., libfoo.a(bar.o) if this is in an archive. INPUT_FILE is
@@ -1255,6 +1257,10 @@ class Relobj : public Object
is_big_endian() const
{ return this->do_is_big_endian(); }
+ Offset_ref&
+ referenced_offsets()
+ { return this->referenced_offsets_; }
+
protected:
// The output section to be used for each input section, indexed by
// the input section number. The output section is NULL if the
@@ -1454,6 +1460,8 @@ class Relobj : public Object
unsigned int first_dyn_reloc_;
// Count of dynamic relocations for this object.
unsigned int dyn_reloc_count_;
+
+ std::map<unsigned int, Offsets_reachable> referenced_offsets_;
};
// This class is used to handle relocations against a section symbol
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch/rfc][pr17902] GC unused parts of mergeable sections
2015-02-03 16:11 [patch/rfc][pr17902] GC unused parts of mergeable sections Rafael Espíndola
@ 2015-02-05 15:26 ` Rafael Espíndola
2015-02-06 16:28 ` Rafael Espíndola
0 siblings, 1 reply; 5+ messages in thread
From: Rafael Espíndola @ 2015-02-05 15:26 UTC (permalink / raw)
To: Binutils; +Cc: Cary Coutant, Nico Weber
[-- Attachment #1: Type: text/plain, Size: 271 bytes --]
A new wip version is attached.
In comparison with the previous one, this version
* Handles non-string SHF_MERGE.
* Handles symbol making part of a section referenced.
* Mix fixes.
It reduces the .rodata section in chrome from 6985174 to 6851542 bytes.
Cheers,
Rafael
[-- Attachment #2: t.patch --]
[-- Type: text/x-patch, Size: 13935 bytes --]
diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..c96faf4 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -29,6 +29,34 @@
namespace gold
{
+void Worklist::just_push(const Section_id &val) { this->work_list_.push(val); }
+
+void Worklist::push(const Section_id &val) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ gold_assert((flags & elfcpp::SHF_MERGE) == 0);
+}
+
+void Worklist::push(const Section_id &val, uint64_t offset) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return;
+
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[shndx];
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), offset);
+ // FIXME: duplicated code with Garbage_collection::do_transitive_closure.
+ if (I == offsets.end() || *I != offset)
+ offsets.insert(I, offset);
+}
+
// Garbage collection uses a worklist style algorithm to determine the
// transitive closure of all referenced sections.
void
@@ -63,11 +91,34 @@ Garbage_collection::do_transitive_closure()
if (this->referenced_list().find(*it_v)
== this->referenced_list().end())
{
- this->worklist().push(*it_v);
+ this->worklist().just_push(*it_v);
}
}
}
this->worklist_ready();
+ for (Sections_reachable::iterator I = this->referenced_list().begin(),
+ E = this->referenced_list().end();
+ I != E; ++I) {
+ Atom_reachable &atoms = this->atom_reloc_map()[*I];
+ for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+ I2 != E2; ++I2) {
+ const Atom &atom = *I2;
+ const Section_id id = atom.first;
+ Object* obj = id.first;
+ unsigned int sec_num = id.second;
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[sec_num];
+ uint64_t new_offset = atom.second;
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), new_offset);
+ // FIXME: Consider different algorithms:
+ // just push_back and sort/uniq afterwards
+ // use a set on the side to avoid inserting duplicates
+ if (I == offsets.end() || *I != new_offset)
+ offsets.insert(I, new_offset);
+ }
+ }
}
} // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index 2db7cb9..7effbe1 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -46,18 +46,49 @@ class Output_section;
class General_options;
class Layout;
+class Worklist
+{
+ public:
+ bool empty() const {
+ return work_list_.empty();
+ }
+ Section_id &front() {
+ return work_list_.front();
+ }
+ void pop() {
+ work_list_.pop();
+ }
+ void just_push(const Section_id& val);
+ void push(const Section_id& val);
+ void push(const Section_id& val, uint64_t offset);
+
+ private:
+ typedef std::queue<Section_id> Worklist_type;
+ Worklist_type work_list_;
+};
+
class Garbage_collection
{
public:
typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
typedef std::map<Section_id, Sections_reachable> Section_ref;
- typedef std::queue<Section_id> Worklist_type;
+
// This maps the name of the section which can be represented as a C
// identifier (cident) to the list of sections that have that name.
// Different object files can have cident sections with the same name.
typedef std::map<std::string, Sections_reachable> Cident_section_map;
+ typedef std::pair<Section_id, uint64_t> Atom;
+ struct Atom_hash {
+ size_t operator()(const Atom &a) const {
+ const Section_id &s = a.first;
+ return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+ }
+ };
+ typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+ typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
Garbage_collection()
: is_worklist_ready_(false)
{ }
@@ -72,7 +103,11 @@ class Garbage_collection
section_reloc_map()
{ return this->section_reloc_map_; }
- Worklist_type&
+ Atom_ref&
+ atom_reloc_map()
+ { return this->atom_reloc_map_; }
+
+ Worklist&
worklist()
{ return this->work_list_; }
@@ -116,13 +151,26 @@ class Garbage_collection
p->second.insert(dst_id);
}
+ void add_reference_to_merge_section(Object *src_object,
+ unsigned int src_shndx,
+ Object *dst_object,
+ unsigned int dst_shndx, uint64_t offset) {
+ add_reference(src_object, src_shndx, dst_object, dst_shndx);
+ Section_id src_id(src_object, src_shndx);
+ Section_id dst_id(dst_object, dst_shndx);
+ Atom atom(dst_id, offset);
+ this->atom_reloc_map_[src_id].insert(atom);
+ }
+
private:
- Worklist_type work_list_;
+ Worklist work_list_;
bool is_worklist_ready_;
Section_ref section_reloc_map_;
Sections_reachable referenced_list_;
Cident_section_map cident_sections_;
+
+ Atom_ref atom_reloc_map_;
};
// Data to pass between successive invocations of do_layout
@@ -238,6 +286,10 @@ gc_process_relocs(
typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
Address dst_off;
+ // If the relocation points to a section, this includes the addend.
+ // Otherwise it doesn't.
+ Address gc_ref_off;
+
if (r_sym < local_count)
{
gold_assert(plocal_syms != NULL);
@@ -247,7 +299,10 @@ gc_process_relocs(
bool is_ordinary;
dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
dst_obj = src_obj;
- dst_off = lsym.get_st_value() + addend;
+ gc_ref_off = dst_off = lsym.get_st_value();
+ dst_off += addend;
+ if (lsym.get_st_type() == elfcpp::STT_SECTION)
+ gc_ref_off += addend;
if (is_icf_tracked)
{
@@ -299,6 +354,7 @@ gc_process_relocs(
dst_indx = gsym->shndx(&is_ordinary);
}
dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
+ gc_ref_off = dst_off;
dst_off += addend;
// When doing safe folding, check to see if this relocation is that
@@ -351,7 +407,14 @@ gc_process_relocs(
}
if (parameters->options().gc_sections())
{
- symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+ Garbage_collection* gc = symtab->gc();
+ uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+ if (dst_flags & elfcpp::SHF_MERGE)
+ gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+ dst_indx, gc_ref_off);
+ else
+ gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
parameters->sized_target<size, big_endian>()
->gc_add_reference(symtab, src_obj, src_indx,
dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index f547388..5776735 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -423,6 +423,9 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
for (section_size_type i = 0; i < len; i += entsize, p += entsize)
{
+ if (!object->is_offset_referenced(shndx, i, entsize))
+ continue;
+
// Add the constant to the section contents. If we find that it
// is already in the hash table, we will remove it again.
Merge_data_key k = this->len_;
@@ -567,6 +570,7 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
while (p < pend)
{
size_t len = p < pend0 ? string_length(p) : pend - p;
+ size_t num_bytes = (len + 1) * sizeof(Char_type);
// Within merge input section each string must be aligned.
if (len != 0
@@ -574,12 +578,15 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
!= init_align_modulo))
has_misaligned_strings = true;
- Stringpool::Key key;
- this->stringpool_.add_with_length(p, len, true, &key);
+ // FIXME: replace offset with i.
+ if (object->is_offset_referenced(shndx, i, num_bytes)) {
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
- merged_strings.push_back(Merged_string(i, key));
+ merged_strings.push_back(Merged_string(i, key));
+ }
p += len + 1;
- i += (len + 1) * sizeof(Char_type);
+ i += num_bytes;
}
// Record the last offset in the input section so that we can
diff --git a/gold/object.cc b/gold/object.cc
index 8f16fe7..4c08dd3 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -368,6 +368,30 @@ Relobj::finalize_incremental_relocs(Layout* layout, bool clear_counts)
layout->incremental_inputs()->set_reloc_count(rindex);
}
+bool Relobj::is_offset_referenced(unsigned int shndx, uint64_t offset,
+ size_t len) {
+ if (!parameters->options().gc_sections())
+ return true;
+
+ uint64_t flags = this->section_flags(shndx);
+ // We don't gc non alloc sections.
+ if ((flags & elfcpp::SHF_ALLOC) == 0)
+ return true;
+
+ // Only SHF_MERGE sections are partially gced.
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return true;
+
+ Object::Offsets_reachable &offsets = this->referenced_offsets()[shndx];
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), offset);
+ if (I == offsets.end())
+ return false;
+ if (*I >= offset + len)
+ return false;
+ return true;
+}
+
// Class Sized_relobj.
// Iterate over local symbols, calling a visitor class V for each GOT offset
@@ -2154,7 +2178,10 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
// Decide whether this symbol should go into the output file.
- if ((shndx < shnum && out_sections[shndx] == NULL)
+ if ((shndx < shnum
+ && (out_sections[shndx] == NULL ||
+ !this->is_offset_referenced(shndx, sym.get_st_value(),
+ /*FIXME*/ 4)))
|| shndx == this->discarded_eh_frame_shndx_)
{
lv.set_no_output_symtab_entry();
@@ -2327,6 +2354,10 @@ Sized_relobj_file<size, big_endian>::compute_final_local_value_internal(
}
else if (!lv_in->is_section_symbol())
{
+ if (!this->is_offset_referenced(shndx, lv_in->input_value(),
+ /*FIXME*/4))
+ return This::CFLV_DISCARDED;
+
// This is not a section symbol. We can determine
// the final value now.
lv_out->set_output_value(
@@ -2589,7 +2620,7 @@ Sized_relobj_file<size, big_endian>::write_local_symbols(
dyn_oview = of->get_output_view(this->local_dynsym_offset_,
dyn_output_size);
- const Output_sections out_sections(this->output_sections());
+ const Output_sections& out_sections(this->output_sections());
gold_assert(this->local_values_.size() == loccount);
diff --git a/gold/object.h b/gold/object.h
index cce6c8c..fe66d1a 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -322,6 +322,8 @@ class Object
{
public:
typedef std::vector<Symbol*> Symbols;
+ typedef std::vector<uint64_t> Offsets_reachable;
+ typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
// NAME is the name of the object as we would report it to the user
// (e.g., libfoo.a(bar.o) if this is in an archive. INPUT_FILE is
@@ -1255,6 +1257,13 @@ class Relobj : public Object
is_big_endian() const
{ return this->do_is_big_endian(); }
+ Offset_ref&
+ referenced_offsets()
+ { return this->referenced_offsets_; }
+
+ bool
+ is_offset_referenced(unsigned int shndx, uint64_t offset, size_t len);
+
protected:
// The output section to be used for each input section, indexed by
// the input section number. The output section is NULL if the
@@ -1454,6 +1463,8 @@ class Relobj : public Object
unsigned int first_dyn_reloc_;
// Count of dynamic relocations for this object.
unsigned int dyn_reloc_count_;
+
+ Offset_ref referenced_offsets_;
};
// This class is used to handle relocations against a section symbol
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..435ee5d 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -637,8 +637,9 @@ Symbol_table::gc_mark_undef_symbols(Layout* layout)
}
}
+template<int size>
void
-Symbol_table::gc_mark_symbol(Symbol* sym)
+Symbol_table::gc_mark_sized_symbol(Sized_symbol<size>* sym)
{
// Add the object and section to the work list.
bool is_ordinary;
@@ -646,11 +647,22 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
{
gold_assert(this->gc_!= NULL);
- this->gc_->worklist().push(Section_id(sym->object(), shndx));
+ this->gc_->worklist().push(Section_id(sym->object(), shndx),
+ sym->value());
}
parameters->target().gc_mark_symbol(this, sym);
}
+void
+Symbol_table::gc_mark_symbol(Symbol* sym)
+{
+ const int size = parameters->target().get_size();
+ if (size == 32)
+ gc_mark_sized_symbol(this->get_sized_symbol<32>(sym));
+ else
+ gc_mark_sized_symbol(this->get_sized_symbol<64>(sym));
+}
+
// When doing garbage collection, keep symbols that have been seen in
// dynamic objects.
inline void
diff --git a/gold/symtab.h b/gold/symtab.h
index aa0cb68..5f245c6 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -1387,6 +1387,10 @@ class Symbol_table
gc_mark_undef_symbols(Layout*);
// This tells garbage collection that this symbol is referenced.
+ template<int size>
+ void
+ gc_mark_sized_symbol(Sized_symbol<size>* sym);
+
void
gc_mark_symbol(Symbol* sym);
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch/rfc][pr17902] GC unused parts of mergeable sections
2015-02-05 15:26 ` Rafael Espíndola
@ 2015-02-06 16:28 ` Rafael Espíndola
2015-02-10 17:36 ` Rafael Espíndola
0 siblings, 1 reply; 5+ messages in thread
From: Rafael Espíndola @ 2015-02-06 16:28 UTC (permalink / raw)
To: Binutils; +Cc: Cary Coutant, Nico Weber
[-- Attachment #1: Type: text/plain, Size: 1091 bytes --]
A new version is attached with just some cleanup on the logic on
whether to keep a local symbol or not.
While working on it I noticed how remarkably similar the code is to
the existing merge map. I now think the merge map can be reused for
this. The plan is:
* During the gc walk, add offset -> -1 mappings. This is similar to
what we do when CIE is dropped.
* In Output_merge_data::do_add_input_section, and
Output_merge_string<Char_type>::do_add_input_section (if gc is enable)
only add entries if a mapping is present.
* Output local symbols only if a mapping is present.
Sounds reasonable or can you thing of a reason why we would need an
independent map?
Cheers,
Rafael
On 5 February 2015 at 10:26, Rafael Espíndola
<rafael.espindola@gmail.com> wrote:
> A new wip version is attached.
>
> In comparison with the previous one, this version
>
> * Handles non-string SHF_MERGE.
> * Handles symbol making part of a section referenced.
> * Mix fixes.
>
> It reduces the .rodata section in chrome from 6985174 to 6851542 bytes.
>
> Cheers,
> Rafael
[-- Attachment #2: t.patch --]
[-- Type: text/x-patch, Size: 15477 bytes --]
diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..c96faf4 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -29,6 +29,34 @@
namespace gold
{
+void Worklist::just_push(const Section_id &val) { this->work_list_.push(val); }
+
+void Worklist::push(const Section_id &val) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ gold_assert((flags & elfcpp::SHF_MERGE) == 0);
+}
+
+void Worklist::push(const Section_id &val, uint64_t offset) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return;
+
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[shndx];
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), offset);
+ // FIXME: duplicated code with Garbage_collection::do_transitive_closure.
+ if (I == offsets.end() || *I != offset)
+ offsets.insert(I, offset);
+}
+
// Garbage collection uses a worklist style algorithm to determine the
// transitive closure of all referenced sections.
void
@@ -63,11 +91,34 @@ Garbage_collection::do_transitive_closure()
if (this->referenced_list().find(*it_v)
== this->referenced_list().end())
{
- this->worklist().push(*it_v);
+ this->worklist().just_push(*it_v);
}
}
}
this->worklist_ready();
+ for (Sections_reachable::iterator I = this->referenced_list().begin(),
+ E = this->referenced_list().end();
+ I != E; ++I) {
+ Atom_reachable &atoms = this->atom_reloc_map()[*I];
+ for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+ I2 != E2; ++I2) {
+ const Atom &atom = *I2;
+ const Section_id id = atom.first;
+ Object* obj = id.first;
+ unsigned int sec_num = id.second;
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[sec_num];
+ uint64_t new_offset = atom.second;
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), new_offset);
+ // FIXME: Consider different algorithms:
+ // just push_back and sort/uniq afterwards
+ // use a set on the side to avoid inserting duplicates
+ if (I == offsets.end() || *I != new_offset)
+ offsets.insert(I, new_offset);
+ }
+ }
}
} // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index 2db7cb9..7effbe1 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -46,18 +46,49 @@ class Output_section;
class General_options;
class Layout;
+class Worklist
+{
+ public:
+ bool empty() const {
+ return work_list_.empty();
+ }
+ Section_id &front() {
+ return work_list_.front();
+ }
+ void pop() {
+ work_list_.pop();
+ }
+ void just_push(const Section_id& val);
+ void push(const Section_id& val);
+ void push(const Section_id& val, uint64_t offset);
+
+ private:
+ typedef std::queue<Section_id> Worklist_type;
+ Worklist_type work_list_;
+};
+
class Garbage_collection
{
public:
typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
typedef std::map<Section_id, Sections_reachable> Section_ref;
- typedef std::queue<Section_id> Worklist_type;
+
// This maps the name of the section which can be represented as a C
// identifier (cident) to the list of sections that have that name.
// Different object files can have cident sections with the same name.
typedef std::map<std::string, Sections_reachable> Cident_section_map;
+ typedef std::pair<Section_id, uint64_t> Atom;
+ struct Atom_hash {
+ size_t operator()(const Atom &a) const {
+ const Section_id &s = a.first;
+ return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+ }
+ };
+ typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+ typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
Garbage_collection()
: is_worklist_ready_(false)
{ }
@@ -72,7 +103,11 @@ class Garbage_collection
section_reloc_map()
{ return this->section_reloc_map_; }
- Worklist_type&
+ Atom_ref&
+ atom_reloc_map()
+ { return this->atom_reloc_map_; }
+
+ Worklist&
worklist()
{ return this->work_list_; }
@@ -116,13 +151,26 @@ class Garbage_collection
p->second.insert(dst_id);
}
+ void add_reference_to_merge_section(Object *src_object,
+ unsigned int src_shndx,
+ Object *dst_object,
+ unsigned int dst_shndx, uint64_t offset) {
+ add_reference(src_object, src_shndx, dst_object, dst_shndx);
+ Section_id src_id(src_object, src_shndx);
+ Section_id dst_id(dst_object, dst_shndx);
+ Atom atom(dst_id, offset);
+ this->atom_reloc_map_[src_id].insert(atom);
+ }
+
private:
- Worklist_type work_list_;
+ Worklist work_list_;
bool is_worklist_ready_;
Section_ref section_reloc_map_;
Sections_reachable referenced_list_;
Cident_section_map cident_sections_;
+
+ Atom_ref atom_reloc_map_;
};
// Data to pass between successive invocations of do_layout
@@ -238,6 +286,10 @@ gc_process_relocs(
typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
Address dst_off;
+ // If the relocation points to a section, this includes the addend.
+ // Otherwise it doesn't.
+ Address gc_ref_off;
+
if (r_sym < local_count)
{
gold_assert(plocal_syms != NULL);
@@ -247,7 +299,10 @@ gc_process_relocs(
bool is_ordinary;
dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
dst_obj = src_obj;
- dst_off = lsym.get_st_value() + addend;
+ gc_ref_off = dst_off = lsym.get_st_value();
+ dst_off += addend;
+ if (lsym.get_st_type() == elfcpp::STT_SECTION)
+ gc_ref_off += addend;
if (is_icf_tracked)
{
@@ -299,6 +354,7 @@ gc_process_relocs(
dst_indx = gsym->shndx(&is_ordinary);
}
dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
+ gc_ref_off = dst_off;
dst_off += addend;
// When doing safe folding, check to see if this relocation is that
@@ -351,7 +407,14 @@ gc_process_relocs(
}
if (parameters->options().gc_sections())
{
- symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+ Garbage_collection* gc = symtab->gc();
+ uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+ if (dst_flags & elfcpp::SHF_MERGE)
+ gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+ dst_indx, gc_ref_off);
+ else
+ gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
parameters->sized_target<size, big_endian>()
->gc_add_reference(symtab, src_obj, src_indx,
dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index f547388..fcb62e4 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -423,6 +423,9 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
for (section_size_type i = 0; i < len; i += entsize, p += entsize)
{
+ if (!object->are_there_any_references_to_range(shndx, i, entsize))
+ continue;
+
// Add the constant to the section contents. If we find that it
// is already in the hash table, we will remove it again.
Merge_data_key k = this->len_;
@@ -567,6 +570,7 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
while (p < pend)
{
size_t len = p < pend0 ? string_length(p) : pend - p;
+ size_t num_bytes = (len + 1) * sizeof(Char_type);
// Within merge input section each string must be aligned.
if (len != 0
@@ -574,12 +578,14 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
!= init_align_modulo))
has_misaligned_strings = true;
- Stringpool::Key key;
- this->stringpool_.add_with_length(p, len, true, &key);
+ if (object->are_there_any_references_to_range(shndx, i, num_bytes)) {
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
- merged_strings.push_back(Merged_string(i, key));
+ merged_strings.push_back(Merged_string(i, key));
+ }
p += len + 1;
- i += (len + 1) * sizeof(Char_type);
+ i += num_bytes;
}
// Record the last offset in the input section so that we can
diff --git a/gold/object.cc b/gold/object.cc
index 8f16fe7..b184a40 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -368,6 +368,51 @@ Relobj::finalize_incremental_relocs(Layout* layout, bool clear_counts)
layout->incremental_inputs()->set_reloc_count(rindex);
}
+bool
+Relobj::are_there_any_references_to_range(unsigned int shndx, uint64_t offset,
+ size_t len) {
+ if (!parameters->options().gc_sections())
+ return true;
+
+ uint64_t flags = this->section_flags(shndx);
+ // We don't gc non alloc sections.
+ if ((flags & elfcpp::SHF_ALLOC) == 0)
+ return true;
+
+ // Only SHF_MERGE sections are partially gced.
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return true;
+
+ Object::Offsets_reachable &offsets = this->referenced_offsets()[shndx];
+ Object::Offsets_reachable::iterator I =
+ std::lower_bound(offsets.begin(), offsets.end(), offset);
+ if (I == offsets.end())
+ return false;
+
+
+ if (*I >= offset + len)
+ return false;
+ return true;
+}
+
+bool Relobj::is_offset_referenced(unsigned int shndx, uint64_t offset) {
+ if (!parameters->options().gc_sections())
+ return true;
+
+ uint64_t flags = this->section_flags(shndx);
+ // We don't gc non alloc sections.
+ if ((flags & elfcpp::SHF_ALLOC) == 0)
+ return true;
+
+ // Only SHF_MERGE sections are partially gced.
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return true;
+
+ // We can't use is_input_address_mapped because finalize_merged_data
+ // has not been called yet and SHF_STRINGS will not have the data.
+ return are_there_any_references_to_range(shndx, offset, /*FIXME*/4);
+}
+
// Class Sized_relobj.
// Iterate over local symbols, calling a visitor class V for each GOT offset
@@ -2154,7 +2199,9 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
// Decide whether this symbol should go into the output file.
- if ((shndx < shnum && out_sections[shndx] == NULL)
+ if ((shndx < shnum
+ && (out_sections[shndx] == NULL ||
+ !this->is_offset_referenced(shndx, sym.get_st_value())))
|| shndx == this->discarded_eh_frame_shndx_)
{
lv.set_no_output_symtab_entry();
@@ -2225,6 +2272,9 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
continue;
}
+ // FIXME: explain
+ lv.set_must_have_output_symtab_entry();
+
// Add the symbol to the symbol table string pool.
pool->add(name, true, NULL);
++count;
@@ -2327,6 +2377,9 @@ Sized_relobj_file<size, big_endian>::compute_final_local_value_internal(
}
else if (!lv_in->is_section_symbol())
{
+ if (!lv_in->will_have_output_symtab_entry())
+ return This::CFLV_DISCARDED;
+
// This is not a section symbol. We can determine
// the final value now.
lv_out->set_output_value(
@@ -2589,7 +2642,7 @@ Sized_relobj_file<size, big_endian>::write_local_symbols(
dyn_oview = of->get_output_view(this->local_dynsym_offset_,
dyn_output_size);
- const Output_sections out_sections(this->output_sections());
+ const Output_sections& out_sections(this->output_sections());
gold_assert(this->local_values_.size() == loccount);
diff --git a/gold/object.h b/gold/object.h
index cce6c8c..45d948b 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -322,6 +322,8 @@ class Object
{
public:
typedef std::vector<Symbol*> Symbols;
+ typedef std::vector<uint64_t> Offsets_reachable;
+ typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
// NAME is the name of the object as we would report it to the user
// (e.g., libfoo.a(bar.o) if this is in an archive. INPUT_FILE is
@@ -1255,6 +1257,17 @@ class Relobj : public Object
is_big_endian() const
{ return this->do_is_big_endian(); }
+ Offset_ref&
+ referenced_offsets()
+ { return this->referenced_offsets_; }
+
+ bool
+ are_there_any_references_to_range(unsigned int shndx, uint64_t offset,
+ size_t len);
+
+ bool
+ is_offset_referenced(unsigned int shndx, uint64_t offset);
+
protected:
// The output section to be used for each input section, indexed by
// the input section number. The output section is NULL if the
@@ -1454,6 +1467,8 @@ class Relobj : public Object
unsigned int first_dyn_reloc_;
// Count of dynamic relocations for this object.
unsigned int dyn_reloc_count_;
+
+ Offset_ref referenced_offsets_;
};
// This class is used to handle relocations against a section symbol
@@ -1661,6 +1676,17 @@ class Symbol_value
return this->output_symtab_index_ != -1U;
}
+ bool
+ will_have_output_symtab_entry() const
+ {
+ // 0 -> we don't know if it will be in the symtab
+ // -1 -> it will not be in the symtab.
+ // -2 -> it will be in the symtab but we don't know where.
+ // other I -> it will be in the symtab at index I
+ gold_assert(this->output_symtab_index_ != 0);
+ return this->output_symtab_index_ != -1U;
+ }
+
// Return the index in the output symbol table.
unsigned int
output_symtab_index() const
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..435ee5d 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -637,8 +637,9 @@ Symbol_table::gc_mark_undef_symbols(Layout* layout)
}
}
+template<int size>
void
-Symbol_table::gc_mark_symbol(Symbol* sym)
+Symbol_table::gc_mark_sized_symbol(Sized_symbol<size>* sym)
{
// Add the object and section to the work list.
bool is_ordinary;
@@ -646,11 +647,22 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
{
gold_assert(this->gc_!= NULL);
- this->gc_->worklist().push(Section_id(sym->object(), shndx));
+ this->gc_->worklist().push(Section_id(sym->object(), shndx),
+ sym->value());
}
parameters->target().gc_mark_symbol(this, sym);
}
+void
+Symbol_table::gc_mark_symbol(Symbol* sym)
+{
+ const int size = parameters->target().get_size();
+ if (size == 32)
+ gc_mark_sized_symbol(this->get_sized_symbol<32>(sym));
+ else
+ gc_mark_sized_symbol(this->get_sized_symbol<64>(sym));
+}
+
// When doing garbage collection, keep symbols that have been seen in
// dynamic objects.
inline void
diff --git a/gold/symtab.h b/gold/symtab.h
index aa0cb68..5f245c6 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -1387,6 +1387,10 @@ class Symbol_table
gc_mark_undef_symbols(Layout*);
// This tells garbage collection that this symbol is referenced.
+ template<int size>
+ void
+ gc_mark_sized_symbol(Sized_symbol<size>* sym);
+
void
gc_mark_symbol(Symbol* sym);
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch/rfc][pr17902] GC unused parts of mergeable sections
2015-02-06 16:28 ` Rafael Espíndola
@ 2015-02-10 17:36 ` Rafael Espíndola
2015-03-31 18:16 ` Rafael Espíndola
0 siblings, 1 reply; 5+ messages in thread
From: Rafael Espíndola @ 2015-02-10 17:36 UTC (permalink / raw)
To: Binutils; +Cc: Cary Coutant, Nico Weber
[-- Attachment #1: Type: text/plain, Size: 309 bytes --]
> While working on it I noticed how remarkably similar the code is to
> the existing merge map. I now think the merge map can be reused for
> this.
A version using the existing merge_map. It still needs cleanups and
tests, but it is probably better to do that after the other patches
are in.
Cheers,
Rafael
[-- Attachment #2: t.patch --]
[-- Type: text/x-patch, Size: 23935 bytes --]
diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..2bf6472 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -25,10 +25,45 @@
#include "object.h"
#include "gc.h"
#include "symtab.h"
+#include "merge.h"
namespace gold
{
+void Worklist::just_push(const Section_id &val) { this->work_list_.push(val); }
+
+void Worklist::push(const Section_id &val) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ gold_assert((flags & elfcpp::SHF_MERGE) == 0);
+}
+
+static void
+add_referenced_offset(Object *obj, unsigned int shndx, uint64_t offset) {
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object_merge_map* object_merge_map = r_obj->get_or_create_merge_map();
+
+ // In the case of strings, findind the start and length requires reading the
+ // contents, which requires decompression. To do that only once,
+ // we record only the reference offset here and computed the start and length
+ // do_add_input_section.
+ object_merge_map->add_reference(shndx, offset);
+}
+
+void Worklist::push(const Section_id &val, uint64_t offset) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return;
+
+ add_referenced_offset(obj, shndx, offset);
+}
+
// Garbage collection uses a worklist style algorithm to determine the
// transitive closure of all referenced sections.
void
@@ -63,11 +98,25 @@ Garbage_collection::do_transitive_closure()
if (this->referenced_list().find(*it_v)
== this->referenced_list().end())
{
- this->worklist().push(*it_v);
+ this->worklist().just_push(*it_v);
}
}
}
this->worklist_ready();
+ for (Sections_reachable::iterator I = this->referenced_list().begin(),
+ E = this->referenced_list().end();
+ I != E; ++I) {
+ Atom_reachable &atoms = this->atom_reloc_map()[*I];
+ for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+ I2 != E2; ++I2) {
+ const Atom &atom = *I2;
+ const Section_id id = atom.first;
+ Object* obj = id.first;
+ unsigned int sec_num = id.second;
+ uint64_t new_offset = atom.second;
+ add_referenced_offset(obj, sec_num, new_offset);
+ }
+ }
}
} // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index 2db7cb9..7effbe1 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -46,18 +46,49 @@ class Output_section;
class General_options;
class Layout;
+class Worklist
+{
+ public:
+ bool empty() const {
+ return work_list_.empty();
+ }
+ Section_id &front() {
+ return work_list_.front();
+ }
+ void pop() {
+ work_list_.pop();
+ }
+ void just_push(const Section_id& val);
+ void push(const Section_id& val);
+ void push(const Section_id& val, uint64_t offset);
+
+ private:
+ typedef std::queue<Section_id> Worklist_type;
+ Worklist_type work_list_;
+};
+
class Garbage_collection
{
public:
typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
typedef std::map<Section_id, Sections_reachable> Section_ref;
- typedef std::queue<Section_id> Worklist_type;
+
// This maps the name of the section which can be represented as a C
// identifier (cident) to the list of sections that have that name.
// Different object files can have cident sections with the same name.
typedef std::map<std::string, Sections_reachable> Cident_section_map;
+ typedef std::pair<Section_id, uint64_t> Atom;
+ struct Atom_hash {
+ size_t operator()(const Atom &a) const {
+ const Section_id &s = a.first;
+ return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+ }
+ };
+ typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+ typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
Garbage_collection()
: is_worklist_ready_(false)
{ }
@@ -72,7 +103,11 @@ class Garbage_collection
section_reloc_map()
{ return this->section_reloc_map_; }
- Worklist_type&
+ Atom_ref&
+ atom_reloc_map()
+ { return this->atom_reloc_map_; }
+
+ Worklist&
worklist()
{ return this->work_list_; }
@@ -116,13 +151,26 @@ class Garbage_collection
p->second.insert(dst_id);
}
+ void add_reference_to_merge_section(Object *src_object,
+ unsigned int src_shndx,
+ Object *dst_object,
+ unsigned int dst_shndx, uint64_t offset) {
+ add_reference(src_object, src_shndx, dst_object, dst_shndx);
+ Section_id src_id(src_object, src_shndx);
+ Section_id dst_id(dst_object, dst_shndx);
+ Atom atom(dst_id, offset);
+ this->atom_reloc_map_[src_id].insert(atom);
+ }
+
private:
- Worklist_type work_list_;
+ Worklist work_list_;
bool is_worklist_ready_;
Section_ref section_reloc_map_;
Sections_reachable referenced_list_;
Cident_section_map cident_sections_;
+
+ Atom_ref atom_reloc_map_;
};
// Data to pass between successive invocations of do_layout
@@ -238,6 +286,10 @@ gc_process_relocs(
typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
Address dst_off;
+ // If the relocation points to a section, this includes the addend.
+ // Otherwise it doesn't.
+ Address gc_ref_off;
+
if (r_sym < local_count)
{
gold_assert(plocal_syms != NULL);
@@ -247,7 +299,10 @@ gc_process_relocs(
bool is_ordinary;
dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
dst_obj = src_obj;
- dst_off = lsym.get_st_value() + addend;
+ gc_ref_off = dst_off = lsym.get_st_value();
+ dst_off += addend;
+ if (lsym.get_st_type() == elfcpp::STT_SECTION)
+ gc_ref_off += addend;
if (is_icf_tracked)
{
@@ -299,6 +354,7 @@ gc_process_relocs(
dst_indx = gsym->shndx(&is_ordinary);
}
dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
+ gc_ref_off = dst_off;
dst_off += addend;
// When doing safe folding, check to see if this relocation is that
@@ -351,7 +407,14 @@ gc_process_relocs(
}
if (parameters->options().gc_sections())
{
- symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+ Garbage_collection* gc = symtab->gc();
+ uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+ if (dst_flags & elfcpp::SHF_MERGE)
+ gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+ dst_indx, gc_ref_off);
+ else
+ gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
parameters->sized_target<size, big_endian>()
->gc_add_reference(symtab, src_obj, src_indx,
dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index 7a532cc..1d3b2b4 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -53,7 +53,7 @@ Object_merge_map::Input_merge_map::add_mapping(
gold_assert(input_offset < entry.input_offset);
gold_assert(input_offset_u + length
<= static_cast<section_size_type>(entry.input_offset));
- this->sorted = false;
+ this->sorted_ = false;
}
else if (entry.input_offset + entry.length == input_offset_u
&& (output_offset == -1
@@ -72,6 +72,61 @@ Object_merge_map::Input_merge_map::add_mapping(
this->entries.push_back(entry);
}
+void
+Object_merge_map::Input_merge_map::add_reference(
+ section_offset_type input_offset) {
+ this->sorted_ = false;
+ Input_merge_entry entry;
+ entry.input_offset = input_offset;
+ entry.length = -1;
+ entry.output_offset = -1;
+ this->entries.push_back(entry);
+}
+
+void
+Object_merge_map::Input_merge_map::ensure_sorted() {
+ if (this->sorted_)
+ return;
+ std::sort(this->entries.begin(), this->entries.end(), Input_merge_less());
+ this->sorted_ = true;
+}
+
+void
+Object_merge_map::Input_merge_map::unique() {
+ ensure_sorted();
+ Entries::iterator I = std::unique(this->entries.begin(), this->entries.end(),
+ Input_merge_same_offset());
+ entries.erase(I, entries.end());
+}
+
+bool
+Object_merge_map::Input_merge_map::get_output_offset(
+ section_offset_type input_offset, section_offset_type *output_offset) {
+ this->ensure_sorted();
+
+ Input_merge_entry entry;
+ entry.input_offset = input_offset;
+ std::vector<Input_merge_entry>::const_iterator p =
+ std::lower_bound(this->entries.begin(), this->entries.end(),
+ entry, Input_merge_less());
+ if (p == this->entries.end() || p->input_offset > input_offset)
+ {
+ if (p == this->entries.begin())
+ return false;
+ --p;
+ gold_assert(p->input_offset <= input_offset);
+ }
+
+ if (input_offset - p->input_offset
+ >= static_cast<section_offset_type>(p->length))
+ return false;
+
+ *output_offset = p->output_offset;
+ if (*output_offset != -1)
+ *output_offset += (input_offset - p->input_offset);
+ return true;
+}
+
// Destructor.
Object_merge_map::~Object_merge_map()
@@ -136,6 +191,12 @@ Object_merge_map::add_mapping(unsigned int shndx,
map->add_mapping(input_offset, length, output_offset);
}
+void Object_merge_map::add_reference(unsigned int shndx,
+ section_offset_type input_offset) {
+ Input_merge_map* map = this->get_or_make_input_merge_map(shndx);
+ map->add_reference(input_offset);
+}
+
// Get the output offset for an input address.
bool
@@ -147,34 +208,7 @@ Object_merge_map::get_output_offset(unsigned int shndx,
if (map == NULL)
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
- >= static_cast<section_offset_type>(p->length))
- return false;
-
- *output_offset = p->output_offset;
- if (*output_offset != -1)
- *output_offset += (input_offset - p->input_offset);
- return true;
+ return map->get_output_offset(input_offset, output_offset);
}
// Initialize a mapping from input offsets to output addresses.
@@ -349,9 +383,42 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
Object_merge_map* merge_map = object->get_or_create_merge_map();
Object_merge_map::Input_merge_map* input_merge_map =
merge_map->get_or_make_input_merge_map(shndx);
+ uint64_t flags = object->section_flags(shndx);
+
+ bool gc = parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ if (gc) {
+ for (Object_merge_map::Input_merge_map::Entries::iterator
+ I = entries.begin(),
+ E = entries.end();
+ I != E; ++I) {
+ I->input_offset &= ~(entsize - 1);
+ I->length = entsize;
+ }
+
+ input_merge_map->unique();
+ }
- for (section_size_type i = 0; i < len; i += entsize, p += entsize)
+ Object_merge_map::Input_merge_map::Entries::iterator entry_i =
+ entries.begin();
+ Object_merge_map::Input_merge_map::Entries::iterator entry_e =
+ entries.end();
+
+ section_offset_type len_u = len;
+ for (section_offset_type i = 0; i < len_u; i += entsize, p += entsize)
{
+ if (gc)
+ {
+ while (entry_i != entry_e && entry_i->input_offset < i)
+ ++entry_i;
+ if (entry_i == entry_e)
+ break;
+ if (entry_i->input_offset != i)
+ continue;
+ }
+
// Add the constant to the section contents. If we find that it
// is already in the hash table, we will remove it again.
Merge_data_key k = this->len_;
@@ -368,7 +435,15 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
}
// Record the offset of this constant in the output section.
- input_merge_map->add_mapping(i, entsize, k);
+ if (gc)
+ {
+ entry_i->length = entsize;
+ entry_i->output_offset = k;
+ }
+ else
+ {
+ input_merge_map->add_mapping(i, entsize, k);
+ }
}
// For script processing, we keep the input sections.
@@ -483,6 +558,31 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
++count;
merged_strings.reserve(count + 1);
+ Object_merge_map* merge_map = object->get_or_create_merge_map();
+ Object_merge_map::Input_merge_map* input_merge_map =
+ merge_map->get_or_make_input_merge_map(shndx);
+
+ uint64_t flags = object->section_flags(shndx);
+ bool gc = parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ if (gc) {
+ for (Object_merge_map::Input_merge_map::Entries::iterator
+ I = entries.begin(),
+ E = entries.end();
+ I != E; ++I) {
+ section_offset_type start_offset = I->input_offset;
+ while (start_offset > 0 && pdata[start_offset - 1] != 0)
+ --start_offset;
+ I->input_offset = start_offset;
+
+ I->length = (string_length(&pdata[start_offset]) + 1) * sizeof(Char_type);
+ }
+
+ input_merge_map->unique();
+ }
+
// The index I is in bytes, not characters.
section_size_type i = 0;
@@ -503,10 +603,12 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
!= init_align_modulo))
has_misaligned_strings = true;
- Stringpool::Key key;
- this->stringpool_.add_with_length(p, len, true, &key);
+ if (object->is_offset_referenced(shndx, i)) {
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
- merged_strings.push_back(Merged_string(i, key));
+ merged_strings.push_back(Merged_string(i, key));
+ }
p += len + 1;
i += (len + 1) * sizeof(Char_type);
}
@@ -552,8 +654,20 @@ Output_merge_string<Char_type>::finalize_merged_data()
section_offset_type last_output_offset = 0;
Relobj *object = (*l)->object;
Object_merge_map* merge_map = object->get_or_create_merge_map();
+ unsigned shndx = (*l)->shndx;
Object_merge_map::Input_merge_map* input_merge_map =
- merge_map->get_or_make_input_merge_map((*l)->shndx);
+ merge_map->get_or_make_input_merge_map(shndx);
+
+ uint64_t flags = object->section_flags(shndx);
+ bool gc =
+ parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ Object_merge_map::Input_merge_map::Entries::iterator entry_i =
+ entries.begin();
+ Object_merge_map::Input_merge_map::Entries::iterator entry_e =
+ entries.end();
for (typename Merged_strings::const_iterator p =
(*l)->merged_strings.begin();
@@ -561,9 +675,20 @@ Output_merge_string<Char_type>::finalize_merged_data()
++p)
{
section_size_type length = p->offset - last_input_offset;
- if (length > 0)
- input_merge_map->add_mapping(last_input_offset, length,
- last_output_offset);
+ if (length > 0) {
+ if (gc) {
+ while (entry_i != entry_e &&
+ entry_i->input_offset < last_input_offset)
+ ++entry_i;
+ if (entry_i == entry_e)
+ break;
+ if (entry_i->input_offset == last_input_offset)
+ entry_i->output_offset = last_output_offset;
+ } else {
+ input_merge_map->add_mapping(last_input_offset, length,
+ last_output_offset);
+ }
+ }
last_input_offset = p->offset;
if (p->stringpool_key != 0)
last_output_offset =
diff --git a/gold/merge.h b/gold/merge.h
index 56c084a..aaa3f5a 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -58,6 +58,9 @@ class Object_merge_map
add_mapping(unsigned int shndx, section_offset_type offset,
section_size_type length, section_offset_type output_offset);
+ void
+ add_reference(unsigned int shndx, section_offset_type offset);
+
// Get the output offset for an input address. MERGE_MAP is the map
// we are looking for, or NULL if we don't care. The input address
// is at offset OFFSET in section SHNDX. This sets *OUTPUT_OFFSET
@@ -97,19 +100,31 @@ class Object_merge_map
// A list of entries for a particular input section.
struct Input_merge_map
{
- void add_mapping(section_offset_type input_offset, section_size_type length,
- section_offset_type output_offset);
+ void
+ add_mapping(section_offset_type input_offset, section_size_type length,
+ section_offset_type output_offset);
+
+ void
+ add_reference(section_offset_type input_offset);
+
+ bool
+ get_output_offset(section_offset_type input_offset,
+ section_offset_type *output_offset);
typedef std::vector<Input_merge_entry> Entries;
// The list of mappings.
Entries entries;
- // Whether the ENTRIES field is sorted by input_offset.
- bool sorted;
Input_merge_map()
- : entries(), sorted(true)
+ : entries(), sorted_(true)
{ }
+
+ void unique();
+ void ensure_sorted();
+ private:
+ // Whether the ENTRIES field is sorted by input_offset.
+ bool sorted_;
};
// Get or make the Input_merge_map to use for the section SHNDX
@@ -119,13 +134,20 @@ class Object_merge_map
private:
// A less-than comparison routine for Input_merge_entry.
- struct Input_merge_compare
+ struct Input_merge_less
{
bool
operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
{ return i1.input_offset < i2.input_offset; }
};
+ struct Input_merge_same_offset
+ {
+ bool
+ operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
+ { return i1.input_offset == i2.input_offset; }
+ };
+
// Map input section indices to merge maps.
typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;
diff --git a/gold/object.cc b/gold/object.cc
index c3eaf77..287a6e3 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -386,6 +386,23 @@ Relobj::finalize_incremental_relocs(Layout* layout, bool clear_counts)
layout->incremental_inputs()->set_reloc_count(rindex);
}
+bool Relobj::is_offset_referenced(unsigned int shndx, uint64_t offset) {
+ if (!parameters->options().gc_sections())
+ return true;
+
+ uint64_t flags = this->section_flags(shndx);
+ // We don't gc non alloc sections.
+ if ((flags & elfcpp::SHF_ALLOC) == 0)
+ return true;
+
+ // Only SHF_MERGE sections are partially gced.
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return true;
+
+ section_offset_type output_offset;
+ return this->merge_output_offset(shndx, offset, &output_offset);
+}
+
Object_merge_map*
Relobj::get_or_create_merge_map()
{
@@ -2180,7 +2197,9 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
// Decide whether this symbol should go into the output file.
- if ((shndx < shnum && out_sections[shndx] == NULL)
+ if ((shndx < shnum
+ && (out_sections[shndx] == NULL ||
+ !this->is_offset_referenced(shndx, sym.get_st_value())))
|| shndx == this->discarded_eh_frame_shndx_)
{
lv.set_no_output_symtab_entry();
@@ -2251,6 +2270,9 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
continue;
}
+ // FIXME: explain
+ lv.set_must_have_output_symtab_entry();
+
// Add the symbol to the symbol table string pool.
pool->add(name, true, NULL);
++count;
@@ -2353,6 +2375,9 @@ Sized_relobj_file<size, big_endian>::compute_final_local_value_internal(
}
else if (!lv_in->is_section_symbol())
{
+ if (!lv_in->will_have_output_symtab_entry())
+ return This::CFLV_DISCARDED;
+
// This is not a section symbol. We can determine
// the final value now.
lv_out->set_output_value(
@@ -2615,7 +2640,7 @@ Sized_relobj_file<size, big_endian>::write_local_symbols(
dyn_oview = of->get_output_view(this->local_dynsym_offset_,
dyn_output_size);
- const Output_sections out_sections(this->output_sections());
+ const Output_sections& out_sections(this->output_sections());
gold_assert(this->local_values_.size() == loccount);
diff --git a/gold/object.h b/gold/object.h
index 167513b..4b2b676 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -323,6 +323,8 @@ class Object
{
public:
typedef std::vector<Symbol*> Symbols;
+ typedef std::vector<uint64_t> Offsets_reachable;
+ typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
// NAME is the name of the object as we would report it to the user
// (e.g., libfoo.a(bar.o) if this is in an archive. INPUT_FILE is
@@ -1260,6 +1262,9 @@ class Relobj : public Object
is_big_endian() const
{ return this->do_is_big_endian(); }
+ bool
+ is_offset_referenced(unsigned int shndx, uint64_t offset);
+
protected:
// The output section to be used for each input section, indexed by
// the input section number. The output section is NULL if the
@@ -1666,6 +1671,17 @@ class Symbol_value
return this->output_symtab_index_ != -1U;
}
+ bool
+ will_have_output_symtab_entry() const
+ {
+ // 0 -> we don't know if it will be in the symtab
+ // -1 -> it will not be in the symtab.
+ // -2 -> it will be in the symtab but we don't know where.
+ // other I -> it will be in the symtab at index I
+ gold_assert(this->output_symtab_index_ != 0);
+ return this->output_symtab_index_ != -1U;
+ }
+
// Return the index in the output symbol table.
unsigned int
output_symtab_index() const
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..435ee5d 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -637,8 +637,9 @@ Symbol_table::gc_mark_undef_symbols(Layout* layout)
}
}
+template<int size>
void
-Symbol_table::gc_mark_symbol(Symbol* sym)
+Symbol_table::gc_mark_sized_symbol(Sized_symbol<size>* sym)
{
// Add the object and section to the work list.
bool is_ordinary;
@@ -646,11 +647,22 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
{
gold_assert(this->gc_!= NULL);
- this->gc_->worklist().push(Section_id(sym->object(), shndx));
+ this->gc_->worklist().push(Section_id(sym->object(), shndx),
+ sym->value());
}
parameters->target().gc_mark_symbol(this, sym);
}
+void
+Symbol_table::gc_mark_symbol(Symbol* sym)
+{
+ const int size = parameters->target().get_size();
+ if (size == 32)
+ gc_mark_sized_symbol(this->get_sized_symbol<32>(sym));
+ else
+ gc_mark_sized_symbol(this->get_sized_symbol<64>(sym));
+}
+
// When doing garbage collection, keep symbols that have been seen in
// dynamic objects.
inline void
diff --git a/gold/symtab.h b/gold/symtab.h
index aa0cb68..5f245c6 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -1387,6 +1387,10 @@ class Symbol_table
gc_mark_undef_symbols(Layout*);
// This tells garbage collection that this symbol is referenced.
+ template<int size>
+ void
+ gc_mark_sized_symbol(Sized_symbol<size>* sym);
+
void
gc_mark_symbol(Symbol* sym);
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch/rfc][pr17902] GC unused parts of mergeable sections
2015-02-10 17:36 ` Rafael Espíndola
@ 2015-03-31 18:16 ` Rafael Espíndola
0 siblings, 0 replies; 5+ messages in thread
From: Rafael Espíndola @ 2015-03-31 18:16 UTC (permalink / raw)
To: Binutils; +Cc: Cary Coutant, Nico Weber
[-- Attachment #1: Type: text/plain, Size: 991 bytes --]
And now that all the refactoring is in, here is a patch with just the GC.
The size savings are still the same: chromium's .rodata goes from
6985174 to 6851542 bytes.
The link time with --gc-secitons -O1 (probably the setup that makes
the cost of this patch most evident) goes from
6.422498558 seconds time elapsed
( +- 0.37% )
to
6.808367419 seconds time elapsed
( +- 0.22% )
What should be done for testing? Is it OK to write tests in assembly?
It is somewhat brittle to try to convince a C compiler to output a
dead string in a small test.
I will be cleaning up and trying to optimize this patch, but it would
be really nice to get feedback on whether the general idea is
reasonable. It is: if doing gc, use the gc pass to record which
offsets of a given SHF_MERGE section are used. That is stored with
dummy entries in the same maps that are use to merge the contents.
During regular SHF_MERGE processing, only include entries that are
already in the map.
Cheers,
Rafael
[-- Attachment #2: t.patch --]
[-- Type: text/x-patch, Size: 20520 bytes --]
diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..2bf6472 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -25,10 +25,45 @@
#include "object.h"
#include "gc.h"
#include "symtab.h"
+#include "merge.h"
namespace gold
{
+void Worklist::just_push(const Section_id &val) { this->work_list_.push(val); }
+
+void Worklist::push(const Section_id &val) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ gold_assert((flags & elfcpp::SHF_MERGE) == 0);
+}
+
+static void
+add_referenced_offset(Object *obj, unsigned int shndx, uint64_t offset) {
+ // FIXME: what is the safe way to do this cast?
+ Relobj* r_obj = static_cast<Relobj*>(obj);
+ Object_merge_map* object_merge_map = r_obj->get_or_create_merge_map();
+
+ // In the case of strings, findind the start and length requires reading the
+ // contents, which requires decompression. To do that only once,
+ // we record only the reference offset here and computed the start and length
+ // do_add_input_section.
+ object_merge_map->add_reference(shndx, offset);
+}
+
+void Worklist::push(const Section_id &val, uint64_t offset) {
+ this->work_list_.push(val);
+ Object *obj = val.first;
+ unsigned int shndx = val.second;
+ uint64_t flags = obj->section_flags(shndx);
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return;
+
+ add_referenced_offset(obj, shndx, offset);
+}
+
// Garbage collection uses a worklist style algorithm to determine the
// transitive closure of all referenced sections.
void
@@ -63,11 +98,25 @@ Garbage_collection::do_transitive_closure()
if (this->referenced_list().find(*it_v)
== this->referenced_list().end())
{
- this->worklist().push(*it_v);
+ this->worklist().just_push(*it_v);
}
}
}
this->worklist_ready();
+ for (Sections_reachable::iterator I = this->referenced_list().begin(),
+ E = this->referenced_list().end();
+ I != E; ++I) {
+ Atom_reachable &atoms = this->atom_reloc_map()[*I];
+ for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+ I2 != E2; ++I2) {
+ const Atom &atom = *I2;
+ const Section_id id = atom.first;
+ Object* obj = id.first;
+ unsigned int sec_num = id.second;
+ uint64_t new_offset = atom.second;
+ add_referenced_offset(obj, sec_num, new_offset);
+ }
+ }
}
} // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index be4a63c..9bc0a1d 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -46,18 +46,49 @@ class Output_section;
class General_options;
class Layout;
+class Worklist
+{
+ public:
+ bool empty() const {
+ return work_list_.empty();
+ }
+ Section_id &front() {
+ return work_list_.front();
+ }
+ void pop() {
+ work_list_.pop();
+ }
+ void just_push(const Section_id& val);
+ void push(const Section_id& val);
+ void push(const Section_id& val, uint64_t offset);
+
+ private:
+ typedef std::queue<Section_id> Worklist_type;
+ Worklist_type work_list_;
+};
+
class Garbage_collection
{
public:
typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
typedef std::map<Section_id, Sections_reachable> Section_ref;
- typedef std::queue<Section_id> Worklist_type;
+
// This maps the name of the section which can be represented as a C
// identifier (cident) to the list of sections that have that name.
// Different object files can have cident sections with the same name.
typedef std::map<std::string, Sections_reachable> Cident_section_map;
+ typedef std::pair<Section_id, uint64_t> Atom;
+ struct Atom_hash {
+ size_t operator()(const Atom &a) const {
+ const Section_id &s = a.first;
+ return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+ }
+ };
+ typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+ typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
Garbage_collection()
: is_worklist_ready_(false)
{ }
@@ -72,7 +103,11 @@ class Garbage_collection
section_reloc_map()
{ return this->section_reloc_map_; }
- Worklist_type&
+ Atom_ref&
+ atom_reloc_map()
+ { return this->atom_reloc_map_; }
+
+ Worklist&
worklist()
{ return this->work_list_; }
@@ -113,13 +148,26 @@ class Garbage_collection
reachable.insert(dst_id);
}
+ void add_reference_to_merge_section(Object *src_object,
+ unsigned int src_shndx,
+ Object *dst_object,
+ unsigned int dst_shndx, uint64_t offset) {
+ add_reference(src_object, src_shndx, dst_object, dst_shndx);
+ Section_id src_id(src_object, src_shndx);
+ Section_id dst_id(dst_object, dst_shndx);
+ Atom atom(dst_id, offset);
+ this->atom_reloc_map_[src_id].insert(atom);
+ }
+
private:
- Worklist_type work_list_;
+ Worklist work_list_;
bool is_worklist_ready_;
Section_ref section_reloc_map_;
Sections_reachable referenced_list_;
Cident_section_map cident_sections_;
+
+ Atom_ref atom_reloc_map_;
};
// Data to pass between successive invocations of do_layout
@@ -235,6 +283,10 @@ gc_process_relocs(
typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
Address dst_off;
+ // If the relocation points to a section, this includes the addend.
+ // Otherwise it doesn't.
+ Address gc_ref_off;
+
if (r_sym < local_count)
{
gold_assert(plocal_syms != NULL);
@@ -244,7 +296,10 @@ gc_process_relocs(
bool is_ordinary;
dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
dst_obj = src_obj;
- dst_off = lsym.get_st_value() + addend;
+ gc_ref_off = dst_off = lsym.get_st_value();
+ dst_off += addend;
+ if (lsym.get_st_type() == elfcpp::STT_SECTION)
+ gc_ref_off += addend;
if (is_icf_tracked)
{
@@ -296,6 +351,7 @@ gc_process_relocs(
dst_indx = gsym->shndx(&is_ordinary);
}
dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
+ gc_ref_off = dst_off;
dst_off += addend;
// When doing safe folding, check to see if this relocation is that
@@ -348,7 +404,14 @@ gc_process_relocs(
}
if (parameters->options().gc_sections())
{
- symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+ Garbage_collection* gc = symtab->gc();
+ uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+ if (dst_flags & elfcpp::SHF_MERGE)
+ gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+ dst_indx, gc_ref_off);
+ else
+ gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
parameters->sized_target<size, big_endian>()
->gc_add_reference(symtab, src_obj, src_indx,
dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index d395312..b8688e6 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -33,6 +33,33 @@ namespace gold
// Class Object_merge_map.
+void
+Object_merge_map::Input_merge_map::add_reference(
+ section_offset_type input_offset) {
+ this->sorted = false;
+ Input_merge_entry entry;
+ entry.input_offset = input_offset;
+ entry.length = -1;
+ entry.output_offset = -1;
+ this->entries.push_back(entry);
+}
+
+void
+Object_merge_map::Input_merge_map::ensure_sorted() {
+ if (this->sorted)
+ return;
+ std::sort(this->entries.begin(), this->entries.end(), Input_merge_compare());
+ this->sorted = true;
+}
+
+void
+Object_merge_map::Input_merge_map::unique() {
+ ensure_sorted();
+ Entries::iterator I = std::unique(this->entries.begin(), this->entries.end(),
+ Input_merge_same_offset());
+ entries.erase(I, entries.end());
+}
+
// Destructor.
Object_merge_map::~Object_merge_map()
@@ -69,7 +96,11 @@ Object_merge_map::get_or_make_input_merge_map(
{
// For a given input section in a given object, every mapping
// must be done with the same Merge_map.
- gold_assert(map->output_data == output_data);
+ // FIXME: comment
+ if (map->output_data == NULL)
+ map->output_data = output_data;
+ else
+ gold_assert(map->output_data == output_data);
return map;
}
@@ -145,6 +176,12 @@ Object_merge_map::Input_merge_map::add_mapping(
this->entries.push_back(entry);
}
+void Object_merge_map::add_reference(unsigned int shndx,
+ section_offset_type input_offset) {
+ Input_merge_map* map = this->get_or_make_input_merge_map(NULL, shndx);
+ map->add_reference(input_offset);
+}
+
// Get the output offset for an input address.
bool
@@ -156,12 +193,7 @@ Object_merge_map::get_output_offset(unsigned int shndx,
if (map == NULL)
return false;
- if (!map->sorted)
- {
- std::sort(map->entries.begin(), map->entries.end(),
- Input_merge_compare());
- map->sorted = true;
- }
+ map->ensure_sorted();
Input_merge_entry entry;
entry.input_offset = input_offset;
@@ -366,9 +398,42 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
Object_merge_map* merge_map = object->get_or_create_merge_map();
Object_merge_map::Input_merge_map* input_merge_map =
merge_map->get_or_make_input_merge_map(this, shndx);
+ uint64_t flags = object->section_flags(shndx);
+
+ bool gc = parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ if (gc) {
+ for (Object_merge_map::Input_merge_map::Entries::iterator
+ I = entries.begin(),
+ E = entries.end();
+ I != E; ++I) {
+ I->input_offset &= ~(entsize - 1);
+ I->length = entsize;
+ }
+
+ input_merge_map->unique();
+ }
+
+ Object_merge_map::Input_merge_map::Entries::iterator entry_i =
+ entries.begin();
+ Object_merge_map::Input_merge_map::Entries::iterator entry_e =
+ entries.end();
- for (section_size_type i = 0; i < len; i += entsize, p += entsize)
+ section_offset_type len_u = len;
+ for (section_offset_type i = 0; i < len_u; i += entsize, p += entsize)
{
+ if (gc)
+ {
+ while (entry_i != entry_e && entry_i->input_offset < i)
+ ++entry_i;
+ if (entry_i == entry_e)
+ break;
+ if (entry_i->input_offset != i)
+ continue;
+ }
+
// Add the constant to the section contents. If we find that it
// is already in the hash table, we will remove it again.
Merge_data_key k = this->len_;
@@ -385,7 +450,15 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
}
// Record the offset of this constant in the output section.
- input_merge_map->add_mapping(i, entsize, k);
+ if (gc)
+ {
+ entry_i->length = entsize;
+ entry_i->output_offset = k;
+ }
+ else
+ {
+ input_merge_map->add_mapping(i, entsize, k);
+ }
}
// For script processing, we keep the input sections.
@@ -500,6 +573,31 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
++count;
merged_strings.reserve(count + 1);
+ Object_merge_map* merge_map = object->get_or_create_merge_map();
+ Object_merge_map::Input_merge_map* input_merge_map =
+ merge_map->get_or_make_input_merge_map(this, shndx);
+
+ uint64_t flags = object->section_flags(shndx);
+ bool gc = parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ if (gc) {
+ for (Object_merge_map::Input_merge_map::Entries::iterator
+ I = entries.begin(),
+ E = entries.end();
+ I != E; ++I) {
+ section_offset_type start_offset = I->input_offset;
+ while (start_offset > 0 && pdata[start_offset - 1] != 0)
+ --start_offset;
+ I->input_offset = start_offset;
+
+ I->length = (string_length(&pdata[start_offset]) + 1) * sizeof(Char_type);
+ }
+
+ input_merge_map->unique();
+ }
+
// The index I is in bytes, not characters.
section_size_type i = 0;
@@ -520,10 +618,12 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
!= init_align_modulo))
has_misaligned_strings = true;
- Stringpool::Key key;
- this->stringpool_.add_with_length(p, len, true, &key);
+ if (object->is_offset_referenced(shndx, i)) {
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
- merged_strings.push_back(Merged_string(i, key));
+ merged_strings.push_back(Merged_string(i, key));
+ }
p += len + 1;
i += (len + 1) * sizeof(Char_type);
}
@@ -569,8 +669,20 @@ Output_merge_string<Char_type>::finalize_merged_data()
section_offset_type last_output_offset = 0;
Relobj *object = (*l)->object;
Object_merge_map* merge_map = object->get_or_create_merge_map();
+ unsigned shndx = (*l)->shndx;
Object_merge_map::Input_merge_map* input_merge_map =
- merge_map->get_or_make_input_merge_map(this, (*l)->shndx);
+ merge_map->get_or_make_input_merge_map(this, shndx);
+
+ uint64_t flags = object->section_flags(shndx);
+ bool gc =
+ parameters->options().gc_sections() && (flags & elfcpp::SHF_ALLOC);
+ Object_merge_map::Input_merge_map::Entries &entries =
+ input_merge_map->entries;
+
+ Object_merge_map::Input_merge_map::Entries::iterator entry_i =
+ entries.begin();
+ Object_merge_map::Input_merge_map::Entries::iterator entry_e =
+ entries.end();
for (typename Merged_strings::const_iterator p =
(*l)->merged_strings.begin();
@@ -578,10 +690,21 @@ Output_merge_string<Char_type>::finalize_merged_data()
++p)
{
section_size_type length = p->offset - last_input_offset;
- if (length > 0)
- input_merge_map->add_mapping(last_input_offset, length,
- last_output_offset);
- last_input_offset = p->offset;
+ if (length > 0) {
+ if (gc) {
+ while (entry_i != entry_e &&
+ entry_i->input_offset < last_input_offset)
+ ++entry_i;
+ if (entry_i == entry_e)
+ break;
+ if (entry_i->input_offset == last_input_offset)
+ entry_i->output_offset = last_output_offset;
+ } else {
+ input_merge_map->add_mapping(last_input_offset, length,
+ last_output_offset);
+ }
+ }
+ last_input_offset = p->offset;
if (p->stringpool_key != 0)
last_output_offset =
this->stringpool_.get_offset_from_key(p->stringpool_key);
diff --git a/gold/merge.h b/gold/merge.h
index 54caed8..3c68a5c 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -59,6 +59,9 @@ class Object_merge_map
section_offset_type offset, section_size_type length,
section_offset_type output_offset);
+ void
+ add_reference(unsigned int shndx, section_offset_type offset);
+
// Get the output offset for an input address. MERGE_MAP is the map
// we are looking for, or NULL if we don't care. The input address
// is at offset OFFSET in section SHNDX. This sets *OUTPUT_OFFSET
@@ -104,6 +107,9 @@ class Object_merge_map
void add_mapping(section_offset_type input_offset, section_size_type length,
section_offset_type output_offset);
+ void
+ add_reference(section_offset_type input_offset);
+
typedef std::vector<Input_merge_entry> Entries;
// We store these with the Relobj, and we look them up by input
@@ -134,6 +140,9 @@ class Object_merge_map
Input_merge_map()
: output_data(NULL), entries(), sorted(true)
{ }
+
+ void unique();
+ void ensure_sorted();
};
// Get or make the Input_merge_map to use for the section SHNDX
@@ -151,6 +160,13 @@ class Object_merge_map
{ return i1.input_offset < i2.input_offset; }
};
+ struct Input_merge_same_offset
+ {
+ bool
+ operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
+ { return i1.input_offset == i2.input_offset; }
+ };
+
// Map input section indices to merge maps.
typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;
diff --git a/gold/object.cc b/gold/object.cc
index f28305b..8a3b040 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -406,6 +406,23 @@ Relobj::finalize_incremental_relocs(Layout* layout, bool clear_counts)
layout->incremental_inputs()->set_reloc_count(rindex);
}
+bool Relobj::is_offset_referenced(unsigned int shndx, uint64_t offset) {
+ if (!parameters->options().gc_sections())
+ return true;
+
+ uint64_t flags = this->section_flags(shndx);
+ // We don't gc non alloc sections.
+ if ((flags & elfcpp::SHF_ALLOC) == 0)
+ return true;
+
+ // Only SHF_MERGE sections are partially gced.
+ if ((flags & elfcpp::SHF_MERGE) == 0)
+ return true;
+
+ section_offset_type output_offset;
+ return this->merge_output_offset(shndx, offset, &output_offset);
+}
+
Object_merge_map*
Relobj::get_or_create_merge_map()
{
@@ -2205,7 +2222,9 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
// Decide whether this symbol should go into the output file.
- if ((shndx < shnum && out_sections[shndx] == NULL)
+ if ((shndx < shnum
+ && (out_sections[shndx] == NULL ||
+ !this->is_offset_referenced(shndx, sym.get_st_value())))
|| shndx == this->discarded_eh_frame_shndx_)
{
lv.set_no_output_symtab_entry();
@@ -2378,6 +2397,9 @@ Sized_relobj_file<size, big_endian>::compute_final_local_value_internal(
}
else if (!lv_in->is_section_symbol())
{
+ if (!this->is_offset_referenced(shndx, lv_in->input_value()))
+ return This::CFLV_DISCARDED;
+
// This is not a section symbol. We can determine
// the final value now.
lv_out->set_output_value(
diff --git a/gold/object.h b/gold/object.h
index fc93abd..1ee1e2d 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -338,6 +338,8 @@ class Object
{
public:
typedef std::vector<Symbol*> Symbols;
+ typedef std::vector<uint64_t> Offsets_reachable;
+ typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
// NAME is the name of the object as we would report it to the user
// (e.g., libfoo.a(bar.o) if this is in an archive. INPUT_FILE is
@@ -1280,6 +1282,9 @@ class Relobj : public Object
is_big_endian() const
{ return this->do_is_big_endian(); }
+ bool
+ is_offset_referenced(unsigned int shndx, uint64_t offset);
+
protected:
// The output section to be used for each input section, indexed by
// the input section number. The output section is NULL if the
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..435ee5d 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -637,8 +637,9 @@ Symbol_table::gc_mark_undef_symbols(Layout* layout)
}
}
+template<int size>
void
-Symbol_table::gc_mark_symbol(Symbol* sym)
+Symbol_table::gc_mark_sized_symbol(Sized_symbol<size>* sym)
{
// Add the object and section to the work list.
bool is_ordinary;
@@ -646,11 +647,22 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
{
gold_assert(this->gc_!= NULL);
- this->gc_->worklist().push(Section_id(sym->object(), shndx));
+ this->gc_->worklist().push(Section_id(sym->object(), shndx),
+ sym->value());
}
parameters->target().gc_mark_symbol(this, sym);
}
+void
+Symbol_table::gc_mark_symbol(Symbol* sym)
+{
+ const int size = parameters->target().get_size();
+ if (size == 32)
+ gc_mark_sized_symbol(this->get_sized_symbol<32>(sym));
+ else
+ gc_mark_sized_symbol(this->get_sized_symbol<64>(sym));
+}
+
// When doing garbage collection, keep symbols that have been seen in
// dynamic objects.
inline void
diff --git a/gold/symtab.h b/gold/symtab.h
index 9413360..1d4a2e8 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -1385,6 +1385,10 @@ class Symbol_table
gc_mark_undef_symbols(Layout*);
// This tells garbage collection that this symbol is referenced.
+ template<int size>
+ void
+ gc_mark_sized_symbol(Sized_symbol<size>* sym);
+
void
gc_mark_symbol(Symbol* sym);
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2015-03-31 18:16 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-02-03 16:11 [patch/rfc][pr17902] GC unused parts of mergeable sections Rafael Espíndola
2015-02-05 15:26 ` Rafael Espíndola
2015-02-06 16:28 ` Rafael Espíndola
2015-02-10 17:36 ` Rafael Espíndola
2015-03-31 18:16 ` Rafael Espíndola
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).