1 // merge.h -- handle section merging for gold -*- C++ -*-
3 // Copyright (C) 2006-2015 Free Software Foundation, Inc.
4 // Written by Ian Lance Taylor <iant@google.com>.
6 // This file is part of gold.
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.
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.
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.
30 #include "stringpool.h"
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
39 // found in the output_sections_ field of the Object.
41 class Object_merge_map
45 : first_shnum_(-1U), first_map_(),
46 second_shnum_(-1U), second_map_(),
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.
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
);
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.
70 get_output_offset(unsigned int shndx
,
71 section_offset_type offset
,
72 section_offset_type
* output_offset
);
74 const Output_section_data
*
75 find_merge_section(unsigned int shndx
) const;
77 // Initialize an mapping from input offsets to output addresses for
78 // section SHNDX. STARTING_ADDRESS is the output address of the
82 initialize_input_to_output_map(
84 typename
elfcpp::Elf_types
<size
>::Elf_Addr starting_address
,
85 Unordered_map
<section_offset_type
,
86 typename
elfcpp::Elf_types
<size
>::Elf_Addr
>*);
89 // Map input section offsets to a length and an output section
90 // offset. An output section offset of -1 means that this part of
91 // the input section is being discarded.
92 struct Input_merge_entry
94 // The offset in the input section.
95 section_offset_type input_offset
;
97 section_size_type length
;
98 // The offset in the output section.
99 section_offset_type output_offset
;
102 // A less-than comparison routine for Input_merge_entry.
103 struct Input_merge_compare
106 operator()(const Input_merge_entry
& i1
, const Input_merge_entry
& i2
) const
107 { return i1
.input_offset
< i2
.input_offset
; }
110 // A list of entries for a particular input section.
111 struct Input_merge_map
113 typedef std::vector
<Input_merge_entry
> Entries
;
115 // We store these with the Relobj, and we look them up by input
116 // section. It is possible to have two different merge maps
117 // associated with a single output section. For example, this
118 // happens routinely with .rodata, when merged string constants
119 // and merged fixed size constants are both put into .rodata. The
120 // output offset that we store is not the offset from the start of
121 // the output section; it is the offset from the start of the
122 // merged data in the output section. That means that the caller
123 // is going to add the offset of the merged data within the output
124 // section, which means that the caller needs to know which set of
125 // merged data it found the entry in. So it's not enough to find
126 // this data based on the input section and the output section; we
127 // also have to find it based on a set of merged data in the
128 // output section. In order to verify that we are looking at the
129 // right data, we store a pointer to the Merge_map here, and we
130 // pass in a pointer when looking at the data. If we are asked to
131 // look up information for a different Merge_map, we report that
132 // we don't have it, rather than trying a lookup and returning an
133 // answer which will receive the wrong offset.
134 const Output_section_data
* output_data
;
135 // The list of mappings.
137 // Whether the ENTRIES field is sorted by input_offset.
141 : output_data(NULL
), entries(), sorted(true)
145 // Map input section indices to merge maps.
146 typedef std::map
<unsigned int, Input_merge_map
*> Section_merge_maps
;
148 // Return a pointer to the Input_merge_map to use for the input
149 // section SHNDX, or NULL.
150 const Input_merge_map
*
151 get_input_merge_map(unsigned int shndx
) const;
154 get_input_merge_map(unsigned int shndx
) {
155 return const_cast<Input_merge_map
*>(static_cast<const Object_merge_map
*>(
156 this)->get_input_merge_map(shndx
));
159 // Get or make the Input_merge_map to use for the section SHNDX
162 get_or_make_input_merge_map(const Output_section_data
* merge_map
,
165 // Any given object file will normally only have a couple of input
166 // sections with mergeable contents. So we keep the first two input
167 // section numbers inline, and push any further ones into a map. A
168 // value of -1U in first_shnum_ or second_shnum_ means that we don't
169 // have a corresponding entry.
170 unsigned int first_shnum_
;
171 Input_merge_map first_map_
;
172 unsigned int second_shnum_
;
173 Input_merge_map second_map_
;
174 Section_merge_maps section_merge_maps_
;
177 // A general class for SHF_MERGE data, to hold functions shared by
178 // fixed-size constant data and string data.
180 class Output_merge_base
: public Output_section_data
183 Output_merge_base(uint64_t entsize
, uint64_t addralign
)
184 : Output_section_data(addralign
), entsize_(entsize
),
185 keeps_input_sections_(false), first_relobj_(NULL
), first_shndx_(-1),
189 // Return the entry size.
192 { return this->entsize_
; }
194 // Whether this is a merge string section. This is only true of
195 // Output_merge_string.
198 { return this->do_is_string(); }
200 // Whether this keeps input sections.
202 keeps_input_sections() const
203 { return this->keeps_input_sections_
; }
205 // Set the keeps-input-sections flag. This is virtual so that sub-classes
206 // can perform additional checks.
208 set_keeps_input_sections()
209 { this->do_set_keeps_input_sections(); }
211 // Return the object of the first merged input section. This used
212 // for script processing. This is NULL if merge section is empty.
215 { return this->first_relobj_
; }
217 // Return the section index of the first merged input section. This
218 // is used for script processing. This is valid only if merge section
223 gold_assert(this->first_relobj_
!= NULL
);
224 return this->first_shndx_
;
227 // Set of merged input sections.
228 typedef Unordered_set
<Section_id
, Section_id_hash
> Input_sections
;
230 // Beginning of merged input sections.
231 Input_sections::const_iterator
232 input_sections_begin() const
234 gold_assert(this->keeps_input_sections_
);
235 return this->input_sections_
.begin();
238 // Beginning of merged input sections.
239 Input_sections::const_iterator
240 input_sections_end() const
242 gold_assert(this->keeps_input_sections_
);
243 return this->input_sections_
.end();
247 // Return the output offset for an input offset.
249 do_output_offset(const Relobj
* object
, unsigned int shndx
,
250 section_offset_type offset
,
251 section_offset_type
* poutput
) const;
253 // This may be overridden by the child class.
258 // This may be overridden by the child class.
260 do_set_keeps_input_sections()
261 { this->keeps_input_sections_
= true; }
263 // Record the merged input section for script processing.
265 record_input_section(Relobj
* relobj
, unsigned int shndx
);
268 // The entry size. For fixed-size constants, this is the size of
269 // the constants. For strings, this is the size of a character.
271 // Whether we keep input sections.
272 bool keeps_input_sections_
;
273 // Object of the first merged input section. We use this for script
275 Relobj
* first_relobj_
;
276 // Section index of the first merged input section.
277 unsigned int first_shndx_
;
278 // Input sections. We only keep them is keeps_input_sections_ is true.
279 Input_sections input_sections_
;
282 // Handle SHF_MERGE sections with fixed-size constant data.
284 class Output_merge_data
: public Output_merge_base
287 Output_merge_data(uint64_t entsize
, uint64_t addralign
)
288 : Output_merge_base(entsize
, addralign
), p_(NULL
), len_(0), alc_(0),
290 hashtable_(128, Merge_data_hash(this), Merge_data_eq(this))
294 // Add an input section.
296 do_add_input_section(Relobj
* object
, unsigned int shndx
);
298 // Set the final data size.
300 set_final_data_size();
302 // Write the data to the file.
304 do_write(Output_file
*);
306 // Write the data to a buffer.
308 do_write_to_buffer(unsigned char*);
310 // Write to a map file.
312 do_print_to_mapfile(Mapfile
* mapfile
) const
313 { mapfile
->print_output_data(this, _("** merge constants")); }
315 // Print merge stats to stderr.
317 do_print_merge_stats(const char* section_name
);
319 // Set keeps-input-sections flag.
321 do_set_keeps_input_sections()
323 gold_assert(this->input_count_
== 0);
324 Output_merge_base::do_set_keeps_input_sections();
328 // We build a hash table of the fixed-size constants. Each constant
329 // is stored as a pointer into the section data we are accumulating.
331 // A key in the hash table. This is an offset in the section
332 // contents we are building.
333 typedef section_offset_type Merge_data_key
;
335 // Compute the hash code. To do this we need a pointer back to the
336 // object holding the data.
337 class Merge_data_hash
340 Merge_data_hash(const Output_merge_data
* pomd
)
345 operator()(Merge_data_key
) const;
348 const Output_merge_data
* pomd_
;
351 friend class Merge_data_hash
;
353 // Compare two entries in the hash table for equality. To do this
354 // we need a pointer back to the object holding the data. Note that
355 // we now have a pointer to the object stored in two places in the
356 // hash table. Fixing this would require specializing the hash
357 // table, which would be hard to do portably.
361 Merge_data_eq(const Output_merge_data
* pomd
)
366 operator()(Merge_data_key k1
, Merge_data_key k2
) const;
369 const Output_merge_data
* pomd_
;
372 friend class Merge_data_eq
;
374 // The type of the hash table.
375 typedef Unordered_set
<Merge_data_key
, Merge_data_hash
, Merge_data_eq
>
376 Merge_data_hashtable
;
378 // Given a hash table key, which is just an offset into the section
379 // data, return a pointer to the corresponding constant.
381 constant(Merge_data_key k
) const
383 gold_assert(k
>= 0 && k
< static_cast<section_offset_type
>(this->len_
));
387 // Add a constant to the output.
389 add_constant(const unsigned char*);
391 // The accumulated data.
393 // The length of the accumulated data.
394 section_size_type len_
;
395 // The size of the allocated buffer.
396 section_size_type alc_
;
397 // The number of entries seen in input files.
400 Merge_data_hashtable hashtable_
;
403 // Handle SHF_MERGE sections with string data. This is a template
404 // based on the type of the characters in the string.
406 template<typename Char_type
>
407 class Output_merge_string
: public Output_merge_base
410 Output_merge_string(uint64_t addralign
)
411 : Output_merge_base(sizeof(Char_type
), addralign
), stringpool_(addralign
),
412 merged_strings_lists_(), input_count_(0), input_size_(0)
414 this->stringpool_
.set_no_zero_null();
418 // Add an input section.
420 do_add_input_section(Relobj
* object
, unsigned int shndx
);
422 // Do all the final processing after the input sections are read in.
423 // Returns the final data size.
425 finalize_merged_data();
427 // Set the final data size.
429 set_final_data_size();
431 // Write the data to the file.
433 do_write(Output_file
*);
435 // Write the data to a buffer.
437 do_write_to_buffer(unsigned char*);
439 // Write to a map file.
441 do_print_to_mapfile(Mapfile
* mapfile
) const
442 { mapfile
->print_output_data(this, _("** merge strings")); }
444 // Print merge stats to stderr.
446 do_print_merge_stats(const char* section_name
);
448 // Writes the stringpool to a buffer.
450 stringpool_to_buffer(unsigned char* buffer
, section_size_type buffer_size
)
451 { this->stringpool_
.write_to_buffer(buffer
, buffer_size
); }
453 // Clears all the data in the stringpool, to save on memory.
456 { this->stringpool_
.clear(); }
458 // Whether this is a merge string section.
463 // Set keeps-input-sections flag.
465 do_set_keeps_input_sections()
467 gold_assert(this->input_count_
== 0);
468 Output_merge_base::do_set_keeps_input_sections();
472 // The name of the string type, for stats.
476 // As we see input sections, we build a mapping from object, section
477 // index and offset to strings.
480 // The offset in the input section.
481 section_offset_type offset
;
482 // The key in the Stringpool.
483 Stringpool::Key stringpool_key
;
485 Merged_string(section_offset_type offseta
, Stringpool::Key stringpool_keya
)
486 : offset(offseta
), stringpool_key(stringpool_keya
)
490 typedef std::vector
<Merged_string
> Merged_strings
;
492 struct Merged_strings_list
494 // The input object where the strings were found.
496 // The input section in the input object.
498 // The list of merged strings.
499 Merged_strings merged_strings
;
501 Merged_strings_list(Relobj
* objecta
, unsigned int shndxa
)
502 : object(objecta
), shndx(shndxa
), merged_strings()
506 typedef std::vector
<Merged_strings_list
*> Merged_strings_lists
;
508 // As we see the strings, we add them to a Stringpool.
509 Stringpool_template
<Char_type
> stringpool_
;
510 // Map from a location in an input object to an entry in the
512 Merged_strings_lists merged_strings_lists_
;
513 // The number of entries seen in input files.
515 // The total size of input sections.
519 } // End namespace gold.
521 #endif // !defined(GOLD_MERGE_H)