aboutsummaryrefslogtreecommitdiffstats
path: root/ELF/SymbolTable.cpp
blob: 3faeed8c2bdc3e041f0ec4afeb4ec35c03a15e35 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
//===- SymbolTable.cpp ----------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Symbol table is a bag of all known symbols. We put all symbols of
// all input files to the symbol table. The symbol table is basically
// a hash table with the logic to resolve symbol name conflicts using
// the symbol types.
//
//===----------------------------------------------------------------------===//

#include "SymbolTable.h"
#include "Config.h"
#include "LinkerScript.h"
#include "Symbols.h"
#include "SyntheticSections.h"
#include "lld/Common/ErrorHandler.h"
#include "lld/Common/Memory.h"
#include "lld/Common/Strings.h"
#include "llvm/ADT/STLExtras.h"

using namespace llvm;
using namespace llvm::object;
using namespace llvm::ELF;

using namespace lld;
using namespace lld::elf;

SymbolTable *elf::symtab;

void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
  // Swap symbols as instructed by -wrap.
  int &idx1 = symMap[CachedHashStringRef(sym->getName())];
  int &idx2 = symMap[CachedHashStringRef(real->getName())];
  int &idx3 = symMap[CachedHashStringRef(wrap->getName())];

  idx2 = idx1;
  idx1 = idx3;

  // Now renaming is complete. No one refers Real symbol. We could leave
  // Real as-is, but if Real is written to the symbol table, that may
  // contain irrelevant values. So, we copy all values from Sym to Real.
  StringRef s = real->getName();
  memcpy(real, sym, sizeof(SymbolUnion));
  real->setName(s);
}

// Find an existing symbol or create a new one.
Symbol *SymbolTable::insert(StringRef name) {
  // <name>@@<version> means the symbol is the default version. In that
  // case <name>@@<version> will be used to resolve references to <name>.
  //
  // Since this is a hot path, the following string search code is
  // optimized for speed. StringRef::find(char) is much faster than
  // StringRef::find(StringRef).
  size_t pos = name.find('@');
  if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
    name = name.take_front(pos);

  auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
  int &symIndex = p.first->second;
  bool isNew = p.second;

  if (!isNew)
    return symVector[symIndex];

  Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
  symVector.push_back(sym);

  sym->setName(name);
  sym->symbolKind = Symbol::PlaceholderKind;
  sym->versionId = config->defaultSymbolVersion;
  sym->visibility = STV_DEFAULT;
  sym->isUsedInRegularObj = false;
  sym->exportDynamic = false;
  sym->canInline = true;
  sym->scriptDefined = false;
  sym->partition = 1;
  return sym;
}

Symbol *SymbolTable::addSymbol(const Symbol &New) {
  Symbol *sym = symtab->insert(New.getName());
  sym->resolve(New);
  return sym;
}

Symbol *SymbolTable::find(StringRef name) {
  auto it = symMap.find(CachedHashStringRef(name));
  if (it == symMap.end())
    return nullptr;
  Symbol *sym = symVector[it->second];
  if (sym->isPlaceholder())
    return nullptr;
  return sym;
}

// Initialize demangledSyms with a map from demangled symbols to symbol
// objects. Used to handle "extern C++" directive in version scripts.
//
// The map will contain all demangled symbols. That can be very large,
// and in LLD we generally want to avoid do anything for each symbol.
// Then, why are we doing this? Here's why.
//
// Users can use "extern C++ {}" directive to match against demangled
// C++ symbols. For example, you can write a pattern such as
// "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
// other than trying to match a pattern against all demangled symbols.
// So, if "extern C++" feature is used, we need to demangle all known
// symbols.
StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
  if (!demangledSyms) {
    demangledSyms.emplace();
    for (Symbol *sym : symVector) {
      if (!sym->isDefined() && !sym->isCommon())
        continue;
      if (Optional<std::string> s = demangleItanium(sym->getName()))
        (*demangledSyms)[*s].push_back(sym);
      else
        (*demangledSyms)[sym->getName()].push_back(sym);
    }
  }
  return *demangledSyms;
}

std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion ver) {
  if (ver.isExternCpp)
    return getDemangledSyms().lookup(ver.name);
  if (Symbol *b = find(ver.name))
    if (b->isDefined() || b->isCommon())
      return {b};
  return {};
}

std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion ver) {
  std::vector<Symbol *> res;
  StringMatcher m(ver.name);

  if (ver.isExternCpp) {
    for (auto &p : getDemangledSyms())
      if (m.match(p.first()))
        res.insert(res.end(), p.second.begin(), p.second.end());
    return res;
  }

  for (Symbol *sym : symVector)
    if ((sym->isDefined() || sym->isCommon()) && m.match(sym->getName()))
      res.push_back(sym);
  return res;
}

