[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

1159

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

1159

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

1159

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

static uint32_t getAndFeatures() {
 
   // Force enable Shadow Stack.
   if (config->zShstk)
     ret |= GNU_PROPERTY_X86_FEATURE_1_SHSTK;
 
   return ret;
 }
 
+static void 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("");
+  }
+}
+
 static void postParseObjectFile(ELFFileBase *file) {
   switch (config->ekind) {
   case ELF32LEKind:
     cast<ObjFile<ELF32LE>>(file)->postParse();
     break;
   case ELF32BEKind:
     cast<ObjFile<ELF32BE>>(file)->postParse();
     break;
void LinkerDriver::link(opt::InputArgList &args) {
   // libcall symbols will be added to the link after LTO when we add the LTO
   // object file to the link.
   if (!bitcodeFiles.empty())
     for (auto *s : lto::LTO::getRuntimeLibcallSymbols())
       handleLibcall(s);
 
   // No more lazy bitcode can be extracted at this point. Do post parse work
   // like checking duplicate symbols.
+  parallelForEach(objectFiles, initializeLocalSymbols);
   parallelForEach(objectFiles, postParseObjectFile);
   parallelForEach(bitcodeFiles, [](BitcodeFile *file) { file->postParse(); });
 
   // Return if there were name resolution errors.
   if (errorCount())
     return;
 
   // We want to declare linker script's symbols early,
void LinkerDriver::link(opt::InputArgList &args) {
 
   // Bail out if normal linked output is skipped due to LTO.
   if (skipLinkedOutput)
     return;
 
   // compileBitcodeFiles may have produced lto.tmp object files. After this, no
   // more file will be added.
   auto newObjectFiles = makeArrayRef(objectFiles).slice(numObjsBeforeLTO);
+  parallelForEach(newObjectFiles, initializeLocalSymbols);
   parallelForEach(newObjectFiles, postParseObjectFile);
 
   // 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);
 

lld/ELF/InputFiles.h

 //===- InputFiles.h ---------------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_INPUT_FILES_H
 #define LLD_ELF_INPUT_FILES_H
 
 #include "Config.h"
+#include "Symbols.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Reproduce.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/BinaryFormat/Magic.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/MemoryBufferRef.h"
 #include "llvm/Support/Threading.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();
 
private:
   // contain .symtab_shndx section. The section contains an array of
   // 32-bit integers whose size is the same as the number of symbols.
   // Nth symbol's section index is in the Nth entry of .symtab_shndx.
   //
   // The following variable contains the contents of .symtab_shndx.
   // If the section does not exist (which is common), the array is empty.
   ArrayRef<Elf_Word> shndxTable;
 
+  // Storage for local symbols.
+  std::unique_ptr<SymbolUnion[]> localSymStorage;
+
   // Debugging information to retrieve source file and line for error
   // reporting. Linker may find reasonable number of errors in a
   // single object file, so we cache debugging information in order to
   // parse it only once for each object file we link.
   std::unique_ptr<DWARFCache> dwarf;
   llvm::once_flag initDwarf;
 };
 

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);
-    symbols[i]->isUsedInRegularObj = true;
-  }
 
   // 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) {
     Symbol *sym = symbols[i];
     sym->resolve(Undefined{this, StringRef(), eSym.getBinding(), eSym.st_other,
                            eSym.getType()});
     sym->isUsedInRegularObj = true;
     sym->referenced = true;
   }
 }
 
+template <class ELFT> void ObjFile<ELFT>::initializeLocalSymbols() {
+  if (!firstGlobal)
+    return;
+  localSymStorage = std::make_unique<SymbolUnion[]>(firstGlobal);
+  SymbolUnion *locals = localSymStorage.get();
+
+  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);
+    symbols[i]->isUsedInRegularObj = 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];
 
     // st_value of STT_TLS represents the assigned offset, not the actual
     // address which is used by STT_FUNC and STT_OBJECT. STT_TLS symbols can
     // only be referenced by special TLS relocations. It is usually an error if
     // a STT_TLS symbol is replaced by a non-STT_TLS symbol, vice versa.

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();
 }