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