1 //===- SymbolTable.cpp ----------------------------------------------------===//
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 // Symbol table is a bag of all known symbols. We put all symbols of
11 // all input files to the symbol table. The symbol Table is basically
12 // a hash table with the logic to resolve symbol name conflicts using
13 // the symbol types.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "SymbolTable.h"
18 #include "Config.h"
19 #include "Error.h"
20 #include "Symbols.h"
21 
22 using namespace llvm;
23 using namespace llvm::object;
24 using namespace llvm::ELF;
25 
26 using namespace lld;
27 using namespace lld::elf2;
28 
29 template <class ELFT> SymbolTable<ELFT>::SymbolTable() {}
30 
31 template <class ELFT> bool SymbolTable<ELFT>::shouldUseRela() const {
32   ELFKind K = cast<ELFFileBase<ELFT>>(Config->FirstElf)->getELFKind();
33   return K == ELF64LEKind || K == ELF64BEKind;
34 }
35 
36 template <class ELFT>
37 void SymbolTable<ELFT>::addFile(std::unique_ptr<InputFile> File) {
38   checkCompatibility(File);
39 
40   if (auto *AF = dyn_cast<ArchiveFile>(File.get())) {
41     ArchiveFiles.emplace_back(std::move(File));
42     AF->parse();
43     for (Lazy &Sym : AF->getLazySymbols())
44       addLazy(&Sym);
45     return;
46   }
47 
48   if (auto *S = dyn_cast<SharedFile<ELFT>>(File.get())) {
49     S->parseSoName();
50     if (!IncludedSoNames.insert(S->getSoName()).second)
51       return;
52     S->parse();
53   } else {
54     cast<ObjectFile<ELFT>>(File.get())->parse(Comdats);
55   }
56   addELFFile(cast<ELFFileBase<ELFT>>(File.release()));
57 }
58 
59 template <class ELFT>
60 SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
61   auto *Sym = new (Alloc) Undefined<ELFT>(Name, Undefined<ELFT>::Required);
62   resolve(Sym);
63   return Sym;
64 }
65 
66 template <class ELFT>
67 SymbolBody *SymbolTable<ELFT>::addUndefinedOpt(StringRef Name) {
68   auto *Sym = new (Alloc) Undefined<ELFT>(Name, Undefined<ELFT>::Optional);
69   resolve(Sym);
70   return Sym;
71 }
72 
73 template <class ELFT>
74 void SymbolTable<ELFT>::addSyntheticSym(StringRef Name,
75                                         OutputSectionBase<ELFT> &Section,
76                                         typename ELFFile<ELFT>::uintX_t Value) {
77   typedef typename DefinedSynthetic<ELFT>::Elf_Sym Elf_Sym;
78   auto ESym = new (Alloc) Elf_Sym;
79   memset(ESym, 0, sizeof(Elf_Sym));
80   ESym->st_value = Value;
81   auto Sym = new (Alloc) DefinedSynthetic<ELFT>(Name, *ESym, Section);
82   resolve(Sym);
83 }
84 
85 template <class ELFT> void SymbolTable<ELFT>::addIgnoredSym(StringRef Name) {
86   auto Sym = new (Alloc)
87       DefinedAbsolute<ELFT>(Name, DefinedAbsolute<ELFT>::IgnoreUndef);
88   resolve(Sym);
89 }
90 
91 template <class ELFT> bool SymbolTable<ELFT>::isUndefined(StringRef Name) {
92   if (SymbolBody *Sym = find(Name))
93     return Sym->isUndefined();
94   return false;
95 }
96 
97 template <class ELFT>
98 void SymbolTable<ELFT>::addELFFile(ELFFileBase<ELFT> *File) {
99   if (auto *O = dyn_cast<ObjectFile<ELFT>>(File))
100     ObjectFiles.emplace_back(O);
101   else if (auto *S = dyn_cast<SharedFile<ELFT>>(File))
102     SharedFiles.emplace_back(S);
103 
104   if (auto *O = dyn_cast<ObjectFile<ELFT>>(File)) {
105     for (SymbolBody *Body : O->getSymbols())
106       resolve(Body);
107   }
108 
109   if (auto *S = dyn_cast<SharedFile<ELFT>>(File)) {
110     for (SharedSymbol<ELFT> &Body : S->getSharedSymbols())
111       resolve(&Body);
112   }
113 }
114 
115 template <class ELFT>
116 void SymbolTable<ELFT>::reportConflict(const Twine &Message,
117                                        const SymbolBody &Old,
118                                        const SymbolBody &New, bool Warning) {
119   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
120   typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
121 
122   const Elf_Sym &OldE = cast<ELFSymbolBody<ELFT>>(Old).Sym;
123   const Elf_Sym &NewE = cast<ELFSymbolBody<ELFT>>(New).Sym;
124   ELFFileBase<ELFT> *OldFile = nullptr;
125   ELFFileBase<ELFT> *NewFile = nullptr;
126 
127   for (const std::unique_ptr<ObjectFile<ELFT>> &File : ObjectFiles) {
128     Elf_Sym_Range Syms = File->getObj().symbols(File->getSymbolTable());
129     if (&OldE > Syms.begin() && &OldE < Syms.end())
130       OldFile = File.get();
131     if (&NewE > Syms.begin() && &NewE < Syms.end())
132       NewFile = File.get();
133   }
134 
135   std::string Msg = (Message + ": " + Old.getName() + " in " +
136                      OldFile->getName() + " and " + NewFile->getName())
137                         .str();
138   if (Warning)
139     warning(Msg);
140   else
141     error(Msg);
142 }
143 
144 // This function resolves conflicts if there's an existing symbol with
145 // the same name. Decisions are made based on symbol type.
146 template <class ELFT> void SymbolTable<ELFT>::resolve(SymbolBody *New) {
147   Symbol *Sym = insert(New);
148   if (Sym->Body == New)
149     return;
150 
151   SymbolBody *Existing = Sym->Body;
152 
153   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
154     if (New->isUndefined()) {
155       if (New->isWeak()) {
156         // See the explanation in SymbolTable::addLazy
157         L->setUsedInRegularObj();
158         L->setWeak();
159         return;
160       }
161       addMemberFile(L);
162       return;
163     }
164 
165     // Found a definition for something also in an archive. Ignore the archive
166     // definition.
167     Sym->Body = New;
168     return;
169   }
170 
171   if (New->isTLS() != Existing->isTLS())
172     reportConflict("TLS attribute mismatch for symbol", *Existing, *New, false);
173 
174   // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
175   // equivalent (conflicting), or more preferable, respectively.
176   int comp = Existing->compare<ELFT>(New);
177   if (comp < 0)
178     Sym->Body = New;
179   else if (comp == 0)
180     reportConflict("duplicate symbol", *Existing, *New,
181                    Config->AllowMultipleDefinition);
182 }
183 
184 template <class ELFT> Symbol *SymbolTable<ELFT>::insert(SymbolBody *New) {
185   // Find an existing Symbol or create and insert a new one.
186   StringRef Name = New->getName();
187   Symbol *&Sym = Symtab[Name];
188   if (!Sym) {
189     Sym = new (Alloc) Symbol(New);
190     New->setBackref(Sym);
191     return Sym;
192   }
193   New->setBackref(Sym);
194   return Sym;
195 }
196 
197 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
198   auto It = Symtab.find(Name);
199   if (It == Symtab.end())
200     return nullptr;
201   return It->second->Body;
202 }
203 
204 template <class ELFT> void SymbolTable<ELFT>::addLazy(Lazy *New) {
205   Symbol *Sym = insert(New);
206   if (Sym->Body == New)
207     return;
208   SymbolBody *Existing = Sym->Body;
209   if (Existing->isDefined() || Existing->isLazy())
210     return;
211   Sym->Body = New;
212   assert(Existing->isUndefined() && "Unexpected symbol kind.");
213 
214   // Weak undefined symbols should not fetch members from archives.
215   // If we were to keep old symbol we would not know that an archive member was
216   // available if a strong undefined symbol shows up afterwards in the link.
217   // If a strong undefined symbol never shows up, this lazy symbol will
218   // get to the end of the link and must be treated as the weak undefined one.
219   // We set UsedInRegularObj in a similar way to what is done with shared
220   // symbols and mark it as weak to reduce how many special cases are needed.
221   if (Existing->isWeak()) {
222     New->setUsedInRegularObj();
223     New->setWeak();
224     return;
225   }
226   addMemberFile(New);
227 }
228 
229 template <class ELFT>
230 void SymbolTable<ELFT>::checkCompatibility(std::unique_ptr<InputFile> &File) {
231   auto *E = dyn_cast<ELFFileBase<ELFT>>(File.get());
232   if (!E)
233     return;
234   if (E->getELFKind() == Config->EKind && E->getEMachine() == Config->EMachine)
235     return;
236   StringRef A = E->getName();
237   StringRef B = Config->Emulation;
238   if (B.empty())
239     B = Config->FirstElf->getName();
240   error(A + " is incompatible with " + B);
241 }
242 
243 template <class ELFT> void SymbolTable<ELFT>::addMemberFile(Lazy *Body) {
244   // getMember returns nullptr if the member was already read from the library.
245   if (std::unique_ptr<InputFile> File = Body->getMember())
246     addFile(std::move(File));
247 }
248 
249 // This function takes care of the case in which shared libraries depend on
250 // the user program (not the other way, which is usual). Shared libraries
251 // may have undefined symbols, expecting that the user program provides
252 // the definitions for them. An example is BSD's __progname symbol.
253 // We need to put such symbols to the main program's .dynsym so that
254 // shared libraries can find them.
255 // Except this, we ignore undefined symbols in DSOs.
256 template <class ELFT> void SymbolTable<ELFT>::scanShlibUndefined() {
257   for (std::unique_ptr<SharedFile<ELFT>> &File : SharedFiles)
258     for (StringRef U : File->getUndefinedSymbols())
259       if (SymbolBody *Sym = find(U))
260         if (Sym->isDefined())
261           Sym->setUsedInDynamicReloc();
262 }
263 
264 template class lld::elf2::SymbolTable<ELF32LE>;
265 template class lld::elf2::SymbolTable<ELF32BE>;
266 template class lld::elf2::SymbolTable<ELF64LE>;
267 template class lld::elf2::SymbolTable<ELF64BE>;
268