Skip to content

Commit 3947c83

Browse files
coeuvremoroten
coeuvre
and
moroten
authored
Remote: Cache merkle trees (#14185)
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 Co-authored-by: Fredrik Medley <[email protected]>
1 parent 8d66a41 commit 3947c83

File tree

20 files changed

+664
-64
lines changed

20 files changed

+664
-64
lines changed

‎src/main/java/com/google/devtools/build/lib/actions/CompositeRunfilesSupplier.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,20 @@ public static RunfilesSupplier of(RunfilesSupplier supplier1, RunfilesSupplier s
6565
this.suppliers = suppliers;
6666
}
6767

68+
@Override
69+
public boolean equals(Object other) {
70+
if (!(other instanceof CompositeRunfilesSupplier)) {
71+
return false;
72+
}
73+
CompositeRunfilesSupplier that = (CompositeRunfilesSupplier) other;
74+
return suppliers.equals(that.suppliers);
75+
}
76+
77+
@Override
78+
public int hashCode() {
79+
return suppliers.hashCode();
80+
}
81+
6882
@Override
6983
public NestedSet<Artifact> getArtifacts() {
7084
NestedSetBuilder<Artifact> result = NestedSetBuilder.stableOrder();

‎src/main/java/com/google/devtools/build/lib/actions/EmptyRunfilesSupplier.java‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,12 +24,22 @@
2424
import java.util.Map;
2525

2626
/** Empty implementation of RunfilesSupplier */
27-
public class EmptyRunfilesSupplier implements RunfilesSupplier {
27+
public final class EmptyRunfilesSupplier implements RunfilesSupplier {
2828

2929
@AutoCodec public static final EmptyRunfilesSupplier INSTANCE = new EmptyRunfilesSupplier();
3030

3131
private EmptyRunfilesSupplier() {}
3232

33+
@Override
34+
public boolean equals(Object other) {
35+
return (other instanceof EmptyRunfilesSupplier);
36+
}
37+
38+
@Override
39+
public int hashCode() {
40+
return 0;
41+
}
42+
3343
@Override
3444
public NestedSet<Artifact> getArtifacts() {
3545
return NestedSetBuilder.<Artifact>stableOrder().build();

‎src/main/java/com/google/devtools/build/lib/analysis/SingleRunfilesSupplier.java‎

Lines changed: 42 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
import com.google.devtools.build.lib.vfs.PathFragment;
2828
import java.lang.ref.SoftReference;
2929
import java.util.Map;
30+
import java.util.Objects;
3031
import java.util.function.Supplier;
3132
import javax.annotation.Nullable;
3233

@@ -47,6 +48,7 @@ public static SingleRunfilesSupplier create(RunfilesSupport runfilesSupport) {
4748
return new SingleRunfilesSupplier(
4849
runfilesSupport.getRunfilesDirectoryExecPath(),
4950
runfilesSupport.getRunfiles(),
51+
/*runfilesCachingEnabled=*/ false,
5052
/*manifest=*/ null,
5153
runfilesSupport.isBuildRunfileLinks(),
5254
runfilesSupport.isRunfilesEnabled());
@@ -68,7 +70,7 @@ public static SingleRunfilesSupplier createCaching(
6870
return new SingleRunfilesSupplier(
6971
runfilesDir,
7072
runfiles,
71-
new RunfilesCacher(runfiles),
73+
/*runfilesCachingEnabled=*/ true,
7274
/*manifest=*/ null,
7375
buildRunfileLinks,
7476
runfileLinksEnabled);
@@ -95,7 +97,25 @@ public SingleRunfilesSupplier(
9597
this(
9698
runfilesDir,
9799
runfiles,
98-
() -> runfiles.getRunfilesInputs(/*eventHandler=*/ null, /*location=*/ null),
100+
/*runfilesCachingEnabled=*/ false,
101+
manifest,
102+
buildRunfileLinks,
103+
runfileLinksEnabled);
104+
}
105+
106+
private SingleRunfilesSupplier(
107+
PathFragment runfilesDir,
108+
Runfiles runfiles,
109+
boolean runfilesCachingEnabled,
110+
@Nullable Artifact manifest,
111+
boolean buildRunfileLinks,
112+
boolean runfileLinksEnabled) {
113+
this(
114+
runfilesDir,
115+
runfiles,
116+
runfilesCachingEnabled
117+
? new RunfilesCacher(runfiles)
118+
: () -> runfiles.getRunfilesInputs(/*eventHandler=*/ null, /*location=*/ null),
99119
manifest,
100120
buildRunfileLinks,
101121
runfileLinksEnabled);
@@ -117,6 +137,26 @@ private SingleRunfilesSupplier(
117137
this.runfileLinksEnabled = runfileLinksEnabled;
118138
}
119139

140+
@Override
141+
public boolean equals(Object other) {
142+
if (!(other instanceof SingleRunfilesSupplier)) {
143+
return false;
144+
}
145+
146+
SingleRunfilesSupplier that = (SingleRunfilesSupplier) other;
147+
// Not dependent on runfilesInputs which is only used for enabling caching.
148+
return (Objects.equals(runfilesDir, that.runfilesDir)
149+
&& Objects.equals(runfiles, that.runfiles)
150+
&& Objects.equals(manifest, that.manifest)
151+
&& (buildRunfileLinks == that.buildRunfileLinks)
152+
&& (runfileLinksEnabled == that.runfileLinksEnabled));
153+
}
154+
155+
@Override
156+
public int hashCode() {
157+
return Objects.hash(runfilesDir, runfiles, manifest, buildRunfileLinks, runfileLinksEnabled);
158+
}
159+
120160
@Override
121161
public NestedSet<Artifact> getArtifacts() {
122162
return runfiles.getAllArtifacts();

‎src/main/java/com/google/devtools/build/lib/exec/AbstractSpawnStrategy.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -269,6 +269,11 @@ public ArtifactPathResolver getPathResolver() {
269269
return actionExecutionContext.getPathResolver();
270270
}
271271

272+
@Override
273+
public SpawnInputExpander getSpawnInputExpander() {
274+
return spawnInputExpander;
275+
}
276+
272277
@Override
273278
public void lockOutputFiles() throws InterruptedException {
274279
if (stopConcurrentSpawns != null) {

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -275,6 +275,7 @@ java_library(
275275
"SpawnSchedulingEvent.java",
276276
],
277277
deps = [
278+
":spawn_input_expander",
278279
":tree_deleter",
279280
"//src/main/java/com/google/devtools/build/lib/actions",
280281
"//src/main/java/com/google/devtools/build/lib/actions:artifacts",

‎src/main/java/com/google/devtools/build/lib/exec/SpawnInputExpander.java‎

Lines changed: 127 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -33,11 +33,13 @@
3333
import com.google.devtools.build.lib.actions.RunfilesSupplier;
3434
import com.google.devtools.build.lib.actions.Spawn;
3535
import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
36+
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
3637
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
3738
import com.google.devtools.build.lib.collect.nestedset.Order;
3839
import com.google.devtools.build.lib.vfs.Path;
3940
import com.google.devtools.build.lib.vfs.PathFragment;
4041
import java.io.IOException;
42+
import java.util.Arrays;
4143
import java.util.HashMap;
4244
import java.util.List;
4345
import java.util.Map;
@@ -95,7 +97,7 @@ public SpawnInputExpander(
9597
this.relSymlinkBehavior = relSymlinkBehavior;
9698
}
9799

98-
private void addMapping(
100+
private static void addMapping(
99101
Map<PathFragment, ActionInput> inputMappings,
100102
PathFragment targetLocation,
101103
ActionInput input,
@@ -215,13 +217,12 @@ void addFilesetManifest(
215217
}
216218
}
217219

218-
private void addInputs(
220+
private static void addInputs(
219221
Map<PathFragment, ActionInput> inputMap,
220-
Spawn spawn,
222+
NestedSet<? extends ActionInput> inputFiles,
221223
ArtifactExpander artifactExpander,
222224
PathFragment baseDirectory) {
223-
List<ActionInput> inputs =
224-
ActionInputHelper.expandArtifacts(spawn.getInputFiles(), artifactExpander);
225+
List<ActionInput> inputs = ActionInputHelper.expandArtifacts(inputFiles, artifactExpander);
225226
for (ActionInput input : inputs) {
226227
addMapping(inputMap, input.getExecPath(), input, baseDirectory);
227228
}
@@ -243,7 +244,7 @@ public SortedMap<PathFragment, ActionInput> getInputMapping(
243244
MetadataProvider actionInputFileCache)
244245
throws IOException, ForbiddenActionInputException {
245246
TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
246-
addInputs(inputMap, spawn, artifactExpander, baseDirectory);
247+
addInputs(inputMap, spawn.getInputFiles(), artifactExpander, baseDirectory);
247248
addRunfilesToInputs(
248249
inputMap,
249250
spawn.getRunfilesSupplier(),
@@ -254,6 +255,126 @@ public SortedMap<PathFragment, ActionInput> getInputMapping(
254255
return inputMap;
255256
}
256257

258+
/** The interface for accessing part of the input hierarchy. */
259+
public interface InputWalker {
260+
SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
261+
throws IOException, ForbiddenActionInputException;
262+
263+
void visitNonLeaves(InputVisitor visitor) throws IOException, ForbiddenActionInputException;
264+
}
265+
266+
/** The interface for visiting part of the input hierarchy. */
267+
public interface InputVisitor {
268+
/**
269+
* Visits a part of the input hierarchy.
270+
*
271+
* <p>{@code nodeKey} can be used as key when memoizing visited parts of the hierarchy.
272+
*/
273+
void visit(Object nodeKey, InputWalker walker)
274+
throws IOException, ForbiddenActionInputException;
275+
}
276+
277+
/**
278+
* Visits the input files hierarchy in a depth first manner.
279+
*
280+
* <p>Similar to {@link #getInputMapping} but allows for early exit, by not visiting children,
281+
* when walking through the input hierarchy. By applying memoization, the retrieval process of the
282+
* inputs can be speeded up.
283+
*
284+
* <p>{@code baseDirectory} is prepended to every path in the input key. This is useful if the
285+
* mapping is used in a context where the directory relative to which the keys are interpreted is
286+
* not the same as the execroot.
287+
*/
288+
public void walkInputs(
289+
Spawn spawn,
290+
ArtifactExpander artifactExpander,
291+
PathFragment baseDirectory,
292+
MetadataProvider actionInputFileCache,
293+
InputVisitor visitor)
294+
throws IOException, ForbiddenActionInputException {
295+
walkNestedSetInputs(baseDirectory, spawn.getInputFiles(), artifactExpander, visitor);
296+
297+
RunfilesSupplier runfilesSupplier = spawn.getRunfilesSupplier();
298+
visitor.visit(
299+
// The list of variables affecting the functional expressions below.
300+
Arrays.asList(
301+
// Assuming that artifactExpander and actionInputFileCache, different for each spawn,
302+
// always expand the same way.
303+
this, // For accessing addRunfilesToInputs.
304+
runfilesSupplier,
305+
baseDirectory),
306+
new InputWalker() {
307+
@Override
308+
public SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
309+
throws IOException, ForbiddenActionInputException {
310+
TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
311+
addRunfilesToInputs(
312+
inputMap, runfilesSupplier, actionInputFileCache, artifactExpander, baseDirectory);
313+
return inputMap;
314+
}
315+
316+
@Override
317+
public void visitNonLeaves(InputVisitor childVisitor) {}
318+
});
319+
320+
Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMappings = spawn.getFilesetMappings();
321+
// filesetMappings is assumed to be very small, so no need to implement visitNonLeaves() for
322+
// improved runtime.
323+
visitor.visit(
324+
// The list of variables affecting the functional expressions below.
325+
Arrays.asList(
326+
this, // For accessing addFilesetManifests.
327+
filesetMappings,
328+
baseDirectory),
329+
new InputWalker() {
330+
@Override
331+
public SortedMap<PathFragment, ActionInput> getLeavesInputMapping()
332+
throws ForbiddenRelativeSymlinkException {
333+
TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
334+
addFilesetManifests(filesetMappings, inputMap, baseDirectory);
335+
return inputMap;
336+
}
337+
338+
@Override
339+
public void visitNonLeaves(InputVisitor childVisitor) {}
340+
});
341+
}
342+
343+
/** Walks through one level of a {@link NestedSet} of {@link ActionInput}s. */
344+
private void walkNestedSetInputs(
345+
PathFragment baseDirectory,
346+
NestedSet<? extends ActionInput> someInputFiles,
347+
ArtifactExpander artifactExpander,
348+
InputVisitor visitor)
349+
throws IOException, ForbiddenActionInputException {
350+
visitor.visit(
351+
// addInputs is static so no need to add 'this' as dependent key.
352+
Arrays.asList(
353+
// Assuming that artifactExpander, different for each spawn, always expands the same
354+
// way.
355+
someInputFiles.toNode(), baseDirectory),
356+
new InputWalker() {
357+
@Override
358+
public SortedMap<PathFragment, ActionInput> getLeavesInputMapping() {
359+
TreeMap<PathFragment, ActionInput> inputMap = new TreeMap<>();
360+
addInputs(
361+
inputMap,
362+
NestedSetBuilder.wrap(someInputFiles.getOrder(), someInputFiles.getLeaves()),
363+
artifactExpander,
364+
baseDirectory);
365+
return inputMap;
366+
}
367+
368+
@Override
369+
public void visitNonLeaves(InputVisitor childVisitor)
370+
throws IOException, ForbiddenActionInputException {
371+
for (NestedSet<? extends ActionInput> subInputs : someInputFiles.getNonLeaves()) {
372+
walkNestedSetInputs(baseDirectory, subInputs, artifactExpander, childVisitor);
373+
}
374+
}
375+
});
376+
}
377+
257378
/**
258379
* Exception signaling that an input was not a regular file: most likely a directory. This
259380
* exception is currently never thrown in practice since we do not enforce "strict" mode.

‎src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -161,6 +161,12 @@ interface SpawnExecutionContext {
161161
// directories? Or maybe we need a separate method to return the set of directories?
162162
ArtifactExpander getArtifactExpander();
163163

164+
/** A spawn input expander. */
165+
// TODO(moroten): This is only used for the remote cache and remote execution to optimize
166+
// Merkle tree generation. Having both this and the getInputMapping method seems a bit
167+
// duplicated.
168+
SpawnInputExpander getSpawnInputExpander();
169+
164170
/** The {@link ArtifactPathResolver} to use when directly writing output files. */
165171
default ArtifactPathResolver getPathResolver() {
166172
return ArtifactPathResolver.IDENTITY;

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,7 @@ java_library(
6666
"//src/main/java/com/google/devtools/build/lib/exec:module_action_context_registry",
6767
"//src/main/java/com/google/devtools/build/lib/exec:remote_local_fallback_registry",
6868
"//src/main/java/com/google/devtools/build/lib/exec:spawn_cache",
69+
"//src/main/java/com/google/devtools/build/lib/exec:spawn_input_expander",
6970
"//src/main/java/com/google/devtools/build/lib/exec:spawn_runner",
7071
"//src/main/java/com/google/devtools/build/lib/exec:spawn_strategy_registry",
7172
"//src/main/java/com/google/devtools/build/lib/packages",
@@ -94,6 +95,7 @@ java_library(
9495
"//src/main/java/com/google/devtools/common/options",
9596
"//src/main/protobuf:failure_details_java_proto",
9697
"//third_party:auth",
98+
"//third_party:caffeine",
9799
"//third_party:flogger",
98100
"//third_party:guava",
99101
"//third_party:jsr305",

0 commit comments

Comments
 (0)