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 // Class Merge_map::Merge_key_less.
  34
  35 // Sort the entries in a merge mapping.  The key is an input object, a
  36 // section index in that object, and an offset in that section.
  37
  38 bool
  39 Merge_map::Merge_key_less::operator()(const Merge_key& mk1,
  40                                       const Merge_key& mk2) const
  41 {
  42   // The order of different objects and different sections doesn't
  43   // matter.  We want to get consistent results across links so we
  44   // don't use pointer comparison.
  45   if (mk1.object != mk2.object)
  46     {
  47       // Two different object files can have the same name: if foo.a
  48       // includes both bar/qux.o and baz/qux.o, then both end up with
  49       // the name foo.a(qux.o).  But it's impossible for two different
  50       // object files to have both the same name and the same offset.
  51       if (mk1.object->offset() != mk2.object->offset())
  52         return mk1.object->offset() < mk2.object->offset();
  53       return mk1.object->name() < mk2.object->name();
  54     }
  55   if (mk1.shndx != mk2.shndx)
  56     return mk1.shndx < mk2.shndx;
  57   return mk1.offset < mk2.offset;
  58 }
  59
  60 // Class Merge_map.
  61
  62 // Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in input
  63 // section SHNDX in object OBJECT to an OUTPUT_OFFSET in a merged
  64 // output section.
  65
  66 void
  67 Merge_map::add_mapping(Relobj* object, unsigned int shndx,
  68                        off_t offset, off_t length, off_t output_offset)
  69 {
  70   Merge_key mk;
  71   mk.object = object;
  72   mk.shndx = shndx;
  73   mk.offset = offset;
  74
  75   Merge_value mv;
  76   mv.length = length;
  77   mv.output_offset = output_offset;
  78
  79   std::pair<Merge_mapping::iterator, bool> ins =
  80     this->merge_map_.insert(std::make_pair(mk, mv));
  81   gold_assert(ins.second);
  82 }
  83
  84 // Return the output offset for an input address.  The input address
  85 // is at offset OFFSET in section SHNDX in OBJECT.  This sets
  86 // *OUTPUT_OFFSET to the offset in the output section.  This returns
  87 // true if the mapping is known, false otherwise.
  88
  89 bool
  90 Merge_map::get_output_offset(const Relobj* object, unsigned int shndx,
  91                              off_t offset, off_t* output_offset) const
  92 {
  93   Merge_key mk;
  94   mk.object = object;
  95   mk.shndx = shndx;
  96   mk.offset = offset;
  97   Merge_mapping::const_iterator p = this->merge_map_.lower_bound(mk);
  98
  99   // If MK is not in the map, lower_bound returns the next iterator
 100   // larger than it.
 101   if (p == this->merge_map_.end()
 102       || p->first.object != object
 103       || p->first.shndx != shndx
 104       || p->first.offset != offset)
 105     {
 106       if (p == this->merge_map_.begin())
 107         return false;
 108       --p;
 109     }
 110
 111   if (p->first.object != object || p->first.shndx != shndx)
 112     return false;
 113
 114   if (offset - p->first.offset >= p->second.length)
 115     return false;
 116
 117   *output_offset = p->second.output_offset;
 118   if (*output_offset != -1)
 119     *output_offset += (offset - p->first.offset);
 120   return true;
 121 }
 122
 123 // Class Output_merge_base.
 124
 125 // Return the output offset for an input offset.  The input address is
 126 // at offset OFFSET in section SHNDX in OBJECT.  If we know the
 127 // offset, set *POUTPUT and return true.  Otherwise return false.
 128
 129 bool
 130 Output_merge_base::do_output_offset(const Relobj* object,
 131                                     unsigned int shndx,
 132                                     off_t offset,
 133                                     off_t* poutput) const
 134 {
 135   return this->merge_map_.get_output_offset(object, shndx, offset, poutput);
 136 }
 137
 138 // Class Output_merge_data.
 139
 140 // Compute the hash code for a fixed-size constant.
 141
 142 size_t
 143 Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const
 144 {
 145   const unsigned char* p = this->pomd_->constant(k);
 146   uint64_t entsize = this->pomd_->entsize();
 147
 148   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
 149   if (sizeof(size_t) == 8)
 150     {
 151       size_t result = static_cast<size_t>(14695981039346656037ULL);
 152       for (uint64_t i = 0; i < entsize; ++i)
 153         {
 154           result &= (size_t) *p++;
 155           result *= 1099511628211ULL;
 156         }
 157       return result;
 158     }
 159   else
 160     {
 161       size_t result = 2166136261UL;
 162       for (uint64_t i = 0; i < entsize; ++i)
 163         {
 164           result ^= (size_t) *p++;
 165           result *= 16777619UL;
 166         }
 167       return result;
 168     }
 169 }
 170
 171 // Return whether one hash table key equals another.
 172
 173 bool
 174 Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1,
 175                                              Merge_data_key k2) const
 176 {
 177   const unsigned char* p1 = this->pomd_->constant(k1);
 178   const unsigned char* p2 = this->pomd_->constant(k2);
 179   return memcmp(p1, p2, this->pomd_->entsize()) == 0;
 180 }
 181
 182 // Add a constant to the end of the section contents.
 183
 184 void
 185 Output_merge_data::add_constant(const unsigned char* p)
 186 {
 187   uint64_t entsize = this->entsize();
 188   uint64_t addsize = std::max(entsize, this->addralign());
 189   if (this->len_ + addsize > this->alc_)
 190     {
 191       if (this->alc_ == 0)
 192         this->alc_ = 128 * addsize;
 193       else
 194         this->alc_ *= 2;
 195       this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_));
 196       if (this->p_ == NULL)
 197         gold_nomem();
 198     }
 199
 200   memcpy(this->p_ + this->len_, p, entsize);
 201   if (addsize > entsize)
 202     memset(this->p_ + this->len_ + entsize, 0, addsize - entsize);
 203   this->len_ += addsize;
 204 }
 205
 206 // Add the input section SHNDX in OBJECT to a merged output section
 207 // which holds fixed length constants.  Return whether we were able to
 208 // handle the section; if not, it will be linked as usual without
 209 // constant merging.
 210
 211 bool
 212 Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
 213 {
 214   off_t len;
 215   const unsigned char* p = object->section_contents(shndx, &len, false);
 216
 217   uint64_t entsize = this->entsize();
 218
 219   if (len % entsize != 0)
 220     return false;
 221
 222   for (off_t i = 0; i < len; i += entsize, p += entsize)
 223     {
 224       // Add the constant to the section contents.  If we find that it
 225       // is already in the hash table, we will remove it again.
 226       Merge_data_key k = this->len_;
 227       this->add_constant(p);
 228
 229       std::pair<Merge_data_hashtable::iterator, bool> ins =
 230         this->hashtable_.insert(k);
 231
 232       if (!ins.second)
 233         {
 234           // Key was already present.  Remove the copy we just added.
 235           this->len_ -= entsize;
 236           k = *ins.first;
 237         }
 238
 239       // Record the offset of this constant in the output section.
 240       this->add_mapping(object, shndx, i, entsize, k);
 241     }
 242
 243   return true;
 244 }
 245
 246 // Set the final data size in a merged output section with fixed size
 247 // constants.
 248
 249 void
 250 Output_merge_data::do_set_address(uint64_t, off_t)
 251 {
 252   // Release the memory we don't need.
 253   this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_));
 254   gold_assert(this->p_ != NULL);
 255   this->set_data_size(this->len_);
 256 }
 257
 258 // Write the data of a merged output section with fixed size constants
 259 // to the file.
 260
 261 void
 262 Output_merge_data::do_write(Output_file* of)
 263 {
 264   of->write(this->offset(), this->p_, this->len_);
 265 }
 266
 267 // Class Output_merge_string.
 268
 269 // Add an input section to a merged string section.
 270
 271 template<typename Char_type>
 272 bool
 273 Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
 274                                                      unsigned int shndx)
 275 {
 276   off_t len;
 277   const unsigned char* pdata = object->section_contents(shndx, &len, false);
 278
 279   const Char_type* p = reinterpret_cast<const Char_type*>(pdata);
 280
 281   if (len % sizeof(Char_type) != 0)
 282     {
 283       object->error(_("mergeable string section length not multiple of "
 284                       "character size"));
 285       return false;
 286     }
 287
 288   // The index I is in bytes, not characters.
 289   off_t i = 0;
 290   while (i < len)
 291     {
 292       off_t plen = 0;
 293       for (const Char_type* pl = p; *pl != 0; ++pl)
 294         {
 295           // The length PLEN is in characters, not bytes.
 296           ++plen;
 297           if (i + plen * static_cast<off_t>(sizeof(Char_type)) >= len)
 298             {
 299               object->error(_("entry in mergeable string section "
 300                               "not null terminated"));
 301               break;
 302             }
 303         }
 304
 305       const Char_type* str = this->stringpool_.add(p, true, NULL);
 306
 307       off_t bytelen_with_null = (plen + 1) * sizeof(Char_type);
 308       this->merged_strings_.push_back(Merged_string(object, shndx, i, str,
 309                                                     bytelen_with_null));
 310
 311       p += plen + 1;
 312       i += bytelen_with_null;
 313     }
 314
 315   return true;
 316 }
 317
 318 // Set the final data size of a merged string section.  This is where
 319 // we finalize the mappings from the input sections to the output
 320 // section.
 321
 322 template<typename Char_type>
 323 void
 324 Output_merge_string<Char_type>::do_set_address(uint64_t, off_t)
 325 {
 326   this->stringpool_.set_string_offsets();
 327
 328   for (typename Merged_strings::const_iterator p =
 329          this->merged_strings_.begin();
 330        p != this->merged_strings_.end();
 331        ++p)
 332     this->add_mapping(p->object, p->shndx, p->offset, p->length,
 333                       this->stringpool_.get_offset(p->string));
 334
 335   this->set_data_size(this->stringpool_.get_strtab_size());
 336
 337   // Save some memory.
 338   this->merged_strings_.clear();
 339 }
 340
 341 // Write out a merged string section.
 342
 343 template<typename Char_type>
 344 void
 345 Output_merge_string<Char_type>::do_write(Output_file* of)
 346 {
 347   this->stringpool_.write(of, this->offset());
 348 }
 349
 350 // Instantiate the templates we need.
 351
 352 template
 353 class Output_merge_string<char>;
 354
 355 template
 356 class Output_merge_string<uint16_t>;
 357
 358 template
 359 class Output_merge_string<uint32_t>;
 360
 361 } // End namespace gold.