[ELF] Parallelize initializeLocalSymbols

[MaskRay]

Summary

ObjFile::parse combines symbol initialization and resolution. Many tasks
unrelated to symbol resolution can be postponed and parallelized. This patch
extracts local symbol initialization and parallelizes it.

Technically the new function initializeLocalSymbols can be merged into
ObjFile::postParse, but functions like getSrcMsg may access the
uninitialized (all nullptr) local part of InputFile::symbols.

Linking chrome: 1.02x as fast with glibc malloc, 1.04x as fast with mimalloc

Depends on D119908

[MaskRay]

rebase

[MaskRay]

Replace getSpecificAllocSingleton<SymbolUnion>().Allocate(firstGlobal); with localSymStorage.

1.02x as fast when linking clang
1.04x as fast when linking chrome

I plan to commit the change separately to decrease diff, but for single threading there is no observable difference for performance.

[ikudrin]

In D119909#3336805, @MaskRay wrote:

Replace getSpecificAllocSingleton<SymbolUnion>().Allocate(firstGlobal); with localSymStorage.

1.02x as fast when linking clang
1.04x as fast when linking chrome

I plan to commit the change separately to decrease diff, but for single threading there is no observable difference for performance.

Do you know where the performance gain comes from? Can the same optimization be useful elsewhere? Can localSymStorage be std::unique_ptr<SymbolUnion> to avoid the low-level manipulations with the alignment?

lld/ELF/InputFiles.cpp

1160

initializeLocalSymbols() is very similar to postParseObjectFile() from D119908. I believe they should be defined in the same way: both in InputFiles.cpp after methods they call or both in Driver.cpp, as static functions before LinkerDriver::link().

[MaskRay]

In D119909#3337162, @ikudrin wrote:

In D119909#3336805, @MaskRay wrote:

Replace getSpecificAllocSingleton<SymbolUnion>().Allocate(firstGlobal); with localSymStorage.

1.02x as fast when linking clang
1.04x as fast when linking chrome

I plan to commit the change separately to decrease diff, but for single threading there is no observable difference for performance.

Do you know where the performance gain comes from? Can the same optimization be useful elsewhere? Can localSymStorage be std::unique_ptr<SymbolUnion> to avoid the low-level manipulations with the alignment?

NUMA aware allocation, memory reference locality, etc. Symbols.h includes InputFiles.h. SymbolUnion is not accessible in InputFiles.h, so localSymStorage cannot use std::unique_ptr<SymbolUnion[]> with incomplete type.

[MaskRay]

rebase

[MaskRay]

Replace manual aligned alloc with std::make_unique<SymbolUnion[]>(firstGlobal);
now that Symbols.h no longer includes InputFiles.h

[MaskRay]

lld/ELF/InputFiles.cpp

1160

Technically the new function initializeLocalSymbols can be merged into ObjFile::postParse, but functions like getSrcMsg may access the uninitialized (all nullptr) local part of InputFile::symbols.

Combing will cause null pointer reference for some diagnostics.

[ikudrin]

lld/ELF/InputFiles.cpp

1160

My comment was not about combining. I only suggested moving initializeLocalSymbols() to Driver.cpp, place it after postParseObjectFile() and make static.

[MaskRay]

Move static void initializeLocalSymbols to Driver.cpp

[ikudrin]

Thanks for the update! LGTM.

[jgorbe]

We've found segfaults in lld when linking go binaries after this patch:

 #0 0x0000562d149b2b8a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x4bb2b8a)
 #1 0x0000562d149b0b78 llvm::sys::RunSignalHandlers() (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x4bb0b78)
 #2 0x0000562d149b31ec SignalHandler(int) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x4bb31ec)
 #3 0x00007fd976fac750 __restore_rt (/usr/grte/v5/lib64/libpthread.so.0+0x15750)
 #4 0x0000562d123eb029 void (anonymous namespace)::MarkLive<llvm::object::ELFType<(llvm::support::endianness)1, true> >::resolveReloc<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> const>(lld::elf::InputSectionBase&, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> const&, bool) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x25eb029)
 #5 0x0000562d123e75f9 void lld::elf::markLive<llvm::object::ELFType<(llvm::support::endianness)1, true> >() (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x25e75f9)
 #6 0x0000562d1235e86b lld::elf::LinkerDriver::link(llvm::opt::InputArgList&) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x255e86b)
 #7 0x0000562d12351137 lld::elf::LinkerDriver::linkerMain(llvm::ArrayRef<char const*>) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x2551137)
 #8 0x0000562d1234f6a9 lld::elf::link(llvm::ArrayRef<char const*>, llvm::raw_ostream&, llvm::raw_ostream&, bool, bool) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x254f6a9)
 #9 0x0000562d122505d3 lldMain(int, char const**, llvm::raw_ostream&, llvm::raw_ostream&, bool) (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x24505d3)
