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