1 //===- SymbolTable.cpp ----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "SymbolTable.h"
10 #include "ConcatOutputSection.h"
11 #include "Config.h"
12 #include "InputFiles.h"
13 #include "Symbols.h"
14 #include "SyntheticSections.h"
15 #include "lld/Common/ErrorHandler.h"
16 #include "lld/Common/Memory.h"
17
18 using namespace llvm;
19 using namespace lld;
20 using namespace lld::macho;
21
find(CachedHashStringRef cachedName)22 Symbol *SymbolTable::find(CachedHashStringRef cachedName) {
23 auto it = symMap.find(cachedName);
24 if (it == symMap.end())
25 return nullptr;
26 return symVector[it->second];
27 }
28
insert(StringRef name,const InputFile * file)29 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
30 const InputFile *file) {
31 auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
32
33 Symbol *sym;
34 if (!p.second) {
35 // Name already present in the symbol table.
36 sym = symVector[p.first->second];
37 } else {
38 // Name is a new symbol.
39 sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
40 symVector.push_back(sym);
41 }
42
43 sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
44 return {sym, p.second};
45 }
46
addDefined(StringRef name,InputFile * file,InputSection * isec,uint64_t value,uint64_t size,bool isWeakDef,bool isPrivateExtern,bool isThumb,bool isReferencedDynamically,bool noDeadStrip)47 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
48 InputSection *isec, uint64_t value,
49 uint64_t size, bool isWeakDef,
50 bool isPrivateExtern, bool isThumb,
51 bool isReferencedDynamically,
52 bool noDeadStrip) {
53 Symbol *s;
54 bool wasInserted;
55 bool overridesWeakDef = false;
56 std::tie(s, wasInserted) = insert(name, file);
57
58 assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
59 (isa<ObjFile>(file) && file == isec->getFile()));
60
61 if (!wasInserted) {
62 if (auto *defined = dyn_cast<Defined>(s)) {
63 if (isWeakDef) {
64 if (defined->isWeakDef()) {
65 // Both old and new symbol weak (e.g. inline function in two TUs):
66 // If one of them isn't private extern, the merged symbol isn't.
67 defined->privateExtern &= isPrivateExtern;
68 defined->referencedDynamically |= isReferencedDynamically;
69 defined->noDeadStrip |= noDeadStrip;
70
71 // FIXME: Handle this for bitcode files.
72 // FIXME: We currently only do this if both symbols are weak.
73 // We could do this if either is weak (but getting the
74 // case where !isWeakDef && defined->isWeakDef() right
75 // requires some care and testing).
76 if (auto concatIsec = dyn_cast_or_null<ConcatInputSection>(isec))
77 concatIsec->wasCoalesced = true;
78 }
79
80 return defined;
81 }
82 if (!defined->isWeakDef())
83 error("duplicate symbol: " + name + "\n>>> defined in " +
84 toString(defined->getFile()) + "\n>>> defined in " +
85 toString(file));
86 } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
87 overridesWeakDef = !isWeakDef && dysym->isWeakDef();
88 dysym->unreference();
89 }
90 // Defined symbols take priority over other types of symbols, so in case
91 // of a name conflict, we fall through to the replaceSymbol() call below.
92 }
93
94 Defined *defined = replaceSymbol<Defined>(
95 s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
96 isPrivateExtern, isThumb, isReferencedDynamically, noDeadStrip);
97 defined->overridesWeakDef = overridesWeakDef;
98 return defined;
99 }
100
addUndefined(StringRef name,InputFile * file,bool isWeakRef)101 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
102 bool isWeakRef) {
103 Symbol *s;
104 bool wasInserted;
105 std::tie(s, wasInserted) = insert(name, file);
106
107 RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;
108
109 if (wasInserted)
110 replaceSymbol<Undefined>(s, name, file, refState);
111 else if (auto *lazy = dyn_cast<LazySymbol>(s))
112 lazy->fetchArchiveMember();
113 else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
114 dynsym->reference(refState);
115 else if (auto *undefined = dyn_cast<Undefined>(s))
116 undefined->refState = std::max(undefined->refState, refState);
117 return s;
118 }
119
addCommon(StringRef name,InputFile * file,uint64_t size,uint32_t align,bool isPrivateExtern)120 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
121 uint32_t align, bool isPrivateExtern) {
122 Symbol *s;
123 bool wasInserted;
124 std::tie(s, wasInserted) = insert(name, file);
125
126 if (!wasInserted) {
127 if (auto *common = dyn_cast<CommonSymbol>(s)) {
128 if (size < common->size)
129 return s;
130 } else if (isa<Defined>(s)) {
131 return s;
132 }
133 // Common symbols take priority over all non-Defined symbols, so in case of
134 // a name conflict, we fall through to the replaceSymbol() call below.
135 }
136
137 replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
138 return s;
139 }
140
addDylib(StringRef name,DylibFile * file,bool isWeakDef,bool isTlv)141 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
142 bool isTlv) {
143 Symbol *s;
144 bool wasInserted;
145 std::tie(s, wasInserted) = insert(name, file);
146
147 RefState refState = RefState::Unreferenced;
148 if (!wasInserted) {
149 if (auto *defined = dyn_cast<Defined>(s)) {
150 if (isWeakDef && !defined->isWeakDef())
151 defined->overridesWeakDef = true;
152 } else if (auto *undefined = dyn_cast<Undefined>(s)) {
153 refState = undefined->refState;
154 } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
155 refState = dysym->getRefState();
156 }
157 }
158
159 bool isDynamicLookup = file == nullptr;
160 if (wasInserted || isa<Undefined>(s) ||
161 (isa<DylibSymbol>(s) &&
162 ((!isWeakDef && s->isWeakDef()) ||
163 (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup())))) {
164 if (auto *dynsym = dyn_cast<DylibSymbol>(s))
165 dynsym->unreference();
166 replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
167 }
168
169 return s;
170 }
171
addDynamicLookup(StringRef name)172 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
173 return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
174 }
175
addLazy(StringRef name,ArchiveFile * file,const object::Archive::Symbol & sym)176 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
177 const object::Archive::Symbol &sym) {
178 Symbol *s;
179 bool wasInserted;
180 std::tie(s, wasInserted) = insert(name, file);
181
182 if (wasInserted)
183 replaceSymbol<LazySymbol>(s, file, sym);
184 else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
185 file->fetch(sym);
186 return s;
187 }
188
addSynthetic(StringRef name,InputSection * isec,uint64_t value,bool isPrivateExtern,bool includeInSymtab,bool referencedDynamically)189 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
190 uint64_t value, bool isPrivateExtern,
191 bool includeInSymtab,
192 bool referencedDynamically) {
193 Defined *s = addDefined(name, nullptr, isec, value, /*size=*/0,
194 /*isWeakDef=*/false, isPrivateExtern,
195 /*isThumb=*/false, referencedDynamically,
196 /*noDeadStrip=*/false);
197 s->includeInSymtab = includeInSymtab;
198 return s;
199 }
200
201 enum class Boundary {
202 Start,
203 End,
204 };
205
createBoundarySymbol(const Undefined & sym)206 static Defined *createBoundarySymbol(const Undefined &sym) {
207 return symtab->addSynthetic(
208 sym.getName(), /*isec=*/nullptr, /*value=*/-1, /*isPrivateExtern=*/true,
209 /*includeInSymtab=*/false, /*referencedDynamically=*/false);
210 }
211
handleSectionBoundarySymbol(const Undefined & sym,StringRef segSect,Boundary which)212 static void handleSectionBoundarySymbol(const Undefined &sym, StringRef segSect,
213 Boundary which) {
214 StringRef segName, sectName;
215 std::tie(segName, sectName) = segSect.split('$');
216
217 // Attach the symbol to any InputSection that will end up in the right
218 // OutputSection -- it doesn't matter which one we pick.
219 // Don't bother looking through inputSections for a matching
220 // ConcatInputSection -- we need to create ConcatInputSection for
221 // non-existing sections anyways, and that codepath works even if we should
222 // already have a ConcatInputSection with the right name.
223
224 OutputSection *osec = nullptr;
225 // This looks for __TEXT,__cstring etc.
226 for (SyntheticSection *ssec : syntheticSections)
227 if (ssec->segname == segName && ssec->name == sectName) {
228 osec = ssec->isec->parent;
229 break;
230 }
231
232 if (!osec) {
233 ConcatInputSection *isec = make<ConcatInputSection>(segName, sectName);
234
235 // This runs after markLive() and is only called for Undefineds that are
236 // live. Marking the isec live ensures an OutputSection is created that the
237 // start/end symbol can refer to.
238 assert(sym.isLive());
239 isec->live = true;
240
241 // This runs after gatherInputSections(), so need to explicitly set parent
242 // and add to inputSections.
243 osec = isec->parent = ConcatOutputSection::getOrCreateForInput(isec);
244 inputSections.push_back(isec);
245 }
246
247 if (which == Boundary::Start)
248 osec->sectionStartSymbols.push_back(createBoundarySymbol(sym));
249 else
250 osec->sectionEndSymbols.push_back(createBoundarySymbol(sym));
251 }
252
handleSegmentBoundarySymbol(const Undefined & sym,StringRef segName,Boundary which)253 static void handleSegmentBoundarySymbol(const Undefined &sym, StringRef segName,
254 Boundary which) {
255 OutputSegment *seg = getOrCreateOutputSegment(segName);
256 if (which == Boundary::Start)
257 seg->segmentStartSymbols.push_back(createBoundarySymbol(sym));
258 else
259 seg->segmentEndSymbols.push_back(createBoundarySymbol(sym));
260 }
261
treatUndefinedSymbol(const Undefined & sym,StringRef source)262 void lld::macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
263 // Handle start/end symbols.
264 StringRef name = sym.getName();
265 if (name.consume_front("section$start$"))
266 return handleSectionBoundarySymbol(sym, name, Boundary::Start);
267 if (name.consume_front("section$end$"))
268 return handleSectionBoundarySymbol(sym, name, Boundary::End);
269 if (name.consume_front("segment$start$"))
270 return handleSegmentBoundarySymbol(sym, name, Boundary::Start);
271 if (name.consume_front("segment$end$"))
272 return handleSegmentBoundarySymbol(sym, name, Boundary::End);
273
274 // Handle -U.
275 if (config->explicitDynamicLookups.count(sym.getName())) {
276 symtab->addDynamicLookup(sym.getName());
277 return;
278 }
279
280 // Handle -undefined.
281 auto message = [source, &sym]() {
282 std::string message = "undefined symbol";
283 if (config->archMultiple)
284 message += (" for arch " + getArchitectureName(config->arch())).str();
285 message += ": " + toString(sym);
286 if (!source.empty())
287 message += "\n>>> referenced by " + source.str();
288 else
289 message += "\n>>> referenced by " + toString(sym.getFile());
290 return message;
291 };
292 switch (config->undefinedSymbolTreatment) {
293 case UndefinedSymbolTreatment::error:
294 error(message());
295 break;
296 case UndefinedSymbolTreatment::warning:
297 warn(message());
298 LLVM_FALLTHROUGH;
299 case UndefinedSymbolTreatment::dynamic_lookup:
300 case UndefinedSymbolTreatment::suppress:
301 symtab->addDynamicLookup(sym.getName());
302 break;
303 case UndefinedSymbolTreatment::unknown:
304 llvm_unreachable("unknown -undefined TREATMENT");
305 }
306 }
307
308 SymbolTable *macho::symtab;
309