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(); + } +}