// Handles -dynamic-list.
void SymbolTable::handleDynamicList() {
  for (SymbolVersion &ver : config->dynamicList) {
    std::vector<Symbol *> syms;
    if (ver.hasWildcard)
      syms = findAllByVersion(ver);
    else
      syms = findByVersion(ver);

    for (Symbol *b : syms) {
      if (!config->shared)
        b->exportDynamic = true;
      else if (b->includeInDynsym())
        b->isPreemptible = true;
    }
  }
}

// Set symbol versions to symbols. This function handles patterns
// containing no wildcard characters.
void SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId,
                                     StringRef versionName) {
  if (ver.hasWildcard)
    return;

  // Get a list of symbols which we need to assign the version to.
  std::vector<Symbol *> syms = findByVersion(ver);
  if (syms.empty()) {
    if (!config->undefinedVersion)
      error("version script assignment of '" + versionName + "' to symbol '" +
            ver.name + "' failed: symbol not defined");
    return;
  }

  auto getName = [](uint16_t ver) -> std::string {
    if (ver == VER_NDX_LOCAL)
      return "VER_NDX_LOCAL";
    if (ver == VER_NDX_GLOBAL)
      return "VER_NDX_GLOBAL";
    return ("version '" + config->versionDefinitions[ver - 2].name + "'").str();
  };

  // Assign the version.
  for (Symbol *sym : syms) {
    // Skip symbols containing version info because symbol versions
    // specified by symbol names take precedence over version scripts.
    // See parseSymbolVersion().
    if (sym->getName().contains('@'))
      continue;

    if (sym->versionId == config->defaultSymbolVersion)
      sym->versionId = versionId;
    if (sym->versionId == versionId)
      continue;

    warn("attempt to reassign symbol '" + ver.name + "' of " +
         getName(sym->versionId) + " to " + getName(versionId));
  }
}

void SymbolTable::assignWildcardVersion(SymbolVersion ver, uint16_t versionId) {
  if (!ver.hasWildcard)
    return;

  // Exact matching takes precendence over fuzzy matching,
  // so we set a version to a symbol only if no version has been assigned
  // to the symbol. This behavior is compatible with GNU.
  for (Symbol *b : findAllByVersion(ver))
    if (b->versionId == config->defaultSymbolVersion)
      b->versionId = versionId;
}

// This function processes version scripts by updating the versionId
// member of symbols.
// If there's only one anonymous version definition in a version
// script file, the script does not actually define any symbol version,
// but just specifies symbols visibilities.
void SymbolTable::scanVersionScript() {
  // First, we assign versions to exact matching symbols,
  // i.e. version definitions not containing any glob meta-characters.
  for (SymbolVersion &ver : config->versionScriptGlobals)
    assignExactVersion(ver, VER_NDX_GLOBAL, "global");
  for (SymbolVersion &ver : config->versionScriptLocals)
    assignExactVersion(ver, VER_NDX_LOCAL, "local");
  for (VersionDefinition &v : config->versionDefinitions)
    for (SymbolVersion &ver : v.globals)
      assignExactVersion(ver, v.id, v.name);

  // Next, we assign versions to fuzzy matching symbols,
  // i.e. version definitions containing glob meta-characters.
  for (SymbolVersion &ver : config->versionScriptGlobals)
    assignWildcardVersion(ver, VER_NDX_GLOBAL);
  for (SymbolVersion &ver : config->versionScriptLocals)
    assignWildcardVersion(ver, VER_NDX_LOCAL);

  // Note that because the last match takes precedence over previous matches,
  // we iterate over the definitions in the reverse order.
  for (VersionDefinition &v : llvm::reverse(config->versionDefinitions))
    for (SymbolVersion &ver : v.globals)
      assignWildcardVersion(ver, v.id);

  // Symbol themselves might know their versions because symbols
  // can contain versions in the form of <name>@<version>.
  // Let them parse and update their names to exclude version suffix.
  for (Symbol *sym : symVector)
    sym->parseSymbolVersion();

  // isPreemptible is false at this point. To correctly compute the binding of a
  // Defined (which is used by includeInDynsym()), we need to know if it is
  // VER_NDX_LOCAL or not. If defaultSymbolVersion is VER_NDX_LOCAL, we should
  // compute symbol versions before handling --dynamic-list.
  handleDynamicList();
}