1 // gc.h -- garbage collection of unused sections
2
3 // Copyright (C) 2009-2023 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 class Output_section;
42 class General_options;
43 class Layout;
44
45 class Garbage_collection
46 {
47 public:
48
49 typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
50 typedef std::map<Section_id, Sections_reachable> Section_ref;
51 typedef std::vector<Section_id> Worklist_type;
52 // This maps the name of the section which can be represented as a C
53 // identifier (cident) to the list of sections that have that name.
54 // Different object files can have cident sections with the same name.
55 typedef std::map<std::string, Sections_reachable> Cident_section_map;
56
57 Garbage_collection()
58 : is_worklist_ready_(false)
59 { }
60
61 // Accessor methods for the private members.
62
63 Sections_reachable&
64 referenced_list()
65 { return referenced_list_; }
66
67 Section_ref&
68 section_reloc_map()
69 { return this->section_reloc_map_; }
70
71 Worklist_type&
72 worklist()
73 { return this->work_list_; }
74
75 bool
76 is_worklist_ready()
77 { return this->is_worklist_ready_; }
78
79 void
80 worklist_ready()
81 { this->is_worklist_ready_ = true; }
82
83 void
84 do_transitive_closure();
85
86 bool
87 is_section_garbage(Relobj* obj, unsigned int shndx)
88 { return (this->referenced_list().find(Section_id(obj, shndx))
89 == this->referenced_list().end()); }
90
91 Cident_section_map*
92 cident_sections()
93 { return &cident_sections_; }
94
95 void
96 add_cident_section(std::string section_name,
97 Section_id secn)
98 { this->cident_sections_[section_name].insert(secn); }
99
100 // Add a reference from the SRC_SHNDX-th section of SRC_OBJECT to
101 // DST_SHNDX-th section of DST_OBJECT.
102 void
103 add_reference(Relobj* src_object, unsigned int src_shndx,
104 Relobj* dst_object, unsigned int dst_shndx)
105 {
106 Section_id src_id(src_object, src_shndx);
107 Section_id dst_id(dst_object, dst_shndx);
108 Sections_reachable& reachable = this->section_reloc_map_[src_id];
109 reachable.insert(dst_id);
110 }
111
112 private:
113
114 Worklist_type work_list_;
115 bool is_worklist_ready_;
116 Section_ref section_reloc_map_;
117 Sections_reachable referenced_list_;
118 Cident_section_map cident_sections_;
119 };
120
121 // Data to pass between successive invocations of do_layout
122 // in object.cc while garbage collecting. This data structure
123 // is filled by using the data from Read_symbols_data.
124
125 struct Symbols_data
126 {
127 // Section headers.
128 unsigned char* section_headers_data;
129 // Section names.
130 unsigned char* section_names_data;
131 // Size of section name data in bytes.
132 section_size_type section_names_size;
133 // Symbol data.
134 unsigned char* symbols_data;
135 // Size of symbol data in bytes.
136 section_size_type symbols_size;
137 // Offset of external symbols within symbol data. This structure
138 // sometimes contains only external symbols, in which case this will
139 // be zero. Sometimes it contains all symbols.
140 section_offset_type external_symbols_offset;
141 // Symbol names.
142 unsigned char* symbol_names_data;
143 // Size of symbol name data in bytes.
144 section_size_type symbol_names_size;
145 };
146
147 // Relocations of type SHT_REL store the addend value in their bytes.
148 // This function returns the size of the embedded addend which is
149 // nothing but the size of the relocation.
150
151 template<typename Classify_reloc>
152 inline unsigned int
153 get_embedded_addend_size(int r_type, Relobj* obj)
154 {
155 if (Classify_reloc::sh_type == elfcpp::SHT_REL)
156 return Classify_reloc::get_size_for_reloc(r_type, obj);
157 return 0;
158 }
159
160 // This function implements the generic part of reloc
161 // processing to map a section to all the sections it
162 // references through relocs. It is called only during
163 // garbage collection (--gc-sections) and identical code
164 // folding (--icf).
165
166 template<int size, bool big_endian, typename Target_type,
167 typename Scan, typename Classify_reloc>
168 inline void
169 gc_process_relocs(
170 Symbol_table* symtab,
171 Layout*,
172 Target_type* target,
173 Sized_relobj_file<size, big_endian>* src_obj,
174 unsigned int src_indx,
175 const unsigned char* prelocs,
176 size_t reloc_count,
177 Output_section*,
178 bool,
179 size_t local_count,
180 const unsigned char* plocal_syms)
181 {
182 Scan scan;
183
184 typedef typename Classify_reloc::Reltype Reltype;
185 const int reloc_size = Classify_reloc::reloc_size;
186 const int sym_size = elfcpp::Elf_sizes<size>::sym_size;
187
188 Icf::Sections_reachable_info* secvec = NULL;
189 Icf::Symbol_info* symvec = NULL;
190 Icf::Addend_info* addendvec = NULL;
191 Icf::Offset_info* offsetvec = NULL;
192 Icf::Reloc_addend_size_info* reloc_addend_size_vec = NULL;
193 bool is_icf_tracked = false;
194 const char* cident_section_name = NULL;
195
196 std::string src_section_name = (parameters->options().icf_enabled()
197 ? src_obj->section_name(src_indx)
198 : "");
199
200 bool check_section_for_function_pointers = false;
201
202 if (parameters->options().icf_enabled()
203 && (is_section_foldable_candidate(src_section_name)
204 || is_prefix_of(".eh_frame", src_section_name.c_str())))
205 {
206 is_icf_tracked = true;
207 Section_id src_id(src_obj, src_indx);
208 Icf::Reloc_info* reloc_info =
209 &symtab->icf()->reloc_info_list()[src_id];
210 secvec = &reloc_info->section_info;
211 symvec = &reloc_info->symbol_info;
212 addendvec = &reloc_info->addend_info;
213 offsetvec = &reloc_info->offset_info;
214 reloc_addend_size_vec = &reloc_info->reloc_addend_size_info;
215 }
216
217 check_section_for_function_pointers =
218 symtab->icf()->check_section_for_function_pointers(src_section_name,
219 target);
220
221 for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size)
222 {
223 Reltype reloc(prelocs);
224 unsigned int r_sym = Classify_reloc::get_r_sym(&reloc);
225 unsigned int r_type = Classify_reloc::get_r_type(&reloc);
226 typename elfcpp::Elf_types<size>::Elf_Swxword addend =
227 Classify_reloc::get_r_addend(&reloc);
228 Relobj* dst_obj;
229 unsigned int dst_indx;
230 typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
231 Address dst_off;
232
233 if (r_sym < local_count)
234 {
235 gold_assert(plocal_syms != NULL);
236 typename elfcpp::Sym<size, big_endian> lsym(plocal_syms
237 + r_sym * sym_size);
238 dst_indx = lsym.get_st_shndx();
239 bool is_ordinary;
240 dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
241 dst_obj = src_obj;
242 dst_off = lsym.get_st_value() + addend;
243
244 if (is_icf_tracked)
245 {
246 Address symvalue = dst_off - addend;
247 if (is_ordinary)
248 (*secvec).push_back(Section_id(src_obj, dst_indx));
249 else
250 (*secvec).push_back(Section_id(static_cast<Relobj*>(NULL), 0));
251 // If the target of the relocation is an STT_SECTION symbol,
252 // make a note of that by storing -1 in the symbol vector.
253 if (lsym.get_st_type() == elfcpp::STT_SECTION)
254 (*symvec).push_back(reinterpret_cast<Symbol*>(-1));
255 else
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>(r_type, 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, target,
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 && gsym->type() == elfcpp::STT_FUNC
305 && check_section_for_function_pointers
306 && dst_obj != NULL
307 && (!is_ordinary
308 || scan.global_reloc_may_be_function_pointer(
309 symtab, NULL, target, src_obj, src_indx, NULL, reloc,
310 r_type, gsym)))
311 symtab->icf()->set_section_has_function_pointers(dst_obj, dst_indx);
312
313 // If the symbol name matches '__start_XXX' then the section with
314 // the C identifier like name 'XXX' should not be garbage collected.
315 // A similar treatment to symbols with the name '__stop_XXX'.
316 if (is_prefix_of(cident_section_start_prefix, gsym->name()))
317 {
318 cident_section_name = (gsym->name()
319 + strlen(cident_section_start_prefix));
320 }
321 else if (is_prefix_of(cident_section_stop_prefix, gsym->name()))
322 {
323 cident_section_name = (gsym->name()
324 + strlen(cident_section_stop_prefix));
325 }
326 if (is_icf_tracked)
327 {
328 Address symvalue = dst_off - addend;
329 if (is_ordinary && dst_obj != NULL)
330 (*secvec).push_back(Section_id(dst_obj, dst_indx));
331 else
332 (*secvec).push_back(Section_id(static_cast<Relobj*>(NULL), 0));
333 (*symvec).push_back(gsym);
334 (*addendvec).push_back(std::make_pair(
335 static_cast<long long>(symvalue),
336 static_cast<long long>(addend)));
337 uint64_t reloc_offset =
338 convert_to_section_size_type(reloc.get_r_offset());
339 (*offsetvec).push_back(reloc_offset);
340 (*reloc_addend_size_vec).push_back(
341 get_embedded_addend_size<Classify_reloc>(r_type, 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