X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gold%2Ficf.cc;h=a49ce2e960ffb6ac9764830f11145d045abba216;hb=4f501a245f67d0b43f245b09515c87bfeec983ec;hp=39334a579a788dd9d5b8d14a966aff22ef3dc0f3;hpb=91d6fa6a035cc7d0b7be5c99c194a64cb80924b0;p=deliverable%2Fbinutils-gdb.git diff --git a/gold/icf.cc b/gold/icf.cc index 39334a579a..a49ce2e960 100644 --- a/gold/icf.cc +++ b/gold/icf.cc @@ -1,6 +1,6 @@ // icf.cc -- Identical Code Folding. // -// Copyright 2009 Free Software Foundation, Inc. +// Copyright (C) 2009-2017 Free Software Foundation, Inc. // Written by Sriraman Tallam . // This file is part of gold. @@ -23,7 +23,7 @@ // Identical Code Folding Algorithm // ---------------------------------- // Detecting identical functions is done here and the basic algorithm -// is as follows. A checksum is computed on each .text section using +// is as follows. A checksum is computed on each foldable section using // its contents and relocations. If the symbol name corresponding to // a relocation is known it is used to compute the checksum. If the // symbol name is not known the stringified name of the object and the @@ -34,8 +34,8 @@ // checking the contents when two sections have the same checksum. // // However, two functions A and B with identical text but with -// relocations pointing to different .text sections can be identical if -// the corresponding .text sections to which their relocations point to +// relocations pointing to different foldable sections can be identical if +// the corresponding foldable sections to which their relocations point to // turn out to be identical. Hence, this checksumming process must be // done repeatedly until convergence is obtained. Here is an example for // the following case : @@ -101,8 +101,38 @@ // when folding takes place. This could lead to unexpected run-time // behaviour. // +// Safe Folding : +// ------------ +// +// ICF in safe mode folds only ctors and dtors if their function pointers can +// never be taken. Also, for X86-64, safe folding uses the relocation +// type to determine if a function's pointer is taken or not and only folds +// functions whose pointers are definitely not taken. +// +// Caveat with safe folding : +// ------------------------ +// +// This applies only to x86_64. +// +// Position independent executables are created from PIC objects (compiled +// with -fPIC) and/or PIE objects (compiled with -fPIE). For PIE objects, the +// relocation types for function pointer taken and a call are the same. +// Now, it is not always possible to tell if an object used in the link of +// a pie executable is a PIC object or a PIE object. Hence, for pie +// executables, using relocation types to disambiguate function pointers is +// currently disabled. +// +// Further, it is not correct to use safe folding to build non-pie +// executables using PIC/PIE objects. PIC/PIE objects have different +// relocation types for function pointers than non-PIC objects, and the +// current implementation of safe folding does not handle those relocation +// types. Hence, if used, functions whose pointers are taken could still be +// folded causing unpredictable run-time behaviour if the pointers were used +// in comparisons. // -// How to run : --icf +// +// +// How to run : --icf=[safe|all|none] // Optional parameters : --icf-iterations --print-icf-sections // // Performance : Less than 20 % link-time overhead on industry strength @@ -115,6 +145,8 @@ #include "symtab.h" #include "libiberty.h" #include "demangle.h" +#include "elfcpp.h" +#include "int_encoding.h" namespace gold { @@ -150,6 +182,11 @@ preprocess_for_unique_sections(const std::vector& id_section, section_size_type plen; if (section_contents == NULL) { + // Lock the object so we can read from it. This is only called + // single-threaded from queue_middle_tasks, so it is OK to lock. + // Unfortunately we have no way to pass in a Task token. + const Task* dummy_task = reinterpret_cast(-1); + Task_lock_obj tl(dummy_task, secn.first); const unsigned char* contents; contents = secn.first->section_contents(secn.second, &plen, @@ -176,6 +213,45 @@ preprocess_for_unique_sections(const std::vector& id_section, } } +// For SHF_MERGE sections that use REL relocations, the addend is stored in +// the text section at the relocation offset. Read the addend value given +// the pointer to the addend in the text section and the addend size. +// Update the addend value if a valid addend is found. +// Parameters: +// RELOC_ADDEND_PTR : Pointer to the addend in the text section. +// ADDEND_SIZE : The size of the addend. +// RELOC_ADDEND_VALUE : Pointer to the addend that is updated. + +inline void +get_rel_addend(const unsigned char* reloc_addend_ptr, + const unsigned int addend_size, + uint64_t* reloc_addend_value) +{ + switch (addend_size) + { + case 0: + break; + case 1: + *reloc_addend_value = + read_from_pointer<8>(reloc_addend_ptr); + break; + case 2: + *reloc_addend_value = + read_from_pointer<16>(reloc_addend_ptr); + break; + case 4: + *reloc_addend_value = + read_from_pointer<32>(reloc_addend_ptr); + break; + case 8: + *reloc_addend_value = + read_from_pointer<64>(reloc_addend_ptr); + break; + default: + gold_unreachable(); + } +} + // This returns the buffer containing the section's contents, both // text and relocs. Relocs are differentiated as those pointing to // sections that could be folded and those that cannot. Only relocs @@ -200,15 +276,16 @@ get_section_contents(bool first_iteration, const std::vector& kept_section_id, std::vector* section_contents) { + // Lock the object so we can read from it. This is only called + // single-threaded from queue_middle_tasks, so it is OK to lock. + // Unfortunately we have no way to pass in a Task token. + const Task* dummy_task = reinterpret_cast(-1); + Task_lock_obj tl(dummy_task, secn.first); + section_size_type plen; const unsigned char* contents = NULL; - if (first_iteration) - { - contents = secn.first->section_contents(secn.second, - &plen, - false); - } + contents = secn.first->section_contents(secn.second, &plen, false); // The buffer to hold all the contents including relocs. A checksum // is then computed on this buffer. @@ -218,39 +295,87 @@ get_section_contents(bool first_iteration, if (num_tracked_relocs) *num_tracked_relocs = 0; - Icf::Section_list& seclist = symtab->icf()->section_reloc_list(); - Icf::Symbol_list& symlist = symtab->icf()->symbol_reloc_list(); - Icf::Addend_list& addendlist = symtab->icf()->addend_reloc_list(); + Icf::Reloc_info_list& reloc_info_list = + symtab->icf()->reloc_info_list(); - Icf::Section_list::iterator it_seclist = seclist.find(secn); - Icf::Symbol_list::iterator it_symlist = symlist.find(secn); - Icf::Addend_list::iterator it_addendlist = addendlist.find(secn); + Icf::Reloc_info_list::iterator it_reloc_info_list = + reloc_info_list.find(secn); buffer.clear(); icf_reloc_buffer.clear(); // Process relocs and put them into the buffer. - if (it_seclist != seclist.end()) + if (it_reloc_info_list != reloc_info_list.end()) { - gold_assert(it_symlist != symlist.end()); - gold_assert(it_addendlist != addendlist.end()); - Icf::Sections_reachable_list v = it_seclist->second; - Icf::Symbol_info s = it_symlist->second; - Icf::Addend_info a = it_addendlist->second; - Icf::Sections_reachable_list::iterator it_v = v.begin(); - Icf::Symbol_info::iterator it_s = s.begin(); + Icf::Sections_reachable_info &v = + (it_reloc_info_list->second).section_info; + // Stores the information of the symbol pointed to by the reloc. + const Icf::Symbol_info &s = (it_reloc_info_list->second).symbol_info; + // Stores the addend and the symbol value. + Icf::Addend_info &a = (it_reloc_info_list->second).addend_info; + // Stores the offset of the reloc. + const Icf::Offset_info &o = (it_reloc_info_list->second).offset_info; + const Icf::Reloc_addend_size_info &reloc_addend_size_info = + (it_reloc_info_list->second).reloc_addend_size_info; + Icf::Sections_reachable_info::iterator it_v = v.begin(); + Icf::Symbol_info::const_iterator it_s = s.begin(); Icf::Addend_info::iterator it_a = a.begin(); + Icf::Offset_info::const_iterator it_o = o.begin(); + Icf::Reloc_addend_size_info::const_iterator it_addend_size = + reloc_addend_size_info.begin(); - for (; it_v != v.end(); ++it_v, ++it_s, ++it_a) + for (; it_v != v.end(); ++it_v, ++it_s, ++it_a, ++it_o, ++it_addend_size) { - // ADDEND_STR stores the symbol value and addend, each - // atmost 16 hex digits long. it_v points to a pair + if (first_iteration + && it_v->first != NULL) + { + Symbol_location loc; + loc.object = it_v->first; + loc.shndx = it_v->second; + loc.offset = convert_types(it_a->first + + it_a->second); + // Look through function descriptors + parameters->target().function_location(&loc); + if (loc.shndx != it_v->second) + { + it_v->second = loc.shndx; + // Modify symvalue/addend to the code entry. + it_a->first = loc.offset; + it_a->second = 0; + } + } + + // ADDEND_STR stores the symbol value and addend and offset, + // each at most 16 hex digits long. it_a points to a pair // where first is the symbol value and second is the // addend. - char addend_str[34]; - snprintf(addend_str, sizeof(addend_str), "%llx %llx", - (*it_a).first, (*it_a).second); + char addend_str[50]; + + // It would be nice if we could use format macros in inttypes.h + // here but there are not in ISO/IEC C++ 1998. + snprintf(addend_str, sizeof(addend_str), "%llx %llx %llux", + static_cast((*it_a).first), + static_cast((*it_a).second), + static_cast(*it_o)); + + // If the symbol pointed to by the reloc is not in an ordinary + // section or if the symbol type is not FROM_OBJECT, then the + // object is NULL. + if (it_v->first == NULL) + { + if (first_iteration) + { + // If the symbol name is available, use it. + if ((*it_s) != NULL) + buffer.append((*it_s)->name()); + // Append the addend. + buffer.append(addend_str); + buffer.append("@"); + } + continue; + } + Section_id reloc_secn(it_v->first, it_v->second); // If this reloc turns back and points to the same section, @@ -270,7 +395,12 @@ get_section_contents(bool first_iteration, symtab->icf()->section_to_int_map(); Icf::Uniq_secn_id_map::iterator section_id_map_it = section_id_map.find(reloc_secn); - if (section_id_map_it != section_id_map.end()) + bool is_sym_preemptible = (*it_s != NULL + && !(*it_s)->is_from_dynobj() + && !(*it_s)->is_undefined() + && (*it_s)->is_preemptible()); + if (!is_sym_preemptible + && section_id_map_it != section_id_map.end()) { // This is a reloc to a section that might be folded. if (num_tracked_relocs) @@ -300,16 +430,42 @@ get_section_contents(bool first_iteration, uint64_t secn_flags = (it_v->first)->section_flags(it_v->second); // This reloc points to a merge section. Hash the // contents of this section. - if ((secn_flags & elfcpp::SHF_MERGE) != 0) + if ((secn_flags & elfcpp::SHF_MERGE) != 0 + && parameters->target().can_icf_inline_merge_sections()) { uint64_t entsize = (it_v->first)->section_entsize(it_v->second); - long long offset = it_a->first + it_a->second; + long long offset = it_a->first; + // Handle SHT_RELA and SHT_REL addends, only one of these + // addends exists. + // Get the SHT_RELA addend. For RELA relocations, we have + // the addend from the relocation. + uint64_t reloc_addend_value = it_a->second; + + // Handle SHT_REL addends. + // For REL relocations, we need to fetch the addend from the + // section contents. + const unsigned char* reloc_addend_ptr = + contents + static_cast(*it_o); + + // Update the addend value with the SHT_REL addend if + // available. + get_rel_addend(reloc_addend_ptr, *it_addend_size, + &reloc_addend_value); + + // Ignore the addend when it is a negative value. See the + // comments in Merged_symbol_value::value in object.h. + if (reloc_addend_value < 0xffffff00) + offset = offset + reloc_addend_value; + section_size_type secn_len; + const unsigned char* str_contents = (it_v->first)->section_contents(it_v->second, &secn_len, false) + offset; + gold_assert (offset < (long long) secn_len); + if ((secn_flags & elfcpp::SHF_STRINGS) != 0) { // String merge section. @@ -350,17 +506,21 @@ get_section_contents(bool first_iteration, } else { - // Use the entsize to determine the length. - buffer.append(reinterpret_cast secn_len) + bufsize = secn_len - offset; + buffer.append(reinterpret_cast(str_contents), - entsize); + bufsize); } + buffer.append("@"); } else if ((*it_s) != NULL) { // If symbol name is available use that. - const char *sym_name = (*it_s)->name(); - buffer.append(sym_name); + buffer.append((*it_s)->name()); // Append the addend. buffer.append(addend_str); buffer.append("@"); @@ -385,7 +545,7 @@ get_section_contents(bool first_iteration, { buffer.append("Contents = "); buffer.append(reinterpret_cast(contents), plen); - // Store the section contents that dont change to avoid recomputing + // Store the section contents that don't change to avoid recomputing // during the next call to this function. (*section_contents)[section_num] = buffer; } @@ -420,7 +580,7 @@ get_section_contents(bool first_iteration, // KEPT_SECTION_ID : Vector which maps folded sections to kept sections. // ID_SECTION : Vector mapping a section to an unique integer. // IS_SECN_OR_GROUP_UNIQUE : To check if a section or a group of identical -// sectionsis already known to be unique. +// sections is already known to be unique. // SECTION_CONTENTS : Store the section's text and relocs to non-ICF // sections. @@ -430,6 +590,7 @@ match_sections(unsigned int iteration_num, std::vector* num_tracked_relocs, std::vector* kept_section_id, const std::vector& id_section, + const std::vector& section_addraligns, std::vector* is_secn_or_group_unique, std::vector* section_contents) { @@ -470,13 +631,7 @@ match_sections(unsigned int iteration_num, { if ((*kept_section_id)[i] != i) { - // This section is already folded into something. See - // if it should point to a different kept section. - unsigned int kept_section = (*kept_section_id)[i]; - if (kept_section != (*kept_section_id)[kept_section]) - { - (*kept_section_id)[i] = (*kept_section_id)[kept_section]; - } + // This section is already folded into something. continue; } this_secn_contents = get_section_contents(false, secn, i, NULL, @@ -511,7 +666,25 @@ match_sections(unsigned int iteration_num, this_secn_contents.c_str(), this_secn_contents.length()) != 0) continue; - (*kept_section_id)[i] = kept_section; + + // Check section alignment here. + // The section with the larger alignment requirement + // should be kept. We assume alignment can only be + // zero or positive integral powers of two. + uint64_t align_i = section_addraligns[i]; + uint64_t align_kept = section_addraligns[kept_section]; + if (align_i <= align_kept) + { + (*kept_section_id)[i] = kept_section; + } + else + { + (*kept_section_id)[kept_section] = i; + it->second = i; + full_section_contents[kept_section].swap( + full_section_contents[i]); + } + converged = false; break; } @@ -528,20 +701,41 @@ match_sections(unsigned int iteration_num, (*is_secn_or_group_unique)[i] = true; } + // If a section was folded into another section that was later folded + // again then the former has to be updated. + for (unsigned int i = 0; i < id_section.size(); i++) + { + // Find the end of the folding chain + unsigned int kept = i; + while ((*kept_section_id)[kept] != kept) + { + kept = (*kept_section_id)[kept]; + } + // Update every element of the chain + unsigned int current = i; + while ((*kept_section_id)[current] != kept) + { + unsigned int next = (*kept_section_id)[current]; + (*kept_section_id)[current] = kept; + current = next; + } + } + return converged; } // During safe icf (--icf=safe), only fold functions that are ctors or dtors. -// This function returns true if the mangled function name is a ctor or a -// dtor. +// This function returns true if the section name is that of a ctor or a dtor. static bool -is_function_ctor_or_dtor(const char* mangled_func_name) +is_function_ctor_or_dtor(const std::string& section_name) { - if ((is_prefix_of("_ZN", mangled_func_name) - || is_prefix_of("_ZZ", mangled_func_name)) - && (is_gnu_v3_mangled_ctor(mangled_func_name) - || is_gnu_v3_mangled_dtor(mangled_func_name))) + const char* mangled_func_name = strrchr(section_name.c_str(), '.'); + gold_assert(mangled_func_name != NULL); + if ((is_prefix_of("._ZN", mangled_func_name) + || is_prefix_of("._ZZ", mangled_func_name)) + && (is_gnu_v3_mangled_ctor(mangled_func_name + 1) + || is_gnu_v3_mangled_dtor(mangled_func_name + 1))) { return true; } @@ -557,9 +751,11 @@ Icf::find_identical_sections(const Input_objects* input_objects, Symbol_table* symtab) { unsigned int section_num = 0; - std::vector num_tracked_rels; + std::vector num_tracked_relocs; + std::vector section_addraligns; std::vector is_secn_or_group_unique; std::vector section_contents; + const Target& target = parameters->target(); // Decide which sections are possible candidates first. @@ -567,25 +763,37 @@ Icf::find_identical_sections(const Input_objects* input_objects, p != input_objects->relobj_end(); ++p) { + // Lock the object so we can read from it. This is only called + // single-threaded from queue_middle_tasks, so it is OK to lock. + // Unfortunately we have no way to pass in a Task token. + const Task* dummy_task = reinterpret_cast(-1); + Task_lock_obj tl(dummy_task, *p); + for (unsigned int i = 0;i < (*p)->shnum(); ++i) { - const char* section_name = (*p)->section_name(i).c_str(); - // Only looking to fold functions, so just look at .text sections. - if (!is_prefix_of(".text.", section_name)) + const std::string section_name = (*p)->section_name(i); + if (!is_section_foldable_candidate(section_name)) continue; if (!(*p)->is_section_included(i)) continue; if (parameters->options().gc_sections() && symtab->gc()->is_section_garbage(*p, i)) continue; - // With --icf=safe, check if mangled name is a ctor or a dtor. + // With --icf=safe, check if the mangled function name is a ctor + // or a dtor. The mangled function name can be obtained from the + // section name by stripping the section prefix. if (parameters->options().icf_safe_folding() - && !is_function_ctor_or_dtor(section_name + 6)) - continue; + && !is_function_ctor_or_dtor(section_name) + && (!target.can_check_for_function_pointers() + || section_has_function_pointers(*p, i))) + { + continue; + } this->id_section_.push_back(Section_id(*p, i)); this->section_id_[Section_id(*p, i)] = section_num; this->kept_section_id_.push_back(section_num); - num_tracked_rels.push_back(0); + num_tracked_relocs.push_back(0); + section_addraligns.push_back((*p)->section_addralign(i)); is_secn_or_group_unique.push_back(false); section_contents.push_back(""); section_num++; @@ -605,9 +813,9 @@ Icf::find_identical_sections(const Input_objects* input_objects, { num_iterations++; converged = match_sections(num_iterations, symtab, - &num_tracked_rels, &this->kept_section_id_, - this->id_section_, &is_secn_or_group_unique, - §ion_contents); + &num_tracked_relocs, &this->kept_section_id_, + this->id_section_, section_addraligns, + &is_secn_or_group_unique, §ion_contents); } if (parameters->options().print_icf_sections()) @@ -635,7 +843,7 @@ Icf::find_identical_sections(const Input_objects* input_objects, else if (sym->source() == Symbol::FROM_OBJECT && !sym->object()->is_dynamic()) { - Object* obj = sym->object(); + Relobj* obj = static_cast(sym->object()); bool is_ordinary; unsigned int shndx = sym->shndx(&is_ordinary); if (is_ordinary) @@ -652,7 +860,7 @@ Icf::find_identical_sections(const Input_objects* input_objects, // Unfolds the section denoted by OBJ and SHNDX if folded. void -Icf::unfold_section(Object* obj, unsigned int shndx) +Icf::unfold_section(Relobj* obj, unsigned int shndx) { Section_id secn(obj, shndx); Uniq_secn_id_map::iterator it = this->section_id_.find(secn); @@ -669,7 +877,7 @@ Icf::unfold_section(Object* obj, unsigned int shndx) // is different from this section. bool -Icf::is_section_folded(Object* obj, unsigned int shndx) +Icf::is_section_folded(Relobj* obj, unsigned int shndx) { Section_id secn(obj, shndx); Uniq_secn_id_map::iterator it = this->section_id_.find(secn); @@ -683,7 +891,7 @@ Icf::is_section_folded(Object* obj, unsigned int shndx) // This function returns the folded section for the given section. Section_id -Icf::get_folded_section(Object* dup_obj, unsigned int dup_shndx) +Icf::get_folded_section(Relobj* dup_obj, unsigned int dup_shndx) { Section_id dup_secn(dup_obj, dup_shndx); Uniq_secn_id_map::iterator it = this->section_id_.find(dup_secn);