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 
15 using namespace llvm;
16 using namespace llvm::object;
17 
18 using namespace lld;
19 using namespace lld::elf2;
20 
21 SymbolTable::SymbolTable() {}
22 
23 bool SymbolTable::shouldUseRela() const {
24   ELFKind K = getFirstELF()->getELFKind();
25   return K == ELF64LEKind || K == ELF64BEKind;
26 }
27 
28 void SymbolTable::addFile(std::unique_ptr<InputFile> File) {
29   File->parse();
30   InputFile *FileP = File.release();
31   if (auto *AF = dyn_cast<ArchiveFile>(FileP)) {
32     ArchiveFiles.emplace_back(AF);
33     for (Lazy &Sym : AF->getLazySymbols())
34       addLazy(&Sym);
35     return;
36   }
37   addELFFile(cast<ELFFileBase>(FileP));
38 }
39 
40 template <class ELFT> void SymbolTable::init() {
41   if (Config->Shared)
42     return;
43   EntrySym = new (Alloc) Undefined<ELFT>("_start", Undefined<ELFT>::Synthetic);
44   resolve<ELFT>(EntrySym);
45 }
46 
47 template <class ELFT> void SymbolTable::addELFFile(ELFFileBase *File) {
48   if (const ELFFileBase *Old = getFirstELF()) {
49     if (!Old->isCompatibleWith(*File))
50       error(Twine(Old->getName() + " is incompatible with " + File->getName()));
51   } else {
52     init<ELFT>();
53   }
54 
55   if (auto *O = dyn_cast<ObjectFileBase>(File)) {
56     ObjectFiles.emplace_back(O);
57     for (SymbolBody *Body : O->getSymbols())
58       resolve<ELFT>(Body);
59   }
60 
61   if (auto *S = dyn_cast<SharedFile<ELFT>>(File)) {
62     SharedFiles.emplace_back(S);
63     for (SharedSymbol<ELFT> &Body : S->getSharedSymbols())
64       resolve<ELFT>(&Body);
65   }
66 }
67 
68 void SymbolTable::addELFFile(ELFFileBase *File) {
69   switch (File->getELFKind()) {
70   case ELF32LEKind:
71     addELFFile<ELF32LE>(File);
72     break;
73   case ELF32BEKind:
74     addELFFile<ELF32BE>(File);
75     break;
76   case ELF64LEKind:
77     addELFFile<ELF64LE>(File);
78     break;
79   case ELF64BEKind:
80     addELFFile<ELF64BE>(File);
81     break;
82   }
83 }
84 
85 // This function resolves conflicts if there's an existing symbol with
86 // the same name. Decisions are made based on symbol type.
87 template <class ELFT> void SymbolTable::resolve(SymbolBody *New) {
88   Symbol *Sym = insert(New);
89   if (Sym->Body == New)
90     return;
91 
92   SymbolBody *Existing = Sym->Body;
93 
94   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
95     if (New->isUndefined()) {
96       addMemberFile(L);
97       return;
98     }
99 
100     // Found a definition for something also in an archive. Ignore the archive
101     // definition.
102     Sym->Body = New;
103     return;
104   }
105 
106   // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
107   // equivalent (conflicting), or more preferable, respectively.
108   int comp = Existing->compare<ELFT>(New);
109   if (comp < 0)
110     Sym->Body = New;
111   if (comp == 0)
112     error(Twine("duplicate symbol: ") + Sym->Body->getName());
113 }
114 
115 Symbol *SymbolTable::insert(SymbolBody *New) {
116   // Find an existing Symbol or create and insert a new one.
117   StringRef Name = New->getName();
118   Symbol *&Sym = Symtab[Name];
119   if (!Sym) {
120     Sym = new (Alloc) Symbol(New);
121     New->setBackref(Sym);
122     return Sym;
123   }
124   New->setBackref(Sym);
125   return Sym;
126 }
127 
128 void SymbolTable::addLazy(Lazy *New) {
129   Symbol *Sym = insert(New);
130   if (Sym->Body == New)
131     return;
132   SymbolBody *Existing = Sym->Body;
133   if (Existing->isDefined() || Existing->isLazy())
134     return;
135   Sym->Body = New;
136   assert(Existing->isUndefined() && "Unexpected symbol kind.");
137   addMemberFile(New);
138 }
139 
140 void SymbolTable::addMemberFile(Lazy *Body) {
141   std::unique_ptr<InputFile> File = Body->getMember();
142 
143   // getMember returns nullptr if the member was already read from the library.
144   if (!File)
145     return;
146 
147   addFile(std::move(File));
148 }
149