#10 0x0000562d1224fd89 main (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x244fd89)
#11 0x00007fd976e3c8d3 __libc_start_main (/usr/grte/v5/lib64/libc.so.6+0x628d3)
#12 0x0000562d1224f96a _start (third_party/crosstool/v18/llvm_unstable/toolchain/bin/ld+0x244f96a)
Segmentation fault

I'm going to revert temporarily until @MaskRay can track down the cause.

lld/ELF/Driver.cpp

void LinkerDriver::link(opt::InputArgList &args) {
   // appended to the Files vector.
   {
     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
void LinkerDriver::link(opt::InputArgList &args) {
   reportBackrefs();
   if (errorCount())
     return;
 
   // Bail out if normal linked output is skipped due to LTO.
   if (skipLinkedOutput)
     return;
 
+  parallelForEach(objectFiles, initializeLocalSymbols);
+  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("");
+    }
+  });
+
   // 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);

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 initializeLocalSymbols();
   void postParse();
 
 private:
   void initializeSections(bool ignoreComdats,
                           const llvm::object::ELFFile<ELFT> &obj);
   void initializeSymbols(const llvm::object::ELFFile<ELFT> &obj);
   void initializeJustSymbols();
 
InputFile *createLazyFile(MemoryBufferRef mb, StringRef archiveName,
                           uint64_t offsetInArchive);
 
 inline bool isBitcode(MemoryBufferRef mb) {
   return identify_magic(mb.getBuffer()) == llvm::file_magic::bitcode;
 }
 
 std::string replaceThinLTOSuffix(StringRef path);
 
+void initializeLocalSymbols(ELFFileBase *file);
+
 extern SmallVector<std::unique_ptr<MemoryBuffer>> memoryBuffers;
 extern SmallVector<BinaryFile *, 0> binaryFiles;
 extern SmallVector<BitcodeFile *, 0> bitcodeFiles;
 extern SmallVector<BitcodeFile *, 0> lazyBitcodeFiles;
 extern SmallVector<ELFFileBase *, 0> objectFiles;
 extern SmallVector<SharedFile *, 0> sharedFiles;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/InputFiles.cpp

 // its corresponding ELF symbol table.
 template <class ELFT>
 void ObjFile<ELFT>::initializeSymbols(const object::ELFFile<ELFT> &obj) {
   ArrayRef<InputSectionBase *> sections(this->sections);
   SymbolTable &symtab = *elf::symtab;
 
   ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
   symbols.resize(eSyms.size());
-  SymbolUnion *locals =
-      firstGlobal == 0
-          ? nullptr
-          : getSpecificAllocSingleton<SymbolUnion>().Allocate(firstGlobal);
-
-  for (size_t i = 0, end = firstGlobal; i != end; ++i) {
-    const Elf_Sym &eSym = eSyms[i];
-    uint32_t secIdx = eSym.st_shndx;
-    if (LLVM_UNLIKELY(secIdx == SHN_XINDEX))
-      secIdx = check(getExtendedSymbolTableIndex<ELFT>(eSym, i, shndxTable));
-    else if (secIdx >= SHN_LORESERVE)
-      secIdx = 0;
-    if (LLVM_UNLIKELY(secIdx >= sections.size()))
-      fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
-    if (LLVM_UNLIKELY(eSym.getBinding() != STB_LOCAL))
-      error(toString(this) + ": non-local symbol (" + Twine(i) +
-            ") found at index < .symtab's sh_info (" + Twine(end) + ")");
-
-    InputSectionBase *sec = sections[secIdx];
-    uint8_t type = eSym.getType();
-    if (type == STT_FILE)
-      sourceFile = CHECK(eSym.getName(stringTable), this);
-    if (LLVM_UNLIKELY(stringTable.size() <= eSym.st_name))
-      fatal(toString(this) + ": invalid symbol name offset");
-    StringRef name(stringTable.data() + eSym.st_name);
-
-    symbols[i] = reinterpret_cast<Symbol *>(locals + i);
-    if (eSym.st_shndx == SHN_UNDEF || sec == &InputSection::discarded)
-      new (symbols[i]) Undefined(this, name, STB_LOCAL, eSym.st_other, type,
-                                 /*discardedSecIdx=*/secIdx);
-    else
-      new (symbols[i]) Defined(this, name, STB_LOCAL, eSym.st_other, type,
-                               eSym.st_value, eSym.st_size, sec);
-  }
 
   // Some entries have been filled by LazyObjFile.
   for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i)
     if (!symbols[i])
       symbols[i] = symtab.insert(CHECK(eSyms[i].getName(stringTable), this));
 
   // Perform symbol resolution on non-local symbols.
   SmallVector<unsigned, 32> undefineds;
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;
   }
 }
 
