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 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 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   for (section_size_type i = 0; i < len; i += entsize, p += entsize)
 418     {
 419       // Add the constant to the section contents.  If we find that it
 420       // is already in the hash table, we will remove it again.
 421       Merge_data_key k = this->len_;
 422       this->add_constant(p);
 423
 424       std::pair<Merge_data_hashtable::iterator, bool> ins =
 425         this->hashtable_.insert(k);
 426
 427       if (!ins.second)
 428         {
 429           // Key was already present.  Remove the copy we just added.
 430           this->len_ -= entsize;
 431           k = *ins.first;
 432         }
 433
 434       // Record the offset of this constant in the output section.
 435       this->add_mapping(object, shndx, i, entsize, k);
 436     }
 437
 438   return true;
 439 }
 440
 441 // Set the final data size in a merged output section with fixed size
 442 // constants.
 443
 444 void
 445 Output_merge_data::set_final_data_size()
 446 {
 447   // Release the memory we don't need.
 448   this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_));
 449   gold_assert(this->p_ != NULL);
 450   this->set_data_size(this->len_);
 451 }
 452
 453 // Write the data of a merged output section with fixed size constants
 454 // to the file.
 455
 456 void
 457 Output_merge_data::do_write(Output_file* of)
 458 {
 459   of->write(this->offset(), this->p_, this->len_);
 460 }
 461
 462 // Write the data to a buffer.
 463
 464 void
 465 Output_merge_data::do_write_to_buffer(unsigned char* buffer)
 466 {
 467   memcpy(buffer, this->p_, this->len_);
 468 }
 469
 470 // Class Output_merge_string.
 471
 472 // Add an input section to a merged string section.
 473
 474 template<typename Char_type>
 475 bool
 476 Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
 477                                                      unsigned int shndx)
 478 {
 479   section_size_type len;
 480   const unsigned char* pdata = object->section_contents(shndx, &len, false);
 481
 482   const Char_type* p = reinterpret_cast<const Char_type*>(pdata);
 483   const Char_type* pend = p + len;
 484
 485   if (len % sizeof(Char_type) != 0)
 486     {
 487       object->error(_("mergeable string section length not multiple of "
 488                       "character size"));
 489       return false;
 490     }
 491
 492   // The index I is in bytes, not characters.
 493   section_size_type i = 0;
 494   while (i < len)
 495     {
 496       const Char_type* pl;
 497       for (pl = p; *pl != 0; ++pl)
 498         {
 499           if (pl >= pend)
 500             {
 501               object->error(_("entry in mergeable string section "
 502                               "not null terminated"));
 503               break;
 504             }
 505         }
 506
 507       const Char_type* str = this->stringpool_.add_prefix(p, pl - p, NULL);
 508
 509       section_size_type bytelen_with_null = ((pl - p) + 1) * sizeof(Char_type);
 510       this->merged_strings_.push_back(Merged_string(object, shndx, i, str,
 511                                                     bytelen_with_null));
 512
 513       p = pl + 1;
 514       i += bytelen_with_null;
 515     }
 516
 517   return true;
 518 }
 519
 520 // Finalize the mappings from the input sections to the output
 521 // section, and return the final data size.
 522
 523 template<typename Char_type>
 524 section_size_type
 525 Output_merge_string<Char_type>::finalize_merged_data()
 526 {
 527   this->stringpool_.set_string_offsets();
 528
 529   for (typename Merged_strings::const_iterator p =
 530          this->merged_strings_.begin();
 531        p != this->merged_strings_.end();
 532        ++p)
 533     this->add_mapping(p->object, p->shndx, p->offset, p->length,
 534                       this->stringpool_.get_offset(p->string));
 535
 536   // Save some memory.
 537   this->merged_strings_.clear();
 538
 539   return this->stringpool_.get_strtab_size();
 540 }
 541
 542 template<typename Char_type>
 543 void
 544 Output_merge_string<Char_type>::set_final_data_size()
 545 {
 546   const off_t final_data_size = this->finalize_merged_data();
 547   this->set_data_size(final_data_size);
 548 }
 549
 550 // Write out a merged string section.
 551
 552 template<typename Char_type>
 553 void
 554 Output_merge_string<Char_type>::do_write(Output_file* of)
 555 {
 556   this->stringpool_.write(of, this->offset());
 557 }
 558
 559 // Write a merged string section to a buffer.
 560
 561 template<typename Char_type>
 562 void
 563 Output_merge_string<Char_type>::do_write_to_buffer(unsigned char* buffer)
 564 {
 565   this->stringpool_.write_to_buffer(buffer, this->data_size());
 566 }
 567
 568 // Instantiate the templates we need.
 569
 570 template
 571 class Output_merge_string<char>;
 572
 573 template
 574 class Output_merge_string<uint16_t>;
 575
 576 template
 577 class Output_merge_string<uint32_t>;
 578
 579 } // End namespace gold.