contrib/llvm/tools/lld/ELF/SymbolTable.h

   1 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLD_ELF_SYMBOL_TABLE_H
  11 #define LLD_ELF_SYMBOL_TABLE_H
  12
  13 #include "InputFiles.h"
  14 #include "LTO.h"
  15 #include "Strings.h"
  16 #include "llvm/ADT/CachedHashString.h"
  17 #include "llvm/ADT/DenseMap.h"
  18
  19 namespace lld {
  20 namespace elf {
  21 class Lazy;
  22 class OutputSectionBase;
  23 struct Symbol;
  24
  25 // SymbolTable is a bucket of all known symbols, including defined,
  26 // undefined, or lazy symbols (the last one is symbols in archive
  27 // files whose archive members are not yet loaded).
  28 //
  29 // We put all symbols of all files to a SymbolTable, and the
  30 // SymbolTable selects the "best" symbols if there are name
  31 // conflicts. For example, obviously, a defined symbol is better than
  32 // an undefined symbol. Or, if there's a conflict between a lazy and a
  33 // undefined, it'll read an archive member to read a real definition
  34 // to replace the lazy symbol. The logic is implemented in the
  35 // add*() functions, which are called by input files as they are parsed. There
  36 // is one add* function per symbol type.
  37 template <class ELFT> class SymbolTable {
  38   typedef typename ELFT::Sym Elf_Sym;
  39   typedef typename ELFT::uint uintX_t;
  40
  41 public:
  42   void addFile(InputFile *File);
  43   void addCombinedLTOObject();
  44
  45   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
  46   ArrayRef<ObjectFile<ELFT> *> getObjectFiles() const { return ObjectFiles; }
  47   ArrayRef<BinaryFile *> getBinaryFiles() const { return BinaryFiles; }
  48   ArrayRef<SharedFile<ELFT> *> getSharedFiles() const { return SharedFiles; }
  49
  50   DefinedRegular<ELFT> *addAbsolute(StringRef Name,
  51                                     uint8_t Visibility = llvm::ELF::STV_HIDDEN,
  52                                     uint8_t Binding = llvm::ELF::STB_GLOBAL);
  53   DefinedRegular<ELFT> *addIgnored(StringRef Name,
  54                                    uint8_t Visibility = llvm::ELF::STV_HIDDEN);
  55
  56   Symbol *addUndefined(StringRef Name);
  57   Symbol *addUndefined(StringRef Name, bool IsLocal, uint8_t Binding,
  58                        uint8_t StOther, uint8_t Type, bool CanOmitFromDynSym,
  59                        InputFile *File);
  60
  61   Symbol *addRegular(StringRef Name, uint8_t StOther, uint8_t Type,
  62                      uintX_t Value, uintX_t Size, uint8_t Binding,
  63                      InputSectionBase<ELFT> *Section, InputFile *File);
  64
  65   Symbol *addSynthetic(StringRef N, const OutputSectionBase *Section,
  66                        uintX_t Value, uint8_t StOther);
  67
  68   void addShared(SharedFile<ELFT> *F, StringRef Name, const Elf_Sym &Sym,
  69                  const typename ELFT::Verdef *Verdef);
  70
  71   void addLazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S);
  72   void addLazyObject(StringRef Name, LazyObjectFile &Obj);
  73   Symbol *addBitcode(StringRef Name, uint8_t Binding, uint8_t StOther,
  74                      uint8_t Type, bool CanOmitFromDynSym, BitcodeFile *File);
  75
  76   Symbol *addCommon(StringRef N, uint64_t Size, uint64_t Alignment,
  77                     uint8_t Binding, uint8_t StOther, uint8_t Type,
  78                     InputFile *File);
  79
  80   void scanUndefinedFlags();
  81   void scanShlibUndefined();
  82   void scanVersionScript();
  83
  84   SymbolBody *find(StringRef Name);
  85
  86   void trace(StringRef Name);
  87   void wrap(StringRef Name);
  88
  89   std::vector<InputSectionBase<ELFT> *> Sections;
  90
  91 private:
  92   std::pair<Symbol *, bool> insert(StringRef Name);
  93   std::pair<Symbol *, bool> insert(StringRef Name, uint8_t Type,
  94                                    uint8_t Visibility, bool CanOmitFromDynSym,
  95                                    InputFile *File);
  96
  97   std::vector<SymbolBody *> findByVersion(SymbolVersion Ver);
  98   std::vector<SymbolBody *> findAllByVersion(SymbolVersion Ver);
  99
 100   llvm::StringMap<std::vector<SymbolBody *>> &getDemangledSyms();
 101   void handleAnonymousVersion();
 102   void assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
 103                           StringRef VersionName);
 104   void assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId);
 105
 106   struct SymIndex {
 107     SymIndex(int Idx, bool Traced) : Idx(Idx), Traced(Traced) {}
 108     int Idx : 31;
 109     unsigned Traced : 1;
 110   };
 111
 112   // The order the global symbols are in is not defined. We can use an arbitrary
 113   // order, but it has to be reproducible. That is true even when cross linking.
 114   // The default hashing of StringRef produces different results on 32 and 64
 115   // bit systems so we use a map to a vector. That is arbitrary, deterministic
 116   // but a bit inefficient.
 117   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
 118   // once symbol resolution is finished.
 119   llvm::DenseMap<llvm::CachedHashStringRef, SymIndex> Symtab;
 120   std::vector<Symbol *> SymVector;
 121
 122   // Comdat groups define "link once" sections. If two comdat groups have the
 123   // same name, only one of them is linked, and the other is ignored. This set
 124   // is used to uniquify them.
 125   llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 126
 127   std::vector<ObjectFile<ELFT> *> ObjectFiles;
 128   std::vector<SharedFile<ELFT> *> SharedFiles;
 129   std::vector<BitcodeFile *> BitcodeFiles;
 130   std::vector<BinaryFile *> BinaryFiles;
 131
 132   // Set of .so files to not link the same shared object file more than once.
 133   llvm::DenseSet<StringRef> SoNames;
 134
 135   // A map from demangled symbol names to their symbol objects.
 136   // This mapping is 1:N because two symbols with different versions
 137   // can have the same name. We use this map to handle "extern C++ {}"
 138   // directive in version scripts.
 139   llvm::Optional<llvm::StringMap<std::vector<SymbolBody *>>> DemangledSyms;
 140
 141   // For LTO.
 142   std::unique_ptr<BitcodeCompiler> LTO;
 143 };
 144
 145 template <class ELFT> struct Symtab { static SymbolTable<ELFT> *X; };
 146 template <class ELFT> SymbolTable<ELFT> *Symtab<ELFT>::X;
 147
 148 } // namespace elf
 149 } // namespace lld
 150
 151 #endif