Add NestedFileSystemOperationNodes, canonical wire format and round-tripping.
Since NestedFileSystemOperationNodes are identified by a fingerprint of
their serialized representation uses a custom, canonical wire format. As
per https://protobuf.dev/programming-guides/serialization-not-canonical/,
protos are not canonical.
Performs some renamings for consistency.
* In some places renames Directory to Listing. This emphasizes that it's
the listing that matters for invalidation.
* For consistency, some places that were DirectoryListing are also
renamed as Listing.
* GetDependenciesResult is renamed to GetFileDependenciesResult for
consistency.
PiperOrigin-RevId: 688712493
Change-Id: I0456a3d7ab0a8f4077d057d9ded3f1061fd85d11
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
index 58dfc5d..a23f807 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -1506,6 +1506,7 @@
"DirectoryListingKey.java",
"FileKey.java",
"FileSystemOperationNode.java",
+ "NestedFileSystemOperationNodes.java",
],
deps = [
":sky_functions",
@@ -1513,6 +1514,8 @@
"//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
"//src/main/java/com/google/devtools/build/lib/vfs",
"//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
+ "//third_party:error_prone_annotations",
+ "//third_party:jsr305",
],
)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemOperationNode.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemOperationNode.java
index 30c03ee..caed576 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemOperationNode.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemOperationNode.java
@@ -13,5 +13,10 @@
// limitations under the License.
package com.google.devtools.build.lib.skyframe;
-/** A {@link FileKey} or {@link DirectoryListingKey}. */
-public sealed interface FileSystemOperationNode permits FileKey, DirectoryListingKey {}
+/**
+ * Represents either a single file system operation or a nested set thereof.
+ *
+ * <p>If the set is unary, it is represented without a wrapper.
+ */
+public sealed interface FileSystemOperationNode
+ permits FileKey, DirectoryListingKey, NestedFileSystemOperationNodes {}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/NestedFileSystemOperationNodes.java b/src/main/java/com/google/devtools/build/lib/skyframe/NestedFileSystemOperationNodes.java
new file mode 100644
index 0000000..1c4de62
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/NestedFileSystemOperationNodes.java
@@ -0,0 +1,88 @@
+// 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;
+
+import com.google.errorprone.annotations.CanIgnoreReturnValue;
+import java.util.ArrayList;
+import javax.annotation.Nullable;
+
+/** Represents multiple {@link FileSystemOperationNode}s with nestable composition. */
+public final class NestedFileSystemOperationNodes implements FileSystemOperationNode {
+ private final FileSystemOperationNode[] nodes;
+
+ /**
+ * Opaque storage for use by serialization.
+ *
+ * <p>{@link FileSystemOperationNode}, {@link FileKey} and {@link DirectoryListingKey} are
+ * mutually dependent via {@link FileSystemOperationNode}. This type is opaque to avoid forcing
+ * {@link FileKey} and {@link DirectoryListingKey} to depend on serialization implementation code.
+ *
+ * <p>The serialization implementation initializes this field with double-checked locking so it is
+ * marked volatile.
+ */
+ private volatile Object serializationScratch;
+
+ public static FileSystemOperationNodeBuilder builder(FileSystemOperationNode node) {
+ return new FileSystemOperationNodeBuilder(node);
+ }
+
+ private NestedFileSystemOperationNodes(FileSystemOperationNode[] nodes) {
+ this.nodes = nodes;
+ }
+
+ public int count() {
+ return nodes.length;
+ }
+
+ public FileSystemOperationNode get(int index) {
+ return nodes[index];
+ }
+
+ @Nullable
+ public Object getSerializationScratch() {
+ return serializationScratch;
+ }
+
+ public void setSerializationScratch(Object value) {
+ this.serializationScratch = value;
+ }
+
+ /**
+ * Effectively, a builder for {@link NestedFileSystemOperationNodes}, but formally a builder for
+ * {@link FileSystemOperationNode}.
+ *
+ * <p>When there is only one node, this builder returns the node directly instead of creating a
+ * useless wrapper.
+ */
+ public static class FileSystemOperationNodeBuilder {
+ private final ArrayList<FileSystemOperationNode> nodes = new ArrayList<>();
+
+ private FileSystemOperationNodeBuilder(FileSystemOperationNode node) {
+ nodes.add(node);
+ }
+
+ @CanIgnoreReturnValue
+ public FileSystemOperationNodeBuilder add(FileSystemOperationNode node) {
+ nodes.add(node);
+ return this;
+ }
+
+ public FileSystemOperationNode build() {
+ if (nodes.size() > 1) {
+ return new NestedFileSystemOperationNodes(nodes.toArray(FileSystemOperationNode[]::new));
+ }
+ return nodes.get(0);
+ }
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackedFingerprint.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackedFingerprint.java
index 35023c7..3a1f981 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackedFingerprint.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackedFingerprint.java
@@ -36,7 +36,8 @@
* @param lo the lower 64-bits of the fingerprint
* @param hi the upper 64-bits of the fingerprint
*/
-public record PackedFingerprint(long lo, long hi) implements KeyBytesProvider {
+public record PackedFingerprint(long lo, long hi)
+ implements KeyBytesProvider, Comparable<PackedFingerprint> {
@VisibleForTesting static final int BYTES = 16;
/**
@@ -108,6 +109,15 @@
return (int) lo;
}
+ @Override
+ public int compareTo(PackedFingerprint o) {
+ int result = Long.compare(hi, o.hi);
+ if (result == 0) {
+ return Long.compare(lo, o.lo);
+ }
+ return result;
+ }
+
/** Changes all 0 bytes of {@code input} into 1. */
@VisibleForTesting
static long offsetZeros(long input) {
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 5d2ff7a..823c607 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
@@ -75,20 +75,23 @@
"//src/main/protobuf:file_invalidation_data_java_proto",
"//third_party:guava",
"//third_party:jsr305",
+ "@protobuf//:protobuf_java",
],
)
java_library(
name = "file_dependency_deserializer",
srcs = [
- "DirectoryListingDependencies.java",
"FileDependencies.java",
"FileDependencyDeserializer.java",
"FileSystemDependencies.java",
+ "ListingDependencies.java",
+ "NestedDependencies.java",
],
deps = [
":file_dependency_key_support",
":settable_future_with_ownership",
+ "//src/main/java/com/google/devtools/build/lib/concurrent",
"//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",
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 fa2cc52..cb86ff7 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
@@ -32,7 +32,7 @@
* value is invalidated.
*/
abstract sealed class FileDependencies
- implements FileSystemDependencies, FileDependencyDeserializer.GetDependenciesResult
+ implements FileSystemDependencies, FileDependencyDeserializer.GetFileDependenciesResult
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 da50172..afc3571 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
@@ -29,17 +29,22 @@
import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.google.common.base.Function;
+import com.google.common.base.Functions;
import com.google.common.util.concurrent.AsyncFunction;
+import com.google.common.util.concurrent.FutureCallback;
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
+import com.google.devtools.build.lib.concurrent.QuiescingFuture;
import com.google.devtools.build.lib.skyframe.serialization.FingerprintValueService;
import com.google.devtools.build.lib.skyframe.serialization.KeyBytesProvider;
+import com.google.devtools.build.lib.skyframe.serialization.PackedFingerprint;
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.CodedInputStream;
import com.google.protobuf.InvalidProtocolBufferException;
import java.io.IOException;
import javax.annotation.Nullable;
@@ -68,7 +73,7 @@
* <li>Request the file data corresponding to the directory (delegating to {@link
* #getFileDependencies}).
* <li>{@link WaitForListingFileDependencies}.
- * <li>Create and cache the {@link DirectoryListingDependencies} instance.
+ * <li>Create and cache the {@link ListingDependencies} instance.
* </ol>
*/
final class FileDependencyDeserializer {
@@ -93,31 +98,34 @@
* 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> fileCache =
+ private final Cache<String, GetFileDependenciesResult> fileCache =
Caffeine.newBuilder().weakValues().build();
/**
- * A cache for {@link DirectoryListingDependencies}, primarily for deduplication.
+ * A cache for {@link ListingDependencies}, primarily for deduplication.
*
* <p>This follows the design of {@link #fileCache} but is for directory listings.
*/
- private final Cache<String, GetDirectoryListingDependenciesResult> listingCache =
+ private final Cache<String, GetListingDependenciesResult> listingCache =
+ Caffeine.newBuilder().weakValues().build();
+
+ private final Cache<PackedFingerprint, GetNestedDependenciesResult> nestedCache =
Caffeine.newBuilder().weakValues().build();
FileDependencyDeserializer(FingerprintValueService fingerprintValueService) {
this.fingerprintValueService = fingerprintValueService;
}
- sealed interface GetDependenciesResult permits FileDependencies, FutureFileDependencies {}
+ sealed interface GetFileDependenciesResult 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}.
+ * as a permitted subtype of {@link GetFileDependenciesResult}.
*/
static final class FutureFileDependencies extends SettableFutureWithOwnership<FileDependencies>
- implements GetDependenciesResult {}
+ implements GetFileDependenciesResult {}
/**
* Reconstitutes the set of file dependencies associated with {@code key}.
@@ -129,7 +137,7 @@
* @return either an immediate {@link FileDependencies} instance or effectively a {@link
* ListenableFuture<FileDependencies>} instance.
*/
- GetDependenciesResult getFileDependencies(String key) {
+ GetFileDependenciesResult getFileDependencies(String key) {
FutureFileDependencies ownedFuture;
switch (fileCache.get(key, unused -> new FutureFileDependencies())) {
case FileDependencies dependencies:
@@ -142,37 +150,36 @@
break;
}
// `ownedFuture` is owned by this thread, which must complete its value.
- fetchInvalidationData(key, WaitForFileInvalidationData::new, ownedFuture);
+ fetchInvalidationData(key, this::getKeyBytes, WaitForFileInvalidationData::new, ownedFuture);
return ownedFuture;
}
- sealed interface GetDirectoryListingDependenciesResult
- permits DirectoryListingDependencies, FutureDirectoryListingDependencies {}
+ sealed interface GetListingDependenciesResult
+ permits ListingDependencies, FutureListingDependencies {}
/**
- * The main purpose of this class is to act as a {@link
- * ListenableFuture<DirectoryListingDependencies>}.
+ * The main purpose of this class is to act as a {@link ListenableFuture<ListingDependencies>}.
*
* <p>Its specific type is explicitly visible to clients to allow them to cleanly distinguish it
- * as a permitted subtype of {@link GetDirectoryListingDependenciesResult}.
+ * as a permitted subtype of {@link GetListingDependenciesResult}.
*/
- static final class FutureDirectoryListingDependencies
- extends SettableFutureWithOwnership<DirectoryListingDependencies>
- implements GetDirectoryListingDependenciesResult {}
+ static final class FutureListingDependencies
+ extends SettableFutureWithOwnership<ListingDependencies>
+ implements GetListingDependenciesResult {}
/**
* 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.
+ * @return either an immediate {@link ListingDependencies} instance or effectively a {@link
+ * ListenableFuture<ListingDependencies>} instance.
*/
- GetDirectoryListingDependenciesResult getDirectoryListingDependencies(String key) {
- FutureDirectoryListingDependencies ownedFuture;
- switch (listingCache.get(key, unused -> new FutureDirectoryListingDependencies())) {
- case DirectoryListingDependencies dependencies:
+ GetListingDependenciesResult getListingDependencies(String key) {
+ FutureListingDependencies ownedFuture;
+ switch (listingCache.get(key, unused -> new FutureListingDependencies())) {
+ case ListingDependencies dependencies:
return dependencies;
- case FutureDirectoryListingDependencies future:
+ case FutureListingDependencies future:
if (!future.tryTakeOwnership()) {
return future; // Owned by another thread.
}
@@ -180,7 +187,42 @@
break;
}
// `ownedFuture` is owned by this thread, which must complete its value.
- fetchInvalidationData(key, WaitForListingInvalidationData::new, ownedFuture);
+ fetchInvalidationData(key, this::getKeyBytes, WaitForListingInvalidationData::new, ownedFuture);
+ return ownedFuture;
+ }
+
+ sealed interface GetNestedDependenciesResult
+ permits NestedDependencies, FutureNestedDependencies {}
+
+ static final class FutureNestedDependencies
+ extends SettableFutureWithOwnership<NestedDependencies>
+ implements GetNestedDependenciesResult {}
+
+ /**
+ * Retrieves the nested dependency information associated with {@code key}.
+ *
+ * <p>Like the other implementations, this can be thought of as a simple state machine. There's
+ * one explicit state represented by {@link WaitForNestedNodeBytes}, which waits for the bytes
+ * associated with {@code key}. There's a second implicit state that waits for child elements,
+ * which may be files, listings or other nested nodes.
+ *
+ * @param key is a fingerprint of the byte representation described at {@link
+ * FileDependencySerializer#computeNodeBytes}.
+ */
+ GetNestedDependenciesResult getNestedDependencies(PackedFingerprint key) {
+ FutureNestedDependencies ownedFuture;
+ switch (nestedCache.get(key, unused -> new FutureNestedDependencies())) {
+ case NestedDependencies dependencies:
+ return dependencies;
+ case FutureNestedDependencies future:
+ if (!future.tryTakeOwnership()) {
+ return future; // Owned by another thread.
+ }
+ ownedFuture = future;
+ break;
+ }
+ // `ownedFuture` is owned by this thread, which must complete its value.
+ fetchInvalidationData(key, Functions.identity(), WaitForNestedNodeBytes::new, ownedFuture);
return ownedFuture;
}
@@ -412,10 +454,10 @@
return !previousParent.startsWith(newParent);
}
- // ---------- Begin DirectoryListingDependencies deserialization implementation ----------
+ // ---------- Begin ListingDependencies deserialization implementation ----------
private class WaitForListingInvalidationData
- implements AsyncFunction<byte[], DirectoryListingDependencies> {
+ implements AsyncFunction<byte[], ListingDependencies> {
private final String key;
private WaitForListingInvalidationData(String key) {
@@ -423,7 +465,7 @@
}
@Override
- public ListenableFuture<DirectoryListingDependencies> apply(byte[] bytes)
+ public ListenableFuture<ListingDependencies> apply(byte[] bytes)
throws InvalidProtocolBufferException {
var data = DirectoryListingInvalidationData.parseFrom(bytes, getEmptyRegistry());
if (data.hasOverflowKey() && !data.getOverflowKey().equals(key)) {
@@ -456,7 +498,7 @@
}
private class WaitForListingFileDependencies
- implements Function<FileDependencies, DirectoryListingDependencies> {
+ implements Function<FileDependencies, ListingDependencies> {
private final String key;
private WaitForListingFileDependencies(String key) {
@@ -464,26 +506,173 @@
}
@Override
- public DirectoryListingDependencies apply(FileDependencies dependencies) {
+ public ListingDependencies apply(FileDependencies dependencies) {
return createAndCacheListingDependencies(key, dependencies);
}
}
- private DirectoryListingDependencies createAndCacheListingDependencies(
+ private ListingDependencies createAndCacheListingDependencies(
String key, FileDependencies dependencies) {
- var result = new DirectoryListingDependencies(dependencies);
+ var result = new ListingDependencies(dependencies);
listingCache.put(key, result);
return result;
}
+ // ---------- Begin NestedDependencies deserialization implementation ----------
+
+ private class WaitForNestedNodeBytes implements AsyncFunction<byte[], NestedDependencies> {
+ private final PackedFingerprint key;
+
+ private WaitForNestedNodeBytes(PackedFingerprint key) {
+ this.key = key;
+ }
+
+ /**
+ * Parses the {@code bytes} to create a {@link NestedDependencies} instance.
+ *
+ * <p>Refer to comment at {@link FileDependencySerializer#computeNodeBytes} for the data format.
+ * Uses delegation for children, which might not be completely resolved.
+ */
+ @Override
+ public ListenableFuture<NestedDependencies> apply(byte[] bytes) {
+ try {
+ var codedIn = CodedInputStream.newInstance(bytes);
+ int fileCount = codedIn.readInt32();
+ int listingCount = codedIn.readInt32();
+ int nestedCount = codedIn.readInt32();
+
+ var elements = new FileSystemDependencies[fileCount + listingCount + nestedCount];
+ var countdown = new PendingElementCountdown(key, elements);
+
+ for (int i = 0; i < fileCount; i++) {
+ String key = codedIn.readString();
+ switch (getFileDependencies(key)) {
+ case FileDependencies dependencies:
+ elements[i] = dependencies;
+ break;
+ case FutureFileDependencies future:
+ countdown.registerPendingElement();
+ Futures.addCallback(
+ future, new WaitingForElement(elements, i, countdown), directExecutor());
+ break;
+ }
+ }
+
+ int directCount = fileCount + listingCount;
+ for (int i = fileCount; i < directCount; i++) {
+ String key = codedIn.readString();
+ switch (getListingDependencies(key)) {
+ case ListingDependencies dependencies:
+ elements[i] = dependencies;
+ break;
+ case FutureListingDependencies future:
+ countdown.registerPendingElement();
+ Futures.addCallback(
+ future, new WaitingForElement(elements, i, countdown), directExecutor());
+ break;
+ }
+ }
+
+ int total = directCount + nestedCount;
+ for (int i = directCount; i < total; i++) {
+ var key = PackedFingerprint.readFrom(codedIn);
+ switch (getNestedDependencies(key)) {
+ case NestedDependencies dependencies:
+ elements[i] = dependencies;
+ break;
+ case FutureNestedDependencies future:
+ countdown.registerPendingElement();
+ Futures.addCallback(
+ future, new WaitingForElement(elements, i, countdown), directExecutor());
+ break;
+ }
+ }
+ countdown.notifyInitializationDone();
+ return countdown;
+ } catch (IOException e) {
+ return immediateFailedFuture(e);
+ }
+ }
+ }
+
+ /**
+ * A future that keeps track of the count of elements that still need to be set.
+ *
+ * <p>This future completes once all the elements are set.
+ */
+ private class PendingElementCountdown extends QuiescingFuture<NestedDependencies> {
+ private final PackedFingerprint key;
+ private final FileSystemDependencies[] elements;
+
+ private PendingElementCountdown(PackedFingerprint key, FileSystemDependencies[] elements) {
+ this.key = key;
+ this.elements = elements;
+ }
+
+ private void registerPendingElement() {
+ increment();
+ }
+
+ private void notifyInitializationDone() {
+ decrement();
+ }
+
+ private void notifyElementSuccess() {
+ decrement();
+ }
+
+ private void notifyElementFailure(Throwable e) {
+ notifyException(e);
+ }
+
+ @Override
+ protected NestedDependencies getValue() {
+ var result = new NestedDependencies(elements);
+ nestedCache.put(key, result); // Replaces the future in the cache with the completed value.
+ return result;
+ }
+ }
+
+ /**
+ * Callback that populates the element at {@link #index} upon success.
+ *
+ * <p>Performs required bookkeeping for {@link PendingElementCountdown}.
+ */
+ private static class WaitingForElement implements FutureCallback<FileSystemDependencies> {
+ private final FileSystemDependencies[] elements;
+ private final int index;
+ private final PendingElementCountdown countdown;
+
+ private WaitingForElement(
+ FileSystemDependencies[] elements, int index, PendingElementCountdown countdown) {
+ this.elements = elements;
+ this.index = index;
+ this.countdown = countdown;
+ }
+
+ @Override
+ public void onSuccess(FileSystemDependencies dependencies) {
+ elements[index] = dependencies;
+ countdown.notifyElementSuccess();
+ }
+
+ @Override
+ public void onFailure(Throwable t) {
+ countdown.notifyElementFailure(t);
+ }
+ }
+
// ---------- Begin shared helpers ----------
- private <T, FutureT extends SettableFutureWithOwnership<T>> void fetchInvalidationData(
- String key, Function<String, AsyncFunction<byte[], T>> waitFactory, FutureT ownedFuture) {
+ private <KeyT, T, FutureT extends SettableFutureWithOwnership<T>> void fetchInvalidationData(
+ KeyT key,
+ Function<KeyT, ? extends KeyBytesProvider> keyConverter,
+ Function<KeyT, AsyncFunction<byte[], T>> waitFactory,
+ FutureT ownedFuture) {
try {
ListenableFuture<byte[]> futureBytes;
try {
- futureBytes = fingerprintValueService.get(getKeyBytes(key));
+ futureBytes = fingerprintValueService.get(keyConverter.apply(key));
} catch (IOException e) {
ownedFuture.failWith(e);
return;
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 bf0eb3a..6255dae 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
@@ -32,11 +32,14 @@
import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider.BundledFileSystem;
import com.google.devtools.build.lib.skyframe.DirectoryListingKey;
import com.google.devtools.build.lib.skyframe.FileKey;
+import com.google.devtools.build.lib.skyframe.NestedFileSystemOperationNodes;
import com.google.devtools.build.lib.skyframe.serialization.FingerprintValueService;
import com.google.devtools.build.lib.skyframe.serialization.KeyBytesProvider;
+import com.google.devtools.build.lib.skyframe.serialization.PackedFingerprint;
import com.google.devtools.build.lib.skyframe.serialization.StringKey;
-import com.google.devtools.build.lib.skyframe.serialization.analysis.InvalidationDataReference.DirectoryInvalidationDataReference;
import com.google.devtools.build.lib.skyframe.serialization.analysis.InvalidationDataReference.FileInvalidationDataReference;
+import com.google.devtools.build.lib.skyframe.serialization.analysis.InvalidationDataReference.ListingInvalidationDataReference;
+import com.google.devtools.build.lib.skyframe.serialization.analysis.InvalidationDataReference.NodeInvalidationDataReference;
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;
@@ -45,22 +48,25 @@
import com.google.devtools.build.skyframe.InMemoryGraph;
import com.google.devtools.build.skyframe.InMemoryNodeEntry;
import com.google.devtools.build.skyframe.Version;
+import com.google.protobuf.CodedOutputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
+import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Consumer;
import javax.annotation.Nullable;
/** Records {@link FileKey} and {@link DirectoryListingKey} invalidation information. */
final class FileDependencySerializer {
-
private final VersionNumberExtractor versionExtractor;
private final InMemoryGraph graph;
private final FingerprintValueService fingerprintValueService;
private final ConcurrentHashMap<FileKey, FileInvalidationDataReference> fileReferences =
new ConcurrentHashMap<>();
- private final ConcurrentHashMap<DirectoryListingKey, DirectoryInvalidationDataReference>
+ private final ConcurrentHashMap<DirectoryListingKey, ListingInvalidationDataReference>
directoryReferences = new ConcurrentHashMap<>();
interface VersionNumberExtractor {
@@ -171,15 +177,14 @@
}
@Nullable // null if `key` isn't relevant to invalidation
- DirectoryInvalidationDataReference registerDependency(DirectoryListingKey key) {
+ ListingInvalidationDataReference registerDependency(DirectoryListingKey key) {
RootedPath rootedPath = key.argument();
if (rootedPath.getRoot().getFileSystem() instanceof BundledFileSystem) {
return null; // This directory doesn't change.
}
- DirectoryInvalidationDataReference reference =
- directoryReferences.computeIfAbsent(
- key, unused -> new DirectoryInvalidationDataReference());
+ ListingInvalidationDataReference reference =
+ directoryReferences.computeIfAbsent(key, unused -> new ListingInvalidationDataReference());
// Uses double-checked locking to determine ownership of `reference`.
if (reference.getCacheKey() != null) {
return reference;
@@ -225,6 +230,59 @@
}
/**
+ * Registers a dependency on the set of transitive dependencies represented by {@code node}.
+ *
+ * <p>Uploads the result to the {@link #fingerprintValueService}.
+ *
+ * @return an reference having a non-null {@link NodeInvalidationDataReference#getCacheKey} or
+ * null. In particular, never returns {@link NodeInvalidationDataReference#EMPTY}.
+ */
+ @Nullable // null if `node` isn't relevant to invalidation
+ NodeInvalidationDataReference registerDependency(NestedFileSystemOperationNodes node) {
+ var reference = (NodeInvalidationDataReference) node.getSerializationScratch();
+ if (reference != null) {
+ return reference == NodeInvalidationDataReference.EMPTY ? null : reference;
+ }
+
+ byte[] nodeBytes;
+ var writeStatuses = new ArrayList<ListenableFuture<Void>>();
+ synchronized (node) {
+ reference = (NodeInvalidationDataReference) node.getSerializationScratch();
+ if (reference != null) {
+ return reference == NodeInvalidationDataReference.EMPTY ? null : reference;
+ }
+ // If this is reached, this thread must call `node.setSerializationScratch` to comply with the
+ // double-checked locking contract.
+
+ nodeBytes = computeNodeBytes(node, writeStatuses);
+ if (nodeBytes == null) {
+ node.setSerializationScratch(NodeInvalidationDataReference.EMPTY);
+ return null;
+ }
+
+ reference =
+ NodeInvalidationDataReference.create(fingerprintValueService.fingerprint(nodeBytes));
+ node.setSerializationScratch(reference);
+ }
+
+ // This thread owns completion of the future associated with `reference`.
+ boolean writeStatusSet = false;
+ try {
+ writeStatuses.add(fingerprintValueService.put(reference.getCacheKey(), nodeBytes));
+ reference.setWriteStatus(
+ writeStatuses.size() == 1
+ ? writeStatuses.get(0)
+ : Futures.whenAllSucceed(writeStatuses).call(() -> null, directExecutor()));
+ writeStatusSet = true;
+ } finally {
+ if (!writeStatusSet) {
+ reference.setUnexpectedlyUnsetError();
+ }
+ }
+ return reference;
+ }
+
+ /**
* Requires that there are no symlink cycles (though ancestor references are benign).
*
* <p>This is assumed to hold for builds that succeed.
@@ -289,6 +347,94 @@
}
}
+ /**
+ * Computes a canonical byte representation of a {@code node}.
+ *
+ * <p>Logically, a node is a set of string file or listing keys, as described at {@link
+ * FileInvalidationData} and {@link DirectoryListingInvalidationData}, respectively, and a set of
+ * {@link NestedFileSystemOperationNodes} fingerprints. The byte representation is specified as
+ * follows.
+ *
+ * <ol>
+ * <li>The count of file keys, as a proto-encoded int.
+ * <li>The count of listing keys, as a proto-encoded int.
+ * <li>The count of nested nodes, as a proto-encoded int.
+ * <li>Sorted and deduplicated, proto-encoded strings of the file keys.
+ * <li>Sorted and deduplicated, proto-encoded strings of the listing keys.
+ * <li>The fingerprints of the {@link NestedFileSystemOperationNodes} byte representations.
+ * </ol>
+ *
+ * <p>More compact formats are possible, but this reduces the complexity of the deserializer.
+ *
+ * @param writeStatuses output parameter collecting transitive write statuses
+ */
+ @Nullable // null if there were no transitive dependencies relevant to invalidation
+ private byte[] computeNodeBytes(
+ NestedFileSystemOperationNodes node, List<ListenableFuture<Void>> writeStatuses) {
+ // Makes no assumptions about the ordering or multiplicity of node dependencies. Sorts and
+ // deduplicates them to make them canonical.
+ var fileKeys = new TreeSet<String>();
+ var listingKeys = new TreeSet<String>();
+ var nodeKeys = new TreeSet<PackedFingerprint>();
+ for (int i = 0; i < node.count(); i++) {
+ switch (node.get(i)) {
+ case FileKey fileKey:
+ FileInvalidationDataReference fileReference = registerDependency(fileKey);
+ if (fileReference != null) {
+ fileKeys.add(checkNotNull(fileReference.getCacheKey(), node));
+ writeStatuses.add(fileReference);
+ }
+ break;
+ case DirectoryListingKey listingKey:
+ ListingInvalidationDataReference listingReference = registerDependency(listingKey);
+ if (listingReference != null) {
+ listingKeys.add(checkNotNull(listingReference.getCacheKey(), node));
+ writeStatuses.add(listingReference);
+ }
+ break;
+ case NestedFileSystemOperationNodes nestedKeys:
+ NodeInvalidationDataReference nodeReference = registerDependency(nestedKeys);
+ if (nodeReference != null) {
+ nodeKeys.add(checkNotNull(nodeReference.getCacheKey(), node));
+ writeStatuses.add(nodeReference);
+ }
+ break;
+ }
+ }
+ if (writeStatuses.isEmpty()) {
+ return null; // Nothing in the transitive closure of `node` is relevant to invalidation.
+ }
+
+ // TODO: b/364831651 - there are multiple ways that result could become unary here, even if
+ // `node` always has at least 2 children. The following may reduce child count.
+ // 1. TreeSet deduplication.
+ // 2. null references.
+ // 3. NestedFileSystemOperationNodes with the same fingerprints.
+ // It may be worth special casing to avoid the additional wrapper if the result is unary.
+
+ try {
+ var bytesOut = new ByteArrayOutputStream();
+ var codedOut = CodedOutputStream.newInstance(bytesOut);
+ codedOut.writeInt32NoTag(fileKeys.size());
+ codedOut.writeInt32NoTag(listingKeys.size());
+ codedOut.writeInt32NoTag(nodeKeys.size());
+ for (String key : fileKeys) {
+ codedOut.writeStringNoTag(key);
+ }
+ for (String key : listingKeys) {
+ codedOut.writeStringNoTag(key);
+ }
+ for (PackedFingerprint fp : nodeKeys) {
+ fp.writeTo(codedOut);
+ }
+ codedOut.flush();
+ bytesOut.flush();
+ return bytesOut.toByteArray();
+ } catch (IOException e) {
+ throw new AssertionError("Unexpected IOException from ByteArrayOutputStream", e);
+ }
+ }
+
private KeyBytesProvider getKeyBytes(String cacheKey, Consumer<String> overflowConsumer) {
if (cacheKey.length() > MAX_KEY_LENGTH) {
overflowConsumer.accept(cacheKey);
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
index 072e135..6841d50 100644
--- 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
@@ -14,12 +14,14 @@
package com.google.devtools.build.lib.skyframe.serialization.analysis;
/**
- * Union type for {@link FileDependencies} and {@link DirectoryListingDependencies}.
+ * Union type for {@link FileDependencies}, {@link ListingDependencies} and {@link
+ * NestedDependencies}.
*
- * <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.
+ * <p>At a structural level {@link FileDependencies} and {@link ListingDependencies} are very
+ * similar. {@link ListingDependencies} could be modeled plainly as {@link FileDependencies}. The
+ * crucial difference is that {@link FileDependencies#containsMatch(ImmutableSet<String>)} takes a
+ * set of files and {@link ListingDependencies#matchesAnyDirectories(ImmutableSet<String>)} takes a
+ * set of directory names so the two types are deliberately separated.
*/
-sealed interface FileSystemDependencies permits FileDependencies, DirectoryListingDependencies {}
+sealed interface FileSystemDependencies
+ permits FileDependencies, ListingDependencies, NestedDependencies {}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/InvalidationDataReference.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/InvalidationDataReference.java
index 51302b2..ab088fd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/InvalidationDataReference.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/InvalidationDataReference.java
@@ -13,35 +13,42 @@
// limitations under the License.
package com.google.devtools.build.lib.skyframe.serialization.analysis;
+import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import com.google.common.util.concurrent.AbstractFuture;
import com.google.common.util.concurrent.ListenableFuture;
+import com.google.devtools.build.lib.skyframe.serialization.PackedFingerprint;
import com.google.devtools.build.lib.vfs.RootedPath;
import javax.annotation.Nullable;
/**
- * Future representing transitive write status for file or directory invalidation data.
+ * Future representing the transitive write status of invalidation data.
*
- * <p>The client should perform double-checked locking to populate some of the metadata by testing
- * {@link #getCacheKey} for nullness. If it is null outside of the lock, and null again inside the
- * lock, the caller must call either one of the {@code populate} methods depending on the subclass.
+ * <p>In the case of {@link FileInvalidationDataReference} and {@link
+ * ListingInvalidationDataReference}, the client should perform double-checked locking to populate
+ * the metadata by testing {@link #getCacheKey} for nullness. If it is null outside of the lock, and
+ * null again inside the lock, the caller must call one of the {@code populate} methods depending on
+ * the subclass.
+ *
+ * <p>For {@link NodeInvalidationDataReference}, the metadata is assigned at construction.
*/
-sealed class InvalidationDataReference extends AbstractFuture<Void>
+sealed class InvalidationDataReference<T> extends AbstractFuture<Void>
permits InvalidationDataReference.FileInvalidationDataReference,
- InvalidationDataReference.DirectoryInvalidationDataReference {
- private volatile String cacheKey;
+ InvalidationDataReference.ListingInvalidationDataReference,
+ InvalidationDataReference.NodeInvalidationDataReference {
+ private volatile T cacheKey;
@Nullable // null when uninitialized
- String getCacheKey() {
+ final T getCacheKey() {
return cacheKey;
}
- void setWriteStatus(ListenableFuture<Void> writeStatus) {
+ final void setWriteStatus(ListenableFuture<Void> writeStatus) {
checkState(setFuture(writeStatus), "already set %s", this);
}
- void setUnexpectedlyUnsetError() {
+ final void setUnexpectedlyUnsetError() {
checkState(
setException(
new IllegalStateException(
@@ -49,11 +56,12 @@
+ " FileDependencySerializer")));
}
- void setCacheKeyForSubclasses(String cacheKey) {
+ final void setCacheKeyForSubclasses(T cacheKey) {
this.cacheKey = cacheKey;
}
- static final class FileInvalidationDataReference extends InvalidationDataReference {
+ /** Future transitive write status for {@link com.google.devtools.build.lib.skyframe.FileKey}. */
+ static final class FileInvalidationDataReference extends InvalidationDataReference<String> {
private long mtsv;
private RootedPath realPath;
@@ -89,9 +97,41 @@
}
}
- static final class DirectoryInvalidationDataReference extends InvalidationDataReference {
+ /**
+ * Future transitive write status for {@link
+ * com.google.devtools.build.lib.skyframe.DirectoryListingKey}.
+ */
+ static final class ListingInvalidationDataReference extends InvalidationDataReference<String> {
void populate(String cacheKey) {
setCacheKeyForSubclasses(cacheKey);
}
}
+
+ /**
+ * Future transitive write status of {@link
+ * com.google.devtools.build.lib.skyframe.NestedFileSystemOperationNodes}.
+ *
+ * <p>{@link #getCacheKey} is null only for {@link #EMPTY}.
+ */
+ static final class NodeInvalidationDataReference
+ extends InvalidationDataReference<PackedFingerprint> {
+ /* In contrast to the above two implementations, there's no distinct populate phase because
+ * this class does not need to be constructed inside a computeIfAbsent callback.
+ */
+
+ /**
+ * A no-data sentinel value.
+ *
+ * <p>Occurs if none of the transitive node inputs are relevant to invalidation.
+ */
+ static final NodeInvalidationDataReference EMPTY = new NodeInvalidationDataReference(null);
+
+ static NodeInvalidationDataReference create(PackedFingerprint key) {
+ return new NodeInvalidationDataReference(checkNotNull(key));
+ }
+
+ private NodeInvalidationDataReference(PackedFingerprint key) {
+ setCacheKeyForSubclasses(key);
+ }
+ }
}
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/ListingDependencies.java
similarity index 86%
rename from src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/DirectoryListingDependencies.java
rename to src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ListingDependencies.java
index 402694b..a1c0b09 100644
--- 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/ListingDependencies.java
@@ -18,12 +18,11 @@
import com.google.common.collect.ImmutableSet;
/** Type representing a directory listing operation. */
-final class DirectoryListingDependencies
- implements FileDependencyDeserializer.GetDirectoryListingDependenciesResult,
- FileSystemDependencies {
+final class ListingDependencies
+ implements FileDependencyDeserializer.GetListingDependenciesResult, FileSystemDependencies {
private final FileDependencies realDirectory;
- DirectoryListingDependencies(FileDependencies realDirectory) {
+ ListingDependencies(FileDependencies realDirectory) {
this.realDirectory = realDirectory;
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java
new file mode 100644
index 0000000..d054632
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java
@@ -0,0 +1,49 @@
+// 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.MoreObjects.toStringHelper;
+import static com.google.common.base.Preconditions.checkArgument;
+
+import java.util.Arrays;
+
+/**
+ * A representation of a recursively composable set of {@link FileSystemDependencies}.
+ *
+ * <p>This corresponds to a previously serialized {@link
+ * com.google.devtools.build.lib.skyframe.NestedFileSystemOperationNodes} instance, but this
+ * implementation is mostly decoupled from Bazel code.
+ */
+final class NestedDependencies
+ implements FileSystemDependencies, FileDependencyDeserializer.GetNestedDependenciesResult {
+ private final FileSystemDependencies[] elements;
+
+ NestedDependencies(FileSystemDependencies[] elements) {
+ checkArgument(elements.length > 1, "expected at least length 2, was %s", elements.length);
+ this.elements = elements;
+ }
+
+ int count() {
+ return elements.length;
+ }
+
+ FileSystemDependencies getElement(int index) {
+ return elements[index];
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("elements", Arrays.asList(elements)).toString();
+ }
+}
