1 // merge.cc -- handle section merging for gold 2 3 // Copyright (C) 2006-2020 Free Software Foundation, Inc. 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 23 #include "gold.h" 24 25 #include <cstdlib> 26 #include <algorithm> 27 28 #include "merge.h" 29 #include "compressed_output.h" 30 31 namespace gold 32 { 33 34 // Class Object_merge_map. 35 36 // Destructor. 37 38 Object_merge_map::~Object_merge_map() 39 { 40 for (Section_merge_maps::iterator p = this->section_merge_maps_.begin(); 41 p != this->section_merge_maps_.end(); 42 ++p) 43 delete p->second; 44 } 45 46 // Get the Input_merge_map to use for an input section, or NULL. 47 48 const Object_merge_map::Input_merge_map* 49 Object_merge_map::get_input_merge_map(unsigned int shndx) const 50 { 51 gold_assert(shndx != -1U); 52 const Section_merge_maps &maps = this->section_merge_maps_; 53 for (Section_merge_maps::const_iterator i = maps.begin(), e = maps.end(); 54 i != e; ++i) 55 { 56 if (i->first == shndx) 57 return i->second; 58 } 59 return NULL; 60 } 61 62 // Get or create the Input_merge_map to use for an input section. 63 64 Object_merge_map::Input_merge_map* 65 Object_merge_map::get_or_make_input_merge_map( 66 const Output_section_data* output_data, unsigned int shndx) { 67 Input_merge_map* map = this->get_input_merge_map(shndx); 68 if (map != NULL) 69 { 70 // For a given input section in a given object, every mapping 71 // must be done with the same Merge_map. 72 gold_assert(map->output_data == output_data); 73 return map; 74 } 75 76 Input_merge_map* new_map = new Input_merge_map; 77 new_map->output_data = output_data; 78 Section_merge_maps &maps = this->section_merge_maps_; 79 maps.push_back(std::make_pair(shndx, new_map)); 80 return new_map; 81 } 82 83 // Add a mapping. 84 85 void 86 Object_merge_map::add_mapping(const Output_section_data* output_data, 87 unsigned int shndx, 88 section_offset_type input_offset, 89 section_size_type length, 90 section_offset_type output_offset) 91 { 92 Input_merge_map* map = this->get_or_make_input_merge_map(output_data, shndx); 93 map->add_mapping(input_offset, length, output_offset); 94 } 95 96 void 97 Object_merge_map::Input_merge_map::add_mapping( 98 section_offset_type input_offset, section_size_type length, 99 section_offset_type output_offset) { 100 // Try to merge the new entry in the last one we saw. 101 if (!this->entries.empty()) 102 { 103 Input_merge_entry& entry(this->entries.back()); 104 105 // Use section_size_type to avoid signed/unsigned warnings. 106 section_size_type input_offset_u = input_offset; 107 section_size_type output_offset_u = output_offset; 108 109 // If this entry is not in order, we need to sort the vector 110 // before looking anything up. 111 if (input_offset_u < entry.input_offset + entry.length) 112 { 113 gold_assert(input_offset < entry.input_offset); 114 gold_assert(input_offset_u + length 115 <= static_cast<section_size_type>(entry.input_offset)); 116 this->sorted = false; 117 } 118 else if (entry.input_offset + entry.length == input_offset_u 119 && (output_offset == -1 120 ? entry.output_offset == -1 121 : entry.output_offset + entry.length == output_offset_u)) 122 { 123 entry.length += length; 124 return; 125 } 126 } 127 128 Input_merge_entry entry; 129 entry.input_offset = input_offset; 130 entry.length = length; 131 entry.output_offset = output_offset; 132 this->entries.push_back(entry); 133 } 134 135 // Get the output offset for an input address. 136 137 bool 138 Object_merge_map::get_output_offset(unsigned int shndx, 139 section_offset_type input_offset, 140 section_offset_type* output_offset) 141 { 142 Input_merge_map* map = this->get_input_merge_map(shndx); 143 if (map == NULL) 144 return false; 145 146 if (!map->sorted) 147 { 148 std::sort(map->entries.begin(), map->entries.end(), 149 Input_merge_compare()); 150 map->sorted = true; 151 } 152 153 Input_merge_entry entry; 154 entry.input_offset = input_offset; 155 std::vector<Input_merge_entry>::const_iterator p = 156 std::upper_bound(map->entries.begin(), map->entries.end(), 157 entry, Input_merge_compare()); 158 if (p == map->entries.begin()) 159 return false; 160 --p; 161 gold_assert(p->input_offset <= input_offset); 162 163 if (input_offset - p->input_offset 164 >= static_cast<section_offset_type>(p->length)) 165 return false; 166 167 *output_offset = p->output_offset; 168 if (*output_offset != -1) 169 *output_offset += (input_offset - p->input_offset); 170 return true; 171 } 172 173 // Return whether this is the merge map for section SHNDX. 174 175 const Output_section_data* 176 Object_merge_map::find_merge_section(unsigned int shndx) const { 177 const Object_merge_map::Input_merge_map* map = 178 this->get_input_merge_map(shndx); 179 if (map == NULL) 180 return NULL; 181 return map->output_data; 182 } 183 184 // Initialize a mapping from input offsets to output addresses. 185 186 template<int size> 187 void 188 Object_merge_map::initialize_input_to_output_map( 189 unsigned int shndx, 190 typename elfcpp::Elf_types<size>::Elf_Addr starting_address, 191 Unordered_map<section_offset_type, 192 typename elfcpp::Elf_types<size>::Elf_Addr>* initialize_map) 193 { 194 Input_merge_map* map = this->get_input_merge_map(shndx); 195 gold_assert(map != NULL); 196 197 gold_assert(initialize_map->empty()); 198 // We know how many entries we are going to add. 199 // reserve_unordered_map takes an expected count of buckets, not a 200 // count of elements, so double it to try to reduce collisions. 201 reserve_unordered_map(initialize_map, map->entries.size() * 2); 202 203 for (Input_merge_map::Entries::const_iterator p = map->entries.begin(); 204 p != map->entries.end(); 205 ++p) 206 { 207 section_offset_type output_offset = p->output_offset; 208 if (output_offset != -1) 209 output_offset += starting_address; 210 else 211 { 212 // If we see a relocation against an address we have chosen 213 // to discard, we relocate to zero. FIXME: We could also 214 // issue a warning in this case; that would require 215 // reporting this somehow and checking it in the routines in 216 // reloc.h. 217 output_offset = 0; 218 } 219 initialize_map->insert(std::make_pair(p->input_offset, output_offset)); 220 } 221 } 222 223 // Class Output_merge_base. 224 225 // Return the output offset for an input offset. The input address is 226 // at offset OFFSET in section SHNDX in OBJECT. If we know the 227 // offset, set *POUTPUT and return true. Otherwise return false. 228 229 bool 230 Output_merge_base::do_output_offset(const Relobj* object, 231 unsigned int shndx, 232 section_offset_type offset, 233 section_offset_type* poutput) const 234 { 235 return object->merge_output_offset(shndx, offset, poutput); 236 } 237 238 // Record a merged input section for script processing. 239 240 void 241 Output_merge_base::record_input_section(Relobj* relobj, unsigned int shndx) 242 { 243 gold_assert(this->keeps_input_sections_ && relobj != NULL); 244 // If this is the first input section, record it. We need do this because 245 // this->input_sections_ is unordered. 246 if (this->first_relobj_ == NULL) 247 { 248 this->first_relobj_ = relobj; 249 this->first_shndx_ = shndx; 250 } 251 252 std::pair<Input_sections::iterator, bool> result = 253 this->input_sections_.insert(Section_id(relobj, shndx)); 254 // We should insert a merge section once only. 255 gold_assert(result.second); 256 } 257 258 // Class Output_merge_data. 259 260 // Compute the hash code for a fixed-size constant. 261 262 size_t 263 Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const 264 { 265 const unsigned char* p = this->pomd_->constant(k); 266 section_size_type entsize = 267 convert_to_section_size_type(this->pomd_->entsize()); 268 269 // Fowler/Noll/Vo (FNV) hash (type FNV-1a). 270 if (sizeof(size_t) == 8) 271 { 272 size_t result = static_cast<size_t>(14695981039346656037ULL); 273 for (section_size_type i = 0; i < entsize; ++i) 274 { 275 result &= (size_t) *p++; 276 result *= 1099511628211ULL; 277 } 278 return result; 279 } 280 else 281 { 282 size_t result = 2166136261UL; 283 for (section_size_type i = 0; i < entsize; ++i) 284 { 285 result ^= (size_t) *p++; 286 result *= 16777619UL; 287 } 288 return result; 289 } 290 } 291 292 // Return whether one hash table key equals another. 293 294 bool 295 Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1, 296 Merge_data_key k2) const 297 { 298 const unsigned char* p1 = this->pomd_->constant(k1); 299 const unsigned char* p2 = this->pomd_->constant(k2); 300 return memcmp(p1, p2, this->pomd_->entsize()) == 0; 301 } 302 303 // Add a constant to the end of the section contents. 304 305 void 306 Output_merge_data::add_constant(const unsigned char* p) 307 { 308 section_size_type entsize = convert_to_section_size_type(this->entsize()); 309 section_size_type addralign = 310 convert_to_section_size_type(this->addralign()); 311 section_size_type addsize = std::max(entsize, addralign); 312 if (this->len_ + addsize > this->alc_) 313 { 314 if (this->alc_ == 0) 315 this->alc_ = 128 * addsize; 316 else 317 this->alc_ *= 2; 318 this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_)); 319 if (this->p_ == NULL) 320 gold_nomem(); 321 } 322 323 memcpy(this->p_ + this->len_, p, entsize); 324 if (addsize > entsize) 325 memset(this->p_ + this->len_ + entsize, 0, addsize - entsize); 326 this->len_ += addsize; 327 } 328 329 // Add the input section SHNDX in OBJECT to a merged output section 330 // which holds fixed length constants. Return whether we were able to 331 // handle the section; if not, it will be linked as usual without 332 // constant merging. 333 334 bool 335 Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx) 336 { 337 section_size_type len; 338 bool is_new; 339 const unsigned char* p = object->decompressed_section_contents(shndx, &len, 340 &is_new); 341 342 section_size_type entsize = convert_to_section_size_type(this->entsize()); 343 344 if (len % entsize != 0) 345 { 346 if (is_new) 347 delete[] p; 348 return false; 349 } 350 351 this->input_count_ += len / entsize; 352 353 Object_merge_map* merge_map = object->get_or_create_merge_map(); 354 Object_merge_map::Input_merge_map* input_merge_map = 355 merge_map->get_or_make_input_merge_map(this, shndx); 356 357 for (section_size_type i = 0; i < len; i += entsize, p += entsize) 358 { 359 // Add the constant to the section contents. If we find that it 360 // is already in the hash table, we will remove it again. 361 Merge_data_key k = this->len_; 362 this->add_constant(p); 363 364 std::pair<Merge_data_hashtable::iterator, bool> ins = 365 this->hashtable_.insert(k); 366 367 if (!ins.second) 368 { 369 // Key was already present. Remove the copy we just added. 370 this->len_ -= entsize; 371 k = *ins.first; 372 } 373 374 // Record the offset of this constant in the output section. 375 input_merge_map->add_mapping(i, entsize, k); 376 } 377 378 // For script processing, we keep the input sections. 379 if (this->keeps_input_sections()) 380 record_input_section(object, shndx); 381 382 if (is_new) 383 delete[] p; 384 385 return true; 386 } 387 388 // Set the final data size in a merged output section with fixed size 389 // constants. 390 391 void 392 Output_merge_data::set_final_data_size() 393 { 394 // Release the memory we don't need. 395 this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_)); 396 // An Output_merge_data object may be empty and realloc is allowed 397 // to return a NULL pointer in this case. An Output_merge_data is empty 398 // if all its input sections have sizes that are not multiples of entsize. 399 gold_assert(this->p_ != NULL || this->len_ == 0); 400 this->set_data_size(this->len_); 401 } 402 403 // Write the data of a merged output section with fixed size constants 404 // to the file. 405 406 void 407 Output_merge_data::do_write(Output_file* of) 408 { 409 of->write(this->offset(), this->p_, this->len_); 410 } 411 412 // Write the data to a buffer. 413 414 void 415 Output_merge_data::do_write_to_buffer(unsigned char* buffer) 416 { 417 memcpy(buffer, this->p_, this->len_); 418 } 419 420 // Print merge stats to stderr. 421 422 void 423 Output_merge_data::do_print_merge_stats(const char* section_name) 424 { 425 fprintf(stderr, 426 _("%s: %s merged constants size: %lu; input: %zu; output: %zu\n"), 427 program_name, section_name, 428 static_cast<unsigned long>(this->entsize()), 429 this->input_count_, this->hashtable_.size()); 430 } 431 432 // Class Output_merge_string. 433 434 // Add an input section to a merged string section. 435 436 template<typename Char_type> 437 bool 438 Output_merge_string<Char_type>::do_add_input_section(Relobj* object, 439 unsigned int shndx) 440 { 441 section_size_type sec_len; 442 bool is_new; 443 uint64_t addralign = this->addralign(); 444 const unsigned char* pdata = object->decompressed_section_contents(shndx, 445 &sec_len, 446 &is_new, 447 &addralign); 448 449 const Char_type* p = reinterpret_cast<const Char_type*>(pdata); 450 const Char_type* pend = p + sec_len / sizeof(Char_type); 451 const Char_type* pend0 = pend; 452 453 if (sec_len % sizeof(Char_type) != 0) 454 { 455 object->error(_("mergeable string section length not multiple of " 456 "character size")); 457 if (is_new) 458 delete[] pdata; 459 return false; 460 } 461 462 if (pend[-1] != 0) 463 { 464 gold_warning(_("%s: last entry in mergeable string section '%s' " 465 "not null terminated"), 466 object->name().c_str(), 467 object->section_name(shndx).c_str()); 468 // Find the end of the last NULL-terminated string in the buffer. 469 while (pend0 > p && pend0[-1] != 0) 470 --pend0; 471 } 472 473 Merged_strings_list* merged_strings_list = 474 new Merged_strings_list(object, shndx); 475 this->merged_strings_lists_.push_back(merged_strings_list); 476 Merged_strings& merged_strings = merged_strings_list->merged_strings; 477 478 // Count the number of non-null strings in the section and size the list. 479 size_t count = 0; 480 const Char_type* pt = p; 481 while (pt < pend0) 482 { 483 size_t len = string_length(pt); 484 if (len != 0) 485 ++count; 486 pt += len + 1; 487 } 488 if (pend0 < pend) 489 ++count; 490 merged_strings.reserve(count + 1); 491 492 // The index I is in bytes, not characters. 493 section_size_type i = 0; 494 495 // We assume here that the beginning of the section is correctly 496 // aligned, so each string within the section must retain the same 497 // modulo. 498 uintptr_t init_align_modulo = (reinterpret_cast<uintptr_t>(pdata) 499 & (addralign - 1)); 500 bool has_misaligned_strings = false; 501 502 while (p < pend) 503 { 504 size_t len = p < pend0 ? string_length(p) : pend - p; 505 506 // Within merge input section each string must be aligned. 507 if (len != 0 508 && ((reinterpret_cast<uintptr_t>(p) & (addralign - 1)) 509 != init_align_modulo)) 510 has_misaligned_strings = true; 511 512 Stringpool::Key key; 513 this->stringpool_.add_with_length(p, len, true, &key); 514 515 merged_strings.push_back(Merged_string(i, key)); 516 p += len + 1; 517 i += (len + 1) * sizeof(Char_type); 518 } 519 520 // Record the last offset in the input section so that we can 521 // compute the length of the last string. 522 merged_strings.push_back(Merged_string(i, 0)); 523 524 this->input_count_ += count; 525 this->input_size_ += i; 526 527 if (has_misaligned_strings) 528 gold_warning(_("%s: section %s contains incorrectly aligned strings;" 529 " the alignment of those strings won't be preserved"), 530 object->name().c_str(), 531 object->section_name(shndx).c_str()); 532 533 // For script processing, we keep the input sections. 534 if (this->keeps_input_sections()) 535 record_input_section(object, shndx); 536 537 if (is_new) 538 delete[] pdata; 539 540 return true; 541 } 542 543 // Finalize the mappings from the input sections to the output 544 // section, and return the final data size. 545 546 template<typename Char_type> 547 section_size_type 548 Output_merge_string<Char_type>::finalize_merged_data() 549 { 550 this->stringpool_.set_string_offsets(); 551 552 for (typename Merged_strings_lists::const_iterator l = 553 this->merged_strings_lists_.begin(); 554 l != this->merged_strings_lists_.end(); 555 ++l) 556 { 557 section_offset_type last_input_offset = 0; 558 section_offset_type last_output_offset = 0; 559 Relobj *object = (*l)->object; 560 Object_merge_map* merge_map = object->get_or_create_merge_map(); 561 Object_merge_map::Input_merge_map* input_merge_map = 562 merge_map->get_or_make_input_merge_map(this, (*l)->shndx); 563 564 for (typename Merged_strings::const_iterator p = 565 (*l)->merged_strings.begin(); 566 p != (*l)->merged_strings.end(); 567 ++p) 568 { 569 section_size_type length = p->offset - last_input_offset; 570 if (length > 0) 571 input_merge_map->add_mapping(last_input_offset, length, 572 last_output_offset); 573 last_input_offset = p->offset; 574 if (p->stringpool_key != 0) 575 last_output_offset = 576 this->stringpool_.get_offset_from_key(p->stringpool_key); 577 } 578 delete *l; 579 } 580 581 // Save some memory. This also ensures that this function will work 582 // if called twice, as may happen if Layout::set_segment_offsets 583 // finds a better alignment. 584 this->merged_strings_lists_.clear(); 585 586 return this->stringpool_.get_strtab_size(); 587 } 588 589 template<typename Char_type> 590 void 591 Output_merge_string<Char_type>::set_final_data_size() 592 { 593 const off_t final_data_size = this->finalize_merged_data(); 594 this->set_data_size(final_data_size); 595 } 596 597 // Write out a merged string section. 598 599 template<typename Char_type> 600 void 601 Output_merge_string<Char_type>::do_write(Output_file* of) 602 { 603 this->stringpool_.write(of, this->offset()); 604 } 605 606 // Write a merged string section to a buffer. 607 608 template<typename Char_type> 609 void 610 Output_merge_string<Char_type>::do_write_to_buffer(unsigned char* buffer) 611 { 612 this->stringpool_.write_to_buffer(buffer, this->data_size()); 613 } 614 615 // Return the name of the types of string to use with 616 // do_print_merge_stats. 617 618 template<typename Char_type> 619 const char* 620 Output_merge_string<Char_type>::string_name() 621 { 622 gold_unreachable(); 623 return NULL; 624 } 625 626 template<> 627 const char* 628 Output_merge_string<char>::string_name() 629 { 630 return "strings"; 631 } 632 633 template<> 634 const char* 635 Output_merge_string<uint16_t>::string_name() 636 { 637 return "16-bit strings"; 638 } 639 640 template<> 641 const char* 642 Output_merge_string<uint32_t>::string_name() 643 { 644 return "32-bit strings"; 645 } 646 647 // Print merge stats to stderr. 648 649 template<typename Char_type> 650 void 651 Output_merge_string<Char_type>::do_print_merge_stats(const char* section_name) 652 { 653 char buf[200]; 654 snprintf(buf, sizeof buf, "%s merged %s", section_name, this->string_name()); 655 fprintf(stderr, _("%s: %s input bytes: %zu\n"), 656 program_name, buf, this->input_size_); 657 fprintf(stderr, _("%s: %s input strings: %zu\n"), 658 program_name, buf, this->input_count_); 659 this->stringpool_.print_stats(buf); 660 } 661 662 // Instantiate the templates we need. 663 664 template 665 class Output_merge_string<char>; 666 667 template 668 class Output_merge_string<uint16_t>; 669 670 template 671 class Output_merge_string<uint32_t>; 672 673 #if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_32_BIG) 674 template 675 void 676 Object_merge_map::initialize_input_to_output_map<32>( 677 unsigned int shndx, 678 elfcpp::Elf_types<32>::Elf_Addr starting_address, 679 Unordered_map<section_offset_type, elfcpp::Elf_types<32>::Elf_Addr>*); 680 #endif 681 682 #if defined(HAVE_TARGET_64_LITTLE) || defined(HAVE_TARGET_64_BIG) 683 template 684 void 685 Object_merge_map::initialize_input_to_output_map<64>( 686 unsigned int shndx, 687 elfcpp::Elf_types<64>::Elf_Addr starting_address, 688 Unordered_map<section_offset_type, elfcpp::Elf_types<64>::Elf_Addr>*); 689 #endif 690 691 } // End namespace gold. 692