From 46706aef724c69016d9eae914cbe7a96349442c2 Mon Sep 17 00:00:00 2001 From: janakr Date: Mon, 30 Apr 2018 16:18:50 -0700 Subject: Allow SkyFunctions to return a sentinel value indicating that all of a node's in-progress data should be forgotten, and its evaluation should be restarted from scratch, as if it were freshly created/dirtied. To guard against this happening unexpectedly, any such events are passed to a GraphInconsistencyReceiver, which can verify that the SkyFunction is behaving properly. This is the first change in a series to permit action rewinding when it is discovered that a previously generated input file is no longer available. When an action detects that one of its inputs is unusable, it can return this sentinel value, causing it to be re-evaluated from scratch. Follow-up changes will make the node corresponding to the input, and the node corresponding to the action that generated the input, dirty when this happens, causing the upstream action to be re-run, regenerating the desired input. Currently works for builds that do not keep edges, although follow-ups may make this possible for all builds. PiperOrigin-RevId: 194863097 --- .../AbstractExceptionalParallelEvaluator.java | 6 +- .../build/skyframe/AbstractParallelEvaluator.java | 28 ++++++++ .../build/skyframe/DelegatingNodeEntry.java | 5 ++ .../build/skyframe/DirtyBuildingState.java | 5 ++ .../build/skyframe/GraphInconsistencyReceiver.java | 41 ++++++++++++ .../build/skyframe/InMemoryMemoizingEvaluator.java | 14 +++- .../devtools/build/skyframe/InMemoryNodeEntry.java | 10 +++ .../build/skyframe/MemoizingEvaluator.java | 1 + .../google/devtools/build/skyframe/NodeEntry.java | 9 +++ .../devtools/build/skyframe/ParallelEvaluator.java | 8 ++- .../build/skyframe/ParallelEvaluatorContext.java | 78 +++++++++++++--------- .../build/skyframe/ReverseDepsUtility.java | 3 +- .../devtools/build/skyframe/SkyFunction.java | 30 ++++++--- 13 files changed, 193 insertions(+), 45 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java (limited to 'src/main/java/com/google/devtools/build/skyframe') diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java index 9526c855d9..e4a4193d57 100644 --- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java @@ -86,7 +86,8 @@ public abstract class AbstractExceptionalParallelEvaluator ErrorInfoManager errorInfoManager, boolean keepGoing, int threadCount, - DirtyTrackingProgressReceiver progressReceiver) { + DirtyTrackingProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver) { super( graph, graphVersion, @@ -98,6 +99,7 @@ public abstract class AbstractExceptionalParallelEvaluator keepGoing, threadCount, progressReceiver, + graphInconsistencyReceiver, new SimpleCycleDetector()); } @@ -111,6 +113,7 @@ public abstract class AbstractExceptionalParallelEvaluator ErrorInfoManager errorInfoManager, boolean keepGoing, DirtyTrackingProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver, ForkJoinPool forkJoinPool, CycleDetector cycleDetector) { super( @@ -123,6 +126,7 @@ public abstract class AbstractExceptionalParallelEvaluator errorInfoManager, keepGoing, progressReceiver, + graphInconsistencyReceiver, forkJoinPool, cycleDetector); } diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java index 6ed51ad3f8..40ed157180 100644 --- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java @@ -70,6 +70,7 @@ public abstract class AbstractParallelEvaluator { boolean keepGoing, int threadCount, DirtyTrackingProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver, CycleDetector cycleDetector) { this.graph = graph; this.cycleDetector = cycleDetector; @@ -85,6 +86,7 @@ public abstract class AbstractParallelEvaluator { storedEventFilter, errorInfoManager, Evaluate::new, + graphInconsistencyReceiver, threadCount); } @@ -98,6 +100,7 @@ public abstract class AbstractParallelEvaluator { ErrorInfoManager errorInfoManager, boolean keepGoing, DirtyTrackingProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver, ForkJoinPool forkJoinPool, CycleDetector cycleDetector) { this.graph = graph; @@ -114,6 +117,7 @@ public abstract class AbstractParallelEvaluator { storedEventFilter, errorInfoManager, Evaluate::new, + graphInconsistencyReceiver, Preconditions.checkNotNull(forkJoinPool)); } @@ -442,6 +446,11 @@ public abstract class AbstractParallelEvaluator { env.doneBuilding(); } + if (maybeEraseNodeToRestartFromScratch(skyKey, state, value)) { + evaluatorContext.getVisitor().enqueueEvaluation(skyKey); + return; + } + // Helper objects for all the newly requested deps that weren't known to the environment, // and may contain duplicate elements. GroupedListHelper newDirectDeps = env.getNewlyRequestedDeps(); @@ -601,6 +610,25 @@ public abstract class AbstractParallelEvaluator { private static final int MAX_REVERSEDEP_DUMP_LENGTH = 1000; } + private boolean maybeEraseNodeToRestartFromScratch( + SkyKey key, NodeEntry entry, SkyValue returnedValue) { + if (!SkyFunction.SENTINEL_FOR_RESTART_FROM_SCRATCH.equals(returnedValue)) { + return false; + } + evaluatorContext + .getGraphInconsistencyReceiver() + .noteInconsistencyAndMaybeThrow( + key, /*otherKey=*/ null, GraphInconsistencyReceiver.Inconsistency.RESET_REQUESTED); + entry.resetForRestartFromScratch(); + // TODO(mschaller): rdeps of children have to be handled here. If the graph does not keep edges, + // nothing has to be done, since there are no reverse deps to keep consistent. If the graph + // keeps edges, it's a harder problem. The reverse deps could just be removed, but in the case + // that this node is dirty, the deps shouldn't be removed, they should just be transformed back + // to "known reverse deps" from "reverse deps declared during this evaluation" (the inverse of + // NodeEntry#checkIfDoneForDirtyReverseDep). Such a method doesn't currently exist, but could. + return true; + } + void propagateEvaluatorContextCrashIfAny() { if (!evaluatorContext.getVisitor().getCrashes().isEmpty()) { evaluatorContext diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java index 689b1cd9db..95124ecb58 100644 --- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java @@ -140,6 +140,11 @@ public abstract class DelegatingNodeEntry implements NodeEntry { getDelegate().removeUnfinishedDeps(unfinishedDeps); } + @Override + public void resetForRestartFromScratch() { + getDelegate().resetForRestartFromScratch(); + } + @Override public Set addTemporaryDirectDeps(GroupedListHelper helper) { return getDelegate().addTemporaryDirectDeps(helper); diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java index d802c3d673..59a2e13db3 100644 --- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java +++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java @@ -193,6 +193,11 @@ public abstract class DirtyBuildingState { return result.build(); } + final void resetForRestartFromScratch() { + Preconditions.checkState(dirtyState == DirtyState.REBUILDING, this); + dirtyDirectDepIndex = 0; + } + protected void markRebuilding() { Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this); dirtyState = DirtyState.REBUILDING; diff --git a/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java b/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java new file mode 100644 index 0000000000..bba9264dac --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java @@ -0,0 +1,41 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package com.google.devtools.build.skyframe; + +import javax.annotation.Nullable; + +/** + * A receiver that can be informed of inconsistencies detected in Skyframe. Such inconsistencies are + * usually the result of external data loss (such as nodes in the graph, or the results of external + * computations stored in a remote execution service). + * + *

