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