gold/dynobj.cc

   1 // dynobj.cc -- dynamic object support 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 <vector>
  26 #include <cstring>
  27
  28 #include "elfcpp.h"
  29 #include "parameters.h"
  30 #include "symtab.h"
  31 #include "dynobj.h"
  32
  33 namespace gold
  34 {
  35
  36 // Class Dynobj.
  37
  38 // Sets up the default soname_ to use, in the (rare) cases we never
  39 // see a DT_SONAME entry.
  40
  41 Dynobj::Dynobj(const std::string& name, Input_file* input_file, off_t offset)
  42   : Object(name, input_file, true, offset),
  43     needed_(),
  44     unknown_needed_(UNKNOWN_NEEDED_UNSET)
  45 {
  46   // This will be overridden by a DT_SONAME entry, hopefully.  But if
  47   // we never see a DT_SONAME entry, our rule is to use the dynamic
  48   // object's filename.  The only exception is when the dynamic object
  49   // is part of an archive (so the filename is the archive's
  50   // filename).  In that case, we use just the dynobj's name-in-archive.
  51   this->soname_ = this->input_file()->found_name();
  52   if (this->offset() != 0)
  53     {
  54       std::string::size_type open_paren = this->name().find('(');
  55       std::string::size_type close_paren = this->name().find(')');
  56       if (open_paren != std::string::npos && close_paren != std::string::npos)
  57         {
  58           // It's an archive, and name() is of the form 'foo.a(bar.so)'.
  59           this->soname_ = this->name().substr(open_paren + 1,
  60                                               close_paren - (open_paren + 1));
  61         }
  62     }
  63 }
  64
  65 // Class Sized_dynobj.
  66
  67 template<int size, bool big_endian>
  68 Sized_dynobj<size, big_endian>::Sized_dynobj(
  69     const std::string& name,
  70     Input_file* input_file,
  71     off_t offset,
  72     const elfcpp::Ehdr<size, big_endian>& ehdr)
  73   : Dynobj(name, input_file, offset),
  74     elf_file_(this, ehdr)
  75 {
  76 }
  77
  78 // Set up the object.
  79
  80 template<int size, bool big_endian>
  81 void
  82 Sized_dynobj<size, big_endian>::setup(
  83     const elfcpp::Ehdr<size, big_endian>& ehdr)
  84 {
  85   this->set_target(ehdr.get_e_machine(), size, big_endian,
  86                    ehdr.get_e_ident()[elfcpp::EI_OSABI],
  87                    ehdr.get_e_ident()[elfcpp::EI_ABIVERSION]);
  88
  89   const unsigned int shnum = this->elf_file_.shnum();
  90   this->set_shnum(shnum);
  91 }
  92
  93 // Find the SHT_DYNSYM section and the various version sections, and
  94 // the dynamic section, given the section headers.
  95
  96 template<int size, bool big_endian>
  97 void
  98 Sized_dynobj<size, big_endian>::find_dynsym_sections(
  99     const unsigned char* pshdrs,
 100     unsigned int* pdynsym_shndx,
 101     unsigned int* pversym_shndx,
 102     unsigned int* pverdef_shndx,
 103     unsigned int* pverneed_shndx,
 104     unsigned int* pdynamic_shndx)
 105 {
 106   *pdynsym_shndx = -1U;
 107   *pversym_shndx = -1U;
 108   *pverdef_shndx = -1U;
 109   *pverneed_shndx = -1U;
 110   *pdynamic_shndx = -1U;
 111
 112   const unsigned int shnum = this->shnum();
 113   const unsigned char* p = pshdrs;
 114   for (unsigned int i = 0; i < shnum; ++i, p += This::shdr_size)
 115     {
 116       typename This::Shdr shdr(p);
 117
 118       unsigned int* pi;
 119       switch (shdr.get_sh_type())
 120         {
 121         case elfcpp::SHT_DYNSYM:
 122           pi = pdynsym_shndx;
 123           break;
 124         case elfcpp::SHT_GNU_versym:
 125           pi = pversym_shndx;
 126           break;
 127         case elfcpp::SHT_GNU_verdef:
 128           pi = pverdef_shndx;
 129           break;
 130         case elfcpp::SHT_GNU_verneed:
 131           pi = pverneed_shndx;
 132           break;
 133         case elfcpp::SHT_DYNAMIC:
 134           pi = pdynamic_shndx;
 135           break;
 136         default:
 137           pi = NULL;
 138           break;
 139         }
 140
 141       if (pi == NULL)
 142         continue;
 143
 144       if (*pi != -1U)
 145         this->error(_("unexpected duplicate type %u section: %u, %u"),
 146                     shdr.get_sh_type(), *pi, i);
 147
 148       *pi = i;
 149     }
 150 }
 151
 152 // Read the contents of section SHNDX.  PSHDRS points to the section
 153 // headers.  TYPE is the expected section type.  LINK is the expected
 154 // section link.  Store the data in *VIEW and *VIEW_SIZE.  The
 155 // section's sh_info field is stored in *VIEW_INFO.
 156
 157 template<int size, bool big_endian>
 158 void
 159 Sized_dynobj<size, big_endian>::read_dynsym_section(
 160     const unsigned char* pshdrs,
 161     unsigned int shndx,
 162     elfcpp::SHT type,
 163     unsigned int link,
 164     File_view** view,
 165     section_size_type* view_size,
 166     unsigned int* view_info)
 167 {
 168   if (shndx == -1U)
 169     {
 170       *view = NULL;
 171       *view_size = 0;
 172       *view_info = 0;
 173       return;
 174     }
 175
 176   typename This::Shdr shdr(pshdrs + shndx * This::shdr_size);
 177
 178   gold_assert(shdr.get_sh_type() == type);
 179
 180   if (shdr.get_sh_link() != link)
 181     this->error(_("unexpected link in section %u header: %u != %u"),
 182                 shndx, shdr.get_sh_link(), link);
 183
 184   *view = this->get_lasting_view(shdr.get_sh_offset(), shdr.get_sh_size(),
 185                                  false);
 186   *view_size = convert_to_section_size_type(shdr.get_sh_size());
 187   *view_info = shdr.get_sh_info();
 188 }
 189
 190 // Read the dynamic tags.  Set the soname field if this shared object
 191 // has a DT_SONAME tag.  Record the DT_NEEDED tags.  PSHDRS points to
 192 // the section headers.  DYNAMIC_SHNDX is the section index of the
 193 // SHT_DYNAMIC section.  STRTAB_SHNDX, STRTAB, and STRTAB_SIZE are the
 194 // section index and contents of a string table which may be the one
 195 // associated with the SHT_DYNAMIC section.
 196
 197 template<int size, bool big_endian>
 198 void
 199 Sized_dynobj<size, big_endian>::read_dynamic(const unsigned char* pshdrs,
 200                                              unsigned int dynamic_shndx,
 201                                              unsigned int strtab_shndx,
 202                                              const unsigned char* strtabu,
 203                                              off_t strtab_size)
 204 {
 205   typename This::Shdr dynamicshdr(pshdrs + dynamic_shndx * This::shdr_size);
 206   gold_assert(dynamicshdr.get_sh_type() == elfcpp::SHT_DYNAMIC);
 207
 208   const off_t dynamic_size = dynamicshdr.get_sh_size();
 209   const unsigned char* pdynamic = this->get_view(dynamicshdr.get_sh_offset(),
 210                                                  dynamic_size, false);
 211
 212   const unsigned int link = dynamicshdr.get_sh_link();
 213   if (link != strtab_shndx)
 214     {
 215       if (link >= this->shnum())
 216         {
 217           this->error(_("DYNAMIC section %u link out of range: %u"),
 218                       dynamic_shndx, link);
 219           return;
 220         }
 221
 222       typename This::Shdr strtabshdr(pshdrs + link * This::shdr_size);
 223       if (strtabshdr.get_sh_type() != elfcpp::SHT_STRTAB)
 224         {
 225           this->error(_("DYNAMIC section %u link %u is not a strtab"),
 226                       dynamic_shndx, link);
 227           return;
 228         }
 229
 230       strtab_size = strtabshdr.get_sh_size();
 231       strtabu = this->get_view(strtabshdr.get_sh_offset(), strtab_size, false);
 232     }
 233
 234   const char* const strtab = reinterpret_cast<const char*>(strtabu);
 235
 236   for (const unsigned char* p = pdynamic;
 237        p < pdynamic + dynamic_size;
 238        p += This::dyn_size)
 239     {
 240       typename This::Dyn dyn(p);
 241
 242       switch (dyn.get_d_tag())
 243         {
 244         case elfcpp::DT_NULL:
 245           // We should always see DT_NULL at the end of the dynamic
 246           // tags.
 247           return;
 248
 249         case elfcpp::DT_SONAME:
 250           {
 251             off_t val = dyn.get_d_val();
 252             if (val >= strtab_size)
 253               this->error(_("DT_SONAME value out of range: %lld >= %lld"),
 254                           static_cast<long long>(val),
 255                           static_cast<long long>(strtab_size));
 256             else
 257               this->set_soname_string(strtab + val);
 258           }
 259           break;
 260
 261         case elfcpp::DT_NEEDED:
 262           {
 263             off_t val = dyn.get_d_val();
 264             if (val >= strtab_size)
 265               this->error(_("DT_NEEDED value out of range: %lld >= %lld"),
 266                           static_cast<long long>(val),
 267                           static_cast<long long>(strtab_size));
 268             else
 269               this->add_needed(strtab + val);
 270           }
 271           break;
 272
 273         default:
 274           break;
 275         }
 276     }
 277
 278   this->error(_("missing DT_NULL in dynamic segment"));
 279 }
 280
 281 // Read the symbols and sections from a dynamic object.  We read the
 282 // dynamic symbols, not the normal symbols.
 283
 284 template<int size, bool big_endian>
 285 void
 286 Sized_dynobj<size, big_endian>::do_read_symbols(Read_symbols_data* sd)
 287 {
 288   this->read_section_data(&this->elf_file_, sd);
 289
 290   const unsigned char* const pshdrs = sd->section_headers->data();
 291
 292   unsigned int dynsym_shndx;
 293   unsigned int versym_shndx;
 294   unsigned int verdef_shndx;
 295   unsigned int verneed_shndx;
 296   unsigned int dynamic_shndx;
 297   this->find_dynsym_sections(pshdrs, &dynsym_shndx, &versym_shndx,
 298                              &verdef_shndx, &verneed_shndx, &dynamic_shndx);
 299
 300   unsigned int strtab_shndx = -1U;
 301
 302   sd->symbols = NULL;
 303   sd->symbols_size = 0;
 304   sd->external_symbols_offset = 0;
 305   sd->symbol_names = NULL;
 306   sd->symbol_names_size = 0;
 307
 308   if (dynsym_shndx != -1U)
 309     {
 310       // Get the dynamic symbols.
 311       typename This::Shdr dynsymshdr(pshdrs + dynsym_shndx * This::shdr_size);
 312       gold_assert(dynsymshdr.get_sh_type() == elfcpp::SHT_DYNSYM);
 313
 314       sd->symbols = this->get_lasting_view(dynsymshdr.get_sh_offset(),
 315                                            dynsymshdr.get_sh_size(), false);
 316       sd->symbols_size =
 317         convert_to_section_size_type(dynsymshdr.get_sh_size());
 318
 319       // Get the symbol names.
 320       strtab_shndx = dynsymshdr.get_sh_link();
 321       if (strtab_shndx >= this->shnum())
 322         {
 323           this->error(_("invalid dynamic symbol table name index: %u"),
 324                       strtab_shndx);
 325           return;
 326         }
 327       typename This::Shdr strtabshdr(pshdrs + strtab_shndx * This::shdr_size);
 328       if (strtabshdr.get_sh_type() != elfcpp::SHT_STRTAB)
 329         {
 330           this->error(_("dynamic symbol table name section "
 331                         "has wrong type: %u"),
 332                       static_cast<unsigned int>(strtabshdr.get_sh_type()));
 333           return;
 334         }
 335
 336       sd->symbol_names = this->get_lasting_view(strtabshdr.get_sh_offset(),
 337                                                 strtabshdr.get_sh_size(),
 338                                                 true);
 339       sd->symbol_names_size =
 340         convert_to_section_size_type(strtabshdr.get_sh_size());
 341
 342       // Get the version information.
 343
 344       unsigned int dummy;
 345       this->read_dynsym_section(pshdrs, versym_shndx, elfcpp::SHT_GNU_versym,
 346                                 dynsym_shndx, &sd->versym, &sd->versym_size,
 347                                 &dummy);
 348
 349       // We require that the version definition and need section link
 350       // to the same string table as the dynamic symbol table.  This
 351       // is not a technical requirement, but it always happens in
 352       // practice.  We could change this if necessary.
 353
 354       this->read_dynsym_section(pshdrs, verdef_shndx, elfcpp::SHT_GNU_verdef,
 355                                 strtab_shndx, &sd->verdef, &sd->verdef_size,
 356                                 &sd->verdef_info);
 357
 358       this->read_dynsym_section(pshdrs, verneed_shndx, elfcpp::SHT_GNU_verneed,
 359                                 strtab_shndx, &sd->verneed, &sd->verneed_size,
 360                                 &sd->verneed_info);
 361     }
 362
 363   // Read the SHT_DYNAMIC section to find whether this shared object
 364   // has a DT_SONAME tag and to record any DT_NEEDED tags.  This
 365   // doesn't really have anything to do with reading the symbols, but
 366   // this is a convenient place to do it.
 367   if (dynamic_shndx != -1U)
 368     this->read_dynamic(pshdrs, dynamic_shndx, strtab_shndx,
 369                        (sd->symbol_names == NULL
 370                         ? NULL
 371                         : sd->symbol_names->data()),
 372                        sd->symbol_names_size);
 373 }
 374
 375 // Lay out the input sections for a dynamic object.  We don't want to
 376 // include sections from a dynamic object, so all that we actually do
 377 // here is check for .gnu.warning sections.
 378
 379 template<int size, bool big_endian>
 380 void
 381 Sized_dynobj<size, big_endian>::do_layout(Symbol_table* symtab,
 382                                           Layout*,
 383                                           Read_symbols_data* sd)
 384 {
 385   const unsigned int shnum = this->shnum();
 386   if (shnum == 0)
 387     return;
 388
 389   // Get the section headers.
 390   const unsigned char* pshdrs = sd->section_headers->data();
 391
 392   // Get the section names.
 393   const unsigned char* pnamesu = sd->section_names->data();
 394   const char* pnames = reinterpret_cast<const char*>(pnamesu);
 395
 396   // Skip the first, dummy, section.
 397   pshdrs += This::shdr_size;
 398   for (unsigned int i = 1; i < shnum; ++i, pshdrs += This::shdr_size)
 399     {
 400       typename This::Shdr shdr(pshdrs);
 401
 402       if (shdr.get_sh_name() >= sd->section_names_size)
 403         {
 404           this->error(_("bad section name offset for section %u: %lu"),
 405                       i, static_cast<unsigned long>(shdr.get_sh_name()));
 406           return;
 407         }
 408
 409       const char* name = pnames + shdr.get_sh_name();
 410
 411       this->handle_gnu_warning_section(name, i, symtab);
 412     }
 413
 414   delete sd->section_headers;
 415   sd->section_headers = NULL;
 416   delete sd->section_names;
 417   sd->section_names = NULL;
 418 }
 419
 420 // Add an entry to the vector mapping version numbers to version
 421 // strings.
 422
 423 template<int size, bool big_endian>
 424 void
 425 Sized_dynobj<size, big_endian>::set_version_map(
 426     Version_map* version_map,
 427     unsigned int ndx,
 428     const char* name) const
 429 {
 430   if (ndx >= version_map->size())
 431     version_map->resize(ndx + 1);
 432   if ((*version_map)[ndx] != NULL)
 433     this->error(_("duplicate definition for version %u"), ndx);
 434   (*version_map)[ndx] = name;
 435 }
 436
 437 // Add mappings for the version definitions to VERSION_MAP.
 438
 439 template<int size, bool big_endian>
 440 void
 441 Sized_dynobj<size, big_endian>::make_verdef_map(
 442     Read_symbols_data* sd,
 443     Version_map* version_map) const
 444 {
 445   if (sd->verdef == NULL)
 446     return;
 447
 448   const char* names = reinterpret_cast<const char*>(sd->symbol_names->data());
 449   section_size_type names_size = sd->symbol_names_size;
 450
 451   const unsigned char* pverdef = sd->verdef->data();
 452   section_size_type verdef_size = sd->verdef_size;
 453   const unsigned int count = sd->verdef_info;
 454
 455   const unsigned char* p = pverdef;
 456   for (unsigned int i = 0; i < count; ++i)
 457     {
 458       elfcpp::Verdef<size, big_endian> verdef(p);
 459
 460       if (verdef.get_vd_version() != elfcpp::VER_DEF_CURRENT)
 461         {
 462           this->error(_("unexpected verdef version %u"),
 463                       verdef.get_vd_version());
 464           return;
 465         }
 466
 467       const unsigned int vd_ndx = verdef.get_vd_ndx();
 468
 469       // The GNU linker clears the VERSYM_HIDDEN bit.  I'm not
 470       // sure why.
 471
 472       // The first Verdaux holds the name of this version.  Subsequent
 473       // ones are versions that this one depends upon, which we don't
 474       // care about here.
 475       const unsigned int vd_cnt = verdef.get_vd_cnt();
 476       if (vd_cnt < 1)
 477         {
 478           this->error(_("verdef vd_cnt field too small: %u"), vd_cnt);
 479           return;
 480         }
 481
 482       const unsigned int vd_aux = verdef.get_vd_aux();
 483       if ((p - pverdef) + vd_aux >= verdef_size)
 484         {
 485           this->error(_("verdef vd_aux field out of range: %u"), vd_aux);
 486           return;
 487         }
 488
 489       const unsigned char* pvda = p + vd_aux;
 490       elfcpp::Verdaux<size, big_endian> verdaux(pvda);
 491
 492       const unsigned int vda_name = verdaux.get_vda_name();
 493       if (vda_name >= names_size)
 494         {
 495           this->error(_("verdaux vda_name field out of range: %u"), vda_name);
 496           return;
 497         }
 498
 499       this->set_version_map(version_map, vd_ndx, names + vda_name);
 500
 501       const unsigned int vd_next = verdef.get_vd_next();
 502       if ((p - pverdef) + vd_next >= verdef_size)
 503         {
 504           this->error(_("verdef vd_next field out of range: %u"), vd_next);
 505           return;
 506         }
 507
 508       p += vd_next;
 509     }
 510 }
 511
 512 // Add mappings for the required versions to VERSION_MAP.
 513
 514 template<int size, bool big_endian>
 515 void
 516 Sized_dynobj<size, big_endian>::make_verneed_map(
 517     Read_symbols_data* sd,
 518     Version_map* version_map) const
 519 {
 520   if (sd->verneed == NULL)
 521     return;
 522
 523   const char* names = reinterpret_cast<const char*>(sd->symbol_names->data());
 524   section_size_type names_size = sd->symbol_names_size;
 525
 526   const unsigned char* pverneed = sd->verneed->data();
 527   const section_size_type verneed_size = sd->verneed_size;
 528   const unsigned int count = sd->verneed_info;
 529
 530   const unsigned char* p = pverneed;
 531   for (unsigned int i = 0; i < count; ++i)
 532     {
 533       elfcpp::Verneed<size, big_endian> verneed(p);
 534
 535       if (verneed.get_vn_version() != elfcpp::VER_NEED_CURRENT)
 536         {
 537           this->error(_("unexpected verneed version %u"),
 538                       verneed.get_vn_version());
 539           return;
 540         }
 541
 542       const unsigned int vn_aux = verneed.get_vn_aux();
 543
 544       if ((p - pverneed) + vn_aux >= verneed_size)
 545         {
 546           this->error(_("verneed vn_aux field out of range: %u"), vn_aux);
 547           return;
 548         }
 549
 550       const unsigned int vn_cnt = verneed.get_vn_cnt();
 551       const unsigned char* pvna = p + vn_aux;
 552       for (unsigned int j = 0; j < vn_cnt; ++j)
 553         {
 554           elfcpp::Vernaux<size, big_endian> vernaux(pvna);
 555
 556           const unsigned int vna_name = vernaux.get_vna_name();
 557           if (vna_name >= names_size)
 558             {
 559               this->error(_("vernaux vna_name field out of range: %u"),
 560                           vna_name);
 561               return;
 562             }
 563
 564           this->set_version_map(version_map, vernaux.get_vna_other(),
 565                                 names + vna_name);
 566
 567           const unsigned int vna_next = vernaux.get_vna_next();
 568           if ((pvna - pverneed) + vna_next >= verneed_size)
 569             {
 570               this->error(_("verneed vna_next field out of range: %u"),
 571                           vna_next);
 572               return;
 573             }
 574
 575           pvna += vna_next;
 576         }
 577
 578       const unsigned int vn_next = verneed.get_vn_next();
 579       if ((p - pverneed) + vn_next >= verneed_size)
 580         {
 581           this->error(_("verneed vn_next field out of range: %u"), vn_next);
 582           return;
 583         }
 584
 585       p += vn_next;
 586     }
 587 }
 588
 589 // Create a vector mapping version numbers to version strings.
 590
 591 template<int size, bool big_endian>
 592 void
 593 Sized_dynobj<size, big_endian>::make_version_map(
 594     Read_symbols_data* sd,
 595     Version_map* version_map) const
 596 {
 597   if (sd->verdef == NULL && sd->verneed == NULL)
 598     return;
 599
 600   // A guess at the maximum version number we will see.  If this is
 601   // wrong we will be less efficient but still correct.
 602   version_map->reserve(sd->verdef_info + sd->verneed_info * 10);
 603
 604   this->make_verdef_map(sd, version_map);
 605   this->make_verneed_map(sd, version_map);
 606 }
 607
 608 // Add the dynamic symbols to the symbol table.
 609
 610 template<int size, bool big_endian>
 611 void
 612 Sized_dynobj<size, big_endian>::do_add_symbols(Symbol_table* symtab,
 613                                                Read_symbols_data* sd)
 614 {
 615   if (sd->symbols == NULL)
 616     {
 617       gold_assert(sd->symbol_names == NULL);
 618       gold_assert(sd->versym == NULL && sd->verdef == NULL
 619                   && sd->verneed == NULL);
 620       return;
 621     }
 622
 623   const int sym_size = This::sym_size;
 624   const size_t symcount = sd->symbols_size / sym_size;
 625   gold_assert(sd->external_symbols_offset == 0);
 626   if (symcount * sym_size != sd->symbols_size)
 627     {
 628       this->error(_("size of dynamic symbols is not multiple of symbol size"));
 629       return;
 630     }
 631
 632   Version_map version_map;
 633   this->make_version_map(sd, &version_map);
 634
 635   const char* sym_names =
 636     reinterpret_cast<const char*>(sd->symbol_names->data());
 637   symtab->add_from_dynobj(this, sd->symbols->data(), symcount,
 638                           sym_names, sd->symbol_names_size,
 639                           (sd->versym == NULL
 640                            ? NULL
 641                            : sd->versym->data()),
 642                           sd->versym_size,
 643                           &version_map);
 644
 645   delete sd->symbols;
 646   sd->symbols = NULL;
 647   delete sd->symbol_names;
 648   sd->symbol_names = NULL;
 649   if (sd->versym != NULL)
 650     {
 651       delete sd->versym;
 652       sd->versym = NULL;
 653     }
 654   if (sd->verdef != NULL)
 655     {
 656       delete sd->verdef;
 657       sd->verdef = NULL;
 658     }
 659   if (sd->verneed != NULL)
 660     {
 661       delete sd->verneed;
 662       sd->verneed = NULL;
 663     }
 664 }
 665
 666 // Given a vector of hash codes, compute the number of hash buckets to
 667 // use.
 668
 669 unsigned int
 670 Dynobj::compute_bucket_count(const std::vector<uint32_t>& hashcodes,
 671                              bool for_gnu_hash_table)
 672 {
 673   // FIXME: Implement optional hash table optimization.
 674
 675   // Array used to determine the number of hash table buckets to use
 676   // based on the number of symbols there are.  If there are fewer
 677   // than 3 symbols we use 1 bucket, fewer than 17 symbols we use 3
 678   // buckets, fewer than 37 we use 17 buckets, and so forth.  We never
 679   // use more than 32771 buckets.  This is straight from the old GNU
 680   // linker.
 681   static const unsigned int buckets[] =
 682   {
 683     1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031, 2053, 4099, 8209,
 684     16411, 32771
 685   };
 686   const int buckets_count = sizeof buckets / sizeof buckets[0];
 687
 688   unsigned int symcount = hashcodes.size();
 689   unsigned int ret = 1;
 690   for (int i = 0; i < buckets_count; ++i)
 691     {
 692       if (symcount < buckets[i])
 693         break;
 694       ret = buckets[i];
 695     }
 696
 697   if (for_gnu_hash_table && ret < 2)
 698     ret = 2;
 699
 700   return ret;
 701 }
 702
 703 // The standard ELF hash function.  This hash function must not
 704 // change, as the dynamic linker uses it also.
 705
 706 uint32_t
 707 Dynobj::elf_hash(const char* name)
 708 {
 709   const unsigned char* nameu = reinterpret_cast<const unsigned char*>(name);
 710   uint32_t h = 0;
 711   unsigned char c;
 712   while ((c = *nameu++) != '\0')
 713     {
 714       h = (h << 4) + c;
 715       uint32_t g = h & 0xf0000000;
 716       if (g != 0)
 717         {
 718           h ^= g >> 24;
 719           // The ELF ABI says h &= ~g, but using xor is equivalent in
 720           // this case (since g was set from h) and may save one
 721           // instruction.
 722           h ^= g;
 723         }
 724     }
 725   return h;
 726 }
 727
 728 // Create a standard ELF hash table, setting *PPHASH and *PHASHLEN.
 729 // DYNSYMS is a vector with all the global dynamic symbols.
 730 // LOCAL_DYNSYM_COUNT is the number of local symbols in the dynamic
 731 // symbol table.
 732
 733 void
 734 Dynobj::create_elf_hash_table(const std::vector<Symbol*>& dynsyms,
 735                               unsigned int local_dynsym_count,
 736                               unsigned char** pphash,
 737                               unsigned int* phashlen)
 738 {
 739   unsigned int dynsym_count = dynsyms.size();
 740
 741   // Get the hash values for all the symbols.
 742   std::vector<uint32_t> dynsym_hashvals(dynsym_count);
 743   for (unsigned int i = 0; i < dynsym_count; ++i)
 744     dynsym_hashvals[i] = Dynobj::elf_hash(dynsyms[i]->name());
 745
 746   const unsigned int bucketcount =
 747     Dynobj::compute_bucket_count(dynsym_hashvals, false);
 748
 749   std::vector<uint32_t> bucket(bucketcount);
 750   std::vector<uint32_t> chain(local_dynsym_count + dynsym_count);
 751
 752   for (unsigned int i = 0; i < dynsym_count; ++i)
 753     {
 754       unsigned int dynsym_index = dynsyms[i]->dynsym_index();
 755       unsigned int bucketpos = dynsym_hashvals[i] % bucketcount;
 756       chain[dynsym_index] = bucket[bucketpos];
 757       bucket[bucketpos] = dynsym_index;
 758     }
 759
 760   unsigned int hashlen = ((2
 761                            + bucketcount
 762                            + local_dynsym_count
 763                            + dynsym_count)
 764                           * 4);
 765   unsigned char* phash = new unsigned char[hashlen];
 766
 767   if (parameters->is_big_endian())
 768     {
 769 #if defined(HAVE_TARGET_32_BIG) || defined(HAVE_TARGET_64_BIG)
 770       Dynobj::sized_create_elf_hash_table<true>(bucket, chain, phash,
 771                                                 hashlen);
 772 #else
 773       gold_unreachable();
 774 #endif
 775     }
 776   else
 777     {
 778 #if defined(HAVE_TARGET_32_LITTLE) || defined(HAVE_TARGET_64_LITTLE)
 779       Dynobj::sized_create_elf_hash_table<false>(bucket, chain, phash,
 780                                                  hashlen);
 781 #else
 782       gold_unreachable();
 783 #endif
 784     }
 785
 786   *pphash = phash;
 787   *phashlen = hashlen;
 788 }
 789
 790 // Fill in an ELF hash table.
 791
 792 template<bool big_endian>
 793 void
 794 Dynobj::sized_create_elf_hash_table(const std::vector<uint32_t>& bucket,
 795                                     const std::vector<uint32_t>& chain,
 796                                     unsigned char* phash,
 797                                     unsigned int hashlen)
 798 {
 799   unsigned char* p = phash;
 800
 801   const unsigned int bucketcount = bucket.size();
 802   const unsigned int chaincount = chain.size();
 803
 804   elfcpp::Swap<32, big_endian>::writeval(p, bucketcount);
 805   p += 4;
 806   elfcpp::Swap<32, big_endian>::writeval(p, chaincount);
 807   p += 4;
 808
 809   for (unsigned int i = 0; i < bucketcount; ++i)
 810     {
 811       elfcpp::Swap<32, big_endian>::writeval(p, bucket[i]);
 812       p += 4;
 813     }
 814
 815   for (unsigned int i = 0; i < chaincount; ++i)
 816     {
 817       elfcpp::Swap<32, big_endian>::writeval(p, chain[i]);
 818       p += 4;
 819     }
 820
 821   gold_assert(static_cast<unsigned int>(p - phash) == hashlen);
 822 }
 823
 824 // The hash function used for the GNU hash table.  This hash function
 825 // must not change, as the dynamic linker uses it also.
 826
 827 uint32_t
 828 Dynobj::gnu_hash(const char* name)
 829 {
 830   const unsigned char* nameu = reinterpret_cast<const unsigned char*>(name);
 831   uint32_t h = 5381;
 832   unsigned char c;
 833   while ((c = *nameu++) != '\0')
 834     h = (h << 5) + h + c;
 835   return h;
 836 }
 837
 838 // Create a GNU hash table, setting *PPHASH and *PHASHLEN.  GNU hash
 839 // tables are an extension to ELF which are recognized by the GNU
 840 // dynamic linker.  They are referenced using dynamic tag DT_GNU_HASH.
 841 // TARGET is the target.  DYNSYMS is a vector with all the global
 842 // symbols which will be going into the dynamic symbol table.
 843 // LOCAL_DYNSYM_COUNT is the number of local symbols in the dynamic
 844 // symbol table.
 845
 846 void
 847 Dynobj::create_gnu_hash_table(const std::vector<Symbol*>& dynsyms,
 848                               unsigned int local_dynsym_count,
 849                               unsigned char** pphash,
 850                               unsigned int* phashlen)
 851 {
 852   const unsigned int count = dynsyms.size();
 853
 854   // Sort the dynamic symbols into two vectors.  Symbols which we do
 855   // not want to put into the hash table we store into
 856   // UNHASHED_DYNSYMS.  Symbols which we do want to store we put into
 857   // HASHED_DYNSYMS.  DYNSYM_HASHVALS is parallel to HASHED_DYNSYMS,
 858   // and records the hash codes.
 859
 860   std::vector<Symbol*> unhashed_dynsyms;
 861   unhashed_dynsyms.reserve(count);
 862
 863   std::vector<Symbol*> hashed_dynsyms;
 864   hashed_dynsyms.reserve(count);
 865
 866   std::vector<uint32_t> dynsym_hashvals;
 867   dynsym_hashvals.reserve(count);
 868
 869   for (unsigned int i = 0; i < count; ++i)
 870     {
 871       Symbol* sym = dynsyms[i];
 872
 873       // FIXME: Should put on unhashed_dynsyms if the symbol is
 874       // hidden.
 875       if (sym->is_undefined())
 876         unhashed_dynsyms.push_back(sym);
 877       else
 878         {
 879           hashed_dynsyms.push_back(sym);
 880           dynsym_hashvals.push_back(Dynobj::gnu_hash(sym->name()));
 881         }
 882     }
 883
 884   // Put the unhashed symbols at the start of the global portion of
 885   // the dynamic symbol table.
 886   const unsigned int unhashed_count = unhashed_dynsyms.size();
 887   unsigned int unhashed_dynsym_index = local_dynsym_count;
 888   for (unsigned int i = 0; i < unhashed_count; ++i)
 889     {
 890       unhashed_dynsyms[i]->set_dynsym_index(unhashed_dynsym_index);
 891       ++unhashed_dynsym_index;
 892     }
 893
 894   // For the actual data generation we call out to a templatized
 895   // function.
 896   int size = parameters->get_size();
 897   bool big_endian = parameters->is_big_endian();
 898   if (size == 32)
 899     {
 900       if (big_endian)
 901         {
 902 #ifdef HAVE_TARGET_32_BIG
 903           Dynobj::sized_create_gnu_hash_table<32, true>(hashed_dynsyms,
 904                                                         dynsym_hashvals,
 905                                                         unhashed_dynsym_index,
 906                                                         pphash,
 907                                                         phashlen);
 908 #else
 909           gold_unreachable();
 910 #endif
 911         }
 912       else
 913         {
 914 #ifdef HAVE_TARGET_32_LITTLE
 915           Dynobj::sized_create_gnu_hash_table<32, false>(hashed_dynsyms,
 916                                                          dynsym_hashvals,
 917                                                          unhashed_dynsym_index,
 918                                                          pphash,
 919                                                          phashlen);
 920 #else
 921           gold_unreachable();
 922 #endif
 923         }
 924     }
 925   else if (size == 64)
 926     {
 927       if (big_endian)
 928         {
 929 #ifdef HAVE_TARGET_64_BIG
 930           Dynobj::sized_create_gnu_hash_table<64, true>(hashed_dynsyms,
 931                                                         dynsym_hashvals,
 932                                                         unhashed_dynsym_index,
 933                                                         pphash,
 934                                                         phashlen);
 935 #else
 936           gold_unreachable();
 937 #endif
 938         }
 939       else
 940         {
 941 #ifdef HAVE_TARGET_64_LITTLE
 942           Dynobj::sized_create_gnu_hash_table<64, false>(hashed_dynsyms,
 943                                                          dynsym_hashvals,
 944                                                          unhashed_dynsym_index,
 945                                                          pphash,
 946                                                          phashlen);
 947 #else
 948           gold_unreachable();
 949 #endif
 950         }
 951     }
 952   else
 953     gold_unreachable();
 954 }
 955
 956 // Create the actual data for a GNU hash table.  This is just a copy
 957 // of the code from the old GNU linker.
 958
 959 template<int size, bool big_endian>
 960 void
 961 Dynobj::sized_create_gnu_hash_table(
 962     const std::vector<Symbol*>& hashed_dynsyms,
 963     const std::vector<uint32_t>& dynsym_hashvals,
 964     unsigned int unhashed_dynsym_count,
 965     unsigned char** pphash,
 966     unsigned int* phashlen)
 967 {
 968   if (hashed_dynsyms.empty())
 969     {
 970       // Special case for the empty hash table.
 971       unsigned int hashlen = 5 * 4 + size / 8;
 972       unsigned char* phash = new unsigned char[hashlen];
 973       // One empty bucket.
 974       elfcpp::Swap<32, big_endian>::writeval(phash, 1);
 975       // Symbol index above unhashed symbols.
 976       elfcpp::Swap<32, big_endian>::writeval(phash + 4, unhashed_dynsym_count);
 977       // One word for bitmask.
 978       elfcpp::Swap<32, big_endian>::writeval(phash + 8, 1);
 979       // Only bloom filter.
 980       elfcpp::Swap<32, big_endian>::writeval(phash + 12, 0);
 981       // No valid hashes.
 982       elfcpp::Swap<size, big_endian>::writeval(phash + 16, 0);
 983       // No hashes in only bucket.
 984       elfcpp::Swap<32, big_endian>::writeval(phash + 16 + size / 8, 0);
 985
 986       *phashlen = hashlen;
 987       *pphash = phash;
 988
 989       return;
 990     }
 991
 992   const unsigned int bucketcount =
 993     Dynobj::compute_bucket_count(dynsym_hashvals, true);
 994
 995   const unsigned int nsyms = hashed_dynsyms.size();
 996
 997   uint32_t maskbitslog2 = 1;
 998   uint32_t x = nsyms >> 1;
 999   while (x != 0)
1000     {
1001       ++maskbitslog2;
1002       x >>= 1;
1003     }
1004   if (maskbitslog2 < 3)
1005     maskbitslog2 = 5;
1006   else if (((1U << (maskbitslog2 - 2)) & nsyms) != 0)
1007     maskbitslog2 += 3;
1008   else
1009     maskbitslog2 += 2;
1010
1011   uint32_t shift1;
1012   if (size == 32)
1013     shift1 = 5;
1014   else
1015     {
1016       if (maskbitslog2 == 5)
1017         maskbitslog2 = 6;
1018       shift1 = 6;
1019     }
1020   uint32_t mask = (1U << shift1) - 1U;
1021   uint32_t shift2 = maskbitslog2;
1022   uint32_t maskbits = 1U << maskbitslog2;
1023   uint32_t maskwords = 1U << (maskbitslog2 - shift1);
1024
1025   typedef typename elfcpp::Elf_types<size>::Elf_WXword Word;
1026   std::vector<Word> bitmask(maskwords);
1027   std::vector<uint32_t> counts(bucketcount);
1028   std::vector<uint32_t> indx(bucketcount);
1029   uint32_t symindx = unhashed_dynsym_count;
1030
1031   // Count the number of times each hash bucket is used.
1032   for (unsigned int i = 0; i < nsyms; ++i)
1033     ++counts[dynsym_hashvals[i] % bucketcount];
1034
1035   unsigned int cnt = symindx;
1036   for (unsigned int i = 0; i < bucketcount; ++i)
1037     {
1038       indx[i] = cnt;
1039       cnt += counts[i];
1040     }
1041
1042   unsigned int hashlen = (4 + bucketcount + nsyms) * 4;
1043   hashlen += maskbits / 8;
1044   unsigned char* phash = new unsigned char[hashlen];
1045
1046   elfcpp::Swap<32, big_endian>::writeval(phash, bucketcount);
1047   elfcpp::Swap<32, big_endian>::writeval(phash + 4, symindx);
1048   elfcpp::Swap<32, big_endian>::writeval(phash + 8, maskwords);
1049   elfcpp::Swap<32, big_endian>::writeval(phash + 12, shift2);
1050
1051   unsigned char* p = phash + 16 + maskbits / 8;
1052   for (unsigned int i = 0; i < bucketcount; ++i)
1053     {
1054       if (counts[i] == 0)
1055         elfcpp::Swap<32, big_endian>::writeval(p, 0);
1056       else
1057         elfcpp::Swap<32, big_endian>::writeval(p, indx[i]);
1058       p += 4;
1059     }
1060
1061   for (unsigned int i = 0; i < nsyms; ++i)
1062     {
1063       Symbol* sym = hashed_dynsyms[i];
1064       uint32_t hashval = dynsym_hashvals[i];
1065
1066       unsigned int bucket = hashval % bucketcount;
1067       unsigned int val = ((hashval >> shift1)
1068                           & ((maskbits >> shift1) - 1));
1069       bitmask[val] |= (static_cast<Word>(1U)) << (hashval & mask);
1070       bitmask[val] |= (static_cast<Word>(1U)) << ((hashval >> shift2) & mask);
1071       val = hashval & ~ 1U;
1072       if (counts[bucket] == 1)
1073         {
1074           // Last element terminates the chain.
1075           val |= 1;
1076         }
1077       elfcpp::Swap<32, big_endian>::writeval(p + (indx[bucket] - symindx) * 4,
1078                                              val);
1079       --counts[bucket];
1080
1081       sym->set_dynsym_index(indx[bucket]);
1082       ++indx[bucket];
1083     }
1084
1085   p = phash + 16;
1086   for (unsigned int i = 0; i < maskwords; ++i)
1087     {
1088       elfcpp::Swap<size, big_endian>::writeval(p, bitmask[i]);
1089       p += size / 8;
1090     }
1091
1092   *phashlen = hashlen;
1093   *pphash = phash;
1094 }
1095
1096 // Verdef methods.
1097
1098 // Write this definition to a buffer for the output section.
1099
1100 template<int size, bool big_endian>
1101 unsigned char*
1102 Verdef::write(const Stringpool* dynpool, bool is_last, unsigned char* pb
1103               ACCEPT_SIZE_ENDIAN) const
1104 {
1105   const int verdef_size = elfcpp::Elf_sizes<size>::verdef_size;
1106   const int verdaux_size = elfcpp::Elf_sizes<size>::verdaux_size;
1107
1108   elfcpp::Verdef_write<size, big_endian> vd(pb);
1109   vd.set_vd_version(elfcpp::VER_DEF_CURRENT);
1110   vd.set_vd_flags((this->is_base_ ? elfcpp::VER_FLG_BASE : 0)
1111                   | (this->is_weak_ ? elfcpp::VER_FLG_WEAK : 0));
1112   vd.set_vd_ndx(this->index());
1113   vd.set_vd_cnt(1 + this->deps_.size());
1114   vd.set_vd_hash(Dynobj::elf_hash(this->name()));
1115   vd.set_vd_aux(verdef_size);
1116   vd.set_vd_next(is_last
1117                  ? 0
1118                  : verdef_size + (1 + this->deps_.size()) * verdaux_size);
1119   pb += verdef_size;
1120
1121   elfcpp::Verdaux_write<size, big_endian> vda(pb);
1122   vda.set_vda_name(dynpool->get_offset(this->name()));
1123   vda.set_vda_next(this->deps_.empty() ? 0 : verdaux_size);
1124   pb += verdaux_size;
1125
1126   Deps::const_iterator p;
1127   unsigned int i;
1128   for (p = this->deps_.begin(), i = 0;
1129        p != this->deps_.end();
1130        ++p, ++i)
1131     {
1132       elfcpp::Verdaux_write<size, big_endian> vda(pb);
1133       vda.set_vda_name(dynpool->get_offset(*p));
1134       vda.set_vda_next(i + 1 >= this->deps_.size() ? 0 : verdaux_size);
1135       pb += verdaux_size;
1136     }
1137
1138   return pb;
1139 }
1140
1141 // Verneed methods.
1142
1143 Verneed::~Verneed()
1144 {
1145   for (Need_versions::iterator p = this->need_versions_.begin();
1146        p != this->need_versions_.end();
1147        ++p)
1148     delete *p;
1149 }
1150
1151 // Add a new version to this file reference.
1152
1153 Verneed_version*
1154 Verneed::add_name(const char* name)
1155 {
1156   Verneed_version* vv = new Verneed_version(name);
1157   this->need_versions_.push_back(vv);
1158   return vv;
1159 }
1160
1161 // Set the version indexes starting at INDEX.
1162
1163 unsigned int
1164 Verneed::finalize(unsigned int index)
1165 {
1166   for (Need_versions::iterator p = this->need_versions_.begin();
1167        p != this->need_versions_.end();
1168        ++p)
1169     {
1170       (*p)->set_index(index);
1171       ++index;
1172     }
1173   return index;
1174 }
1175
1176 // Write this list of referenced versions to a buffer for the output
1177 // section.
1178
1179 template<int size, bool big_endian>
1180 unsigned char*
1181 Verneed::write(const Stringpool* dynpool, bool is_last,
1182                unsigned char* pb ACCEPT_SIZE_ENDIAN) const
1183 {
1184   const int verneed_size = elfcpp::Elf_sizes<size>::verneed_size;
1185   const int vernaux_size = elfcpp::Elf_sizes<size>::vernaux_size;
1186
1187   elfcpp::Verneed_write<size, big_endian> vn(pb);
1188   vn.set_vn_version(elfcpp::VER_NEED_CURRENT);
1189   vn.set_vn_cnt(this->need_versions_.size());
1190   vn.set_vn_file(dynpool->get_offset(this->filename()));
1191   vn.set_vn_aux(verneed_size);
1192   vn.set_vn_next(is_last
1193                  ? 0
1194                  : verneed_size + this->need_versions_.size() * vernaux_size);
1195   pb += verneed_size;
1196
1197   Need_versions::const_iterator p;
1198   unsigned int i;
1199   for (p = this->need_versions_.begin(), i = 0;
1200        p != this->need_versions_.end();
1201        ++p, ++i)
1202     {
1203       elfcpp::Vernaux_write<size, big_endian> vna(pb);
1204       vna.set_vna_hash(Dynobj::elf_hash((*p)->version()));
1205       // FIXME: We need to sometimes set VER_FLG_WEAK here.
1206       vna.set_vna_flags(0);
1207       vna.set_vna_other((*p)->index());
1208       vna.set_vna_name(dynpool->get_offset((*p)->version()));
1209       vna.set_vna_next(i + 1 >= this->need_versions_.size()
1210                        ? 0
1211                        : vernaux_size);
1212       pb += vernaux_size;
1213     }
1214
1215   return pb;
1216 }
1217
1218 // Versions methods.
1219
1220 Versions::~Versions()
1221 {
1222   for (Defs::iterator p = this->defs_.begin();
1223        p != this->defs_.end();
1224        ++p)
1225     delete *p;
1226
1227   for (Needs::iterator p = this->needs_.begin();
1228        p != this->needs_.end();
1229        ++p)
1230     delete *p;
1231 }
1232
1233 // Return the dynamic object which a symbol refers to.
1234
1235 Dynobj*
1236 Versions::get_dynobj_for_sym(const Symbol_table* symtab,
1237                              const Symbol* sym) const
1238 {
1239   if (sym->is_copied_from_dynobj())
1240     return symtab->get_copy_source(sym);
1241   else
1242     {
1243       Object* object = sym->object();
1244       gold_assert(object->is_dynamic());
1245       return static_cast<Dynobj*>(object);
1246     }
1247 }
1248
1249 // Record version information for a symbol going into the dynamic
1250 // symbol table.
1251
1252 void
1253 Versions::record_version(const Symbol_table* symtab,
1254                          Stringpool* dynpool, const Symbol* sym)
1255 {
1256   gold_assert(!this->is_finalized_);
1257   gold_assert(sym->version() != NULL);
1258
1259   Stringpool::Key version_key;
1260   const char* version = dynpool->add(sym->version(), false, &version_key);
1261
1262   if (!sym->is_from_dynobj() && !sym->is_copied_from_dynobj())
1263     {
1264       if (parameters->output_is_shared())
1265         this->add_def(sym, version, version_key);
1266     }
1267   else
1268     {
1269       // This is a version reference.
1270       Dynobj* dynobj = this->get_dynobj_for_sym(symtab, sym);
1271       this->add_need(dynpool, dynobj->soname(), version, version_key);
1272     }
1273 }
1274
1275 // We've found a symbol SYM defined in version VERSION.
1276
1277 void
1278 Versions::add_def(const Symbol* sym, const char* version,
1279                   Stringpool::Key version_key)
1280 {
1281   Key k(version_key, 0);
1282   Version_base* const vbnull = NULL;
1283   std::pair<Version_table::iterator, bool> ins =
1284     this->version_table_.insert(std::make_pair(k, vbnull));
1285
1286   if (!ins.second)
1287     {
1288       // We already have an entry for this version.
1289       Version_base* vb = ins.first->second;
1290
1291       // We have now seen a symbol in this version, so it is not
1292       // weak.
1293       vb->clear_weak();
1294
1295       // FIXME: When we support version scripts, we will need to
1296       // check whether this symbol should be forced local.
1297     }
1298   else
1299     {
1300       // If we are creating a shared object, it is an error to
1301       // find a definition of a symbol with a version which is not
1302       // in the version script.
1303       if (parameters->output_is_shared())
1304         {
1305           gold_error(_("symbol %s has undefined version %s"),
1306                      sym->demangled_name().c_str(), version);
1307           return;
1308         }
1309
1310       // If this is the first version we are defining, first define
1311       // the base version.  FIXME: Should use soname here when
1312       // creating a shared object.
1313       Verdef* vdbase = new Verdef(parameters->output_file_name(), true, false,
1314                                   true);
1315       this->defs_.push_back(vdbase);
1316
1317       // When creating a regular executable, automatically define
1318       // a new version.
1319       Verdef* vd = new Verdef(version, false, false, false);
1320       this->defs_.push_back(vd);
1321       ins.first->second = vd;
1322     }
1323 }
1324
1325 // Add a reference to version NAME in file FILENAME.
1326
1327 void
1328 Versions::add_need(Stringpool* dynpool, const char* filename, const char* name,
1329                    Stringpool::Key name_key)
1330 {
1331   Stringpool::Key filename_key;
1332   filename = dynpool->add(filename, true, &filename_key);
1333
1334   Key k(name_key, filename_key);
1335   Version_base* const vbnull = NULL;
1336   std::pair<Version_table::iterator, bool> ins =
1337     this->version_table_.insert(std::make_pair(k, vbnull));
1338
1339   if (!ins.second)
1340     {
1341       // We already have an entry for this filename/version.
1342       return;
1343     }
1344
1345   // See whether we already have this filename.  We don't expect many
1346   // version references, so we just do a linear search.  This could be
1347   // replaced by a hash table.
1348   Verneed* vn = NULL;
1349   for (Needs::iterator p = this->needs_.begin();
1350        p != this->needs_.end();
1351        ++p)
1352     {
1353       if ((*p)->filename() == filename)
1354         {
1355           vn = *p;
1356           break;
1357         }
1358     }
1359
1360   if (vn == NULL)
1361     {
1362       // We have a new filename.
1363       vn = new Verneed(filename);
1364       this->needs_.push_back(vn);
1365     }
1366
1367   ins.first->second = vn->add_name(name);
1368 }
1369
1370 // Set the version indexes.  Create a new dynamic version symbol for
1371 // each new version definition.
1372
1373 unsigned int
1374 Versions::finalize(const Target* target, Symbol_table* symtab,
1375                    unsigned int dynsym_index, std::vector<Symbol*>* syms)
1376 {
1377   gold_assert(!this->is_finalized_);
1378
1379   unsigned int vi = 1;
1380
1381   for (Defs::iterator p = this->defs_.begin();
1382        p != this->defs_.end();
1383        ++p)
1384     {
1385       (*p)->set_index(vi);
1386       ++vi;
1387
1388       // Create a version symbol if necessary.
1389       if (!(*p)->is_symbol_created())
1390         {
1391           Symbol* vsym = symtab->define_as_constant(target, (*p)->name(),
1392                                                     (*p)->name(), 0, 0,
1393                                                     elfcpp::STT_OBJECT,
1394                                                     elfcpp::STB_GLOBAL,
1395                                                     elfcpp::STV_DEFAULT, 0,
1396                                                     false);
1397           vsym->set_needs_dynsym_entry();
1398           vsym->set_dynsym_index(dynsym_index);
1399           ++dynsym_index;
1400           syms->push_back(vsym);
1401           // The name is already in the dynamic pool.
1402         }
1403     }
1404
1405   // Index 1 is used for global symbols.
1406   if (vi == 1)
1407     {
1408       gold_assert(this->defs_.empty());
1409       vi = 2;
1410     }
1411
1412   for (Needs::iterator p = this->needs_.begin();
1413        p != this->needs_.end();
1414        ++p)
1415     vi = (*p)->finalize(vi);
1416
1417   this->is_finalized_ = true;
1418
1419   return dynsym_index;
1420 }
1421
1422 // Return the version index to use for a symbol.  This does two hash
1423 // table lookups: one in DYNPOOL and one in this->version_table_.
1424 // Another approach alternative would be store a pointer in SYM, which
1425 // would increase the size of the symbol table.  Or perhaps we could
1426 // use a hash table from dynamic symbol pointer values to Version_base
1427 // pointers.
1428
1429 unsigned int
1430 Versions::version_index(const Symbol_table* symtab, const Stringpool* dynpool,
1431                         const Symbol* sym) const
1432 {
1433   Stringpool::Key version_key;
1434   const char* version = dynpool->find(sym->version(), &version_key);
1435   gold_assert(version != NULL);
1436
1437   Key k;
1438   if (!sym->is_from_dynobj() && !sym->is_copied_from_dynobj())
1439     {
1440       if (!parameters->output_is_shared())
1441         return elfcpp::VER_NDX_GLOBAL;
1442       k = Key(version_key, 0);
1443     }
1444   else
1445     {
1446       Dynobj* dynobj = this->get_dynobj_for_sym(symtab, sym);
1447
1448       Stringpool::Key filename_key;
1449       const char* filename = dynpool->find(dynobj->soname(), &filename_key);
1450       gold_assert(filename != NULL);
1451
1452       k = Key(version_key, filename_key);
1453     }
1454
1455   Version_table::const_iterator p = this->version_table_.find(k);
1456   gold_assert(p != this->version_table_.end());
1457
1458   return p->second->index();
1459 }
1460
1461 // Return an allocated buffer holding the contents of the symbol
1462 // version section.
1463
1464 template<int size, bool big_endian>
1465 void
1466 Versions::symbol_section_contents(const Symbol_table* symtab,
1467                                   const Stringpool* dynpool,
1468                                   unsigned int local_symcount,
1469                                   const std::vector<Symbol*>& syms,
1470                                   unsigned char** pp,
1471                                   unsigned int* psize
1472                                   ACCEPT_SIZE_ENDIAN) const
1473 {
1474   gold_assert(this->is_finalized_);
1475
1476   unsigned int sz = (local_symcount + syms.size()) * 2;
1477   unsigned char* pbuf = new unsigned char[sz];
1478
1479   for (unsigned int i = 0; i < local_symcount; ++i)
1480     elfcpp::Swap<16, big_endian>::writeval(pbuf + i * 2,
1481                                            elfcpp::VER_NDX_LOCAL);
1482
1483   for (std::vector<Symbol*>::const_iterator p = syms.begin();
1484        p != syms.end();
1485        ++p)
1486     {
1487       unsigned int version_index;
1488       const char* version = (*p)->version();
1489       if (version == NULL)
1490         version_index = elfcpp::VER_NDX_GLOBAL;
1491       else
1492         version_index = this->version_index(symtab, dynpool, *p);
1493       elfcpp::Swap<16, big_endian>::writeval(pbuf + (*p)->dynsym_index() * 2,
1494                                              version_index);
1495     }
1496
1497   *pp = pbuf;
1498   *psize = sz;
1499 }
1500
1501 // Return an allocated buffer holding the contents of the version
1502 // definition section.
1503
1504 template<int size, bool big_endian>
1505 void
1506 Versions::def_section_contents(const Stringpool* dynpool,
1507                                unsigned char** pp, unsigned int* psize,
1508                                unsigned int* pentries
1509                                ACCEPT_SIZE_ENDIAN) const
1510 {
1511   gold_assert(this->is_finalized_);
1512   gold_assert(!this->defs_.empty());
1513
1514   const int verdef_size = elfcpp::Elf_sizes<size>::verdef_size;
1515   const int verdaux_size = elfcpp::Elf_sizes<size>::verdaux_size;
1516
1517   unsigned int sz = 0;
1518   for (Defs::const_iterator p = this->defs_.begin();
1519        p != this->defs_.end();
1520        ++p)
1521     {
1522       sz += verdef_size + verdaux_size;
1523       sz += (*p)->count_dependencies() * verdaux_size;
1524     }
1525
1526   unsigned char* pbuf = new unsigned char[sz];
1527
1528   unsigned char* pb = pbuf;
1529   Defs::const_iterator p;
1530   unsigned int i;
1531   for (p = this->defs_.begin(), i = 0;
1532        p != this->defs_.end();
1533        ++p, ++i)
1534     pb = (*p)->write SELECT_SIZE_ENDIAN_NAME(size, big_endian)(
1535             dynpool, i + 1 >= this->defs_.size(), pb
1536             SELECT_SIZE_ENDIAN(size, big_endian));
1537
1538   gold_assert(static_cast<unsigned int>(pb - pbuf) == sz);
1539
1540   *pp = pbuf;
1541   *psize = sz;
1542   *pentries = this->defs_.size();
1543 }
1544
1545 // Return an allocated buffer holding the contents of the version
1546 // reference section.
1547
1548 template<int size, bool big_endian>
1549 void
1550 Versions::need_section_contents(const Stringpool* dynpool,
1551                                 unsigned char** pp, unsigned int *psize,
1552                                 unsigned int *pentries
1553                                 ACCEPT_SIZE_ENDIAN) const
1554 {
1555   gold_assert(this->is_finalized_);
1556   gold_assert(!this->needs_.empty());
1557
1558   const int verneed_size = elfcpp::Elf_sizes<size>::verneed_size;
1559   const int vernaux_size = elfcpp::Elf_sizes<size>::vernaux_size;
1560
1561   unsigned int sz = 0;
1562   for (Needs::const_iterator p = this->needs_.begin();
1563        p != this->needs_.end();
1564        ++p)
1565     {
1566       sz += verneed_size;
1567       sz += (*p)->count_versions() * vernaux_size;
1568     }
1569
1570   unsigned char* pbuf = new unsigned char[sz];
1571
1572   unsigned char* pb = pbuf;
1573   Needs::const_iterator p;
1574   unsigned int i;
1575   for (p = this->needs_.begin(), i = 0;
1576        p != this->needs_.end();
1577        ++p, ++i)
1578     pb = (*p)->write SELECT_SIZE_ENDIAN_NAME(size, big_endian)(
1579             dynpool, i + 1 >= this->needs_.size(), pb
1580             SELECT_SIZE_ENDIAN(size, big_endian));
1581
1582   gold_assert(static_cast<unsigned int>(pb - pbuf) == sz);
1583
1584   *pp = pbuf;
1585   *psize = sz;
1586   *pentries = this->needs_.size();
1587 }
1588
1589 // Instantiate the templates we need.  We could use the configure
1590 // script to restrict this to only the ones for implemented targets.
1591
1592 #ifdef HAVE_TARGET_32_LITTLE
1593 template
1594 class Sized_dynobj<32, false>;
1595 #endif
1596
1597 #ifdef HAVE_TARGET_32_BIG
1598 template
1599 class Sized_dynobj<32, true>;
1600 #endif
1601
1602 #ifdef HAVE_TARGET_64_LITTLE
1603 template
1604 class Sized_dynobj<64, false>;
1605 #endif
1606
1607 #ifdef HAVE_TARGET_64_BIG
1608 template
1609 class Sized_dynobj<64, true>;
1610 #endif
1611
1612 #ifdef HAVE_TARGET_32_LITTLE
1613 template
1614 void
1615 Versions::symbol_section_contents<32, false>(
1616     const Symbol_table*,
1617     const Stringpool*,
1618     unsigned int,
1619     const std::vector<Symbol*>&,
1620     unsigned char**,
1621     unsigned int*
1622     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, false)) const;
1623 #endif
1624
1625 #ifdef HAVE_TARGET_32_BIG
1626 template
1627 void
1628 Versions::symbol_section_contents<32, true>(
1629     const Symbol_table*,
1630     const Stringpool*,
1631     unsigned int,
1632     const std::vector<Symbol*>&,
1633     unsigned char**,
1634     unsigned int*
1635     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, true)) const;
1636 #endif
1637
1638 #ifdef HAVE_TARGET_64_LITTLE
1639 template
1640 void
1641 Versions::symbol_section_contents<64, false>(
1642     const Symbol_table*,
1643     const Stringpool*,
1644     unsigned int,
1645     const std::vector<Symbol*>&,
1646     unsigned char**,
1647     unsigned int*
1648     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, false)) const;
1649 #endif
1650
1651 #ifdef HAVE_TARGET_64_BIG
1652 template
1653 void
1654 Versions::symbol_section_contents<64, true>(
1655     const Symbol_table*,
1656     const Stringpool*,
1657     unsigned int,
1658     const std::vector<Symbol*>&,
1659     unsigned char**,
1660     unsigned int*
1661     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, true)) const;
1662 #endif
1663
1664 #ifdef HAVE_TARGET_32_LITTLE
1665 template
1666 void
1667 Versions::def_section_contents<32, false>(
1668     const Stringpool*,
1669     unsigned char**,
1670     unsigned int*,
1671     unsigned int*
1672     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, false)) const;
1673 #endif
1674
1675 #ifdef HAVE_TARGET_32_BIG
1676 template
1677 void
1678 Versions::def_section_contents<32, true>(
1679     const Stringpool*,
1680     unsigned char**,
1681     unsigned int*,
1682     unsigned int*
1683     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, true)) const;
1684 #endif
1685
1686 #ifdef HAVE_TARGET_64_LITTLE
1687 template
1688 void
1689 Versions::def_section_contents<64, false>(
1690     const Stringpool*,
1691     unsigned char**,
1692     unsigned int*,
1693     unsigned int*
1694     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, false)) const;
1695 #endif
1696
1697 #ifdef HAVE_TARGET_64_BIG
1698 template
1699 void
1700 Versions::def_section_contents<64, true>(
1701     const Stringpool*,
1702     unsigned char**,
1703     unsigned int*,
1704     unsigned int*
1705     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, true)) const;
1706 #endif
1707
1708 #ifdef HAVE_TARGET_32_LITTLE
1709 template
1710 void
1711 Versions::need_section_contents<32, false>(
1712     const Stringpool*,
1713     unsigned char**,
1714     unsigned int*,
1715     unsigned int*
1716     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, false)) const;
1717 #endif
1718
1719 #ifdef HAVE_TARGET_32_BIG
1720 template
1721 void
1722 Versions::need_section_contents<32, true>(
1723     const Stringpool*,
1724     unsigned char**,
1725     unsigned int*,
1726     unsigned int*
1727     ACCEPT_SIZE_ENDIAN_EXPLICIT(32, true)) const;
1728 #endif
1729
1730 #ifdef HAVE_TARGET_64_LITTLE
1731 template
1732 void
1733 Versions::need_section_contents<64, false>(
1734     const Stringpool*,
1735     unsigned char**,
1736     unsigned int*,
1737     unsigned int*
1738     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, false)) const;
1739 #endif
1740
1741 #ifdef HAVE_TARGET_64_BIG
1742 template
1743 void
1744 Versions::need_section_contents<64, true>(
1745     const Stringpool*,
1746     unsigned char**,
1747     unsigned int*,
1748     unsigned int*
1749     ACCEPT_SIZE_ENDIAN_EXPLICIT(64, true)) const;
1750 #endif
1751
1752 } // End namespace gold.