| 1 | // gc.h -- garbage collection of unused sections |
| 2 | |
| 3 | // Copyright (C) 2009-2015 Free Software Foundation, Inc. |
| 4 | // Written by Sriraman Tallam <tmsriram@google.com>. |
| 5 | |
| 6 | // This file is part of gold. |
| 7 | |
| 8 | // This program is free software; you can redistribute it and/or modify |
| 9 | // it under the terms of the GNU General Public License as published by |
| 10 | // the Free Software Foundation; either version 3 of the License, or |
| 11 | // (at your option) any later version. |
| 12 | |
| 13 | // This program is distributed in the hope that it will be useful, |
| 14 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 15 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 16 | // GNU General Public License for more details. |
| 17 | |
| 18 | // You should have received a copy of the GNU General Public License |
| 19 | // along with this program; if not, write to the Free Software |
| 20 | // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, |
| 21 | // MA 02110-1301, USA. |
| 22 | |
| 23 | #ifndef GOLD_GC_H |
| 24 | #define GOLD_GC_H |
| 25 | |
| 26 | #include <vector> |
| 27 | |
| 28 | #include "elfcpp.h" |
| 29 | #include "symtab.h" |
| 30 | #include "object.h" |
| 31 | #include "icf.h" |
| 32 | |
| 33 | namespace gold |
| 34 | { |
| 35 | |
| 36 | class Object; |
| 37 | |
| 38 | template<int size, bool big_endian> |
| 39 | class Sized_relobj_file; |
| 40 | |
| 41 | template<int sh_type, int size, bool big_endian> |
| 42 | struct Reloc_types; |
| 43 | |
| 44 | class Output_section; |
| 45 | class General_options; |
| 46 | class Layout; |
| 47 | |
| 48 | class Garbage_collection |
| 49 | { |
| 50 | public: |
| 51 | |
| 52 | typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable; |
| 53 | typedef std::map<Section_id, Sections_reachable> Section_ref; |
| 54 | typedef std::vector<Section_id> Worklist_type; |
| 55 | // This maps the name of the section which can be represented as a C |
| 56 | // identifier (cident) to the list of sections that have that name. |
| 57 | // Different object files can have cident sections with the same name. |
| 58 | typedef std::map<std::string, Sections_reachable> Cident_section_map; |
| 59 | |
| 60 | Garbage_collection() |
| 61 | : is_worklist_ready_(false) |
| 62 | { } |
| 63 | |
| 64 | // Accessor methods for the private members. |
| 65 | |
| 66 | Sections_reachable& |
| 67 | referenced_list() |
| 68 | { return referenced_list_; } |
| 69 | |
| 70 | Section_ref& |
| 71 | section_reloc_map() |
| 72 | { return this->section_reloc_map_; } |
| 73 | |
| 74 | Worklist_type& |
| 75 | worklist() |
| 76 | { return this->work_list_; } |
| 77 | |
| 78 | bool |
| 79 | is_worklist_ready() |
| 80 | { return this->is_worklist_ready_; } |
| 81 | |
| 82 | void |
| 83 | worklist_ready() |
| 84 | { this->is_worklist_ready_ = true; } |
| 85 | |
| 86 | void |
| 87 | do_transitive_closure(); |
| 88 | |
| 89 | bool |
| 90 | is_section_garbage(Relobj* obj, unsigned int shndx) |
| 91 | { return (this->referenced_list().find(Section_id(obj, shndx)) |
| 92 | == this->referenced_list().end()); } |
| 93 | |
| 94 | Cident_section_map* |
| 95 | cident_sections() |
| 96 | { return &cident_sections_; } |
| 97 | |
| 98 | void |
| 99 | add_cident_section(std::string section_name, |
| 100 | Section_id secn) |
| 101 | { this->cident_sections_[section_name].insert(secn); } |
| 102 | |
| 103 | // Add a reference from the SRC_SHNDX-th section of SRC_OBJECT to |
| 104 | // DST_SHNDX-th section of DST_OBJECT. |
| 105 | void |
| 106 | add_reference(Relobj* src_object, unsigned int src_shndx, |
| 107 | Relobj* dst_object, unsigned int dst_shndx) |
| 108 | { |
| 109 | Section_id src_id(src_object, src_shndx); |
| 110 | Section_id dst_id(dst_object, dst_shndx); |
| 111 | Sections_reachable& reachable = this->section_reloc_map_[src_id]; |
| 112 | reachable.insert(dst_id); |
| 113 | } |
| 114 | |
| 115 | private: |
| 116 | |
| 117 | Worklist_type work_list_; |
| 118 | bool is_worklist_ready_; |
| 119 | Section_ref section_reloc_map_; |
| 120 | Sections_reachable referenced_list_; |
| 121 | Cident_section_map cident_sections_; |
| 122 | }; |
| 123 | |
| 124 | // Data to pass between successive invocations of do_layout |
| 125 | // in object.cc while garbage collecting. This data structure |
| 126 | // is filled by using the data from Read_symbols_data. |
| 127 | |
| 128 | struct Symbols_data |
| 129 | { |
| 130 | // Section headers. |
| 131 | unsigned char* section_headers_data; |
| 132 | // Section names. |
| 133 | unsigned char* section_names_data; |
| 134 | // Size of section name data in bytes. |
| 135 | section_size_type section_names_size; |
| 136 | // Symbol data. |
| 137 | unsigned char* symbols_data; |
| 138 | // Size of symbol data in bytes. |
| 139 | section_size_type symbols_size; |
| 140 | // Offset of external symbols within symbol data. This structure |
| 141 | // sometimes contains only external symbols, in which case this will |
| 142 | // be zero. Sometimes it contains all symbols. |
| 143 | section_offset_type external_symbols_offset; |
| 144 | // Symbol names. |
| 145 | unsigned char* symbol_names_data; |
| 146 | // Size of symbol name data in bytes. |
| 147 | section_size_type symbol_names_size; |
| 148 | }; |
| 149 | |
| 150 | // Relocations of type SHT_REL store the addend value in their bytes. |
| 151 | // This function returns the size of the embedded addend which is |
| 152 | // nothing but the size of the relocation. |
| 153 | |
| 154 | template<typename Classify_reloc> |
| 155 | inline unsigned int |
| 156 | get_embedded_addend_size(int sh_type, int r_type, Relobj* obj) |
| 157 | { |
| 158 | if (sh_type != elfcpp::SHT_REL) |
| 159 | return 0; |
| 160 | Classify_reloc classify_reloc; |
| 161 | return classify_reloc.get_size_for_reloc(r_type, obj); |
| 162 | } |
| 163 | |
| 164 | // This function implements the generic part of reloc |
| 165 | // processing to map a section to all the sections it |
| 166 | // references through relocs. It is called only during |
| 167 | // garbage collection (--gc-sections) and identical code |
| 168 | // folding (--icf). |
| 169 | |
| 170 | template<int size, bool big_endian, typename Target_type, int sh_type, |
| 171 | typename Scan, typename Classify_reloc> |
| 172 | inline void |
| 173 | gc_process_relocs( |
| 174 | Symbol_table* symtab, |
| 175 | Layout*, |
| 176 | Target_type* target, |
| 177 | Sized_relobj_file<size, big_endian>* src_obj, |
| 178 | unsigned int src_indx, |
| 179 | const unsigned char* prelocs, |
| 180 | size_t reloc_count, |
| 181 | Output_section*, |
| 182 | bool, |
| 183 | size_t local_count, |
| 184 | const unsigned char* plocal_syms) |
| 185 | { |
| 186 | Scan scan; |
| 187 | |
| 188 | typedef typename Reloc_types<sh_type, size, big_endian>::Reloc Reltype; |
| 189 | const int reloc_size = Reloc_types<sh_type, size, big_endian>::reloc_size; |
| 190 | const int sym_size = elfcpp::Elf_sizes<size>::sym_size; |
| 191 | |
| 192 | Icf::Sections_reachable_info* secvec = NULL; |
| 193 | Icf::Symbol_info* symvec = NULL; |
| 194 | Icf::Addend_info* addendvec = NULL; |
| 195 | Icf::Offset_info* offsetvec = NULL; |
| 196 | Icf::Reloc_addend_size_info* reloc_addend_size_vec = NULL; |
| 197 | bool is_icf_tracked = false; |
| 198 | const char* cident_section_name = NULL; |
| 199 | |
| 200 | std::string src_section_name = (parameters->options().icf_enabled() |
| 201 | ? src_obj->section_name(src_indx) |
| 202 | : ""); |
| 203 | |
| 204 | bool check_section_for_function_pointers = false; |
| 205 | |
| 206 | if (parameters->options().icf_enabled() |
| 207 | && is_section_foldable_candidate(src_section_name.c_str())) |
| 208 | { |
| 209 | is_icf_tracked = true; |
| 210 | Section_id src_id(src_obj, src_indx); |
| 211 | Icf::Reloc_info* reloc_info = |
| 212 | &symtab->icf()->reloc_info_list()[src_id]; |
| 213 | secvec = &reloc_info->section_info; |
| 214 | symvec = &reloc_info->symbol_info; |
| 215 | addendvec = &reloc_info->addend_info; |
| 216 | offsetvec = &reloc_info->offset_info; |
| 217 | reloc_addend_size_vec = &reloc_info->reloc_addend_size_info; |
| 218 | } |
| 219 | |
| 220 | check_section_for_function_pointers = |
| 221 | symtab->icf()->check_section_for_function_pointers(src_section_name, |
| 222 | target); |
| 223 | |
| 224 | for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size) |
| 225 | { |
| 226 | Reltype reloc(prelocs); |
| 227 | typename elfcpp::Elf_types<size>::Elf_WXword r_info = reloc.get_r_info(); |
| 228 | unsigned int r_sym = elfcpp::elf_r_sym<size>(r_info); |
| 229 | unsigned int r_type = elfcpp::elf_r_type<size>(r_info); |
| 230 | typename elfcpp::Elf_types<size>::Elf_Swxword addend = |
| 231 | Reloc_types<sh_type, size, big_endian>::get_reloc_addend_noerror(&reloc); |
| 232 | Relobj* dst_obj; |
| 233 | unsigned int dst_indx; |
| 234 | typedef typename elfcpp::Elf_types<size>::Elf_Addr Address; |
| 235 | Address dst_off; |
| 236 | |
| 237 | if (r_sym < local_count) |
| 238 | { |
| 239 | gold_assert(plocal_syms != NULL); |
| 240 | typename elfcpp::Sym<size, big_endian> lsym(plocal_syms |
| 241 | + r_sym * sym_size); |
| 242 | dst_indx = lsym.get_st_shndx(); |
| 243 | bool is_ordinary; |
| 244 | dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary); |
| 245 | dst_obj = src_obj; |
| 246 | dst_off = lsym.get_st_value() + addend; |
| 247 | |
| 248 | if (is_icf_tracked) |
| 249 | { |
| 250 | Address symvalue = dst_off - addend; |
| 251 | if (is_ordinary) |
| 252 | (*secvec).push_back(Section_id(src_obj, dst_indx)); |
| 253 | else |
| 254 | (*secvec).push_back(Section_id(NULL, 0)); |
| 255 | (*symvec).push_back(NULL); |
| 256 | (*addendvec).push_back(std::make_pair( |
| 257 | static_cast<long long>(symvalue), |
| 258 | static_cast<long long>(addend))); |
| 259 | uint64_t reloc_offset = |
| 260 | convert_to_section_size_type(reloc.get_r_offset()); |
| 261 | (*offsetvec).push_back(reloc_offset); |
| 262 | (*reloc_addend_size_vec).push_back( |
| 263 | get_embedded_addend_size<Classify_reloc>(sh_type, r_type, |
| 264 | src_obj)); |
| 265 | } |
| 266 | |
| 267 | // When doing safe folding, check to see if this relocation is that |
| 268 | // of a function pointer being taken. |
| 269 | if (is_ordinary |
| 270 | && check_section_for_function_pointers |
| 271 | && lsym.get_st_type() != elfcpp::STT_OBJECT |
| 272 | && scan.local_reloc_may_be_function_pointer(symtab, NULL, NULL, |
| 273 | src_obj, src_indx, |
| 274 | NULL, reloc, r_type, |
| 275 | lsym)) |
| 276 | symtab->icf()->set_section_has_function_pointers( |
| 277 | src_obj, lsym.get_st_shndx()); |
| 278 | |
| 279 | if (!is_ordinary || dst_indx == src_indx) |
| 280 | continue; |
| 281 | } |
| 282 | else |
| 283 | { |
| 284 | Symbol* gsym = src_obj->global_symbol(r_sym); |
| 285 | gold_assert(gsym != NULL); |
| 286 | if (gsym->is_forwarder()) |
| 287 | gsym = symtab->resolve_forwards(gsym); |
| 288 | |
| 289 | dst_obj = NULL; |
| 290 | dst_indx = 0; |
| 291 | bool is_ordinary = false; |
| 292 | if (gsym->source() == Symbol::FROM_OBJECT |
| 293 | && !gsym->object()->is_dynamic()) |
| 294 | { |
| 295 | dst_obj = static_cast<Relobj*>(gsym->object()); |
| 296 | dst_indx = gsym->shndx(&is_ordinary); |
| 297 | } |
| 298 | dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value(); |
| 299 | dst_off += addend; |
| 300 | |
| 301 | // When doing safe folding, check to see if this relocation is that |
| 302 | // of a function pointer being taken. |
| 303 | if (gsym->source() == Symbol::FROM_OBJECT |
| 304 | && check_section_for_function_pointers |
| 305 | && dst_obj != NULL |
| 306 | && (!is_ordinary |
| 307 | || scan.global_reloc_may_be_function_pointer( |
| 308 | symtab, NULL, NULL, src_obj, src_indx, NULL, reloc, |
| 309 | r_type, gsym))) |
| 310 | symtab->icf()->set_section_has_function_pointers(dst_obj, dst_indx); |
| 311 | |
| 312 | // If the symbol name matches '__start_XXX' then the section with |
| 313 | // the C identifier like name 'XXX' should not be garbage collected. |
| 314 | // A similar treatment to symbols with the name '__stop_XXX'. |
| 315 | if (is_prefix_of(cident_section_start_prefix, gsym->name())) |
| 316 | { |
| 317 | cident_section_name = (gsym->name() |
| 318 | + strlen(cident_section_start_prefix)); |
| 319 | } |
| 320 | else if (is_prefix_of(cident_section_stop_prefix, gsym->name())) |
| 321 | { |
| 322 | cident_section_name = (gsym->name() |
| 323 | + strlen(cident_section_stop_prefix)); |
| 324 | } |
| 325 | if (is_icf_tracked) |
| 326 | { |
| 327 | Address symvalue = dst_off - addend; |
| 328 | if (is_ordinary && dst_obj != NULL) |
| 329 | (*secvec).push_back(Section_id(dst_obj, dst_indx)); |
| 330 | else |
| 331 | (*secvec).push_back(Section_id(NULL, 0)); |
| 332 | (*symvec).push_back(gsym); |
| 333 | (*addendvec).push_back(std::make_pair( |
| 334 | static_cast<long long>(symvalue), |
| 335 | static_cast<long long>(addend))); |
| 336 | uint64_t reloc_offset = |
| 337 | convert_to_section_size_type(reloc.get_r_offset()); |
| 338 | (*offsetvec).push_back(reloc_offset); |
| 339 | (*reloc_addend_size_vec).push_back( |
| 340 | get_embedded_addend_size<Classify_reloc>(sh_type, r_type, |
| 341 | src_obj)); |
| 342 | } |
| 343 | |
| 344 | if (dst_obj == NULL) |
| 345 | continue; |
| 346 | if (!is_ordinary) |
| 347 | continue; |
| 348 | } |
| 349 | if (parameters->options().gc_sections()) |
| 350 | { |
| 351 | symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx); |
| 352 | parameters->sized_target<size, big_endian>() |
| 353 | ->gc_add_reference(symtab, src_obj, src_indx, dst_obj, dst_indx, |
| 354 | dst_off); |
| 355 | if (cident_section_name != NULL) |
| 356 | { |
| 357 | Garbage_collection::Cident_section_map::iterator ele = |
| 358 | symtab->gc()->cident_sections()->find(std::string(cident_section_name)); |
| 359 | if (ele == symtab->gc()->cident_sections()->end()) |
| 360 | continue; |
| 361 | Section_id src_id(src_obj, src_indx); |
| 362 | Garbage_collection::Sections_reachable& |
| 363 | v(symtab->gc()->section_reloc_map()[src_id]); |
| 364 | Garbage_collection::Sections_reachable& cident_secn(ele->second); |
| 365 | for (Garbage_collection::Sections_reachable::iterator it_v |
| 366 | = cident_secn.begin(); |
| 367 | it_v != cident_secn.end(); |
| 368 | ++it_v) |
| 369 | { |
| 370 | v.insert(*it_v); |
| 371 | } |
| 372 | } |
| 373 | } |
| 374 | } |
| 375 | return; |
| 376 | } |
| 377 | |
| 378 | } // End of namespace gold. |
| 379 | |
| 380 | #endif |