[lld][Driver] Parallelize reading initial object files.

[shankarke]

I think it would be nice to have an option to not use any threads, for debugging / testing purposes. It could also be an option to benchmark / experiment things with number of threads spawned inside the thread pool.

lib/Driver/Driver.cpp

47

Why you want this to be atomic bool ? because you are only setting the value to be true and the check/return is done only after all the threads have got synced ?

Also it would be essential to check if there was a failure reading one of the files before reading the next set of files.

For example:

Say thread concurrency = 2

TG created 2 threads and there were 4 files

Say there was an error reading file 1 (or) file 2. You could stop file 3/4 from being read.

62–67

Isnt using index a problem with archive files.

--force-load-archive option / multiple archive files getting pulled in ?

lib/ReaderWriter/ELF/ELFTargetInfo.cpp

95–120 ↗

(On Diff #1614)

I think we could create the _elfReader/_yamlReader/_linkerScriptReader as soon as ELFTargetInfo is initialized. Because after the first time the _elfReader/_yamlReader/_linkerScriptReader is initialized, you dont need the locks. This implementation will lock them and make it slower too, because of the locks / unlocks being done multiple times.

lib/ReaderWriter/ELF/File.h

314

did you mean iterate over sections by their positions in the object file ?

315–325

Was there an issue earlier ?

[shankarke]

In future may be, atoms from each section can be parallelized too, which will make the reader very powerful. The references vector may need to change.

What do you think ?

[Bigcheese]

lib/Driver/Driver.cpp

47

It has to be atomic because it could be written from multiple threads.

I don't see why it's essential to early exit the other tasks. It is indeed possible though. Just check the value of fail.

62–67

files is a std::vector<std::vector<std::unique_ptr<File>>>. Each input argument gets a std::vector.

lib/ReaderWriter/ELF/ELFTargetInfo.cpp

95–120 ↗

(On Diff #1614)

k

lib/ReaderWriter/ELF/File.h

314

Yes, that's what that says.

315–325

I changed sectionSymbols to a DenseMap instead of a std::map. This is required because DenseMap is unordered.

[Bigcheese]

In future may be, atoms from each section can be parallelized too, which will make the reader very powerful. The references vector may need to change.

What do you think ?

A reader can do this, sure. We just need to ensure the section is large enough to overcome the cost of creating a task.

[shankarke]

lib/Driver/Driver.cpp

47

But all threads would write only a value true. Atomic would be needed only if one thread is writing true and other false, and you need to sync between them right ?

Say that 3.o and 4.o were very huge files. Linker is going to anyways exit with an error, I see no point of reading 3.o / 4.o.

62–67

ah ok.

[Bigcheese]

lib/Driver/Driver.cpp

47

[intro.multithreaded] 4 Two expression evaluations conflict if one of them modifies a memory location (1.7) and the other one accesses or modifies the same memory location.

[intro.multithreaded] 21 The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior.

Thus synchronization is required.

And yes, early exit is desirable.

[kledzik]

lib/Driver/Driver.cpp

53–67

Is there a reason why the high level readFile() in the original was split up into its two low level steps of getBuffer() and parseFile()? Using the low level steps makes this code more complicated.

Also, if multiple files have errors, you can get intermixed error message since you have lots of threads writing to diagnostics at once. Another way would be to have a parallel array of error_codes and each thread/lambda just sets its error code in ec[index] and returns. Then after the tg.sync(), you walk the ec array in order and if there is an error, you write it out. That way every run results in the same error messages in the same order, and you don't need the atomic "fail" anymore (unless you want it to terminate early).

[Bigcheese]

lib/Driver/Driver.cpp

53–67

It uses getBuffer and parseFile so that we don't mmap the file multiple times.

Good idea for synchronizing the errors.

[kledzik]

lib/Driver/Driver.cpp

53–67

The multiple mappings is independent of this parallelization (i.e. could be separate patch). We should overload readFile() to take a LinkerInput or a path.

Sometimes the reader needs to take ownership of the buffer and sometimes it does not. Which is why parseFile() takes the unique_ptr<MemoryBuffer> by reference. This intermediate getMemBuffer() object muddies the water.

[Bigcheese]

Address comments and split out reader fix.

[shankarke]

LGTM.

[ruiu]

Resurrecting the old thread.

I'm thinking to rewrite the concurrent file parsing part using std::future and std::async. We can get performance benefit from doing that, as the core linker will not have to wait all the input files to be parsed (but instead will be blocked when it tries to use a future which is not ready). It will also simplifies the code because it's the standard library.

What I'm wondering is why this code did not use std::future and std::async from the beginning. Was there any reason to avoid that?

[ruiu]

I'll start writing a patch to use std::future to represent a file object which may or may not be being parsed. If there's an issue, please yell at me.

lib/Driver/Driver.cpp

 //===- lib/Driver/Driver.cpp - Linker Driver Emulator ---------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lld/Driver/Driver.h"
+
 #include "lld/Core/LLVM.h"
 #include "lld/Core/InputFiles.h"
-#include "lld/Core/Resolver.h"
 #include "lld/Core/PassManager.h"
+#include "lld/Core/Parallel.h"
+#include "lld/Core/Resolver.h"
 #include "lld/ReaderWriter/Reader.h"
 #include "lld/ReaderWriter/Writer.h"
 
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
if (!targetInfo.llvmOptions().empty()) {
     args[0] = "lld (LLVM option parsing)";
     for (unsigned i = 0; i != numArgs; ++i)
       args[i + 1] = targetInfo.llvmOptions()[i];
     args[numArgs + 1] = 0;
     llvm::cl::ParseCommandLineOptions(numArgs + 1, args);
   }
 
   // Read inputs
-  InputFiles inputs;
+  std::vector<std::vector<std::unique_ptr<File>>> files(
+      targetInfo.inputFiles().size());
+  size_t index = 0;
+  std::atomic<bool> fail(false);
+  TaskGroup tg;
   for (const auto &input : targetInfo.inputFiles()) {
-    std::vector<std::unique_ptr<File>> files;
     if (targetInfo.logInputFiles())
       llvm::outs() << input.getPath() << "\n";
-      
-    error_code ec = targetInfo.readFile(input.getPath(), files);
-    if (ec) {
-      diagnostics   << "Failed to read file: " << input.getPath() << ": "
-                    << ec.message() << "\n";
-      return true;
+    tg.spawn([&, index] {
+      if (error_code ec = targetInfo.readFile(input.getPath(), files[index])) {
+        diagnostics << "Failed to read file: " << input.getPath()
+                    << ": " << ec.message() << "\n";
+        fail = true;
+        return;
       }
-    inputs.appendFiles(files);
+    });
+    ++index;
   }
+  tg.sync();
+
+  if (fail)
+    return true;
+
+  InputFiles inputs;
+  for (auto &f : files)
+    inputs.appendFiles(f);
 
   // Give target a chance to add files.
   targetInfo.addImplicitFiles(inputs);
 
   // assign an ordinal to each file so sort() can preserve command line order
   inputs.assignFileOrdinals();
 
   // Do core linking.

lib/ReaderWriter/ELF/File.h

template <class ELFT> class ELFFile : public File {
   MergeAtomsIter findMergeAtom(const Elf_Shdr *shdr, uint64_t offset) {
     return std::find_if(_mergeAtoms.begin(), _mergeAtoms.end(),
                         FindByOffset(shdr, offset));
   }
 
   typedef std::unordered_map<MergeSectionKey, DefinedAtom *, MergeSectionEq,
                              MergeSectionEq> MergedSectionMapT;
   typedef typename MergedSectionMapT::iterator MergedSectionMapIterT;
+  typedef llvm::DenseMap<const Elf_Shdr *, std::vector<const Elf_Sym *>>
+      SectionSymbolsT;
 
 public:
   ELFFile(const ELFTargetInfo &ti, StringRef name)
       : File(name, kindObject), _elfTargetInfo(ti) {}
 
   ELFFile(const ELFTargetInfo &ti, std::unique_ptr<llvm::MemoryBuffer> MB,
           llvm::error_code &EC)
       : File(MB->getBufferIdentifier(), kindObject), _elfTargetInfo(ti) {
ELFFile(const ELFTargetInfo &ti, std::unique_ptr<llvm::MemoryBuffer> MB,
 
     if (!_objFile) {
       EC = make_error_code(llvm::object::object_error::invalid_file_type);
       return;
     }
 
     binaryFile.take();
 
-    std::map<const Elf_Shdr *, std::vector<const Elf_Sym *> > sectionSymbols;
+    /// \brief Map from sections to a list of symbols that section contains.
+    SectionSymbolsT sectionSymbols;
 
     // Sections that have merge string property
     std::vector<const Elf_Shdr *> mergeStringSections;
 
     bool doStringsMerge = _elfTargetInfo.mergeCommonStrings();
 
     // Handle: SHT_REL and SHT_RELA sections:
     // Increment over the sections, when REL/RELA section types are found add
for (; it != ie; it.increment(EC)) {
         } else {
           llvm::errs() << "Unable to create atom for: " << symbolName << "\n";
           EC = llvm::object::object_error::parse_failed;
           return;
         }
       }
     }
 
+    // Iterate over sections by object file position. The pointers point into
+    // the memory mapped file, so it's valid to sort based on them.
+    std::vector<typename SectionSymbolsT::value_type *> secSyms;
+    secSyms.reserve(sectionSymbols.size());
     for (auto &i : sectionSymbols) {
-      auto &symbols = i.second;
+      secSyms.push_back(&i);
+    }
+    std::sort(secSyms.begin(), secSyms.end(),
+              [](const typename SectionSymbolsT::value_type *a,
+                 const typename SectionSymbolsT::value_type *b) {
+       return a->first < b->first;
+    });
+
+    for (auto &i : secSyms) {
+      auto &symbols = i->second;
       // Sort symbols by position.
       std::stable_sort(symbols.begin(), symbols.end(),
                        [](const Elf_Sym * A, const Elf_Sym * B) {
         return A->st_value < B->st_value;
       });
 
       StringRef sectionContents;
-      if ((EC = _objFile->getSectionContents(i.first, sectionContents)))
+      if ((EC = _objFile->getSectionContents(i->first, sectionContents)))
         return;
 
       StringRef sectionName;
-      if ((EC = _objFile->getSectionName(i.first, sectionName)))
+      if ((EC = _objFile->getSectionName(i->first, sectionName)))
         return;
 
       // If the section has no symbols, create a custom atom for it.
-      if (i.first->sh_type == llvm::ELF::SHT_PROGBITS && symbols.empty() &&
+      if (i->first->sh_type == llvm::ELF::SHT_PROGBITS && symbols.empty() &&
           !sectionContents.empty()) {
         Elf_Sym *sym = new (_readerStorage) Elf_Sym;
         sym->st_name = 0;
         sym->setBindingAndType(llvm::ELF::STB_LOCAL, llvm::ELF::STT_SECTION);
         sym->st_other = 0;
         sym->st_shndx = 0;
         sym->st_value = 0;
         sym->st_size = 0;
         ArrayRef<uint8_t> content((const uint8_t *)sectionContents.data(),
                                   sectionContents.size());
         auto newAtom = new (_readerStorage)
-            ELFDefinedAtom<ELFT>(*this, sectionName, sectionName, sym, i.first,
+            ELFDefinedAtom<ELFT>(*this, sectionName, sectionName, sym, i->first,
                                  content, 0, 0, _references);
         newAtom->setOrdinal(++ordinal);
         _definedAtoms._atoms.push_back(newAtom);
       }
 
       ELFDefinedAtom<ELFT> *previous_atom = nullptr;
       // Don't allocate content to a weak symbol, as they may be merged away.
       // Create an anonymous atom to hold the data.
       ELFDefinedAtom<ELFT> *anonAtom = nullptr;
       ELFReference<ELFT> *anonPrecededBy = nullptr;
       ELFReference<ELFT> *anonFollowedBy = nullptr;
 
-      // i.first is the section the symbol lives in
+      // i->first is the section the symbol lives in
       for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
         StringRef symbolName;
-        if ((EC = _objFile->getSymbolName(i.first, *si, symbolName)))
+        if ((EC = _objFile->getSymbolName(i->first, *si, symbolName)))
           return;
 
         const Elf_Shdr *section = _objFile->getSection(*si);
 
         bool isCommon = (*si)->getType() == llvm::ELF::STT_COMMON ||
                         (*si)->st_shndx == llvm::ELF::SHN_COMMON;
 
         if ((section && section->sh_flags & llvm::ELF::SHF_MASKPROC) ||
             (((*si)->st_shndx >= llvm::ELF::SHN_LOPROC) &&
              ((*si)->st_shndx <= llvm::ELF::SHN_HIPROC))) {
           TargetHandler<ELFT> &TargetHandler =
               _elfTargetInfo.template getTargetHandler<ELFT>();
           TargetAtomHandler<ELFT> &elfAtomHandler =
               TargetHandler.targetAtomHandler();
           int64_t targetSymType = elfAtomHandler.getType(*si);
 
           if (targetSymType == llvm::ELF::STT_COMMON)
             isCommon = true;
         }
 
         // Get the symbol's content:
         uint64_t contentSize;
         if (si + 1 == se) {
           // if this is the last symbol, take up the remaining data.
-          contentSize = isCommon ? 0 : i.first->sh_size - (*si)->st_value;
+          contentSize = isCommon ? 0 : i->first->sh_size - (*si)->st_value;
         } else {
           contentSize = isCommon ? 0 : (*(si + 1))->st_value - (*si)->st_value;
         }
 
         // Check to see if we need to add the FollowOn Reference
         // We dont want to do for symbols that are
         // a) common symbols
         ELFReference<ELFT> *followOn = nullptr;
for (auto &i : secSyms) {
         anonPrecededBy = nullptr;
         anonFollowedBy = nullptr;
         if ((*si)->getBinding() == llvm::ELF::STB_WEAK && contentSize != 0) {
           // Create a new non-weak ELF symbol.
           auto sym = new (_readerStorage) Elf_Sym;
           *sym = **si;
           sym->setBinding(llvm::ELF::STB_GLOBAL);
           anonAtom = createDefinedAtomAndAssignRelocations(
-              "", sectionName, sym, i.first,
+              "", sectionName, sym, i->first,
               ArrayRef<uint8_t>(
                   (uint8_t *)sectionContents.data() + (*si)->st_value,
                   contentSize));
           anonAtom->setOrdinal(++ordinal);
 
           // If this is the last atom, lets not create a followon
           // reference
           if ((si + 1) != se)
for (auto &i : secSyms) {
                 *this, symbolName, sectionName, (*si), section, symbolData,
                 _references.size(), _references.size(), _references);
             _definedAtoms._atoms.push_back(definedMergeAtom);
           }
           continue;
         }
 
         auto newAtom = createDefinedAtomAndAssignRelocations(
-            symbolName, sectionName, *si, i.first, symbolData);
+            symbolName, sectionName, *si, i->first, symbolData);
 
         newAtom->setOrdinal(++ordinal);
 
         // If the atom was a weak symbol, lets create a followon
         // reference to the anonymous atom that we created
         if ((*si)->getBinding() == llvm::ELF::STB_WEAK && anonAtom) {
           ELFReference<ELFT> *wFollowedBy = new (_readerStorage)
               ELFReference<ELFT>(lld::Reference::kindLayoutAfter);
ELFDefinedAtom<ELFT> *createDefinedAtomAndAssignRelocations(
     auto rari = _relocationAddendRefences.find(sectionName);
     auto rri = _relocationReferences.find(sectionName);
     if (rari != _relocationAddendRefences.end())
       for (auto &rai : rari->second) {
         if (!((rai.r_offset >= symbol->st_value) &&
               (rai.r_offset < symbol->st_value + content.size())))
           continue;
         bool isMips64EL = _objFile->isMips64EL();
-        Kind kind = (Kind) rai.getType(isMips64EL);
+        Reference::Kind kind = (Reference::Kind) rai.getType(isMips64EL);
         uint32_t symbolIndex = rai.getSymbol(isMips64EL);
         auto *ERef = new (_readerStorage)
             ELFReference<ELFT>(&rai, rai.r_offset - symbol->st_value, nullptr,
                                kind, symbolIndex);
         _references.push_back(ERef);
       }
 
     // Add Rel references.
     if (rri != _relocationReferences.end())
       for (auto &ri : rri->second) {
         if ((ri.r_offset >= symbol->st_value) &&
             (ri.r_offset < symbol->st_value + content.size())) {
           bool isMips64EL = _objFile->isMips64EL();
-          Kind kind = (Kind) ri.getType(isMips64EL);
+          Reference::Kind kind = (Reference::Kind) ri.getType(isMips64EL);
           uint32_t symbolIndex = ri.getSymbol(isMips64EL);
           auto *ERef = new (_readerStorage)
               ELFReference<ELFT>(&ri, ri.r_offset - symbol->st_value, nullptr,
                                  kind, symbolIndex);
           // Read the addend from the section contents
           // TODO : We should move the way lld reads relocations totally from
           // ELFObjectFile
           int32_t addend = *(content.data() + ri.r_offset - symbol->st_value);