Skip to content

Commit 68ffdd2

Browse files
justinhorvitzcopybara-github
justinhorvitz
authored and
copybara-github
committed
Permit action rewinding in eligible builds (no incremental state, no action cache).
This change open sources a bit more of the action rewinding machinery. However, action rewinding still requires a `LostInputsActionExecutionException` or `LostInputsExecException` to be thrown from a running action in order to be initiated. At the time of this writing, neither of these exceptions are ever thrown in bazel. PiperOrigin-RevId: 442104054
1 parent bd67975 commit 68ffdd2

7 files changed

Lines changed: 309 additions & 22 deletions

File tree

‎src/main/java/com/google/devtools/build/lib/BUILD‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -346,7 +346,7 @@ java_library(
346346
"//src/main/java/com/google/devtools/build/lib/skyframe:top_level_aspects_value",
347347
"//src/main/java/com/google/devtools/build/lib/skyframe:workspace_info",
348348
"//src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2:actiongraph_v2",
349-
"//src/main/java/com/google/devtools/build/lib/skyframe/rewinding",
349+
"//src/main/java/com/google/devtools/build/lib/skyframe/rewinding:action_rewound_event",
350350
"//src/main/java/com/google/devtools/build/lib/unix",
351351
"//src/main/java/com/google/devtools/build/lib/util",
352352
"//src/main/java/com/google/devtools/build/lib/util:TestType",

‎src/main/java/com/google/devtools/build/lib/skyframe/BUILD‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -314,6 +314,8 @@ java_library(
314314
"//src/main/java/com/google/devtools/build/lib/rules:repository/workspace_file_helper",
315315
"//src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2:actiongraph_v2",
316316
"//src/main/java/com/google/devtools/build/lib/skyframe/rewinding",
317+
"//src/main/java/com/google/devtools/build/lib/skyframe/rewinding:action_rewound_event",
318+
"//src/main/java/com/google/devtools/build/lib/skyframe/rewinding:rewindable_graph_inconsistency_receiver",
317319
"//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
318320
"//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec:serialization-constant",
319321
"//src/main/java/com/google/devtools/build/lib/util",

‎src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,7 @@
8080
import com.google.devtools.build.lib.skyframe.FilesystemValueChecker.ImmutableBatchDirtyResult;
8181
import com.google.devtools.build.lib.skyframe.PackageFunction.ActionOnIOExceptionReadingBuildFile;
8282
import com.google.devtools.build.lib.skyframe.PackageLookupFunction.CrossRepositoryLabelViolationStrategy;
83+
import com.google.devtools.build.lib.skyframe.rewinding.RewindableGraphInconsistencyReceiver;
8384
import com.google.devtools.build.lib.util.AbruptExitException;
8485
import com.google.devtools.build.lib.util.DetailedExitCode;
8586
import com.google.devtools.build.lib.util.ExitCode;
@@ -166,6 +167,7 @@ public final class SequencedSkyframeExecutor extends SkyframeExecutor {
166167
private Duration outputTreeDiffCheckingDuration = Duration.ofSeconds(-1L);
167168

168169
private final WorkspaceInfoFromDiffReceiver workspaceInfoFromDiffReceiver;
170+
private GraphInconsistencyReceiver inconsistencyReceiver = GraphInconsistencyReceiver.THROWING;
169171

170172
private SequencedSkyframeExecutor(
171173
Consumer<SkyframeExecutor> skyframeExecutorConsumerOnInit,
@@ -230,7 +232,7 @@ protected InMemoryMemoizingEvaluator createEvaluator(
230232
skyFunctions,
231233
recordingDiffer,
232234
progressReceiver,
233-
GraphInconsistencyReceiver.THROWING,
235+
inconsistencyReceiver,
234236
eventFilter,
235237
emittedEventState,
236238
trackIncrementalState);
@@ -271,6 +273,11 @@ public WorkspaceInfoFromDiff sync(
271273
OptionsProvider options)
272274
throws InterruptedException, AbruptExitException {
273275
if (evaluatorNeedsReset) {
276+
// Rewinding is only supported with no incremental state and no action cache.
277+
inconsistencyReceiver =
278+
trackIncrementalState || useActionCache(options)
279+
? GraphInconsistencyReceiver.THROWING
280+
: new RewindableGraphInconsistencyReceiver();
274281
// Recreate MemoizingEvaluator so that graph is recreated with correct edge-clearing status,
275282
// or if the graph doesn't have edges, so that a fresh graph can be used.
276283
resetEvaluator();
@@ -293,6 +300,11 @@ public WorkspaceInfoFromDiff sync(
293300
return workspaceInfo;
294301
}
295302

303+
private static boolean useActionCache(OptionsProvider options) {
304+
BuildRequestOptions buildRequestOptions = options.getOptions(BuildRequestOptions.class);
305+
return buildRequestOptions != null && buildRequestOptions.useActionCache;
306+
}
307+
296308
/**
297309
* The value types whose builders have direct access to the package locator, rather than accessing
298310
* it via an explicit Skyframe dependency. They need to be invalidated if the package locator

‎src/main/java/com/google/devtools/build/lib/skyframe/rewinding/BUILD‎

Lines changed: 40 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,20 @@ filegroup(
1010
visibility = ["//src:__subpackages__"],
1111
)
1212

13+
java_library(
14+
name = "action_rewound_event",
15+
srcs = ["ActionRewoundEvent.java"],
16+
deps = [
17+
"//src/main/java/com/google/devtools/build/lib/actions",
18+
"//src/main/java/com/google/devtools/build/lib/events",
19+
],
20+
)
21+
1322
java_library(
1423
name = "rewinding",
1524
srcs = [
1625
"ActionRewindStrategy.java",
1726
"ActionRewindingStats.java",
18-
"ActionRewoundEvent.java",
1927
],
2028
deps = [
2129
"//src/main/java/com/google/devtools/build/lib/actions",
@@ -39,3 +47,34 @@ java_library(
3947
"//third_party:jsr305",
4048
],
4149
)
50+
51+
java_library(
52+
name = "rewindable_graph_inconsistency_receiver",
53+
srcs = ["RewindableGraphInconsistencyReceiver.java"],
54+
deps = [
55+
":rewinding_inconsistency_utils",
56+
"//src/main/java/com/google/devtools/build/skyframe",
57+
"//src/main/java/com/google/devtools/build/skyframe:graph_inconsistency_java_proto",
58+
"//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
59+
"//third_party:flogger",
60+
"//third_party:guava",
61+
"//third_party:jsr305",
62+
],
63+
)
64+
65+
java_library(
66+
name = "rewinding_inconsistency_utils",
67+
srcs = ["RewindingInconsistencyUtils.java"],
68+
deps = [
69+
"//src/main/java/com/google/devtools/build/lib/actions:action_lookup_data",
70+
"//src/main/java/com/google/devtools/build/lib/actions:artifacts",
71+
"//src/main/java/com/google/devtools/build/lib/skyframe:action_template_expansion_value",
72+
"//src/main/java/com/google/devtools/build/lib/skyframe:artifact_nested_set_key",
73+
"//src/main/java/com/google/devtools/build/lib/skyframe:aspect_completion_value",
74+
"//src/main/java/com/google/devtools/build/lib/skyframe:fileset_entry_key",
75+
"//src/main/java/com/google/devtools/build/lib/skyframe:recursive_filesystem_traversal",
76+
"//src/main/java/com/google/devtools/build/lib/skyframe:target_completion_value",
77+
"//src/main/java/com/google/devtools/build/lib/skyframe:test_completion_value",
78+
"//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
79+
],
80+
)

‎src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java‎

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
// Copyright 2022 The Bazel Authors. All rights reserved.
2+
//
3+
// Licensed under the Apache License, Version 2.0 (the "License");
4+
// you may not use this file except in compliance with the License.
5+
// You may obtain a copy of the License at
6+
//
7+
// http://www.apache.org/licenses/LICENSE-2.0
8+
//
9+
// Unless required by applicable law or agreed to in writing, software
10+
// distributed under the License is distributed on an "AS IS" BASIS,
11+
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12+
// See the License for the specific language governing permissions and
13+
// limitations under the License.
14+
package com.google.devtools.build.lib.skyframe.rewinding;
15+
16+
import static com.google.common.base.Preconditions.checkState;
17+
import static com.google.common.collect.ImmutableList.toImmutableList;
18+
19+
import com.google.common.collect.ImmutableList;
20+
import com.google.common.flogger.GoogleLogger;
21+
import com.google.devtools.build.skyframe.GraphInconsistencyReceiver;
22+
import com.google.devtools.build.skyframe.SkyKey;
23+
import com.google.devtools.build.skyframe.proto.GraphInconsistency.Inconsistency;
24+
import java.util.Collection;
25+
import java.util.function.Predicate;
26+
import javax.annotation.Nullable;
27+
28+
/**
29+
* {@link GraphInconsistencyReceiver} for evaluations operating on graphs that support rewinding (no
30+
* reverse dependencies, no action cache).
31+
*
32+
* <p>Action rewinding results in various kinds of inconsistencies which this receiver tolerates.
33+
*/
34+
public final class RewindableGraphInconsistencyReceiver implements GraphInconsistencyReceiver {
35+
36+
private static final GoogleLogger logger = GoogleLogger.forEnclosingClass();
37+
38+
private boolean rewindingInitiated = false;
39+
40+
@Override
41+
public void noteInconsistencyAndMaybeThrow(
42+
SkyKey key, @Nullable Collection<SkyKey> otherKeys, Inconsistency inconsistency) {
43+
String childrenAsString =
44+
otherKeys != null ? GraphInconsistencyReceiver.listChildren(otherKeys) : "null";
45+
46+
// RESET_REQUESTED and PARENT_FORCE_REBUILD_OF_CHILD may be the first inconsistencies seen with
47+
// rewinding. BUILDING_PARENT_FOUND_UNDONE_CHILD may also be seen, but it will not be the first.
48+
switch (inconsistency) {
49+
case RESET_REQUESTED:
50+
checkState(
51+
RewindingInconsistencyUtils.isTypeThatDependsOnRewindableNodes(key),
52+
"Unexpected reset requested for: %s",
53+
key);
54+
logger.atInfo().log("Reset requested for: %s", key);
55+
rewindingInitiated = true;
56+
return;
57+
58+
case PARENT_FORCE_REBUILD_OF_CHILD:
59+
boolean parentMayForceRebuildChildren =
60+
RewindingInconsistencyUtils.mayForceRebuildChildren(key);
61+
ImmutableList<SkyKey> unrewindableRebuildChildren =
62+
otherKeys.stream()
63+
.filter(Predicate.not(RewindingInconsistencyUtils::isRewindable))
64+
.collect(toImmutableList());
65+
checkState(
66+
parentMayForceRebuildChildren && unrewindableRebuildChildren.isEmpty(),
67+
"Unexpected force rebuild, parent = %s, children = %s",
68+
key,
69+
parentMayForceRebuildChildren
70+
? GraphInconsistencyReceiver.listChildren(unrewindableRebuildChildren)
71+
: childrenAsString);
72+
logger.atInfo().log(
73+
"Parent force rebuild of children: parent = %s, children = %s", key, childrenAsString);
74+
rewindingInitiated = true;
75+
return;
76+
77+
case BUILDING_PARENT_FOUND_UNDONE_CHILD:
78+
boolean parentDependsOnRewindableNodes =
79+
RewindingInconsistencyUtils.isTypeThatDependsOnRewindableNodes(key);
80+
ImmutableList<SkyKey> unrewindableUndoneChildren =
81+
otherKeys.stream()
82+
.filter(Predicate.not(RewindingInconsistencyUtils::isRewindable))
83+
.collect(toImmutableList());
84+
checkState(
85+
rewindingInitiated
86+
&& parentDependsOnRewindableNodes
87+
&& unrewindableUndoneChildren.isEmpty(),
88+
"Unexpected undone children: parent = %s, children = %s",
89+
key,
90+
rewindingInitiated && parentDependsOnRewindableNodes
91+
? GraphInconsistencyReceiver.listChildren(unrewindableUndoneChildren)
92+
: childrenAsString);
93+
logger.atInfo().log(
94+
"Building parent found undone children: parent = %s, children = %s",
95+
key, childrenAsString);
96+
return;
97+
98+
case PARENT_FORCE_REBUILD_OF_MISSING_CHILD:
99+
case DIRTY_PARENT_HAD_MISSING_CHILD:
100+
case ALREADY_DECLARED_CHILD_MISSING:
101+
throw new IllegalStateException(
102+
String.format(
103+
"Unexpected inconsistency %s, key = %s, otherKeys = %s ",
104+
inconsistency, key, childrenAsString));
105+
default: // Needed because protobuf creates additional enum values.
106+
throw new IllegalStateException(
107+
String.format(
108+
"Unknown inconsistency %s, key = %s, otherKeys = %s ",
109+
inconsistency, key, childrenAsString));
110+
}
111+
}
112+
113+
@Override
114+
public boolean restartPermitted() {
115+
return true;
116+
}
117+
}

‎src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindingInconsistencyUtils.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
// Copyright 2022 The Bazel Authors. All rights reserved.
2+
//
3+
// Licensed under the Apache License, Version 2.0 (the "License");
4+
// you may not use this file except in compliance with the License.
5+
// You may obtain a copy of the License at
6+
//
7+
// http://www.apache.org/licenses/LICENSE-2.0
8+
//
9+
// Unless required by applicable law or agreed to in writing, software
10+
// distributed under the License is distributed on an "AS IS" BASIS,
11+
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12+
// See the License for the specific language governing permissions and
13+
// limitations under the License.
14+
package com.google.devtools.build.lib.skyframe.rewinding;
15+
16+
import com.google.devtools.build.lib.actions.ActionLookupData;
17+
import com.google.devtools.build.lib.actions.Artifact;
18+
import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
19+
import com.google.devtools.build.lib.skyframe.ArtifactNestedSetKey;
20+
import com.google.devtools.build.lib.skyframe.AspectCompletionValue.AspectCompletionKey;
21+
import com.google.devtools.build.lib.skyframe.FilesetEntryKey;
22+
import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue;
23+
import com.google.devtools.build.lib.skyframe.TargetCompletionValue.TargetCompletionKey;
24+
import com.google.devtools.build.lib.skyframe.TestCompletionValue.TestCompletionKey;
25+
import com.google.devtools.build.skyframe.SkyKey;
26+
27+
/**
28+
* Centralizes rewinding-related logic used by {@link
29+
* com.google.devtools.build.skyframe.GraphInconsistencyReceiver} policies.
30+
*/
31+
public final class RewindingInconsistencyUtils {
32+
33+
private RewindingInconsistencyUtils() {}
34+
35+
public static boolean mayForceRebuildChildren(SkyKey key) {
36+
return key instanceof ActionLookupData || key instanceof ArtifactNestedSetKey;
37+
}
38+
39+
/** Returns whether the key specifies a node which may be rewound by a failed action. */
40+
public static boolean isRewindable(SkyKey key) {
41+
return key instanceof ActionLookupData
42+
|| key instanceof ArtifactNestedSetKey
43+
|| key instanceof Artifact
44+
|| key instanceof FilesetEntryKey
45+
|| key instanceof RecursiveFilesystemTraversalValue.TraversalRequest;
46+
}
47+
48+
/**
49+
* Returns whether the key specifies a node which depends on nodes which may be rewound.
50+
*
51+
* <p>Such a node may discover, while in-flight, that a dependency of theirs transitioned from
52+
* done to undone.
53+
*/
54+
public static boolean isTypeThatDependsOnRewindableNodes(SkyKey key) {
55+
return key instanceof ActionLookupData
56+
|| key instanceof ArtifactNestedSetKey
57+
|| key instanceof ActionTemplateExpansionKey
58+
|| key instanceof Artifact
59+
|| key instanceof TargetCompletionKey
60+
|| key instanceof TestCompletionKey
61+
|| key instanceof AspectCompletionKey
62+
|| key instanceof RecursiveFilesystemTraversalValue.TraversalRequest
63+
|| key instanceof FilesetEntryKey;
64+
}
65+
}

0 commit comments

Comments
 (0)