1 // gc.h -- garbage collection of unused sections 2 3 // Copyright (C) 2009-2014 Free Software Foundation, Inc. 4 // Written by Sriraman Tallam <tmsriram (at) 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 <queue> 27 #include <vector> 28 29 #include "elfcpp.h" 30 #include "symtab.h" 31 #include "object.h" 32 #include "icf.h" 33 34 namespace gold 35 { 36 37 class Object; 38 39 template<int size, bool big_endian> 40 class Sized_relobj_file; 41 42 template<int sh_type, int size, bool big_endian> 43 struct Reloc_types; 44 45 class Output_section; 46 class General_options; 47 class Layout; 48 49 class Garbage_collection 50 { 51 public: 52 53 typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable; 54 typedef std::map<Section_id, Sections_reachable> Section_ref; 55 typedef std::queue<Section_id> Worklist_type; 56 // This maps the name of the section which can be represented as a C 57 // identifier (cident) to the list of sections that have that name. 58 // Different object files can have cident sections with the same name. 59 typedef std::map<std::string, Sections_reachable> Cident_section_map; 60 61 Garbage_collection() 62 : is_worklist_ready_(false) 63 { } 64 65 // Accessor methods for the private members. 66 67 Sections_reachable& 68 referenced_list() 69 { return referenced_list_; } 70 71 Section_ref& 72 section_reloc_map() 73 { return this->section_reloc_map_; } 74 75 Worklist_type& 76 worklist() 77 { return this->work_list_; } 78 79 bool 80 is_worklist_ready() 81 { return this->is_worklist_ready_; } 82 83 void 84 worklist_ready() 85 { this->is_worklist_ready_ = true; } 86 87 void 88 do_transitive_closure(); 89 90 bool 91 is_section_garbage(Object* obj, unsigned int shndx) 92 { return (this->referenced_list().find(Section_id(obj, shndx)) 93 == this->referenced_list().end()); } 94 95 Cident_section_map* 96 cident_sections() 97 { return &cident_sections_; } 98 99 void 100 add_cident_section(std::string section_name, 101 Section_id secn) 102 { this->cident_sections_[section_name].insert(secn); } 103 104 // Add a reference from the SRC_SHNDX-th section of SRC_OBJECT to 105 // DST_SHNDX-th section of DST_OBJECT. 106 void 107 add_reference(Object* src_object, unsigned int src_shndx, 108 Object* dst_object, unsigned int dst_shndx) 109 { 110 Section_id src_id(src_object, src_shndx); 111 Section_id dst_id(dst_object, dst_shndx); 112 Sections_reachable& reachable = this->section_reloc_map_[src_id]; 113 reachable.insert(dst_id); 114 } 115 116 private: 117 118 Worklist_type work_list_; 119 bool is_worklist_ready_; 120 Section_ref section_reloc_map_; 121 Sections_reachable referenced_list_; 122 Cident_section_map cident_sections_; 123 }; 124 125 // Data to pass between successive invocations of do_layout 126 // in object.cc while garbage collecting. This data structure 127 // is filled by using the data from Read_symbols_data. 128 129 struct Symbols_data 130 { 131 // Section headers. 132 unsigned char* section_headers_data; 133 // Section names. 134 unsigned char* section_names_data; 135 // Size of section name data in bytes. 136 section_size_type section_names_size; 137 // Symbol data. 138 unsigned char* symbols_data; 139 // Size of symbol data in bytes. 140 section_size_type symbols_size; 141 // Offset of external symbols within symbol data. This structure 142 // sometimes contains only external symbols, in which case this will 143 // be zero. Sometimes it contains all symbols. 144 section_offset_type external_symbols_offset; 145 // Symbol names. 146 unsigned char* symbol_names_data; 147 // Size of symbol name data in bytes. 148 section_size_type symbol_names_size; 149 }; 150 151 // Relocations of type SHT_REL store the addend value in their bytes. 152 // This function returns the size of the embedded addend which is 153 // nothing but the size of the relocation. 154 155 template<typename Classify_reloc> 156 inline unsigned int 157 get_embedded_addend_size(int sh_type, int r_type, Relobj* obj) 158 { 159 if (sh_type != elfcpp::SHT_REL) 160 return 0; 161 Classify_reloc classify_reloc; 162 return classify_reloc.get_size_for_reloc(r_type, obj); 163 } 164 165 // This function implements the generic part of reloc 166 // processing to map a section to all the sections it 167 // references through relocs. It is called only during 168 // garbage collection (--gc-sections) and identical code 169 // folding (--icf). 170 171 template<int size, bool big_endian, typename Target_type, int sh_type, 172 typename Scan, typename Classify_reloc> 173 inline void 174 gc_process_relocs( 175 Symbol_table* symtab, 176 Layout*, 177 Target_type* target, 178 Sized_relobj_file<size, big_endian>* src_obj, 179 unsigned int src_indx, 180 const unsigned char* prelocs, 181 size_t reloc_count, 182 Output_section*, 183 bool, 184 size_t local_count, 185 const unsigned char* plocal_syms) 186 { 187 Scan scan; 188 189 typedef typename Reloc_types<sh_type, size, big_endian>::Reloc Reltype; 190 const int reloc_size = Reloc_types<sh_type, size, big_endian>::reloc_size; 191 const int sym_size = elfcpp::Elf_sizes<size>::sym_size; 192 193 Icf::Sections_reachable_info* secvec = NULL; 194 Icf::Symbol_info* symvec = NULL; 195 Icf::Addend_info* addendvec = NULL; 196 Icf::Offset_info* offsetvec = NULL; 197 Icf::Reloc_addend_size_info* reloc_addend_size_vec = NULL; 198 bool is_icf_tracked = false; 199 const char* cident_section_name = NULL; 200 201 std::string src_section_name = (parameters->options().icf_enabled() 202 ? src_obj->section_name(src_indx) 203 : ""); 204 205 bool check_section_for_function_pointers = false; 206 207 if (parameters->options().icf_enabled() 208 && is_section_foldable_candidate(src_section_name.c_str())) 209 { 210 is_icf_tracked = true; 211 Section_id src_id(src_obj, src_indx); 212 Icf::Reloc_info* reloc_info = 213 &symtab->icf()->reloc_info_list()[src_id]; 214 secvec = &reloc_info->section_info; 215 symvec = &reloc_info->symbol_info; 216 addendvec = &reloc_info->addend_info; 217 offsetvec = &reloc_info->offset_info; 218 reloc_addend_size_vec = &reloc_info->reloc_addend_size_info; 219 } 220 221 check_section_for_function_pointers = 222 symtab->icf()->check_section_for_function_pointers(src_section_name, 223 target); 224 225 for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size) 226 { 227 Reltype reloc(prelocs); 228 typename elfcpp::Elf_types<size>::Elf_WXword r_info = reloc.get_r_info(); 229 unsigned int r_sym = elfcpp::elf_r_sym<size>(r_info); 230 unsigned int r_type = elfcpp::elf_r_type<size>(r_info); 231 typename elfcpp::Elf_types<size>::Elf_Swxword addend = 232 Reloc_types<sh_type, size, big_endian>::get_reloc_addend_noerror(&reloc); 233 Object* dst_obj; 234 unsigned int dst_indx; 235 typedef typename elfcpp::Elf_types<size>::Elf_Addr Address; 236 Address dst_off; 237 238 if (r_sym < local_count) 239 { 240 gold_assert(plocal_syms != NULL); 241 typename elfcpp::Sym<size, big_endian> lsym(plocal_syms 242 + r_sym * sym_size); 243 dst_indx = lsym.get_st_shndx(); 244 bool is_ordinary; 245 dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary); 246 dst_obj = src_obj; 247 dst_off = lsym.get_st_value() + addend; 248 249 if (is_icf_tracked) 250 { 251 Address symvalue = dst_off - addend; 252 if (is_ordinary) 253 (*secvec).push_back(Section_id(dst_obj, dst_indx)); 254 else 255 (*secvec).push_back(Section_id(NULL, 0)); 256 (*symvec).push_back(NULL); 257 (*addendvec).push_back(std::make_pair( 258 static_cast<long long>(symvalue), 259 static_cast<long long>(addend))); 260 uint64_t reloc_offset = 261 convert_to_section_size_type(reloc.get_r_offset()); 262 (*offsetvec).push_back(reloc_offset); 263 (*reloc_addend_size_vec).push_back( 264 get_embedded_addend_size<Classify_reloc>(sh_type, r_type, 265 src_obj)); 266 } 267 268 // When doing safe folding, check to see if this relocation is that 269 // of a function pointer being taken. 270 if (is_ordinary 271 && check_section_for_function_pointers 272 && lsym.get_st_type() != elfcpp::STT_OBJECT 273 && scan.local_reloc_may_be_function_pointer(symtab, NULL, NULL, 274 src_obj, src_indx, 275 NULL, reloc, r_type, 276 lsym)) 277 symtab->icf()->set_section_has_function_pointers( 278 src_obj, lsym.get_st_shndx()); 279 280 if (!is_ordinary || dst_indx == src_indx) 281 continue; 282 } 283 else 284 { 285 Symbol* gsym = src_obj->global_symbol(r_sym); 286 gold_assert(gsym != NULL); 287 if (gsym->is_forwarder()) 288 gsym = symtab->resolve_forwards(gsym); 289 290 dst_obj = NULL; 291 dst_indx = 0; 292 bool is_ordinary = false; 293 if (gsym->source() == Symbol::FROM_OBJECT) 294 { 295 dst_obj = 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 && gsym->type() != elfcpp::STT_OBJECT 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 && gsym->source() == Symbol::FROM_OBJECT) 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 (gsym->source() != Symbol::FROM_OBJECT) 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, 354 dst_obj, dst_indx, 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 381
