1 //===- Core/SymbolTable.cpp - Main Symbol Table ---------------------------===//
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 "lld/Core/SymbolTable.h"
11 #include "lld/Common/LLVM.h"
12 #include "lld/Core/AbsoluteAtom.h"
13 #include "lld/Core/Atom.h"
14 #include "lld/Core/DefinedAtom.h"
15 #include "lld/Core/File.h"
16 #include "lld/Core/LinkingContext.h"
17 #include "lld/Core/Resolver.h"
18 #include "lld/Core/SharedLibraryAtom.h"
19 #include "lld/Core/UndefinedAtom.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMapInfo.h"
22 #include "llvm/ADT/Hashing.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include <algorithm>
26 #include <cassert>
27 #include <cstdlib>
28 #include <vector>
29
30 namespace lld {
add(const UndefinedAtom & atom)31 bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
32
add(const SharedLibraryAtom & atom)33 bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
34
add(const AbsoluteAtom & atom)35 bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
36
add(const DefinedAtom & atom)37 bool SymbolTable::add(const DefinedAtom &atom) {
38 if (!atom.name().empty() &&
39 atom.scope() != DefinedAtom::scopeTranslationUnit) {
40 // Named atoms cannot be merged by content.
41 assert(atom.merge() != DefinedAtom::mergeByContent);
42 // Track named atoms that are not scoped to file (static).
43 return addByName(atom);
44 }
45 if (atom.merge() == DefinedAtom::mergeByContent) {
46 // Named atoms cannot be merged by content.
47 assert(atom.name().empty());
48 // Currently only read-only constants can be merged.
49 if (atom.permissions() == DefinedAtom::permR__)
50 return addByContent(atom);
51 // TODO: support mergeByContent of data atoms by comparing content & fixups.
52 }
53 return false;
54 }
55
56 enum NameCollisionResolution {
57 NCR_First,
58 NCR_Second,
59 NCR_DupDef,
60 NCR_DupUndef,
61 NCR_DupShLib,
62 NCR_Error
63 };
64
65 static NameCollisionResolution cases[4][4] = {
66 //regular absolute undef sharedLib
67 {
68 // first is regular
69 NCR_DupDef, NCR_Error, NCR_First, NCR_First
70 },
71 {
72 // first is absolute
73 NCR_Error, NCR_Error, NCR_First, NCR_First
74 },
75 {
76 // first is undef
77 NCR_Second, NCR_Second, NCR_DupUndef, NCR_Second
78 },
79 {
80 // first is sharedLib
81 NCR_Second, NCR_Second, NCR_First, NCR_DupShLib
82 }
83 };
84
collide(Atom::Definition first,Atom::Definition second)85 static NameCollisionResolution collide(Atom::Definition first,
86 Atom::Definition second) {
87 return cases[first][second];
88 }
89
90 enum MergeResolution {
91 MCR_First,
92 MCR_Second,
93 MCR_Largest,
94 MCR_SameSize,
95 MCR_Error
96 };
97
98 static MergeResolution mergeCases[][6] = {
99 // no tentative weak weakAddress sameNameAndSize largest
100 {MCR_Error, MCR_First, MCR_First, MCR_First, MCR_SameSize, MCR_Largest}, // no
101 {MCR_Second, MCR_Largest, MCR_Second, MCR_Second, MCR_SameSize, MCR_Largest}, // tentative
102 {MCR_Second, MCR_First, MCR_First, MCR_Second, MCR_SameSize, MCR_Largest}, // weak
103 {MCR_Second, MCR_First, MCR_First, MCR_First, MCR_SameSize, MCR_Largest}, // weakAddress
104 {MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize}, // sameSize
105 {MCR_Largest, MCR_Largest, MCR_Largest, MCR_Largest, MCR_SameSize, MCR_Largest}, // largest
106 };
107
mergeSelect(DefinedAtom::Merge first,DefinedAtom::Merge second)108 static MergeResolution mergeSelect(DefinedAtom::Merge first,
109 DefinedAtom::Merge second) {
110 assert(first != DefinedAtom::mergeByContent);
111 assert(second != DefinedAtom::mergeByContent);
112 return mergeCases[first][second];
113 }
114
addByName(const Atom & newAtom)115 bool SymbolTable::addByName(const Atom &newAtom) {
116 StringRef name = newAtom.name();
117 assert(!name.empty());
118 const Atom *existing = findByName(name);
119 if (existing == nullptr) {
120 // Name is not in symbol table yet, add it associate with this atom.
121 _nameTable[name] = &newAtom;
122 return true;
123 }
124
125 // Do nothing if the same object is added more than once.
126 if (existing == &newAtom)
127 return false;
128
129 // Name is already in symbol table and associated with another atom.
130 bool useNew = true;
131 switch (collide(existing->definition(), newAtom.definition())) {
132 case NCR_First:
133 useNew = false;
134 break;
135 case NCR_Second:
136 useNew = true;
137 break;
138 case NCR_DupDef: {
139 const auto *existingDef = cast<DefinedAtom>(existing);
140 const auto *newDef = cast<DefinedAtom>(&newAtom);
141 switch (mergeSelect(existingDef->merge(), newDef->merge())) {
142 case MCR_First:
143 useNew = false;
144 break;
145 case MCR_Second:
146 useNew = true;
147 break;
148 case MCR_Largest: {
149 uint64_t existingSize = existingDef->sectionSize();
150 uint64_t newSize = newDef->sectionSize();
151 useNew = (newSize >= existingSize);
152 break;
153 }
154 case MCR_SameSize: {
155 uint64_t existingSize = existingDef->sectionSize();
156 uint64_t newSize = newDef->sectionSize();
157 if (existingSize == newSize) {
158 useNew = true;
159 break;
160 }
161 llvm::errs() << "Size mismatch: "
162 << existing->name() << " (" << existingSize << ") "
163 << newAtom.name() << " (" << newSize << ")\n";
164 LLVM_FALLTHROUGH;
165 }
166 case MCR_Error:
167 llvm::errs() << "Duplicate symbols: "
168 << existing->name()
169 << ":"
170 << existing->file().path()
171 << " and "
172 << newAtom.name()
173 << ":"
174 << newAtom.file().path()
175 << "\n";
176 llvm::report_fatal_error("duplicate symbol error");
177 break;
178 }
179 break;
180 }
181 case NCR_DupUndef: {
182 const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing);
183 const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom);
184
185 bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull());
186 if (sameCanBeNull)
187 useNew = false;
188 else
189 useNew = (newUndef->canBeNull() < existingUndef->canBeNull());
190 break;
191 }
192 case NCR_DupShLib: {
193 useNew = false;
194 break;
195 }
196 case NCR_Error:
197 llvm::errs() << "SymbolTable: error while merging " << name << "\n";
198 llvm::report_fatal_error("duplicate symbol error");
199 break;
200 }
201
202 if (useNew) {
203 // Update name table to use new atom.
204 _nameTable[name] = &newAtom;
205 // Add existing atom to replacement table.
206 _replacedAtoms[existing] = &newAtom;
207 } else {
208 // New atom is not being used. Add it to replacement table.
209 _replacedAtoms[&newAtom] = existing;
210 }
211 return false;
212 }
213
getHashValue(const DefinedAtom * atom)214 unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
215 auto content = atom->rawContent();
216 return llvm::hash_combine(atom->size(),
217 atom->contentType(),
218 llvm::hash_combine_range(content.begin(),
219 content.end()));
220 }
221
isEqual(const DefinedAtom * const l,const DefinedAtom * const r)222 bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l,
223 const DefinedAtom * const r) {
224 if (l == r)
225 return true;
226 if (l == getEmptyKey() || r == getEmptyKey())
227 return false;
228 if (l == getTombstoneKey() || r == getTombstoneKey())
229 return false;
230 if (l->contentType() != r->contentType())
231 return false;
232 if (l->size() != r->size())
233 return false;
234 if (l->sectionChoice() != r->sectionChoice())
235 return false;
236 if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) {
237 if (!l->customSectionName().equals(r->customSectionName()))
238 return false;
239 }
240 ArrayRef<uint8_t> lc = l->rawContent();
241 ArrayRef<uint8_t> rc = r->rawContent();
242 return memcmp(lc.data(), rc.data(), lc.size()) == 0;
243 }
244
addByContent(const DefinedAtom & newAtom)245 bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
246 AtomContentSet::iterator pos = _contentTable.find(&newAtom);
247 if (pos == _contentTable.end()) {
248 _contentTable.insert(&newAtom);
249 return true;
250 }
251 const Atom* existing = *pos;
252 // New atom is not being used. Add it to replacement table.
253 _replacedAtoms[&newAtom] = existing;
254 return false;
255 }
256
findByName(StringRef sym)257 const Atom *SymbolTable::findByName(StringRef sym) {
258 NameToAtom::iterator pos = _nameTable.find(sym);
259 if (pos == _nameTable.end())
260 return nullptr;
261 return pos->second;
262 }
263
replacement(const Atom * atom)264 const Atom *SymbolTable::replacement(const Atom *atom) {
265 // Find the replacement for a given atom. Atoms in _replacedAtoms
266 // may be chained, so find the last one.
267 for (;;) {
268 AtomToAtom::iterator pos = _replacedAtoms.find(atom);
269 if (pos == _replacedAtoms.end())
270 return atom;
271 atom = pos->second;
272 }
273 }
274
isCoalescedAway(const Atom * atom)275 bool SymbolTable::isCoalescedAway(const Atom *atom) {
276 return _replacedAtoms.count(atom) > 0;
277 }
278
undefines()279 std::vector<const UndefinedAtom *> SymbolTable::undefines() {
280 std::vector<const UndefinedAtom *> ret;
281 for (auto it : _nameTable) {
282 const Atom *atom = it.second;
283 assert(atom != nullptr);
284 if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
285 if (_replacedAtoms.count(undef) == 0)
286 ret.push_back(undef);
287 }
288 return ret;
289 }
290
291 } // namespace lld
292