[lld] fix data race in ELF/ICF.cpp

[inglorion]

Summary

r328610 fixed a data race in the COFF linker. This change makes a
similar fix to the ELF linker.

[ruiu]

LGTM

lld/ELF/ICF.cpp

399 ↗

(On Diff #140710)

This looks a bit too dense, so please insert a newline here

402 ↗

(On Diff #140710)

and here

[inglorion]

Thanks, ruiu. Added the newlines before committing.

lld/trunk/ELF/ICF.cpp

if (Class != Sections[I]->Class[Current])
       return I;
   return End;
 }
 
 // Sections in the same equivalence class are contiguous in Sections
 // vector. Therefore, Sections vector can be considered as contiguous
 // groups of sections, grouped by the class.
 //
-// This function calls Fn on every group that starts within [Begin, End).
-// Note that a group must start in that range but doesn't necessarily
-// have to end before End.
+// This function calls Fn on every group within [Begin, End).
 template <class ELFT>
 void ICF<ELFT>::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, Sections.size());
+    size_t Mid = findBoundary(Begin, End);
     Fn(Begin, Mid);
     Begin = Mid;
   }
 }
 
 // Call Fn on each equivalence class.
 template <class ELFT>
 void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
   // If threading is disabled or the number of sections are
   // too small to use threading, call Fn sequentially.
   if (!ThreadsEnabled || Sections.size() < 1024) {
     forEachClassRange(0, Sections.size(), Fn);
     ++Cnt;
     return;
   }
 
   Current = Cnt % 2;
   Next = (Cnt + 1) % 2;
 
-  // 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 = Sections.size() / NumShards;
-  parallelForEachN(0, NumShards, [&](size_t I) {
-    size_t End = (I == NumShards - 1) ? Sections.size() : (I + 1) * Step;
-    forEachClassRange(I * Step, End, Fn);
+  size_t Boundaries[NumShards + 1];
+  Boundaries[0] = 0;
+  Boundaries[NumShards] = Sections.size();
+
+  parallelForEachN(1, NumShards, [&](size_t I) {
+    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
+  });
+
+  parallelForEachN(1, NumShards + 1, [&](size_t I) {
+    if (Boundaries[I - 1] < Boundaries[I])
+      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
   });
   ++Cnt;
 }
 
 static void print(const Twine &S) {
   if (Config->PrintIcfSections)
     message(S);
 }