1 // merge.cc -- handle section merging for gold 2 3 // Copyright (C) 2006-2014 Free Software Foundation, Inc. 4 // Written by Ian Lance Taylor <iant (at) 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 Object_merge_map::Input_merge_map* 49 Object_merge_map::get_input_merge_map(unsigned int shndx) 50 { 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()) 58 return p->second; 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(const Merge_map* merge_map, 66 unsigned int shndx) 67 { 68 Input_merge_map* map = this->get_input_merge_map(shndx); 69 if (map != NULL) 70 { 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); 74 return map; 75 } 76 77 // We need to create a new entry. 78 if (this->first_shnum_ == -1U) 79 { 80 this->first_shnum_ = shndx; 81 this->first_map_.merge_map = merge_map; 82 return &this->first_map_; 83 } 84 if (this->second_shnum_ == -1U) 85 { 86 this->second_shnum_ = shndx; 87 this->second_map_.merge_map = merge_map; 88 return &this->second_map_; 89 } 90 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; 94 return new_map; 95 } 96 97 // Add a mapping. 98 99 void 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) 104 { 105 Input_merge_map* map = this->get_or_make_input_merge_map(merge_map, shndx); 106 107 // Try to merge the new entry in the last one we saw. 108 if (!map->entries.empty()) 109 { 110 Input_merge_entry& entry(map->entries.back()); 111 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; 115 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) 119 { 120 gold_assert(input_offset < entry.input_offset); 121 gold_assert(input_offset_u + length 122 <= static_cast<section_size_type>(entry.input_offset)); 123 map->sorted = false; 124 } 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)) 129 { 130 entry.length += length; 131 return; 132 } 133 } 134 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); 140 } 141 142 // Get the output offset for an input address. 143 144 bool 145 Object_merge_map::get_output_offset(const Merge_map* merge_map, 146 unsigned int shndx, 147 section_offset_type input_offset, 148 section_offset_type* output_offset) 149 { 150 Input_merge_map* map = this->get_input_merge_map(shndx); 151 if (map == NULL 152 || (merge_map != NULL && map->merge_map != merge_map)) 153 return false; 154 155 if (!map->sorted) 156 { 157 std::sort(map->entries.begin(), map->entries.end(), 158 Input_merge_compare()); 159 map->sorted = true; 160 } 161 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()) 168 return false; 169 --p; 170 gold_assert(p->input_offset <= input_offset); 171 172 if (input_offset - p->input_offset 173 >= static_cast<section_offset_type>(p->length)) 174 return false; 175 176 *output_offset = p->output_offset; 177 if (*output_offset != -1) 178 *output_offset += (input_offset - p->input_offset); 179 return true; 180 } 181 182 // Return whether this is the merge map for section SHNDX. 183 184 inline bool 185 Object_merge_map::is_merge_section_for(const Merge_map* merge_map, 186 unsigned int shndx) 187 { 188 Input_merge_map* map = this->get_input_merge_map(shndx); 189 return map != NULL && map->merge_map == merge_map; 190 } 191 192 // Initialize a mapping from input offsets to output addresses. 193 194 template<int size> 195 void 196 Object_merge_map::initialize_input_to_output_map( 197 unsigned int shndx, 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) 201 { 202 Input_merge_map* map = this->get_input_merge_map(shndx); 203 gold_assert(map != NULL); 204 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); 210 211 for (Input_merge_map::Entries::const_iterator p = map->entries.begin(); 212 p != map->entries.end(); 213 ++p) 214 { 215 section_offset_type output_offset = p->output_offset; 216 if (output_offset != -1) 217 output_offset += starting_address; 218 else 219 { 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 224 // reloc.h. 225 output_offset = 0; 226 } 227 initialize_map->insert(std::make_pair(p->input_offset, output_offset)); 228 } 229 } 230 231 // Class Merge_map. 232 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. 236 237 void 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) 241 { 242 gold_assert(object != NULL); 243 Object_merge_map* object_merge_map = object->merge_map(); 244 if (object_merge_map == NULL) 245 { 246 object_merge_map = new Object_merge_map(); 247 object->set_merge_map(object_merge_map); 248 } 249 250 object_merge_map->add_mapping(this, shndx, offset, length, output_offset); 251 } 252 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 257 // otherwise. 258 259 bool 260 Merge_map::get_output_offset(const Relobj* object, unsigned int shndx, 261 section_offset_type offset, 262 section_offset_type* output_offset) const 263 { 264 Object_merge_map* object_merge_map = object->merge_map(); 265 if (object_merge_map == NULL) 266 return false; 267 return object_merge_map->get_output_offset(this, shndx, offset, 268 output_offset); 269 } 270 271 // Return whether this is the merge section for SHNDX in OBJECT. 272 273 bool 274 Merge_map::is_merge_section_for(const Relobj* object, unsigned int shndx) const 275 { 276 Object_merge_map* object_merge_map = object->merge_map(); 277 if (object_merge_map == NULL) 278 return false; 279 return object_merge_map->is_merge_section_for(this, shndx); 280 } 281 282 // Class Output_merge_base. 283 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. 287 288 bool 289 Output_merge_base::do_output_offset(const Relobj* object, 290 unsigned int shndx, 291 section_offset_type offset, 292 section_offset_type* poutput) const 293 { 294 return this->merge_map_.get_output_offset(object, shndx, offset, poutput); 295 } 296 297 // Return whether this is the merge section for SHNDX in OBJECT. 298 299 bool 300 Output_merge_base::do_is_merge_section_for(const Relobj* object, 301 unsigned int shndx) const 302 { 303 return this->merge_map_.is_merge_section_for(object, shndx); 304 } 305 306 // Record a merged input section for script processing. 307 308 void 309 Output_merge_base::record_input_section(Relobj* relobj, unsigned int shndx) 310 { 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) 315 { 316 this->first_relobj_ = relobj; 317 this->first_shndx_ = shndx; 318 } 319 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); 324 } 325 326 // Class Output_merge_data. 327 328 // Compute the hash code for a fixed-size constant. 329 330 size_t 331 Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const 332 { 333 const unsigned char* p = this->pomd_->constant(k); 334 section_size_type entsize = 335 convert_to_section_size_type(this->pomd_->entsize()); 336 337 // Fowler/Noll/Vo (FNV) hash (type FNV-1a). 338 if (sizeof(size_t) == 8) 339 { 340 size_t result = static_cast<size_t>(14695981039346656037ULL); 341 for (section_size_type i = 0; i < entsize; ++i) 342 { 343 result &= (size_t) *p++; 344 result *= 1099511628211ULL; 345 } 346 return result; 347 } 348 else 349 { 350 size_t result = 2166136261UL; 351 for (section_size_type i = 0; i < entsize; ++i) 352 { 353 result ^= (size_t) *p++; 354 result *= 16777619UL; 355 } 356 return result; 357 } 358 } 359 360 // Return whether one hash table key equals another. 361 362 bool 363 Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1, 364 Merge_data_key k2) const 365 { 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; 369 } 370 371 // Add a constant to the end of the section contents. 372 373 void 374 Output_merge_data::add_constant(const unsigned char* p) 375 { 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_) 381 { 382 if (this->alc_ == 0) 383 this->alc_ = 128 * addsize; 384 else 385 this->alc_ *= 2; 386 this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_)); 387 if (this->p_ == NULL) 388 gold_nomem(); 389 } 390 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; 395 } 396 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 400 // constant merging. 401 402 bool 403 Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx) 404 { 405 section_size_type len; 406 bool is_new; 407 const unsigned char* p = object->decompressed_section_contents(shndx, &len, 408 &is_new); 409 410 section_size_type entsize = convert_to_section_size_type(this->entsize()); 411 412 if (len % entsize != 0) 413 { 414 if (is_new) 415 delete[] p; 416 return false; 417 } 418 419 this->input_count_ += len / entsize; 420 421 for (section_size_type i = 0; i < len; i += entsize, p += entsize) 422 { 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); 427 428 std::pair<Merge_data_hashtable::iterator, bool> ins = 429 this->hashtable_.insert(k); 430 431 if (!ins.second) 432 { 433 // Key was already present. Remove the copy we just added. 434 this->len_ -= entsize; 435 k = *ins.first; 436 } 437 438 // Record the offset of this constant in the output section. 439 this->add_mapping(object, shndx, i, entsize, k); 440 } 441 442 // For script processing, we keep the input sections. 443 if (this->keeps_input_sections()) 444 record_input_section(object, shndx); 445 446 if (is_new) 447 delete[] p; 448 449 return true; 450 } 451 452 // Set the final data size in a merged output section with fixed size 453 // constants. 454 455 void 456 Output_merge_data::set_final_data_size() 457 { 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_); 465 } 466 467 // Write the data of a merged output section with fixed size constants 468 // to the file. 469 470 void 471 Output_merge_data::do_write(Output_file* of) 472 { 473 of->write(this->offset(), this->p_, this->len_); 474 } 475 476 // Write the data to a buffer. 477 478 void 479 Output_merge_data::do_write_to_buffer(unsigned char* buffer) 480 { 481 memcpy(buffer, this->p_, this->len_); 482 } 483 484 // Print merge stats to stderr. 485 486 void 487 Output_merge_data::do_print_merge_stats(const char* section_name) 488 { 489 fprintf(stderr, 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()); 494 } 495 496 // Class Output_merge_string. 497 498 // Add an input section to a merged string section. 499 500 template<typename Char_type> 501 bool 502 Output_merge_string<Char_type>::do_add_input_section(Relobj* object, 503 unsigned int shndx) 504 { 505 section_size_type sec_len; 506 bool is_new; 507 const unsigned char* pdata = object->decompressed_section_contents(shndx, 508 &sec_len, 509 &is_new); 510 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; 514 515 if (sec_len % sizeof(Char_type) != 0) 516 { 517 object->error(_("mergeable string section length not multiple of " 518 "character size")); 519 if (is_new) 520 delete[] pdata; 521 return false; 522 } 523 524 if (pend[-1] != 0) 525 { 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) 532 --pend0; 533 } 534 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; 539 540 // Count the number of non-null strings in the section and size the list. 541 size_t count = 0; 542 const Char_type* pt = p; 543 while (pt < pend0) 544 { 545 size_t len = string_length(pt); 546 if (len != 0) 547 ++count; 548 pt += len + 1; 549 } 550 if (pend0 < pend) 551 ++count; 552 merged_strings.reserve(count + 1); 553 554 // The index I is in bytes, not characters. 555 section_size_type i = 0; 556 557 // We assume here that the beginning of the section is correctly 558 // aligned, so each string within the section must retain the same 559 // modulo. 560 uintptr_t init_align_modulo = (reinterpret_cast<uintptr_t>(pdata) 561 & (this->addralign() - 1)); 562 bool has_misaligned_strings = false; 563 564 while (p < pend) 565 { 566 size_t len = p < pend0 ? string_length(p) : pend - p; 567 568 // Within merge input section each string must be aligned. 569 if (len != 0 570 && ((reinterpret_cast<uintptr_t>(p) & (this->addralign() - 1)) 571 != init_align_modulo)) 572 has_misaligned_strings = true; 573 574 Stringpool::Key key; 575 this->stringpool_.add_with_length(p, len, true, &key); 576 577 merged_strings.push_back(Merged_string(i, key)); 578 p += len + 1; 579 i += (len + 1) * sizeof(Char_type); 580 } 581 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)); 585 586 this->input_count_ += count; 587 this->input_size_ += i; 588 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()); 594 595 // For script processing, we keep the input sections. 596 if (this->keeps_input_sections()) 597 record_input_section(object, shndx); 598 599 if (is_new) 600 delete[] pdata; 601 602 return true; 603 } 604 605 // Finalize the mappings from the input sections to the output 606 // section, and return the final data size. 607 608 template<typename Char_type> 609 section_size_type 610 Output_merge_string<Char_type>::finalize_merged_data() 611 { 612 this->stringpool_.set_string_offsets(); 613 614 for (typename Merged_strings_lists::const_iterator l = 615 this->merged_strings_lists_.begin(); 616 l != this->merged_strings_lists_.end(); 617 ++l) 618 { 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(); 624 ++p) 625 { 626 section_size_type length = p->offset - last_input_offset; 627 if (length > 0) 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) 632 last_output_offset = 633 this->stringpool_.get_offset_from_key(p->stringpool_key); 634 } 635 delete *l; 636 } 637 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(); 642 643 return this->stringpool_.get_strtab_size(); 644 } 645 646 template<typename Char_type> 647 void 648 Output_merge_string<Char_type>::set_final_data_size() 649 { 650 const off_t final_data_size = this->finalize_merged_data(); 651 this->set_data_size(final_data_size); 652 } 653 654 // Write out a merged string section. 655 656 template<typename Char_type> 657 void 658 Output_merge_string<Char_type>::do_write(Output_file* of) 659 { 660 this->stringpool_.write(of, this->offset()); 661 } 662 663 // Write a merged string section to a buffer. 664 665 template<typename Char_type> 666 void 667 Output_merge_string<Char_type>::do_write_to_buffer(unsigned char* buffer) 668 { 669 this->stringpool_.write_to_buffer(buffer, this->data_size()); 670 } 671 672 // Return the name of the types of string to use with 673 // do_print_merge_stats. 674 675 template<typename Char_type> 676 const char* 677 Output_merge_string<Char_type>::string_name() 678 { 679 gold_unreachable(); 680 return NULL; 681 } 682 683 template<> 684 const char* 685 Output_merge_string<char>::string_name() 686 { 687 return "strings"; 688 } 689 690 template<> 691 const char* 692 Output_merge_string<uint16_t>::string_name() 693 { 694 return "16-bit strings"; 695 } 696 697 template<> 698 const char* 699 Output_merge_string<uint32_t>::string_name() 700 { 701 return "32-bit strings"; 702 } 703 704 // Print merge stats to stderr. 705 706 template<typename Char_type> 707 void 708 Output_merge_string<Char_type>::do_print_merge_stats(const char* section_name) 709 { 710 char buf[200]; 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); 717 } 718 719 // Instantiate the templates we need. 720 721 template 722 class Output_merge_string<char>; 723 724 template 725 class Output_merge_string<uint16_t>; 726 727 template 728 class Output_merge_string<uint32_t>; 729 730 #if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_32_BIG) 731 template 732 void 733 Object_merge_map::initialize_input_to_output_map<32>( 734 unsigned int shndx, 735 elfcpp::Elf_types<32>::Elf_Addr starting_address, 736 Unordered_map<section_offset_type, elfcpp::Elf_types<32>::Elf_Addr>*); 737 #endif 738 739 #if defined(HAVE_TARGET_64_LITTLE) || defined(HAVE_TARGET_64_BIG) 740 template 741 void 742 Object_merge_map::initialize_input_to_output_map<64>( 743 unsigned int shndx, 744 elfcpp::Elf_types<64>::Elf_Addr starting_address, 745 Unordered_map<section_offset_type, elfcpp::Elf_types<64>::Elf_Addr>*); 746 #endif 747 748 } // End namespace gold. 749
