Add FileDependencyDeserializer.getDirectoryListingDependencies.
The implementation is closely resembles that of getFileDependencies.
* Adds the DirectoryListingDependencies type to contain the result.
* Creates common base class FileSystemDependencies, for
DirectoryListingDependencies and FileDependencies. These classes will
be put into the same containers.
* Pulls FileDependencyDeserializer.FutureFileDependencies out into
SettableFutureWithOwnership and makes it generic for reuse.
PiperOrigin-RevId: 684818562
Change-Id: I963276a534b04e19b17f390c85d0d5a73cf0f481
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
index de25f48..dc5af33 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
@@ -81,11 +81,14 @@
java_library(
name = "file_dependency_deserializer",
srcs = [
+ "DirectoryListingDependencies.java",
"FileDependencies.java",
"FileDependencyDeserializer.java",
+ "FileSystemDependencies.java",
],
deps = [
":file_dependency_key_support",
+ ":settable_future_with_ownership",
"//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
"//src/main/java/com/google/devtools/build/lib/vfs:ospathpolicy",
"//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
@@ -99,6 +102,12 @@
)
java_library(
+ name = "settable_future_with_ownership",
+ srcs = ["SettableFutureWithOwnership.java"],
+ deps = ["//third_party:guava"],
+)
+
+java_library(
name = "file_dependency_key_support",
srcs = ["FileDependencyKeySupport.java"],
deps = [
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/DirectoryListingDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/DirectoryListingDependencies.java
new file mode 100644
index 0000000..a6df57f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/DirectoryListingDependencies.java
@@ -0,0 +1,26 @@
+// Copyright 2024 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.serialization.analysis;
+
+import com.google.common.collect.ImmutableSet;
+
+/** Type representing a directory listing operation. */
+record DirectoryListingDependencies(FileDependencies realDirectory)
+ implements FileDependencyDeserializer.GetDirectoryListingDependenciesResult,
+ FileSystemDependencies {
+ /** True if this entry matches any directory name in {@code directoryPaths}. */
+ boolean matchesAnyDirectory(ImmutableSet<String> directoryPaths) {
+ return directoryPaths.contains(realDirectory.resolvedPath());
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
index ccd9c3e..01ad942 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
@@ -28,7 +28,8 @@
* #getDependencyCount} and {@link #getDependency}. If any matches are encountered, the associated
* value is invalidated.
*/
-sealed interface FileDependencies extends FileDependencyDeserializer.GetDependenciesResult
+sealed interface FileDependencies
+ extends FileSystemDependencies, FileDependencyDeserializer.GetDependenciesResult
permits FileDependencies.SingleResolvedPath,
FileDependencies.SingleResolvedPathAndDependency,
FileDependencies.MultiplePaths {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
index d4c954a..da50172 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
@@ -17,6 +17,7 @@
import static com.google.common.util.concurrent.Futures.immediateFailedFuture;
import static com.google.common.util.concurrent.Futures.immediateFuture;
import static com.google.common.util.concurrent.MoreExecutors.directExecutor;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.FileDependencyKeySupport.DIRECTORY_KEY_DELIMITER;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.FileDependencyKeySupport.FILE_KEY_DELIMITER;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.FileDependencyKeySupport.MAX_KEY_LENGTH;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.FileDependencyKeySupport.MTSV_SENTINEL;
@@ -27,7 +28,7 @@
import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
-import com.google.common.util.concurrent.AbstractFuture;
+import com.google.common.base.Function;
import com.google.common.util.concurrent.AsyncFunction;
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
@@ -35,34 +36,47 @@
import com.google.devtools.build.lib.skyframe.serialization.KeyBytesProvider;
import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
import com.google.devtools.build.lib.skyframe.serialization.StringKey;
+import com.google.devtools.build.lib.skyframe.serialization.proto.DirectoryListingInvalidationData;
import com.google.devtools.build.lib.skyframe.serialization.proto.FileInvalidationData;
import com.google.devtools.build.lib.skyframe.serialization.proto.Symlink;
import com.google.devtools.build.lib.vfs.OsPathPolicy;
import com.google.protobuf.InvalidProtocolBufferException;
import java.io.IOException;
-import java.lang.invoke.MethodHandles;
-import java.lang.invoke.VarHandle;
import javax.annotation.Nullable;
/**
* Deserializes dependency information persisted by {@link FileDependencySerializer}.
*
- * <p>Fetching a dependency is a mostly linear asynchronous state machine that performs actions then
- * waits in an alternating manner.
+ * <p>Fetching a file dependency is a mostly linear asynchronous state machine that performs actions
+ * then waits in an alternating manner.
*
* <ol>
* <li>Request the data for a given key.
- * <li>{@link WaitForData}.
+ * <li>{@link WaitForFileInvalidationData}.
* <li>Request the data for the parent directory (a recursive call).
* <li>{@link WaitForParent}.
* <li>Process any symlinks, resolving symlink parents as needed.
* <li>{@link WaitForSymlinkParent}.
* <li>Processing symlinks repeats for all the symlinks associated with an entry.
* </ol>
+ *
+ * <p>A similar, but simpler state machine is used for directory listings.
+ *
+ * <ol>
+ * <li>Request the data for a given key.
+ * <li>{@link WaitForListingInvalidationData}.
+ * <li>Request the file data corresponding to the directory (delegating to {@link
+ * #getFileDependencies}).
+ * <li>{@link WaitForListingFileDependencies}.
+ * <li>Create and cache the {@link DirectoryListingDependencies} instance.
+ * </ol>
*/
final class FileDependencyDeserializer {
private static final OsPathPolicy OS = OsPathPolicy.getFilePathOs();
+ /** Singleton representing the root file. */
+ static final FileDependencies ROOT_FILE = FileDependencies.builder("").build();
+
private final FingerprintValueService fingerprintValueService;
/**
@@ -79,8 +93,16 @@
* retained by the {@code SkyValue}s that depend on them. When all such associated {@code
* SkyValue}s are invalidated, the dependency information becomes eligible for GC.
*/
- private final Cache<String, GetDependenciesResult> dependenciesCache =
- Caffeine.newBuilder().weakValues().<String, GetDependenciesResult>build();
+ private final Cache<String, GetDependenciesResult> fileCache =
+ Caffeine.newBuilder().weakValues().build();
+
+ /**
+ * A cache for {@link DirectoryListingDependencies}, primarily for deduplication.
+ *
+ * <p>This follows the design of {@link #fileCache} but is for directory listings.
+ */
+ private final Cache<String, GetDirectoryListingDependenciesResult> listingCache =
+ Caffeine.newBuilder().weakValues().build();
FileDependencyDeserializer(FingerprintValueService fingerprintValueService) {
this.fingerprintValueService = fingerprintValueService;
@@ -89,6 +111,15 @@
sealed interface GetDependenciesResult permits FileDependencies, FutureFileDependencies {}
/**
+ * The main purpose of this class is to act as a {@link ListenableFuture<FileDependencies>}.
+ *
+ * <p>Its specific type is explicitly visible to clients to allow them to cleanly distinguish it
+ * as a permitted subtype of {@link GetDependenciesResult}.
+ */
+ static final class FutureFileDependencies extends SettableFutureWithOwnership<FileDependencies>
+ implements GetDependenciesResult {}
+
+ /**
* Reconstitutes the set of file dependencies associated with {@code key}.
*
* <p>Performs lookups and parent resolution (recursively) and symlink resolution to obtain all
@@ -100,7 +131,7 @@
*/
GetDependenciesResult getFileDependencies(String key) {
FutureFileDependencies ownedFuture;
- switch (dependenciesCache.get(key, unused -> new FutureFileDependencies())) {
+ switch (fileCache.get(key, unused -> new FutureFileDependencies())) {
case FileDependencies dependencies:
return dependencies;
case FutureFileDependencies future:
@@ -111,79 +142,54 @@
break;
}
// `ownedFuture` is owned by this thread, which must complete its value.
- try {
- ListenableFuture<byte[]> futureBytes;
- try {
- futureBytes = fingerprintValueService.get(getKeyBytes(key));
- } catch (IOException e) {
- ownedFuture.setIoException(e);
- return ownedFuture;
- }
-
- ownedFuture.setFutureFiles(
- Futures.transformAsync(
- futureBytes, new WaitForData(key), fingerprintValueService.getExecutor()));
- return ownedFuture;
- } finally {
- ownedFuture.verifySet();
- }
+ fetchInvalidationData(key, WaitForFileInvalidationData::new, ownedFuture);
+ return ownedFuture;
}
+ sealed interface GetDirectoryListingDependenciesResult
+ permits DirectoryListingDependencies, FutureDirectoryListingDependencies {}
+
/**
- * The main purpose of this class is to act as a {@link ListenableFuture<FileDependencies>}.
+ * The main purpose of this class is to act as a {@link
+ * ListenableFuture<DirectoryListingDependencies>}.
*
* <p>Its specific type is explicitly visible to clients to allow them to cleanly distinguish it
- * as a permitted subtype of {@link GetDependenciesResult}.
+ * as a permitted subtype of {@link GetDirectoryListingDependenciesResult}.
*/
- static final class FutureFileDependencies extends AbstractFuture<FileDependencies>
- implements GetDependenciesResult {
- /** Used to establish exactly-once ownership of this future with {@link #tryTakeOwnership}. */
- @SuppressWarnings({"UnusedVariable", "FieldCanBeFinal"}) // set with OWNED_HANDLE
- private boolean owned = false;
+ static final class FutureDirectoryListingDependencies
+ extends SettableFutureWithOwnership<DirectoryListingDependencies>
+ implements GetDirectoryListingDependenciesResult {}
- private boolean isSet = false;
-
- private boolean tryTakeOwnership() {
- return OWNED_HANDLE.compareAndSet(this, false, true);
+ /**
+ * Deserializes the resolved directory listing information associated with {@code key}.
+ *
+ * @param key should be as described at {@link DirectoryListingInvalidationData}.
+ * @return either an immediate {@link DirectoryListingDependencies} instance or effectively a
+ * {@link ListenableFuture<DirectoryListingDependencies>} instance.
+ */
+ GetDirectoryListingDependenciesResult getDirectoryListingDependencies(String key) {
+ FutureDirectoryListingDependencies ownedFuture;
+ switch (listingCache.get(key, unused -> new FutureDirectoryListingDependencies())) {
+ case DirectoryListingDependencies dependencies:
+ return dependencies;
+ case FutureDirectoryListingDependencies future:
+ if (!future.tryTakeOwnership()) {
+ return future; // Owned by another thread.
+ }
+ ownedFuture = future;
+ break;
}
-
- private void setFutureFiles(ListenableFuture<FileDependencies> files) {
- checkState(setFuture(files), "already set %s", this);
- isSet = true;
- }
-
- private void setIoException(IOException e) {
- checkState(setException(e));
- isSet = true;
- }
-
- private void verifySet() {
- if (!isSet) {
- checkState(
- setException(
- new IllegalStateException(
- "future was unexpectedly unset, look for unchecked exceptions in"
- + " FileDependencyDeserializer")));
- }
- }
-
- private static final VarHandle OWNED_HANDLE;
-
- static {
- try {
- OWNED_HANDLE =
- MethodHandles.lookup()
- .findVarHandle(FutureFileDependencies.class, "owned", boolean.class);
- } catch (ReflectiveOperationException e) {
- throw new ExceptionInInitializerError(e);
- }
- }
+ // `ownedFuture` is owned by this thread, which must complete its value.
+ fetchInvalidationData(key, WaitForListingInvalidationData::new, ownedFuture);
+ return ownedFuture;
}
- private class WaitForData implements AsyncFunction<byte[], FileDependencies> {
+ // ---------- Begin FileDependencies deserialization implementation ----------
+
+ private class WaitForFileInvalidationData implements AsyncFunction<byte[], FileDependencies> {
private final String key;
- private WaitForData(String key) {
+ private WaitForFileInvalidationData(String key) {
this.key = key;
}
@@ -280,7 +286,7 @@
// Replaces the cache value with the completed value. The future is likely to become eligible
// for GC shortly after the return below. Clients are expected to retain the meaningful
// top-level values.
- dependenciesCache.put(key, dependencies);
+ fileCache.put(key, dependencies);
return immediateFuture(dependencies);
}
@@ -406,6 +412,91 @@
return !previousParent.startsWith(newParent);
}
+ // ---------- Begin DirectoryListingDependencies deserialization implementation ----------
+
+ private class WaitForListingInvalidationData
+ implements AsyncFunction<byte[], DirectoryListingDependencies> {
+ private final String key;
+
+ private WaitForListingInvalidationData(String key) {
+ this.key = key;
+ }
+
+ @Override
+ public ListenableFuture<DirectoryListingDependencies> apply(byte[] bytes)
+ throws InvalidProtocolBufferException {
+ var data = DirectoryListingInvalidationData.parseFrom(bytes, getEmptyRegistry());
+ if (data.hasOverflowKey() && !data.getOverflowKey().equals(key)) {
+ return immediateFailedFuture(
+ new SerializationException(
+ String.format(
+ "Non-matching overflow key. This is possible if there is a key fingerprint"
+ + " collision. Expected %s got %s",
+ key, data)));
+ }
+
+ int pathBegin = key.indexOf(DIRECTORY_KEY_DELIMITER) + 1;
+
+ String path = key.substring(pathBegin);
+ if (path.isEmpty()) {
+ return immediateFuture(createAndCacheListingDependencies(key, ROOT_FILE));
+ }
+
+ String fileKey =
+ computeCacheKey(
+ path, data.hasFileMtsv() ? data.getFileMtsv() : MTSV_SENTINEL, FILE_KEY_DELIMITER);
+ switch (getFileDependencies(fileKey)) {
+ case FileDependencies dependencies:
+ return immediateFuture(createAndCacheListingDependencies(key, dependencies));
+ case FutureFileDependencies future:
+ return Futures.transform(
+ future, new WaitForListingFileDependencies(key), directExecutor());
+ }
+ }
+ }
+
+ private class WaitForListingFileDependencies
+ implements Function<FileDependencies, DirectoryListingDependencies> {
+ private final String key;
+
+ private WaitForListingFileDependencies(String key) {
+ this.key = key;
+ }
+
+ @Override
+ public DirectoryListingDependencies apply(FileDependencies dependencies) {
+ return createAndCacheListingDependencies(key, dependencies);
+ }
+ }
+
+ private DirectoryListingDependencies createAndCacheListingDependencies(
+ String key, FileDependencies dependencies) {
+ var result = new DirectoryListingDependencies(dependencies);
+ listingCache.put(key, result);
+ return result;
+ }
+
+ // ---------- Begin shared helpers ----------
+
+ private <T, FutureT extends SettableFutureWithOwnership<T>> void fetchInvalidationData(
+ String key, Function<String, AsyncFunction<byte[], T>> waitFactory, FutureT ownedFuture) {
+ try {
+ ListenableFuture<byte[]> futureBytes;
+ try {
+ futureBytes = fingerprintValueService.get(getKeyBytes(key));
+ } catch (IOException e) {
+ ownedFuture.failWith(e);
+ return;
+ }
+
+ ownedFuture.completeWith(
+ Futures.transformAsync(
+ futureBytes, waitFactory.apply(key), fingerprintValueService.getExecutor()));
+ } finally {
+ ownedFuture.verifyComplete();
+ }
+ }
+
private KeyBytesProvider getKeyBytes(String cacheKey) {
if (cacheKey.length() > MAX_KEY_LENGTH) {
return fingerprintValueService.fingerprint(cacheKey.getBytes(UTF_8));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencySerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencySerializer.java
index ad0b618..cf99008 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencySerializer.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencySerializer.java
@@ -194,7 +194,7 @@
reference.populate(
computeCacheKey(rootedPath.getRootRelativePath(), mtsv, DIRECTORY_KEY_DELIMITER));
}
- // If this is reached, this thread owns `reference` and must complete it's future.
+ // If this is reached, this thread owns `reference` and must complete its future.
boolean writeStatusSet = false;
try {
DirectoryListingInvalidationData.Builder data = DirectoryListingInvalidationData.newBuilder();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java
new file mode 100644
index 0000000..072e135
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java
@@ -0,0 +1,25 @@
+// Copyright 2024 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.serialization.analysis;
+
+/**
+ * Union type for {@link FileDependencies} and {@link DirectoryListingDependencies}.
+ *
+ * <p>At a structural level these two classes are very similar and {@link
+ * DirectoryListingDependencies} could be modeled plainly as {@link FileDependencies}. The crucial
+ * difference is that {@link FileDependencies#containsMatch(ImmutableSet<String>)} takes a set of
+ * files and {@link DirectoryListingDependencies#matchesAnyDirectories(ImmutableSet<String>)} takes
+ * a set of directory names so the two types are deliberately separated.
+ */
+sealed interface FileSystemDependencies permits FileDependencies, DirectoryListingDependencies {}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/SettableFutureWithOwnership.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/SettableFutureWithOwnership.java
new file mode 100644
index 0000000..5d8efd3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/SettableFutureWithOwnership.java
@@ -0,0 +1,82 @@
+// Copyright 2024 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.serialization.analysis;
+
+import static com.google.common.base.Preconditions.checkState;
+
+import com.google.common.util.concurrent.AbstractFuture;
+import com.google.common.util.concurrent.ListenableFuture;
+import java.io.IOException;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+
+/** A tailored settable future with ownership tracking. */
+abstract class SettableFutureWithOwnership<T> extends AbstractFuture<T> {
+ /** Used to establish exactly-once ownership of this future with {@link #tryTakeOwnership}. */
+ @SuppressWarnings({"UnusedVariable", "FieldCanBeFinal"}) // set with OWNED_HANDLE
+ private boolean owned = false;
+
+ private boolean isSet = false;
+
+ /**
+ * Returns true once.
+ *
+ * <p>When using {@link com.github.benmanes.caffeine.cache.Cache#get} with future values and a
+ * mapping function, there's a need to determine which thread owns the future. This method
+ * provides such a mechanism.
+ *
+ * <p>When this returns true, the caller must call either {@link #completeWith} or {@link
+ * #failWith}.
+ */
+ boolean tryTakeOwnership() {
+ return OWNED_HANDLE.compareAndSet(this, false, true);
+ }
+
+ void completeWith(ListenableFuture<T> future) {
+ checkState(setFuture(future), "already set %s", this);
+ isSet = true;
+ }
+
+ void failWith(IOException e) {
+ checkState(setException(e));
+ isSet = true;
+ }
+
+ /**
+ * Verifies that the future was complete.
+ *
+ * <p>With settable futures, there's a risk of deadlock-like behavior if the future is not
+ * complete. The owning thread should call this in a finally clause to fail-fast instead.
+ */
+ void verifyComplete() {
+ if (!isSet) {
+ checkState(
+ setException(
+ new IllegalStateException(
+ "future was unexpectedly unset, look for unchecked exceptions")));
+ }
+ }
+
+ private static final VarHandle OWNED_HANDLE;
+
+ static {
+ try {
+ OWNED_HANDLE =
+ MethodHandles.lookup()
+ .findVarHandle(SettableFutureWithOwnership.class, "owned", boolean.class);
+ } catch (ReflectiveOperationException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ }
+}
