1// merge.cc -- handle section merging for gold 2 3// Copyright 2006, 2007, 2008, 2010 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 31namespace gold 32{ 33 34// Class Object_merge_map. 35 36// Destructor. 37 38Object_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 48Object_merge_map::Input_merge_map* 49Object_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 64Object_merge_map::Input_merge_map* 65Object_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 99void 100Object_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 144bool 145Object_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::lower_bound(map->entries.begin(), map->entries.end(), 166 entry, Input_merge_compare()); 167 if (p == map->entries.end() || p->input_offset > input_offset) 168 { 169 if (p == map->entries.begin()) 170 return false; 171 --p; 172 gold_assert(p->input_offset <= input_offset); 173 } 174 175 if (input_offset - p->input_offset 176 >= static_cast<section_offset_type>(p->length)) 177 return false; 178 179 *output_offset = p->output_offset; 180 if (*output_offset != -1) 181 *output_offset += (input_offset - p->input_offset); 182 return true; 183} 184 185// Return whether this is the merge map for section SHNDX. 186 187inline bool 188Object_merge_map::is_merge_section_for(const Merge_map* merge_map, 189 unsigned int shndx) 190{ 191 Input_merge_map* map = this->get_input_merge_map(shndx); 192 return map != NULL && map->merge_map == merge_map; 193} 194 195// Initialize a mapping from input offsets to output addresses. 196 197template<int size> 198void 199Object_merge_map::initialize_input_to_output_map( 200 unsigned int shndx, 201 typename elfcpp::Elf_types<size>::Elf_Addr starting_address, 202 Unordered_map<section_offset_type, 203 typename elfcpp::Elf_types<size>::Elf_Addr>* initialize_map) 204{ 205 Input_merge_map* map = this->get_input_merge_map(shndx); 206 gold_assert(map != NULL); 207 208 gold_assert(initialize_map->empty()); 209 // We know how many entries we are going to add. 210 // reserve_unordered_map takes an expected count of buckets, not a 211 // count of elements, so double it to try to reduce collisions. 212 reserve_unordered_map(initialize_map, map->entries.size() * 2); 213 214 for (Input_merge_map::Entries::const_iterator p = map->entries.begin(); 215 p != map->entries.end(); 216 ++p) 217 { 218 section_offset_type output_offset = p->output_offset; 219 if (output_offset != -1) 220 output_offset += starting_address; 221 else 222 { 223 // If we see a relocation against an address we have chosen 224 // to discard, we relocate to zero. FIXME: We could also 225 // issue a warning in this case; that would require 226 // reporting this somehow and checking it in the routines in 227 // reloc.h. 228 output_offset = 0; 229 } 230 initialize_map->insert(std::make_pair(p->input_offset, output_offset)); 231 } 232} 233 234// Class Merge_map. 235 236// Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in input 237// section SHNDX in object OBJECT to an OUTPUT_OFFSET in merged data 238// in an output section. 239 240void 241Merge_map::add_mapping(Relobj* object, unsigned int shndx, 242 section_offset_type offset, section_size_type length, 243 section_offset_type output_offset) 244{ 245 Object_merge_map* object_merge_map = object->merge_map(); 246 if (object_merge_map == NULL) 247 { 248 object_merge_map = new Object_merge_map(); 249 object->set_merge_map(object_merge_map); 250 } 251 252 object_merge_map->add_mapping(this, shndx, offset, length, output_offset); 253} 254 255// Return the output offset for an input address. The input address 256// is at offset OFFSET in section SHNDX in OBJECT. This sets 257// *OUTPUT_OFFSET to the offset in the merged data in the output 258// section. This returns true if the mapping is known, false 259// otherwise. 260 261bool 262Merge_map::get_output_offset(const Relobj* object, unsigned int shndx, 263 section_offset_type offset, 264 section_offset_type* output_offset) const 265{ 266 Object_merge_map* object_merge_map = object->merge_map(); 267 if (object_merge_map == NULL) 268 return false; 269 return object_merge_map->get_output_offset(this, shndx, offset, 270 output_offset); 271} 272 273// Return whether this is the merge section for SHNDX in OBJECT. 274 275bool 276Merge_map::is_merge_section_for(const Relobj* object, unsigned int shndx) const 277{ 278 Object_merge_map* object_merge_map = object->merge_map(); 279 if (object_merge_map == NULL) 280 return false; 281 return object_merge_map->is_merge_section_for(this, shndx); 282} 283 284// Class Output_merge_base. 285 286// Return the output offset for an input offset. The input address is 287// at offset OFFSET in section SHNDX in OBJECT. If we know the 288// offset, set *POUTPUT and return true. Otherwise return false. 289 290bool 291Output_merge_base::do_output_offset(const Relobj* object, 292 unsigned int shndx, 293 section_offset_type offset, 294 section_offset_type* poutput) const 295{ 296 return this->merge_map_.get_output_offset(object, shndx, offset, poutput); 297} 298 299// Return whether this is the merge section for SHNDX in OBJECT. 300 301bool 302Output_merge_base::do_is_merge_section_for(const Relobj* object, 303 unsigned int shndx) const 304{ 305 return this->merge_map_.is_merge_section_for(object, shndx); 306} 307 308// Record a merged input section for script processing. 309 310void 311Output_merge_base::record_input_section(Relobj* relobj, unsigned int shndx) 312{ 313 gold_assert(this->keeps_input_sections_ && relobj != NULL); 314 // If this is the first input section, record it. We need do this because 315 // this->input_sections_ is unordered. 316 if (this->first_relobj_ == NULL) 317 { 318 this->first_relobj_ = relobj; 319 this->first_shndx_ = shndx; 320 } 321 322 std::pair<Input_sections::iterator, bool> result = 323 this->input_sections_.insert(Section_id(relobj, shndx)); 324 // We should insert a merge section once only. 325 gold_assert(result.second); 326} 327 328// Class Output_merge_data. 329 330// Compute the hash code for a fixed-size constant. 331 332size_t 333Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const 334{ 335 const unsigned char* p = this->pomd_->constant(k); 336 section_size_type entsize = 337 convert_to_section_size_type(this->pomd_->entsize()); 338 339 // Fowler/Noll/Vo (FNV) hash (type FNV-1a). 340 if (sizeof(size_t) == 8) 341 { 342 size_t result = static_cast<size_t>(14695981039346656037ULL); 343 for (section_size_type i = 0; i < entsize; ++i) 344 { 345 result &= (size_t) *p++; 346 result *= 1099511628211ULL; 347 } 348 return result; 349 } 350 else 351 { 352 size_t result = 2166136261UL; 353 for (section_size_type i = 0; i < entsize; ++i) 354 { 355 result ^= (size_t) *p++; 356 result *= 16777619UL; 357 } 358 return result; 359 } 360} 361 362// Return whether one hash table key equals another. 363 364bool 365Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1, 366 Merge_data_key k2) const 367{ 368 const unsigned char* p1 = this->pomd_->constant(k1); 369 const unsigned char* p2 = this->pomd_->constant(k2); 370 return memcmp(p1, p2, this->pomd_->entsize()) == 0; 371} 372 373// Add a constant to the end of the section contents. 374 375void 376Output_merge_data::add_constant(const unsigned char* p) 377{ 378 section_size_type entsize = convert_to_section_size_type(this->entsize()); 379 section_size_type addralign = 380 convert_to_section_size_type(this->addralign()); 381 section_size_type addsize = std::max(entsize, addralign); 382 if (this->len_ + addsize > this->alc_) 383 { 384 if (this->alc_ == 0) 385 this->alc_ = 128 * addsize; 386 else 387 this->alc_ *= 2; 388 this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_)); 389 if (this->p_ == NULL) 390 gold_nomem(); 391 } 392 393 memcpy(this->p_ + this->len_, p, entsize); 394 if (addsize > entsize) 395 memset(this->p_ + this->len_ + entsize, 0, addsize - entsize); 396 this->len_ += addsize; 397} 398 399// Add the input section SHNDX in OBJECT to a merged output section 400// which holds fixed length constants. Return whether we were able to 401// handle the section; if not, it will be linked as usual without 402// constant merging. 403 404bool 405Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx) 406{ 407 section_size_type len; 408 section_size_type uncompressed_size = 0; 409 unsigned char* uncompressed_data = NULL; 410 const unsigned char* p = object->section_contents(shndx, &len, false); 411 412 if (object->section_is_compressed(shndx, &uncompressed_size)) 413 { 414 uncompressed_data = new unsigned char[uncompressed_size]; 415 if (!decompress_input_section(p, len, uncompressed_data, 416 uncompressed_size)) 417 object->error(_("could not decompress section %s"), 418 object->section_name(shndx).c_str()); 419 p = uncompressed_data; 420 len = uncompressed_size; 421 } 422 423 section_size_type entsize = convert_to_section_size_type(this->entsize()); 424 425 if (len % entsize != 0) 426 { 427 if (uncompressed_data != NULL) 428 delete[] uncompressed_data; 429 return false; 430 } 431 432 this->input_count_ += len / entsize; 433 434 for (section_size_type i = 0; i < len; i += entsize, p += entsize) 435 { 436 // Add the constant to the section contents. If we find that it 437 // is already in the hash table, we will remove it again. 438 Merge_data_key k = this->len_; 439 this->add_constant(p); 440 441 std::pair<Merge_data_hashtable::iterator, bool> ins = 442 this->hashtable_.insert(k); 443 444 if (!ins.second) 445 { 446 // Key was already present. Remove the copy we just added. 447 this->len_ -= entsize; 448 k = *ins.first; 449 } 450 451 // Record the offset of this constant in the output section. 452 this->add_mapping(object, shndx, i, entsize, k); 453 } 454 455 // For script processing, we keep the input sections. 456 if (this->keeps_input_sections()) 457 record_input_section(object, shndx); 458 459 if (uncompressed_data != NULL) 460 delete[] uncompressed_data; 461 462 return true; 463} 464 465// Set the final data size in a merged output section with fixed size 466// constants. 467 468void 469Output_merge_data::set_final_data_size() 470{ 471 // Release the memory we don't need. 472 this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_)); 473 // An Output_merge_data object may be empty and realloc is allowed 474 // to return a NULL pointer in this case. An Output_merge_data is empty 475 // if all its input sections have sizes that are not multiples of entsize. 476 gold_assert(this->p_ != NULL || this->len_ == 0); 477 this->set_data_size(this->len_); 478} 479 480// Write the data of a merged output section with fixed size constants 481// to the file. 482 483void 484Output_merge_data::do_write(Output_file* of) 485{ 486 of->write(this->offset(), this->p_, this->len_); 487} 488 489// Write the data to a buffer. 490 491void 492Output_merge_data::do_write_to_buffer(unsigned char* buffer) 493{ 494 memcpy(buffer, this->p_, this->len_); 495} 496 497// Print merge stats to stderr. 498 499void 500Output_merge_data::do_print_merge_stats(const char* section_name) 501{ 502 fprintf(stderr, 503 _("%s: %s merged constants size: %lu; input: %zu; output: %zu\n"), 504 program_name, section_name, 505 static_cast<unsigned long>(this->entsize()), 506 this->input_count_, this->hashtable_.size()); 507} 508 509// Class Output_merge_string. 510 511// Add an input section to a merged string section. 512 513template<typename Char_type> 514bool 515Output_merge_string<Char_type>::do_add_input_section(Relobj* object, 516 unsigned int shndx) 517{ 518 section_size_type len; 519 section_size_type uncompressed_size = 0; 520 unsigned char* uncompressed_data = NULL; 521 const unsigned char* pdata = object->section_contents(shndx, &len, false); 522 523 if (object->section_is_compressed(shndx, &uncompressed_size)) 524 { 525 uncompressed_data = new unsigned char[uncompressed_size]; 526 if (!decompress_input_section(pdata, len, uncompressed_data, 527 uncompressed_size)) 528 object->error(_("could not decompress section %s"), 529 object->section_name(shndx).c_str()); 530 pdata = uncompressed_data; 531 len = uncompressed_size; 532 } 533 534 const Char_type* p = reinterpret_cast<const Char_type*>(pdata); 535 const Char_type* pend = p + len / sizeof(Char_type); 536 const Char_type* pend0 = pend; 537 538 if (len % sizeof(Char_type) != 0) 539 { 540 object->error(_("mergeable string section length not multiple of " 541 "character size")); 542 if (uncompressed_data != NULL) 543 delete[] uncompressed_data; 544 return false; 545 } 546 547 if (pend[-1] != 0) 548 { 549 gold_warning(_("%s: last entry in mergeable string section '%s' " 550 "not null terminated"), 551 object->name().c_str(), 552 object->section_name(shndx).c_str()); 553 // Find the end of the last NULL-terminated string in the buffer. 554 while (pend0 > p && pend0[-1] != 0) 555 --pend0; 556 } 557 558 Merged_strings_list* merged_strings_list = 559 new Merged_strings_list(object, shndx); 560 this->merged_strings_lists_.push_back(merged_strings_list); 561 Merged_strings& merged_strings = merged_strings_list->merged_strings; 562 563 // Count the number of strings in the section and size the list. 564 size_t count = 0; 565 for (const Char_type* pt = p; pt < pend0; pt += string_length(pt) + 1) 566 ++count; 567 if (pend0 < pend) 568 ++count; 569 merged_strings.reserve(count + 1); 570 571 // The index I is in bytes, not characters. 572 section_size_type i = 0; 573 while (p < pend0) 574 { 575 size_t len = string_length(p); 576 577 Stringpool::Key key; 578 this->stringpool_.add_with_length(p, len, true, &key); 579 580 merged_strings.push_back(Merged_string(i, key)); 581 582 p += len + 1; 583 i += (len + 1) * sizeof(Char_type); 584 } 585 if (p < pend) 586 { 587 size_t len = pend - p; 588 589 Stringpool::Key key; 590 this->stringpool_.add_with_length(p, len, true, &key); 591 592 merged_strings.push_back(Merged_string(i, key)); 593 594 i += (len + 1) * sizeof(Char_type); 595 } 596 597 // Record the last offset in the input section so that we can 598 // compute the length of the last string. 599 merged_strings.push_back(Merged_string(i, 0)); 600 601 this->input_count_ += count; 602 this->input_size_ += len; 603 604 // For script processing, we keep the input sections. 605 if (this->keeps_input_sections()) 606 record_input_section(object, shndx); 607 608 if (uncompressed_data != NULL) 609 delete[] uncompressed_data; 610 611 return true; 612} 613 614// Finalize the mappings from the input sections to the output 615// section, and return the final data size. 616 617template<typename Char_type> 618section_size_type 619Output_merge_string<Char_type>::finalize_merged_data() 620{ 621 this->stringpool_.set_string_offsets(); 622 623 for (typename Merged_strings_lists::const_iterator l = 624 this->merged_strings_lists_.begin(); 625 l != this->merged_strings_lists_.end(); 626 ++l) 627 { 628 section_offset_type last_input_offset = 0; 629 section_offset_type last_output_offset = 0; 630 for (typename Merged_strings::const_iterator p = 631 (*l)->merged_strings.begin(); 632 p != (*l)->merged_strings.end(); 633 ++p) 634 { 635 section_size_type length = p->offset - last_input_offset; 636 if (length > 0) 637 this->add_mapping((*l)->object, (*l)->shndx, last_input_offset, 638 length, last_output_offset); 639 last_input_offset = p->offset; 640 if (p->stringpool_key != 0) 641 last_output_offset = 642 this->stringpool_.get_offset_from_key(p->stringpool_key); 643 } 644 delete *l; 645 } 646 647 // Save some memory. This also ensures that this function will work 648 // if called twice, as may happen if Layout::set_segment_offsets 649 // finds a better alignment. 650 this->merged_strings_lists_.clear(); 651 652 return this->stringpool_.get_strtab_size(); 653} 654 655template<typename Char_type> 656void 657Output_merge_string<Char_type>::set_final_data_size() 658{ 659 const off_t final_data_size = this->finalize_merged_data(); 660 this->set_data_size(final_data_size); 661} 662 663// Write out a merged string section. 664 665template<typename Char_type> 666void 667Output_merge_string<Char_type>::do_write(Output_file* of) 668{ 669 this->stringpool_.write(of, this->offset()); 670} 671 672// Write a merged string section to a buffer. 673 674template<typename Char_type> 675void 676Output_merge_string<Char_type>::do_write_to_buffer(unsigned char* buffer) 677{ 678 this->stringpool_.write_to_buffer(buffer, this->data_size()); 679} 680 681// Return the name of the types of string to use with 682// do_print_merge_stats. 683 684template<typename Char_type> 685const char* 686Output_merge_string<Char_type>::string_name() 687{ 688 gold_unreachable(); 689 return NULL; 690} 691 692template<> 693const char* 694Output_merge_string<char>::string_name() 695{ 696 return "strings"; 697} 698 699template<> 700const char* 701Output_merge_string<uint16_t>::string_name() 702{ 703 return "16-bit strings"; 704} 705 706template<> 707const char* 708Output_merge_string<uint32_t>::string_name() 709{ 710 return "32-bit strings"; 711} 712 713// Print merge stats to stderr. 714 715template<typename Char_type> 716void 717Output_merge_string<Char_type>::do_print_merge_stats(const char* section_name) 718{ 719 char buf[200]; 720 snprintf(buf, sizeof buf, "%s merged %s", section_name, this->string_name()); 721 fprintf(stderr, _("%s: %s input bytes: %zu\n"), 722 program_name, buf, this->input_size_); 723 fprintf(stderr, _("%s: %s input strings: %zu\n"), 724 program_name, buf, this->input_count_); 725 this->stringpool_.print_stats(buf); 726} 727 728// Instantiate the templates we need. 729 730template 731class Output_merge_string<char>; 732 733template 734class Output_merge_string<uint16_t>; 735 736template 737class Output_merge_string<uint32_t>; 738 739#if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_32_BIG) 740template 741void 742Object_merge_map::initialize_input_to_output_map<32>( 743 unsigned int shndx, 744 elfcpp::Elf_types<32>::Elf_Addr starting_address, 745 Unordered_map<section_offset_type, elfcpp::Elf_types<32>::Elf_Addr>*); 746#endif 747 748#if defined(HAVE_TARGET_64_LITTLE) || defined(HAVE_TARGET_64_BIG) 749template 750void 751Object_merge_map::initialize_input_to_output_map<64>( 752 unsigned int shndx, 753 elfcpp::Elf_types<64>::Elf_Addr starting_address, 754 Unordered_map<section_offset_type, elfcpp::Elf_types<64>::Elf_Addr>*); 755#endif 756 757} // End namespace gold. 758