1 files changed, 162 insertions, 137 deletions

diff --git a/ELF/Relocations.cpp b/ELF/Relocations.cpp
index ee48f48081360..ab3030d91017b 100644
--- a/ELF/Relocations.cpp
+++ b/ELF/Relocations.cpp
@@ -62,9 +62,8 @@ using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
-using namespace lld;
-using namespace lld::elf;
-
+namespace lld {
+namespace elf {
 static Optional<std::string> getLinkerScriptLocation(const Symbol &sym) {
   for (BaseCommand *base : script->sectionCommands)
     if (auto *cmd = dyn_cast<SymbolAssignment>(base))
@@ -344,9 +343,9 @@ static bool needsPlt(RelExpr expr) {
 // returns false for TLS variables even though they need GOT, because
 // TLS variables uses GOT differently than the regular variables.
 static bool needsGot(RelExpr expr) {
-  return oneof<R_GOT, R_GOT_OFF, R_HEXAGON_GOT, R_MIPS_GOT_LOCAL_PAGE,
-               R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC,
-               R_GOT_PC, R_GOTPLT>(expr);
+  return oneof<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF,
+               R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT>(
+      expr);
 }
 
 // True if this expression is of the form Sym - X, where X is a position in the
@@ -369,7 +368,7 @@ static bool isRelExpr(RelExpr expr) {
 static bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
                                      InputSectionBase &s, uint64_t relOff) {
   // These expressions always compute a constant
-  if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_HEXAGON_GOT, R_TLSLD_GOT_OFF,
+  if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_TLSLD_GOT_OFF,
             R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF,
             R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD,
             R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
@@ -510,10 +509,8 @@ static void replaceWithDefined(Symbol &sym, SectionBase *sec, uint64_t value,
   sym.gotIndex = old.gotIndex;
   sym.verdefIndex = old.verdefIndex;
   sym.ppc64BranchltIndex = old.ppc64BranchltIndex;
-  sym.isPreemptible = true;
   sym.exportDynamic = true;
   sym.isUsedInRegularObj = true;
-  sym.used = true;
 }
 
 // Reserve space in .bss or .bss.rel.ro for copy relocation.
@@ -569,10 +566,16 @@ template <class ELFT> static void addCopyRelSymbol(SharedSymbol &ss) {
   bool isRO = isReadOnly<ELFT>(ss);
   BssSection *sec =
       make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment);
-  if (isRO)
-    in.bssRelRo->getParent()->addSection(sec);
-  else
-    in.bss->getParent()->addSection(sec);
+  OutputSection *osec = (isRO ? in.bssRelRo : in.bss)->getParent();
+
+  // At this point, sectionBases has been migrated to sections. Append sec to
+  // sections.
+  if (osec->sectionCommands.empty() ||
+      !isa<InputSectionDescription>(osec->sectionCommands.back()))
+    osec->sectionCommands.push_back(make<InputSectionDescription>(""));
+  auto *isd = cast<InputSectionDescription>(osec->sectionCommands.back());
+  isd->sections.push_back(sec);
+  osec->commitSection(sec);
 
   // Look through the DSO's dynamic symbol table for aliases and create a
   // dynamic symbol for each one. This causes the copy relocation to correctly
@@ -693,8 +696,75 @@ struct UndefinedDiag {
 
 static std::vector<UndefinedDiag> undefs;
 
+// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
+// the suggested symbol, which is either in the symbol table, or in the same
+// file of sym.
+static const Symbol *getAlternativeSpelling(const Undefined &sym) {
+  // Build a map of local defined symbols.
+  DenseMap<StringRef, const Symbol *> map;
+  if (sym.file && !isa<SharedFile>(sym.file)) {
+    for (const Symbol *s : sym.file->getSymbols())
+      if (s->isLocal() && s->isDefined())
+        map.try_emplace(s->getName(), s);
+  }
+
+  auto suggest = [&](StringRef newName) -> const Symbol * {
+    // If defined locally.
+    if (const Symbol *s = map.lookup(newName))
+      return s;
+
+    // If in the symbol table and not undefined.
+    if (const Symbol *s = symtab->find(newName))
+      if (!s->isUndefined())
+        return s;
+
+    return nullptr;
+  };
+
+  // This loop enumerates all strings of Levenshtein distance 1 as typo
+  // correction candidates and suggests the one that exists as a non-undefined
+  // symbol.
+  StringRef name = sym.getName();
+  for (size_t i = 0, e = name.size(); i != e + 1; ++i) {
+    // Insert a character before name[i].
+    std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str();
+    for (char c = '0'; c <= 'z'; ++c) {
+      newName[i] = c;
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+    if (i == e)
+      break;
+
+    // Substitute name[i].
+    newName = name;
+    for (char c = '0'; c <= 'z'; ++c) {
+      newName[i] = c;
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+
+    // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is
+    // common.
+    if (i + 1 < e) {
+      newName[i] = name[i + 1];
+      newName[i + 1] = name[i];
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+
+    // Delete name[i].
+    newName = (name.substr(0, i) + name.substr(i + 1)).str();
+    if (const Symbol *s = suggest(newName))
+      return s;
+  }
+
+  return nullptr;
+}
+
 template <class ELFT>
-static void reportUndefinedSymbol(const UndefinedDiag &undef) {
+static void reportUndefinedSymbol(const UndefinedDiag &undef,
+                                  bool correctSpelling) {
   Symbol &sym = *undef.sym;
 
   auto visibility = [&]() -> std::string {
@@ -734,6 +804,14 @@ static void reportUndefinedSymbol(const UndefinedDiag &undef) {
     msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times")
                .str();
 
+  if (correctSpelling)
+    if (const Symbol *corrected =
+            getAlternativeSpelling(cast<Undefined>(sym))) {
+      msg += "\n>>> did you mean: " + toString(*corrected);
+      if (corrected->file)
+        msg += "\n>>> defined in: " + toString(corrected->file);
+    }
+
   if (sym.getName().startswith("_ZTV"))
     msg += "\nthe vtable symbol may be undefined because the class is missing "
            "its key function (see https://lld.llvm.org/missingkeyfunction)";
@@ -744,7 +822,7 @@ static void reportUndefinedSymbol(const UndefinedDiag &undef) {
     error(msg);
 }
 
-template <class ELFT> void elf::reportUndefinedSymbols() {
+template <class ELFT> void reportUndefinedSymbols() {
   // Find the first "undefined symbol" diagnostic for each diagnostic, and
   // collect all "referenced from" lines at the first diagnostic.
   DenseMap<Symbol *, UndefinedDiag *> firstRef;
@@ -757,23 +835,21 @@ template <class ELFT> void elf::reportUndefinedSymbols() {
       firstRef[undef.sym] = &undef;
   }
 
-  for (const UndefinedDiag &undef : undefs) {
-    if (!undef.locs.empty())
-      reportUndefinedSymbol<ELFT>(undef);
-  }
+  // Enable spell corrector for the first 2 diagnostics.
+  for (auto it : enumerate(undefs))
+    if (!it.value().locs.empty())
+      reportUndefinedSymbol<ELFT>(it.value(), it.index() < 2);
   undefs.clear();
 }
 
 // Report an undefined symbol if necessary.
 // Returns true if the undefined symbol will produce an error message.
-template <class ELFT>
 static bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec,
                                  uint64_t offset) {
   if (!sym.isUndefined() || sym.isWeak())
     return false;
 
-  bool canBeExternal = !sym.isLocal() && sym.computeBinding() != STB_LOCAL &&
-                       sym.visibility == STV_DEFAULT;
+  bool canBeExternal = !sym.isLocal() && sym.visibility == STV_DEFAULT;
   if (config->unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal)
     return false;
 
@@ -997,56 +1073,29 @@ static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type,
     }
   }
 
-  if (!canWrite && (config->isPic && !isRelExpr(expr))) {
-    error(
-        "can't create dynamic relocation " + toString(type) + " against " +
-        (sym.getName().empty() ? "local symbol" : "symbol: " + toString(sym)) +
-        " in readonly segment; recompile object files with -fPIC "
-        "or pass '-Wl,-z,notext' to allow text relocations in the output" +
-        getLocation(sec, sym, offset));
-    return;
-  }
-
-  // Copy relocations (for STT_OBJECT) and canonical PLT (for STT_FUNC) are only
-  // possible in an executable.
-  //
-  // Among R_ABS relocatoin types, symbolicRel has the same size as the word
-  // size. Others have fewer bits and may cause runtime overflow in -pie/-shared
-  // mode. Disallow them.
-  if (config->shared ||
-      (config->pie && expr == R_ABS && type != target->symbolicRel)) {
-    errorOrWarn(
-        "relocation " + toString(type) + " cannot be used against " +
-        (sym.getName().empty() ? "local symbol" : "symbol " + toString(sym)) +
-        "; recompile with -fPIC" + getLocation(sec, sym, offset));
-    return;
-  }
-
-  // If the symbol is undefined we already reported any relevant errors.
-  if (sym.isUndefined())
-    return;
-
-  if (!canDefineSymbolInExecutable(sym)) {
-    error("cannot preempt symbol: " + toString(sym) +
-          getLocation(sec, sym, offset));
-    return;
-  }
+  // When producing an executable, we can perform copy relocations (for
+  // STT_OBJECT) and canonical PLT (for STT_FUNC).
+  if (!config->shared) {
+    if (!canDefineSymbolInExecutable(sym)) {
+      errorOrWarn("cannot preempt symbol: " + toString(sym) +
+                  getLocation(sec, sym, offset));
+      return;
+    }
 
-  if (sym.isObject()) {
-    // Produce a copy relocation.
-    if (auto *ss = dyn_cast<SharedSymbol>(&sym)) {
-      if (!config->zCopyreloc)
-        error("unresolvable relocation " + toString(type) +
-              " against symbol '" + toString(*ss) +
-              "'; recompile with -fPIC or remove '-z nocopyreloc'" +
-              getLocation(sec, sym, offset));
-      addCopyRelSymbol<ELFT>(*ss);
+    if (sym.isObject()) {
+      // Produce a copy relocation.
+      if (auto *ss = dyn_cast<SharedSymbol>(&sym)) {
+        if (!config->zCopyreloc)
+          error("unresolvable relocation " + toString(type) +
+                " against symbol '" + toString(*ss) +
+                "'; recompile with -fPIC or remove '-z nocopyreloc'" +
+                getLocation(sec, sym, offset));
+        addCopyRelSymbol<ELFT>(*ss);
+      }
+      sec.relocations.push_back({expr, type, offset, addend, &sym});
+      return;
     }
-    sec.relocations.push_back({expr, type, offset, addend, &sym});
-    return;
-  }
 
-  if (sym.isFunc()) {
     // This handles a non PIC program call to function in a shared library. In
     // an ideal world, we could just report an error saying the relocation can
     // overflow at runtime. In the real world with glibc, crt1.o has a
@@ -1074,18 +1123,37 @@ static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type,
     //   compiled without -fPIE/-fPIC and doesn't maintain ebx.
     // * If a library definition gets preempted to the executable, it will have
     //   the wrong ebx value.
-    if (config->pie && config->emachine == EM_386)
-      errorOrWarn("symbol '" + toString(sym) +
-                  "' cannot be preempted; recompile with -fPIE" +
-                  getLocation(sec, sym, offset));
-    if (!sym.isInPlt())
-      addPltEntry<ELFT>(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym);
-    if (!sym.isDefined())
-      replaceWithDefined(
-          sym, in.plt,
-          target->pltHeaderSize + target->pltEntrySize * sym.pltIndex, 0);
-    sym.needsPltAddr = true;
-    sec.relocations.push_back({expr, type, offset, addend, &sym});
+    if (sym.isFunc()) {
+      if (config->pie && config->emachine == EM_386)
+        errorOrWarn("symbol '" + toString(sym) +
+                    "' cannot be preempted; recompile with -fPIE" +
+                    getLocation(sec, sym, offset));
+      if (!sym.isInPlt())
+        addPltEntry<ELFT>(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym);
+      if (!sym.isDefined())
+        replaceWithDefined(
+            sym, in.plt,
+            target->pltHeaderSize + target->pltEntrySize * sym.pltIndex, 0);
+      sym.needsPltAddr = true;
+      sec.relocations.push_back({expr, type, offset, addend, &sym});
+      return;
+    }
+  }
+
+  if (config->isPic) {
+    if (!canWrite && !isRelExpr(expr))
+      errorOrWarn(
+          "can't create dynamic relocation " + toString(type) + " against " +
+          (sym.getName().empty() ? "local symbol"
+                                 : "symbol: " + toString(sym)) +
+          " in readonly segment; recompile object files with -fPIC "
+          "or pass '-Wl,-z,notext' to allow text relocations in the output" +
+          getLocation(sec, sym, offset));
+    else
+      errorOrWarn(
+          "relocation " + toString(type) + " cannot be used against " +
+          (sym.getName().empty() ? "local symbol" : "symbol " + toString(sym)) +
+          "; recompile with -fPIC" + getLocation(sec, sym, offset));
     return;
   }
 
@@ -1093,15 +1161,6 @@ static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type,
               getLocation(sec, sym, offset));
 }
 
-struct IRelativeReloc {
-  RelType type;
-  InputSectionBase *sec;
-  uint64_t offset;
-  Symbol *sym;
-};
-
-static std::vector<IRelativeReloc> iRelativeRelocs;
-
 template <class ELFT, class RelTy>
 static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
                       RelTy *end) {
@@ -1125,7 +1184,7 @@ static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
 
   // Error if the target symbol is undefined. Symbol index 0 may be used by
   // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them.
-  if (symIndex != 0 && maybeReportUndefined<ELFT>(sym, sec, rel.r_offset))
+  if (symIndex != 0 && maybeReportUndefined(sym, sec, rel.r_offset))
     return;
 
   const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset;
@@ -1269,12 +1328,6 @@ static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
     //   correctly, the IRELATIVE relocations are stored in an array which a
     //   statically linked executable's startup code must enumerate using the
     //   linker-defined symbols __rela?_iplt_{start,end}.
-    //
-    // - An absolute relocation to a non-preemptible ifunc (such as a global
-    //   variable containing a pointer to the ifunc) needs to be relocated in
-    //   the exact same way as a GOT entry, so we can avoid needing to make the
-    //   PLT entry canonical by translating such relocations into IRELATIVE
-    //   relocations in the relaIplt.
     if (!sym.isInPlt()) {
       // Create PLT and GOTPLT slots for the symbol.
       sym.isInIplt = true;
@@ -1291,17 +1344,6 @@ static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
                         *directSym);
       sym.pltIndex = directSym->pltIndex;
     }
-    if (expr == R_ABS && addend == 0 && (sec.flags & SHF_WRITE)) {
-      // We might be able to represent this as an IRELATIVE. But we don't know
-      // yet whether some later relocation will make the symbol point to a
-      // canonical PLT, which would make this either a dynamic RELATIVE (PIC) or
-      // static (non-PIC) relocation. So we keep a record of the information
-      // required to process the relocation, and after scanRelocs() has been
-      // called on all relocations, the relocation is resolved by
-      // addIRelativeRelocs().
-      iRelativeRelocs.push_back({type, &sec, offset, &sym});
-      return;
-    }
     if (needsGot(expr)) {
       // Redirect GOT accesses to point to the Igot.
       //
@@ -1362,28 +1404,13 @@ static void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) {
                       });
 }
 
-template <class ELFT> void elf::scanRelocations(InputSectionBase &s) {
+template <class ELFT> void scanRelocations(InputSectionBase &s) {
   if (s.areRelocsRela)
     scanRelocs<ELFT>(s, s.relas<ELFT>());
   else
     scanRelocs<ELFT>(s, s.rels<ELFT>());
 }
 
-// Figure out which representation to use for any absolute relocs to
-// non-preemptible ifuncs that we visited during scanRelocs().
-void elf::addIRelativeRelocs() {
-  for (IRelativeReloc &r : iRelativeRelocs) {
-    if (r.sym->type == STT_GNU_IFUNC)
-      in.relaIplt->addReloc(
-          {target->iRelativeRel, r.sec, r.offset, true, r.sym, 0});
-    else if (config->isPic)
-      addRelativeReloc(r.sec, r.offset, r.sym, 0, R_ABS, r.type);
-    else
-      r.sec->relocations.push_back({R_ABS, r.type, r.offset, 0, r.sym});
-  }
-  iRelativeRelocs.clear();
-}
-
 static bool mergeCmp(const InputSection *a, const InputSection *b) {
   // std::merge requires a strict weak ordering.
   if (a->outSecOff < b->outSecOff)
@@ -1745,11 +1772,6 @@ bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) {
   if (pass == 0 && target->getThunkSectionSpacing())
     createInitialThunkSections(outputSections);
 
-  // With Thunk Size much smaller than branch range we expect to
-  // converge quickly; if we get to 10 something has gone wrong.
-  if (pass == 10)
-    fatal("thunk creation not converged");
-
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into InputSectionDescriptions.
   // We separate the creation of ThunkSections from the insertion of the
@@ -1809,11 +1831,14 @@ bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) {
   return addressesChanged;
 }
 
-template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
-template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
-template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
-template void elf::scanRelocations<ELF64BE>(InputSectionBase &);
-template void elf::reportUndefinedSymbols<ELF32LE>();
-template void elf::reportUndefinedSymbols<ELF32BE>();
-template void elf::reportUndefinedSymbols<ELF64LE>();
-template void elf::reportUndefinedSymbols<ELF64BE>();
+template void scanRelocations<ELF32LE>(InputSectionBase &);
+template void scanRelocations<ELF32BE>(InputSectionBase &);
+template void scanRelocations<ELF64LE>(InputSectionBase &);
+template void scanRelocations<ELF64BE>(InputSectionBase &);
+template void reportUndefinedSymbols<ELF32LE>();
+template void reportUndefinedSymbols<ELF32BE>();
+template void reportUndefinedSymbols<ELF64LE>();
+template void reportUndefinedSymbols<ELF64BE>();
+
+} // namespace elf
+} // namespace lld