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 ? OldFile->getName() : "(internal)") + " and " +
143                      (NewFile ? NewFile->getName() : "(internal)"))
144                         .str();
145   if (Warning)
146     warning(Msg);
147   else
148     error(Msg);
149 }
150 
151 // This function resolves conflicts if there's an existing symbol with
152 // the same name. Decisions are made based on symbol type.
153 template <class ELFT> void SymbolTable<ELFT>::resolve(SymbolBody *New) {
154   Symbol *Sym = insert(New);
155   if (Sym->Body == New)
156     return;
157 
158   SymbolBody *Existing = Sym->Body;
159 
160   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
161     if (New->isUndefined()) {
162       if (New->isWeak()) {
163         // See the explanation in SymbolTable::addLazy
164         L->setUsedInRegularObj();
165         L->setWeak();
166         return;
167       }
168       addMemberFile(L);
169       return;
170     }
171 
172     // Found a definition for something also in an archive. Ignore the archive
173     // definition.
174     Sym->Body = New;
175     return;
176   }
177 
178   if (New->isTLS() != Existing->isTLS())
179     reportConflict("TLS attribute mismatch for symbol", *Existing, *New, false);
180 
181   // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
182   // equivalent (conflicting), or more preferable, respectively.
183   int comp = Existing->compare<ELFT>(New);
184   if (comp < 0)
185     Sym->Body = New;
186   else if (comp == 0)
187     reportConflict("duplicate symbol", *Existing, *New,
188                    Config->AllowMultipleDefinition);
189 }
190 
191 template <class ELFT> Symbol *SymbolTable<ELFT>::insert(SymbolBody *New) {
192   // Find an existing Symbol or create and insert a new one.
193   StringRef Name = New->getName();
194   Symbol *&Sym = Symtab[Name];
195   if (!Sym) {
196     Sym = new (Alloc) Symbol(New);
197     New->setBackref(Sym);
198     return Sym;
199   }
200   New->setBackref(Sym);
201   return Sym;
202 }
203 
204 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
205   auto It = Symtab.find(Name);
206   if (It == Symtab.end())
207     return nullptr;
208   return It->second->Body;
209 }
210 
211 template <class ELFT> void SymbolTable<ELFT>::addLazy(Lazy *New) {
212   Symbol *Sym = insert(New);
213   if (Sym->Body == New)
214     return;
215   SymbolBody *Existing = Sym->Body;
216   if (Existing->isDefined() || Existing->isLazy())
217     return;
218   Sym->Body = New;
219   assert(Existing->isUndefined() && "Unexpected symbol kind.");
220 
221   // Weak undefined symbols should not fetch members from archives.
222   // If we were to keep old symbol we would not know that an archive member was
223   // available if a strong undefined symbol shows up afterwards in the link.
224   // If a strong undefined symbol never shows up, this lazy symbol will
225   // get to the end of the link and must be treated as the weak undefined one.
226   // We set UsedInRegularObj in a similar way to what is done with shared
227   // symbols and mark it as weak to reduce how many special cases are needed.
228   if (Existing->isWeak()) {
229     New->setUsedInRegularObj();
230     New->setWeak();
231     return;
232   }
233   addMemberFile(New);
234 }
235 
236 template <class ELFT>
237 void SymbolTable<ELFT>::checkCompatibility(std::unique_ptr<InputFile> &File) {
238   auto *E = dyn_cast<ELFFileBase<ELFT>>(File.get());
239   if (!E)
240     return;
241   if (E->getELFKind() == Config->EKind && E->getEMachine() == Config->EMachine)
242     return;
243   StringRef A = E->getName();
244   StringRef B = Config->Emulation;
245   if (B.empty())
246     B = Config->FirstElf->getName();
247   error(A + " is incompatible with " + B);
248 }
249 
250 template <class ELFT> void SymbolTable<ELFT>::addMemberFile(Lazy *Body) {
251   // getMember returns nullptr if the member was already read from the library.
252   if (std::unique_ptr<InputFile> File = Body->getMember())
253     addFile(std::move(File));
254 }
255 
256 // This function takes care of the case in which shared libraries depend on
257 // the user program (not the other way, which is usual). Shared libraries
258 // may have undefined symbols, expecting that the user program provides
259 // the definitions for them. An example is BSD's __progname symbol.
260 // We need to put such symbols to the main program's .dynsym so that
261 // shared libraries can find them.
262 // Except this, we ignore undefined symbols in DSOs.
263 template <class ELFT> void SymbolTable<ELFT>::scanShlibUndefined() {
264   for (std::unique_ptr<SharedFile<ELFT>> &File : SharedFiles)
265     for (StringRef U : File->getUndefinedSymbols())
266       if (SymbolBody *Sym = find(U))
267         if (Sym->isDefined())
268           Sym->setUsedInDynamicReloc();
269 }
270 
271 template class lld::elf2::SymbolTable<ELF32LE>;
272 template class lld::elf2::SymbolTable<ELF32BE>;
273 template class lld::elf2::SymbolTable<ELF64LE>;
274 template class lld::elf2::SymbolTable<ELF64BE>;
275