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