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 "InputFiles.h"
11 #include "Symbols.h"
12 #include "lld/Common/ErrorHandler.h"
13 #include "lld/Common/Memory.h"
14 
15 using namespace llvm;
16 using namespace lld;
17 using namespace lld::macho;
18 
19 Symbol *SymbolTable::find(StringRef name) {
20   auto it = symMap.find(llvm::CachedHashStringRef(name));
21   if (it == symMap.end())
22     return nullptr;
23   return symVector[it->second];
24 }
25 
26 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name) {
27   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
28 
29   // Name already present in the symbol table.
30   if (!p.second)
31     return {symVector[p.first->second], false};
32 
33   // Name is a new symbol.
34   Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
35   symVector.push_back(sym);
36   return {sym, true};
37 }
38 
39 Symbol *SymbolTable::addDefined(StringRef name, InputSection *isec,
40                                 uint32_t value, bool isWeakDef) {
41   Symbol *s;
42   bool wasInserted;
43   bool overridesWeakDef = false;
44   std::tie(s, wasInserted) = insert(name);
45 
46   if (!wasInserted) {
47     if (auto *defined = dyn_cast<Defined>(s)) {
48       if (isWeakDef)
49         return s;
50       if (!defined->isWeakDef())
51         error("duplicate symbol: " + name);
52     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
53       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
54     }
55     // Defined symbols take priority over other types of symbols, so in case
56     // of a name conflict, we fall through to the replaceSymbol() call below.
57   }
58 
59   Defined *defined = replaceSymbol<Defined>(s, name, isec, value, isWeakDef,
60                                             /*isExternal=*/true);
61   defined->overridesWeakDef = overridesWeakDef;
62   return s;
63 }
64 
65 Symbol *SymbolTable::addUndefined(StringRef name, bool isWeakRef) {
66   Symbol *s;
67   bool wasInserted;
68   std::tie(s, wasInserted) = insert(name);
69 
70   auto refState = isWeakRef ? RefState::Weak : RefState::Strong;
71 
72   if (wasInserted)
73     replaceSymbol<Undefined>(s, name, refState);
74   else if (auto *lazy = dyn_cast<LazySymbol>(s))
75     lazy->fetchArchiveMember();
76   else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
77     dynsym->refState = std::max(dynsym->refState, refState);
78   else if (auto *undefined = dyn_cast<Undefined>(s))
79     undefined->refState = std::max(undefined->refState, refState);
80   return s;
81 }
82 
83 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
84                                uint32_t align) {
85   Symbol *s;
86   bool wasInserted;
87   std::tie(s, wasInserted) = insert(name);
88 
89   if (!wasInserted) {
90     if (auto *common = dyn_cast<CommonSymbol>(s)) {
91       if (size < common->size)
92         return s;
93     } else if (isa<Defined>(s)) {
94       return s;
95     }
96     // Common symbols take priority over all non-Defined symbols, so in case of
97     // a name conflict, we fall through to the replaceSymbol() call below.
98   }
99 
100   replaceSymbol<CommonSymbol>(s, name, file, size, align);
101   return s;
102 }
103 
104 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
105                               bool isTlv) {
106   Symbol *s;
107   bool wasInserted;
108   std::tie(s, wasInserted) = insert(name);
109 
110   auto refState = RefState::Unreferenced;
111   if (!wasInserted) {
112     if (auto *defined = dyn_cast<Defined>(s)) {
113       if (isWeakDef && !defined->isWeakDef())
114         defined->overridesWeakDef = true;
115     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
116       refState = undefined->refState;
117     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
118       refState = dysym->refState;
119     }
120   }
121 
122   if (wasInserted || isa<Undefined>(s) ||
123       (isa<DylibSymbol>(s) && !isWeakDef && s->isWeakDef()))
124     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
125 
126   return s;
127 }
128 
129 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
130                              const llvm::object::Archive::Symbol &sym) {
131   Symbol *s;
132   bool wasInserted;
133   std::tie(s, wasInserted) = insert(name);
134 
135   if (wasInserted)
136     replaceSymbol<LazySymbol>(s, file, sym);
137   else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
138     file->fetch(sym);
139   return s;
140 }
141 
142 Symbol *SymbolTable::addDSOHandle(const MachHeaderSection *header) {
143   Symbol *s;
144   bool wasInserted;
145   std::tie(s, wasInserted) = insert(DSOHandle::name);
146   if (!wasInserted) {
147     // FIXME: Make every symbol (including absolute symbols) contain a
148     // reference to their originating file, then add that file name to this
149     // error message.
150     if (isa<Defined>(s))
151       error("found defined symbol with illegal name " + DSOHandle::name);
152   }
153   replaceSymbol<DSOHandle>(s, header);
154   return s;
155 }
156 
157 SymbolTable *macho::symtab;
158