]>
Commit | Line | Data |
---|---|---|
b8e6aad9 ILT |
1 | // merge.h -- handle section merging for gold -*- C++ -*- |
2 | ||
b90efa5b | 3 | // Copyright (C) 2006-2015 Free Software Foundation, Inc. |
6cb15b7f ILT |
4 | // Written by Ian Lance Taylor <iant@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 | ||
b8e6aad9 ILT |
23 | #ifndef GOLD_MERGE_H |
24 | #define GOLD_MERGE_H | |
25 | ||
26 | #include <climits> | |
a9a60db6 ILT |
27 | #include <map> |
28 | #include <vector> | |
b8e6aad9 ILT |
29 | |
30 | #include "stringpool.h" | |
31 | #include "output.h" | |
32 | ||
33 | namespace gold | |
34 | { | |
35 | ||
a9a60db6 ILT |
36 | // For each object with merge sections, we store an Object_merge_map. |
37 | // This is used to map locations in input sections to a merged output | |
38 | // section. The output section itself is not recorded here--it can be | |
ef9beddf | 39 | // found in the output_sections_ field of the Object. |
a9a60db6 ILT |
40 | |
41 | class Object_merge_map | |
42 | { | |
43 | public: | |
44 | Object_merge_map() | |
45 | : first_shnum_(-1U), first_map_(), | |
46 | second_shnum_(-1U), second_map_(), | |
47 | section_merge_maps_() | |
48 | { } | |
49 | ||
50 | ~Object_merge_map(); | |
51 | ||
52 | // Add a mapping for MERGE_MAP, for the bytes from OFFSET to OFFSET | |
53 | // + LENGTH in the input section SHNDX to OUTPUT_OFFSET in the | |
54 | // output section. An OUTPUT_OFFSET of -1 means that the bytes are | |
55 | // discarded. OUTPUT_OFFSET is relative to the start of the merged | |
56 | // data in the output section. | |
57 | void | |
dbe40a88 RÁE |
58 | add_mapping(const Output_section_data*, unsigned int shndx, |
59 | section_offset_type offset, section_size_type length, | |
60 | section_offset_type output_offset); | |
a9a60db6 ILT |
61 | |
62 | // Get the output offset for an input address. MERGE_MAP is the map | |
63 | // we are looking for, or NULL if we don't care. The input address | |
64 | // is at offset OFFSET in section SHNDX. This sets *OUTPUT_OFFSET | |
65 | // to the offset in the output section; this will be -1 if the bytes | |
66 | // are not being copied to the output. This returns true if the | |
67 | // mapping is known, false otherwise. *OUTPUT_OFFSET is relative to | |
68 | // the start of the merged data in the output section. | |
69 | bool | |
dbe40a88 | 70 | get_output_offset(unsigned int shndx, |
a9a60db6 | 71 | section_offset_type offset, |
ca09d69a | 72 | section_offset_type* output_offset); |
a9a60db6 ILT |
73 | |
74 | // Return whether this is the merge map for section SHNDX. | |
75 | bool | |
dbe40a88 | 76 | is_merge_section_for(const Output_section_data*, unsigned int shndx); |
a9a60db6 ILT |
77 | |
78 | // Initialize an mapping from input offsets to output addresses for | |
79 | // section SHNDX. STARTING_ADDRESS is the output address of the | |
80 | // merged section. | |
81 | template<int size> | |
82 | void | |
83 | initialize_input_to_output_map( | |
84 | unsigned int shndx, | |
85 | typename elfcpp::Elf_types<size>::Elf_Addr starting_address, | |
86 | Unordered_map<section_offset_type, | |
87 | typename elfcpp::Elf_types<size>::Elf_Addr>*); | |
88 | ||
89 | private: | |
90 | // Map input section offsets to a length and an output section | |
91 | // offset. An output section offset of -1 means that this part of | |
92 | // the input section is being discarded. | |
93 | struct Input_merge_entry | |
94 | { | |
95 | // The offset in the input section. | |
96 | section_offset_type input_offset; | |
97 | // The length. | |
98 | section_size_type length; | |
99 | // The offset in the output section. | |
100 | section_offset_type output_offset; | |
101 | }; | |
102 | ||
103 | // A less-than comparison routine for Input_merge_entry. | |
104 | struct Input_merge_compare | |
105 | { | |
106 | bool | |
107 | operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const | |
108 | { return i1.input_offset < i2.input_offset; } | |
109 | }; | |
110 | ||
111 | // A list of entries for a particular input section. | |
112 | struct Input_merge_map | |
113 | { | |
114 | typedef std::vector<Input_merge_entry> Entries; | |
115 | ||
116 | // We store these with the Relobj, and we look them up by input | |
117 | // section. It is possible to have two different merge maps | |
118 | // associated with a single output section. For example, this | |
119 | // happens routinely with .rodata, when merged string constants | |
120 | // and merged fixed size constants are both put into .rodata. The | |
121 | // output offset that we store is not the offset from the start of | |
122 | // the output section; it is the offset from the start of the | |
123 | // merged data in the output section. That means that the caller | |
124 | // is going to add the offset of the merged data within the output | |
125 | // section, which means that the caller needs to know which set of | |
126 | // merged data it found the entry in. So it's not enough to find | |
127 | // this data based on the input section and the output section; we | |
128 | // also have to find it based on a set of merged data in the | |
129 | // output section. In order to verify that we are looking at the | |
130 | // right data, we store a pointer to the Merge_map here, and we | |
131 | // pass in a pointer when looking at the data. If we are asked to | |
132 | // look up information for a different Merge_map, we report that | |
133 | // we don't have it, rather than trying a lookup and returning an | |
134 | // answer which will receive the wrong offset. | |
dbe40a88 | 135 | const Output_section_data* output_data; |
a9a60db6 ILT |
136 | // The list of mappings. |
137 | Entries entries; | |
138 | // Whether the ENTRIES field is sorted by input_offset. | |
139 | bool sorted; | |
140 | ||
141 | Input_merge_map() | |
dbe40a88 | 142 | : output_data(NULL), entries(), sorted(true) |
a9a60db6 ILT |
143 | { } |
144 | }; | |
145 | ||
146 | // Map input section indices to merge maps. | |
147 | typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps; | |
148 | ||
149 | // Return a pointer to the Input_merge_map to use for the input | |
150 | // section SHNDX, or NULL. | |
151 | Input_merge_map* | |
152 | get_input_merge_map(unsigned int shndx); | |
153 | ||
9b547ce6 | 154 | // Get or make the Input_merge_map to use for the section SHNDX |
a9a60db6 ILT |
155 | // with MERGE_MAP. |
156 | Input_merge_map* | |
dbe40a88 RÁE |
157 | get_or_make_input_merge_map(const Output_section_data* merge_map, |
158 | unsigned int shndx); | |
a9a60db6 ILT |
159 | |
160 | // Any given object file will normally only have a couple of input | |
161 | // sections with mergeable contents. So we keep the first two input | |
162 | // section numbers inline, and push any further ones into a map. A | |
163 | // value of -1U in first_shnum_ or second_shnum_ means that we don't | |
164 | // have a corresponding entry. | |
165 | unsigned int first_shnum_; | |
166 | Input_merge_map first_map_; | |
167 | unsigned int second_shnum_; | |
168 | Input_merge_map second_map_; | |
169 | Section_merge_maps section_merge_maps_; | |
170 | }; | |
171 | ||
b8e6aad9 ILT |
172 | // A general class for SHF_MERGE data, to hold functions shared by |
173 | // fixed-size constant data and string data. | |
174 | ||
175 | class Output_merge_base : public Output_section_data | |
176 | { | |
177 | public: | |
2ea97941 | 178 | Output_merge_base(uint64_t entsize, uint64_t addralign) |
dbe40a88 | 179 | : Output_section_data(addralign), entsize_(entsize), |
0439c796 DK |
180 | keeps_input_sections_(false), first_relobj_(NULL), first_shndx_(-1), |
181 | input_sections_() | |
b8e6aad9 ILT |
182 | { } |
183 | ||
c0a62865 DK |
184 | // Return the entry size. |
185 | uint64_t | |
186 | entsize() const | |
187 | { return this->entsize_; } | |
188 | ||
189 | // Whether this is a merge string section. This is only true of | |
190 | // Output_merge_string. | |
191 | bool | |
192 | is_string() | |
193 | { return this->do_is_string(); } | |
194 | ||
0439c796 DK |
195 | // Whether this keeps input sections. |
196 | bool | |
197 | keeps_input_sections() const | |
198 | { return this->keeps_input_sections_; } | |
199 | ||
200 | // Set the keeps-input-sections flag. This is virtual so that sub-classes | |
201 | // can perform additional checks. | |
202 | void | |
203 | set_keeps_input_sections() | |
204 | { this->do_set_keeps_input_sections(); } | |
205 | ||
206 | // Return the object of the first merged input section. This used | |
207 | // for script processing. This is NULL if merge section is empty. | |
208 | Relobj* | |
209 | first_relobj() const | |
210 | { return this->first_relobj_; } | |
211 | ||
212 | // Return the section index of the first merged input section. This | |
213 | // is used for script processing. This is valid only if merge section | |
214 | // is not valid. | |
215 | unsigned int | |
216 | first_shndx() const | |
217 | { | |
218 | gold_assert(this->first_relobj_ != NULL); | |
219 | return this->first_shndx_; | |
220 | } | |
221 | ||
222 | // Set of merged input sections. | |
223 | typedef Unordered_set<Section_id, Section_id_hash> Input_sections; | |
224 | ||
225 | // Beginning of merged input sections. | |
226 | Input_sections::const_iterator | |
227 | input_sections_begin() const | |
228 | { | |
229 | gold_assert(this->keeps_input_sections_); | |
230 | return this->input_sections_.begin(); | |
231 | } | |
232 | ||
233 | // Beginning of merged input sections. | |
234 | Input_sections::const_iterator | |
235 | input_sections_end() const | |
236 | { | |
237 | gold_assert(this->keeps_input_sections_); | |
238 | return this->input_sections_.end(); | |
239 | } | |
240 | ||
a9a60db6 | 241 | protected: |
730cdc88 | 242 | // Return the output offset for an input offset. |
b8e6aad9 | 243 | bool |
8383303e ILT |
244 | do_output_offset(const Relobj* object, unsigned int shndx, |
245 | section_offset_type offset, | |
246 | section_offset_type* poutput) const; | |
b8e6aad9 | 247 | |
9b547ce6 | 248 | // This may be overridden by the child class. |
c0a62865 DK |
249 | virtual bool |
250 | do_is_string() | |
251 | { return false; } | |
252 | ||
0439c796 DK |
253 | // This may be overridden by the child class. |
254 | virtual void | |
255 | do_set_keeps_input_sections() | |
256 | { this->keeps_input_sections_ = true; } | |
257 | ||
258 | // Record the merged input section for script processing. | |
259 | void | |
260 | record_input_section(Relobj* relobj, unsigned int shndx); | |
261 | ||
730cdc88 | 262 | private: |
b8e6aad9 ILT |
263 | // The entry size. For fixed-size constants, this is the size of |
264 | // the constants. For strings, this is the size of a character. | |
265 | uint64_t entsize_; | |
0439c796 DK |
266 | // Whether we keep input sections. |
267 | bool keeps_input_sections_; | |
268 | // Object of the first merged input section. We use this for script | |
269 | // processing. | |
270 | Relobj* first_relobj_; | |
271 | // Section index of the first merged input section. | |
272 | unsigned int first_shndx_; | |
273 | // Input sections. We only keep them is keeps_input_sections_ is true. | |
274 | Input_sections input_sections_; | |
b8e6aad9 ILT |
275 | }; |
276 | ||
277 | // Handle SHF_MERGE sections with fixed-size constant data. | |
278 | ||
279 | class Output_merge_data : public Output_merge_base | |
280 | { | |
281 | public: | |
2ea97941 ILT |
282 | Output_merge_data(uint64_t entsize, uint64_t addralign) |
283 | : Output_merge_base(entsize, addralign), p_(NULL), len_(0), alc_(0), | |
38c5e8b4 | 284 | input_count_(0), |
b8e6aad9 ILT |
285 | hashtable_(128, Merge_data_hash(this), Merge_data_eq(this)) |
286 | { } | |
287 | ||
38c5e8b4 | 288 | protected: |
b8e6aad9 ILT |
289 | // Add an input section. |
290 | bool | |
291 | do_add_input_section(Relobj* object, unsigned int shndx); | |
292 | ||
293 | // Set the final data size. | |
294 | void | |
27bc2bce | 295 | set_final_data_size(); |
b8e6aad9 ILT |
296 | |
297 | // Write the data to the file. | |
298 | void | |
299 | do_write(Output_file*); | |
300 | ||
96803768 ILT |
301 | // Write the data to a buffer. |
302 | void | |
303 | do_write_to_buffer(unsigned char*); | |
304 | ||
7d9e3d98 ILT |
305 | // Write to a map file. |
306 | void | |
307 | do_print_to_mapfile(Mapfile* mapfile) const | |
308 | { mapfile->print_output_data(this, _("** merge constants")); } | |
309 | ||
38c5e8b4 ILT |
310 | // Print merge stats to stderr. |
311 | void | |
312 | do_print_merge_stats(const char* section_name); | |
313 | ||
0439c796 DK |
314 | // Set keeps-input-sections flag. |
315 | void | |
316 | do_set_keeps_input_sections() | |
317 | { | |
318 | gold_assert(this->input_count_ == 0); | |
319 | Output_merge_base::do_set_keeps_input_sections(); | |
320 | } | |
321 | ||
b8e6aad9 ILT |
322 | private: |
323 | // We build a hash table of the fixed-size constants. Each constant | |
324 | // is stored as a pointer into the section data we are accumulating. | |
325 | ||
326 | // A key in the hash table. This is an offset in the section | |
327 | // contents we are building. | |
8383303e | 328 | typedef section_offset_type Merge_data_key; |
b8e6aad9 ILT |
329 | |
330 | // Compute the hash code. To do this we need a pointer back to the | |
331 | // object holding the data. | |
332 | class Merge_data_hash | |
333 | { | |
334 | public: | |
335 | Merge_data_hash(const Output_merge_data* pomd) | |
336 | : pomd_(pomd) | |
337 | { } | |
338 | ||
339 | size_t | |
340 | operator()(Merge_data_key) const; | |
341 | ||
342 | private: | |
343 | const Output_merge_data* pomd_; | |
344 | }; | |
345 | ||
346 | friend class Merge_data_hash; | |
347 | ||
348 | // Compare two entries in the hash table for equality. To do this | |
349 | // we need a pointer back to the object holding the data. Note that | |
350 | // we now have a pointer to the object stored in two places in the | |
351 | // hash table. Fixing this would require specializing the hash | |
352 | // table, which would be hard to do portably. | |
353 | class Merge_data_eq | |
354 | { | |
355 | public: | |
356 | Merge_data_eq(const Output_merge_data* pomd) | |
357 | : pomd_(pomd) | |
358 | { } | |
359 | ||
360 | bool | |
361 | operator()(Merge_data_key k1, Merge_data_key k2) const; | |
362 | ||
363 | private: | |
364 | const Output_merge_data* pomd_; | |
365 | }; | |
366 | ||
367 | friend class Merge_data_eq; | |
368 | ||
369 | // The type of the hash table. | |
370 | typedef Unordered_set<Merge_data_key, Merge_data_hash, Merge_data_eq> | |
371 | Merge_data_hashtable; | |
372 | ||
373 | // Given a hash table key, which is just an offset into the section | |
374 | // data, return a pointer to the corresponding constant. | |
375 | const unsigned char* | |
376 | constant(Merge_data_key k) const | |
377 | { | |
8383303e | 378 | gold_assert(k >= 0 && k < static_cast<section_offset_type>(this->len_)); |
b8e6aad9 ILT |
379 | return this->p_ + k; |
380 | } | |
381 | ||
382 | // Add a constant to the output. | |
383 | void | |
384 | add_constant(const unsigned char*); | |
385 | ||
386 | // The accumulated data. | |
387 | unsigned char* p_; | |
388 | // The length of the accumulated data. | |
8383303e | 389 | section_size_type len_; |
b8e6aad9 | 390 | // The size of the allocated buffer. |
8383303e | 391 | section_size_type alc_; |
38c5e8b4 ILT |
392 | // The number of entries seen in input files. |
393 | size_t input_count_; | |
b8e6aad9 ILT |
394 | // The hash table. |
395 | Merge_data_hashtable hashtable_; | |
396 | }; | |
397 | ||
398 | // Handle SHF_MERGE sections with string data. This is a template | |
399 | // based on the type of the characters in the string. | |
400 | ||
401 | template<typename Char_type> | |
402 | class Output_merge_string : public Output_merge_base | |
403 | { | |
404 | public: | |
2ea97941 | 405 | Output_merge_string(uint64_t addralign) |
e31908b6 | 406 | : Output_merge_base(sizeof(Char_type), addralign), stringpool_(addralign), |
fef830db | 407 | merged_strings_lists_(), input_count_(0), input_size_(0) |
87f95776 | 408 | { |
87f95776 ILT |
409 | this->stringpool_.set_no_zero_null(); |
410 | } | |
b8e6aad9 | 411 | |
9a0910c3 | 412 | protected: |
b8e6aad9 ILT |
413 | // Add an input section. |
414 | bool | |
415 | do_add_input_section(Relobj* object, unsigned int shndx); | |
416 | ||
9a0910c3 ILT |
417 | // Do all the final processing after the input sections are read in. |
418 | // Returns the final data size. | |
8383303e | 419 | section_size_type |
9a0910c3 ILT |
420 | finalize_merged_data(); |
421 | ||
b8e6aad9 ILT |
422 | // Set the final data size. |
423 | void | |
27bc2bce | 424 | set_final_data_size(); |
b8e6aad9 ILT |
425 | |
426 | // Write the data to the file. | |
427 | void | |
428 | do_write(Output_file*); | |
429 | ||
96803768 ILT |
430 | // Write the data to a buffer. |
431 | void | |
432 | do_write_to_buffer(unsigned char*); | |
433 | ||
7d9e3d98 ILT |
434 | // Write to a map file. |
435 | void | |
436 | do_print_to_mapfile(Mapfile* mapfile) const | |
437 | { mapfile->print_output_data(this, _("** merge strings")); } | |
438 | ||
38c5e8b4 ILT |
439 | // Print merge stats to stderr. |
440 | void | |
441 | do_print_merge_stats(const char* section_name); | |
442 | ||
9a0910c3 ILT |
443 | // Writes the stringpool to a buffer. |
444 | void | |
8383303e | 445 | stringpool_to_buffer(unsigned char* buffer, section_size_type buffer_size) |
9a0910c3 ILT |
446 | { this->stringpool_.write_to_buffer(buffer, buffer_size); } |
447 | ||
448 | // Clears all the data in the stringpool, to save on memory. | |
449 | void | |
450 | clear_stringpool() | |
bc2c67ff | 451 | { this->stringpool_.clear(); } |
9a0910c3 | 452 | |
c0a62865 DK |
453 | // Whether this is a merge string section. |
454 | virtual bool | |
455 | do_is_string() | |
456 | { return true; } | |
457 | ||
0439c796 DK |
458 | // Set keeps-input-sections flag. |
459 | void | |
460 | do_set_keeps_input_sections() | |
461 | { | |
462 | gold_assert(this->input_count_ == 0); | |
463 | Output_merge_base::do_set_keeps_input_sections(); | |
464 | } | |
465 | ||
b8e6aad9 | 466 | private: |
38c5e8b4 ILT |
467 | // The name of the string type, for stats. |
468 | const char* | |
469 | string_name(); | |
470 | ||
b8e6aad9 ILT |
471 | // As we see input sections, we build a mapping from object, section |
472 | // index and offset to strings. | |
42e3fe0d | 473 | struct Merged_string |
b8e6aad9 | 474 | { |
42e3fe0d | 475 | // The offset in the input section. |
8383303e | 476 | section_offset_type offset; |
2030fba0 ILT |
477 | // The key in the Stringpool. |
478 | Stringpool::Key stringpool_key; | |
b8e6aad9 | 479 | |
76897331 CC |
480 | Merged_string(section_offset_type offseta, Stringpool::Key stringpool_keya) |
481 | : offset(offseta), stringpool_key(stringpool_keya) | |
b8e6aad9 ILT |
482 | { } |
483 | }; | |
484 | ||
42e3fe0d | 485 | typedef std::vector<Merged_string> Merged_strings; |
b8e6aad9 | 486 | |
76897331 CC |
487 | struct Merged_strings_list |
488 | { | |
489 | // The input object where the strings were found. | |
490 | Relobj* object; | |
491 | // The input section in the input object. | |
492 | unsigned int shndx; | |
493 | // The list of merged strings. | |
494 | Merged_strings merged_strings; | |
495 | ||
496 | Merged_strings_list(Relobj* objecta, unsigned int shndxa) | |
497 | : object(objecta), shndx(shndxa), merged_strings() | |
498 | { } | |
499 | }; | |
500 | ||
501 | typedef std::vector<Merged_strings_list*> Merged_strings_lists; | |
502 | ||
b8e6aad9 ILT |
503 | // As we see the strings, we add them to a Stringpool. |
504 | Stringpool_template<Char_type> stringpool_; | |
505 | // Map from a location in an input object to an entry in the | |
506 | // Stringpool. | |
76897331 | 507 | Merged_strings_lists merged_strings_lists_; |
38c5e8b4 ILT |
508 | // The number of entries seen in input files. |
509 | size_t input_count_; | |
fef830db CC |
510 | // The total size of input sections. |
511 | size_t input_size_; | |
b8e6aad9 ILT |
512 | }; |
513 | ||
514 | } // End namespace gold. | |
515 | ||
516 | #endif // !defined(GOLD_MERGE_H) |