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