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