[ELF] Move duplicate symbol check after input file parsing

[MaskRay]

Summary

https://discourse.llvm.org/t/parallel-input-file-parsing/60164

To decouple symbol initialization and section initialization, Defined::section
assignment should be postponed after input file parsing. To avoid spurious
duplicate definition error due to two definitions in COMDAT groups of the same
signature, we should postpone the duplicate symbol check.

The function is called postScan instead of a more specific name like
checkDuplicateSymbols, because we may merge Symbol::mergeProperties into
postScan. It is placed after compileBitcodeFiles to apply to ET_REL files
produced by LTO. This causes minor diagnostic regression
for skipLinkedOutput configurations: ld.lld --thinlto-index-only a.bc b.o
(bitcode definition prevails) won't detect duplicate symbol error. I think this
is an acceptable compromise. The important cases where (a) both files are
bitcode or (b) --thinlto-index-only is unused are still detected.

[ikudrin]

lld/ELF/Driver.cpp

2291

In D119909, this loop is moved later in the method. It would be better to place it in the right position from the beginning.

2291–2308

In D119909, a helper function initializeLocalSymbols() is added for a similar purpose. It would be better to do the same for ObjFile<T>::postParse().

2309–2310

• Why no parallel execution for bitcode files?
• Shouldn't this loop be placed later in the function to detect duplicate symbols if some bitcode files are parsed after this point? They may define an --entry symbol, as an example.

[MaskRay]

Finalize postParse position.

This means we need to sacrifice a bit for a duplicate symbol error in this patch.

[MaskRay]

lld/ELF/Driver.cpp

2309–2310

Added. Because I thought the code size may not justify the very little performance improvement... With LTO, symbol resolution takes a very tiny time.
That said, the code of parallelForEach has been significantly lowered by D117510, so perhaps just simply add it even if the gain is very low.

--entry is a good point. I added a similar --undefined-glob test to lto/duplicated.ll

[ikudrin]

lld/ELF/Driver.cpp

2432

If this is moved next to the loop for bitcode files, it should detect all the errors and avoid not-that-helpful error messages like

ld.lld: error: duplicate symbol: f
>>> defined at ld-temp.o
>>>            lto.tmp:(f)
>>> defined at ...test\ELF\lto\Output\duplicated.ll.tmp/b.o:(.text+0x0)

If I understand it right, the object files for LTO cannot introduce new duplicate symbols, no?

As for future extensions of the postParse() method, which should also be applied to the LTO-produced object files, we can have an additional list of them and run postParse() only for them, separately, after compileBitcodeFiles().

2432

Why not add a function like postParseObjectFile() instead of the lambda?

lld/ELF/Symbols.cpp

653–657

The code should be removed, not commented out.

[MaskRay]

Add postParseObjectFile
Use two postParseObjectFile loops

[MaskRay]

rebase

[MaskRay]

lld/ELF/Driver.cpp

2432

If I understand it right, the object files for LTO cannot introduce new duplicate symbols, no?

Ideally, yes. Due to some properties like isUsedInRegularObj, it needs more thoughts whether the loop can be omitted. Perhaps do this omission after the changes are proven to be stable.

[ikudrin]

It looks like the patch was somehow intermixed with D119909. git cannot apply it on ToT.

[MaskRay]

This comment has been deleted.

[MaskRay]

Restore the previous diff.
(the update to D119909 accidentally changed this Differential)

[ikudrin]

LGTM.

lld/ELF/Driver.cpp

2432

Maybe define newObjectFiles in this patch so that the lines are not immediately changed in the subsequent patch (D119909)?

[MaskRay]

comment

lld/ELF/Driver.cpp

