Introduce top-down action caching in Bazel. The top-down cache may be provided by a Bazel module.
The cache works by first computing a _transitive_ cache key for the action, known as a sketch. It composes the action keys for all dependent actions and all transitive source file digest hashes.
This feature is not currently wired up for use - consider it extremely experimental at this point.
RELNOTES: None
PiperOrigin-RevId: 260973078
diff --git a/src/BUILD b/src/BUILD
index b8f1a7d..d9d5184 100644
--- a/src/BUILD
+++ b/src/BUILD
@@ -430,6 +430,7 @@
"//src/java_tools/singlejar:srcs",
"//src/main/cpp:srcs",
"//src/main/java/com/google/devtools/build/docgen:srcs",
+ "//src/main/java/com/google/devtools/build/lib/actionsketch:srcs",
"//src/main/java/com/google/devtools/build/lib:srcs",
"//src/main/java/com/google/devtools/build/lib/includescanning:srcs",
"//src/main/java/com/google/devtools/build/lib/network:srcs",
diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 625ef89..3a01018 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -679,6 +679,7 @@
"//src/main/java/com/google/devtools/build/lib/actions",
"//src/main/java/com/google/devtools/build/lib/actions:commandline_item",
"//src/main/java/com/google/devtools/build/lib/actions:localhost_capacity",
+ "//src/main/java/com/google/devtools/build/lib/actionsketch:action_sketch",
"//src/main/java/com/google/devtools/build/lib/analysis/platform",
"//src/main/java/com/google/devtools/build/lib/analysis/platform:platform_utils",
"//src/main/java/com/google/devtools/build/lib/analysis/platform:utils",
diff --git a/src/main/java/com/google/devtools/build/lib/actionsketch/ActionSketch.java b/src/main/java/com/google/devtools/build/lib/actionsketch/ActionSketch.java
index 16ddbe8..f936ae7 100644
--- a/src/main/java/com/google/devtools/build/lib/actionsketch/ActionSketch.java
+++ b/src/main/java/com/google/devtools/build/lib/actionsketch/ActionSketch.java
@@ -16,6 +16,7 @@
import com.google.auto.value.AutoValue;
import com.google.common.base.Preconditions;
+import com.google.devtools.build.skyframe.SkyValue;
import com.google.protobuf.ByteString;
import java.math.BigInteger;
import java.nio.ByteBuffer;
@@ -27,7 +28,7 @@
* all transitively consumed input files, as well as a transitive hash of all action keys.
*/
@AutoValue
-public abstract class ActionSketch {
+public abstract class ActionSketch implements SkyValue {
public static final int BIGINTEGER_ENCODED_LENGTH = /*length=*/ 1 + /*payload=*/ 17;
public static final int MAX_BYTES = /*hashes=*/ 2 * BIGINTEGER_ENCODED_LENGTH;
diff --git a/src/main/java/com/google/devtools/build/lib/actionsketch/BUILD b/src/main/java/com/google/devtools/build/lib/actionsketch/BUILD
new file mode 100644
index 0000000..0b9fa08
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actionsketch/BUILD
@@ -0,0 +1,21 @@
+package(
+ default_visibility = ["//src:__subpackages__"],
+)
+
+filegroup(
+ name = "srcs",
+ srcs = glob(["**"]),
+)
+
+java_library(
+ name = "action_sketch",
+ srcs = glob(["*.java"]),
+ deps = [
+ "//src/main/java/com/google/devtools/build/lib/actions",
+ "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
+ "//third_party:auto_value",
+ "//third_party:guava",
+ "//third_party:jsr305",
+ "//third_party/protobuf:protobuf_java",
+ ],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
index aa70340..c8d0ba8 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
@@ -628,6 +628,7 @@
.setEnabled(options.useActionCache)
.setVerboseExplanations(options.verboseExplanations)
.build()),
+ env.getTopDownActionCache(),
request.getPackageCacheOptions().checkOutputFiles
? modifiedOutputFiles
: ModifiedFileSet.NOTHING_MODIFIED,
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java b/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
index 0a8f4ce..f45b673 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
@@ -45,6 +45,7 @@
import com.google.devtools.build.lib.skyframe.Builder;
import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
+import com.google.devtools.build.lib.skyframe.TopDownActionCache;
import com.google.devtools.build.lib.util.AbruptExitException;
import com.google.devtools.build.lib.util.ExitCode;
import com.google.devtools.build.lib.util.LoggingUtil;
@@ -76,16 +77,19 @@
private final MetadataProvider fileCache;
private final ActionInputPrefetcher actionInputPrefetcher;
private final ActionCacheChecker actionCacheChecker;
+ private final TopDownActionCache topDownActionCache;
@VisibleForTesting
public SkyframeBuilder(
SkyframeExecutor skyframeExecutor,
ActionCacheChecker actionCacheChecker,
+ TopDownActionCache topDownActionCache,
ModifiedFileSet modifiedOutputFiles,
MetadataProvider fileCache,
ActionInputPrefetcher actionInputPrefetcher) {
this.skyframeExecutor = skyframeExecutor;
this.actionCacheChecker = actionCacheChecker;
+ this.topDownActionCache = topDownActionCache;
this.modifiedOutputFiles = modifiedOutputFiles;
this.fileCache = fileCache;
this.actionInputPrefetcher = actionInputPrefetcher;
@@ -156,6 +160,7 @@
exclusiveTests,
options,
actionCacheChecker,
+ topDownActionCache,
executionProgressReceiver,
topLevelArtifactContext);
// progressReceiver is finished, so unsynchronized access to builtTargets is now safe.
@@ -183,6 +188,7 @@
exclusiveTest,
options,
actionCacheChecker,
+ topDownActionCache,
null,
topLevelArtifactContext);
exitCode =
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
index 13ed9f9..4fd69b29 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
@@ -33,6 +33,7 @@
import com.google.devtools.build.lib.packages.PackageFactory;
import com.google.devtools.build.lib.skyframe.AspectValue;
import com.google.devtools.build.lib.skyframe.PrecomputedValue;
+import com.google.devtools.build.lib.skyframe.TopDownActionCache;
import com.google.devtools.build.lib.util.AbruptExitException;
import com.google.devtools.build.lib.util.io.OutErr;
import com.google.devtools.build.lib.vfs.DigestHashFunction.DefaultHashFunctionNotSetException;
@@ -93,6 +94,17 @@
return null;
}
+ /**
+ * Returns the {@link TopDownActionCache} used by Bazel. It is an error if more than one module
+ * returns a top-down action cache. If all modules return null, there will be no top-down caching.
+ *
+ * <p>This method will be called at the beginning of Bazel startup (in-between {@link #globalInit}
+ * and {@link #blazeStartup}).
+ */
+ public TopDownActionCache getTopDownActionCache() {
+ return null;
+ }
+
/** Tuple returned by {@link #getFileSystem}. */
@AutoValue
public abstract static class ModuleFileSystem {
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
index 668b333..cb29551 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
@@ -34,6 +34,7 @@
import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.InvocationPolicy;
import com.google.devtools.build.lib.skyframe.SkyframeBuildView;
import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
+import com.google.devtools.build.lib.skyframe.TopDownActionCache;
import com.google.devtools.build.lib.util.AbruptExitException;
import com.google.devtools.build.lib.util.ExitCode;
import com.google.devtools.build.lib.util.io.OutErr;
@@ -87,6 +88,7 @@
private PathFragment relativeWorkingDirectory = PathFragment.EMPTY_FRAGMENT;
private long commandStartTime;
private OutputService outputService;
+ private TopDownActionCache topDownActionCache;
private Path workingDirectory;
private String workspaceName;
private boolean haveSetupPackageCache = false;
@@ -490,6 +492,11 @@
return workspace.getPersistentActionCache(reporter);
}
+ /** Returns the top-down action cache to use, or null. */
+ public TopDownActionCache getTopDownActionCache() {
+ return topDownActionCache;
+ }
+
/**
* An array of String values useful if Blaze crashes. For now, just returns the build id as soon
* as it is determined.
@@ -633,6 +640,8 @@
outputService = null;
BlazeModule outputModule = null;
+ topDownActionCache = null;
+ BlazeModule topDownCachingModule = null;
if (command.builds()) {
for (BlazeModule module : runtime.getBlazeModules()) {
OutputService moduleService = module.getOutputService();
@@ -646,6 +655,18 @@
outputService = moduleService;
outputModule = module;
}
+
+ TopDownActionCache moduleCache = module.getTopDownActionCache();
+ if (moduleCache != null) {
+ if (topDownActionCache != null) {
+ throw new IllegalStateException(
+ String.format(
+ "More than one module (%s and %s) returns a top down action cache",
+ module.getClass(), topDownCachingModule.getClass()));
+ }
+ topDownActionCache = moduleCache;
+ topDownCachingModule = module;
+ }
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index ded849a..c4eedd2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -45,6 +45,7 @@
import com.google.devtools.build.lib.actions.MissingInputFileException;
import com.google.devtools.build.lib.actions.NotifyOnActionCacheHit;
import com.google.devtools.build.lib.actions.PackageRootResolver;
+import com.google.devtools.build.lib.actionsketch.ActionSketch;
import com.google.devtools.build.lib.analysis.BlazeDirectories;
import com.google.devtools.build.lib.causes.Cause;
import com.google.devtools.build.lib.causes.LabelCause;
@@ -100,6 +101,7 @@
* </ol>
*/
public class ActionExecutionFunction implements SkyFunction {
+
private final ActionRewindStrategy actionRewindStrategy = new ActionRewindStrategy();
private final SkyframeActionExecutor skyframeActionExecutor;
private final BlazeDirectories directories;
@@ -154,6 +156,19 @@
}
}
+ ActionSketch sketch = null;
+ TopDownActionCache topDownActionCache = skyframeActionExecutor.getTopDownActionCache();
+ if (topDownActionCache != null) {
+ sketch = (ActionSketch) env.getValue(ActionSketchFunction.key(actionLookupData));
+ if (sketch == null) {
+ return null;
+ }
+ ActionExecutionValue actionExecutionValue = topDownActionCache.get(sketch);
+ if (actionExecutionValue != null) {
+ return actionExecutionValue.transformForSharedAction(action.getOutputs());
+ }
+ }
+
// For restarts of this ActionExecutionFunction we use a ContinuationState variable, below, to
// avoid redoing work.
//
@@ -289,6 +304,9 @@
// Remove action from state map in case it's there (won't be unless it discovers inputs).
stateMap.remove(action);
+ if (sketch != null && result.dataIsShareable()) {
+ topDownActionCache.put(sketch, result);
+ }
return result;
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionSketchFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionSketchFunction.java
new file mode 100644
index 0000000..454adae
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionSketchFunction.java
@@ -0,0 +1,142 @@
+// Copyright 2019 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.lib.skyframe;
+
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
+import com.google.devtools.build.lib.actions.FileArtifactValue;
+import com.google.devtools.build.lib.actionsketch.ActionSketch;
+import com.google.devtools.build.lib.actionsketch.Sketches;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.lib.util.BigIntegerFingerprintUtils;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.Nullable;
+
+/**
+ * {@link ActionSketchFunction} computes an {@link ActionSketch} for the given Action. This is a
+ * transitive hash of the dependent action keys and source file content hashes.
+ */
+public final class ActionSketchFunction implements SkyFunction {
+ private final ActionKeyContext actionKeyContext;
+
+ public ActionSketchFunction(ActionKeyContext actionKeyContext) {
+ this.actionKeyContext = actionKeyContext;
+ }
+
+ public static SketchKey key(ActionLookupData key) {
+ return SketchKey.create(key);
+ }
+
+ @AutoCodec.VisibleForSerialization
+ @AutoCodec
+ static class SketchKey extends AbstractSkyKey<ActionLookupData> {
+ private static final LoadingCache<ActionLookupData, SketchKey> keyCache =
+ CacheBuilder.newBuilder()
+ .weakKeys()
+ .concurrencyLevel(BlazeInterners.concurrencyLevel())
+ .build(CacheLoader.from(SketchKey::new));
+
+ private SketchKey(ActionLookupData arg) {
+ super(arg);
+ }
+
+ @AutoCodec.VisibleForSerialization
+ @AutoCodec.Instantiator
+ static SketchKey create(ActionLookupData arg) {
+ return keyCache.getUnchecked(arg);
+ }
+
+ @Override
+ public SkyFunctionName functionName() {
+ return SkyFunctions.ACTION_SKETCH;
+ }
+ }
+
+ @Nullable
+ @Override
+ public String extractTag(SkyKey skyKey) {
+ return null;
+ }
+
+ @Nullable
+ @Override
+ public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
+ ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
+ ActionLookupValue actionLookupValue =
+ ArtifactFunction.getActionLookupValue(actionLookupData.getActionLookupKey(), env);
+ if (actionLookupValue == null) {
+ return null;
+ }
+
+ Action action = actionLookupValue.getAction(actionLookupData.getActionIndex());
+ List<Artifact> srcArtifacts = new ArrayList<>();
+ List<SketchKey> depActions = new ArrayList<>();
+ for (Artifact artifact : action.getInputs()) {
+ if (artifact.isSourceArtifact()) {
+ srcArtifacts.add(artifact);
+ } else {
+ depActions.add(SketchKey.create(((DerivedArtifact) artifact).getGeneratingActionKey()));
+ }
+ }
+
+ Map<SkyKey, SkyValue> srcArtifactValues = env.getValues(srcArtifacts);
+ Map<SkyKey, SkyValue> depSketchValues = env.getValues(depActions);
+ if (env.valuesMissing()) {
+ return null;
+ }
+
+ BigInteger transitiveActionKeyHash = Sketches.computeActionKey(action, actionKeyContext);
+ BigInteger transitiveSourceHash = BigInteger.ZERO;
+
+ // Incorporate the direct source values.
+ for (SkyValue val : srcArtifactValues.values()) {
+ FileArtifactValue fileArtifactValue = (FileArtifactValue) val;
+ transitiveSourceHash =
+ BigIntegerFingerprintUtils.compose(
+ transitiveSourceHash, fileArtifactValue.getValueFingerprint());
+ }
+
+ // Incorporate the transitive action key and source values.
+ for (SkyValue sketchVal : depSketchValues.values()) {
+ ActionSketch depSketch = (ActionSketch) sketchVal;
+ transitiveActionKeyHash =
+ BigIntegerFingerprintUtils.compose(
+ transitiveActionKeyHash, depSketch.transitiveActionLookupHash());
+ transitiveSourceHash =
+ BigIntegerFingerprintUtils.compose(
+ transitiveSourceHash, depSketch.transitiveSourceHash());
+ }
+
+ return ActionSketch.builder()
+ .setTransitiveActionLookupHash(transitiveActionKeyHash)
+ .setTransitiveSourceHash(transitiveSourceHash)
+ .build();
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index 12a8dab..fc4fc06 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -27,6 +27,7 @@
SkyFunctionName.createNonHermetic("PRECOMPUTED");
public static final SkyFunctionName CLIENT_ENVIRONMENT_VARIABLE =
SkyFunctionName.createNonHermetic("CLIENT_ENVIRONMENT_VARIABLE");
+ static final SkyFunctionName ACTION_SKETCH = SkyFunctionName.createHermetic("ACTION_SKETCH");
public static final SkyFunctionName ACTION_ENVIRONMENT_VARIABLE =
SkyFunctionName.createHermetic("ACTION_ENVIRONMENT_VARIABLE");
public static final SkyFunctionName DIRECTORY_LISTING_STATE =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index e8a340e..e9ce780 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -148,6 +148,7 @@
private ExtendedEventHandler progressSuppressingEventHandler;
private ActionLogBufferPathGenerator actionLogBufferPathGenerator;
private ActionCacheChecker actionCacheChecker;
+ @Nullable private TopDownActionCache topDownActionCache;
private final Profiler profiler = Profiler.instance();
// We keep track of actions already executed this build in order to avoid executing a shared
@@ -402,6 +403,7 @@
Executor executor,
OptionsProvider options,
ActionCacheChecker actionCacheChecker,
+ TopDownActionCache topDownActionCache,
OutputService outputService) {
this.reporter = Preconditions.checkNotNull(reporter);
this.executorEngine = Preconditions.checkNotNull(executor);
@@ -413,6 +415,7 @@
this.lostDiscoveredInputsMap = Maps.newConcurrentMap();
this.hadExecutionError = false;
this.actionCacheChecker = Preconditions.checkNotNull(actionCacheChecker);
+ this.topDownActionCache = topDownActionCache;
// Don't cache possibly stale data from the last build.
this.options = options;
// Cache some option values for performance, since we consult them on every action.
@@ -479,6 +482,7 @@
this.completedAndResetActions = null;
this.lostDiscoveredInputsMap = null;
this.actionCacheChecker = null;
+ this.topDownActionCache = null;
}
/**
@@ -583,6 +587,10 @@
: progressSuppressingEventHandler;
}
+ TopDownActionCache getTopDownActionCache() {
+ return topDownActionCache;
+ }
+
/**
* Returns an ActionExecutionContext suitable for executing a particular action. The caller should
* pass the returned context to {@link #executeAction}, and any other method that needs to execute
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 540fdd9..c1d1747 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -607,6 +607,7 @@
new ActionExecutionFunction(skyframeActionExecutor, directories, tsgm);
map.put(SkyFunctions.ACTION_EXECUTION, actionExecutionFunction);
this.actionExecutionFunction = actionExecutionFunction;
+ map.put(SkyFunctions.ACTION_SKETCH, new ActionSketchFunction(actionKeyContext));
map.put(
SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, new RecursiveFilesystemTraversalFunction());
map.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction(directories::getExecRoot));
@@ -1542,6 +1543,7 @@
Set<ConfiguredTarget> exclusiveTests,
OptionsProvider options,
ActionCacheChecker actionCacheChecker,
+ TopDownActionCache topDownActionCache,
@Nullable EvaluationProgressReceiver executionProgressReceiver,
TopLevelArtifactContext topLevelArtifactContext)
throws InterruptedException {
@@ -1551,7 +1553,7 @@
try (SilentCloseable c =
Profiler.instance().profile("skyframeActionExecutor.prepareForExecution")) {
skyframeActionExecutor.prepareForExecution(
- reporter, executor, options, actionCacheChecker, outputService);
+ reporter, executor, options, actionCacheChecker, topDownActionCache, outputService);
}
resourceManager.resetResourceUsage();
@@ -1589,6 +1591,7 @@
ConfiguredTarget exclusiveTest,
OptionsProvider options,
ActionCacheChecker actionCacheChecker,
+ TopDownActionCache topDownActionCache,
@Nullable EvaluationProgressReceiver executionProgressReceiver,
TopLevelArtifactContext topLevelArtifactContext)
throws InterruptedException {
@@ -1598,7 +1601,7 @@
try (SilentCloseable c =
Profiler.instance().profile("skyframeActionExecutor.prepareForExecution")) {
skyframeActionExecutor.prepareForExecution(
- reporter, executor, options, actionCacheChecker, outputService);
+ reporter, executor, options, actionCacheChecker, topDownActionCache, outputService);
}
resourceManager.resetResourceUsage();
@@ -1622,8 +1625,13 @@
@VisibleForTesting
public void prepareBuildingForTestingOnly(
- Reporter reporter, Executor executor, OptionsProvider options, ActionCacheChecker checker) {
- skyframeActionExecutor.prepareForExecution(reporter, executor, options, checker, outputService);
+ Reporter reporter,
+ Executor executor,
+ OptionsProvider options,
+ ActionCacheChecker checker,
+ TopDownActionCache topDownActionCache) {
+ skyframeActionExecutor.prepareForExecution(
+ reporter, executor, options, checker, topDownActionCache, outputService);
}
EvaluationResult<SkyValue> targetPatterns(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TopDownActionCache.java b/src/main/java/com/google/devtools/build/lib/skyframe/TopDownActionCache.java
new file mode 100644
index 0000000..a508e25
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TopDownActionCache.java
@@ -0,0 +1,33 @@
+// Copyright 2019 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.lib.skyframe;
+
+import com.google.devtools.build.lib.actionsketch.ActionSketch;
+import javax.annotation.Nullable;
+
+/**
+ * A top-down action cache is a cache of {@link ActionSketch} to {@link ActionExecutionValue}.
+ *
+ * <p>Unlike {@link com.google.devtools.build.lib.actions.ActionCacheChecker}, a top-down cache can
+ * cull large subgraphs by computing the transitive cache key (known as the {@link ActionSketch}).
+ */
+public interface TopDownActionCache {
+
+ /** Retrieves the cached value for the given action sketch, or null. */
+ @Nullable
+ ActionExecutionValue get(ActionSketch sketch);
+
+ /** Puts the sketch into the top-down cache. May complete asynchronously. */
+ void put(ActionSketch sketch, ActionExecutionValue value);
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
index 968c424..71cba10 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -78,6 +78,7 @@
"//src/main/java/com/google/devtools/build/lib:util",
"//src/main/java/com/google/devtools/build/lib/actions",
"//src/main/java/com/google/devtools/build/lib/actions:localhost_capacity",
+ "//src/main/java/com/google/devtools/build/lib/actionsketch:action_sketch",
"//src/main/java/com/google/devtools/build/lib/analysis/platform",
"//src/main/java/com/google/devtools/build/lib/causes",
"//src/main/java/com/google/devtools/build/lib/clock",
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index c4b7081..50fe5a3 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -140,6 +140,7 @@
protected OptionsParser options;
protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
+ private TopDownActionCache topDownActionCache;
@Before
public final void initialize() throws Exception {
@@ -153,6 +154,11 @@
ResourceManager.instance().setAvailableResources(ResourceSet.createWithRamCpu(100, 1));
actions = new LinkedHashSet<>();
actionTemplateExpansionFunction = new ActionTemplateExpansionFunction(actionKeyContext);
+ topDownActionCache = initTopDownActionCache();
+ }
+
+ protected TopDownActionCache initTopDownActionCache() {
+ return null;
}
protected void clearActions() {
@@ -262,6 +268,7 @@
.put(
SkyFunctions.ACTION_TEMPLATE_EXPANSION,
new DelegatingActionTemplateExpansionFunction())
+ .put(SkyFunctions.ACTION_SKETCH, new ActionSketchFunction(actionKeyContext))
.build(),
differencer,
evaluationProgressReceiver);
@@ -310,6 +317,7 @@
options,
new ActionCacheChecker(
actionCache, null, actionKeyContext, ALWAYS_EXECUTE_FILTER, null),
+ topDownActionCache,
null);
skyframeActionExecutor.setActionExecutionProgressReportingObjects(
EMPTY_PROGRESS_SUPPLIER, EMPTY_COMPLETION_RECEIVER);
@@ -444,9 +452,7 @@
}
protected void buildArtifacts(Builder builder, Executor executor, Artifact... artifacts)
- throws BuildFailedException, AbruptExitException, InterruptedException, TestExecException,
- OptionsParsingException {
-
+ throws BuildFailedException, AbruptExitException, InterruptedException, TestExecException {
tsgm.setCommandStartTime();
Set<Artifact> artifactsToBuild = Sets.newHashSet(artifacts);
Set<ConfiguredTargetKey> builtTargets = new HashSet<>();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TopDownActionCacheTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TopDownActionCacheTest.java
new file mode 100644
index 0000000..e4a0f6d
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TopDownActionCacheTest.java
@@ -0,0 +1,216 @@
+// Copyright 2019 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.lib.skyframe;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.actionsketch.ActionSketch;
+import com.google.devtools.build.lib.util.Fingerprint;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import java.util.Collection;
+import javax.annotation.Nullable;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for top-down, transitive action caching. */
+@RunWith(JUnit4.class)
+public class TopDownActionCacheTest extends TimestampBuilderTestCase {
+
+ @Override
+ protected TopDownActionCache initTopDownActionCache() {
+ return new InMemoryTopDownActionCache();
+ }
+
+ private void buildArtifacts(Artifact... artifacts) throws Exception {
+ buildArtifacts(amnesiacBuilder(), artifacts);
+ }
+
+ @Test
+ public void testAmnesiacBuilderGetsTopDownHit() throws Exception {
+ Artifact hello = createDerivedArtifact("hello");
+ Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+ button.pressed = false;
+ buildArtifacts(hello);
+ assertThat(button.pressed).isTrue();
+
+ button.pressed = false;
+ buildArtifacts(hello);
+ assertThat(button.pressed).isFalse();
+ }
+
+ @Test
+ public void testTransitiveTopDownCache() throws Exception {
+ Artifact hello = createDerivedArtifact("hello");
+ Artifact hello2 = createDerivedArtifact("hello2");
+ Button button = createActionButton(emptySet, ImmutableSet.of(hello));
+ Button button2 = createActionButton(ImmutableSet.of(hello), ImmutableSet.of(hello2));
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isTrue();
+ assertThat(button2.pressed).isTrue();
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isFalse();
+ assertThat(button2.pressed).isFalse();
+ }
+
+ @Test
+ public void testActionKeyCaching() throws Exception {
+ Artifact hello = createDerivedArtifact("hello");
+ Artifact hello2 = createDerivedArtifact("hello2");
+
+ ActionKeyButton button = createActionKeyButton(emptySet, ImmutableSet.of(hello), "abc");
+ ActionKeyButton button2 =
+ createActionKeyButton(ImmutableSet.of(hello), ImmutableSet.of(hello2), "xyz");
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isTrue();
+ assertThat(button2.pressed).isTrue();
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isFalse();
+ assertThat(button2.pressed).isFalse();
+
+ clearActions();
+ hello = createDerivedArtifact("hello");
+ hello2 = createDerivedArtifact("hello2");
+ button = createActionKeyButton(emptySet, ImmutableSet.of(hello), "abc");
+ button2 = createActionKeyButton(ImmutableSet.of(hello), ImmutableSet.of(hello2), "123");
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isFalse();
+ assertThat(button2.pressed).isTrue();
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isFalse();
+ assertThat(button2.pressed).isFalse();
+
+ clearActions();
+ hello = createDerivedArtifact("hello");
+ hello2 = createDerivedArtifact("hello2");
+ button = createActionKeyButton(emptySet, ImmutableSet.of(hello), "456");
+ button2 = createActionKeyButton(ImmutableSet.of(hello), ImmutableSet.of(hello2), "123");
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isTrue();
+ assertThat(button2.pressed).isTrue();
+
+ button.pressed = false;
+ button2.pressed = false;
+ buildArtifacts(hello2);
+ assertThat(button.pressed).isFalse();
+ assertThat(button2.pressed).isFalse();
+ }
+
+ @Test
+ public void testSingleSourceArtifactChanged() throws Exception {
+ Artifact hello = createSourceArtifact("hello");
+ hello.getPath().getParentDirectory().createDirectoryAndParents();
+ FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content1");
+
+ Artifact goodbye = createDerivedArtifact("goodbye");
+ Button button = createActionButton(ImmutableSet.of(hello), Sets.newHashSet(goodbye));
+
+ button.pressed = false;
+ buildArtifacts(goodbye);
+ assertThat(button.pressed).isTrue();
+
+ button.pressed = false;
+ buildArtifacts(goodbye);
+ assertThat(button.pressed).isFalse(); // top-down cached
+
+ FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content1");
+ button.pressed = false;
+ buildArtifacts(goodbye);
+ assertThat(button.pressed).isFalse(); // top-down cached
+
+ FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content2");
+ button.pressed = false;
+ buildArtifacts(goodbye);
+ assertThat(button.pressed).isTrue(); // built
+
+ button.pressed = false;
+ buildArtifacts(goodbye);
+ assertThat(button.pressed).isFalse(); // top-down cached
+ }
+
+ private static class InMemoryTopDownActionCache implements TopDownActionCache {
+ private final Cache<ActionSketch, ActionExecutionValue> cache =
+ CacheBuilder.newBuilder().build();
+
+ @Nullable
+ @Override
+ public ActionExecutionValue get(ActionSketch sketch) {
+ return cache.getIfPresent(sketch);
+ }
+
+ @Override
+ public void put(ActionSketch sketch, ActionExecutionValue value) {
+ cache.put(sketch, value);
+ }
+ }
+
+ private static class MutableActionKeyAction extends TestAction {
+
+ private final ActionKeyButton button;
+
+ public MutableActionKeyAction(
+ ActionKeyButton button, Collection<Artifact> inputs, Collection<Artifact> outputs) {
+ super(button, inputs, outputs);
+ this.button = button;
+ }
+
+ @Override
+ protected void computeKey(ActionKeyContext actionKeyContext, Fingerprint fp) {
+ super.computeKey(actionKeyContext, fp);
+ fp.addString(button.key);
+ }
+ }
+
+ private static class ActionKeyButton extends Button {
+ private final String key;
+
+ public ActionKeyButton(String key) {
+ this.key = key;
+ }
+ }
+
+ private ActionKeyButton createActionKeyButton(
+ Collection<Artifact> inputs, Collection<Artifact> outputs, String key) {
+ ActionKeyButton button = new ActionKeyButton(key);
+ registerAction(new MutableActionKeyAction(button, inputs, outputs));
+ return button;
+ }
+}
