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