[ELF] - Implemented threaded --build-id computation

[grimar]

Summary

Patch switches computing of --build-id hash to tree.

This is the way when input data is splitted by chunks,
hash is computed for each one in threaded/non-threaded way.
At the end hash is conputed for result tree.

With or without -threads the result hash is the same.

[ruiu]

I don't think we want to add one more different type of --build-id= option because we already have too many. We probably should use threads by default for "fast", "sha1" and "md5".

[grimar]

• Reimplemented according to review comments.

Now each algorithm is threaded if -threads option used.

[ruiu]

ELF/Config.h

147

There's no real benefit to make it customziable, so please remove from Config.

ELF/SyntheticSections.cpp

61

doTree sounds a bit weird. Maybe something like computeHash.

62

You don't have to pass Buf because it's a class member.

63

Please don't name Job or Worker because they sound like high level stuffs. They are in fact just an ArrayRef and a callback function.

65–67

This is not a tree but an array.

I don't know why you are using the global allocator here. This can be a local std::vector variable, no?

69

I think I don't understand the code. So, basically, what you want to do in this function is

1. Split Buf into small chunks. So we need a function, say split(), which takes an ArrayRef<uint8_t> and returns std::vector<ArrayRef<uint8_t>>.
2. Call a callback for each chunk.
3. And then compute the final hash.

What we need to do here is not too complicated, so I think you can simplify the code.

96

You can directly pass DoHash to the function, e.g., doTree(Buf, DoHash). Dohash sounds a bit weird too, but you don't really name it in this context.

doTree(Buf, [](...) {
  ...
});

[emaste]

ELF/InputSection.cpp

897 ↗