if (!sym2)
       continue;
     const char *suffix2 = sym2->getVersionSuffix();
     if (suffix2[0] == '@' && suffix2[1] == '@' &&
         strcmp(suffix1 + 1, suffix2 + 2) == 0) {
       // foo@v1 and foo@@v1 should be merged, so redirect foo@v1 to foo@@v1.
       map.try_emplace(sym, sym2);
       // If both foo@v1 and foo@@v1 are defined and non-weak, report a duplicate
       // definition error.
+      if (sym->isDefined())
+        sym2->checkDuplicate(cast<Defined>(*sym));
       sym2->resolve(*sym);
       // Eliminate foo@v1 from the symbol table.
       sym->symbolKind = Symbol::PlaceholderKind;
       sym->isUsedInRegularObj = false;
     } else if (auto *sym1 = dyn_cast<Defined>(sym)) {
       if (sym2->versionId > VER_NDX_GLOBAL
               ? config->versionDefinitions[sym2->versionId].name == suffix1 + 1
               : sym1->section == sym2->section && sym1->value == sym2->value) {
void LinkerDriver::link(opt::InputArgList &args) {
   {
     llvm::TimeTraceScope timeScope("Parse input files");
     for (size_t i = 0; i < files.size(); ++i) {
       llvm::TimeTraceScope timeScope("Parse input files", files[i]->getName());
       parseFile(files[i]);
     }
   }
 
+  parallelForEach(objectFiles, [](ELFFileBase *file) {
+    switch (config->ekind) {
+    case ELF32LEKind:
+      cast<ObjFile<ELF32LE>>(file)->postParse();
+      break;
+    case ELF32BEKind:
+      cast<ObjFile<ELF32BE>>(file)->postParse();
+      break;
+    case ELF64LEKind:
+      cast<ObjFile<ELF64LE>>(file)->postParse();
+      break;
+    case ELF64BEKind:
+      cast<ObjFile<ELF64BE>>(file)->postParse();
+      break;
+    default:
+      llvm_unreachable("");
+    }
+  });
+  for (BitcodeFile *file : bitcodeFiles)
+    file->postParse();
+
   // Now that we have every file, we can decide if we will need a
   // dynamic symbol table.
   // We need one if we were asked to export dynamic symbols or if we are
   // producing a shared library.
   // We also need one if any shared libraries are used and for pie executables
   // (probably because the dynamic linker needs it).
   config->hasDynSymTab =
       !sharedFiles.empty() || config->isPic || config->exportDynamic;
if (errorCount())
     return;
 
   // Bail out if normal linked output is skipped due to LTO.
   if (skipLinkedOutput)
     return;
 
   // Handle --exclude-libs again because lto.tmp may reference additional
   // libcalls symbols defined in an excluded archive. This may override
   // versionId set by scanVersionScript().
   if (args.hasArg(OPT_exclude_libs))
     excludeLibs(args);
 
   // Apply symbol renames for --wrap and combine foo@v1 and foo@@v1.
   redirectSymbols(wrapped);
 
   // Replace common symbols with regular symbols.
   replaceCommonSymbols();

lld/ELF/InputFiles.h

public:
 
   // True if the file defines functions compiled with -fsplit-stack,
   // but had one or more functions with the no_split_stack attribute.
   bool someNoSplitStack = false;
 
   // Get cached DWARF information.
   DWARFCache *getDwarf();
 
+  void postParse();
+
 private:
   void initializeSections(bool ignoreComdats,
                           const llvm::object::ELFFile<ELFT> &obj);
   void initializeSymbols(const llvm::object::ELFFile<ELFT> &obj);
   void initializeJustSymbols();
 
   InputSectionBase *getRelocTarget(uint32_t idx, const Elf_Shdr &sec,
                                    uint32_t info);

 
 class BitcodeFile : public InputFile {
 public:
   BitcodeFile(MemoryBufferRef m, StringRef archiveName,
               uint64_t offsetInArchive, bool lazy);
   static bool classof(const InputFile *f) { return f->kind() == BitcodeKind; }
   template <class ELFT> void parse();
   void parseLazy();
+  void postParse();
   std::unique_ptr<llvm::lto::InputFile> obj;
+  std::vector<bool> keptComdats;
 };
 
 // .so file.
 class SharedFile : public ELFFileBase {
 public:
   SharedFile(MemoryBufferRef m, StringRef defaultSoName)
       : ELFFileBase(SharedKind, m), soName(defaultSoName),
         isNeeded(!config->asNeeded) {}

lld/ELF/InputFiles.cpp

for (unsigned i : undefineds) {
     const Elf_Sym &eSym = eSyms[i];
     Symbol *sym = symbols[i];
     sym->resolve(Undefined{this, StringRef(), eSym.getBinding(), eSym.st_other,
                            eSym.getType()});
     sym->referenced = true;
   }
 }
 
+// Called after all ObjFile::parse is called for all ObjFiles. This checks
+// duplicate symbols and may do symbol property merge in the future.
+template <class ELFT> void ObjFile<ELFT>::postParse() {
+  ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
+  for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
+    const Elf_Sym &eSym = eSyms[i];
+    const Symbol &sym = *symbols[i];
+    // !sym.file allows a symbol assignment redefines a symbol without an error.
+    if (sym.file == this || !sym.file || !sym.isDefined() ||
+        eSym.st_shndx == SHN_UNDEF || eSym.st_shndx == SHN_COMMON ||
+        eSym.getBinding() == STB_WEAK)
+      continue;
+    uint32_t secIdx = eSym.st_shndx;
+    if (LLVM_UNLIKELY(secIdx == SHN_XINDEX))
+      secIdx = cantFail(getExtendedSymbolTableIndex<ELFT>(eSym, i, shndxTable));
+    else if (secIdx >= SHN_LORESERVE)
+      secIdx = 0;
+    if (sections[secIdx] == &InputSection::discarded)
+      continue;
+    // Allow absolute symbols with the same value for GNU ld compatibility.
+    if (!cast<Defined>(sym).section && !sections[secIdx] &&
+        cast<Defined>(sym).value == eSym.st_value)
+      continue;
+    reportDuplicate(sym, this, sections[secIdx], eSym.st_value);
+  }
+}
+
 // The handling of tentative definitions (COMMON symbols) in archives is murky.
 // A tentative definition will be promoted to a global definition if there are
 // no non-tentative definitions to dominate it. When we hold a tentative
 // definition to a symbol and are inspecting archive members for inclusion
 // there are 2 ways we can proceed:
 //
 // 1) Consider the tentative definition a 'real' definition (ie promotion from
 //    tentative to real definition has already happened) and not inspect
if (objSym.isCommon()) {
     Defined newSym(&f, StringRef(), binding, visibility, type, 0, 0, nullptr);
     if (objSym.canBeOmittedFromSymbolTable())
       newSym.exportDynamic = false;
     sym->resolve(newSym);
   }
 }
 
 template <class ELFT> void BitcodeFile::parse() {
-  std::vector<bool> keptComdats;
   for (std::pair<StringRef, Comdat::SelectionKind> s : obj->getComdatTable()) {
     keptComdats.push_back(
         s.second == Comdat::NoDeduplicate ||
         symtab->comdatGroups.try_emplace(CachedHashStringRef(s.first), this)
             .second);
   }
 
   symbols.resize(obj->symbols().size());
void BitcodeFile::parseLazy() {
   for (auto it : llvm::enumerate(obj->symbols()))
     if (!it.value().isUndefined()) {
       auto *sym = symtab.insert(saver().save(it.value().getName()));
       sym->resolve(LazyObject{*this});
       symbols[it.index()] = sym;
     }
 }
 
+void BitcodeFile::postParse() {
+  for (auto it : llvm::enumerate(obj->symbols())) {
+    const Symbol &sym = *symbols[it.index()];
+    const auto &objSym = it.value();
+    if (sym.file == this || !sym.isDefined() || objSym.isUndefined() ||
+        objSym.isCommon() || objSym.isWeak())
+      continue;
+    int c = objSym.getComdatIndex();
+    if (c != -1 && !keptComdats[c])
+      continue;
+    reportDuplicate(sym, this, nullptr, 0);
+  }
+}
+
 void BinaryFile::parse() {
   ArrayRef<uint8_t> data = arrayRefFromStringRef(mb.getBuffer());
   auto *section = make<InputSection>(this, SHF_ALLOC | SHF_WRITE, SHT_PROGBITS,
                                      8, data, ".data");
   sections.push_back(section);
 
   // For each input file foo that is embedded to a result as a binary
   // blob, we define _binary_foo_{start,end,size} symbols, so that
   // user programs can access blobs by name. Non-alphanumeric
   // characters in a filename are replaced with underscore.
   std::string s = "_binary_" + mb.getBufferIdentifier().str();
   for (size_t i = 0; i < s.size(); ++i)
     if (!isAlnum(s[i]))
       s[i] = '_';
 
   llvm::StringSaver &saver = lld::saver();
 
-  symtab->addSymbol(Defined{nullptr, saver.save(s + "_start"), STB_GLOBAL,
-                            STV_DEFAULT, STT_OBJECT, 0, 0, section});
-  symtab->addSymbol(Defined{nullptr, saver.save(s + "_end"), STB_GLOBAL,
-                            STV_DEFAULT, STT_OBJECT, data.size(), 0, section});
-  symtab->addSymbol(Defined{nullptr, saver.save(s + "_size"), STB_GLOBAL,
-                            STV_DEFAULT, STT_OBJECT, data.size(), 0, nullptr});
+  symtab->addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_start"),
+                                       STB_GLOBAL, STV_DEFAULT, STT_OBJECT, 0,
+                                       0, section});
+  symtab->addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_end"),
+                                       STB_GLOBAL, STV_DEFAULT, STT_OBJECT,
+                                       data.size(), 0, section});
+  symtab->addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_size"),
+                                       STB_GLOBAL, STV_DEFAULT, STT_OBJECT,
+                                       data.size(), 0, nullptr});
 }
 
 InputFile *elf::createObjectFile(MemoryBufferRef mb, StringRef archiveName,
                                  uint64_t offsetInArchive) {
   if (isBitcode(mb))
     return make<BitcodeFile>(mb, archiveName, offsetInArchive, /*lazy=*/false);
 
   switch (getELFKind(mb, archiveName)) {

lld/ELF/SymbolTable.h

 public:
   ArrayRef<Symbol *> symbols() const { return symVector; }
 
   void wrap(Symbol *sym, Symbol *real, Symbol *wrap);
 
   Symbol *insert(StringRef name);
 
   Symbol *addSymbol(const Symbol &newSym);
+  Symbol *addAndCheckDuplicate(const Defined &newSym);
 
   void scanVersionScript();
 
   Symbol *find(StringRef name);
 
   void handleDynamicList();
 
   // Set of .so files to not link the same shared object file more than once.

lld/ELF/SymbolTable.cpp

 }
 
 Symbol *SymbolTable::addSymbol(const Symbol &newSym) {
   Symbol *sym = insert(newSym.getName());
   sym->resolve(newSym);
   return sym;
 }
 
+// This variant of addSymbol is used by BinaryFile::parse to check duplicate
+// symbol errors.
+Symbol *SymbolTable::addAndCheckDuplicate(const Defined &newSym) {
+  Symbol *sym = insert(newSym.getName());
+  if (sym->isDefined())
+    sym->checkDuplicate(newSym);
+  sym->resolve(newSym);
+  return sym;
+}
+
 Symbol *SymbolTable::find(StringRef name) {
   auto it = symMap.find(CachedHashStringRef(name));
   if (it == symMap.end())
     return nullptr;
   return symVector[it->second];
 }
 
 // A version script/dynamic list is only meaningful for a Defined symbol.

lld/ELF/Symbols.h

public:
   void mergeProperties(const Symbol &other);
   void resolve(const Symbol &other);
 
   // If this is a lazy symbol, extract an input file and add the symbol
   // in the file to the symbol table. Calling this function on
   // non-lazy object causes a runtime error.
   void extract() const;
 
+  void checkDuplicate(const Defined &other) const;
+
 private:
   void resolveUndefined(const Undefined &other);
   void resolveCommon(const CommonSymbol &other);
   void resolveDefined(const Defined &other);
   template <class LazyT> void resolveLazy(const LazyT &other);
   void resolveShared(const SharedSymbol &other);
 
   int compare(const Symbol *other) const;

 }
 
 template <typename... T> Defined *makeDefined(T &&...args) {
   return new (reinterpret_cast<Defined *>(
       getSpecificAllocSingleton<SymbolUnion>().Allocate()))
       Defined(std::forward<T>(args)...);
 }
 
