[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 ↗

(On Diff #76704)

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

ELF/SyntheticSections.cpp

61 ↗

(On Diff #76704)

doTree sounds a bit weird. Maybe something like computeHash.

62 ↗

(On Diff #76704)

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

63 ↗

(On Diff #76704)

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 ↗

(On Diff #76704)

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 ↗

(On Diff #76704)

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 ↗

(On Diff #76704)

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 ↗

(On Diff #76704)

Done.

ELF/SyntheticSections.cpp

61 ↗

(On Diff #76704)

Done.

62 ↗

(On Diff #76704)

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 ↗

(On Diff #76704)

Ok, done.

65–67 ↗

(On Diff #76704)

I expected that might be a bit faster. Removed.

69 ↗

(On Diff #76704)

Reimplemented.

96 ↗

(On Diff #76704)

Done.

[ruiu]

ELF/SyntheticSections.cpp

74–82 ↗

(On Diff #76847)

This can be simplified.

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

88 ↗

(On Diff #76847)

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

93 ↗

(On Diff #76847)

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

109 ↗

(On Diff #76847)

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

[grimar]

ELF/SyntheticSections.cpp

93 ↗

(On Diff #76847)

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

74–82 ↗

(On Diff #76847)

Done.

88 ↗

(On Diff #76847)

Done.

109 ↗

(On Diff #76847)

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

[ruiu]

LGTM

lld/trunk/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
+  computeHash(llvm::ArrayRef<uint8_t> Buf,
+              std::function<void(ArrayRef<uint8_t> Arr, uint8_t *Hash)> Hash);
+
+  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;
 };

lld/trunk/ELF/SyntheticSections.cpp

 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.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;
InterpSection<ELFT>::InterpSection()
     : InputSection<ELFT>(SHF_ALLOC, SHT_PROGBITS, 1, createInterp(),
                          ".interp") {
   this->Live = true;
 }
 
 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) {
   this->Live = true;
 
   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;
 }
 
+static std::vector<ArrayRef<uint8_t>> split(ArrayRef<uint8_t> Arr,
+                                            size_t ChunkSize) {
+  std::vector<ArrayRef<uint8_t>> Ret;
+  while (Arr.size() > ChunkSize) {
+    Ret.push_back(Arr.take_front(ChunkSize));
+    Arr = Arr.drop_front(ChunkSize);
+  }
+  if (!Arr.empty())
+    Ret.push_back(Arr);
+  return Ret;
+}
+
 template <class ELFT>
-void BuildIdFastHash<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
-  const endianness E = ELFT::TargetEndianness;
+void BuildIdSection<ELFT>::computeHash(
+    llvm::ArrayRef<uint8_t> Data,
+    std::function<void(ArrayRef<uint8_t> Arr, uint8_t *Hash)> Hash) {
+  std::vector<ArrayRef<uint8_t>> Chunks = split(Data, 1024 * 1024);
+  std::vector<uint8_t> HashList(Chunks.size() * HashSize);
+
+  if (Config->Threads)
+    parallel_for_each(Chunks.begin(), Chunks.end(),
+                      [&](ArrayRef<uint8_t> &Chunk) {
+                        size_t Id = &Chunk - Chunks.data();
+                        Hash(Chunk, HashList.data() + Id * HashSize);
+                      });
+  else
+    std::for_each(Chunks.begin(), Chunks.end(), [&](ArrayRef<uint8_t> &Chunk) {
+      size_t Id = &Chunk - Chunks.data();
+      Hash(Chunk, HashList.data() + Id * HashSize);
+    });
 
-  // 64-bit xxhash
-  uint64_t Hash = xxHash64(toStringRef(Buf));
-  write64<E>(this->getOutputLoc(Buf.begin()) + 16, Hash);
+  Hash(HashList, this->getOutputLoc((uint8_t *)Data.begin()) + 16);
+}
+
+template <class ELFT>
+void BuildIdFastHash<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
+  computeHash(Buf, [](ArrayRef<uint8_t> Arr, uint8_t *Dest) {
+    uint64_t Hash = xxHash64(toStringRef(Arr));
+    write64<ELFT::TargetEndianness>(Dest, Hash);
+  });
 }
 
 template <class ELFT>
 void BuildIdMd5<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
+  computeHash(Buf, [&](ArrayRef<uint8_t> Arr, uint8_t *Dest) {
     MD5 Hash;
-  Hash.update(Buf);
+    Hash.update(Arr);
     MD5::MD5Result Res;
     Hash.final(Res);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Res, 16);
+    memcpy(Dest, Res, HashSize);
+  });
 }
 
 template <class ELFT>
 void BuildIdSha1<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
+  computeHash(Buf, [&](ArrayRef<uint8_t> Arr, uint8_t *Dest) {
     SHA1 Hash;
-  Hash.update(Buf);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Hash.final().data(), 20);
+    Hash.update(Arr);
+    memcpy(Dest, Hash.final().data(), HashSize);
+  });
 }
 
 template <class ELFT>
 void BuildIdUuid<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
   if (getRandomBytes(this->getOutputLoc(Buf.begin()) + 16, 16))
     error("entropy source failure");
 }
 

lld/trunk/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: