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