The receiver can tolerate such inconsistencies, or throw hard if they are unexpected. + */ +public interface GraphInconsistencyReceiver { + void noteInconsistencyAndMaybeThrow( + SkyKey key, @Nullable SkyKey otherKey, Inconsistency inconsistency); + + /** The type of inconsistency detected. */ + enum Inconsistency { + RESET_REQUESTED + } + + /** A {@link GraphInconsistencyReceiver} that crashes on any inconsistency. */ + GraphInconsistencyReceiver THROWING = + (key, otherKey, inconsistency) -> { + throw new IllegalStateException( + "Unexpected inconsistency: " + key + ", " + otherKey + ", " + inconsistency); + }; +} diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java index 5d29b82758..923c71242a 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java @@ -61,6 +61,7 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { private Map valuesToInject = new HashMap<>(); private final InvalidationState deleterState = new DeletingInvalidationState(); private final Differencer differencer; + private final GraphInconsistencyReceiver graphInconsistencyReceiver; // Keep edges in graph. Can be false to save memory, in which case incremental builds are // not possible. @@ -83,18 +84,26 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { Map skyFunctions, Differencer differencer, @Nullable EvaluationProgressReceiver progressReceiver) { - this(skyFunctions, differencer, progressReceiver, new EmittedEventState(), true); + this( + skyFunctions, + differencer, + progressReceiver, + GraphInconsistencyReceiver.THROWING, + new EmittedEventState(), + true); } public InMemoryMemoizingEvaluator( Map skyFunctions, Differencer differencer, @Nullable EvaluationProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver, EmittedEventState emittedEventState, boolean keepEdges) { this.skyFunctions = ImmutableMap.copyOf(skyFunctions); this.differencer = Preconditions.checkNotNull(differencer); this.progressReceiver = new DirtyTrackingProgressReceiver(progressReceiver); + this.graphInconsistencyReceiver = Preconditions.checkNotNull(graphInconsistencyReceiver); this.graph = new InMemoryGraphImpl(keepEdges); this.emittedEventState = emittedEventState; this.keepEdges = keepEdges; @@ -179,7 +188,8 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE, keepGoing, numThreads, - progressReceiver); + progressReceiver, + graphInconsistencyReceiver); EvaluationResult result = evaluator.eval(roots); return EvaluationResult.builder() .mergeFrom(result) diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java index 7b48275cbe..5a13c57ce0 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java @@ -581,6 +581,16 @@ public class InMemoryNodeEntry implements NodeEntry { getTemporaryDirectDeps().remove(unfinishedDeps); } + @Override + public synchronized void resetForRestartFromScratch() { + Preconditions.checkState(!isDone(), "Reset entry can't be done: %s", this); + directDeps = null; + signaledDeps = 0; + if (dirtyBuildingState != null) { + dirtyBuildingState.resetForRestartFromScratch(); + } + } + @Override public synchronized Set addTemporaryDirectDeps(GroupedListHelper helper) { Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this); diff --git a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java index dac0927ca0..adff0d0589 100644 --- a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java @@ -165,6 +165,7 @@ public interface MemoizingEvaluator { ImmutableMap skyFunctions, Differencer differencer, EvaluationProgressReceiver progressReceiver, + GraphInconsistencyReceiver graphInconsistencyReceiver, EmittedEventState emittedEventState, boolean keepEdges); } diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java index 02796390ef..aee68b3b91 100644 --- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java @@ -354,6 +354,15 @@ public interface NodeEntry extends ThinNodeEntry { @ThreadSafe void removeUnfinishedDeps(Set unfinishedDeps); + /** + * Erases all stored work during this evaluation from this entry, namely all temporary direct + * deps. The entry will be as if it had never evaluated at this version. Called after the {@link + * SkyFunction} for this entry returns {@link SkyFunction#SENTINEL_FOR_RESTART_FROM_SCRATCH}, + * indicating that something went wrong in external state and the evaluation has to be restarted. + */ + @ThreadSafe + void resetForRestartFromScratch(); + /** * Adds the temporary direct deps given in {@code helper} and returns the set of unique deps * added. It is the users responsibility to ensure that there are no elements in common between diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java index cdcec829a9..afd0279e5f 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java @@ -42,7 +42,8 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator runnableMaker, + GraphInconsistencyReceiver graphInconsistencyReceiver, final int threadCount) { - this.graph = graph; - this.graphVersion = graphVersion; - this.skyFunctions = skyFunctions; - this.reporter = reporter; - this.replayingNestedSetEventVisitor = - new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState.eventState); - this.replayingNestedSetPostableVisitor = - new NestedSetVisitor<>( - new NestedSetPostableReceiver(reporter), emittedEventState.postableState); - this.keepGoing = keepGoing; - this.progressReceiver = Preconditions.checkNotNull(progressReceiver); - this.storedEventFilter = storedEventFilter; - this.errorInfoManager = errorInfoManager; - visitorSupplier = - Suppliers.memoize( - new Supplier() { - @Override - public NodeEntryVisitor get() { - return new NodeEntryVisitor( - threadCount, progressReceiver, runnableMaker); - } - }); + this( + graph, + graphVersion, + skyFunctions, + reporter, + emittedEventState, + keepGoing, + progressReceiver, + storedEventFilter, + errorInfoManager, + graphInconsistencyReceiver, + () -> new NodeEntryVisitor(threadCount, progressReceiver, runnableMaker)); } ParallelEvaluatorContext( @@ -108,11 +100,39 @@ class ParallelEvaluatorContext { EventFilter storedEventFilter, ErrorInfoManager errorInfoManager, final Function runnableMaker, + GraphInconsistencyReceiver graphInconsistencyReceiver, final ForkJoinPool forkJoinPool) { + this( + graph, + graphVersion, + skyFunctions, + reporter, + emittedEventState, + keepGoing, + progressReceiver, + storedEventFilter, + errorInfoManager, + graphInconsistencyReceiver, + () -> new NodeEntryVisitor(forkJoinPool, progressReceiver, runnableMaker)); + } + + private ParallelEvaluatorContext( + QueryableGraph graph, + Version graphVersion, + ImmutableMap skyFunctions, + ExtendedEventHandler reporter, + EmittedEventState emittedEventState, + boolean keepGoing, + final DirtyTrackingProgressReceiver progressReceiver, + EventFilter storedEventFilter, + ErrorInfoManager errorInfoManager, + GraphInconsistencyReceiver graphInconsistencyReceiver, + Supplier visitorSupplier) { this.graph = graph; this.graphVersion = graphVersion; this.skyFunctions = skyFunctions; this.reporter = reporter; + this.graphInconsistencyReceiver = graphInconsistencyReceiver; this.replayingNestedSetEventVisitor = new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState.eventState); this.replayingNestedSetPostableVisitor = @@ -122,15 +142,7 @@ class ParallelEvaluatorContext { this.progressReceiver = Preconditions.checkNotNull(progressReceiver); this.storedEventFilter = storedEventFilter; this.errorInfoManager = errorInfoManager; - visitorSupplier = - Suppliers.memoize( - new Supplier() { - @Override - public NodeEntryVisitor get() { - return new NodeEntryVisitor( - forkJoinPool, progressReceiver, runnableMaker); - } - }); + this.visitorSupplier = Suppliers.memoize(visitorSupplier); } Map getBatchValues( @@ -196,6 +208,10 @@ class ParallelEvaluatorContext { return progressReceiver; } + GraphInconsistencyReceiver getGraphInconsistencyReceiver() { + return graphInconsistencyReceiver; + } + NestedSetVisitor getReplayingNestedSetEventVisitor() { return replayingNestedSetEventVisitor; } diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java index e1d16bb9ec..5eea55a17b 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java +++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java @@ -13,6 +13,7 @@ // limitations under the License. package com.google.devtools.build.skyframe; +import com.google.common.annotations.VisibleForTesting; import com.google.common.base.MoreObjects; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; @@ -53,7 +54,7 @@ import java.util.Set; abstract class ReverseDepsUtility { private ReverseDepsUtility() {} - static final int MAYBE_CHECK_THRESHOLD = 10; + @VisibleForTesting static final int MAYBE_CHECK_THRESHOLD = 10; /** * We can store one type of operation bare in order to save memory. For done nodes, most diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java index 9975996af5..1ae29160b8 100644 --- a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java +++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java @@ -36,15 +36,18 @@ public interface SkyFunction { * When a value is requested, this method is called with the name of the value and a * dependency-tracking environment. * - *

This method should return a non-{@code null} value, or {@code null} if any dependencies - * were missing ({@link Environment#valuesMissing} was true before returning). In that case the - * missing dependencies will be computed and the {@code compute} method called again. + *

This method should return a non-{@code null} value, or {@code null} if any dependencies were + * missing ({@link Environment#valuesMissing} was true before returning). In that case the missing + * dependencies will be computed and the {@code compute} method called again. * - *

This method should throw if it fails, or if one of its dependencies fails with an - * exception and this method cannot recover. If one of its dependencies fails and this method can - * enrich the exception with additional context, then this method should catch that exception and - * throw another containing that additional context. If it has no such additional context, then - * it should allow its dependency's exception to be thrown through it. + *

This method should throw if it fails, or if one of its dependencies fails with an exception + * and this method cannot recover. If one of its dependencies fails and this method can enrich the + * exception with additional context, then this method should catch that exception and throw + * another containing that additional context. If it has no such additional context, then it + * should allow its dependency's exception to be thrown through it. + * + *

This method may return {@link #SENTINEL_FOR_RESTART_FROM_SCRATCH} in rare circumstances. See + * its docs. Do not return this value unless you know exactly what you are doing. * * @throws SkyFunctionException on failure * @throws InterruptedException if interrupted @@ -65,6 +68,17 @@ public interface SkyFunction { @Nullable String extractTag(SkyKey skyKey); + /** + * Sentinel value for {@link #compute} to return, indicating that something went wrong in external + * state and the evaluation has to be restarted from scratch, ignoring any deps that the {@link + * #compute} function may have declared during evaluation at this version (including deps declared + * during previous calls that returned null). Common causes for returning this would be data loss, + * if a dep's data is not actually available externally. In this case, the {@link SkyFunction} + * will likely dirty the unusable dep to force its re-evalution when re-requested by the restarted + * entry's computation. + */ + SkyValue SENTINEL_FOR_RESTART_FROM_SCRATCH = new SkyValue() {}; + /** * The services provided to the {@link SkyFunction#compute} implementation by the Skyframe * evaluation framework. -- cgit v1.2.3