Hash tables, dynamic section, i386 PLT, gold_assert.
[platform/upstream/binutils.git] / 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.