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 152