Fix a potential infinite loop in the case of an interruption.

joeleba · copybara-github · commit d70592850908 · 2024-06-05T07:52:55.000-07:00
**The Issue** Some external users reported the following sequence: 1. Build starts 2. Build interrupted very early on 3. Another build is started. The command line says "A previous command is running", while the server is stuck. What happened under the hood: The issue could be reproduced very reliably by placing a breakpoint here[1] and interrupt the build. Bazel is in the middle of the recursive `IncrementalPackageRoots.registerAndPlantMissingSymlinks` method when it received the interruption. One important detail: we only add a NestedSet to the `donePackagesRef` set when the _method_ is done successfully. When there's an interruption, we always bail early and never actually reach this line where the NestedSet is added to the set[2]. Without deduplication, this could lead to what feels like an finite loop if the packages are structured like so: ``` [[A], [B, [A]]] ``` In this case, NestedSet `[A]` represents a common child of many NestedSets and would be repeated again and again. We've indeed observed this in a real build, making it unable to finish within any reasonable timeframe. **The Solution** It was overly restrictive to only commit a NestedSet into the de-dup set _after_ all of its symlinks have been planted. It only makes sense if we're planting the symlinks for multiple top-level targets at the same time and want to avoid the situation where a top-level target is allowed to enter execution without all of its symlinks planted. We're already avoiding this situation by design by planting the symlinks for 1 single top-level target at a time. To avoid the near-infinite loop caused by a repeated NestedSet, we add each NestedSet to the de-duplication set the very first time it's seen. **Changes in this CL** - [Bug-fixing] Add a NestedSet to the de-duplication set the very first time it's seen. - [Code simplicity] 1 single blocking `Future.get()` instead of 1 for each recursive layer. Fixes #22586. --- [1] https://github.com/bazelbuild/bazel/blob/193b114287b3e20850a4b106b889771dfa63a601/src/main/java/com/google/devtools/build/lib/skyframe/IncrementalPackageRoots.java#L253 [2] https://github.com/bazelbuild/bazel/blob/193b114287b3e20850a4b106b889771dfa63a601/src/main/java/com/google/devtools/build/lib/skyframe/IncrementalPackageRoots.java#L256 PiperOrigin-RevId: 640524271 Change-Id: I63c39d7c8f27abaf9229396af1424e775cf5f85f
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/IncrementalPackageRoots.java b/src/main/java/com/google/devtools/build/lib/skyframe/IncrementalPackageRoots.java
@@ -158,7 +158,7 @@ public static IncrementalPackageRoots createAndRegisterToEventBus(
    * </pre>
    *
    * We'd plant the symlink to "noclash" first, then wait to see whether we need "foo" or "Foo". If
-   * we end up needing both, throw an error. See {@link #registerAndPlantMissingSymlinks}.
+   * we end up needing both, throw an error. See {@link #recursiveRegisterAndPlantMissingSymlinks}.
    */
   public void eagerlyPlantSymlinksToSingleSourceRoot() throws AbruptExitException {
     try {
@@ -193,7 +193,7 @@ public PackageRootLookup getPackageRootLookup() {
   // a symlink and starting an action that requires that symlink. This race condition is possible
   // because of the various memoizations we use to avoid repeated work.
   @Subscribe
-  public void topLevelTargetReadyForSymlinkPlanting(TopLevelTargetReadyForSymlinkPlanting event)
+  public void lazilyPlantSymlinks(TopLevelTargetReadyForSymlinkPlanting event)
       throws AbruptExitException {
     if (allowExternalRepositories || !maybeConflictingBaseNamesLowercase.isEmpty()) {
       Set<NestedSet.Node> donePackagesLocalRef;
@@ -206,10 +206,28 @@ public void topLevelTargetReadyForSymlinkPlanting(TopLevelTargetReadyForSymlinkP
         donePackagesLocalRef = donePackages;
         lazilyPlantedSymlinksLocalRef = lazilyPlantedSymlinks;
       }
-      registerAndPlantMissingSymlinks(
+
+      // Initial capacity: arbitrarily chosen.
+      // This list doesn't need to be thread-safe, as items are added sequentially.
+      List<ListenableFuture<Void>> futures = new ArrayList<>(128);
+      recursiveRegisterAndPlantMissingSymlinks(
           event.transitivePackagesForSymlinkPlanting(),
           donePackagesLocalRef,
-          lazilyPlantedSymlinksLocalRef);
+          lazilyPlantedSymlinksLocalRef,
+          futures);
+
+      // Now wait on the futures. After that, we can be sure that the symlinks have been planted.
+      try {
+        Futures.whenAllSucceed(futures).call(() -> null, directExecutor()).get();
+      } catch (InterruptedException e) {
+        Thread.currentThread().interrupt();
+        // Bail
+      } catch (ExecutionException e) {
+        if (e.getCause() instanceof AbruptExitException) {
+          throw (AbruptExitException) e.getCause();
+        }
+        throw new IllegalStateException("Unexpected exception", e);
+      }
     }
   }
 
@@ -224,16 +242,17 @@ public void analysisFinished(AnalysisPhaseCompleteEvent unused) {
    * <p>There are 2 possibilities: either we're planting symlinks to the external repos, or there's
    * potentially conflicting symlinks detected.
    */
-  private void registerAndPlantMissingSymlinks(
-      NestedSet<Package> packages, Set<Node> donePackagesRef, Set<Path> lazilyPlantedSymlinksRef)
-      throws AbruptExitException {
+  private void recursiveRegisterAndPlantMissingSymlinks(
+      NestedSet<Package> packages,
+      Set<Node> donePackagesRef,
+      Set<Path> lazilyPlantedSymlinksRef,
+      List<ListenableFuture<Void>> futures) {
     // Optimization to prune subsequent traversals.
     // A false negative does not affect correctness.
-    if (donePackagesRef.contains(packages.toNode())) {
+    if (!donePackagesRef.add(packages.toNode())) {
       return;
     }
 
-    List<ListenableFuture<Void>> futures = new ArrayList<>(packages.getLeaves().size());
     synchronized (symlinkPlantingPool) {
       // Some other thread shut down the executor, exit now.
       if (symlinkPlantingPool.isShutdown()) {
@@ -246,22 +265,9 @@ private void registerAndPlantMissingSymlinks(
       }
     }
     for (NestedSet<Package> transitive : packages.getNonLeaves()) {
-      registerAndPlantMissingSymlinks(transitive, donePackagesRef, lazilyPlantedSymlinksRef);
-    }
-    // Now wait on the futures.
-    try {
-      Futures.whenAllSucceed(futures).call(() -> null, directExecutor()).get();
-    } catch (InterruptedException e) {
-      Thread.currentThread().interrupt();
-      return; // Bail
-    } catch (ExecutionException e) {
-      if (e.getCause() instanceof AbruptExitException) {
-        throw (AbruptExitException) e.getCause();
-      }
-      throw new IllegalStateException("Unexpected exception", e);
+      recursiveRegisterAndPlantMissingSymlinks(
+          transitive, donePackagesRef, lazilyPlantedSymlinksRef, futures);
     }
-    // Only update the memoization set now, after the symlinks are confirmed planted.
-    donePackagesRef.add(packages.toNode());
   }
 
   private Void plantSingleSymlinkForPackage(Package pkg, Set<Path> lazilyPlantedSymlinksRef)
