1 // merge.cc -- handle section merging for gold
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.
29 #include "compressed_output.h"
34 // Class Object_merge_map.
38 Object_merge_map::~Object_merge_map()
40 for (Section_merge_maps::iterator p
= this->section_merge_maps_
.begin();
41 p
!= this->section_merge_maps_
.end();
46 // Get the Input_merge_map to use for an input section, or NULL.
48 Object_merge_map::Input_merge_map
*
49 Object_merge_map::get_input_merge_map(unsigned int shndx
)
51 gold_assert(shndx
!= -1U);
52 if (shndx
== this->first_shnum_
)
53 return &this->first_map_
;
54 if (shndx
== this->second_shnum_
)
55 return &this->second_map_
;
56 Section_merge_maps::const_iterator p
= this->section_merge_maps_
.find(shndx
);
57 if (p
!= this->section_merge_maps_
.end())
62 // Get or create the Input_merge_map to use for an input section.
64 Object_merge_map::Input_merge_map
*
65 Object_merge_map::get_or_make_input_merge_map(const Merge_map
* merge_map
,
68 Input_merge_map
* map
= this->get_input_merge_map(shndx
);
71 // For a given input section in a given object, every mapping
72 // must be done with the same Merge_map.
73 gold_assert(map
->merge_map
== merge_map
);
77 // We need to create a new entry.
78 if (this->first_shnum_
== -1U)
80 this->first_shnum_
= shndx
;
81 this->first_map_
.merge_map
= merge_map
;
82 return &this->first_map_
;
84 if (this->second_shnum_
== -1U)
86 this->second_shnum_
= shndx
;
87 this->second_map_
.merge_map
= merge_map
;
88 return &this->second_map_
;
91 Input_merge_map
* new_map
= new Input_merge_map
;
92 new_map
->merge_map
= merge_map
;
93 this->section_merge_maps_
[shndx
] = new_map
;
100 Object_merge_map::add_mapping(const Merge_map
* merge_map
, unsigned int shndx
,
101 section_offset_type input_offset
,
102 section_size_type length
,
103 section_offset_type output_offset
)
105 Input_merge_map
* map
= this->get_or_make_input_merge_map(merge_map
, shndx
);
107 // Try to merge the new entry in the last one we saw.
108 if (!map
->entries
.empty())
110 Input_merge_entry
& entry(map
->entries
.back());
112 // Use section_size_type to avoid signed/unsigned warnings.
113 section_size_type input_offset_u
= input_offset
;
114 section_size_type output_offset_u
= output_offset
;
116 // If this entry is not in order, we need to sort the vector
117 // before looking anything up.
118 if (input_offset_u
< entry
.input_offset
+ entry
.length
)
120 gold_assert(input_offset
< entry
.input_offset
);
121 gold_assert(input_offset_u
+ length
122 <= static_cast<section_size_type
>(entry
.input_offset
));
125 else if (entry
.input_offset
+ entry
.length
== input_offset_u
126 && (output_offset
== -1
127 ? entry
.output_offset
== -1
128 : entry
.output_offset
+ entry
.length
== output_offset_u
))
130 entry
.length
+= length
;
135 Input_merge_entry entry
;
136 entry
.input_offset
= input_offset
;
137 entry
.length
= length
;
138 entry
.output_offset
= output_offset
;
139 map
->entries
.push_back(entry
);
142 // Get the output offset for an input address.
145 Object_merge_map::get_output_offset(const Merge_map
* merge_map
,
147 section_offset_type input_offset
,
148 section_offset_type
* output_offset
)
150 Input_merge_map
* map
= this->get_input_merge_map(shndx
);
152 || (merge_map
!= NULL
&& map
->merge_map
!= merge_map
))
157 std::sort(map
->entries
.begin(), map
->entries
.end(),
158 Input_merge_compare());
162 Input_merge_entry entry
;
163 entry
.input_offset
= input_offset
;
164 std::vector
<Input_merge_entry
>::const_iterator p
=
165 std::upper_bound(map
->entries
.begin(), map
->entries
.end(),
166 entry
, Input_merge_compare());
167 if (p
== map
->entries
.begin())
170 gold_assert(p
->input_offset
<= input_offset
);
172 if (input_offset
- p
->input_offset
173 >= static_cast<section_offset_type
>(p
->length
))
176 *output_offset
= p
->output_offset
;
177 if (*output_offset
!= -1)
178 *output_offset
+= (input_offset
- p
->input_offset
);
182 // Return whether this is the merge map for section SHNDX.
185 Object_merge_map::is_merge_section_for(const Merge_map
* merge_map
,
188 Input_merge_map
* map
= this->get_input_merge_map(shndx
);
189 return map
!= NULL
&& map
->merge_map
== merge_map
;
192 // Initialize a mapping from input offsets to output addresses.
196 Object_merge_map::initialize_input_to_output_map(
198 typename
elfcpp::Elf_types
<size
>::Elf_Addr starting_address
,
199 Unordered_map
<section_offset_type
,
200 typename
elfcpp::Elf_types
<size
>::Elf_Addr
>* initialize_map
)
202 Input_merge_map
* map
= this->get_input_merge_map(shndx
);
203 gold_assert(map
!= NULL
);
205 gold_assert(initialize_map
->empty());
206 // We know how many entries we are going to add.
207 // reserve_unordered_map takes an expected count of buckets, not a
208 // count of elements, so double it to try to reduce collisions.
209 reserve_unordered_map(initialize_map
, map
->entries
.size() * 2);
211 for (Input_merge_map::Entries::const_iterator p
= map
->entries
.begin();
212 p
!= map
->entries
.end();
215 section_offset_type output_offset
= p
->output_offset
;
216 if (output_offset
!= -1)
217 output_offset
+= starting_address
;
220 // If we see a relocation against an address we have chosen
221 // to discard, we relocate to zero. FIXME: We could also
222 // issue a warning in this case; that would require
223 // reporting this somehow and checking it in the routines in
227 initialize_map
->insert(std::make_pair(p
->input_offset
, output_offset
));
233 // Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in input
234 // section SHNDX in object OBJECT to an OUTPUT_OFFSET in merged data
235 // in an output section.
238 Merge_map::add_mapping(Relobj
* object
, unsigned int shndx
,
239 section_offset_type offset
, section_size_type length
,
240 section_offset_type output_offset
)
242 gold_assert(object
!= NULL
);
243 Object_merge_map
* object_merge_map
= object
->merge_map();
244 if (object_merge_map
== NULL
)
246 object_merge_map
= new Object_merge_map();
247 object
->set_merge_map(object_merge_map
);
250 object_merge_map
->add_mapping(this, shndx
, offset
, length
, output_offset
);
253 // Return the output offset for an input address. The input address
254 // is at offset OFFSET in section SHNDX in OBJECT. This sets
255 // *OUTPUT_OFFSET to the offset in the merged data in the output
256 // section. This returns true if the mapping is known, false
260 Merge_map::get_output_offset(const Relobj
* object
, unsigned int shndx
,
261 section_offset_type offset
,
262 section_offset_type
* output_offset
) const
264 Object_merge_map
* object_merge_map
= object
->merge_map();
265 if (object_merge_map
== NULL
)
267 return object_merge_map
->get_output_offset(this, shndx
, offset
,
271 // Return whether this is the merge section for SHNDX in OBJECT.
274 Merge_map::is_merge_section_for(const Relobj
* object
, unsigned int shndx
) const
276 Object_merge_map
* object_merge_map
= object
->merge_map();
277 if (object_merge_map
== NULL
)
279 return object_merge_map
->is_merge_section_for(this, shndx
);
282 // Class Output_merge_base.
284 // Return the output offset for an input offset. The input address is
285 // at offset OFFSET in section SHNDX in OBJECT. If we know the
286 // offset, set *POUTPUT and return true. Otherwise return false.
289 Output_merge_base::do_output_offset(const Relobj
* object
,
291 section_offset_type offset
,
292 section_offset_type
* poutput
) const
294 return this->merge_map_
.get_output_offset(object
, shndx
, offset
, poutput
);
297 // Return whether this is the merge section for SHNDX in OBJECT.
300 Output_merge_base::do_is_merge_section_for(const Relobj
* object
,
301 unsigned int shndx
) const
303 return this->merge_map_
.is_merge_section_for(object
, shndx
);
306 // Record a merged input section for script processing.
309 Output_merge_base::record_input_section(Relobj
* relobj
, unsigned int shndx
)
311 gold_assert(this->keeps_input_sections_
&& relobj
!= NULL
);
312 // If this is the first input section, record it. We need do this because
313 // this->input_sections_ is unordered.
314 if (this->first_relobj_
== NULL
)
316 this->first_relobj_
= relobj
;
317 this->first_shndx_
= shndx
;
320 std::pair
<Input_sections::iterator
, bool> result
=
321 this->input_sections_
.insert(Section_id(relobj
, shndx
));
322 // We should insert a merge section once only.
323 gold_assert(result
.second
);
326 // Class Output_merge_data.
328 // Compute the hash code for a fixed-size constant.
331 Output_merge_data::Merge_data_hash::operator()(Merge_data_key k
) const
333 const unsigned char* p
= this->pomd_
->constant(k
);
334 section_size_type entsize
=
335 convert_to_section_size_type(this->pomd_
->entsize());
337 // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
338 if (sizeof(size_t) == 8)
340 size_t result
= static_cast<size_t>(14695981039346656037ULL);
341 for (section_size_type i
= 0; i
< entsize
; ++i
)
343 result
&= (size_t) *p
++;
344 result
*= 1099511628211ULL;
350 size_t result
= 2166136261UL;
351 for (section_size_type i
= 0; i
< entsize
; ++i
)
353 result
^= (size_t) *p
++;
354 result
*= 16777619UL;
360 // Return whether one hash table key equals another.
363 Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1
,
364 Merge_data_key k2
) const
366 const unsigned char* p1
= this->pomd_
->constant(k1
);
367 const unsigned char* p2
= this->pomd_
->constant(k2
);
368 return memcmp(p1
, p2
, this->pomd_
->entsize()) == 0;
371 // Add a constant to the end of the section contents.
374 Output_merge_data::add_constant(const unsigned char* p
)
376 section_size_type entsize
= convert_to_section_size_type(this->entsize());
377 section_size_type addralign
=
378 convert_to_section_size_type(this->addralign());
379 section_size_type addsize
= std::max(entsize
, addralign
);
380 if (this->len_
+ addsize
> this->alc_
)
383 this->alc_
= 128 * addsize
;
386 this->p_
= static_cast<unsigned char*>(realloc(this->p_
, this->alc_
));
387 if (this->p_
== NULL
)
391 memcpy(this->p_
+ this->len_
, p
, entsize
);
392 if (addsize
> entsize
)
393 memset(this->p_
+ this->len_
+ entsize
, 0, addsize
- entsize
);
394 this->len_
+= addsize
;
397 // Add the input section SHNDX in OBJECT to a merged output section
398 // which holds fixed length constants. Return whether we were able to
399 // handle the section; if not, it will be linked as usual without
403 Output_merge_data::do_add_input_section(Relobj
* object
, unsigned int shndx
)
405 section_size_type len
;
407 const unsigned char* p
= object
->decompressed_section_contents(shndx
, &len
,
410 section_size_type entsize
= convert_to_section_size_type(this->entsize());
412 if (len
% entsize
!= 0)
419 this->input_count_
+= len
/ entsize
;
421 for (section_size_type i
= 0; i
< len
; i
+= entsize
, p
+= entsize
)
423 // Add the constant to the section contents. If we find that it
424 // is already in the hash table, we will remove it again.
425 Merge_data_key k
= this->len_
;
426 this->add_constant(p
);
428 std::pair
<Merge_data_hashtable::iterator
, bool> ins
=
429 this->hashtable_
.insert(k
);
433 // Key was already present. Remove the copy we just added.
434 this->len_
-= entsize
;
438 // Record the offset of this constant in the output section.
439 this->add_mapping(object
, shndx
, i
, entsize
, k
);
442 // For script processing, we keep the input sections.
443 if (this->keeps_input_sections())
444 record_input_section(object
, shndx
);
452 // Set the final data size in a merged output section with fixed size
456 Output_merge_data::set_final_data_size()
458 // Release the memory we don't need.
459 this->p_
= static_cast<unsigned char*>(realloc(this->p_
, this->len_
));
460 // An Output_merge_data object may be empty and realloc is allowed
461 // to return a NULL pointer in this case. An Output_merge_data is empty
462 // if all its input sections have sizes that are not multiples of entsize.
463 gold_assert(this->p_
!= NULL
|| this->len_
== 0);
464 this->set_data_size(this->len_
);
467 // Write the data of a merged output section with fixed size constants
471 Output_merge_data::do_write(Output_file
* of
)
473 of
->write(this->offset(), this->p_
, this->len_
);
476 // Write the data to a buffer.
479 Output_merge_data::do_write_to_buffer(unsigned char* buffer
)
481 memcpy(buffer
, this->p_
, this->len_
);
484 // Print merge stats to stderr.
487 Output_merge_data::do_print_merge_stats(const char* section_name
)
490 _("%s: %s merged constants size: %lu; input: %zu; output: %zu\n"),
491 program_name
, section_name
,
492 static_cast<unsigned long>(this->entsize()),
493 this->input_count_
, this->hashtable_
.size());
496 // Class Output_merge_string.
498 // Add an input section to a merged string section.
500 template<typename Char_type
>
502 Output_merge_string
<Char_type
>::do_add_input_section(Relobj
* object
,
505 section_size_type sec_len
;
507 const unsigned char* pdata
= object
->decompressed_section_contents(shndx
,
511 const Char_type
* p
= reinterpret_cast<const Char_type
*>(pdata
);
512 const Char_type
* pend
= p
+ sec_len
/ sizeof(Char_type
);
513 const Char_type
* pend0
= pend
;
515 if (sec_len
% sizeof(Char_type
) != 0)
517 object
->error(_("mergeable string section length not multiple of "
526 gold_warning(_("%s: last entry in mergeable string section '%s' "
527 "not null terminated"),
528 object
->name().c_str(),
529 object
->section_name(shndx
).c_str());
530 // Find the end of the last NULL-terminated string in the buffer.
531 while (pend0
> p
&& pend0
[-1] != 0)
535 Merged_strings_list
* merged_strings_list
=
536 new Merged_strings_list(object
, shndx
);
537 this->merged_strings_lists_
.push_back(merged_strings_list
);
538 Merged_strings
& merged_strings
= merged_strings_list
->merged_strings
;
540 // Count the number of non-null strings in the section and size the list.
542 const Char_type
* pt
= p
;
545 size_t len
= string_length(pt
);
552 merged_strings
.reserve(count
+ 1);
554 // The index I is in bytes, not characters.
555 section_size_type i
= 0;
557 // We assume here that the beginning of the section is correctly
558 // aligned, so each string within the section must retain the same
560 uintptr_t init_align_modulo
= (reinterpret_cast<uintptr_t>(pdata
)
561 & (this->addralign() - 1));
562 bool has_misaligned_strings
= false;
566 size_t len
= p
< pend0
? string_length(p
) : pend
- p
;
568 // Within merge input section each string must be aligned.
570 && ((reinterpret_cast<uintptr_t>(p
) & (this->addralign() - 1))
571 != init_align_modulo
))
572 has_misaligned_strings
= true;
575 this->stringpool_
.add_with_length(p
, len
, true, &key
);
577 merged_strings
.push_back(Merged_string(i
, key
));
579 i
+= (len
+ 1) * sizeof(Char_type
);
582 // Record the last offset in the input section so that we can
583 // compute the length of the last string.
584 merged_strings
.push_back(Merged_string(i
, 0));
586 this->input_count_
+= count
;
587 this->input_size_
+= i
;
589 if (has_misaligned_strings
)
590 gold_warning(_("%s: section %s contains incorrectly aligned strings;"
591 " the alignment of those strings won't be preserved"),
592 object
->name().c_str(),
593 object
->section_name(shndx
).c_str());
595 // For script processing, we keep the input sections.
596 if (this->keeps_input_sections())
597 record_input_section(object
, shndx
);
605 // Finalize the mappings from the input sections to the output
606 // section, and return the final data size.
608 template<typename Char_type
>
610 Output_merge_string
<Char_type
>::finalize_merged_data()
612 this->stringpool_
.set_string_offsets();
614 for (typename
Merged_strings_lists::const_iterator l
=
615 this->merged_strings_lists_
.begin();
616 l
!= this->merged_strings_lists_
.end();
619 section_offset_type last_input_offset
= 0;
620 section_offset_type last_output_offset
= 0;
621 for (typename
Merged_strings::const_iterator p
=
622 (*l
)->merged_strings
.begin();
623 p
!= (*l
)->merged_strings
.end();
626 section_size_type length
= p
->offset
- last_input_offset
;
628 this->add_mapping((*l
)->object
, (*l
)->shndx
, last_input_offset
,
629 length
, last_output_offset
);
630 last_input_offset
= p
->offset
;
631 if (p
->stringpool_key
!= 0)
633 this->stringpool_
.get_offset_from_key(p
->stringpool_key
);
638 // Save some memory. This also ensures that this function will work
639 // if called twice, as may happen if Layout::set_segment_offsets
640 // finds a better alignment.
641 this->merged_strings_lists_
.clear();
643 return this->stringpool_
.get_strtab_size();
646 template<typename Char_type
>
648 Output_merge_string
<Char_type
>::set_final_data_size()
650 const off_t final_data_size
= this->finalize_merged_data();
651 this->set_data_size(final_data_size
);
654 // Write out a merged string section.
656 template<typename Char_type
>
658 Output_merge_string
<Char_type
>::do_write(Output_file
* of
)
660 this->stringpool_
.write(of
, this->offset());
663 // Write a merged string section to a buffer.
665 template<typename Char_type
>
667 Output_merge_string
<Char_type
>::do_write_to_buffer(unsigned char* buffer
)
669 this->stringpool_
.write_to_buffer(buffer
, this->data_size());
672 // Return the name of the types of string to use with
673 // do_print_merge_stats.
675 template<typename Char_type
>
677 Output_merge_string
<Char_type
>::string_name()
685 Output_merge_string
<char>::string_name()
692 Output_merge_string
<uint16_t>::string_name()
694 return "16-bit strings";
699 Output_merge_string
<uint32_t>::string_name()
701 return "32-bit strings";
704 // Print merge stats to stderr.
706 template<typename Char_type
>
708 Output_merge_string
<Char_type
>::do_print_merge_stats(const char* section_name
)
711 snprintf(buf
, sizeof buf
, "%s merged %s", section_name
, this->string_name());
712 fprintf(stderr
, _("%s: %s input bytes: %zu\n"),
713 program_name
, buf
, this->input_size_
);
714 fprintf(stderr
, _("%s: %s input strings: %zu\n"),
715 program_name
, buf
, this->input_count_
);
716 this->stringpool_
.print_stats(buf
);
719 // Instantiate the templates we need.
722 class Output_merge_string
<char>;
725 class Output_merge_string
<uint16_t>;
728 class Output_merge_string
<uint32_t>;
730 #if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_32_BIG)
733 Object_merge_map::initialize_input_to_output_map
<32>(
735 elfcpp::Elf_types
<32>::Elf_Addr starting_address
,
736 Unordered_map
<section_offset_type
, elfcpp::Elf_types
<32>::Elf_Addr
>*);
739 #if defined(HAVE_TARGET_64_LITTLE) || defined(HAVE_TARGET_64_BIG)
742 Object_merge_map::initialize_input_to_output_map
<64>(
744 elfcpp::Elf_types
<64>::Elf_Addr starting_address
,
745 Unordered_map
<section_offset_type
, elfcpp::Elf_types
<64>::Elf_Addr
>*);
748 } // End namespace gold.