Skip to content

Commit df07d27

Browse files
tjgqcopybara-github
tjgq
authored and
copybara-github
committed
Parallelize TreeArtifactValue.visitTree across files instead of subdirectories.
This performs better when the subdirectories are unbalanced (and doesn't degrade catastrophically for a flat hierarchy). Most tree artifacts are too small for this to matter, but some users have very large ones (with hundreds of thousands of files) for which this can reduce the overall traversal time by 30% or more (after other, more important optimizations such as f2512a0 have been made). Also remove the edge case for the root directory; the code is cleaner that way. Related to #17009. PiperOrigin-RevId: 606897861 Change-Id: I143d55a844ac191543a856f73849a95560199468
1 parent bb80319 commit df07d27

File tree

3 files changed

+40
-39
lines changed

3 files changed

+40
-39
lines changed

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

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -283,10 +283,6 @@ private TreeArtifactValue constructTreeArtifactValueFromFilesystem(SpecialArtifa
283283
return TreeArtifactValue.MISSING_TREE_ARTIFACT;
284284
}
285285

286-
if (chmod) {
287-
setPathPermissions(treeDir);
288-
}
289-
290286
AtomicBoolean anyRemote = new AtomicBoolean(false);
291287

292288
TreeArtifactValue.Builder tree = TreeArtifactValue.newBuilder(parent);

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

Lines changed: 17 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -518,38 +518,33 @@ static class Visitor extends AbstractQueueVisitor {
518518
}
519519

520520
void run() throws IOException, InterruptedException {
521-
execute(() -> visitTree(PathFragment.EMPTY_FRAGMENT));
521+
execute(() -> visit(PathFragment.EMPTY_FRAGMENT, Dirent.Type.DIRECTORY));
522522
try {
523523
awaitQuiescence(true);
524524
} catch (IORuntimeException e) {
525525
throw e.getCauseIOException();
526526
}
527527
}
528528

529-
// IOExceptions are wrapped in IORuntimeException so that it can be propagated to the main
530-
// thread
531-
private void visitTree(PathFragment subdir) {
529+
private void visit(PathFragment parentRelativePath, Dirent.Type type) {
532530
try {
533-
for (Dirent dirent : parentDir.getRelative(subdir).readdir(Symlinks.NOFOLLOW)) {
534-
PathFragment parentRelativePath = subdir.getChild(dirent.getName());
535-
Dirent.Type type = dirent.getType();
536-
537-
if (type == Dirent.Type.UNKNOWN) {
538-
throw new IOException(
539-
"Could not determine type of file for "
540-
+ parentRelativePath
541-
+ " under "
542-
+ parentDir);
543-
}
531+
Path path = parentDir.getRelative(parentRelativePath);
544532

545-
if (type == Dirent.Type.SYMLINK) {
546-
checkSymlink(subdir, parentDir.getRelative(parentRelativePath));
547-
}
533+
if (type == Dirent.Type.UNKNOWN) {
534+
throw new IOException("Could not determine type of file for " + path.getPathString());
535+
}
536+
537+
if (type == Dirent.Type.SYMLINK) {
538+
checkSymlink(parentRelativePath.getParentDirectory(), path);
539+
}
548540

549-
visitor.visit(parentRelativePath, type);
541+
visitor.visit(parentRelativePath, type);
550542

551-
if (type == Dirent.Type.DIRECTORY) {
552-
execute(() -> visitTree(parentRelativePath));
543+
if (type == Dirent.Type.DIRECTORY) {
544+
for (Dirent dirent : path.readdir(Symlinks.NOFOLLOW)) {
545+
PathFragment childPath = parentRelativePath.getChild(dirent.getName());
546+
Dirent.Type childType = dirent.getType();
547+
execute(() -> visit(childPath, childType));
553548
}
554549
}
555550
} catch (IOException e) {
@@ -563,7 +558,7 @@ private void visitTree(PathFragment subdir) {
563558
* Recursively visits all descendants under a directory.
564559
*
565560
* <p>{@link TreeArtifactVisitor#visit} is invoked on {@code visitor} for each directory, file,
566-
* and symlink under the given {@code parentDir}.
561+
* and symlink under the given {@code parentDir}, including {@code parentDir} itself.
567562
*
568563
* <p>This method is intended to provide uniform semantics for constructing a tree artifact,
569564
* including special logic that validates directory entries. Invalid directory entries include a

‎src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactValueTest.java‎

Lines changed: 23 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,6 @@
1515

1616
import static com.google.common.truth.Truth.assertThat;
1717
import static org.junit.Assert.assertThrows;
18-
import static org.junit.Assert.fail;
1918
import static org.mockito.Mockito.doReturn;
2019
import static org.mockito.Mockito.spy;
2120

@@ -382,6 +381,7 @@ public void visitTree_visitsEachChild() throws Exception {
382381

383382
assertThat(children)
384383
.containsExactly(
384+
Pair.of(PathFragment.create(""), Dirent.Type.DIRECTORY),
385385
Pair.of(PathFragment.create("a"), Dirent.Type.DIRECTORY),
386386
Pair.of(PathFragment.create("a/b"), Dirent.Type.DIRECTORY),
387387
Pair.of(PathFragment.create("file1"), Dirent.Type.FILE),
@@ -405,17 +405,13 @@ public ImmutableList<Dirent> readdir(PathFragment path, boolean followSymlinks)
405405

406406
Exception e =
407407
assertThrows(
408-
IOException.class,
409-
() ->
410-
TreeArtifactValue.visitTree(
411-
treeDir, (child, type) -> fail("Should not be called")));
412-
assertThat(e).hasMessageThat().contains("Could not determine type of file for ? under /tree");
408+
IOException.class, () -> TreeArtifactValue.visitTree(treeDir, (child, type) -> {}));
409+
assertThat(e).hasMessageThat().contains("Could not determine type of file for /tree/?");
413410
}
414411

415412
@Test
416413
public void visitTree_propagatesIoExceptionFromVisitor() throws Exception {
417414
Path treeDir = scratch.dir("tree");
418-
scratch.file("tree/file");
419415
IOException e = new IOException("From visitor");
420416

421417
IOException thrown =
@@ -425,8 +421,6 @@ public void visitTree_propagatesIoExceptionFromVisitor() throws Exception {
425421
TreeArtifactValue.visitTree(
426422
treeDir,
427423
(child, type) -> {
428-
assertThat(child).isEqualTo(PathFragment.create("file"));
429-
assertThat(type).isEqualTo(Dirent.Type.FILE);
430424
throw e;
431425
}));
432426
assertThat(thrown).isSameInstanceAs(e);
@@ -450,6 +444,7 @@ public void visitTree_pemitsUpLevelSymlinkInsideTree() throws Exception {
450444

451445
assertThat(children)
452446
.containsExactly(
447+
Pair.of(PathFragment.create(""), Dirent.Type.DIRECTORY),
453448
Pair.of(PathFragment.create("file"), Dirent.Type.FILE),
454449
Pair.of(PathFragment.create("a"), Dirent.Type.DIRECTORY),
455450
Pair.of(PathFragment.create("a/up_link"), Dirent.Type.SYMLINK));
@@ -470,21 +465,30 @@ public void visitTree_permitsAbsoluteSymlink() throws Exception {
470465
});
471466

472467
assertThat(children)
473-
.containsExactly(Pair.of(PathFragment.create("absolute_link"), Dirent.Type.SYMLINK));
468+
.containsExactly(
469+
Pair.of(PathFragment.create(""), Dirent.Type.DIRECTORY),
470+
Pair.of(PathFragment.create("absolute_link"), Dirent.Type.SYMLINK));
474471
}
475472

476473
@Test
477474
public void visitTree_throwsOnSymlinkPointingOutsideTree() throws Exception {
478475
Path treeDir = scratch.dir("tree");
479476
scratch.file("outside");
480477
scratch.resolve("tree/link").createSymbolicLink(PathFragment.create("../outside"));
478+
List<Pair<PathFragment, Dirent.Type>> children = new ArrayList<>();
481479

482480
Exception e =
483481
assertThrows(
484482
IOException.class,
485483
() ->
486484
TreeArtifactValue.visitTree(
487-
treeDir, (child, type) -> fail("Should not be called")));
485+
treeDir,
486+
(child, type) -> {
487+
synchronized (children) {
488+
children.add(Pair.of(child, type));
489+
}
490+
}));
491+
assertThat(children).containsExactly(Pair.of(PathFragment.create(""), Dirent.Type.DIRECTORY));
488492
assertThat(e).hasMessageThat().contains("/tree/link pointing to ../outside");
489493
}
490494

@@ -493,6 +497,7 @@ public void visitTree_throwsOnSymlinkTraversingOutsideThenBackInsideTree() throw
493497
Path treeDir = scratch.dir("tree");
494498
scratch.file("tree/file");
495499
scratch.resolve("tree/link").createSymbolicLink(PathFragment.create("../tree/file"));
500+
List<Pair<PathFragment, Dirent.Type>> children = new ArrayList<>();
496501

497502
Exception e =
498503
assertThrows(
@@ -501,9 +506,14 @@ public void visitTree_throwsOnSymlinkTraversingOutsideThenBackInsideTree() throw
501506
TreeArtifactValue.visitTree(
502507
treeDir,
503508
(child, type) -> {
504-
assertThat(child).isEqualTo(PathFragment.create("file"));
505-
assertThat(type).isEqualTo(Dirent.Type.FILE);
509+
synchronized (children) {
510+
children.add(Pair.of(child, type));
511+
}
506512
}));
513+
assertThat(children)
514+
.containsExactly(
515+
Pair.of(PathFragment.create(""), Dirent.Type.DIRECTORY),
516+
Pair.of(PathFragment.create("file"), Dirent.Type.FILE));
507517
assertThat(e).hasMessageThat().contains("/tree/link pointing to ../tree/file");
508518
}
509519

0 commit comments

Comments
 (0)