[lld] fix data race in ICF.cpp

[inglorion]

Summary

Fixes PR36823.

[inglorion]

ruiu informs me similar code exists in the other ports. Let's get this reviewed first and then I'll update the others.

[ruiu]

Generally looking good.

lld/COFF/ICF.cpp

203–214

This doubles the total number of computation because you call findBoundary calls twice for each iteration. I wonder if we need to parallelize this in the first place. Maybe it is better to do this with a regular for loop?

208–211

I would allocate NumShards+1 elements for Boundaries and set Boundaries[0] to 0, so that we don't need to special-case I==0.

[inglorion]

Removed double computation of boundaries and special case for I == 0.

[inglorion]

lld/COFF/ICF.cpp

203–214

Ah, yeah. I meant to make this call findBoundary once per shard. Fixed in new upload.

208–211

Good idea! Done.

[inglorion]

removed log message

[inglorion]

This passes tests and links all of chromium without tsan failures, but the resulting component_unittests.exe crashes.

[ruiu]

LGTM

[inglorion]

Fixed off-by-one error: LLVM's for_each_n takes an end index, not a count

[inglorion]

This now generates a components_unittests.exe that is the same size as without this change that works correctly. I also verified that the data race is gone on COFF. I will land this to give the bots a chance to chew on it, and then fix the same data race in the ELF linker.

lld/COFF/ICF.cpp

auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
         return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
     return false;
   };
   return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
 }
 
+// Find the first Chunk after Begin that has a different class from Begin.
 size_t ICF::findBoundary(size_t Begin, size_t End) {
   for (size_t I = Begin + 1; I < End; ++I)
     if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
       return I;
   return End;
 }
 
 void ICF::forEachClassRange(size_t Begin, size_t End,
                             std::function<void(size_t, size_t)> Fn) {
-  if (Begin > 0)
-    Begin = findBoundary(Begin - 1, End);
-
   while (Begin < End) {
-    size_t Mid = findBoundary(Begin, Chunks.size());
+    size_t Mid = findBoundary(Begin, End);
     Fn(Begin, Mid);
     Begin = Mid;
   }
 }
 
 // Call Fn on each class group.
 void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
   // If the number of sections are too small to use threading,
   // call Fn sequentially.
   if (Chunks.size() < 1024) {
     forEachClassRange(0, Chunks.size(), Fn);
     ++Cnt;
     return;
   }
 
-  // Split sections into 256 shards and call Fn in parallel.
-  size_t NumShards = 256;
+  // Shard into non-overlapping intervals, and call Fn in parallel.
+  // The sharding must be completed before any calls to Fn are made
+  // so that Fn can modify the Chunks in its shard without causing data
+  // races.
+  const size_t NumShards = 256;
   size_t Step = Chunks.size() / NumShards;
-  for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
-    size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step;
-    forEachClassRange(I * Step, End, Fn);
+  size_t Boundaries[NumShards + 1];
+  Boundaries[0] = 0;
+  Boundaries[NumShards] = Chunks.size();
+  for_each_n(parallel::par, size_t(1), NumShards, [&](size_t I) {
+    Boundaries[I] = findBoundary((I - 1) * Step, Chunks.size());
+  });
+  for_each_n(parallel::par, size_t(1), NumShards + 1, [&](size_t I) {
+    if (Boundaries[I - 1] < Boundaries[I]) {
+      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
+    }
   });
   ++Cnt;
 }
 
 // Merge identical COMDAT sections.
 // Two sections are considered the same if their section headers,
 // contents and relocations are all the same.
 void ICF::run(ArrayRef<Chunk *> Vec) {
   ScopedTimer T(ICFTimer);