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