gold/merge.cc

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