1 // gc.h -- garbage collection of unused sections 2 3 // Copyright 2009, 2010, 2011, 2012 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 <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 Section_ref::iterator p = this->section_reloc_map_.find(src_id); 113 if (p == this->section_reloc_map_.end()) 114 this->section_reloc_map_[src_id].insert(dst_id); 115 else 116 p->second.insert(dst_id); 117 } 118 119 private: 120 121 Worklist_type work_list_; 122 bool is_worklist_ready_; 123 Section_ref section_reloc_map_; 124 Sections_reachable referenced_list_; 125 Cident_section_map cident_sections_; 126 }; 127 128 // Data to pass between successive invocations of do_layout 129 // in object.cc while garbage collecting. This data structure 130 // is filled by using the data from Read_symbols_data. 131 132 struct Symbols_data 133 { 134 // Section headers. 135 unsigned char* section_headers_data; 136 // Section names. 137 unsigned char* section_names_data; 138 // Size of section name data in bytes. 139 section_size_type section_names_size; 140 // Symbol data. 141 unsigned char* symbols_data; 142 // Size of symbol data in bytes. 143 section_size_type symbols_size; 144 // Offset of external symbols within symbol data. This structure 145 // sometimes contains only external symbols, in which case this will 146 // be zero. Sometimes it contains all symbols. 147 section_offset_type external_symbols_offset; 148 // Symbol names. 149 unsigned char* symbol_names_data; 150 // Size of symbol name data in bytes. 151 section_size_type symbol_names_size; 152 }; 153 154 // Relocations of type SHT_REL store the addend value in their bytes. 155 // This function returns the size of the embedded addend which is 156 // nothing but the size of the relocation. 157 158 template<typename Classify_reloc> 159 inline unsigned int 160 get_embedded_addend_size(int sh_type, int r_type, Relobj* obj) 161 { 162 if (sh_type != elfcpp::SHT_REL) 163 return 0; 164 Classify_reloc classify_reloc; 165 return classify_reloc.get_size_for_reloc(r_type, obj); 166 } 167 168 // This function implements the generic part of reloc 169 // processing to map a section to all the sections it 170 // references through relocs. It is called only during 171 // garbage collection (--gc-sections) and identical code 172 // folding (--icf). 173 174 template<int size, bool big_endian, typename Target_type, int sh_type, 175 typename Scan, typename Classify_reloc> 176 inline void 177 gc_process_relocs( 178 Symbol_table* symtab, 179 Layout*, 180 Target_type* target, 181 Sized_relobj_file<size, big_endian>* src_obj, 182 unsigned int src_indx, 183 const unsigned char* prelocs, 184 size_t reloc_count, 185 Output_section*, 186 bool, 187 size_t local_count, 188 const unsigned char* plocal_syms) 189 { 190 Object* dst_obj; 191 unsigned int dst_indx; 192 Scan scan; 193 194 typedef typename Reloc_types<sh_type, size, big_endian>::Reloc Reltype; 195 const int reloc_size = Reloc_types<sh_type, size, big_endian>::reloc_size; 196 const int sym_size = elfcpp::Elf_sizes<size>::sym_size; 197 198 Icf::Sections_reachable_info* secvec = NULL; 199 Icf::Symbol_info* symvec = NULL; 200 Icf::Addend_info* addendvec = NULL; 201 Icf::Offset_info* offsetvec = NULL; 202 Icf::Reloc_addend_size_info* reloc_addend_size_vec = NULL; 203 bool is_icf_tracked = false; 204 const char* cident_section_name = NULL; 205 206 std::string src_section_name = (parameters->options().icf_enabled() 207 ? src_obj->section_name(src_indx) 208 : ""); 209 210 bool check_section_for_function_pointers = false; 211 212 if (parameters->options().icf_enabled() 213 && is_section_foldable_candidate(src_section_name.c_str())) 214 { 215 is_icf_tracked = true; 216 Section_id src_id(src_obj, src_indx); 217 Icf::Reloc_info* reloc_info = 218 &symtab->icf()->reloc_info_list()[src_id]; 219 secvec = &reloc_info->section_info; 220 symvec = &reloc_info->symbol_info; 221 addendvec = &reloc_info->addend_info; 222 offsetvec = &reloc_info->offset_info; 223 reloc_addend_size_vec = &reloc_info->reloc_addend_size_info; 224 } 225 226 check_section_for_function_pointers = 227 symtab->icf()->check_section_for_function_pointers(src_section_name, 228 target); 229 230 for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size) 231 { 232 Reltype reloc(prelocs); 233 typename elfcpp::Elf_types<size>::Elf_WXword r_info = reloc.get_r_info(); 234 unsigned int r_sym = elfcpp::elf_r_sym<size>(r_info); 235 unsigned int r_type = elfcpp::elf_r_type<size>(r_info); 236 typename elfcpp::Elf_types<size>::Elf_Swxword addend = 237 Reloc_types<sh_type, size, big_endian>::get_reloc_addend_noerror(&reloc); 238 239 if (r_sym < local_count) 240 { 241 gold_assert(plocal_syms != NULL); 242 typename elfcpp::Sym<size, big_endian> lsym(plocal_syms 243 + r_sym * sym_size); 244 unsigned int shndx = lsym.get_st_shndx(); 245 bool is_ordinary; 246 shndx = src_obj->adjust_sym_shndx(r_sym, shndx, &is_ordinary); 247 dst_obj = src_obj; 248 dst_indx = shndx; 249 if (is_icf_tracked) 250 { 251 if (is_ordinary) 252 (*secvec).push_back(Section_id(dst_obj, dst_indx)); 253 else 254 (*secvec).push_back(Section_id(NULL, 0)); 255 (*symvec).push_back(NULL); 256 long long symvalue = static_cast<long long>(lsym.get_st_value()); 257 (*addendvec).push_back(std::make_pair(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 || shndx == 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 { 294 dst_obj = gsym->object(); 295 dst_indx = gsym->shndx(&is_ordinary); 296 } 297 298 // When doing safe folding, check to see if this relocation is that 299 // of a function pointer being taken. 300 if (gsym->source() == Symbol::FROM_OBJECT 301 && check_section_for_function_pointers 302 && gsym->type() != elfcpp::STT_OBJECT 303 && (!is_ordinary 304 || scan.global_reloc_may_be_function_pointer( 305 symtab, NULL, NULL, src_obj, src_indx, NULL, reloc, 306 r_type, gsym))) 307 symtab->icf()->set_section_has_function_pointers(dst_obj, dst_indx); 308 309 // If the symbol name matches '__start_XXX' then the section with 310 // the C identifier like name 'XXX' should not be garbage collected. 311 // A similar treatment to symbols with the name '__stop_XXX'. 312 if (is_prefix_of(cident_section_start_prefix, gsym->name())) 313 { 314 cident_section_name = (gsym->name() 315 + strlen(cident_section_start_prefix)); 316 } 317 else if (is_prefix_of(cident_section_stop_prefix, gsym->name())) 318 { 319 cident_section_name = (gsym->name() 320 + strlen(cident_section_stop_prefix)); 321 } 322 if (is_icf_tracked) 323 { 324 if (is_ordinary && gsym->source() == Symbol::FROM_OBJECT) 325 (*secvec).push_back(Section_id(dst_obj, dst_indx)); 326 else 327 (*secvec).push_back(Section_id(NULL, 0)); 328 (*symvec).push_back(gsym); 329 Sized_symbol<size>* sized_gsym = 330 static_cast<Sized_symbol<size>* >(gsym); 331 long long symvalue = 332 static_cast<long long>(sized_gsym->value()); 333 (*addendvec).push_back(std::make_pair(symvalue, 334 static_cast<long long>(addend))); 335 uint64_t reloc_offset = 336 convert_to_section_size_type(reloc.get_r_offset()); 337 (*offsetvec).push_back(reloc_offset); 338 (*reloc_addend_size_vec).push_back( 339 get_embedded_addend_size<Classify_reloc>(sh_type, r_type, 340 src_obj)); 341 } 342 343 if (gsym->source() != Symbol::FROM_OBJECT) 344 continue; 345 if (!is_ordinary) 346 continue; 347 } 348 if (parameters->options().gc_sections()) 349 { 350 symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx); 351 if (cident_section_name != NULL) 352 { 353 Garbage_collection::Cident_section_map::iterator ele = 354 symtab->gc()->cident_sections()->find(std::string(cident_section_name)); 355 if (ele == symtab->gc()->cident_sections()->end()) 356 continue; 357 Section_id src_id(src_obj, src_indx); 358 Garbage_collection::Sections_reachable& 359 v(symtab->gc()->section_reloc_map()[src_id]); 360 Garbage_collection::Sections_reachable& cident_secn(ele->second); 361 for (Garbage_collection::Sections_reachable::iterator it_v 362 = cident_secn.begin(); 363 it_v != cident_secn.end(); 364 ++it_v) 365 { 366 v.insert(*it_v); 367 } 368 } 369 } 370 } 371 return; 372 } 373 374 } // End of namespace gold. 375 376 #endif 377