Can now do a full static link of hello, world in C or C++
[external/binutils.git] / gold / symtab.h
1 // symtab.h -- the gold symbol table   -*- C++ -*-
2
3 // Symbol_table
4 //   The symbol table.
5
6 #include <string>
7 #include <utility>
8 #include <vector>
9 #include <cassert>
10
11 #include "elfcpp.h"
12 #include "stringpool.h"
13
14 #ifndef GOLD_SYMTAB_H
15 #define GOLD_SYMTAB_H
16
17 namespace gold
18 {
19
20 class Object;
21 class Output_data;
22 class Output_segment;
23 class Output_file;
24 class Target;
25
26 template<int size, bool big_endian>
27 class Sized_object;
28
29 // The base class of an entry in the symbol table.  The symbol table
30 // can have a lot of entries, so we don't want this class to big.
31 // Size dependent fields can be found in the template class
32 // Sized_symbol.  Targets may support their own derived classes.
33
34 class Symbol
35 {
36  public:
37   // Because we want the class to be small, we don't use any virtual
38   // functions.  But because symbols can be defined in different
39   // places, we need to classify them.  This enum is the different
40   // sources of symbols we support.
41   enum Source
42   {
43     // Symbol defined in an input file--this is the most common case.
44     FROM_OBJECT,
45     // Symbol defined in an Output_data, a special section created by
46     // the target.
47     IN_OUTPUT_DATA,
48     // Symbol defined in an Output_segment, with no associated
49     // section.
50     IN_OUTPUT_SEGMENT,
51     // Symbol value is constant.
52     CONSTANT
53   };
54
55   // When the source is IN_OUTPUT_SEGMENT, we need to describe what
56   // the offset means.
57   enum Segment_offset_base
58   {
59     // From the start of the segment.
60     SEGMENT_START,
61     // From the end of the segment.
62     SEGMENT_END,
63     // From the filesz of the segment--i.e., after the loaded bytes
64     // but before the bytes which are allocated but zeroed.
65     SEGMENT_BSS
66   };
67
68   // Return the symbol name.
69   const char*
70   name() const
71   { return this->name_; }
72
73   // Return the symbol version.  This will return NULL for an
74   // unversioned symbol.
75   const char*
76   version() const
77   { return this->version_; }
78
79   // Return the symbol source.
80   Source
81   source() const
82   { return this->source_; }
83
84   // Return the object with which this symbol is associated.
85   Object*
86   object() const
87   {
88     assert(this->source_ == FROM_OBJECT);
89     return this->u_.from_object.object;
90   }
91
92   // Return the index of the section in the input object file.
93   unsigned int
94   shnum() const
95   {
96     assert(this->source_ == FROM_OBJECT);
97     return this->u_.from_object.shnum;
98   }
99
100   // Return the output data section with which this symbol is
101   // associated, if the symbol was specially defined with respect to
102   // an output data section.
103   Output_data*
104   output_data() const
105   {
106     assert(this->source_ == IN_OUTPUT_DATA);
107     return this->u_.in_output_data.output_data;
108   }
109
110   // If this symbol was defined with respect to an output data
111   // section, return whether the value is an offset from end.
112   bool
113   offset_is_from_end() const
114   {
115     assert(this->source_ == IN_OUTPUT_DATA);
116     return this->u_.in_output_data.offset_is_from_end;
117   }
118
119   // Return the output segment with which this symbol is associated,
120   // if the symbol was specially defined with respect to an output
121   // segment.
122   Output_segment*
123   output_segment() const
124   {
125     assert(this->source_ == IN_OUTPUT_SEGMENT);
126     return this->u_.in_output_segment.output_segment;
127   }
128
129   // If this symbol was defined with respect to an output segment,
130   // return the offset base.
131   Segment_offset_base
132   offset_base() const
133   {
134     assert(this->source_ == IN_OUTPUT_SEGMENT);
135     return this->u_.in_output_segment.offset_base;
136   }
137
138   // Return the symbol binding.
139   elfcpp::STB
140   binding() const
141   { return this->binding_; }
142
143   // Return the symbol type.
144   elfcpp::STT
145   type() const
146   { return this->type_; }
147
148   // Return the symbol visibility.
149   elfcpp::STV
150   visibility() const
151   { return this->visibility_; }
152
153   // Return the non-visibility part of the st_other field.
154   unsigned char
155   nonvis() const
156   { return this->nonvis_; }
157
158   // Return whether this symbol is a forwarder.  This will never be
159   // true of a symbol found in the hash table, but may be true of
160   // symbol pointers attached to object files.
161   bool
162   is_forwarder() const
163   { return this->is_forwarder_; }
164
165   // Mark this symbol as a forwarder.
166   void
167   set_forwarder()
168   { this->is_forwarder_ = true; }
169
170   // Return whether this symbol was seen in a dynamic object.
171   bool
172   in_dyn() const
173   { return this->in_dyn_; }
174
175   // Mark this symbol as seen in a dynamic object.
176   void
177   set_in_dyn()
178   { this->in_dyn_ = true; }
179
180   // Return whether this symbol has an entry in the GOT section.
181   bool
182   has_got_offset() const
183   { return this->has_got_offset_; }
184
185   // Return the offset into the GOT section of this symbol.
186   unsigned int
187   got_offset() const
188   {
189     assert(this->has_got_offset());
190     return this->got_offset_;
191   }
192
193   // Set the GOT offset of this symbol.
194   void
195   set_got_offset(unsigned int got_offset)
196   {
197     this->has_got_offset_ = true;
198     this->got_offset_ = got_offset;
199   }
200
201   // Return whether this symbol is resolved locally.  This is always
202   // true when linking statically.  It is true for a symbol defined in
203   // this object when using -Bsymbolic.  It is true for a symbol
204   // marked local in a version file.  FIXME: This needs to be
205   // completed.
206   bool
207   is_resolved_locally() const
208   { return !this->in_dyn_; }
209
210   // Return whether this is an undefined symbol.
211   bool
212   is_undefined() const
213   {
214     return this->source_ == FROM_OBJECT && this->shnum() == elfcpp::SHN_UNDEF;
215   }
216
217   // Return whether this is a common symbol.
218   bool
219   is_common() const
220   {
221     return this->source_ == FROM_OBJECT && this->shnum() == elfcpp::SHN_COMMON;
222   }
223
224  protected:
225   // Instances of this class should always be created at a specific
226   // size.
227   Symbol()
228   { }
229
230   // Initialize the general fields.
231   void
232   init_fields(const char* name, const char* version,
233               elfcpp::STT type, elfcpp::STB binding,
234               elfcpp::STV visibility, unsigned char nonvis);
235
236   // Initialize fields from an ELF symbol in OBJECT.
237   template<int size, bool big_endian>
238   void
239   init_base(const char *name, const char* version, Object* object,
240             const elfcpp::Sym<size, big_endian>&);
241
242   // Initialize fields for an Output_data.
243   void
244   init_base(const char* name, Output_data*, elfcpp::STT, elfcpp::STB,
245             elfcpp::STV, unsigned char nonvis, bool offset_is_from_end);
246
247   // Initialize fields for an Output_segment.
248   void
249   init_base(const char* name, Output_segment* os, elfcpp::STT type,
250             elfcpp::STB binding, elfcpp::STV visibility,
251             unsigned char nonvis, Segment_offset_base offset_base);
252
253   // Initialize fields for a constant.
254   void
255   init_base(const char* name, elfcpp::STT type, elfcpp::STB binding,
256             elfcpp::STV visibility, unsigned char nonvis);
257
258   // Override existing symbol.
259   template<int size, bool big_endian>
260   void
261   override_base(const elfcpp::Sym<size, big_endian>&, Object* object);
262
263  private:
264   Symbol(const Symbol&);
265   Symbol& operator=(const Symbol&);
266
267   // Symbol name (expected to point into a Stringpool).
268   const char* name_;
269   // Symbol version (expected to point into a Stringpool).  This may
270   // be NULL.
271   const char* version_;
272
273   union
274   {
275     // This struct is used if SOURCE_ == FROM_OBJECT.
276     struct
277     {
278       // Object in which symbol is defined, or in which it was first
279       // seen.
280       Object* object;
281       // Section number in object_ in which symbol is defined.
282       unsigned int shnum;
283     } from_object;
284
285     // This struct is used if SOURCE_ == IN_OUTPUT_DATA.
286     struct
287     {
288       // Output_data in which symbol is defined.  Before
289       // Layout::finalize the symbol's value is an offset within the
290       // Output_data.
291       Output_data* output_data;
292       // True if the offset is from the end, false if the offset is
293       // from the beginning.
294       bool offset_is_from_end;
295     } in_output_data;
296
297     // This struct is used if SOURCE_ == IN_OUTPUT_SEGMENT.
298     struct
299     {
300       // Output_segment in which the symbol is defined.  Before
301       // Layout::finalize the symbol's value is an offset.
302       Output_segment* output_segment;
303       // The base to use for the offset before Layout::finalize.
304       Segment_offset_base offset_base;
305     } in_output_segment;
306   } u_;
307
308   // If this symbol has an entry in the GOT section (has_got_offset_
309   // is true), this is the offset.
310   unsigned int got_offset_;
311   // Symbol type.
312   elfcpp::STT type_ : 4;
313   // Symbol binding.
314   elfcpp::STB binding_ : 4;
315   // Symbol visibility.
316   elfcpp::STV visibility_ : 2;
317   // Rest of symbol st_other field.
318   unsigned int nonvis_ : 6;
319   // The type of symbol.
320   Source source_ : 2;
321   // True if this symbol always requires special target-specific
322   // handling.
323   bool is_target_special_ : 1;
324   // True if this is the default version of the symbol.
325   bool is_def_ : 1;
326   // True if this symbol really forwards to another symbol.  This is
327   // used when we discover after the fact that two different entries
328   // in the hash table really refer to the same symbol.  This will
329   // never be set for a symbol found in the hash table, but may be set
330   // for a symbol found in the list of symbols attached to an Object.
331   // It forwards to the symbol found in the forwarders_ map of
332   // Symbol_table.
333   bool is_forwarder_ : 1;
334   // True if we've seen this symbol in a dynamic object.
335   bool in_dyn_ : 1;
336   // True if the symbol has an entry in the GOT section.
337   bool has_got_offset_ : 1;
338 };
339
340 // The parts of a symbol which are size specific.  Using a template
341 // derived class like this helps us use less space on a 32-bit system.
342
343 template<int size>
344 class Sized_symbol : public Symbol
345 {
346  public:
347   typedef typename elfcpp::Elf_types<size>::Elf_Addr Value_type;
348   typedef typename elfcpp::Elf_types<size>::Elf_WXword Size_type;
349
350   Sized_symbol()
351   { }
352
353   // Initialize fields from an ELF symbol in OBJECT.
354   template<bool big_endian>
355   void
356   init(const char *name, const char* version, Object* object,
357        const elfcpp::Sym<size, big_endian>&);
358
359   // Initialize fields for an Output_data.
360   void
361   init(const char* name, Output_data*, Value_type value, Size_type symsize,
362        elfcpp::STT, elfcpp::STB, elfcpp::STV, unsigned char nonvis,
363        bool offset_is_from_end);
364
365   // Initialize fields for an Output_segment.
366   void
367   init(const char* name, Output_segment*, Value_type value, Size_type symsize,
368        elfcpp::STT, elfcpp::STB, elfcpp::STV, unsigned char nonvis,
369        Segment_offset_base offset_base);
370
371   // Initialize fields for a constant.
372   void
373   init(const char* name, Value_type value, Size_type symsize,
374        elfcpp::STT, elfcpp::STB, elfcpp::STV, unsigned char nonvis);
375
376   // Override existing symbol.
377   template<bool big_endian>
378   void
379   override(const elfcpp::Sym<size, big_endian>&, Object* object);
380
381   // Return the symbol's value.
382   Value_type
383   value() const
384   { return this->value_; }
385
386   // Return the symbol's size (we can't call this 'size' because that
387   // is a template parameter).
388   Size_type
389   symsize() const
390   { return this->symsize_; }
391
392   // Set the symbol size.  This is used when resolving common symbols.
393   void
394   set_symsize(Size_type symsize)
395   { this->symsize_ = symsize; }
396
397   // Set the symbol value.  This is called when we store the final
398   // values of the symbols into the symbol table.
399   void
400   set_value(Value_type value)
401   { this->value_ = value; }
402
403  private:
404   Sized_symbol(const Sized_symbol&);
405   Sized_symbol& operator=(const Sized_symbol&);
406
407   // Symbol value.  Before Layout::finalize this is the offset in the
408   // input section.  This is set to the final value during
409   // Layout::finalize.
410   Value_type value_;
411   // Symbol size.
412   Size_type symsize_;
413 };
414
415 // A struct describing a symbol defined by the linker, where the value
416 // of the symbol is defined based on an output section.  This is used
417 // for symbols defined by the linker, like "_init_array_start".
418
419 struct Define_symbol_in_section
420 {
421   // The symbol name.
422   const char* name;
423   // The name of the output section with which this symbol should be
424   // associated.  If there is no output section with that name, the
425   // symbol will be defined as zero.
426   const char* output_section;
427   // The offset of the symbol within the output section.  This is an
428   // offset from the start of the output section, unless start_at_end
429   // is true, in which case this is an offset from the end of the
430   // output section.
431   uint64_t value;
432   // The size of the symbol.
433   uint64_t size;
434   // The symbol type.
435   elfcpp::STT type;
436   // The symbol binding.
437   elfcpp::STB binding;
438   // The symbol visibility.
439   elfcpp::STV visibility;
440   // The rest of the st_other field.
441   unsigned char nonvis;
442   // If true, the value field is an offset from the end of the output
443   // section.
444   bool offset_is_from_end;
445   // If true, this symbol is defined only if we see a reference to it.
446   bool only_if_ref;
447 };
448
449 // A struct describing a symbol defined by the linker, where the value
450 // of the symbol is defined based on a segment.  This is used for
451 // symbols defined by the linker, like "_end".  We describe the
452 // segment with which the symbol should be associated by its
453 // characteristics.  If no segment meets these characteristics, the
454 // symbol will be defined as zero.  If there is more than one segment
455 // which meets these characteristics, we will use the first one.
456
457 struct Define_symbol_in_segment
458 {
459   // The symbol name.
460   const char* name;
461   // The segment type where the symbol should be defined, typically
462   // PT_LOAD.
463   elfcpp::PT segment_type;
464   // Bitmask of segment flags which must be set.
465   elfcpp::PF segment_flags_set;
466   // Bitmask of segment flags which must be clear.
467   elfcpp::PF segment_flags_clear;
468   // The offset of the symbol within the segment.  The offset is
469   // calculated from the position set by offset_base.
470   uint64_t value;
471   // The size of the symbol.
472   uint64_t size;
473   // The symbol type.
474   elfcpp::STT type;
475   // The symbol binding.
476   elfcpp::STB binding;
477   // The symbol visibility.
478   elfcpp::STV visibility;
479   // The rest of the st_other field.
480   unsigned char nonvis;
481   // The base from which we compute the offset.
482   Symbol::Segment_offset_base offset_base;
483   // If true, this symbol is defined only if we see a reference to it.
484   bool only_if_ref;
485 };
486
487 // The main linker symbol table.
488
489 class Symbol_table
490 {
491  public:
492   Symbol_table();
493
494   ~Symbol_table();
495
496   // Add COUNT external symbols from OBJECT to the symbol table.  SYMS
497   // is the symbols, SYM_NAMES is their names, SYM_NAME_SIZE is the
498   // size of SYM_NAMES.  This sets SYMPOINTERS to point to the symbols
499   // in the symbol table.
500   template<int size, bool big_endian>
501   void
502   add_from_object(Sized_object<size, big_endian>* object,
503                   const elfcpp::Sym<size, big_endian>* syms,
504                   size_t count, const char* sym_names, size_t sym_name_size,
505                   Symbol** sympointers);
506
507   // Define a special symbol.
508   template<int size, bool big_endian>
509   Sized_symbol<size>*
510   define_special_symbol(Target* target, const char* name, bool only_if_ref);
511
512   // Define a special symbol based on an Output_data.  It is a
513   // multiple definition error if this symbol is already defined.
514   void
515   define_in_output_data(Target*, const char* name, Output_data*,
516                         uint64_t value, uint64_t symsize,
517                         elfcpp::STT type, elfcpp::STB binding,
518                         elfcpp::STV visibility, unsigned char nonvis,
519                         bool offset_is_from_end, bool only_if_ref);
520
521   // Define a special symbol based on an Output_segment.  It is a
522   // multiple definition error if this symbol is already defined.
523   void
524   define_in_output_segment(Target*, const char* name, Output_segment*,
525                            uint64_t value, uint64_t symsize,
526                            elfcpp::STT type, elfcpp::STB binding,
527                            elfcpp::STV visibility, unsigned char nonvis,
528                            Symbol::Segment_offset_base, bool only_if_ref);
529
530   // Define a special symbol with a constant value.  It is a multiple
531   // definition error if this symbol is already defined.
532   void
533   define_as_constant(Target*, const char* name, uint64_t value,
534                      uint64_t symsize, elfcpp::STT type, elfcpp::STB binding,
535                      elfcpp::STV visibility, unsigned char nonvis,
536                      bool only_if_ref);
537
538   // Define a set of symbols in output sections.
539   void
540   define_symbols(const Layout*, Target*, int count,
541                  const Define_symbol_in_section*);
542
543   // Define a set of symbols in output segments.
544   void
545   define_symbols(const Layout*, Target*, int count,
546                  const Define_symbol_in_segment*);  
547
548   // Look up a symbol.
549   Symbol*
550   lookup(const char*, const char* version = NULL) const;
551
552   // Return the real symbol associated with the forwarder symbol FROM.
553   Symbol*
554   resolve_forwards(Symbol* from) const;
555
556   // Return the size of the symbols in the table.
557   int
558   get_size() const
559   { return this->size_; }
560
561   // Return the sized version of a symbol in this table.
562   template<int size>
563   Sized_symbol<size>*
564   get_sized_symbol(Symbol* ACCEPT_SIZE) const;
565
566   template<int size>
567   const Sized_symbol<size>*
568   get_sized_symbol(const Symbol* ACCEPT_SIZE) const;
569
570   // Return the count of undefined symbols seen.
571   int
572   saw_undefined() const
573   { return this->saw_undefined_; }
574
575   // Allocate the common symbols
576   void
577   allocate_commons(const General_options&, Layout*);
578
579   // Finalize the symbol table after we have set the final addresses
580   // of all the input sections.  This sets the final symbol values and
581   // adds the names to *POOL.  It records the file offset OFF, and
582   // returns the new file offset.
583   off_t
584   finalize(off_t, Stringpool*);
585
586   // Write out the global symbols.
587   void
588   write_globals(const Target*, const Stringpool*, Output_file*) const;
589
590  private:
591   Symbol_table(const Symbol_table&);
592   Symbol_table& operator=(const Symbol_table&);
593
594   // Set the size of the symbols in the table.
595   void
596   set_size(int size)
597   { this->size_ = size; }
598
599   // Make FROM a forwarder symbol to TO.
600   void
601   make_forwarder(Symbol* from, Symbol* to);
602
603   // Add a symbol.
604   template<int size, bool big_endian>
605   Symbol*
606   add_from_object(Sized_object<size, big_endian>*, const char *name,
607                   const char *version, bool def,
608                   const elfcpp::Sym<size, big_endian>& sym);
609
610   // Resolve symbols.
611   template<int size, bool big_endian>
612   static void
613   resolve(Sized_symbol<size>* to,
614           const elfcpp::Sym<size, big_endian>& sym,
615           Object*);
616
617   template<int size, bool big_endian>
618   static void
619   resolve(Sized_symbol<size>* to, const Sized_symbol<size>* from
620           ACCEPT_SIZE_ENDIAN);
621
622   // Define a symbol in an Output_data, sized version.
623   template<int size>
624   void
625   do_define_in_output_data(Target*, const char* name, Output_data*,
626                            typename elfcpp::Elf_types<size>::Elf_Addr value,
627                            typename elfcpp::Elf_types<size>::Elf_WXword ssize,
628                            elfcpp::STT type, elfcpp::STB binding,
629                            elfcpp::STV visibility, unsigned char nonvis,
630                            bool offset_is_from_end, bool only_if_ref);
631
632   // Define a symbol in an Output_segment, sized version.
633   template<int size>
634   void
635   do_define_in_output_segment(
636     Target*, const char* name, Output_segment* os,
637     typename elfcpp::Elf_types<size>::Elf_Addr value,
638     typename elfcpp::Elf_types<size>::Elf_WXword ssize,
639     elfcpp::STT type, elfcpp::STB binding,
640     elfcpp::STV visibility, unsigned char nonvis,
641     Symbol::Segment_offset_base offset_base, bool only_if_ref);
642
643   // Define a symbol as a constant, sized version.
644   template<int size>
645   void
646   do_define_as_constant(
647     Target*, const char* name,
648     typename elfcpp::Elf_types<size>::Elf_Addr value,
649     typename elfcpp::Elf_types<size>::Elf_WXword ssize,
650     elfcpp::STT type, elfcpp::STB binding,
651     elfcpp::STV visibility, unsigned char nonvis,
652     bool only_if_ref);
653
654   // Allocate the common symbols, sized version.
655   template<int size>
656   void
657   do_allocate_commons(const General_options&, Layout*);
658
659   // Finalize symbols specialized for size.
660   template<int size>
661   off_t
662   sized_finalize(off_t, Stringpool*);
663
664   // Write globals specialized for size and endianness.
665   template<int size, bool big_endian>
666   void
667   sized_write_globals(const Target*, const Stringpool*, Output_file*) const;
668
669   // The type of the symbol hash table.
670
671   typedef std::pair<const char*, const char*> Symbol_table_key;
672
673   struct Symbol_table_hash
674   {
675     size_t
676     operator()(const Symbol_table_key&) const;
677   };
678
679   struct Symbol_table_eq
680   {
681     bool
682     operator()(const Symbol_table_key&, const Symbol_table_key&) const;
683   };
684
685   typedef Unordered_map<Symbol_table_key, Symbol*, Symbol_table_hash,
686                         Symbol_table_eq> Symbol_table_type;
687
688   // The type of the list of common symbols.
689
690   typedef std::vector<Symbol*> Commons_type;
691
692   // The size of the symbols in the symbol table (32 or 64).
693   int size_;
694
695   // We increment this every time we see a new undefined symbol, for
696   // use in archive groups.
697   int saw_undefined_;
698
699   // The file offset within the output symtab section where we should
700   // write the table.
701   off_t offset_;
702
703   // The number of global symbols we want to write out.
704   size_t output_count_;
705
706   // The symbol hash table.
707   Symbol_table_type table_;
708
709   // A pool of symbol names.  This is used for all global symbols.
710   // Entries in the hash table point into this pool.
711   Stringpool namepool_;
712
713   // Forwarding symbols.
714   Unordered_map<Symbol*, Symbol*> forwarders_;
715
716   // We don't expect there to be very many common symbols, so we keep
717   // a list of them.  When we find a common symbol we add it to this
718   // list.  It is possible that by the time we process the list the
719   // symbol is no longer a common symbol.  It may also have become a
720   // forwarder.
721   Commons_type commons_;
722 };
723
724 // We inline get_sized_symbol for efficiency.
725
726 template<int size>
727 Sized_symbol<size>*
728 Symbol_table::get_sized_symbol(Symbol* sym ACCEPT_SIZE) const
729 {
730   assert(size == this->get_size());
731   return static_cast<Sized_symbol<size>*>(sym);
732 }
733
734 template<int size>
735 const Sized_symbol<size>*
736 Symbol_table::get_sized_symbol(const Symbol* sym ACCEPT_SIZE) const
737 {
738   assert(size == this->get_size());
739   return static_cast<const Sized_symbol<size>*>(sym);
740 }
741
742 } // End namespace gold.
743
744 #endif // !defined(GOLD_SYMTAB_H)