+template <class ELFT> void ObjFile<ELFT>::initializeLocalSymbols() {
+  if (!firstGlobal)
+    return;
+  SymbolUnion *locals;
+  {
+    static std::mutex mu;
+    std::lock_guard<std::mutex> lock(mu);
+    locals = getSpecificAllocSingleton<SymbolUnion>().Allocate(firstGlobal);
+  }
+
+  ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
+  for (size_t i = 0, end = firstGlobal; i != end; ++i) {
+    const Elf_Sym &eSym = eSyms[i];
+    uint32_t secIdx = eSym.st_shndx;
+    if (LLVM_UNLIKELY(secIdx == SHN_XINDEX))
+      secIdx = check(getExtendedSymbolTableIndex<ELFT>(eSym, i, shndxTable));
+    else if (secIdx >= SHN_LORESERVE)
+      secIdx = 0;
+    if (LLVM_UNLIKELY(secIdx >= sections.size()))
+      fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
+    if (LLVM_UNLIKELY(eSym.getBinding() != STB_LOCAL))
+      error(toString(this) + ": non-local symbol (" + Twine(i) +
+            ") found at index < .symtab's sh_info (" + Twine(end) + ")");
+
+    InputSectionBase *sec = sections[secIdx];
+    uint8_t type = eSym.getType();
+    if (type == STT_FILE)
+      sourceFile = CHECK(eSym.getName(stringTable), this);
+    if (LLVM_UNLIKELY(stringTable.size() <= eSym.st_name))
+      fatal(toString(this) + ": invalid symbol name offset");
+    StringRef name(stringTable.data() + eSym.st_name);
+
+    symbols[i] = reinterpret_cast<Symbol *>(locals + i);
+    if (eSym.st_shndx == SHN_UNDEF || sec == &InputSection::discarded)
+      new (symbols[i]) Undefined(this, name, STB_LOCAL, eSym.st_other, type,
+                                 /*discardedSecIdx=*/secIdx);
+    else
+      new (symbols[i]) Defined(this, name, STB_LOCAL, eSym.st_other, type,
+                               eSym.st_value, eSym.st_size, sec);
+  }
+}
+
+void elf::initializeLocalSymbols(ELFFileBase *file) {
+  switch (config->ekind) {
+  case ELF32LEKind:
+    cast<ObjFile<ELF32LE>>(file)->initializeLocalSymbols();
+    break;
+  case ELF32BEKind:
+    cast<ObjFile<ELF32BE>>(file)->initializeLocalSymbols();
+    break;
+  case ELF64LEKind:
+    cast<ObjFile<ELF64LE>>(file)->initializeLocalSymbols();
+    break;
+  case ELF64BEKind:
+    cast<ObjFile<ELF64BE>>(file)->initializeLocalSymbols();
+    break;
+  default:
+    llvm_unreachable("");
+  }
+}
+
 // 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.

lld/ELF/InputSection.cpp

 //   path/to/foo.o:(function bar) in archive path/to/bar.a
 std::string InputSectionBase::getObjMsg(uint64_t off) {
   std::string filename = std::string(file->getName());
 
   std::string archive;
   if (!file->archiveName.empty())
     archive = (" in archive " + file->archiveName).str();
 
-  // Find a symbol that encloses a given location.
+  // Find a symbol that encloses a given location. getObjMsg may be called
+  // before ObjFile::initializeLocalSymbols where local symbols are initialized.
   for (Symbol *b : file->getSymbols())
-    if (auto *d = dyn_cast<Defined>(b))
+    if (auto *d = dyn_cast_or_null<Defined>(b))
       if (d->section == this && d->value <= off && off < d->value + d->size)
         return filename + ":(" + toString(*d) + ")" + archive;
 
   // If there's no symbol, print out the offset in the section.
   return (filename + ":(" + name + "+0x" + utohexstr(off) + ")" + archive)
       .str();
 }
 

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:
 
 # 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