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