Parallelize fetches of symlink file values, subdirectory globs, and subdirectory package lookup values. This should improve change pruning speed when we have to check a glob. It also keeps GlobFunction closer to the contract of Skyframe, because in order to avoid quadratic restarts, it wasn't checking for missing deps between getValue calls.
--
MOS_MIGRATED_REVID=115882309
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
index e233cdf..2044a90 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
@@ -15,9 +15,12 @@
import com.google.common.cache.Cache;
import com.google.common.cache.CacheBuilder;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Maps;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.util.Preconditions;
import com.google.devtools.build.lib.vfs.Dirent;
import com.google.devtools.build.lib.vfs.Dirent.Type;
import com.google.devtools.build.lib.vfs.PathFragment;
@@ -29,6 +32,7 @@
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.SkyValue;
+import java.util.Map;
import java.util.regex.Pattern;
import javax.annotation.Nullable;
@@ -57,10 +61,13 @@
// exists which implies that the package's directory exists.
PathFragment globSubdir = glob.getSubdir();
if (!globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
- PackageLookupValue globSubdirPkgLookupValue = (PackageLookupValue) env.getValue(
- PackageLookupValue.key(PackageIdentifier.create(
- glob.getPackageId().getRepository(),
- glob.getPackageId().getPackageFragment().getRelative(globSubdir))));
+ PackageLookupValue globSubdirPkgLookupValue =
+ (PackageLookupValue)
+ env.getValue(
+ PackageLookupValue.key(
+ PackageIdentifier.create(
+ glob.getPackageId().getRepository(),
+ glob.getPackageId().getPackageFragment().getRelative(globSubdir))));
if (globSubdirPkgLookupValue == null) {
return null;
}
@@ -87,16 +94,23 @@
NestedSetBuilder<PathFragment> matches = NestedSetBuilder.stableOrder();
+ boolean globMatchesBareFile = patternTail == null;
+
// "**" also matches an empty segment, so try the case where it is not present.
if ("**".equals(patternHead)) {
- if (patternTail == null) {
+ if (globMatchesBareFile) {
// Recursive globs aren't supposed to match the package's directory.
if (!glob.excludeDirs() && !globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
matches.add(globSubdir);
}
} else {
- SkyKey globKey = GlobValue.internalKey(glob.getPackageId(), glob.getPackageRoot(),
- globSubdir, patternTail, glob.excludeDirs());
+ SkyKey globKey =
+ GlobValue.internalKey(
+ glob.getPackageId(),
+ glob.getPackageRoot(),
+ globSubdir,
+ patternTail,
+ glob.excludeDirs());
GlobValue globValue = (GlobValue) env.getValue(globKey);
if (globValue == null) {
return null;
@@ -108,6 +122,7 @@
PathFragment dirPathFragment = glob.getPackageId().getPackageFragment().getRelative(globSubdir);
RootedPath dirRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(), dirPathFragment);
if (alwaysUseDirListing || containsGlobs(patternHead)) {
+ String subdirPattern = "**".equals(patternHead) ? glob.getPattern() : patternTail;
// Pattern contains globs, so a directory listing is required.
//
// Note that we have good reason to believe the directory exists: if this is the
@@ -121,12 +136,20 @@
return null;
}
+ // In order to batch Skyframe requests, we do three passes over the directory:
+ // (1) Process every dirent, keeping track of values we need to request if the dirent cannot
+ // be processed with current information (symlink targets and subdirectory globs/package
+ // lookups for some subdirectories).
+ // (2) Get those values and process the symlinks, keeping track of subdirectory globs/package
+ // lookups we may need to request in case the symlink's target is a directory.
+ // (3) Process the necessary subdirectories.
+ int direntsSize = listingValue.getDirents().size();
+ Map<Dirent, SkyKey> symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize);
+ Map<Dirent, SkyKey> firstPassSubdirMap = Maps.newHashMapWithExpectedSize(direntsSize);
+ // First pass: do normal files and collect SkyKeys to request.
for (Dirent dirent : listingValue.getDirents()) {
Type direntType = dirent.getType();
String fileName = dirent.getName();
-
- boolean isDirectory = (direntType == Dirent.Type.DIRECTORY);
-
if (!UnixGlob.matches(patternHead, fileName, regexPatternCache)) {
continue;
}
@@ -135,46 +158,103 @@
// TODO(bazel-team): Consider extracting the symlink resolution logic.
// For symlinks, look up the corresponding FileValue. This ensures that if the symlink
// changes and "switches types" (say, from a file to a directory), this value will be
- // invalidated.
- RootedPath symlinkRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(),
- dirPathFragment.getRelative(fileName));
- FileValue symlinkFileValue = (FileValue) env.getValue(FileValue.key(symlinkRootedPath));
- if (symlinkFileValue == null) {
- continue;
- }
- if (!symlinkFileValue.isSymlink()) {
- throw new GlobFunctionException(new InconsistentFilesystemException(
- "readdir and stat disagree about whether " + symlinkRootedPath.asPath()
- + " is a symlink."), Transience.TRANSIENT);
- }
- if (!symlinkFileValue.exists()) {
- continue;
- }
- isDirectory = symlinkFileValue.isDirectory();
+ // invalidated. We also need the target's type to properly process the symlink.
+ symlinkFileMap.put(
+ dirent,
+ FileValue.key(
+ RootedPath.toRootedPath(
+ glob.getPackageRoot(), dirPathFragment.getRelative(fileName))));
+ continue;
}
- String subdirPattern = "**".equals(patternHead) ? glob.getPattern() : patternTail;
- addFile(fileName, glob, subdirPattern, patternTail == null, isDirectory,
- matches, env);
+ if (direntType == Dirent.Type.DIRECTORY) {
+ SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern);
+ if (keyToRequest != null) {
+ firstPassSubdirMap.put(dirent, keyToRequest);
+ }
+ } else if (globMatchesBareFile) {
+ matches.add(glob.getSubdir().getRelative(fileName));
+ }
+ }
+
+ Map<SkyKey, SkyValue> firstPassAndSymlinksResult =
+ env.getValues(Iterables.concat(firstPassSubdirMap.values(), symlinkFileMap.values()));
+ if (env.valuesMissing()) {
+ return null;
+ }
+ // Second pass: do symlinks, and maybe collect further SkyKeys if targets are directories.
+ Map<Dirent, SkyKey> symlinkSubdirMap = Maps.newHashMapWithExpectedSize(symlinkFileMap.size());
+ for (Map.Entry<Dirent, SkyKey> direntAndKey : symlinkFileMap.entrySet()) {
+ Dirent dirent = direntAndKey.getKey();
+ String fileName = dirent.getName();
+ Preconditions.checkState(dirent.getType() == Dirent.Type.SYMLINK, direntAndKey);
+ FileValue symlinkFileValue =
+ Preconditions.checkNotNull(
+ (FileValue) firstPassAndSymlinksResult.get(direntAndKey.getValue()), direntAndKey);
+ if (!symlinkFileValue.isSymlink()) {
+ throw new GlobFunctionException(
+ new InconsistentFilesystemException(
+ "readdir and stat disagree about whether "
+ + ((RootedPath) direntAndKey.getValue().argument()).asPath()
+ + " is a symlink."),
+ Transience.TRANSIENT);
+ }
+ if (!symlinkFileValue.exists()) {
+ continue;
+ }
+ if (symlinkFileValue.isDirectory()) {
+ SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern);
+ if (keyToRequest != null) {
+ symlinkSubdirMap.put(dirent, keyToRequest);
+ }
+ } else if (globMatchesBareFile) {
+ matches.add(glob.getSubdir().getRelative(fileName));
+ }
+ }
+
+ Map<SkyKey, SkyValue> secondResult = env.getValues(symlinkSubdirMap.values());
+ if (env.valuesMissing()) {
+ return null;
+ }
+ // Third pass: do needed subdirectories.
+ for (Map.Entry<Dirent, SkyKey> direntAndKey :
+ Iterables.concat(firstPassSubdirMap.entrySet(), symlinkSubdirMap.entrySet())) {
+ Dirent dirent = direntAndKey.getKey();
+ String fileName = dirent.getName();
+ SkyKey key = direntAndKey.getValue();
+ SkyValue valueRequested =
+ symlinkSubdirMap.containsKey(dirent)
+ ? secondResult.get(key)
+ : firstPassAndSymlinksResult.get(key);
+ Preconditions.checkNotNull(valueRequested, direntAndKey);
+ addSubdirMatchesFromSkyValue(fileName, glob, matches, valueRequested);
}
} else {
// Pattern does not contain globs, so a direct stat is enough.
String fileName = patternHead;
- RootedPath fileRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(),
- dirPathFragment.getRelative(fileName));
+ RootedPath fileRootedPath =
+ RootedPath.toRootedPath(glob.getPackageRoot(), dirPathFragment.getRelative(fileName));
FileValue fileValue = (FileValue) env.getValue(FileValue.key(fileRootedPath));
if (fileValue == null) {
return null;
}
if (fileValue.exists()) {
- addFile(fileName, glob, patternTail, patternTail == null,
- fileValue.isDirectory(), matches, env);
+ if (fileValue.isDirectory()) {
+ SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, patternTail);
+ if (keyToRequest != null) {
+ SkyValue valueRequested = env.getValue(keyToRequest);
+ if (env.valuesMissing()) {
+ return null;
+ }
+ addSubdirMatchesFromSkyValue(fileName, glob, matches, valueRequested);
+ }
+ } else if (globMatchesBareFile) {
+ matches.add(glob.getSubdir().getRelative(fileName));
+ }
}
}
- if (env.valuesMissing()) {
- return null;
- }
+ Preconditions.checkState(!env.valuesMissing(), skyKey);
NestedSet<PathFragment> matchesBuilt = matches.build();
// Use the same value to represent that we did not match anything.
@@ -184,10 +264,8 @@
return new GlobValue(matchesBuilt);
}
- /**
- * Returns true if the given pattern contains globs.
- */
- private boolean containsGlobs(String pattern) {
+ /** Returns true if the given pattern contains globs. */
+ private static boolean containsGlobs(String pattern) {
return pattern.contains("*") || pattern.contains("?");
}
@@ -198,41 +276,60 @@
*
* <p>{@code isDirectory} must be true iff the file is a directory.
*
- * <p>{@code directResult} must be set if the file should be included in the result set
- * directly rather than recursed into if it is a directory.
+ * <p>Returns a {@link SkyKey} for a value that is needed to compute the files that will be added
+ * to {@code matches}, or {@code null} if no additional value is needed. The returned value should
+ * be opaquely passed to {@link #addSubdirMatchesFromSkyValue}.
*/
- private void addFile(String fileName, GlobDescriptor glob, String subdirPattern,
- boolean directResult, boolean isDirectory, NestedSetBuilder<PathFragment> matches,
- Environment env) {
- if (isDirectory && subdirPattern != null) {
- // This is a directory, and the pattern covers files under that directory.
- SkyKey subdirGlobKey = GlobValue.internalKey(glob.getPackageId(), glob.getPackageRoot(),
- glob.getSubdir().getRelative(fileName), subdirPattern, glob.excludeDirs());
- GlobValue subdirGlob = (GlobValue) env.getValue(subdirGlobKey);
- if (subdirGlob == null) {
- return;
+ private static SkyKey getSkyKeyForSubdir(
+ String fileName, GlobDescriptor glob, String subdirPattern) {
+ if (subdirPattern == null) {
+ if (glob.excludeDirs()) {
+ return null;
+ } else {
+ return PackageLookupValue.key(
+ PackageIdentifier.create(
+ glob.getPackageId().getRepository(),
+ glob.getPackageId()
+ .getPackageFragment()
+ .getRelative(glob.getSubdir())
+ .getRelative(fileName)));
}
- matches.addTransitive(subdirGlob.getMatches());
+ } else {
+ // There is some more pattern to match. Get the glob for the subdirectory. Note that this
+ // directory may also match directly in the case of a pattern that starts with "**", but that
+ // match will be found in the subdirectory glob.
+ return GlobValue.internalKey(
+ glob.getPackageId(),
+ glob.getPackageRoot(),
+ glob.getSubdir().getRelative(fileName),
+ subdirPattern,
+ glob.excludeDirs());
}
+ }
- if (directResult && !(isDirectory && glob.excludeDirs())) {
- if (isDirectory) {
- // TODO(bazel-team): Refactor. This is basically inlined code from the next recursion level.
- // Ensure that subdirectories that contain other packages are not picked up.
- PathFragment directory = glob.getPackageId().getPackageFragment()
- .getRelative(glob.getSubdir()).getRelative(fileName);
- PackageLookupValue pkgLookupValue = (PackageLookupValue)
- env.getValue(PackageLookupValue.key(PackageIdentifier.create(
- glob.getPackageId().getRepository(), directory)));
- if (pkgLookupValue == null) {
- return;
- }
- if (pkgLookupValue.packageExists()) {
- // The file is a directory and contains another package.
- return;
- }
+ /**
+ * Add matches to {@code matches} coming from the directory {@code fileName} if appropriate.
+ *
+ * <p>{@code valueRequested} must be the SkyValue whose key was returned by
+ * {@link #getSkyKeyForSubdir} for these parameters.
+ */
+ private static void addSubdirMatchesFromSkyValue(
+ String fileName,
+ GlobDescriptor glob,
+ NestedSetBuilder<PathFragment> matches,
+ SkyValue valueRequested) {
+ if (valueRequested instanceof GlobValue) {
+ matches.addTransitive(((GlobValue) valueRequested).getMatches());
+ } else {
+ Preconditions.checkState(
+ valueRequested instanceof PackageLookupValue,
+ "%s is not a GlobValue or PackageLookupValue (%s %s)",
+ valueRequested,
+ fileName,
+ glob);
+ if (!((PackageLookupValue) valueRequested).packageExists()) {
+ matches.add(glob.getSubdir().getRelative(fileName));
}
- matches.add(glob.getSubdir().getRelative(fileName));
}
}
