gold/dynobj.cc

   1 // dynobj.cc -- dynamic object support for gold
   2
   3 #include "gold.h"
   4
   5 #include <vector>
   6 #include <cstring>
   7
   8 #include "elfcpp.h"
   9 #include "symtab.h"
  10 #include "dynobj.h"
  11
  12 namespace gold
  13 {
  14
  15 // Class Dynobj.
  16
  17 // Return the string to use in a DT_NEEDED entry.
  18
  19 const char*
  20 Dynobj::soname() const
  21 {
  22   if (!this->soname_.empty())
  23     return this->soname_.c_str();
  24   return this->name().c_str();
  25 }
  26
  27 // Class Sized_dynobj.
  28
  29 template<int size, bool big_endian>
  30 Sized_dynobj<size, big_endian>::Sized_dynobj(
  31     const std::string& name,
  32     Input_file* input_file,
  33     off_t offset,
  34     const elfcpp::Ehdr<size, big_endian>& ehdr)
  35   : Dynobj(name, input_file, offset),
  36     elf_file_(this, ehdr)
  37 {
  38 }
  39
  40 // Set up the object.
  41
  42 template<int size, bool big_endian>
  43 void
  44 Sized_dynobj<size, big_endian>::setup(
  45     const elfcpp::Ehdr<size, big_endian>& ehdr)
  46 {
  47   this->set_target(ehdr.get_e_machine(), size, big_endian,
  48                    ehdr.get_e_ident()[elfcpp::EI_OSABI],
  49                    ehdr.get_e_ident()[elfcpp::EI_ABIVERSION]);
  50
  51   const unsigned int shnum = this->elf_file_.shnum();
  52   this->set_shnum(shnum);
  53 }
  54
  55 // Find the SHT_DYNSYM section and the various version sections, and
  56 // the dynamic section, given the section headers.
  57
  58 template<int size, bool big_endian>
  59 void
  60 Sized_dynobj<size, big_endian>::find_dynsym_sections(
  61     const unsigned char* pshdrs,
  62     unsigned int* pdynsym_shndx,
  63     unsigned int* pversym_shndx,
  64     unsigned int* pverdef_shndx,
  65     unsigned int* pverneed_shndx,
  66     unsigned int* pdynamic_shndx)
  67 {
  68   *pdynsym_shndx = -1U;
  69   *pversym_shndx = -1U;
  70   *pverdef_shndx = -1U;
  71   *pverneed_shndx = -1U;
  72   *pdynamic_shndx = -1U;
  73
  74   const unsigned int shnum = this->shnum();
  75   const unsigned char* p = pshdrs;
  76   for (unsigned int i = 0; i < shnum; ++i, p += This::shdr_size)
  77     {
  78       typename This::Shdr shdr(p);
  79
  80       unsigned int* pi;
  81       switch (shdr.get_sh_type())
  82         {
  83         case elfcpp::SHT_DYNSYM:
  84           pi = pdynsym_shndx;
  85           break;
  86         case elfcpp::SHT_GNU_versym:
  87           pi = pversym_shndx;
  88           break;
  89         case elfcpp::SHT_GNU_verdef:
  90           pi = pverdef_shndx;
  91           break;
  92         case elfcpp::SHT_GNU_verneed:
  93           pi = pverneed_shndx;
  94           break;
  95         case elfcpp::SHT_DYNAMIC:
  96           pi = pdynamic_shndx;
  97           break;
  98         default:
  99           pi = NULL;
 100           break;
 101         }
 102
 103       if (pi == NULL)
 104         continue;
 105
 106       if (*pi != -1U)
 107         {
 108           fprintf(stderr,
 109                   _("%s: %s: unexpected duplicate type %u section: %u, %u\n"),
 110                   program_name, this->name().c_str(), shdr.get_sh_type(),
 111                   *pi, i);
 112           gold_exit(false);
 113         }
 114
 115       *pi = i;
 116     }
 117 }
 118
 119 // Read the contents of section SHNDX.  PSHDRS points to the section
 120 // headers.  TYPE is the expected section type.  LINK is the expected
 121 // section link.  Store the data in *VIEW and *VIEW_SIZE.  The
 122 // section's sh_info field is stored in *VIEW_INFO.
 123
 124 template<int size, bool big_endian>
 125 void
 126 Sized_dynobj<size, big_endian>::read_dynsym_section(
 127     const unsigned char* pshdrs,
 128     unsigned int shndx,
 129     elfcpp::SHT type,
 130     unsigned int link,
 131     File_view** view,
 132     off_t* view_size,
 133     unsigned int* view_info)
 134 {
 135   if (shndx == -1U)
 136     {
 137       *view = NULL;
 138       *view_size = 0;
 139       *view_info = 0;
 140       return;
 141     }
 142
 143   typename This::Shdr shdr(pshdrs + shndx * This::shdr_size);
 144
 145   gold_assert(shdr.get_sh_type() == type);
 146
 147   if (shdr.get_sh_link() != link)
 148     {
 149       fprintf(stderr,
 150               _("%s: %s: unexpected link in section %u header: %u != %u\n"),
 151               program_name, this->name().c_str(), shndx,
 152               shdr.get_sh_link(), link);
 153       gold_exit(false);
 154     }
 155
 156   *view = this->get_lasting_view(shdr.get_sh_offset(), shdr.get_sh_size());
 157   *view_size = shdr.get_sh_size();
 158   *view_info = shdr.get_sh_info();
 159 }
 160
 161 // Set the soname field if this shared object has a DT_SONAME tag.
 162 // PSHDRS points to the section headers.  DYNAMIC_SHNDX is the section
 163 // index of the SHT_DYNAMIC section.  STRTAB_SHNDX, STRTAB, and
 164 // STRTAB_SIZE are the section index and contents of a string table
 165 // which may be the one associated with the SHT_DYNAMIC section.
 166
 167 template<int size, bool big_endian>
 168 void
 169 Sized_dynobj<size, big_endian>::set_soname(const unsigned char* pshdrs,
 170                                            unsigned int dynamic_shndx,
 171                                            unsigned int strtab_shndx,
 172                                            const unsigned char* strtabu,
 173                                            off_t strtab_size)
 174 {
 175   typename This::Shdr dynamicshdr(pshdrs + dynamic_shndx * This::shdr_size);
 176   gold_assert(dynamicshdr.get_sh_type() == elfcpp::SHT_DYNAMIC);
 177
 178   const off_t dynamic_size = dynamicshdr.get_sh_size();
 179   const unsigned char* pdynamic = this->get_view(dynamicshdr.get_sh_offset(),
 180                                                  dynamic_size);
 181
 182   const unsigned int link = dynamicshdr.get_sh_link();
 183   if (link != strtab_shndx)
 184     {
 185       if (link >= this->shnum())
 186         {
 187           fprintf(stderr,
 188                   _("%s: %s: DYNAMIC section %u link out of range: %u\n"),
 189                   program_name, this->name().c_str(),
 190                   dynamic_shndx, link);
 191           gold_exit(false);
 192         }
 193
 194       typename This::Shdr strtabshdr(pshdrs + link * This::shdr_size);
 195       if (strtabshdr.get_sh_type() != elfcpp::SHT_STRTAB)
 196         {
 197           fprintf(stderr,
 198                   _("%s: %s: DYNAMIC section %u link %u is not a strtab\n"),
 199                   program_name, this->name().c_str(),
 200                   dynamic_shndx, link);
 201           gold_exit(false);
 202         }
 203
 204       strtab_size = strtabshdr.get_sh_size();
 205       strtabu = this->get_view(strtabshdr.get_sh_offset(), strtab_size);
 206     }
 207
 208   for (const unsigned char* p = pdynamic;
 209        p < pdynamic + dynamic_size;
 210        p += This::dyn_size)
 211     {
 212       typename This::Dyn dyn(p);
 213
 214       if (dyn.get_d_tag() == elfcpp::DT_SONAME)
 215         {
 216           off_t val = dyn.get_d_val();
 217           if (val >= strtab_size)
 218             {
 219               fprintf(stderr,
 220                       _("%s: %s: DT_SONAME value out of range: "
 221                         "%lld >= %lld\n"),
 222                       program_name, this->name().c_str(),
 223                       static_cast<long long>(val),
 224                       static_cast<long long>(strtab_size));
 225               gold_exit(false);
 226             }
 227
 228           const char* strtab = reinterpret_cast<const char*>(strtabu);
 229           this->set_soname_string(strtab + val);
 230           return;
 231         }
 232
 233       if (dyn.get_d_tag() == elfcpp::DT_NULL)
 234         return;
 235     }
 236
 237   fprintf(stderr, _("%s: %s: missing DT_NULL in dynamic segment\n"),
 238           program_name, this->name().c_str());
 239   gold_exit(false);
 240 }
 241
 242 // Read the symbols and sections from a dynamic object.  We read the
 243 // dynamic symbols, not the normal symbols.
 244
 245 template<int size, bool big_endian>
 246 void
 247 Sized_dynobj<size, big_endian>::do_read_symbols(Read_symbols_data* sd)
 248 {
 249   this->read_section_data(&this->elf_file_, sd);
 250
 251   const unsigned char* const pshdrs = sd->section_headers->data();
 252
 253   unsigned int dynsym_shndx;
 254   unsigned int versym_shndx;
 255   unsigned int verdef_shndx;
 256   unsigned int verneed_shndx;
 257   unsigned int dynamic_shndx;
 258   this->find_dynsym_sections(pshdrs, &dynsym_shndx, &versym_shndx,
 259                              &verdef_shndx, &verneed_shndx, &dynamic_shndx);
 260
 261   unsigned int strtab_shndx = -1U;
 262
 263   if (dynsym_shndx == -1U)
 264     {
 265       sd->symbols = NULL;
 266       sd->symbols_size = 0;
 267       sd->symbol_names = NULL;
 268       sd->symbol_names_size = 0;
 269     }
 270   else
 271     {
 272       // Get the dynamic symbols.
 273       typename This::Shdr dynsymshdr(pshdrs + dynsym_shndx * This::shdr_size);
 274       gold_assert(dynsymshdr.get_sh_type() == elfcpp::SHT_DYNSYM);
 275
 276       sd->symbols = this->get_lasting_view(dynsymshdr.get_sh_offset(),
 277                                            dynsymshdr.get_sh_size());
 278       sd->symbols_size = dynsymshdr.get_sh_size();
 279
 280       // Get the symbol names.
 281       strtab_shndx = dynsymshdr.get_sh_link();
 282       if (strtab_shndx >= this->shnum())
 283         {
 284           fprintf(stderr,
 285                   _("%s: %s: invalid dynamic symbol table name index: %u\n"),
 286                   program_name, this->name().c_str(), strtab_shndx);
 287           gold_exit(false);
 288         }
 289       typename This::Shdr strtabshdr(pshdrs + strtab_shndx * This::shdr_size);
 290       if (strtabshdr.get_sh_type() != elfcpp::SHT_STRTAB)
 291         {
 292           fprintf(stderr,
 293                   _("%s: %s: dynamic symbol table name section "
 294                     "has wrong type: %u\n"),
 295                   program_name, this->name().c_str(),
 296                   static_cast<unsigned int>(strtabshdr.get_sh_type()));
 297           gold_exit(false);
 298         }
 299
 300       sd->symbol_names = this->get_lasting_view(strtabshdr.get_sh_offset(),
 301                                                 strtabshdr.get_sh_size());
 302       sd->symbol_names_size = strtabshdr.get_sh_size();
 303
 304       // Get the version information.
 305
 306       unsigned int dummy;
 307       this->read_dynsym_section(pshdrs, versym_shndx, elfcpp::SHT_GNU_versym,
 308                                 dynsym_shndx, &sd->versym, &sd->versym_size,
 309                                 &dummy);
 310
 311       // We require that the version definition and need section link
 312       // to the same string table as the dynamic symbol table.  This
 313       // is not a technical requirement, but it always happens in
 314       // practice.  We could change this if necessary.
 315
 316       this->read_dynsym_section(pshdrs, verdef_shndx, elfcpp::SHT_GNU_verdef,
 317                                 strtab_shndx, &sd->verdef, &sd->verdef_size,
 318                                 &sd->verdef_info);
 319
 320       this->read_dynsym_section(pshdrs, verneed_shndx, elfcpp::SHT_GNU_verneed,
 321                                 strtab_shndx, &sd->verneed, &sd->verneed_size,
 322                                 &sd->verneed_info);
 323     }
 324
 325   // Read the SHT_DYNAMIC section to find whether this shared object
 326   // has a DT_SONAME tag.  This doesn't really have anything to do
 327   // with reading the symbols, but this is a convenient place to do
 328   // it.
 329   if (dynamic_shndx != -1U)
 330     this->set_soname(pshdrs, dynamic_shndx, strtab_shndx,
 331                      (sd->symbol_names == NULL
 332                       ? NULL
 333                       : sd->symbol_names->data()),
 334                      sd->symbol_names_size);
 335 }
 336
 337 // Lay out the input sections for a dynamic object.  We don't want to
 338 // include sections from a dynamic object, so all that we actually do
 339 // here is check for .gnu.warning sections.
 340
 341 template<int size, bool big_endian>
 342 void
 343 Sized_dynobj<size, big_endian>::do_layout(const General_options&,
 344                                           Symbol_table* symtab,
 345                                           Layout*,
 346                                           Read_symbols_data* sd)
 347 {
 348   const unsigned int shnum = this->shnum();
 349   if (shnum == 0)
 350     return;
 351
 352   // Get the section headers.
 353   const unsigned char* pshdrs = sd->section_headers->data();
 354
 355   // Get the section names.
 356   const unsigned char* pnamesu = sd->section_names->data();
 357   const char* pnames = reinterpret_cast<const char*>(pnamesu);
 358
 359   // Skip the first, dummy, section.
 360   pshdrs += This::shdr_size;
 361   for (unsigned int i = 1; i < shnum; ++i, pshdrs += This::shdr_size)
 362     {
 363       typename This::Shdr shdr(pshdrs);
 364
 365       if (shdr.get_sh_name() >= sd->section_names_size)
 366         {
 367           fprintf(stderr,
 368                   _("%s: %s: bad section name offset for section %u: %lu\n"),
 369                   program_name, this->name().c_str(), i,
 370                   static_cast<unsigned long>(shdr.get_sh_name()));
 371           gold_exit(false);
 372         }
 373
 374       const char* name = pnames + shdr.get_sh_name();
 375
 376       this->handle_gnu_warning_section(name, i, symtab);
 377     }
 378
 379   delete sd->section_headers;
 380   sd->section_headers = NULL;
 381   delete sd->section_names;
 382   sd->section_names = NULL;
 383 }
 384
 385 // Add an entry to the vector mapping version numbers to version
 386 // strings.
 387
 388 template<int size, bool big_endian>
 389 void
 390 Sized_dynobj<size, big_endian>::set_version_map(
 391     Version_map* version_map,
 392     unsigned int ndx,
 393     const char* name) const
 394 {
 395   gold_assert(ndx < version_map->size());
 396   if ((*version_map)[ndx] != NULL)
 397     {
 398       fprintf(stderr, _("%s: %s: duplicate definition for version %u\n"),
 399               program_name, this->name().c_str(), ndx);
 400       gold_exit(false);
 401     }
 402   (*version_map)[ndx] = name;
 403 }
 404
 405 // Create a vector mapping version numbers to version strings.
 406
 407 template<int size, bool big_endian>
 408 void
 409 Sized_dynobj<size, big_endian>::make_version_map(
 410     Read_symbols_data* sd,
 411     Version_map* version_map) const
 412 {
 413   if (sd->verdef == NULL && sd->verneed == NULL)
 414     return;
 415
 416   // First find the largest version index.
 417   unsigned int maxver = 0;
 418
 419   if (sd->verdef != NULL)
 420     {
 421       const unsigned char* pverdef = sd->verdef->data();
 422       off_t verdef_size = sd->verdef_size;
 423       const unsigned int count = sd->verdef_info;
 424
 425       const unsigned char* p = pverdef;
 426       for (unsigned int i = 0; i < count; ++i)
 427         {
 428           elfcpp::Verdef<size, big_endian> verdef(p);
 429
 430           const unsigned int vd_ndx = verdef.get_vd_ndx();
 431
 432           // The GNU linker clears the VERSYM_HIDDEN bit.  I'm not
 433           // sure why.
 434
 435           if (vd_ndx > maxver)
 436             maxver = vd_ndx;
 437
 438           const unsigned int vd_next = verdef.get_vd_next();
 439           if ((p - pverdef) + vd_next >= verdef_size)
 440             {
 441               fprintf(stderr,
 442                       _("%s: %s: verdef vd_next field out of range: %u\n"),
 443                       program_name, this->name().c_str(), vd_next);
 444               gold_exit(false);
 445             }
 446
 447           p += vd_next;
 448         }
 449     }
 450
 451   if (sd->verneed != NULL)
 452     {
 453       const unsigned char* pverneed = sd->verneed->data();
 454       off_t verneed_size = sd->verneed_size;
 455       const unsigned int count = sd->verneed_info;
 456
 457       const unsigned char* p = pverneed;
 458       for (unsigned int i = 0; i < count; ++i)
 459         {
 460           elfcpp::Verneed<size, big_endian> verneed(p);
 461
 462           const unsigned int vn_aux = verneed.get_vn_aux();
 463           if ((p - pverneed) + vn_aux >= verneed_size)
 464             {
 465               fprintf(stderr,
 466                       _("%s: %s: verneed vn_aux field out of range: %u\n"),
 467                       program_name, this->name().c_str(), vn_aux);
 468               gold_exit(false);
 469             }
 470
 471           const unsigned int vn_cnt = verneed.get_vn_cnt();
 472           const unsigned char* pvna = p + vn_aux;
 473           for (unsigned int j = 0; j < vn_cnt; ++j)
 474             {
 475               elfcpp::Vernaux<size, big_endian> vernaux(pvna);
 476
 477               const unsigned int vna_other = vernaux.get_vna_other();
 478               if (vna_other > maxver)
 479                 maxver = vna_other;
 480
 481               const unsigned int vna_next = vernaux.get_vna_next();
 482               if ((pvna - pverneed) + vna_next >= verneed_size)
 483                 {
 484                   fprintf(stderr,
 485                           _("%s: %s: verneed vna_next field "
 486                             "out of range: %u\n"),
 487                           program_name, this->name().c_str(), vna_next);
 488                   gold_exit(false);
 489                 }
 490
 491               pvna += vna_next;
 492             }
 493
 494           const unsigned int vn_next = verneed.get_vn_next();
 495           if ((p - pverneed) + vn_next >= verneed_size)
 496             {
 497               fprintf(stderr,
 498                       _("%s: %s: verneed vn_next field out of range: %u\n"),
 499                       program_name, this->name().c_str(), vn_next);
 500               gold_exit(false);
 501             }
 502
 503           p += vn_next;
 504         }
 505     }
 506
 507   // Now MAXVER is the largest version index we have seen.
 508
 509   version_map->resize(maxver + 1);
 510
 511   const char* names = reinterpret_cast<const char*>(sd->symbol_names->data());
 512   off_t names_size = sd->symbol_names_size;
 513
 514   if (sd->verdef != NULL)
 515     {
 516       const unsigned char* pverdef = sd->verdef->data();
 517       off_t verdef_size = sd->verdef_size;
 518       const unsigned int count = sd->verdef_info;
 519
 520       const unsigned char* p = pverdef;
 521       for (unsigned int i = 0; i < count; ++i)
 522         {
 523           elfcpp::Verdef<size, big_endian> verdef(p);
 524
 525           const unsigned int vd_cnt = verdef.get_vd_cnt();
 526           if (vd_cnt < 1)
 527             {
 528               fprintf(stderr, _("%s: %s: verdef vd_cnt field too small: %u\n"),
 529                       program_name, this->name().c_str(), vd_cnt);
 530               gold_exit(false);
 531             }
 532
 533           const unsigned int vd_aux = verdef.get_vd_aux();
 534           if ((p - pverdef) + vd_aux >= verdef_size)
 535             {
 536               fprintf(stderr,
 537                       _("%s: %s: verdef vd_aux field out of range: %u\n"),
 538                       program_name, this->name().c_str(), vd_aux);
 539               gold_exit(false);
 540             }
 541
 542           const unsigned char* pvda = p + vd_aux;
 543           elfcpp::Verdaux<size, big_endian> verdaux(pvda);
 544
 545           const unsigned int vda_name = verdaux.get_vda_name();
 546           if (vda_name >= names_size)
 547             {
 548               fprintf(stderr,
 549                       _("%s: %s: verdaux vda_name field out of range: %u\n"),
 550                       program_name, this->name().c_str(), vda_name);
 551               gold_exit(false);
 552             }
 553
 554           this->set_version_map(version_map, verdef.get_vd_ndx(),
 555                                 names + vda_name);
 556
 557           const unsigned int vd_next = verdef.get_vd_next();
 558           if ((p - pverdef) + vd_next >= verdef_size)
 559             {
 560               fprintf(stderr,
 561                       _("%s: %s: verdef vd_next field out of range: %u\n"),
 562                       program_name, this->name().c_str(), vd_next);
 563               gold_exit(false);
 564             }
 565
 566           p += vd_next;
 567         }
 568     }
 569
 570   if (sd->verneed != NULL)
 571     {
 572       const unsigned char* pverneed = sd->verneed->data();
 573       const unsigned int count = sd->verneed_info;
 574
 575       const unsigned char* p = pverneed;
 576       for (unsigned int i = 0; i < count; ++i)
 577         {
 578           elfcpp::Verneed<size, big_endian> verneed(p);
 579
 580           const unsigned int vn_aux = verneed.get_vn_aux();
 581           const unsigned int vn_cnt = verneed.get_vn_cnt();
 582           const unsigned char* pvna = p + vn_aux;
 583           for (unsigned int j = 0; j < vn_cnt; ++j)
 584             {
 585               elfcpp::Vernaux<size, big_endian> vernaux(pvna);
 586
 587               const unsigned int vna_name = vernaux.get_vna_name();
 588               if (vna_name >= names_size)
 589                 {
 590                   fprintf(stderr,
 591                           _("%s: %s: vernaux vna_name field "
 592                             "out of range: %u\n"),
 593                           program_name, this->name().c_str(), vna_name);
 594                   gold_exit(false);
 595                 }
 596
 597               this->set_version_map(version_map, vernaux.get_vna_other(),
 598                                     names + vna_name);
 599
 600               pvna += vernaux.get_vna_next();
 601             }
 602
 603           p += verneed.get_vn_next();
 604         }
 605     }
 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   if (symcount * sym_size != sd->symbols_size)
 626     {
 627       fprintf(stderr,
 628               _("%s: %s: size of dynamic symbols is not "
 629                 "multiple of symbol size\n"),
 630               program_name, this->name().c_str());
 631       gold_exit(false);
 632     }
 633
 634   Version_map version_map;
 635   this->make_version_map(sd, &version_map);
 636
 637   const char* sym_names =
 638     reinterpret_cast<const char*>(sd->symbol_names->data());
 639   symtab->add_from_dynobj(this, sd->symbols->data(), symcount,
 640                           sym_names, sd->symbol_names_size,
 641                           (sd->versym == NULL
 642                            ? NULL
 643                            : sd->versym->data()),
 644                           sd->versym_size,
 645                           &version_map);
 646
 647   delete sd->symbols;
 648   sd->symbols = NULL;
 649   delete sd->symbol_names;
 650   sd->symbol_names = NULL;
 651   if (sd->versym != NULL)
 652     {
 653       delete sd->versym;
 654       sd->versym = NULL;
 655     }
 656   if (sd->verdef != NULL)
 657     {
 658       delete sd->verdef;
 659       sd->verdef = NULL;
 660     }
 661   if (sd->verneed != NULL)
 662     {
 663       delete sd->verneed;
 664       sd->verneed = NULL;
 665     }
 666 }
 667
 668 // Given a vector of hash codes, compute the number of hash buckets to
 669 // use.
 670
 671 unsigned int
 672 Dynobj::compute_bucket_count(const std::vector<uint32_t>& hashcodes,
 673                              bool for_gnu_hash_table)
 674 {
 675   // FIXME: Implement optional hash table optimization.
 676
 677   // Array used to determine the number of hash table buckets to use
 678   // based on the number of symbols there are.  If there are fewer
 679   // than 3 symbols we use 1 bucket, fewer than 17 symbols we use 3
 680   // buckets, fewer than 37 we use 17 buckets, and so forth.  We never
 681   // use more than 32771 buckets.  This is straight from the old GNU
 682   // linker.
 683   static const unsigned int buckets[] =
 684   {
 685     1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031, 2053, 4099, 8209,
 686     16411, 32771
 687   };
 688   const int buckets_count = sizeof buckets / sizeof buckets[0];
 689
 690   unsigned int symcount = hashcodes.size();
 691   unsigned int ret = 1;
 692   for (int i = 0; i < buckets_count; ++i)
 693     {
 694       if (symcount < buckets[i])
 695         break;
 696       ret = buckets[i];
 697     }
 698
 699   if (for_gnu_hash_table && ret < 2)
 700     ret = 2;
 701
 702   return ret;
 703 }
 704
 705 // The standard ELF hash function.  This hash function must not
 706 // change, as the dynamic linker uses it also.
 707
 708 uint32_t
 709 Dynobj::elf_hash(const char* name)
 710 {
 711   const unsigned char* nameu = reinterpret_cast<const unsigned char*>(name);
 712   uint32_t h = 0;
 713   unsigned char c;
 714   while ((c = *nameu++) != '\0')
 715     {
 716       h = (h << 4) + c;
 717       uint32_t g = h & 0xf0000000;
 718       if (g != 0)
 719         {
 720           h ^= g >> 24;
 721           // The ELF ABI says h &= ~g, but using xor is equivalent in
 722           // this case (since g was set from h) and may save one
 723           // instruction.
 724           h ^= g;
 725         }
 726     }
 727   return h;
 728 }
 729
 730 // Create a standard ELF hash table, setting *PPHASH and *PHASHLEN.
 731 // DYNSYMS is a vector with all the global dynamic symbols.
 732 // LOCAL_DYNSYM_COUNT is the number of local symbols in the dynamic
 733 // symbol table.
 734
 735 void
 736 Dynobj::create_elf_hash_table(const Target* target,
 737                               const std::vector<Symbol*>& dynsyms,
 738                               unsigned int local_dynsym_count,
 739                               unsigned char** pphash,
 740                               unsigned int* phashlen)
 741 {
 742   unsigned int dynsym_count = dynsyms.size();
 743
 744   // Get the hash values for all the symbols.
 745   std::vector<uint32_t> dynsym_hashvals(dynsym_count);
 746   for (unsigned int i = 0; i < dynsym_count; ++i)
 747     dynsym_hashvals[i] = Dynobj::elf_hash(dynsyms[i]->name());
 748
 749   const unsigned int bucketcount =
 750     Dynobj::compute_bucket_count(dynsym_hashvals, false);
 751
 752   std::vector<uint32_t> bucket(bucketcount);
 753   std::vector<uint32_t> chain(local_dynsym_count + dynsym_count);
 754
 755   for (unsigned int i = 0; i < dynsym_count; ++i)
 756     {
 757       unsigned int dynsym_index = dynsyms[i]->dynsym_index();
 758       unsigned int bucketpos = dynsym_hashvals[i] % bucketcount;
 759       chain[dynsym_index] = bucket[bucketpos];
 760       bucket[bucketpos] = dynsym_index;
 761     }
 762
 763   unsigned int hashlen = ((2
 764                            + bucketcount
 765                            + local_dynsym_count
 766                            + dynsym_count)
 767                           * 4);
 768   unsigned char* phash = new unsigned char[hashlen];
 769
 770   if (target->is_big_endian())
 771     Dynobj::sized_create_elf_hash_table<true>(bucket, chain, phash, hashlen);
 772   else
 773     Dynobj::sized_create_elf_hash_table<false>(bucket, chain, phash, hashlen);
 774
 775   *pphash = phash;
 776   *phashlen = hashlen;
 777 }
 778
 779 // Fill in an ELF hash table.
 780
 781 template<bool big_endian>
 782 void
 783 Dynobj::sized_create_elf_hash_table(const std::vector<uint32_t>& bucket,
 784                                     const std::vector<uint32_t>& chain,
 785                                     unsigned char* phash,
 786                                     unsigned int hashlen)
 787 {
 788   unsigned char* p = phash;
 789
 790   const unsigned int bucketcount = bucket.size();
 791   const unsigned int chaincount = chain.size();
 792
 793   elfcpp::Swap<32, big_endian>::writeval(p, bucketcount);
 794   p += 4;
 795   elfcpp::Swap<32, big_endian>::writeval(p, chaincount);
 796   p += 4;
 797
 798   for (unsigned int i = 0; i < bucketcount; ++i)
 799     {
 800       elfcpp::Swap<32, big_endian>::writeval(p, bucket[i]);
 801       p += 4;
 802     }
 803
 804   for (unsigned int i = 0; i < chaincount; ++i)
 805     {
 806       elfcpp::Swap<32, big_endian>::writeval(p, chain[i]);
 807       p += 4;
 808     }
 809
 810   gold_assert(static_cast<unsigned int>(p - phash) == hashlen);
 811 }
 812
 813 // The hash function used for the GNU hash table.  This hash function
 814 // must not change, as the dynamic linker uses it also.
 815
 816 uint32_t
 817 Dynobj::gnu_hash(const char* name)
 818 {
 819   const unsigned char* nameu = reinterpret_cast<const unsigned char*>(name);
 820   uint32_t h = 5381;
 821   unsigned char c;
 822   while ((c = *nameu++) != '\0')
 823     h = (h << 5) + h + c;
 824   return h;
 825 }
 826
 827 // Create a GNU hash table, setting *PPHASH and *PHASHLEN.  GNU hash
 828 // tables are an extension to ELF which are recognized by the GNU
 829 // dynamic linker.  They are referenced using dynamic tag DT_GNU_HASH.
 830 // TARGET is the target.  DYNSYMS is a vector with all the global
 831 // symbols which will be going into the dynamic symbol table.
 832 // LOCAL_DYNSYM_COUNT is the number of local symbols in the dynamic
 833 // symbol table.
 834
 835 void
 836 Dynobj::create_gnu_hash_table(const Target* target,
 837                               const std::vector<Symbol*>& dynsyms,
 838                               unsigned int local_dynsym_count,
 839                               unsigned char** pphash,
 840                               unsigned int* phashlen)
 841 {
 842   const unsigned int count = dynsyms.size();
 843
 844   // Sort the dynamic symbols into two vectors.  Symbols which we do
 845   // not want to put into the hash table we store into
 846   // UNHASHED_DYNSYMS.  Symbols which we do want to store we put into
 847   // HASHED_DYNSYMS.  DYNSYM_HASHVALS is parallel to HASHED_DYNSYMS,
 848   // and records the hash codes.
 849
 850   std::vector<Symbol*> unhashed_dynsyms;
 851   unhashed_dynsyms.reserve(count);
 852
 853   std::vector<Symbol*> hashed_dynsyms;
 854   hashed_dynsyms.reserve(count);
 855
 856   std::vector<uint32_t> dynsym_hashvals;
 857   dynsym_hashvals.reserve(count);
 858
 859   for (unsigned int i = 0; i < count; ++i)
 860     {
 861       Symbol* sym = dynsyms[i];
 862
 863       // FIXME: Should put on unhashed_dynsyms if the symbol is
 864       // hidden.
 865       if (sym->is_undefined())
 866         unhashed_dynsyms.push_back(sym);
 867       else
 868         {
 869           hashed_dynsyms.push_back(sym);
 870           dynsym_hashvals.push_back(Dynobj::gnu_hash(sym->name()));
 871         }
 872     }
 873
 874   // Put the unhashed symbols at the start of the global portion of
 875   // the dynamic symbol table.
 876   const unsigned int unhashed_count = unhashed_dynsyms.size();
 877   unsigned int unhashed_dynsym_index = local_dynsym_count;
 878   for (unsigned int i = 0; i < unhashed_count; ++i)
 879     {
 880       unhashed_dynsyms[i]->set_dynsym_index(unhashed_dynsym_index);
 881       ++unhashed_dynsym_index;
 882     }
 883
 884   // For the actual data generation we call out to a templatized
 885   // function.
 886   int size = target->get_size();
 887   bool big_endian = target->is_big_endian();
 888   if (size == 32)
 889     {
 890       if (big_endian)
 891         Dynobj::sized_create_gnu_hash_table<32, true>(hashed_dynsyms,
 892                                                       dynsym_hashvals,
 893                                                       unhashed_dynsym_index,
 894                                                       pphash,
 895                                                       phashlen);
 896       else
 897         Dynobj::sized_create_gnu_hash_table<32, false>(hashed_dynsyms,
 898                                                        dynsym_hashvals,
 899                                                        unhashed_dynsym_index,
 900                                                        pphash,
 901                                                        phashlen);
 902     }
 903   else if (size == 64)
 904     {
 905       if (big_endian)
 906         Dynobj::sized_create_gnu_hash_table<64, true>(hashed_dynsyms,
 907                                                       dynsym_hashvals,
 908                                                       unhashed_dynsym_index,
 909                                                       pphash,
 910                                                       phashlen);
 911       else
 912         Dynobj::sized_create_gnu_hash_table<64, false>(hashed_dynsyms,
 913                                                        dynsym_hashvals,
 914                                                        unhashed_dynsym_index,
 915                                                        pphash,
 916                                                        phashlen);
 917     }
 918   else
 919     gold_unreachable();
 920 }
 921
 922 // Create the actual data for a GNU hash table.  This is just a copy
 923 // of the code from the old GNU linker.
 924
 925 template<int size, bool big_endian>
 926 void
 927 Dynobj::sized_create_gnu_hash_table(
 928     const std::vector<Symbol*>& hashed_dynsyms,
 929     const std::vector<uint32_t>& dynsym_hashvals,
 930     unsigned int unhashed_dynsym_count,
 931     unsigned char** pphash,
 932     unsigned int* phashlen)
 933 {
 934   if (hashed_dynsyms.empty())
 935     {
 936       // Special case for the empty hash table.
 937       unsigned int hashlen = 5 * 4 + size / 8;
 938       unsigned char* phash = new unsigned char[hashlen];
 939       // One empty bucket.
 940       elfcpp::Swap<32, big_endian>::writeval(phash, 1);
 941       // Symbol index above unhashed symbols.
 942       elfcpp::Swap<32, big_endian>::writeval(phash + 4, unhashed_dynsym_count);
 943       // One word for bitmask.
 944       elfcpp::Swap<32, big_endian>::writeval(phash + 8, 1);
 945       // Only bloom filter.
 946       elfcpp::Swap<32, big_endian>::writeval(phash + 12, 0);
 947       // No valid hashes.
 948       elfcpp::Swap<size, big_endian>::writeval(phash + 16, 0);
 949       // No hashes in only bucket.
 950       elfcpp::Swap<32, big_endian>::writeval(phash + 16 + size / 8, 0);
 951
 952       *phashlen = hashlen;
 953       *pphash = phash;
 954
 955       return;
 956     }
 957
 958   const unsigned int bucketcount =
 959     Dynobj::compute_bucket_count(dynsym_hashvals, true);
 960
 961   const unsigned int nsyms = hashed_dynsyms.size();
 962
 963   uint32_t maskbitslog2 = 1;
 964   uint32_t x = nsyms >> 1;
 965   while (x != 0)
 966     {
 967       ++maskbitslog2;
 968       x >>= 1;
 969     }
 970   if (maskbitslog2 < 3)
 971     maskbitslog2 = 5;
 972   else if (((1U << (maskbitslog2 - 2)) & nsyms) != 0)
 973     maskbitslog2 += 3;
 974   else
 975     maskbitslog2 += 2;
 976
 977   uint32_t shift1;
 978   if (size == 32)
 979     shift1 = 5;
 980   else
 981     {
 982       if (maskbitslog2 == 5)
 983         maskbitslog2 = 6;
 984       shift1 = 6;
 985     }
 986   uint32_t mask = (1U << shift1) - 1U;
 987   uint32_t shift2 = maskbitslog2;
 988   uint32_t maskbits = 1U << maskbitslog2;
 989   uint32_t maskwords = 1U << (maskbitslog2 - shift1);
 990
 991   typedef typename elfcpp::Elf_types<size>::Elf_WXword Word;
 992   std::vector<Word> bitmask(maskwords);
 993   std::vector<uint32_t> counts(bucketcount);
 994   std::vector<uint32_t> indx(bucketcount);
 995   uint32_t symindx = unhashed_dynsym_count;
 996
 997   // Count the number of times each hash bucket is used.
 998   for (unsigned int i = 0; i < nsyms; ++i)
 999     ++counts[dynsym_hashvals[i] % bucketcount];
1000
1001   unsigned int cnt = symindx;
1002   for (unsigned int i = 0; i < bucketcount; ++i)
1003     {
1004       indx[i] = cnt;
1005       cnt += counts[i];
1006     }
1007
1008   unsigned int hashlen = (4 + bucketcount + nsyms) * 4;
1009   hashlen += maskbits / 8;
1010   unsigned char* phash = new unsigned char[hashlen];
1011
1012   elfcpp::Swap<32, big_endian>::writeval(phash, bucketcount);
1013   elfcpp::Swap<32, big_endian>::writeval(phash + 4, symindx);
1014   elfcpp::Swap<32, big_endian>::writeval(phash + 8, maskwords);
1015   elfcpp::Swap<32, big_endian>::writeval(phash + 12, shift2);
1016
1017   unsigned char* p = phash + 16 + maskbits / 8;
1018   for (unsigned int i = 0; i < bucketcount; ++i)
1019     {
1020       if (counts[i] == 0)
1021         elfcpp::Swap<32, big_endian>::writeval(p, 0);
1022       else
1023         elfcpp::Swap<32, big_endian>::writeval(p, indx[i]);
1024       p += 4;
1025     }
1026
1027   for (unsigned int i = 0; i < nsyms; ++i)
1028     {
1029       Symbol* sym = hashed_dynsyms[i];
1030       uint32_t hashval = dynsym_hashvals[i];
1031
1032       unsigned int bucket = hashval % bucketcount;
1033       unsigned int val = ((hashval >> shift1)
1034                           & ((maskbits >> shift1) - 1));
1035       bitmask[val] |= (static_cast<Word>(1U)) << (hashval & mask);
1036       bitmask[val] |= (static_cast<Word>(1U)) << ((hashval >> shift2) & mask);
1037       val = hashval & ~ 1U;
1038       if (counts[bucket] == 1)
1039         {
1040           // Last element terminates the chain.
1041           val |= 1;
1042         }
1043       elfcpp::Swap<32, big_endian>::writeval(p + (indx[bucket] - symindx) * 4,
1044                                              val);
1045       --counts[bucket];
1046
1047       sym->set_dynsym_index(indx[bucket]);
1048       ++indx[bucket];
1049     }
1050
1051   p = phash + 16;
1052   for (unsigned int i = 0; i < maskwords; ++i)
1053     {
1054       elfcpp::Swap<size, big_endian>::writeval(p, bitmask[i]);
1055       p += size / 8;
1056     }
1057
1058   *phashlen = hashlen;
1059   *pphash = phash;
1060 }
1061
1062 // Instantiate the templates we need.  We could use the configure
1063 // script to restrict this to only the ones for implemented targets.
1064
1065 template
1066 class Sized_dynobj<32, false>;
1067
1068 template
1069 class Sized_dynobj<32, true>;
1070
1071 template
1072 class Sized_dynobj<64, false>;
1073
1074 template
1075 class Sized_dynobj<64, true>;
1076
1077 } // End namespace gold.