+void reportDuplicate(const Symbol &sym, InputFile *newFile,
+                     InputSectionBase *errSec, uint64_t errOffset);
 void maybeWarnUnorderableSymbol(const Symbol *sym);
 bool computeIsPreemptible(const Symbol &sym);
 void reportBackrefs();
 
 // A mapping from a symbol to an InputFile referencing it backward. Used by
 // --warn-backrefs.
 extern llvm::DenseMap<const Symbol *,
                       std::pair<const InputFile *, const InputFile *>>

lld/ELF/Symbols.cpp

int Symbol::compare(const Symbol *other) const {
   }
 
   if (other->isCommon()) {
     if (config->warnCommon)
       warn("common " + getName() + " is overridden");
     return -1;
   }
 
-  auto *oldSym = cast<Defined>(this);
-  auto *newSym = cast<Defined>(other);
-
-  if (isa_and_nonnull<BitcodeFile>(other->file))
-    return 0;
-
-  if (!oldSym->section && !newSym->section && oldSym->value == newSym->value &&
-      newSym->binding == STB_GLOBAL)
-    return -1;
-
   return 0;
 }
 
-static void reportDuplicate(const Symbol &sym, InputFile *newFile,
-                            InputSectionBase *errSec, uint64_t errOffset) {
+void elf::reportDuplicate(const Symbol &sym, InputFile *newFile,
   if (config->allowMultipleDefinition)
     return;
   const Defined *d = cast<Defined>(&sym);
   if (!d->section || !errSec) {
     error("duplicate symbol: " + toString(sym) + "\n>>> defined in " +
           toString(sym.file) + "\n>>> defined in " + toString(newFile));
     return;
   }
if (!src1.empty())
     msg += src1 + "\n>>>            ";
   msg += obj1 + "\n>>> defined at ";
   if (!src2.empty())
     msg += src2 + "\n>>>            ";
   msg += obj2;
   error(msg);
 }
 
+void Symbol::checkDuplicate(const Defined &other) const {
+  if (compare(&other) == 0)
+    reportDuplicate(*this, other.file,
+                    dyn_cast_or_null<InputSectionBase>(other.section),
+                    other.value);
+}
+
 void Symbol::resolveCommon(const CommonSymbol &other) {
   int cmp = compare(&other);
   if (cmp < 0)
     return;
 
   if (cmp > 0) {
     if (auto *s = dyn_cast<SharedSymbol>(this)) {
       // Increase st_size if the shared symbol has a larger st_size. The shared
if (oldSym->size < other.size) {
     oldSym->size = other.size;
   }
 }
 
 void Symbol::resolveDefined(const Defined &other) {
   int cmp = compare(&other);
   if (cmp > 0)
     replace(other);
-  else if (cmp == 0)
-    reportDuplicate(*this, other.file,
-                    dyn_cast_or_null<InputSectionBase>(other.section),
-                    other.value);
+  // else if (cmp == 0)
+  //   reportDuplicate(this, other.file,
+  //                   dyn_cast_or_null<InputSectionBase>(other.section),
+  //                   other.value);
 }
 
 template <class LazyT>
 static void replaceCommon(Symbol &oldSym, const LazyT &newSym) {
   backwardReferences.erase(&oldSym);
   oldSym.replace(newSym);
   newSym.extract();
 }
 

lld/test/ELF/invalid/symtab-sh-info-dup.test

 # REQUIRES: x86
 ## The ELF spec says all symbols with STB_LOCAL binding precede the weak and
 ## global symbols. If a local symbol is found in the non-local part of the
 ## symbol table, make sure we have filled in all entries of InputFile::symbols.
 ## Otherwise a null entry can lead to a null pointer dereference when iterating
 ## over InputFile::symbols.
 
 # RUN: yaml2obj %s -o %t.o
 # RUN: not ld.lld %t.o %t.o -o /dev/null 2>&1 | FileCheck %s
 
 # CHECK:      error: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
+# CHECK-NEXT: error: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
 # CHECK-NEXT: error: duplicate symbol: _start
 # CHECK-NEXT: >>> defined at {{.*}}.o:(.text+0x0)
 # CHECK-NEXT: >>> defined at {{.*}}.o:(.text+0x0)
-# CHECK-EMPTY:
-# CHECK-NEXT: error: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
 
 # RUN: ld.lld --noinhibit-exec %t.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=WARN
 # WARN: warning: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
 
 !ELF
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB

lld/test/ELF/vs-diagnostics-duplicate.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 // RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/vs-diagnostics-duplicate2.s -o %t2.o
 // RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/vs-diagnostics-duplicate3.s -o %t3.o
-// RUN: not ld.lld --vs-diagnostics %t1.o %t2.o %t3.o -o /dev/null 2>&1 | FileCheck %s
+// RUN: not ld.lld --vs-diagnostics --threads=1 %t1.o %t2.o %t3.o -o /dev/null 2>&1 | FileCheck %s
 
 // Case 1. The source locations are unknown for both symbols.
 // CHECK:      {{.*}}ld.lld{{.*}}: error: duplicate symbol: foo
 // CHECK-NEXT: >>> defined at {{.*}}1.o:(.text+0x{{.+}})
 // CHECK-NEXT: >>> defined at {{.*}}2.o:(.text+0x{{.+}})
 
 // Case 2. Both symbols have full source location.
 // CHECK:      duplicate.s(15): error: duplicate symbol: bar