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 #include "SymbolTable.h"
11 #include "Config.h"
12 #include "Error.h"
13 #include "Symbols.h"
14 #include "Target.h"
15 
16 using namespace llvm;
17 using namespace llvm::object;
18 using namespace llvm::ELF;
19 
20 using namespace lld;
21 using namespace lld::elf2;
22 
23 SymbolTable::SymbolTable() {}
24 
25 bool SymbolTable::shouldUseRela() const {
26   ELFKind K = getFirstELF()->getELFKind();
27   return K == ELF64LEKind || K == ELF64BEKind;
28 }
29 
30 void SymbolTable::addFile(std::unique_ptr<InputFile> File) {
31   if (auto *AF = dyn_cast<ArchiveFile>(File.get())) {
32     File.release();
33     ArchiveFiles.emplace_back(AF);
34     if (Config->WholeArchive) {
35       for (MemoryBufferRef &MBRef : AF->getMembers())
36         addFile(createELFFile<ObjectFile>(MBRef));
37       return;
38     }
39     AF->parse();
40     for (Lazy &Sym : AF->getLazySymbols())
41       addLazy(&Sym);
42     return;
43   }
44   if (auto *S = dyn_cast<SharedFileBase>(File.get())) {
45     S->parseSoName();
46     if (!IncludedSoNames.insert(S->getSoName()).second)
47       return;
48   }
49   File->parse();
50   addELFFile(cast<ELFFileBase>(File.release()));
51 }
52 
53 static TargetInfo *createTarget(uint16_t EMachine) {
54   switch (EMachine) {
55   case EM_386:
56     return new X86TargetInfo();
57   case EM_AARCH64:
58     return new AArch64TargetInfo();
59   case EM_ARM:
60     return new ARMTargetInfo();
61   case EM_MIPS:
62     return new MipsTargetInfo();
63   case EM_PPC:
64     return new PPCTargetInfo();
65   case EM_PPC64:
66     return new PPC64TargetInfo();
67   case EM_X86_64:
68     return new X86_64TargetInfo();
69   }
70   error("Unknown target machine");
71 }
72 
73 void SymbolTable::addUndefinedSym(StringRef Name) {
74   switch (getFirstELF()->getELFKind()) {
75   case ELF32LEKind:
76     addUndefinedSym<ELF32LE>(Name);
77     break;
78   case ELF32BEKind:
79     addUndefinedSym<ELF32BE>(Name);
80     break;
81   case ELF64LEKind:
82     addUndefinedSym<ELF64LE>(Name);
83     break;
84   case ELF64BEKind:
85     addUndefinedSym<ELF64BE>(Name);
86     break;
87   }
88 }
89 
90 template <class ELFT> void SymbolTable::addUndefinedSym(StringRef Name) {
91   Undefined<ELFT>::SyntheticOptional.setVisibility(STV_HIDDEN);
92   resolve<ELFT>(new (Alloc)
93                     Undefined<ELFT>(Name, Undefined<ELFT>::SyntheticOptional));
94 }
95 
96 template <class ELFT>
97 void SymbolTable::addSyntheticSym(StringRef Name, OutputSection<ELFT> &Section,
98                                   typename ELFFile<ELFT>::uintX_t Value) {
99   typedef typename DefinedSynthetic<ELFT>::Elf_Sym Elf_Sym;
100   auto ESym = new (Alloc) Elf_Sym;
101   memset(ESym, 0, sizeof(Elf_Sym));
102   ESym->st_value = Value;
103   auto Sym = new (Alloc) DefinedSynthetic<ELFT>(Name, *ESym, Section);
104   resolve<ELFT>(Sym);
105 }
106 
107 template <class ELFT> void SymbolTable::addIgnoredSym(StringRef Name) {
108   DefinedAbsolute<ELFT>::IgnoreUndef.setVisibility(STV_HIDDEN);
109   auto Sym = new (Alloc)
110       DefinedAbsolute<ELFT>(Name, DefinedAbsolute<ELFT>::IgnoreUndef);
111   resolve<ELFT>(Sym);
112 }
113 
114 template <class ELFT> void SymbolTable::init(uint16_t EMachine) {
115   Target.reset(createTarget(EMachine));
116   if (Config->Shared)
117     return;
118   EntrySym = new (Alloc) Undefined<ELFT>(
119       Config->Entry.empty() ? Target->getDefaultEntry() : Config->Entry,
120       Undefined<ELFT>::SyntheticRequired);
121   resolve<ELFT>(EntrySym);
122 
123   // In the assembly for 32 bit x86 the _GLOBAL_OFFSET_TABLE_ symbol is magical
124   // and is used to produce a R_386_GOTPC relocation.
125   // The R_386_GOTPC relocation value doesn't actually depend on the
126   // symbol value, so it could use an index of STN_UNDEF which, according to the
127   // spec, means the symbol value is 0.
128   // Unfortunately both gas and MC keep the _GLOBAL_OFFSET_TABLE_ symbol in
129   // the object file.
130   // The situation is even stranger on x86_64 where the assembly doesn't
131   // need the magical symbol, but gas still puts _GLOBAL_OFFSET_TABLE_ as
132   // an undefined symbol in the .o files.
133   // Given that the symbol is effectively unused, we just create a dummy
134   // hidden one to avoid the undefined symbol error.
135   addIgnoredSym<ELFT>("_GLOBAL_OFFSET_TABLE_");
136 }
137 
138 template <class ELFT> void SymbolTable::addELFFile(ELFFileBase *File) {
139   if (const ELFFileBase *Old = getFirstELF()) {
140     if (!Old->isCompatibleWith(*File))
141       error(Twine(Old->getName() + " is incompatible with " + File->getName()));
142   } else {
143     init<ELFT>(File->getEMachine());
144   }
145 
146   if (auto *O = dyn_cast<ObjectFileBase>(File)) {
147     ObjectFiles.emplace_back(O);
148     for (SymbolBody *Body : O->getSymbols())
149       resolve<ELFT>(Body);
150   }
151 
152   if (auto *S = dyn_cast<SharedFile<ELFT>>(File)) {
153     SharedFiles.emplace_back(S);
154     for (SharedSymbol<ELFT> &Body : S->getSharedSymbols())
155       resolve<ELFT>(&Body);
156   }
157 }
158 
159 void SymbolTable::addELFFile(ELFFileBase *File) {
160   switch (File->getELFKind()) {
161   case ELF32LEKind:
162     addELFFile<ELF32LE>(File);
163     break;
164   case ELF32BEKind:
165     addELFFile<ELF32BE>(File);
166     break;
167   case ELF64LEKind:
168     addELFFile<ELF64LE>(File);
169     break;
170   case ELF64BEKind:
171     addELFFile<ELF64BE>(File);
172     break;
173   }
174 }
175 
176 template <class ELFT>
177 void SymbolTable::dupError(const SymbolBody &Old, const SymbolBody &New) {
178   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
179   typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
180 
181   const Elf_Sym &OldE = cast<ELFSymbolBody<ELFT>>(Old).Sym;
182   const Elf_Sym &NewE = cast<ELFSymbolBody<ELFT>>(New).Sym;
183   ELFFileBase *OldFile = nullptr;
184   ELFFileBase *NewFile = nullptr;
185 
186   for (const std::unique_ptr<ObjectFileBase> &F : ObjectFiles) {
187     const auto &File = cast<ObjectFile<ELFT>>(*F);
188     Elf_Sym_Range Syms = File.getObj().symbols(File.getSymbolTable());
189     if (&OldE > Syms.begin() && &OldE < Syms.end())
190       OldFile = F.get();
191     if (&NewE > Syms.begin() && &NewE < Syms.end())
192       NewFile = F.get();
193   }
194 
195   std::string Msg = (Twine("duplicate symbol: ") + Old.getName() + " in " +
196                      OldFile->getName() + " and " + NewFile->getName())
197                         .str();
198   if (Config->AllowMultipleDefinition)
199     warning(Msg);
200   else
201     error(Msg);
202 }
203 
204 // This function resolves conflicts if there's an existing symbol with
205 // the same name. Decisions are made based on symbol type.
206 template <class ELFT> void SymbolTable::resolve(SymbolBody *New) {
207   Symbol *Sym = insert(New);
208   if (Sym->Body == New)
209     return;
210 
211   SymbolBody *Existing = Sym->Body;
212 
213   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
214     if (New->isUndefined()) {
215       addMemberFile(L);
216       return;
217     }
218 
219     // Found a definition for something also in an archive. Ignore the archive
220     // definition.
221     Sym->Body = New;
222     return;
223   }
224 
225   // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
226   // equivalent (conflicting), or more preferable, respectively.
227   int comp = Existing->compare<ELFT>(New);
228   if (comp < 0)
229     Sym->Body = New;
230   else if (comp == 0)
231     dupError<ELFT>(*Existing, *New);
232 }
233 
234 Symbol *SymbolTable::insert(SymbolBody *New) {
235   // Find an existing Symbol or create and insert a new one.
236   StringRef Name = New->getName();
237   Symbol *&Sym = Symtab[Name];
238   if (!Sym) {
239     Sym = new (Alloc) Symbol(New);
240     New->setBackref(Sym);
241     return Sym;
242   }
243   New->setBackref(Sym);
244   return Sym;
245 }
246 
247 void SymbolTable::addLazy(Lazy *New) {
248   Symbol *Sym = insert(New);
249   if (Sym->Body == New)
250     return;
251   SymbolBody *Existing = Sym->Body;
252   if (Existing->isDefined() || Existing->isLazy() || Existing->isWeak())
253     return;
254   Sym->Body = New;
255   assert(Existing->isUndefined() && "Unexpected symbol kind.");
256   addMemberFile(New);
257 }
258 
259 void SymbolTable::addMemberFile(Lazy *Body) {
260   std::unique_ptr<InputFile> File = Body->getMember();
261 
262   // getMember returns nullptr if the member was already read from the library.
263   if (!File)
264     return;
265 
266   addFile(std::move(File));
267 }
268 
269 namespace lld {
270 namespace elf2 {
271 template void SymbolTable::addSyntheticSym(StringRef, OutputSection<ELF32LE> &,
272                                            ELFFile<ELF32LE>::uintX_t);
273 template void SymbolTable::addSyntheticSym(StringRef, OutputSection<ELF32BE> &,
274                                            ELFFile<ELF32BE>::uintX_t);
275 template void SymbolTable::addSyntheticSym(StringRef, OutputSection<ELF64LE> &,
276                                            ELFFile<ELF64LE>::uintX_t);
277 template void SymbolTable::addSyntheticSym(StringRef, OutputSection<ELF64BE> &,
278                                            ELFFile<ELF64BE>::uintX_t);
279 
280 template void SymbolTable::addIgnoredSym<ELF32LE>(StringRef);
281 template void SymbolTable::addIgnoredSym<ELF32BE>(StringRef);
282 template void SymbolTable::addIgnoredSym<ELF64LE>(StringRef);
283 template void SymbolTable::addIgnoredSym<ELF64BE>(StringRef);
284 }
285 }
286