diff options
author | 2018-06-13 13:06:17 -0700 | |
---|---|---|
committer | 2018-06-13 13:07:41 -0700 | |
commit | 9bbc66c8613deb4233e3cb116d0aae5724eece7f (patch) | |
tree | c1a95e1cb6b0370a616f5d9daf9ce966a6d6fea0 | |
parent | d6bd9eb43b8e4b47acd4e5003b586bd47edaba4e (diff) |
Allow deserialization futures as NestedSet contents, with unrolling blocking on that future.
This allows NestedSet deserialization not to block on storage reads - in-progress deserializations are simply made a member of the NestedSets they produce.
PiperOrigin-RevId: 200440131
10 files changed, 401 insertions, 132 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java index 52df58e36a..5371c306eb 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java @@ -19,6 +19,7 @@ import com.google.common.base.Function; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; +import com.google.common.util.concurrent.ListenableFuture; import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet; import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec; import com.google.protobuf.ByteString; @@ -29,6 +30,7 @@ import java.util.Iterator; import java.util.List; import java.util.Objects; import java.util.Set; +import java.util.concurrent.ExecutionException; import javax.annotation.Nullable; /** @@ -55,9 +57,7 @@ public final class NestedSet<E> implements Iterable<E> { private static final byte[] LEAF_MEMO = {}; @AutoCodec static final Object[] EMPTY_CHILDREN = {}; - /** - * Construct an empty NestedSet. Should only be called by Order's class initializer. - */ + /** Construct an empty NestedSet. Should only be called by Order's class initializer. */ NestedSet(Order order) { this.orderAndSize = order.ordinal(); this.children = EMPTY_CHILDREN; @@ -116,7 +116,8 @@ public final class NestedSet<E> implements Iterable<E> { } else if ((pass == 1) == preorder && !transitive.isEmpty()) { CompactHashSet<E> hoisted = CompactHashSet.create(); for (NestedSet<E> subset : transitiveOrder) { - Object c = subset.children; + // If this is a deserialization future, this call blocks. + Object c = subset.getChildren(); if (c instanceof Object[]) { Object[] a = (Object[]) c; if (a.length < 2) { @@ -149,63 +150,93 @@ public final class NestedSet<E> implements Iterable<E> { } } - // Only used by deserialization - @AutoCodec.Instantiator - NestedSet(Order order, Object children) { + private NestedSet(Order order, Object children, byte[] memo) { this.orderAndSize = order.ordinal(); this.children = children; + this.memo = memo; + } + + /** + * Constructs a NestedSet that is currently being deserialized. The provided future, when + * complete, gives the contents of the NestedSet. + */ + static <E> NestedSet<E> withFuture( + Order order, ListenableFuture<Object[]> deserializationFuture) { + return new NestedSet<>(order, deserializationFuture, /*memo=*/ null); + } + + // Only used by deserialization + @AutoCodec.Instantiator + static <E> NestedSet<E> forDeserialization(Order order, Object children) { + Preconditions.checkState(!(children instanceof ListenableFuture)); boolean hasChildren = children instanceof Object[] && (Arrays.stream((Object[]) children).anyMatch(child -> child instanceof Object[])); - this.memo = hasChildren ? null : LEAF_MEMO; + byte[] memo = hasChildren ? null : LEAF_MEMO; + return new NestedSet<>(order, children, memo); } - /** - * Returns the ordering of this nested set. - */ + /** Returns the ordering of this nested set. */ public Order getOrder() { return Order.getOrder(orderAndSize & 3); } /** - * Returns the internal item or array. For use by NestedSetVisitor and NestedSetView. Those two - * classes also have knowledge of the internal implementation of NestedSet. + * Returns the internal item or array. If the internal item is a deserialization future, blocks on + * completion. For external use only by NestedSetVisitor and NestedSetView. Those two classes also + * have knowledge of the internal implementation of NestedSet. */ + Object getChildren() { + if (children instanceof ListenableFuture) { + try { + return ((ListenableFuture<Object[]>) children).get(); + } catch (InterruptedException | ExecutionException e) { + throw new IllegalStateException(e); + } + } else { + return children; + } + } + + /** Returns the internal item, array, or future. */ Object rawChildren() { return children; } - /** - * Returns true if the set is empty. Runs in O(1) time (i.e. does not flatten the set). - */ + /** Returns true if the set is empty. Runs in O(1) time (i.e. does not flatten the set). */ public boolean isEmpty() { + // We don't check for future members here, since empty sets are special-cased in serialization + // and do not make requests against storage. return children == EMPTY_CHILDREN; } /** Returns true if the set has exactly one element. */ public boolean isSingleton() { - return !(children instanceof Object[]); + // Singleton sets are special cased in serialization, and make no calls to storage. Therefore, + // we know that any NestedSet with a ListenableFuture member is not a singleton. + return !(children instanceof Object[] || children instanceof ListenableFuture); } /** - * Returns a collection of all unique elements of this set (including subsets) - * in an implementation-specified order as a {@code Collection}. + * Returns a collection of all unique elements of this set (including subsets) in an + * implementation-specified order as a {@code Collection}. * - * <p>If you do not need a Collection and an Iterable is enough, use the - * nested set itself as an Iterable. + * <p>If you do not need a Collection and an Iterable is enough, use the nested set itself as an + * Iterable. */ public Collection<E> toCollection() { return toList(); } /** - * Returns a collection of all unique elements of this set (including subsets) - * in an implementation-specified order as a {code List}. + * Returns a collection of all unique elements of this set (including subsets) in an + * implementation-specified order as a {code List}. * * <p>Use {@link #toCollection} when possible for better efficiency. */ public List<E> toList() { if (isSingleton()) { + // No need to check for ListenableFuture members - singletons can't have them. return ImmutableList.of((E) children); } if (isEmpty()) { @@ -215,8 +246,8 @@ public final class NestedSet<E> implements Iterable<E> { } /** - * Returns a collection of all unique elements of this set (including subsets) - * in an implementation-specified order as a {@code Set}. + * Returns a collection of all unique elements of this set (including subsets) in an + * implementation-specified order as a {@code Set}. * * <p>Use {@link #toCollection} when possible for better efficiency. */ @@ -225,11 +256,13 @@ public final class NestedSet<E> implements Iterable<E> { } /** - * Returns true if this set is equal to {@code other} based on the top-level - * elements and object identity (==) of direct subsets. As such, this function - * can fail to equate {@code this} with another {@code NestedSet} that holds - * the same elements. It will never fail to detect that two {@code NestedSet}s - * are different, however. + * Returns true if this set is equal to {@code other} based on the top-level elements and object + * identity (==) of direct subsets. As such, this function can fail to equate {@code this} with + * another {@code NestedSet} that holds the same elements. It will never fail to detect that two + * {@code NestedSet}s are different, however. + * + * <p>If one of the sets is in the process of deserialization, returns true iff both sets depend + * on the same future. * * @param other the {@code NestedSet} to compare against. */ @@ -237,25 +270,28 @@ public final class NestedSet<E> implements Iterable<E> { if (this == other) { return true; } + return other != null && getOrder() == other.getOrder() - && (children.equals(other.children) + && (rawChildren().equals(other.rawChildren()) || (!isSingleton() && !other.isSingleton() + && rawChildren() instanceof Object[] + && other.rawChildren() instanceof Object[] && Arrays.equals((Object[]) children, (Object[]) other.children))); } /** - * Returns a hash code that produces a notion of identity that is consistent with - * {@link #shallowEquals}. In other words, if two {@code NestedSet}s are equal according - * to {@code #shallowEquals}, then they return the same {@code shallowHashCode}. + * Returns a hash code that produces a notion of identity that is consistent with {@link + * #shallowEquals}. In other words, if two {@code NestedSet}s are equal according to {@code + * #shallowEquals}, then they return the same {@code shallowHashCode}. * - * <p>The main reason for having these separate functions instead of reusing - * the standard equals/hashCode is to minimize accidental use, since they are - * different from both standard Java objects and collection-like objects. + * <p>The main reason for having these separate functions instead of reusing the standard + * equals/hashCode is to minimize accidental use, since they are different from both standard Java + * objects and collection-like objects. */ public int shallowHashCode() { - return isSingleton() + return isSingleton() || children instanceof ListenableFuture ? Objects.hash(getOrder(), children) : Objects.hash(getOrder(), Arrays.hashCode((Object[]) children)); } @@ -278,7 +314,9 @@ public final class NestedSet<E> implements Iterable<E> { private enum Stringer implements Function<Object, String> { INSTANCE; - @Override public String apply(Object o) { + + @Override + public String apply(Object o) { return childrenToString(o); } } @@ -290,9 +328,9 @@ public final class NestedSet<E> implements Iterable<E> { } /** - * Implementation of {@link #toList}. Uses one of three strategies based on the value of - * {@code this.memo}: wrap our direct items in a list, call {@link #lockedExpand} to perform - * the initial {@link #walk}, or call {@link #replay} if we have a nontrivial memo. + * Implementation of {@link #toList}. Uses one of three strategies based on the value of {@code + * this.memo}: wrap our direct items in a list, call {@link #lockedExpand} to perform the initial + * {@link #walk}, or call {@link #replay} if we have a nontrivial memo. */ private ImmutableList<E> expand() { // This value is only set in the constructor, so safe to test here with no lock. @@ -303,7 +341,7 @@ public final class NestedSet<E> implements Iterable<E> { if (members != null) { return ImmutableList.copyOf(members); } - Object[] children = (Object[]) this.children; + Object[] children = (Object[]) this.getChildren(); ImmutableList.Builder<E> output = ImmutableList.builderWithExpectedSize(orderAndSize >> 2); replay(output, children, memo, 0); return output.build(); @@ -316,26 +354,32 @@ public final class NestedSet<E> implements Iterable<E> { ArraySharingCollection(Object[] array) { this.array = array; } - @Override public Object[] toArray() { + + @Override + public Object[] toArray() { return array; } - @Override public int size() { + + @Override + public int size() { return array.length; } - @Override public Iterator<E> iterator() { + + @Override + public Iterator<E> iterator() { throw new UnsupportedOperationException(); } } /** * If this is the first call for this object, fills {@code this.memo} and returns a set from - * {@link #walk}. Otherwise returns null; the caller should use {@link #replay} instead. + * {@link #walk}. Otherwise returns null; the caller should use {@link #replay} instead. */ private synchronized CompactHashSet<E> lockedExpand() { if (memo != null) { return null; } - Object[] children = (Object[]) this.children; + Object[] children = (Object[]) this.getChildren(); CompactHashSet<E> members = CompactHashSet.createWithExpectedSize(128); CompactHashSet<Object> sets = CompactHashSet.createWithExpectedSize(128); sets.add(children); diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java index ea455f87e1..36171b5cdc 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java @@ -23,6 +23,7 @@ import com.google.devtools.build.lib.skyframe.serialization.SerializationExcepti import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec; import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization; import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester; +import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester.VerificationFunction; import java.io.IOException; /** Utilities for testing NestedSet serialization. */ @@ -49,7 +50,7 @@ public class NestedSetCodecTestUtils { return false; } HasNestedSet that = (HasNestedSet) o; - return Objects.equal(nestedSetField.rawChildren(), that.nestedSetField.rawChildren()); + return Objects.equal(nestedSetField.getChildren(), that.nestedSetField.getChildren()); } @Override @@ -59,7 +60,8 @@ public class NestedSetCodecTestUtils { } /** Perform serialization/deserialization checks for several simple NestedSet examples. */ - public static void checkCodec(ObjectCodecs objectCodecs, boolean allowFutureBlocking) + public static void checkCodec( + ObjectCodecs objectCodecs, boolean allowFutureBlocking, boolean assertSymmetricEquality) throws Exception { new SerializationTester( NestedSetBuilder.emptySet(Order.STABLE_ORDER), @@ -86,7 +88,7 @@ public class NestedSetCodecTestUtils { new HasNestedSet(NestedSetBuilder.create(Order.STABLE_ORDER, "a")))) .setObjectCodecs(objectCodecs) .makeMemoizingAndAllowFutureBlocking(allowFutureBlocking) - .setVerificationFunction(NestedSetCodecTestUtils::verifyDeserialization) + .setVerificationFunction(verificationFunction(assertSymmetricEquality)) .runTests(); } @@ -94,15 +96,21 @@ public class NestedSetCodecTestUtils { NestedSetStore store, NestedSet<?> nestedSet, SerializationContext serializationContext) throws IOException, SerializationException { return store - .computeFingerprintAndStore((Object[]) nestedSet.rawChildren(), serializationContext) + .computeFingerprintAndStore((Object[]) nestedSet.getChildren(), serializationContext) .writeStatus(); } - private static void verifyDeserialization( - NestedSet<String> subject, NestedSet<String> deserialized) { - assertThat(subject.getOrder()).isEqualTo(deserialized.getOrder()); - assertThat(subject.toSet()).isEqualTo(deserialized.toSet()); - verifyStructure(subject.rawChildren(), deserialized.rawChildren()); + private static VerificationFunction<NestedSet<String>> verificationFunction( + boolean assertSymmetricEquality) { + return (subject, deserialized) -> { + if (assertSymmetricEquality) { + assertThat(subject).isEqualTo(deserialized); + assertThat(deserialized).isEqualTo(subject); + } + assertThat(subject.getOrder()).isEqualTo(deserialized.getOrder()); + assertThat(subject.toSet()).isEqualTo(deserialized.toSet()); + verifyStructure(subject.getChildren(), deserialized.getChildren()); + }; } private static void verifyStructure(Object lhs, Object rhs) { diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java index 081fd674f8..acd7ec5931 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java @@ -15,6 +15,8 @@ package com.google.devtools.build.lib.collect.nestedset; import com.google.common.cache.Cache; import com.google.common.cache.CacheBuilder; +import com.google.common.util.concurrent.Futures; +import com.google.common.util.concurrent.ListenableFuture; import com.google.devtools.build.lib.collect.nestedset.NestedSetStore.FingerprintComputationResult; import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext; import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec; @@ -86,11 +88,11 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> { } else if (obj.isSingleton()) { // If the NestedSet is a singleton, we serialize directly as an optimization. codedOut.writeEnumNoTag(NestedSetSize.SINGLETON.ordinal()); - context.serialize(obj.rawChildren(), codedOut); + context.serialize(obj.getChildren(), codedOut); } else { codedOut.writeEnumNoTag(NestedSetSize.GROUP.ordinal()); FingerprintComputationResult fingerprintComputationResult = - nestedSetStore.computeFingerprintAndStore((Object[]) obj.rawChildren(), context); + nestedSetStore.computeFingerprintAndStore((Object[]) obj.getChildren(), context); context.addFutureToBlockWritingOn(fingerprintComputationResult.writeStatus()); codedOut.writeByteArrayNoTag(fingerprintComputationResult.fingerprint().toByteArray()); } @@ -115,8 +117,9 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> { return intern(order, contents); case GROUP: ByteString fingerprint = ByteString.copyFrom(codedIn.readByteArray()); - Object members = nestedSetStore.getContentsAndDeserialize(fingerprint, context); - return intern(order, members); + ListenableFuture<Object[]> deserializationFuture = + nestedSetStore.getContentsAndDeserialize(fingerprint, context); + return intern(order, deserializationFuture); } throw new IllegalStateException("NestedSet size " + nestedSetSize + " not known"); } @@ -125,20 +128,31 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> { * Morally, NestedSets are compared using reference equality, to avoid the cost of unrolling them. * However, when deserializing NestedSet, we don't want to end up with two sets that "should" be * reference-equal, but are not. Since our codec implementation caches the underlying {@link - * NestedSet#children} Object[], two nested sets that should be the same will have equal - * underlying {@link NestedSet#children}, so we can use that for an equality check. + * NestedSet#getChildren()} Object[], two nested sets that should be the same will have equal + * underlying {@link NestedSet#getChildren()}, so we can use that for an equality check. + * + * <p>We also would like to prevent the existence of two equal NestedSets in a single JVM, in + * which one NestedSet contains an Object[] and the other contains a ListenableFuture<Object[]> + * for the same contents. This can happen if a NestedSet is serialized, and then deserialized with + * a call to storage for those contents. In order to guarantee that only one NestedSet exists for + * a given Object[], the interner checks the doneness of any ListenableFuture, and if done, holds + * on only to the "materialized" NestedSet, with the Object[] as its children object. * * <p>Note that singleton NestedSets' underlying children are not cached, but we must still * enforce equality for them. To do that, we use the #hashCode and #equals of the {@link - * NestedSet#children}. When that field is an Object[], this is just identity hash code and + * NestedSet#getChildren()}. When that field is an Object[], this is just identity hash code and * reference equality, but when it is something else (like an Artifact), we will do an actual * equality comparison. This may make some singleton NestedSets reference-equal where they were * not before. This should be ok as long as the contained object properly implements equality. - * - * <p>TODO(janakr): Fix this bug. */ + @SuppressWarnings("unchecked") private NestedSet<T> intern(Order order, Object contents) { - NestedSet<T> result = new NestedSet<>(order, contents); + NestedSet<T> result; + if (contents instanceof ListenableFuture) { + result = NestedSet.withFuture(order, (ListenableFuture<Object[]>) contents); + } else { + result = NestedSet.forDeserialization(order, contents); + } try { return interner.get(new EqualsWrapper<>(result), () -> result); } catch (ExecutionException e) { @@ -153,11 +167,38 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> { this.nestedSet = nestedSet; } + @SuppressWarnings("unchecked") @Override public int hashCode() { - return 37 * nestedSet.getOrder().hashCode() + nestedSet.rawChildren().hashCode(); + int childrenHashCode; + if (nestedSet.rawChildren() instanceof ListenableFuture + && ((ListenableFuture) nestedSet.rawChildren()).isDone()) { + try { + childrenHashCode = Futures.getDone((ListenableFuture) nestedSet.rawChildren()).hashCode(); + } catch (ExecutionException e) { + throw new IllegalStateException(e); + } + } else { + childrenHashCode = nestedSet.rawChildren().hashCode(); + } + + return 37 * nestedSet.getOrder().hashCode() + childrenHashCode; } + private static boolean deserializingAndMaterializedSetsAreEqual( + Object[] contents, ListenableFuture<Object[]> contentsFuture) { + if (!contentsFuture.isDone()) { + return false; + } + + try { + return Futures.getDone(contentsFuture) == contents; + } catch (ExecutionException e) { + throw new IllegalStateException(e); + } + } + + @SuppressWarnings("unchecked") @Override public boolean equals(Object obj) { if (this == obj) { @@ -166,9 +207,28 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> { if (!(obj instanceof EqualsWrapper)) { return false; } + + // Both sets contain Object[] or both sets contain ListenableFuture<Object[]> NestedSet<?> thatSet = ((EqualsWrapper<?>) obj).nestedSet; - return this.nestedSet.getOrder().equals(thatSet.getOrder()) - && this.nestedSet.rawChildren().equals(thatSet.rawChildren()); + if (this.nestedSet.getOrder().equals(thatSet.getOrder()) + && this.nestedSet.rawChildren().equals(thatSet.rawChildren())) { + return true; + } + + // One set contains Object[], while the other contains ListenableFuture<Object[]> + if (this.nestedSet.rawChildren() instanceof ListenableFuture + && thatSet.rawChildren() instanceof Object[]) { + return deserializingAndMaterializedSetsAreEqual( + (Object[]) thatSet.rawChildren(), + (ListenableFuture<Object[]>) this.nestedSet.rawChildren()); + } else if (thatSet.rawChildren() instanceof ListenableFuture + && this.nestedSet.rawChildren() instanceof Object[]) { + return deserializingAndMaterializedSetsAreEqual( + (Object[]) this.nestedSet.rawChildren(), + (ListenableFuture<Object[]>) thatSet.rawChildren()); + } else { + return false; + } } } } diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java index f0b1c2a8db..8eb4131793 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java @@ -53,7 +53,7 @@ public class NestedSetFingerprintCache { } DigestMap digestMap = mapFnToDigestMap.computeIfAbsent(mapFn, this::newDigestMap); fingerprint.addInt(nestedSet.getOrder().ordinal()); - Object children = nestedSet.rawChildren(); + Object children = nestedSet.getChildren(); addToFingerprint(mapFn, fingerprint, digestMap, children); } diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java index 52d7769a2c..173420aa1d 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java @@ -31,7 +31,11 @@ import com.google.protobuf.CodedInputStream; import com.google.protobuf.CodedOutputStream; import java.io.ByteArrayOutputStream; import java.io.IOException; +import java.util.ArrayList; +import java.util.List; import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ExecutionException; +import java.util.concurrent.Executor; import javax.annotation.Nullable; /** @@ -70,11 +74,12 @@ public class NestedSetStore { /** * Retrieves the serialized bytes for the NestedSet contents associated with this fingerprint. */ - byte[] get(ByteString fingerprint) throws IOException; + ListenableFuture<byte[]> get(ByteString fingerprint) throws IOException; } /** An in-memory {@link NestedSetStorageEndpoint} */ - private static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint { + @VisibleForTesting + static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint { private final ConcurrentHashMap<ByteString, byte[]> fingerprintToContents = new ConcurrentHashMap<>(); @@ -85,14 +90,15 @@ public class NestedSetStore { } @Override - public byte[] get(ByteString fingerprint) { - return fingerprintToContents.get(fingerprint); + public ListenableFuture<byte[]> get(ByteString fingerprint) { + return Futures.immediateFuture(fingerprintToContents.get(fingerprint)); } } /** An in-memory cache for fingerprint <-> NestedSet associations. */ - private static class NestedSetCache { - private final Cache<ByteString, Object[]> fingerprintToContents = + @VisibleForTesting + static class NestedSetCache { + private final Cache<ByteString, ListenableFuture<Object[]>> fingerprintToContents = CacheBuilder.newBuilder() .concurrencyLevel(SerializationConstants.DESERIALIZATION_POOL_SIZE) .weakValues() @@ -110,7 +116,7 @@ public class NestedSetStore { * fingerprint is not known. */ @Nullable - public Object[] contentsForFingerprint(ByteString fingerprint) { + public ListenableFuture<Object[]> contentsForFingerprint(ByteString fingerprint) { return fingerprintToContents.getIfPresent(fingerprint); } @@ -124,9 +130,29 @@ public class NestedSetStore { } /** Associates the provided fingerprint and NestedSet contents. */ + public void put( + FingerprintComputationResult fingerprintComputationResult, + ListenableFuture<Object[]> contents) { + contents.addListener( + () -> { + try { + contentsToFingerprint.put(Futures.getDone(contents), fingerprintComputationResult); + } catch (ExecutionException e) { + throw new AssertionError( + "Expected write for " + + fingerprintComputationResult.fingerprint() + + " to be complete", + e.getCause()); + } + }, + MoreExecutors.directExecutor()); + fingerprintToContents.put(fingerprintComputationResult.fingerprint(), contents); + } + public void put(FingerprintComputationResult fingerprintComputationResult, Object[] contents) { contentsToFingerprint.put(contents, fingerprintComputationResult); - fingerprintToContents.put(fingerprintComputationResult.fingerprint(), contents); + fingerprintToContents.put( + fingerprintComputationResult.fingerprint(), Futures.immediateFuture(contents)); } } @@ -145,12 +171,31 @@ public class NestedSetStore { public abstract ListenableFuture<Void> writeStatus(); } - private final NestedSetCache nestedSetCache = new NestedSetCache(); + private final NestedSetCache nestedSetCache; private final NestedSetStorageEndpoint nestedSetStorageEndpoint; + private final Executor executor; /** Creates a NestedSetStore with the provided {@link NestedSetStorageEndpoint} as a backend. */ public NestedSetStore(NestedSetStorageEndpoint nestedSetStorageEndpoint) { + this(nestedSetStorageEndpoint, new NestedSetCache(), MoreExecutors.directExecutor()); + } + + /** + * Creates a NestedSetStore with the provided {@link NestedSetStorageEndpoint} and executor for + * deserialization. + */ + public NestedSetStore(NestedSetStorageEndpoint nestedSetStorageEndpoint, Executor executor) { + this(nestedSetStorageEndpoint, new NestedSetCache(), executor); + } + + @VisibleForTesting + public NestedSetStore( + NestedSetStorageEndpoint nestedSetStorageEndpoint, + NestedSetCache nestedSetCache, + Executor executor) { this.nestedSetStorageEndpoint = nestedSetStorageEndpoint; + this.nestedSetCache = nestedSetCache; + this.executor = executor; } /** Creates a NestedSetStore with an in-memory storage backend. */ @@ -226,37 +271,54 @@ public class NestedSetStore { } /** Retrieves and deserializes the NestedSet contents associated with the given fingerprint. */ - public Object[] getContentsAndDeserialize( - ByteString fingerprint, DeserializationContext deserializationContext) - throws SerializationException, IOException { - Object[] contents = nestedSetCache.contentsForFingerprint(fingerprint); + public ListenableFuture<Object[]> getContentsAndDeserialize( + ByteString fingerprint, DeserializationContext deserializationContext) throws IOException { + ListenableFuture<Object[]> contents = nestedSetCache.contentsForFingerprint(fingerprint); if (contents != null) { return contents; } + ListenableFuture<byte[]> retrieved = nestedSetStorageEndpoint.get(fingerprint); + ListenableFuture<Object[]> result = + Futures.transformAsync( + retrieved, + bytes -> { + CodedInputStream codedIn = CodedInputStream.newInstance(bytes); + int numberOfElements = codedIn.readInt32(); + DeserializationContext newDeserializationContext = + deserializationContext.getNewMemoizingContext(); - byte[] retrieved = nestedSetStorageEndpoint.get(fingerprint); - if (retrieved == null) { - throw new AssertionError("Fingerprint " + fingerprint + " not found in NestedSetStore"); - } + // The elements of this list are futures for the deserialized values of these + // NestedSet contents. For direct members, the futures complete immediately and yield + // an Object. For transitive members (fingerprints), the futures complete with the + // underlying fetch, and yield Object[]s. + List<ListenableFuture<?>> deserializationFutures = new ArrayList<>(); + for (int i = 0; i < numberOfElements; i++) { + Object deserializedElement = newDeserializationContext.deserialize(codedIn); + if (deserializedElement instanceof ByteString) { + deserializationFutures.add( + getContentsAndDeserialize( + (ByteString) deserializedElement, deserializationContext)); + } else { + deserializationFutures.add(Futures.immediateFuture(deserializedElement)); + } + } - CodedInputStream codedIn = CodedInputStream.newInstance(retrieved); - DeserializationContext newDeserializationContext = - deserializationContext.getNewMemoizingContext(); - - int numberOfElements = codedIn.readInt32(); - Object[] dereferencedContents = new Object[numberOfElements]; - for (int i = 0; i < numberOfElements; i++) { - Object deserializedElement = newDeserializationContext.deserialize(codedIn); - dereferencedContents[i] = - deserializedElement instanceof ByteString - ? getContentsAndDeserialize( - (ByteString) deserializedElement, deserializationContext) - : deserializedElement; - } + return Futures.whenAllComplete(deserializationFutures) + .call( + () -> { + Object[] deserializedContents = new Object[deserializationFutures.size()]; + for (int i = 0; i < deserializationFutures.size(); i++) { + deserializedContents[i] = Futures.getDone(deserializationFutures.get(i)); + } + return deserializedContents; + }, + executor); + }, + executor); FingerprintComputationResult fingerprintComputationResult = FingerprintComputationResult.create(fingerprint, Futures.immediateFuture(null)); - nestedSetCache.put(fingerprintComputationResult, dereferencedContents); - return dereferencedContents; + nestedSetCache.put(fingerprintComputationResult, result); + return result; } } diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java index 2d81b8ef66..26487b0915 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java @@ -42,7 +42,7 @@ public class NestedSetView<E> { /** Construct a view of a given NestedSet. */ public NestedSetView(NestedSet<E> set) { - this(set.rawChildren()); + this(set.getChildren()); } /** diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java index 090b8e33bb..c6e0e87133 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java @@ -59,7 +59,7 @@ public final class NestedSetVisitor<E> { // We can short-circuit empty nested set visitation here, avoiding load on the shared map // VisitedState#seenNodes. if (!nestedSet.isEmpty()) { - visitRaw(nestedSet.rawChildren()); + visitRaw(nestedSet.getChildren()); } } diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java index 5f81394129..f7bf43360b 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java @@ -14,6 +14,7 @@ package com.google.devtools.build.lib.skyframe.serialization; +import com.google.common.annotations.VisibleForTesting; import com.google.common.collect.ImmutableMap; import com.google.protobuf.ByteString; import com.google.protobuf.CodedInputStream; @@ -42,6 +43,16 @@ public class ObjectCodecs { this(codecRegistry, ImmutableMap.of()); } + @VisibleForTesting + public SerializationContext getSerializationContext() { + return serializationContext; + } + + @VisibleForTesting + public DeserializationContext getDeserializationContext() { + return deserializationContext; + } + public ByteString serialize(Object subject) throws SerializationException { return serializeToByteString(subject, this::serialize); } diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java index e9b1d647eb..9341084eec 100644 --- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java +++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java @@ -17,18 +17,24 @@ import static com.google.common.truth.Truth.assertThat; import com.google.common.collect.ImmutableMap; import com.google.common.util.concurrent.Futures; +import com.google.common.util.concurrent.ListenableFuture; +import com.google.common.util.concurrent.MoreExecutors; import com.google.common.util.concurrent.SettableFuture; +import com.google.devtools.build.lib.collect.nestedset.NestedSetStore.InMemoryNestedSetStorageEndpoint; +import com.google.devtools.build.lib.collect.nestedset.NestedSetStore.NestedSetCache; import com.google.devtools.build.lib.collect.nestedset.NestedSetStore.NestedSetStorageEndpoint; import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry; import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecs; import com.google.devtools.build.lib.skyframe.serialization.SerializationConstants; import com.google.devtools.build.lib.skyframe.serialization.SerializationResult; import com.google.protobuf.ByteString; +import java.nio.charset.Charset; import org.junit.After; import org.junit.Before; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.JUnit4; +import org.mockito.ArgumentCaptor; import org.mockito.Mockito; /** Tests for {@link NestedSet} serialization. */ @@ -49,7 +55,7 @@ public class NestedSetCodecTest { ObjectCodecs objectCodecs = new ObjectCodecs( AutoRegistry.get().getBuilder().setAllowDefaultCodec(true).build(), ImmutableMap.of()); - NestedSetCodecTestUtils.checkCodec(objectCodecs, false); + NestedSetCodecTestUtils.checkCodec(objectCodecs, false, false); } @Test @@ -62,7 +68,7 @@ public class NestedSetCodecTest { .add(new NestedSetCodecWithStore<>(NestedSetStore.inMemory())) .build(), ImmutableMap.of()); - NestedSetCodecTestUtils.checkCodec(objectCodecs, true); + NestedSetCodecTestUtils.checkCodec(objectCodecs, true, true); } /** @@ -166,7 +172,68 @@ public class NestedSetCodecTest { .setAllowDefaultCodec(true) .add(new NestedSetCodecWithStore<>(mockNestedSetStore)) .build()); - NestedSet<String> singletonNestedSet = new NestedSet<>(Order.STABLE_ORDER, "a"); + NestedSet<String> singletonNestedSet = + new NestedSetBuilder<String>(Order.STABLE_ORDER).add("a").build(); objectCodecs.serialize(singletonNestedSet); } + + @Test + public void testDeserializationInParallel() throws Exception { + NestedSetStorageEndpoint nestedSetStorageEndpoint = + Mockito.spy(new InMemoryNestedSetStorageEndpoint()); + NestedSetCache emptyNestedSetCache = Mockito.mock(NestedSetCache.class); + NestedSetStore nestedSetStore = + new NestedSetStore( + nestedSetStorageEndpoint, emptyNestedSetCache, MoreExecutors.directExecutor()); + + ObjectCodecs objectCodecs = + new ObjectCodecs( + AutoRegistry.get() + .getBuilder() + .setAllowDefaultCodec(true) + .add(new NestedSetCodecWithStore<>(nestedSetStore)) + .build()); + + NestedSet<String> subset1 = + new NestedSetBuilder<String>(Order.STABLE_ORDER).add("a").add("b").build(); + SettableFuture<byte[]> subset1Future = SettableFuture.create(); + NestedSet<String> subset2 = + new NestedSetBuilder<String>(Order.STABLE_ORDER).add("c").add("d").build(); + SettableFuture<byte[]> subset2Future = SettableFuture.create(); + NestedSet<String> set = + new NestedSetBuilder<String>(Order.STABLE_ORDER) + .addTransitive(subset1) + .addTransitive(subset2) + .build(); + + // We capture the arguments to #put() during serialization, so as to correctly mock results for + // #get() + ArgumentCaptor<ByteString> fingerprintCaptor = ArgumentCaptor.forClass(ByteString.class); + ByteString fingerprint = + nestedSetStore + .computeFingerprintAndStore( + (Object[]) set.getChildren(), objectCodecs.getSerializationContext()) + .fingerprint(); + Mockito.verify(nestedSetStorageEndpoint, Mockito.times(3)) + .put(fingerprintCaptor.capture(), Mockito.any()); + Mockito.doReturn(subset1Future) + .when(nestedSetStorageEndpoint) + .get(fingerprintCaptor.getAllValues().get(0)); + Mockito.doReturn(subset2Future) + .when(nestedSetStorageEndpoint) + .get(fingerprintCaptor.getAllValues().get(1)); + + ListenableFuture<Object[]> deserializationFuture = + nestedSetStore.getContentsAndDeserialize( + fingerprint, objectCodecs.getDeserializationContext()); + // At this point, we expect deserializationFuture to be waiting on both of the underlying + // fetches, which should have both been started. + assertThat(deserializationFuture.isDone()).isFalse(); + Mockito.verify(nestedSetStorageEndpoint, Mockito.times(3)).get(Mockito.any()); + + // Once the underlying fetches complete, we expect deserialization to complete. + subset1Future.set(ByteString.copyFrom("mock bytes", Charset.defaultCharset()).toByteArray()); + subset2Future.set(ByteString.copyFrom("mock bytes", Charset.defaultCharset()).toByteArray()); + assertThat(deserializationFuture.isDone()).isTrue(); + } } diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java index ff4515276b..97fbf8d336 100644 --- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java +++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java @@ -18,6 +18,8 @@ import static org.junit.Assert.fail; import com.google.common.collect.Lists; import com.google.common.testing.EqualsTester; +import com.google.common.util.concurrent.Futures; +import com.google.common.util.concurrent.ListenableFuture; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.JUnit4; @@ -164,40 +166,55 @@ public class NestedSetImplTest { public void shallowEquality() { // Used below to check that inner nested sets can be compared by reference equality. SetWrapper<Integer> myRef = nest(nest(flat(7, 8)), flat(9)); + // Used to check equality for deserializing nested sets + ListenableFuture<Object[]> contents = Futures.immediateFuture(new Object[] {"a", "b"}); + NestedSet<String> referenceNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, contents); + NestedSet<String> otherReferenceNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, contents); // Each "equality group" contains elements that are equal to one another // (according to equals() and hashCode()), yet distinct from all elements // of all other equality groups. new EqualsTester() - .addEqualityGroup(flat(), - flat(), - nest(flat())) // Empty set elision. - .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().build()) - .addEqualityGroup(flat(3), - flat(3), - flat(3, 3)) // Element de-duplication. - .addEqualityGroup(flat(4), - nest(flat(4))) // Automatic elision of one-element nested sets. - .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().add(4).build()) - .addEqualityGroup(nestedSetBuilder("4").build()) // Like flat("4"). - .addEqualityGroup(flat(3, 4), - flat(3, 4)) - // Make a couple sets deep enough that shallowEquals() fails. - // If this test case fails because you improve the representation, just delete it. - .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8)))) - .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8)))) - .addEqualityGroup(nest(myRef), - nest(myRef), - nest(myRef, myRef)) // Set de-duplication. - .addEqualityGroup(nest(3, myRef)) - .addEqualityGroup(nest(4, myRef)) - .testEquals(); + .addEqualityGroup(flat(), flat(), nest(flat())) // Empty set elision. + .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().build()) + .addEqualityGroup(flat(3), flat(3), flat(3, 3)) // Element de-duplication. + .addEqualityGroup(flat(4), nest(flat(4))) // Automatic elision of one-element nested sets. + .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().add(4).build()) + .addEqualityGroup(nestedSetBuilder("4").build()) // Like flat("4"). + .addEqualityGroup(flat(3, 4), flat(3, 4)) + // Make a couple sets deep enough that shallowEquals() fails. + // If this test case fails because you improve the representation, just delete it. + .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8)))) + .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8)))) + .addEqualityGroup(nest(myRef), nest(myRef), nest(myRef, myRef)) // Set de-duplication. + .addEqualityGroup(nest(3, myRef)) + .addEqualityGroup(nest(4, myRef)) + .addEqualityGroup( + new SetWrapper<>(referenceNestedSet), new SetWrapper<>(otherReferenceNestedSet)) + .testEquals(); // Some things that are not tested by the above: // - ordering among direct members // - ordering among transitive sets } + @Test + public void shallowInequality() { + assertThat(nestedSetBuilder("a").build().shallowEquals(null)).isFalse(); + Object[] contents = {"a", "b"}; + assertThat( + NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents)) + .shallowEquals(null)) + .isFalse(); + + // shallowEquals() should require reference equality for underlying futures + assertThat( + NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents)) + .shallowEquals( + NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents)))) + .isFalse(); + } + /** Checks that the builder always return a nested set with the correct order. */ @Test public void correctOrder() { |