Remote: Cache merkle trees
When --experimental_remote_merkle_tree_cache is set, Merkle tree calculations are cached for each node in the input NestedSets (depsets). This drastically improves the speed when checking for remote cache hits. One example reduced the Merkle tree calculation time from 78 ms to 3 ms for 3000 inputs.
The memory foot print of the cache is controlled by --experimental_remote_merkle_tree_cache_size.
The caching is discarded after each build to free up memory, the cache setup time is negligible.
Fixes #10875.
Closes #13879.
PiperOrigin-RevId: 405793372
diff --git a/src/main/java/com/google/devtools/build/lib/actions/CompositeRunfilesSupplier.java b/src/main/java/com/google/devtools/build/lib/actions/CompositeRunfilesSupplier.java
index 24aef85..c29b5c6 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/CompositeRunfilesSupplier.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/CompositeRunfilesSupplier.java
@@ -66,6 +66,20 @@
}
@Override
+ public boolean equals(Object other) {
+ if (!(other instanceof CompositeRunfilesSupplier)) {
+ return false;
+ }
+ CompositeRunfilesSupplier that = (CompositeRunfilesSupplier) other;
+ return suppliers.equals(that.suppliers);
+ }
+
+ @Override
+ public int hashCode() {
+ return suppliers.hashCode();
+ }
+
+ @Override
public NestedSet<Artifact> getArtifacts() {
NestedSetBuilder<Artifact> result = NestedSetBuilder.stableOrder();
for (RunfilesSupplier supplier : suppliers) {
diff --git a/src/main/java/com/google/devtools/build/lib/actions/EmptyRunfilesSupplier.java b/src/main/java/com/google/devtools/build/lib/actions/EmptyRunfilesSupplier.java
index 5c32d6f..44086cb 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/EmptyRunfilesSupplier.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/EmptyRunfilesSupplier.java
@@ -24,13 +24,23 @@
import java.util.Map;
/** Empty implementation of RunfilesSupplier */
-public class EmptyRunfilesSupplier implements RunfilesSupplier {
+public final class EmptyRunfilesSupplier implements RunfilesSupplier {
@AutoCodec public static final EmptyRunfilesSupplier INSTANCE = new EmptyRunfilesSupplier();
private EmptyRunfilesSupplier() {}
@Override
+ public boolean equals(Object other) {
+ return (other instanceof EmptyRunfilesSupplier);
+ }
+
+ @Override
+ public int hashCode() {
+ return 0;
+ }
+
+ @Override
public NestedSet<Artifact> getArtifacts() {
return NestedSetBuilder.<Artifact>stableOrder().build();
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SingleRunfilesSupplier.java b/src/main/java/com/google/devtools/build/lib/analysis/SingleRunfilesSupplier.java
index 56dc97d..126c0e9 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SingleRunfilesSupplier.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SingleRunfilesSupplier.java
@@ -27,6 +27,7 @@
import com.google.devtools.build.lib.vfs.PathFragment;
import java.lang.ref.SoftReference;
import java.util.Map;
+import java.util.Objects;
import java.util.function.Supplier;
import javax.annotation.Nullable;
@@ -47,6 +48,7 @@
return new SingleRunfilesSupplier(
runfilesSupport.getRunfilesDirectoryExecPath(),
runfilesSupport.getRunfiles(),
+ /*runfilesCachingEnabled=*/ false,
/*manifest=*/ null,
runfilesSupport.isBuildRunfileLinks(),
runfilesSupport.isRunfilesEnabled());
@@ -68,7 +70,7 @@
return new SingleRunfilesSupplier(
runfilesDir,
runfiles,
- new RunfilesCacher(runfiles),
+ /*runfilesCachingEnabled=*/ true,
/*manifest=*/ null,
buildRunfileLinks,
runfileLinksEnabled);
@@ -95,7 +97,25 @@
this(
runfilesDir,
runfiles,
- () -> runfiles.getRunfilesInputs(/*eventHandler=*/ null, /*location=*/ null),
+ /*runfilesCachingEnabled=*/ false,
+ manifest,
+ buildRunfileLinks,
+ runfileLinksEnabled);
+ }
+
+ private SingleRunfilesSupplier(
+ PathFragment runfilesDir,
+ Runfiles runfiles,
+ boolean runfilesCachingEnabled,
+ @Nullable Artifact manifest,
+ boolean buildRunfileLinks,
+ boolean runfileLinksEnabled) {
+ this(
+ runfilesDir,
+ runfiles,
+ runfilesCachingEnabled
+ ? new RunfilesCacher(runfiles)
+ : () -> runfiles.getRunfilesInputs(/*eventHandler=*/ null, /*location=*/ null),
manifest,
buildRunfileLinks,
runfileLinksEnabled);
@@ -118,6 +138,26 @@
}
@Override
+ public boolean equals(Object other) {
+ if (!(other instanceof SingleRunfilesSupplier)) {
+ return false;
+ }
+
+ SingleRunfilesSupplier that = (SingleRunfilesSupplier) other;
+ // Not dependent on runfilesInputs which is only used for enabling caching.
+ return (Objects.equals(runfilesDir, that.runfilesDir)
+ && Objects.equals(runfiles, that.runfiles)
+ && Objects.equals(manifest, that.manifest)
+ && (buildRunfileLinks == that.buildRunfileLinks)
+ && (runfileLinksEnabled == that.runfileLinksEnabled));
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(runfilesDir, runfiles, manifest, buildRunfileLinks, runfileLinksEnabled);
+ }
+
+ @Override
public NestedSet<Artifact> getArtifacts() {
return runfiles.getAllArtifacts();
}
diff --git a/src/main/java/com/google/devtools/build/lib/exec/AbstractSpawnStrategy.java b/src/main/java/com/google/devtools/build/lib/exec/AbstractSpawnStrategy.java
index 5b9df88..8dab93d 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/AbstractSpawnStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/AbstractSpawnStrategy.java
@@ -270,6 +270,11 @@
}
@Override
+ public SpawnInputExpander getSpawnInputExpander() {
+ return spawnInputExpander;
+ }
+
+ @Override
public void lockOutputFiles() throws InterruptedException {
if (stopConcurrentSpawns != null) {
stopConcurrentSpawns.stop();
diff --git a/src/main/java/com/google/devtools/build/lib/exec/BUILD b/src/main/java/com/google/devtools/build/lib/exec/BUILD
index 0fa09ae..bee9f38 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/exec/BUILD
@@ -275,6 +275,7 @@
"SpawnSchedulingEvent.java",
],
deps = [
+ ":spawn_input_expander",
":tree_deleter",
"//src/main/java/com/google/devtools/build/lib/actions",
"//src/main/java/com/google/devtools/build/lib/actions:artifacts",
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SpawnInputExpander.java b/src/main/java/com/google/devtools/build/lib/exec/SpawnInputExpander.java
index 160b965..44cb021 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SpawnInputExpander.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SpawnInputExpander.java
@@ -33,11 +33,13 @@
import com.google.devtools.build.lib.actions.RunfilesSupplier;
import com.google.devtools.build.lib.actions.Spawn;
import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.collect.nestedset.Order;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.io.IOException;
+import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
@@ -95,7 +97,7 @@
this.relSymlinkBehavior = relSymlinkBehavior;
}
- private void addMapping(
+ private static void addMapping(
Map<PathFragment, ActionInput> inputMappings,
PathFragment targetLocation,
ActionInput input,
@@ -215,13 +217,12 @@
}
}
- private void addInputs(
+ private static void addInputs(
Map<PathFragment, ActionInput> inputMap,
- Spawn spawn,
+ NestedSet<? extends ActionInput> inputFiles,
ArtifactExpander artifactExpander,
PathFragment baseDirectory) {
- List<ActionInput> inputs =
- ActionInputHelper.expandArtifacts(spawn.getInputFiles(), artifactExpander);
+ List<ActionInput> inputs = ActionInputHelper.expandArtifacts(inputFiles, artifactExpander);
for (ActionInput input : inputs) {
addMapping(inputMap, input.getExecPath(), input, baseDirectory);
}
@@ -243,7 +244,7 @@
MetadataProvider actionInputFileCache)
throws IOException, ForbiddenActionInputException {
TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
- addInputs(inputMap, spawn, artifactExpander, baseDirectory);
+ addInputs(inputMap, spawn.getInputFiles(), artifactExpander, baseDirectory);
addRunfilesToInputs(
inputMap,
spawn.getRunfilesSupplier(),
@@ -254,6 +255,126 @@
return inputMap;
}
+ /** The interface for accessing part of the input hierarchy. */
+ public interface InputWalker {
+ SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
+ throws IOException, ForbiddenActionInputException;
+
+ void visitNonLeaves(InputVisitor visitor) throws IOException, ForbiddenActionInputException;
+ }
+
+ /** The interface for visiting part of the input hierarchy. */
+ public interface InputVisitor {
+ /**
+ * Visits a part of the input hierarchy.
+ *
+ * <p>{@code nodeKey} can be used as key when memoizing visited parts of the hierarchy.
+ */
+ void visit(Object nodeKey, InputWalker walker)
+ throws IOException, ForbiddenActionInputException;
+ }
+
+ /**
+ * Visits the input files hierarchy in a depth first manner.
+ *
+ * <p>Similar to {@link #getInputMapping} but allows for early exit, by not visiting children,
+ * when walking through the input hierarchy. By applying memoization, the retrieval process of the
+ * inputs can be speeded up.
+ *
+ * <p>{@code baseDirectory} is prepended to every path in the input key. This is useful if the
+ * mapping is used in a context where the directory relative to which the keys are interpreted is
+ * not the same as the execroot.
+ */
+ public void walkInputs(
+ Spawn spawn,
+ ArtifactExpander artifactExpander,
+ PathFragment baseDirectory,
+ MetadataProvider actionInputFileCache,
+ InputVisitor visitor)
+ throws IOException, ForbiddenActionInputException {
+ walkNestedSetInputs(baseDirectory, spawn.getInputFiles(), artifactExpander, visitor);
+
+ RunfilesSupplier runfilesSupplier = spawn.getRunfilesSupplier();
+ visitor.visit(
+ // The list of variables affecting the functional expressions below.
+ Arrays.asList(
+ // Assuming that artifactExpander and actionInputFileCache, different for each spawn,
+ // always expand the same way.
+ this, // For accessing addRunfilesToInputs.
+ runfilesSupplier,
+ baseDirectory),
+ new InputWalker() {
+ @Override
+ public SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
+ throws IOException, ForbiddenActionInputException {
+ TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
+ addRunfilesToInputs(
+ inputMap, runfilesSupplier, actionInputFileCache, artifactExpander, baseDirectory);
+ return inputMap;
+ }
+
+ @Override
+ public void visitNonLeaves(InputVisitor childVisitor) {}
+ });
+
+ Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMappings = spawn.getFilesetMappings();
+ // filesetMappings is assumed to be very small, so no need to implement visitNonLeaves() for
+ // improved runtime.
+ visitor.visit(
+ // The list of variables affecting the functional expressions below.
+ Arrays.asList(
+ this, // For accessing addFilesetManifests.
+ filesetMappings,
+ baseDirectory),
+ new InputWalker() {
+ @Override
+ public SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
+ throws ForbiddenRelativeSymlinkException {
+ TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
+ addFilesetManifests(filesetMappings, inputMap, baseDirectory);
+ return inputMap;
+ }
+
+ @Override
+ public void visitNonLeaves(InputVisitor childVisitor) {}
+ });
+ }
+
+ /** Walks through one level of a {@link NestedSet} of {@link ActionInput}s. */
+ private void walkNestedSetInputs(
+ PathFragment baseDirectory,
+ NestedSet<? extends ActionInput> someInputFiles,
+ ArtifactExpander artifactExpander,
+ InputVisitor visitor)
+ throws IOException, ForbiddenActionInputException {
+ visitor.visit(
+ // addInputs is static so no need to add 'this' as dependent key.
+ Arrays.asList(
+ // Assuming that artifactExpander, different for each spawn, always expands the same
+ // way.
+ someInputFiles.toNode(), baseDirectory),
+ new InputWalker() {
+ @Override
+ public SortedMap<PathFragment, ActionInput> getLeavesInputMapping() {
+ TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
+ addInputs(
+ inputMap,
+ NestedSetBuilder.wrap(someInputFiles.getOrder(), someInputFiles.getLeaves()),
+ artifactExpander,
+ baseDirectory);
+ return inputMap;
+ }
+
+ @Override
+ public void visitNonLeaves(InputVisitor childVisitor)
+ throws IOException, ForbiddenActionInputException {
+ for (NestedSet<? extends ActionInput> subInputs : someInputFiles.getNonLeaves()) {
+ walkNestedSetInputs(baseDirectory, subInputs, artifactExpander, childVisitor);
+ }
+ }
+ });
+ }
+
/**
* Exception signaling that an input was not a regular file: most likely a directory. This
* exception is currently never thrown in practice since we do not enforce "strict" mode.
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java b/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
index 5cadd59..673b6f9 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
@@ -161,6 +161,12 @@
// directories? Or maybe we need a separate method to return the set of directories?
ArtifactExpander getArtifactExpander();
+ /** A spawn input expander. */
+ // TODO(moroten): This is only used for the remote cache and remote execution to optimize
+ // Merkle tree generation. Having both this and the getInputMapping method seems a bit
+ // duplicated.
+ SpawnInputExpander getSpawnInputExpander();
+
/** The {@link ArtifactPathResolver} to use when directly writing output files. */
default ArtifactPathResolver getPathResolver() {
return ArtifactPathResolver.IDENTITY;
diff --git a/src/main/java/com/google/devtools/build/lib/remote/BUILD b/src/main/java/com/google/devtools/build/lib/remote/BUILD
index 1490cc8..e2e1b98 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/remote/BUILD
@@ -66,6 +66,7 @@
"//src/main/java/com/google/devtools/build/lib/exec:module_action_context_registry",
"//src/main/java/com/google/devtools/build/lib/exec:remote_local_fallback_registry",
"//src/main/java/com/google/devtools/build/lib/exec:spawn_cache",
+ "//src/main/java/com/google/devtools/build/lib/exec:spawn_input_expander",
"//src/main/java/com/google/devtools/build/lib/exec:spawn_runner",
"//src/main/java/com/google/devtools/build/lib/exec:spawn_strategy_registry",
"//src/main/java/com/google/devtools/build/lib/packages",
@@ -94,6 +95,7 @@
"//src/main/java/com/google/devtools/common/options",
"//src/main/protobuf:failure_details_java_proto",
"//third_party:auth",
+ "//third_party:caffeine",
"//third_party:flogger",
"//third_party:guava",
"//third_party:jsr305",
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionService.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionService.java
index 7722aff..aa48ba9 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionService.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionService.java
@@ -53,6 +53,8 @@
import build.bazel.remote.execution.v2.RequestMetadata;
import build.bazel.remote.execution.v2.SymlinkNode;
import build.bazel.remote.execution.v2.Tree;
+import com.github.benmanes.caffeine.cache.Cache;
+import com.github.benmanes.caffeine.cache.Caffeine;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.base.Strings;
@@ -73,6 +75,7 @@
import com.google.devtools.build.lib.actions.ExecException;
import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
import com.google.devtools.build.lib.actions.ForbiddenActionInputException;
+import com.google.devtools.build.lib.actions.MetadataProvider;
import com.google.devtools.build.lib.actions.Spawn;
import com.google.devtools.build.lib.actions.SpawnResult;
import com.google.devtools.build.lib.actions.Spawns;
@@ -82,6 +85,7 @@
import com.google.devtools.build.lib.buildtool.buildevent.BuildInterruptedEvent;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.Reporter;
+import com.google.devtools.build.lib.exec.SpawnInputExpander.InputWalker;
import com.google.devtools.build.lib.exec.SpawnRunner.SpawnExecutionContext;
import com.google.devtools.build.lib.profiler.Profiler;
import com.google.devtools.build.lib.profiler.ProfilerTask;
@@ -133,6 +137,7 @@
import java.util.Objects;
import java.util.SortedMap;
import java.util.TreeSet;
+import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.Executor;
import java.util.concurrent.atomic.AtomicBoolean;
import javax.annotation.Nullable;
@@ -154,6 +159,7 @@
@Nullable private final RemoteExecutionClient remoteExecutor;
private final ImmutableSet<PathFragment> filesToDownload;
@Nullable private final Path captureCorruptedOutputsDir;
+ private final Cache<Object, MerkleTree> merkleTreeCache;
private final Scheduler scheduler;
@@ -184,6 +190,14 @@
this.remoteOptions = remoteOptions;
this.remoteCache = remoteCache;
this.remoteExecutor = remoteExecutor;
+
+ Caffeine<Object, Object> merkleTreeCacheBuilder = Caffeine.newBuilder().softValues();
+ // remoteMerkleTreesCacheSize = 0 means limitless.
+ if (remoteOptions.remoteMerkleTreeCacheSize != 0) {
+ merkleTreeCacheBuilder.maximumSize(remoteOptions.remoteMerkleTreeCacheSize);
+ }
+ this.merkleTreeCache = merkleTreeCacheBuilder.build();
+
ImmutableSet.Builder<PathFragment> filesToDownloadBuilder = ImmutableSet.builder();
for (ActionInput actionInput : filesToDownload) {
filesToDownloadBuilder.add(actionInput.getExecPath());
@@ -238,7 +252,7 @@
private final Spawn spawn;
private final SpawnExecutionContext spawnExecutionContext;
private final RemoteActionExecutionContext remoteActionExecutionContext;
- private final SortedMap<PathFragment, ActionInput> inputMap;
+ private final RemotePathResolver remotePathResolver;
private final MerkleTree merkleTree;
private final Digest commandHash;
private final Command command;
@@ -249,7 +263,7 @@
Spawn spawn,
SpawnExecutionContext spawnExecutionContext,
RemoteActionExecutionContext remoteActionExecutionContext,
- SortedMap<PathFragment, ActionInput> inputMap,
+ RemotePathResolver remotePathResolver,
MerkleTree merkleTree,
Digest commandHash,
Command command,
@@ -258,7 +272,7 @@
this.spawn = spawn;
this.spawnExecutionContext = spawnExecutionContext;
this.remoteActionExecutionContext = remoteActionExecutionContext;
- this.inputMap = inputMap;
+ this.remotePathResolver = remotePathResolver;
this.merkleTree = merkleTree;
this.commandHash = commandHash;
this.command = command;
@@ -297,8 +311,9 @@
* Returns a {@link SortedMap} which maps from input paths for remote action to {@link
* ActionInput}.
*/
- public SortedMap<PathFragment, ActionInput> getInputMap() {
- return inputMap;
+ public SortedMap<PathFragment, ActionInput> getInputMap()
+ throws IOException, ForbiddenActionInputException {
+ return remotePathResolver.getInputMapping(spawnExecutionContext);
}
/**
@@ -362,12 +377,53 @@
&& Spawns.mayBeExecutedRemotely(spawn);
}
+ private MerkleTree buildInputMerkleTree(Spawn spawn, SpawnExecutionContext context)
+ throws IOException, ForbiddenActionInputException {
+ if (remoteOptions.remoteMerkleTreeCache) {
+ MetadataProvider metadataProvider = context.getMetadataProvider();
+ ConcurrentLinkedQueue<MerkleTree> subMerkleTrees = new ConcurrentLinkedQueue<>();
+ remotePathResolver.walkInputs(
+ spawn,
+ context,
+ (Object nodeKey, InputWalker walker) -> {
+ subMerkleTrees.add(buildMerkleTreeVisitor(nodeKey, walker, metadataProvider));
+ });
+ return MerkleTree.merge(subMerkleTrees, digestUtil);
+ } else {
+ SortedMap<PathFragment, ActionInput> inputMap = remotePathResolver.getInputMapping(context);
+ return MerkleTree.build(inputMap, context.getMetadataProvider(), execRoot, digestUtil);
+ }
+ }
+
+ private MerkleTree buildMerkleTreeVisitor(
+ Object nodeKey, InputWalker walker, MetadataProvider metadataProvider)
+ throws IOException, ForbiddenActionInputException {
+ MerkleTree result = merkleTreeCache.getIfPresent(nodeKey);
+ if (result == null) {
+ result = uncachedBuildMerkleTreeVisitor(walker, metadataProvider);
+ merkleTreeCache.put(nodeKey, result);
+ }
+ return result;
+ }
+
+ @VisibleForTesting
+ public MerkleTree uncachedBuildMerkleTreeVisitor(
+ InputWalker walker, MetadataProvider metadataProvider)
+ throws IOException, ForbiddenActionInputException {
+ ConcurrentLinkedQueue<MerkleTree> subMerkleTrees = new ConcurrentLinkedQueue<>();
+ subMerkleTrees.add(
+ MerkleTree.build(walker.getLeavesInputMapping(), metadataProvider, execRoot, digestUtil));
+ walker.visitNonLeaves(
+ (Object subNodeKey, InputWalker subWalker) -> {
+ subMerkleTrees.add(buildMerkleTreeVisitor(subNodeKey, subWalker, metadataProvider));
+ });
+ return MerkleTree.merge(subMerkleTrees, digestUtil);
+ }
+
/** Creates a new {@link RemoteAction} instance from spawn. */
public RemoteAction buildRemoteAction(Spawn spawn, SpawnExecutionContext context)
throws IOException, UserExecException, ForbiddenActionInputException {
- SortedMap<PathFragment, ActionInput> inputMap = remotePathResolver.getInputMapping(context);
- final MerkleTree merkleTree =
- MerkleTree.build(inputMap, context.getMetadataProvider(), execRoot, digestUtil);
+ final MerkleTree merkleTree = buildInputMerkleTree(spawn, context);
// Get the remote platform properties.
Platform platform = PlatformUtils.getPlatformProto(spawn, remoteOptions);
@@ -400,7 +456,7 @@
spawn,
context,
remoteActionExecutionContext,
- inputMap,
+ remotePathResolver,
merkleTree,
commandHash,
command,
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
index 3b8344c..e40969b 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
@@ -192,7 +192,7 @@
if (options.experimentalGuardAgainstConcurrentChanges) {
try (SilentCloseable c = prof.profile("RemoteCache.checkForConcurrentModifications")) {
checkForConcurrentModifications();
- } catch (IOException e) {
+ } catch (IOException | ForbiddenActionInputException e) {
report(Event.warn(e.getMessage()));
return;
}
@@ -204,7 +204,8 @@
@Override
public void close() {}
- private void checkForConcurrentModifications() throws IOException {
+ private void checkForConcurrentModifications()
+ throws IOException, ForbiddenActionInputException {
for (ActionInput input : action.getInputMap().values()) {
if (input instanceof VirtualActionInput) {
continue;
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/BUILD b/src/main/java/com/google/devtools/build/lib/remote/common/BUILD
index 1926df1..e6279c3 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/BUILD
@@ -19,6 +19,7 @@
"//src/main/java/com/google/devtools/build/lib/actions:artifacts",
"//src/main/java/com/google/devtools/build/lib/actions:file_metadata",
"//src/main/java/com/google/devtools/build/lib/concurrent",
+ "//src/main/java/com/google/devtools/build/lib/exec:spawn_input_expander",
"//src/main/java/com/google/devtools/build/lib/exec:spawn_runner",
"//src/main/java/com/google/devtools/build/lib/vfs",
"//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/RemotePathResolver.java b/src/main/java/com/google/devtools/build/lib/remote/common/RemotePathResolver.java
index 5b063c6..d2c1c2c 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/RemotePathResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/RemotePathResolver.java
@@ -18,6 +18,8 @@
import com.google.devtools.build.lib.actions.ActionInput;
import com.google.devtools.build.lib.actions.ActionInputHelper;
import com.google.devtools.build.lib.actions.ForbiddenActionInputException;
+import com.google.devtools.build.lib.actions.Spawn;
+import com.google.devtools.build.lib.exec.SpawnInputExpander;
import com.google.devtools.build.lib.exec.SpawnRunner.SpawnExecutionContext;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
@@ -43,6 +45,10 @@
SortedMap<PathFragment, ActionInput> getInputMapping(SpawnExecutionContext context)
throws IOException, ForbiddenActionInputException;
+ void walkInputs(
+ Spawn spawn, SpawnExecutionContext context, SpawnInputExpander.InputVisitor visitor)
+ throws IOException, ForbiddenActionInputException;
+
/** Resolves the output path relative to input root for the given {@link Path}. */
String localPathToOutputPath(Path path);
@@ -100,6 +106,20 @@
}
@Override
+ public void walkInputs(
+ Spawn spawn, SpawnExecutionContext context, SpawnInputExpander.InputVisitor visitor)
+ throws IOException, ForbiddenActionInputException {
+ context
+ .getSpawnInputExpander()
+ .walkInputs(
+ spawn,
+ context.getArtifactExpander(),
+ PathFragment.EMPTY_FRAGMENT,
+ context.getMetadataProvider(),
+ visitor);
+ }
+
+ @Override
public String localPathToOutputPath(Path path) {
return path.relativeTo(execRoot).getPathString();
}
@@ -159,6 +179,20 @@
return context.getInputMapping(PathFragment.create(checkNotNull(getWorkingDirectory())));
}
+ @Override
+ public void walkInputs(
+ Spawn spawn, SpawnExecutionContext context, SpawnInputExpander.InputVisitor visitor)
+ throws IOException, ForbiddenActionInputException {
+ context
+ .getSpawnInputExpander()
+ .walkInputs(
+ spawn,
+ context.getArtifactExpander(),
+ PathFragment.create(checkNotNull(getWorkingDirectory())),
+ context.getMetadataProvider(),
+ visitor);
+ }
+
private Path getBase() {
if (incompatibleRemoteOutputPathsRelativeToInputRoot) {
return execRoot.getParentDirectory();
diff --git a/src/main/java/com/google/devtools/build/lib/remote/merkletree/MerkleTree.java b/src/main/java/com/google/devtools/build/lib/remote/merkletree/MerkleTree.java
index 5b33c57..f519402 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/merkletree/MerkleTree.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/merkletree/MerkleTree.java
@@ -18,9 +18,14 @@
import build.bazel.remote.execution.v2.DirectoryNode;
import build.bazel.remote.execution.v2.FileNode;
import com.google.common.base.Preconditions;
+import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Maps;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Sets;
import com.google.devtools.build.lib.actions.ActionInput;
import com.google.devtools.build.lib.actions.MetadataProvider;
import com.google.devtools.build.lib.profiler.Profiler;
@@ -30,10 +35,14 @@
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.protobuf.ByteString;
import java.io.IOException;
+import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
+import java.util.Objects;
import java.util.SortedMap;
-import java.util.concurrent.atomic.AtomicLong;
+import java.util.SortedSet;
+import java.util.TreeMap;
+import java.util.TreeSet;
import javax.annotation.Nullable;
/** A merkle tree representation as defined by the remote execution api. */
@@ -66,30 +75,70 @@
}
}
- private final Map<Digest, Directory> digestDirectoryMap;
- private final Map<Digest, PathOrBytes> digestFileMap;
+ private interface MerkleTreeDirectoryVisitor {
+
+ /**
+ * Visits each directory in a {@code MerkleTree}.
+ *
+ * <p>The order of the iteration is undefined.
+ *
+ * @param dir a directory in the {@code MerkleTree}.
+ */
+ void visitDirectory(MerkleTree dir);
+ }
+
+ private Map<Digest, Directory> digestDirectoryMap;
+ private Map<Digest, PathOrBytes> digestFileMap;
+ @Nullable private final Directory rootProto;
private final Digest rootDigest;
+ private final SortedSet<DirectoryTree.FileNode> files;
+ private final SortedMap<String, MerkleTree> directories;
private final long inputFiles;
private final long inputBytes;
private MerkleTree(
- Map<Digest, Directory> digestDirectoryMap,
- Map<Digest, PathOrBytes> digestFileMap,
+ @Nullable Directory rootProto,
Digest rootDigest,
+ SortedSet<DirectoryTree.FileNode> files,
+ SortedMap<String, MerkleTree> directories,
long inputFiles,
long inputBytes) {
- this.digestDirectoryMap = digestDirectoryMap;
- this.digestFileMap = digestFileMap;
- this.rootDigest = rootDigest;
+ this.digestDirectoryMap = null;
+ this.digestFileMap = null;
+ this.rootProto = rootProto;
+ this.rootDigest = Preconditions.checkNotNull(rootDigest, "rootDigest");
+ this.files = Preconditions.checkNotNull(files, "files");
+ this.directories = Preconditions.checkNotNull(directories, "directories");
this.inputFiles = inputFiles;
this.inputBytes = inputBytes;
}
- /** Returns the digest of the merkle tree's root. */
+ /** Returns the digest of the Merkle tree's root. */
+ @Nullable
+ public Directory getRootProto() {
+ return rootProto;
+ }
+
+ /** Returns the protobuf representation of the Merkle tree's root. */
public Digest getRootDigest() {
return rootDigest;
}
+ private SortedSet<DirectoryTree.FileNode> getFiles() {
+ return files;
+ }
+
+ private SortedMap<String, MerkleTree> getDirectories() {
+ return directories;
+ }
+
+ private void visitTree(MerkleTreeDirectoryVisitor visitor) {
+ visitor.visitDirectory(this);
+ for (MerkleTree dir : getDirectories().values()) {
+ dir.visitTree(visitor);
+ }
+ }
+
/** Returns the number of files represented by this merkle tree */
public long getInputFiles() {
return inputFiles;
@@ -100,14 +149,42 @@
return inputBytes;
}
+ private Map<Digest, Directory> getDigestDirectoryMap() {
+ if (this.digestDirectoryMap == null) {
+ Map<Digest, Directory> newDigestMap = Maps.newHashMap();
+ visitTree(
+ (dir) -> {
+ if (dir.getRootProto() != null) {
+ newDigestMap.put(dir.getRootDigest(), dir.getRootProto());
+ }
+ });
+ this.digestDirectoryMap = newDigestMap;
+ }
+ return this.digestDirectoryMap;
+ }
+
+ private Map<Digest, PathOrBytes> getDigestFileMap() {
+ if (this.digestFileMap == null) {
+ Map<Digest, PathOrBytes> newDigestMap = Maps.newHashMap();
+ visitTree(
+ (dir) -> {
+ for (DirectoryTree.FileNode file : dir.getFiles()) {
+ newDigestMap.put(file.getDigest(), toPathOrBytes(file));
+ }
+ });
+ this.digestFileMap = newDigestMap;
+ }
+ return this.digestFileMap;
+ }
+
@Nullable
public Directory getDirectoryByDigest(Digest digest) {
- return digestDirectoryMap.get(digest);
+ return getDigestDirectoryMap().get(digest);
}
@Nullable
public PathOrBytes getFileByDigest(Digest digest) {
- return digestFileMap.get(digest);
+ return getDigestFileMap().get(digest);
}
/**
@@ -115,7 +192,7 @@
* Directory} protobufs and {@link ActionInput} files.
*/
public Iterable<Digest> getAllDigests() {
- return Iterables.concat(digestDirectoryMap.keySet(), digestFileMap.keySet());
+ return Iterables.concat(getDigestDirectoryMap().keySet(), getDigestFileMap().keySet());
}
/**
@@ -161,37 +238,97 @@
Preconditions.checkNotNull(tree);
if (tree.isEmpty()) {
return new MerkleTree(
- ImmutableMap.of(), ImmutableMap.of(), digestUtil.compute(new byte[0]), 0, 0);
+ null,
+ digestUtil.compute(new byte[0]),
+ ImmutableSortedSet.of(),
+ ImmutableSortedMap.of(),
+ 0,
+ 0);
}
- Map<Digest, Directory> digestDirectoryMap =
- Maps.newHashMapWithExpectedSize(tree.numDirectories());
- Map<Digest, PathOrBytes> digestPathMap = Maps.newHashMapWithExpectedSize(tree.numFiles());
- Map<PathFragment, Digest> m = new HashMap<>();
- AtomicLong inputBytes = new AtomicLong(0);
+ Map<PathFragment, MerkleTree> m = new HashMap<>();
tree.visit(
(dirname, files, dirs) -> {
- Directory.Builder b = Directory.newBuilder();
- for (DirectoryTree.FileNode file : files) {
- b.addFiles(buildProto(file));
- digestPathMap.put(file.getDigest(), toPathOrBytes(file));
- inputBytes.addAndGet(file.getDigest().getSizeBytes());
- }
+ SortedMap<String, MerkleTree> subDirs = new TreeMap<>();
for (DirectoryTree.DirectoryNode dir : dirs) {
PathFragment subDirname = dirname.getRelative(dir.getPathSegment());
- Digest protoDirDigest =
- Preconditions.checkNotNull(m.remove(subDirname), "protoDirDigest was null");
- b.addDirectories(buildProto(dir, protoDirDigest));
- inputBytes.addAndGet(protoDirDigest.getSizeBytes());
+ MerkleTree subMerkleTree =
+ Preconditions.checkNotNull(m.remove(subDirname), "subMerkleTree was null");
+ subDirs.put(dir.getPathSegment(), subMerkleTree);
}
- Directory protoDir = b.build();
- Digest protoDirDigest = digestUtil.compute(protoDir);
- digestDirectoryMap.put(protoDirDigest, protoDir);
- m.put(dirname, protoDirDigest);
+ MerkleTree mt = buildMerkleTree(new TreeSet<>(files), subDirs, digestUtil);
+ m.put(dirname, mt);
});
- Digest rootDigest = m.get(PathFragment.EMPTY_FRAGMENT);
- inputBytes.addAndGet(rootDigest.getSizeBytes());
- return new MerkleTree(
- digestDirectoryMap, digestPathMap, rootDigest, tree.numFiles(), inputBytes.get());
+ MerkleTree rootMerkleTree = m.get(PathFragment.EMPTY_FRAGMENT);
+ Preconditions.checkState(
+ rootMerkleTree.getInputFiles() == tree.numFiles(),
+ "rootMerkleTree.getInputFiles() %s != tree.numFiles() %s",
+ rootMerkleTree.getInputFiles(),
+ tree.numFiles());
+ return rootMerkleTree;
+ }
+
+ public static MerkleTree merge(Collection<MerkleTree> merkleTrees, DigestUtil digestUtil) {
+ if (merkleTrees.isEmpty()) {
+ return build(new DirectoryTree(ImmutableMap.of(), 0), digestUtil);
+ }
+
+ MerkleTree firstMerkleTree = merkleTrees.iterator().next();
+ Digest firstRootDigest = firstMerkleTree.getRootDigest();
+ if (merkleTrees.stream()
+ .allMatch((mt) -> Objects.equals(mt.getRootDigest(), firstRootDigest))) {
+ // All are the same, pick the first one.
+ return firstMerkleTree;
+ }
+
+ // Some differ, do a full merge.
+ SortedSet<DirectoryTree.FileNode> files = Sets.newTreeSet();
+ for (MerkleTree merkleTree : merkleTrees) {
+ files.addAll(merkleTree.getFiles());
+ }
+
+ // Group all Merkle trees per path.
+ Multimap<String, MerkleTree> allDirsToMerge = ArrayListMultimap.create();
+ for (MerkleTree merkleTree : merkleTrees) {
+ merkleTree.getDirectories().forEach(allDirsToMerge::put);
+ }
+ // Merge the Merkle trees for each path.
+ SortedMap<String, MerkleTree> directories = new TreeMap<>();
+ allDirsToMerge
+ .asMap()
+ .forEach(
+ (baseName, dirsToMerge) -> directories.put(baseName, merge(dirsToMerge, digestUtil)));
+
+ return buildMerkleTree(files, directories, digestUtil);
+ }
+
+ private static MerkleTree buildMerkleTree(
+ SortedSet<DirectoryTree.FileNode> files,
+ SortedMap<String, MerkleTree> directories,
+ DigestUtil digestUtil) {
+ Directory.Builder b = Directory.newBuilder();
+ for (DirectoryTree.FileNode file : files) {
+ b.addFiles(buildProto(file));
+ }
+ for (Map.Entry<String, MerkleTree> nameAndDir : directories.entrySet()) {
+ b.addDirectories(buildProto(nameAndDir.getKey(), nameAndDir.getValue()));
+ }
+ Directory protoDir = b.build();
+ Digest protoDirDigest = digestUtil.compute(protoDir);
+
+ long inputFiles = files.size();
+ for (MerkleTree dir : directories.values()) {
+ inputFiles += dir.getInputFiles();
+ }
+
+ long inputBytes = protoDirDigest.getSizeBytes();
+ for (DirectoryTree.FileNode file : files) {
+ inputBytes += file.getDigest().getSizeBytes();
+ }
+ for (MerkleTree dir : directories.values()) {
+ inputBytes += dir.getInputBytes();
+ }
+
+ return new MerkleTree(protoDir, protoDirDigest, files, directories, inputFiles, inputBytes);
}
private static FileNode buildProto(DirectoryTree.FileNode file) {
@@ -202,11 +339,8 @@
.build();
}
- private static DirectoryNode buildProto(DirectoryTree.DirectoryNode dir, Digest protoDirDigest) {
- return DirectoryNode.newBuilder()
- .setName(dir.getPathSegment())
- .setDigest(protoDirDigest)
- .build();
+ private static DirectoryNode buildProto(String baseName, MerkleTree dir) {
+ return DirectoryNode.newBuilder().setName(baseName).setDigest(dir.getRootDigest()).build();
}
private static PathOrBytes toPathOrBytes(DirectoryTree.FileNode file) {
diff --git a/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java b/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
index b4896a2..89d6e1c 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
@@ -506,6 +506,29 @@
public boolean remoteVerifyDownloads;
@Option(
+ name = "experimental_remote_merkle_tree_cache",
+ defaultValue = "false",
+ documentationCategory = OptionDocumentationCategory.REMOTE,
+ effectTags = {OptionEffectTag.UNKNOWN},
+ help =
+ "If set to true, Merkle tree calculations will be memoized to improve the remote cache "
+ + "hit checking speed. The memory foot print of the cache is controlled by "
+ + "--experimental_remote_merkle_tree_cache_size.")
+ public boolean remoteMerkleTreeCache;
+
+ @Option(
+ name = "experimental_remote_merkle_tree_cache_size",
+ defaultValue = "0",
+ documentationCategory = OptionDocumentationCategory.REMOTE,
+ effectTags = {OptionEffectTag.UNKNOWN},
+ help =
+ "The number of Merkle trees to memoize to improve the remote cache hit checking speed. "
+ + "Even though the cache is automatically pruned according to Java's handling of "
+ + "soft references, out-of-memory errors can occur if set too high. If set to 0 "
+ + "(default), the cache size is unlimited.")
+ public long remoteMerkleTreeCacheSize;
+
+ @Option(
name = "remote_download_symlink_template",
defaultValue = "",
category = "remote",
diff --git a/src/test/java/com/google/devtools/build/lib/exec/local/BUILD b/src/test/java/com/google/devtools/build/lib/exec/local/BUILD
index 8727600..4a053aa 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/local/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/exec/local/BUILD
@@ -28,6 +28,7 @@
"//src/main/java/com/google/devtools/build/lib/actions:localhost_capacity",
"//src/main/java/com/google/devtools/build/lib/exec:bin_tools",
"//src/main/java/com/google/devtools/build/lib/exec:runfiles_tree_updater",
+ "//src/main/java/com/google/devtools/build/lib/exec:spawn_input_expander",
"//src/main/java/com/google/devtools/build/lib/exec:spawn_runner",
"//src/main/java/com/google/devtools/build/lib/exec/local",
"//src/main/java/com/google/devtools/build/lib/exec/local:options",
diff --git a/src/test/java/com/google/devtools/build/lib/exec/local/LocalSpawnRunnerTest.java b/src/test/java/com/google/devtools/build/lib/exec/local/LocalSpawnRunnerTest.java
index f1a608c..e91cc0a 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/local/LocalSpawnRunnerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/exec/local/LocalSpawnRunnerTest.java
@@ -49,6 +49,7 @@
import com.google.devtools.build.lib.exec.BinTools;
import com.google.devtools.build.lib.exec.RunfilesTreeUpdater;
import com.google.devtools.build.lib.exec.SpawnExecutingEvent;
+import com.google.devtools.build.lib.exec.SpawnInputExpander;
import com.google.devtools.build.lib.exec.SpawnRunner.ProgressStatus;
import com.google.devtools.build.lib.exec.SpawnRunner.SpawnExecutionContext;
import com.google.devtools.build.lib.exec.SpawnSchedulingEvent;
@@ -261,6 +262,11 @@
}
@Override
+ public SpawnInputExpander getSpawnInputExpander() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
public Duration getTimeout() {
return Duration.ofMillis(timeoutMillis);
}
diff --git a/src/test/java/com/google/devtools/build/lib/remote/RemoteExecutionServiceTest.java b/src/test/java/com/google/devtools/build/lib/remote/RemoteExecutionServiceTest.java
index 03d8fc7..30f13bd 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/RemoteExecutionServiceTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/RemoteExecutionServiceTest.java
@@ -1386,6 +1386,97 @@
}
}
+ @Test
+ public void buildMerkleTree_withMemoization_works() throws Exception {
+ // Test that Merkle tree building can be memoized.
+
+ // TODO: Would like to check that NestedSet.getNonLeaves() is only called once per node, but
+ // cannot Mockito.spy on NestedSet as it is final.
+
+ // arrange
+ /*
+ * First:
+ * /bar/file
+ * /foo1/file
+ * Second:
+ * /bar/file
+ * /foo2/file
+ */
+
+ // arrange
+ // Single node NestedSets are folded, so always add a dummy file everywhere.
+ ActionInput dummyFile = ActionInputHelper.fromPath("dummy");
+ fakeFileCache.createScratchInput(dummyFile, "dummy");
+
+ ActionInput barFile = ActionInputHelper.fromPath("bar/file");
+ NestedSet<ActionInput> nodeBar =
+ NestedSetBuilder.create(Order.STABLE_ORDER, dummyFile, barFile);
+ fakeFileCache.createScratchInput(barFile, "bar");
+
+ ActionInput foo1File = ActionInputHelper.fromPath("foo1/file");
+ NestedSet<ActionInput> nodeFoo1 =
+ NestedSetBuilder.create(Order.STABLE_ORDER, dummyFile, foo1File);
+ fakeFileCache.createScratchInput(foo1File, "foo1");
+
+ ActionInput foo2File = ActionInputHelper.fromPath("foo2/file");
+ NestedSet<ActionInput> nodeFoo2 =
+ NestedSetBuilder.create(Order.STABLE_ORDER, dummyFile, foo2File);
+ fakeFileCache.createScratchInput(foo2File, "foo2");
+
+ NestedSet<ActionInput> nodeRoot1 =
+ new NestedSetBuilder<ActionInput>(Order.STABLE_ORDER)
+ .add(dummyFile)
+ .addTransitive(nodeBar)
+ .addTransitive(nodeFoo1)
+ .build();
+ NestedSet<ActionInput> nodeRoot2 =
+ new NestedSetBuilder<ActionInput>(Order.STABLE_ORDER)
+ .add(dummyFile)
+ .addTransitive(nodeBar)
+ .addTransitive(nodeFoo2)
+ .build();
+
+ Spawn spawn1 =
+ new SimpleSpawn(
+ new FakeOwner("foo", "bar", "//dummy:label"),
+ /*arguments=*/ ImmutableList.of(),
+ /*environment=*/ ImmutableMap.of(),
+ /*executionInfo=*/ ImmutableMap.of(),
+ /*inputs=*/ nodeRoot1,
+ /*outputs=*/ ImmutableSet.of(),
+ ResourceSet.ZERO);
+ Spawn spawn2 =
+ new SimpleSpawn(
+ new FakeOwner("foo", "bar", "//dummy:label"),
+ /*arguments=*/ ImmutableList.of(),
+ /*environment=*/ ImmutableMap.of(),
+ /*executionInfo=*/ ImmutableMap.of(),
+ /*inputs=*/ nodeRoot2,
+ /*outputs=*/ ImmutableSet.of(),
+ ResourceSet.ZERO);
+
+ FakeSpawnExecutionContext context1 = newSpawnExecutionContext(spawn1);
+ FakeSpawnExecutionContext context2 = newSpawnExecutionContext(spawn2);
+ RemoteOptions remoteOptions = Options.getDefaults(RemoteOptions.class);
+ remoteOptions.remoteMerkleTreeCache = true;
+ remoteOptions.remoteMerkleTreeCacheSize = 0;
+ RemoteExecutionService service = spy(newRemoteExecutionService(remoteOptions));
+
+ // act first time
+ service.buildRemoteAction(spawn1, context1);
+
+ // assert first time
+ // Called for: manifests, runfiles, nodeRoot1, nodeFoo1 and nodeBar.
+ verify(service, times(5)).uncachedBuildMerkleTreeVisitor(any(), any());
+
+ // act second time
+ service.buildRemoteAction(spawn2, context2);
+
+ // assert second time
+ // Called again for: manifests, runfiles, nodeRoot2 and nodeFoo2 but not nodeBar (cached).
+ verify(service, times(5 + 4)).uncachedBuildMerkleTreeVisitor(any(), any());
+ }
+
private Spawn newSpawnFromResult(RemoteActionResult result) {
return newSpawnFromResult(ImmutableMap.of(), result);
}
diff --git a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
index 4747110..4171d01 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
@@ -147,6 +147,11 @@
}
@Override
+ public SpawnInputExpander getSpawnInputExpander() {
+ return new SpawnInputExpander(execRoot, /*strict*/ false);
+ }
+
+ @Override
public Duration getTimeout() {
return Duration.ZERO;
}
@@ -159,7 +164,7 @@
@Override
public SortedMap<PathFragment, ActionInput> getInputMapping(PathFragment baseDirectory)
throws IOException, ForbiddenActionInputException {
- return new SpawnInputExpander(execRoot, /*strict*/ false)
+ return getSpawnInputExpander()
.getInputMapping(simpleSpawn, SIMPLE_ARTIFACT_EXPANDER, baseDirectory, fakeFileCache);
}
diff --git a/src/test/java/com/google/devtools/build/lib/remote/merkletree/MerkleTreeTest.java b/src/test/java/com/google/devtools/build/lib/remote/merkletree/MerkleTreeTest.java
index 17d7148..221fdc1 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/merkletree/MerkleTreeTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/merkletree/MerkleTreeTest.java
@@ -37,6 +37,7 @@
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
import java.io.IOException;
+import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
@@ -138,6 +139,49 @@
assertThat(allDigests).asList().containsAtLeastElementsIn(inputDigests);
}
+ @Test
+ public void mergeMerkleTrees() throws IOException {
+ // arrange
+ SortedMap<PathFragment, ActionInput> sortedInputs1 = new TreeMap<>();
+ SortedMap<PathFragment, ActionInput> sortedInputs2 = new TreeMap<>();
+ SortedMap<PathFragment, ActionInput> sortedInputsAll = new TreeMap<>();
+ Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();
+
+ addFile("srcs/foo.cc", "foo", sortedInputs1, metadata);
+ addFile("srcs/bar.cc", "bar", sortedInputs2, metadata);
+ addFile("srcs/fizz/buzz.cc", "buzz", sortedInputs1, metadata);
+ addFile("srcs/fizz/fizzbuzz.cc", "fizzbuzz", sortedInputs2, metadata);
+ sortedInputsAll.putAll(sortedInputs1);
+ sortedInputsAll.putAll(sortedInputs2);
+
+ MerkleTree treeEmpty =
+ MerkleTree.build(
+ new TreeMap<>(), new StaticMetadataProvider(metadata), execRoot, digestUtil);
+ MerkleTree tree1 =
+ MerkleTree.build(sortedInputs1, new StaticMetadataProvider(metadata), execRoot, digestUtil);
+ MerkleTree tree2 =
+ MerkleTree.build(sortedInputs2, new StaticMetadataProvider(metadata), execRoot, digestUtil);
+ MerkleTree treeAll =
+ MerkleTree.build(
+ sortedInputsAll, new StaticMetadataProvider(metadata), execRoot, digestUtil);
+
+ // act
+ MerkleTree mergedTreeEmpty = MerkleTree.merge(Arrays.asList(), digestUtil);
+ MerkleTree mergedTree1 = MerkleTree.merge(Arrays.asList(tree1), digestUtil);
+ MerkleTree mergedTree11 = MerkleTree.merge(Arrays.asList(tree1, tree1), digestUtil);
+ MerkleTree mergedTree12 = MerkleTree.merge(Arrays.asList(tree1, tree2), digestUtil);
+
+ // assert
+ assertThat(mergedTreeEmpty.getRootDigest()).isEqualTo(treeEmpty.getRootDigest());
+ assertThat(mergedTree1.getRootDigest()).isEqualTo(tree1.getRootDigest());
+ assertThat(mergedTree11.getRootDigest()).isEqualTo(tree1.getRootDigest());
+ assertThat(mergedTree12.getRootDigest()).isEqualTo(treeAll.getRootDigest());
+
+ assertThat(mergedTree1).isSameInstanceAs(tree1);
+
+ assertThat(mergedTree12.getAllDigests()).containsExactlyElementsIn(treeAll.getAllDigests());
+ }
+
private Artifact addFile(
String path,
String content,
diff --git a/src/test/java/com/google/devtools/build/lib/remote/util/FakeSpawnExecutionContext.java b/src/test/java/com/google/devtools/build/lib/remote/util/FakeSpawnExecutionContext.java
index 6a6ba60..6c719bc 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/util/FakeSpawnExecutionContext.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/util/FakeSpawnExecutionContext.java
@@ -123,7 +123,12 @@
@Override
public ArtifactExpander getArtifactExpander() {
- throw new UnsupportedOperationException();
+ return this::artifactExpander;
+ }
+
+ @Override
+ public SpawnInputExpander getSpawnInputExpander() {
+ return new SpawnInputExpander(execRoot, /*strict*/ false);
}
@Override
@@ -139,7 +144,7 @@
@Override
public SortedMap<PathFragment, ActionInput> getInputMapping(PathFragment baseDirectory)
throws IOException, ForbiddenActionInputException {
- return new SpawnInputExpander(execRoot, /*strict*/ false)
+ return getSpawnInputExpander()
.getInputMapping(spawn, this::artifactExpander, baseDirectory, metadataProvider);
}