(On Diff #76582)

This seems like a strange combination. Why not just SHAx?

907 ↗

(On Diff #76582)

We don't have a way to select another size so "default" doesn't seem right

[emaste]

(Sorry, comments were on an old version of the patch)

[grimar]

In D26199#586312, @emaste wrote:

(Sorry, comments were on an old version of the patch)

Just in case:

Why not just SHAx?

That seems how gold do. I am interested myself why such mix was implemented.
(https://sourceware.org/ml/binutils/2013-04/msg00134/t.patch).

Anyways current version looks much better for me.

[grimar]

Addressed review comments.

ELF/Config.h

147

Done.

ELF/SyntheticSections.cpp

61

Done.

62

I have to. Argument Buf was a data to hash, it is not the same that member which is a section content.
I renamed argument to Data to avoid confusion (actually I did not notice the member with the same name when wrote it).

63

Ok, done.

65–67

I expected that might be a bit faster. Removed.

69

Reimplemented.

96

Done.

[ruiu]

ELF/SyntheticSections.cpp

63–71

This can be simplified.

while (Arr.size() > ChunkSize) {
  Ret.push_back(...);
  Arr = Arr.drop_front...;
}
if (!Arr.empty())
  Ret.push_back(Arr);
return Ret;

93

Cb is not a good name. Let's name Hash.

98

You can always call parallel_for_each. If multi-threads are not available, it will fall back to std::for_each.

101

Replace [&] with [] because I think it doesn't capture anything. (And ditto for other functions.)

[grimar]

ELF/SyntheticSections.cpp

98

Why we do that check in
void OutputSection<ELFT>::writeTo(uint8_t *Buf) then ?

if (Config->Threads) {
  parallel_for_each(Sections.begin(), Sections.end(),
                    [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
} else {
  for (InputSection<ELFT> *C : Sections)
    C->writeTo(Buf);
}

I was thinking that it is for user to decide, if he/she uses -threads in command line, then threading is used if possible in LLD.
I think that might be helpfull. And also as I mentioned is consistent with OutputSection<ELFT>::writeTo.

[grimar]

• Addressed review comments.

ELF/SyntheticSections.cpp

63–71

Done.

93

Done.

101

Removed & here, but others lambdas below still needs to capture HashSize.

[ruiu]

LGTM

ELF/Config.h

struct Configuration {
   BuildIdKind BuildId = BuildIdKind::None;
   ELFKind EKind = ELFNoneKind;
   uint16_t DefaultSymbolVersion = llvm::ELF::VER_NDX_GLOBAL;
   uint16_t EMachine = llvm::ELF::EM_NONE;
   uint64_t EntryAddr = 0;
   uint64_t ImageBase;
   uint64_t MaxPageSize;
   uint64_t ZStackSize;
+  unsigned BuildIdChunkSize = 1024 * 1024;
   unsigned LtoPartitions;
   unsigned LtoO;
   unsigned Optimize;
   unsigned ThinLtoJobs;
 };
 
 // The only instance of Configuration struct.
 extern Configuration *Config;
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SyntheticSections.h

public:
   virtual void writeBuildId(llvm::MutableArrayRef<uint8_t> Buf) = 0;
   virtual ~BuildIdSection() = default;
 
   uint8_t *getOutputLoc(uint8_t *Start) const;
 
 protected:
   BuildIdSection(size_t HashSize);
   std::vector<uint8_t> Buf;
+
+  void doTree(llvm::ArrayRef<uint8_t> Buf,
+              std::function<void(ArrayRef<uint8_t> Job, uint8_t *Dest)> Worker);
+
+  size_t HashSize;
 };
 
 template <class ELFT>
 class BuildIdFastHash final : public BuildIdSection<ELFT> {
 public:
   BuildIdFastHash() : BuildIdSection<ELFT>(8) {}
   void writeBuildId(llvm::MutableArrayRef<uint8_t> Buf) override;
 };

ELF/SyntheticSections.cpp

 // input sections.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SyntheticSections.h"
 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
+#include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 
+#include "lld/Core/Parallel.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 template <class ELFT>
 BuildIdSection<ELFT>::BuildIdSection(size_t HashSize)
     : InputSection<ELFT>(SHF_ALLOC, SHT_NOTE, 1, ArrayRef<uint8_t>(),
-                         ".note.gnu.build-id") {
+                         ".note.gnu.build-id"),
+      HashSize(HashSize) {
   Buf.resize(16 + HashSize);
   const endianness E = ELFT::TargetEndianness;
   write32<E>(Buf.data(), 4);                   // Name size
   write32<E>(Buf.data() + 4, HashSize);        // Content size
   write32<E>(Buf.data() + 8, NT_GNU_BUILD_ID); // Type
   memcpy(Buf.data() + 12, "GNU", 4);           // Name string
   this->Data = ArrayRef<uint8_t>(Buf);
 }
 
 template <class ELFT>
 uint8_t *BuildIdSection<ELFT>::getOutputLoc(uint8_t *Start) const {
   return Start + this->OutSec->getFileOffset() + this->OutSecOff;
 }
 
 template <class ELFT>
+void BuildIdSection<ELFT>::doTree(
+    llvm::ArrayRef<uint8_t> Buf,
+    std::function<void(ArrayRef<uint8_t> Job, uint8_t *Dest)> Worker) {
+  size_t NumChunks = (Buf.size() - 1) / Config->BuildIdChunkSize + 1;
+  MutableArrayRef<uint8_t> Tree = {
+      BAlloc.template Allocate<uint8_t>(NumChunks * HashSize),
+      NumChunks * HashSize};
+
+  auto CallWorker = [&](size_t Id) {
+    ArrayRef<uint8_t> Part = Buf.drop_front(Id * Config->BuildIdChunkSize)
+                                 .take_front(Config->BuildIdChunkSize);
+    Worker(Part, Tree.data() + Id * HashSize);
+  };
+
+  std::vector<size_t> Tasks(NumChunks);
+  for (size_t I = 0; I < NumChunks; ++I)
+    Tasks[I] = I;
+
+  if (Config->Threads)
+    parallel_for_each(Tasks.begin(), Tasks.end(),
+                      [=](size_t Id) { CallWorker(Id); });
+  else
+    std::for_each(Tasks.begin(), Tasks.end(),
+                  [=](size_t Id) { CallWorker(Id); });
+
+  Worker(Tree, this->getOutputLoc((uint8_t *)Buf.begin()) + 16);
+}
+
+template <class ELFT>
 void BuildIdFastHash<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
-  const endianness E = ELFT::TargetEndianness;
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
+    uint64_t Hash = xxHash64(toStringRef(Job));
+    write64<ELFT::TargetEndianness>(Dest, Hash);
+  };
 
-  // 64-bit xxhash
-  uint64_t Hash = xxHash64(toStringRef(Buf));
-  write64<E>(this->getOutputLoc(Buf.begin()) + 16, Hash);
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
 void BuildIdMd5<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
     MD5 Hash;
-  Hash.update(Buf);
+    Hash.update(Job);
     MD5::MD5Result Res;
     Hash.final(Res);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Res, 16);
+    memcpy(Dest, Res, HashSize);
+  };
+
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
 void BuildIdSha1<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
     SHA1 Hash;
-  Hash.update(Buf);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Hash.final().data(), 20);
+    Hash.update(Job);
+    memcpy(Dest, Hash.final().data(), HashSize);
+  };
+
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
 void BuildIdUuid<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
   if (getRandomBytes(this->getOutputLoc(Buf.begin()) + 16, 16))
     error("entropy source failure");
 }
 

test/ELF/build-id.s

 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=UUID %s
 # RUN: ld.lld --build-id=0x12345678 %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=HEX %s
 # RUN: ld.lld %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NONE %s
 # RUN: ld.lld --build-id=md5 --build-id=none %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NONE %s
 
+## Multithreaded cases:
+# RUN: ld.lld --build-id -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=DEFAULT %s
+# RUN: ld.lld --build-id=md5 -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=MD5 %s
+# RUN: ld.lld --build-id=sha1 -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SHA1 %s
+
 .globl _start
 _start:
   nop
 
 .section .note.test, "a", @note
    .quad 42
 
 # DEFAULT:      Contents of section .note.test:
 # DEFAULT:      Contents of section .note.gnu.build-id:
 # DEFAULT-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
+# DEFAULT-NEXT: ab
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
+# MD5-NEXT: 29
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
+# SHA1-NEXT: b1
+
+# TREE:      Contents of section .note.gnu.build-id:
+# TREE-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
+# TREE-NEXT: 18
 
 # UUID:      Contents of section .note.gnu.build-id:
 # UUID-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
 
 # HEX:      Contents of section .note.gnu.build-id:
 # HEX-NEXT: 04000000 04000000 03000000 474e5500  ............GNU.
 # HEX-NEXT: 12345678
 
 # NONE-NOT: Contents of section .note.gnu.build-id: