diff options
17 files changed, 956 insertions, 834 deletions
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java index d2f92b864e..455ecda809 100644 --- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java +++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java @@ -15,14 +15,9 @@ package com.google.devtools.build.skyframe; import com.google.common.base.MoreObjects; import com.google.common.base.MoreObjects.ToStringHelper; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible; import com.google.devtools.build.lib.util.Preconditions; -import java.util.Collections; -import java.util.List; - /** * Data the NodeEntry uses to maintain its state before it is done building. It allows the {@link * NodeEntry} to keep the current state of the entry across invalidation and successive evaluations. @@ -60,6 +55,8 @@ import java.util.List; */ @ThreadCompatible class BuildingState { + protected static final int NOT_EVALUATING_SENTINEL = -1; + /** * The number of dependencies that are known to be done in a {@link NodeEntry} if it is already * evaluating, and a sentinel (-1) indicating that it has not yet started evaluating otherwise. @@ -81,45 +78,7 @@ class BuildingState { * thread is not working on the node anymore. Note that this requires that there is no code after * the loop in {@code ParallelEvaluator.Evaluate#run}. */ - int signaledDeps = -1; - - /** - * The set of reverse dependencies that are registered before the node has finished building. Upon - * building, these reverse deps will be signaled and then stored in the permanent {@link - * InMemoryNodeEntry#reverseDeps}. This field is marked volatile for subclasses that may change - * its value and require volatile reads. - */ - protected volatile Object reverseDepsToSignal = ImmutableList.of(); - private List<Object> reverseDepsDataToConsolidate = null; - - private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL = - new ReverseDepsUtilImpl<BuildingState>() { - @Override - void setReverseDepsObject(BuildingState container, Object object) { - container.reverseDepsToSignal = object; - } - - @Override - void setDataToConsolidate(BuildingState container, List<Object> dataToConsolidate) { - container.reverseDepsDataToConsolidate = dataToConsolidate; - } - - @Override - Object getReverseDepsObject(BuildingState container) { - return container.reverseDepsToSignal; - } - - @Override - List<Object> getDataToConsolidate(BuildingState container) { - return container.reverseDepsDataToConsolidate; - } - - @Override - public void consolidateReverseDeps(BuildingState container) { - // #consolidateReverseDeps is only supported for node entries, not building states. - throw new UnsupportedOperationException(); - } - }; + protected int signaledDeps = NOT_EVALUATING_SENTINEL; /** Returns whether all known children of this node have signaled that they are done. */ final boolean isReady(int numDirectDeps) { @@ -170,7 +129,7 @@ class BuildingState { } final boolean isEvaluating() { - return signaledDeps > -1; + return signaledDeps > NOT_EVALUATING_SENTINEL; } /** @@ -191,34 +150,10 @@ class BuildingState { void signalDepInternal(boolean childChanged, int numDirectDeps) {} - /** - * Returns reverse deps to signal that have been registered this build. - * - * @see NodeEntry#getReverseDeps() - */ - final ImmutableSet<SkyKey> getReverseDepsToSignal() { - return REVERSE_DEPS_UTIL.getReverseDeps(this); - } - - /** - * Adds a reverse dependency that should be notified when this entry is done. - * - * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey) - */ - final void addReverseDepToSignal(SkyKey newReverseDep) { - REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep)); - } - - /** @see NodeEntry#removeReverseDep(SkyKey) */ - final void removeReverseDepToSignal(SkyKey reverseDep) { - REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); - } - protected ToStringHelper getStringHelper() { return MoreObjects.toStringHelper(this) .add("hash", System.identityHashCode(this)) - .add("signaledDeps/evaluating state", signaledDeps) - .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this)); + .add("signaledDeps/evaluating state", signaledDeps); } @Override public final String toString() { diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java index f0003f7be2..e0b3579d09 100644 --- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java @@ -121,6 +121,11 @@ public abstract class DelegatingNodeEntry implements NodeEntry { } @Override + public Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() { + return getDelegate().getAllReverseDepsForNodeBeingDeleted(); + } + + @Override public void markRebuilding() { getDelegate().markRebuilding(); } @@ -171,8 +176,8 @@ public abstract class DelegatingNodeEntry implements NodeEntry { } @Override - public Iterable<SkyKey> getReverseDeps() throws InterruptedException { - return getDelegate().getReverseDeps(); + public Iterable<SkyKey> getReverseDepsForDoneEntry() throws InterruptedException { + return getDelegate().getReverseDepsForDoneEntry(); } @Override diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java index 76ebe75db5..217ebd9310 100644 --- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java @@ -128,7 +128,7 @@ public class DelegatingWalkableGraph implements WalkableGraph { Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size()); for (Entry<SkyKey, ? extends NodeEntry> entry : entries.entrySet()) { Preconditions.checkState(entry.getValue().isDone(), entry); - result.put(entry.getKey(), entry.getValue().getReverseDeps()); + result.put(entry.getKey(), entry.getValue().getReverseDepsForDoneEntry()); } return result; } diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java index fefee27763..7f8330195b 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java @@ -21,6 +21,9 @@ import com.google.common.collect.Iterables; import com.google.devtools.build.lib.util.GroupedList; import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import com.google.devtools.build.lib.util.Preconditions; +import com.google.devtools.build.skyframe.KeyToConsolidate.Op; +import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare; +import java.util.ArrayList; import java.util.Collection; import java.util.List; import java.util.Set; @@ -84,44 +87,35 @@ public class InMemoryNodeEntry implements NodeEntry { * * <p>In case of a single object we store the object unwrapped, without the list, for * memory-efficiency. + * + * <p>When an entry is being re-evaluated, this object stores the reverse deps from the previous + * evaluation. At the end of evaluation, the changed reverse dep operations from {@link + * #reverseDepsDataToConsolidate} are merged in here. */ protected Object reverseDeps = ImmutableList.of(); /** - * When reverse deps are removed, checked for presence, or possibly added, we store them in this - * object instead of directly doing the operation. That is because removals/checks in reverseDeps - * are O(N). Originally reverseDeps was a HashSet, but because of memory consumption we switched - * to a list. + * This list stores objects returned by {@link KeyToConsolidate#create}. Morally they are {@link + * KeyToConsolidate} objects, but since some operations are stored bare, we can only declare that + * this list holds {@link Object} references. Created lazily to save memory. + * + * <p>This list serves double duty. For a done node, when a reverse dep is removed, checked for + * presence, or possibly added, we store the mutation in this object instead of immediately doing + * the operation. That is because removals/checks in reverseDeps are O(N). Originally reverseDeps + * was a HashSet, but because of memory consumption we switched to a list. * - * <p>Internally, ReverseDepsUtilImpl consolidates this data periodically, and when the set of - * reverse deps is requested. While this operation is not free, it can be done more effectively + * <p>Internally, {@link ReverseDepsUtility} consolidates this data periodically, and when the set + * of reverse deps is requested. While this operation is not free, it can be done more effectively * than trying to remove/check each dirty reverse dependency individually (O(N) each time). + * + * <p>When the node entry is evaluating, this list serves to declare the reverse dep operations + * that have taken place on it during this evaluation. When evaluation finishes, this list will be + * merged into the existing reverse deps if any, but furthermore, this list will also be used to + * calculate the set of reverse deps to signal when this entry finishes evaluation. That is done + * by {@link ReverseDepsUtility#consolidateDataAndReturnNewElements}. */ private List<Object> reverseDepsDataToConsolidate = null; - private static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL = - new ReverseDepsUtilImpl<InMemoryNodeEntry>() { - @Override - void setReverseDepsObject(InMemoryNodeEntry container, Object object) { - container.reverseDeps = object; - } - - @Override - void setDataToConsolidate(InMemoryNodeEntry container, List<Object> dataToConsolidate) { - container.reverseDepsDataToConsolidate = dataToConsolidate; - } - - @Override - Object getReverseDepsObject(InMemoryNodeEntry container) { - return container.reverseDeps; - } - - @Override - List<Object> getDataToConsolidate(InMemoryNodeEntry container) { - return container.reverseDepsDataToConsolidate; - } - }; - /** * The transient state of this entry, after it has been created but before it is done. It allows * us to keep the current state of the entry across invalidation and successive evaluations. @@ -209,11 +203,8 @@ public class InMemoryNodeEntry implements NodeEntry { } protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() { - // Get reverse deps that need to be signaled. - ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal(); - getReverseDepsUtil().addReverseDeps(this, reverseDepsToSignal); - // Force consistency check and consolidate rdeps changes. - getReverseDepsUtil().consolidateReverseDeps(this); + Set<SkyKey> reverseDepsToSignal = + ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare()); this.directDeps = getTemporaryDirectDeps().compress(); markDone(); @@ -228,7 +219,7 @@ public class InMemoryNodeEntry implements NodeEntry { @Override public synchronized Set<SkyKey> getInProgressReverseDeps() { Preconditions.checkState(!isDone(), this); - return buildingState.getReverseDepsToSignal(); + return ReverseDepsUtility.returnNewElements(this, getOpToStoreBare()); } @Override @@ -256,23 +247,15 @@ public class InMemoryNodeEntry implements NodeEntry { return setStateFinishedAndReturnReverseDepsToSignal(); } - protected ReverseDepsUtil<InMemoryNodeEntry> getReverseDepsUtil() { - return REVERSE_DEPS_UTIL; - } - @Override public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) { if (reverseDep != null) { - if (keepEdges()) { - getReverseDepsUtil().maybeCheckReverseDepNotPresent(this, reverseDep); - } if (isDone()) { if (keepEdges()) { - getReverseDepsUtil().addReverseDeps(this, ImmutableList.of(reverseDep)); + ReverseDepsUtility.addReverseDeps(this, ImmutableList.of(reverseDep)); } } else { - // Parent should never register itself twice in the same build. - buildingState.addReverseDepToSignal(reverseDep); + appendToReverseDepOperations(reverseDep, Op.ADD); } } if (isDone()) { @@ -282,15 +265,52 @@ public class InMemoryNodeEntry implements NodeEntry { : DependencyState.ALREADY_EVALUATING; } + /** Sets {@link #reverseDeps}. Does not alter {@link #reverseDepsDataToConsolidate}. */ + synchronized void setSingleReverseDepForReverseDepsUtil(SkyKey reverseDep) { + this.reverseDeps = reverseDep; + } + + /** Sets {@link #reverseDeps}. Does not alter {@link #reverseDepsDataToConsolidate}. */ + synchronized void setReverseDepsForReverseDepsUtil(List<SkyKey> reverseDeps) { + this.reverseDeps = reverseDeps; + } + + /** Sets {@link #reverseDepsDataToConsolidate}. Does not alter {@link #reverseDeps}. */ + synchronized void setReverseDepsDataToConsolidateForReverseDepsUtil( + List<Object> dataToConsolidate) { + this.reverseDepsDataToConsolidate = dataToConsolidate; + } + + synchronized Object getReverseDepsRawForReverseDepsUtil() { + return this.reverseDeps; + } + + synchronized List<Object> getReverseDepsDataToConsolidateForReverseDepsUtil() { + return this.reverseDepsDataToConsolidate; + } + + private synchronized void appendToReverseDepOperations(SkyKey reverseDep, Op op) { + Preconditions.checkState(!isDone(), "Don't append to done %s %s %s", this, reverseDep, op); + if (reverseDepsDataToConsolidate == null) { + reverseDepsDataToConsolidate = new ArrayList<>(); + } + Preconditions.checkState( + isDirty() || op != Op.CHECK, "Not dirty check %s %s", this, reverseDep); + reverseDepsDataToConsolidate.add(KeyToConsolidate.create(reverseDep, op, getOpToStoreBare())); + } + + private OpToStoreBare getOpToStoreBare() { + return isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD; + } + @Override public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) { Preconditions.checkNotNull(reverseDep, this); Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this); - if (!isDone()) { - getReverseDepsUtil().removeReverseDep(this, reverseDep); - buildingState.addReverseDepToSignal(reverseDep); + if (isDone()) { + ReverseDepsUtility.checkReverseDep(this, reverseDep); } else { - getReverseDepsUtil().checkReverseDep(this, reverseDep); + appendToReverseDepOperations(reverseDep, Op.CHECK); } return addReverseDepAndCheckIfDone(null); } @@ -300,23 +320,36 @@ public class InMemoryNodeEntry implements NodeEntry { if (!keepEdges()) { return; } - getReverseDepsUtil().removeReverseDep(this, reverseDep); + if (isDone()) { + ReverseDepsUtility.removeReverseDep(this, reverseDep); + } else { + // Removing a reverse dep from an in-flight node is rare -- it should only happen when this + // node is about to be cleaned from the graph. + appendToReverseDepOperations(reverseDep, Op.REMOVE_OLD); + } } @Override public synchronized void removeInProgressReverseDep(SkyKey reverseDep) { - buildingState.removeReverseDepToSignal(reverseDep); + appendToReverseDepOperations(reverseDep, Op.REMOVE); } @Override - public synchronized Iterable<SkyKey> getReverseDeps() { + public synchronized Iterable<SkyKey> getReverseDepsForDoneEntry() { assertKeepEdges(); - Iterable<SkyKey> reverseDeps = getReverseDepsUtil().getReverseDeps(this); - if (isDone()) { - return reverseDeps; - } else { - return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal()); + Preconditions.checkState(isDone(), "Called on not done %s", this); + return ReverseDepsUtility.getReverseDeps(this); + } + + @Override + public synchronized Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() { + assertKeepEdges(); + if (!isDone()) { + // This consolidation loses information about pending reverse deps to signal, but that is + // unimportant since this node is being deleted. + ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare()); } + return ReverseDepsUtility.getReverseDeps(this); } @Override @@ -355,7 +388,7 @@ public class InMemoryNodeEntry implements NodeEntry { DirtyBuildingState.create(isChanged, GroupedList.<SkyKey>create(directDeps), value); value = null; directDeps = null; - return new MarkedDirtyResult(getReverseDepsUtil().getReverseDeps(this)); + return new MarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this)); } // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty // thread may have lost the race, but it is the caller's responsibility not to try to mark @@ -499,7 +532,7 @@ public class InMemoryNodeEntry implements NodeEntry { .add("lastChangedVersion", lastChangedVersion) .add("lastEvaluatedVersion", lastEvaluatedVersion) .add("directDeps", isDone() ? GroupedList.create(directDeps) : directDeps) - .add("reverseDeps", getReverseDepsUtil().toString(this)) + .add("reverseDeps", ReverseDepsUtility.toString(this)) .add("buildingState", buildingState) .toString(); } @@ -516,7 +549,7 @@ public class InMemoryNodeEntry implements NodeEntry { nodeEntry.value = value; nodeEntry.lastChangedVersion = this.lastChangedVersion; nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion; - getReverseDepsUtil().addReverseDeps(nodeEntry, getReverseDepsUtil().getReverseDeps(this)); + ReverseDepsUtility.addReverseDeps(nodeEntry, ReverseDepsUtility.getReverseDeps(this)); nodeEntry.directDeps = directDeps; nodeEntry.buildingState = null; return nodeEntry; diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java index 577639a618..d7bb2d2cab 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java +++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java @@ -271,16 +271,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> { if (traverseGraph) { // Propagate deletion upwards. - try { - visit(entry.getReverseDeps(), InvalidationType.DELETED); - } catch (InterruptedException e) { - throw new IllegalStateException( - "Deletion cannot happen on a graph that may have blocking operations: " - + key - + ", " - + entry, - e); - } + visit(entry.getAllReverseDepsForNodeBeingDeleted(), InvalidationType.DELETED); // Unregister this node as an rdep from its direct deps, since reverse dep // edges cannot point to non-existent nodes. To know whether the child has this @@ -339,8 +330,8 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> { } // Allow custom key-specific logic to update dirtiness status. - progressReceiver.invalidated(key, - EvaluationProgressReceiver.InvalidationState.DELETED); + progressReceiver.invalidated( + key, EvaluationProgressReceiver.InvalidationState.DELETED); // Actually remove the node. graph.remove(key); diff --git a/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java b/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java new file mode 100644 index 0000000000..2b2572c727 --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java @@ -0,0 +1,206 @@ +// Copyright 2017 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.skyframe; + +import com.google.common.base.MoreObjects; +import com.google.common.collect.Interner; +import com.google.devtools.build.lib.concurrent.BlazeInterners; +import com.google.devtools.build.lib.util.Preconditions; + +/** + * Container for a pending operation on the reverse deps set. We use subclasses to save 8 bytes of + * memory instead of keeping a field in this class, and we store {@link Op#CHECK} or {@link Op#ADD} + * operations as the bare {@link SkyKey} in order to save the wrapper object in that case. + * + * <p>When a list of {@link KeyToConsolidate} operations is processed, each operation is performed + * in order. Operations on a done or freshly evaluating node entry are straightforward: they apply + * to the entry's reverse deps. Operations on a re-evaluating node entry have a double meaning: they + * will eventually be applied to the node entry's existing reverse deps, just as for a done node + * entry, but they are also used to track the entries that declared/redeclared a reverse dep on this + * entry during this evaluation (and will thus need to be signaled when this entry finishes + * evaluating). + */ +abstract class KeyToConsolidate { + enum Op { + /** + * Assert that the reverse dep is already present in the set of reverse deps. If the entry is + * re-evaluating, add this reverse dep to the set of reverse deps to signal when this entry is + * done. + */ + CHECK, + /** + * Add the reverse dep to the set of reverse deps and assert it was not already present. If the + * entry is re-evaluating, add this reverse dep to the set of reverse deps to signal when this + * entry is done. + */ + ADD, + /** + * Remove the reverse dep from the set of reverse deps and assert it was present. If the entry + * is re-evaluating, also remove the reverse dep from the set of reverse deps to signal when + * this entry is done, and assert that it was present. + */ + REMOVE, + /** + * The same as {@link #REMOVE}, except that if the entry is re-evaluating, we assert that the + * set of reverse deps to signal did <i>not</i> contain this reverse dep. + */ + REMOVE_OLD + } + + enum OpToStoreBare { + ADD(Op.ADD), + CHECK(Op.CHECK); + + private final Op op; + + OpToStoreBare(Op op) { + this.op = op; + } + } + + private static final Interner<KeyToConsolidate> consolidateInterner = + BlazeInterners.newWeakInterner(); + + private final SkyKey key; + + /** Do not call directly -- use the {@link #create} static method instead. */ + private KeyToConsolidate(SkyKey key) { + this.key = key; + } + + @Override + public String toString() { + return MoreObjects.toStringHelper(this).add("key", key).toString(); + } + + /** + * Gets which operation was delayed for the given object, created using {@link #create}. The same + * {@code opToStoreBare} passed in to {@link #create} should be passed in here. + */ + static Op op(Object obj, OpToStoreBare opToStoreBare) { + if (obj instanceof SkyKey) { + return opToStoreBare.op; + } + if (obj instanceof KeyToAdd) { + return Op.ADD; + } + if (obj instanceof KeyToCheck) { + return Op.CHECK; + } + if (obj instanceof KeyToRemove) { + return Op.REMOVE; + } + if (obj instanceof KeyToRemoveOld) { + return Op.REMOVE_OLD; + } + throw new IllegalStateException( + "Unknown object type: " + obj + ", " + opToStoreBare + ", " + obj.getClass()); + } + + /** Gets the key whose operation was delayed for the given object. */ + static SkyKey key(Object obj) { + if (obj instanceof SkyKey) { + return (SkyKey) obj; + } + Preconditions.checkState(obj instanceof KeyToConsolidate, obj); + return ((KeyToConsolidate) obj).key; + } + + /** + * Creates a new operation, encoding the operation {@code op} with reverse dep {@code key}. To + * save memory, the caller should specify the most common operation expected as {@code + * opToStoreBare}. That operation will be encoded as the raw {@code key}, saving the memory of an + * object wrapper. Whatever {@code opToStoreBare} is set to here, the same value must be passed in + * to {@link #op} when decoding an operation emitted by this method. + */ + static Object create(SkyKey key, Op op, OpToStoreBare opToStoreBare) { + if (op == opToStoreBare.op) { + return key; + } + switch (op) { + case CHECK: + return consolidateInterner.intern(new KeyToCheck(key)); + case REMOVE: + return consolidateInterner.intern(new KeyToRemove(key)); + case REMOVE_OLD: + return consolidateInterner.intern(new KeyToRemoveOld(key)); + case ADD: + return consolidateInterner.intern(new KeyToAdd(key)); + default: + throw new IllegalStateException(op + ", " + key); + } + } + + @Override + public boolean equals(Object obj) { + if (obj == null) { + return false; + } + return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key); + } + + protected int keyHashCode() { + return key.hashCode(); + } + + @Override + public int hashCode() { + // Overridden in subclasses. + throw new UnsupportedOperationException(key.toString()); + } + + private static final class KeyToAdd extends KeyToConsolidate { + KeyToAdd(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return keyHashCode(); + } + } + + private static final class KeyToCheck extends KeyToConsolidate { + KeyToCheck(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return 31 + 43 * keyHashCode(); + } + } + + private static final class KeyToRemove extends KeyToConsolidate { + KeyToRemove(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return 42 + 37 * keyHashCode(); + } + } + + private static final class KeyToRemoveOld extends KeyToConsolidate { + KeyToRemoveOld(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return 93 + 37 * keyHashCode(); + } + } +} diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java index d7f7fcfc89..57334d6384 100644 --- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java @@ -104,7 +104,8 @@ public interface NodeEntry extends ThinNodeEntry { * Removes a reverse dependency. * * <p>May only be called if this entry is not done (i.e. {@link #isDone} is false) and {@param - * reverseDep} is present in {@link #getReverseDeps} + * reverseDep} was added/confirmed during this evaluation (by {@link #addReverseDepAndCheckIfDone} + * or {@link #checkIfDoneForDirtyReverseDep}). */ @ThreadSafe void removeInProgressReverseDep(SkyKey reverseDep); @@ -112,9 +113,11 @@ public interface NodeEntry extends ThinNodeEntry { /** * Returns a copy of the set of reverse dependencies. Note that this introduces a potential * check-then-act race; {@link #removeReverseDep} may fail for a key that is returned here. + * + * <p>May only be called on a done node entry. */ @ThreadSafe - Iterable<SkyKey> getReverseDeps() throws InterruptedException; + Iterable<SkyKey> getReverseDepsForDoneEntry() throws InterruptedException; /** * Returns raw {@link SkyValue} stored in this entry, which may include metadata associated with @@ -199,6 +202,8 @@ public interface NodeEntry extends ThinNodeEntry { @ThreadSafe DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) throws InterruptedException; + Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted(); + /** * Tell this node that one of its dependencies is now done. Callers must check the return value, * and if true, they must re-schedule this node for evaluation. Equivalent to diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java index e45f0a8927..19b18cb8cf 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java @@ -870,9 +870,10 @@ public final class ParallelEvaluator implements Evaluator { NodeEntry errorEntry = Preconditions.checkNotNull( graph.get(null, Reason.ERROR_BUBBLING, errorKey), errorKey); - Iterable<SkyKey> reverseDeps = errorEntry.isDone() - ? errorEntry.getReverseDeps() - : errorEntry.getInProgressReverseDeps(); + Iterable<SkyKey> reverseDeps = + errorEntry.isDone() + ? errorEntry.getReverseDepsForDoneEntry() + : errorEntry.getInProgressReverseDeps(); // We should break from loop only when node doesn't have any parents. if (Iterables.isEmpty(reverseDeps)) { Preconditions.checkState(rootValues.contains(errorKey), diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java deleted file mode 100644 index 52ad31229c..0000000000 --- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java +++ /dev/null @@ -1,47 +0,0 @@ -// Copyright 2015 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.skyframe; - -import com.google.common.collect.ImmutableSet; - -import java.util.Collection; - -/** - * A utility interface for dealing with reverse deps in NodeEntry and BuildingState implementations. - * - * <p>The reason for this interface is to abstract out dealing with reverse deps, which is subject - * to various non-trivial and fairly ugly memory/performance optimizations. - * - * <p>This interface is public only for the benefit of alternative graph implementations outside of - * the package. - */ -public interface ReverseDepsUtil<T> { - void addReverseDeps(T container, Collection<SkyKey> reverseDeps); - /** - * Checks that the reverse dependency is not already present. Implementations may choose not to - * perform this check, or only to do it if reverseDeps is small, so that it does not impact - * performance. - */ - void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep); - - void checkReverseDep(T container, SkyKey reverseDep); - - void removeReverseDep(T container, SkyKey reverseDep); - - void consolidateReverseDeps(T container); - - ImmutableSet<SkyKey> getReverseDeps(T container); - - String toString(T container); -} diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java deleted file mode 100644 index 6f29e39b59..0000000000 --- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java +++ /dev/null @@ -1,413 +0,0 @@ -// Copyright 2014 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.skyframe; - -import com.google.common.base.MoreObjects; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Interner; -import com.google.common.collect.Iterables; -import com.google.common.collect.Lists; -import com.google.devtools.build.lib.collect.CompactHashSet; -import com.google.devtools.build.lib.concurrent.BlazeInterners; -import com.google.devtools.build.lib.util.Preconditions; -import java.util.ArrayList; -import java.util.Collection; -import java.util.HashSet; -import java.util.List; -import java.util.Set; -import javax.annotation.Nullable; - -/** - * A utility class that allows us to keep the reverse dependencies as an array list instead of a - * set. This is more memory-efficient. At the same time it allows us to group the removals and - * uniqueness checks so that it also performs well. - * - * <p>The reason for making this a separate class is to share non-trivial code between BuildingState - * and NodeEntry. We could simply make those two classes extend this class instead, but we would be - * less memory-efficient since object memory alignment does not cross classes (you would have two - * memory alignments, one for the base class and one for the extended one). - * - */ -public abstract class ReverseDepsUtilImpl<T> implements ReverseDepsUtil<T> { - - static final int MAYBE_CHECK_THRESHOLD = 10; - - private static final Interner<KeyToConsolidate> consolidateInterner = - BlazeInterners.newWeakInterner(); - - abstract void setReverseDepsObject(T container, Object object); - - abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate); - - abstract Object getReverseDepsObject(T container); - - abstract List<Object> getDataToConsolidate(T container); - - private enum ConsolidateOp { - CHECK, - ADD, - REMOVE - } - - /** - * Opaque container for a pending operation on the reverse deps set. We use subclasses to save - * 8 bytes of memory instead of keeping a field in this class, and we store - * {@link ConsolidateOp#CHECK} operations as the bare {@link SkyKey} in order to save the wrapper - * object in that case. - */ - private abstract static class KeyToConsolidate { - // Do not access directly -- use the {@link #key} static accessor instead. - protected final SkyKey key; - - /** Do not call directly -- use the {@link #create} static method instead. */ - private KeyToConsolidate(SkyKey key) { - this.key = key; - } - - @Override - public String toString() { - return MoreObjects.toStringHelper(this).add("key", key).toString(); - } - - /** Gets which operation was delayed for the given object. */ - static ConsolidateOp op(Object obj) { - if (obj instanceof SkyKey) { - return ConsolidateOp.CHECK; - } - if (obj instanceof KeyToRemove) { - return ConsolidateOp.REMOVE; - } - Preconditions.checkState(obj instanceof KeyToAdd, obj); - return ConsolidateOp.ADD; - } - - /** Gets the key whose operation was delayed for the given object. */ - static SkyKey key(Object obj) { - if (obj instanceof SkyKey) { - return (SkyKey) obj; - } - Preconditions.checkState(obj instanceof KeyToConsolidate, obj); - return ((KeyToConsolidate) obj).key; - } - - static Object create(SkyKey key, ConsolidateOp op) { - switch (op) { - case CHECK: - return key; - case REMOVE: - return consolidateInterner.intern(new KeyToRemove(key)); - case ADD: - return consolidateInterner.intern(new KeyToAdd(key)); - default: - throw new IllegalStateException(op + ", " + key); - } - } - - @Override - public boolean equals(Object obj) { - if (obj == null) { - return false; - } - return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key); - } - - @Override - public int hashCode() { - // Overridden in subclasses. - throw new UnsupportedOperationException(key.toString()); - } - } - - private static final class KeyToAdd extends KeyToConsolidate { - KeyToAdd(SkyKey key) { - super(key); - } - - @Override - public int hashCode() { - return key.hashCode(); - } - } - - private static final class KeyToRemove extends KeyToConsolidate { - KeyToRemove(SkyKey key) { - super(key); - } - - @Override - public int hashCode() { - return 42 + 37 * key.hashCode(); - } - } - - private void maybeDelayReverseDepOp(T container, Iterable<SkyKey> reverseDeps, ConsolidateOp op) { - List<Object> consolidations = getDataToConsolidate(container); - int currentReverseDepSize = getCurrentReverseDepSize(container); - if (consolidations == null) { - consolidations = new ArrayList<>(currentReverseDepSize); - setDataToConsolidate(container, consolidations); - } - for (SkyKey reverseDep : reverseDeps) { - consolidations.add(KeyToConsolidate.create(reverseDep, op)); - } - // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized. - if (consolidations.size() == currentReverseDepSize) { - consolidateData(container); - } - } - - private boolean isSingleReverseDep(T container) { - return !(getReverseDepsObject(container) instanceof List); - } - - /** - * We only check if reverse deps is small and there are no delayed data to consolidate, since - * then presence or absence would not be known. - */ - @Override - public void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) { - if (getDataToConsolidate(container) != null) { - return; - } - if (isSingleReverseDep(container)) { - Preconditions.checkState( - !getReverseDepsObject(container).equals(reverseDep), - "Reverse dep %s already present in %s", - reverseDep, - container); - return; - } - @SuppressWarnings("unchecked") - List<SkyKey> asList = (List<SkyKey>) getReverseDepsObject(container); - if (asList.size() < MAYBE_CHECK_THRESHOLD) { - Preconditions.checkState( - !asList.contains(reverseDep), - "Reverse dep %s already present in %s for %s", - reverseDep, - asList, - container); - } - } - - private int getCurrentReverseDepSize(T container) { - return isSingleReverseDep(container) - ? 1 - : ((List<SkyKey>) getReverseDepsObject(container)).size(); - } - - /** - * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are - * dominant over the number of nodes. - * - * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the - * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because - * we also have a decent number of nodes for which the reverseDeps are huge (for example almost - * everything depends on BuildInfo node). - * - * <p>We also optimize for the case where we have only one dependency. In that case we keep the - * object directly instead of a wrapper list. - */ - @SuppressWarnings("unchecked") - public void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) { - if (newReverseDeps.isEmpty()) { - return; - } - List<Object> dataToConsolidate = getDataToConsolidate(container); - if (dataToConsolidate != null) { - maybeDelayReverseDepOp(container, newReverseDeps, ConsolidateOp.ADD); - return; - } - Object reverseDeps = getReverseDepsObject(container); - int reverseDepsSize = isSingleReverseDep(container) ? 1 : ((List<SkyKey>) reverseDeps).size(); - int newSize = reverseDepsSize + newReverseDeps.size(); - if (newSize == 1) { - overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(newReverseDeps)); - } else if (reverseDepsSize == 0) { - overwriteReverseDepsList(container, Lists.newArrayList(newReverseDeps)); - } else if (reverseDepsSize == 1) { - List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize); - newList.add((SkyKey) reverseDeps); - newList.addAll(newReverseDeps); - overwriteReverseDepsList(container, newList); - } else { - ((List<SkyKey>) reverseDeps).addAll(newReverseDeps); - } - } - - @Override - public void checkReverseDep(T container, SkyKey reverseDep) { - maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK); - } - - /** - * See {@code addReverseDeps} method. - */ - @Override - public void removeReverseDep(T container, SkyKey reverseDep) { - maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE); - } - - @Override - public ImmutableSet<SkyKey> getReverseDeps(T container) { - consolidateData(container); - - // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side - // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted, - // and we can't handle that right now. - if (isSingleReverseDep(container)) { - return ImmutableSet.of((SkyKey) getReverseDepsObject(container)); - } else { - @SuppressWarnings("unchecked") - List<SkyKey> reverseDeps = (List<SkyKey>) getReverseDepsObject(container); - ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps); - Preconditions.checkState( - set.size() == reverseDeps.size(), - "Duplicate reverse deps present in %s: %s. %s", - this, - reverseDeps, - container); - return set; - } - } - - @Override - public void consolidateReverseDeps(T container) { - consolidateData(container); - } - - private void consolidateData(T container) { - List<Object> dataToConsolidate = getDataToConsolidate(container); - if (dataToConsolidate == null) { - return; - } - setDataToConsolidate(container, null); - Object reverseDeps = getReverseDepsObject(container); - if (isSingleReverseDep(container)) { - Preconditions.checkState( - dataToConsolidate.size() == 1, - "dataToConsolidate not size 1 even though only one rdep: %s %s %s", - dataToConsolidate, - reverseDeps, - container); - Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate); - SkyKey key = KeyToConsolidate.key(keyToConsolidate); - switch (KeyToConsolidate.op(keyToConsolidate)) { - case REMOVE: - overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); - // Fall through to check. - case CHECK: - Preconditions.checkState( - key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, container); - break; - case ADD: - throw new IllegalStateException( - "Shouldn't delay add if only one element: " - + keyToConsolidate - + ", " - + reverseDeps - + ", " - + container); - default: - throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + container); - } - return; - } - List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; - Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList); - - if (reverseDepsAsSet.size() != reverseDepsAsList.size()) { - // We're about to crash. Try to print an informative error message. - Set<SkyKey> seen = new HashSet<>(); - List<SkyKey> duplicates = new ArrayList<>(); - for (SkyKey key : reverseDepsAsList) { - if (!seen.add(key)) { - duplicates.add(key); - } - } - throw new IllegalStateException( - (reverseDepsAsList.size() - reverseDepsAsSet.size()) - + " duplicates: " - + duplicates - + " for " - + container); - } - for (Object keyToConsolidate : dataToConsolidate) { - SkyKey key = KeyToConsolidate.key(keyToConsolidate); - switch (KeyToConsolidate.op(keyToConsolidate)) { - case CHECK: - Preconditions.checkState( - reverseDepsAsSet.contains(key), - "%s %s %s %s", - keyToConsolidate, - reverseDepsAsSet, - dataToConsolidate, - container); - break; - case REMOVE: - Preconditions.checkState( - reverseDepsAsSet.remove(key), - "%s %s %s %s", - keyToConsolidate, - reverseDeps, - dataToConsolidate, - container); - break; - case ADD: - Preconditions.checkState( - reverseDepsAsSet.add(key), - "%s %s %s %s", - keyToConsolidate, - reverseDeps, - dataToConsolidate, - container); - break; - default: - throw new IllegalStateException( - keyToConsolidate - + ", " - + reverseDepsAsSet - + ", " - + dataToConsolidate - + ", " - + container); - } - } - - if (reverseDepsAsSet.isEmpty()) { - overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); - } else if (reverseDepsAsSet.size() == 1) { - overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet)); - } else { - overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet)); - } - } - - @Override - public String toString(T container) { - return MoreObjects.toStringHelper("ReverseDeps") - .add("reverseDeps", getReverseDepsObject(container)) - .add("singleReverseDep", isSingleReverseDep(container)) - .add("dataToConsolidate", getDataToConsolidate(container)) - .toString(); - } - - private void overwriteReverseDepsWithObject(T container, SkyKey newObject) { - setReverseDepsObject(container, newObject); - } - - private void overwriteReverseDepsList(T container, List<SkyKey> list) { - setReverseDepsObject(container, list); - } -} diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java new file mode 100644 index 0000000000..0f93fa6a21 --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java @@ -0,0 +1,438 @@ +// Copyright 2014 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.skyframe; + +import com.google.common.base.MoreObjects; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; +import com.google.devtools.build.lib.collect.CompactHashSet; +import com.google.devtools.build.lib.util.Preconditions; +import com.google.devtools.build.skyframe.KeyToConsolidate.Op; +import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * A utility class that allows us to keep the reverse dependencies as an array list instead of a + * set. This is more memory-efficient. At the same time it allows us to group the removals and + * uniqueness checks so that it also performs well. + * + * <p>We could simply make {@link InMemoryNodeEntry} extend this class, but we would be less + * memory-efficient since object memory alignment does not cross classes (you would have two memory + * alignments, one for the base class and one for the extended one). We could also merge this + * functionality directly into {@link InMemoryNodeEntry} at the cost of increasing its size and + * complexity even more. + * + * <p>The operations {@link #addReverseDeps}, {@link #checkReverseDep}, and {@link + * #removeReverseDep} here are optimized for a done entry. Done entries rarely have rdeps added and + * removed, but do have {@link Op#CHECK} operations performed frequently. As well, done node entries + * may never have their data forcibly consolidated, since their reverse deps will only be retrieved + * as a whole if they are marked dirty. Thus, we consolidate periodically. + * + * <p>{@link InMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty or initally + * evaluating node itself, using similar logic tuned to those cases, and calls into {@link + * #consolidateDataAndReturnNewElements(InMemoryNodeEntry, OpToStoreBare)} when transitioning to + * done. + */ +abstract class ReverseDepsUtility { + private ReverseDepsUtility() {} + + static final int MAYBE_CHECK_THRESHOLD = 10; + + /** + * We can store one type of operation bare in order to save memory. For done nodes, most + * operations are CHECKS. + */ + private static final OpToStoreBare DEFAULT_OP_TO_STORE_BARE = OpToStoreBare.CHECK; + + private static void maybeDelayReverseDepOp( + InMemoryNodeEntry entry, Iterable<SkyKey> reverseDeps, Op op) { + List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil(); + int currentReverseDepSize = getCurrentReverseDepSize(entry); + if (consolidations == null) { + consolidations = new ArrayList<>(currentReverseDepSize); + entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations); + } + for (SkyKey reverseDep : reverseDeps) { + consolidations.add(KeyToConsolidate.create(reverseDep, op, DEFAULT_OP_TO_STORE_BARE)); + } + // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized. + if (consolidations.size() >= currentReverseDepSize) { + consolidateData(entry); + } + } + + private static boolean isSingleReverseDep(InMemoryNodeEntry entry) { + return !(entry.getReverseDepsRawForReverseDepsUtil() instanceof List); + } + + /** + * We only check if reverse deps is small and there are no delayed data to consolidate, since then + * presence or absence would not be known. + */ + static void maybeCheckReverseDepNotPresent(InMemoryNodeEntry entry, SkyKey reverseDep) { + if (entry.getReverseDepsDataToConsolidateForReverseDepsUtil() != null) { + return; + } + if (isSingleReverseDep(entry)) { + Preconditions.checkState( + !entry.getReverseDepsRawForReverseDepsUtil().equals(reverseDep), + "Reverse dep %s already present in %s", + reverseDep, + entry); + return; + } + @SuppressWarnings("unchecked") + List<SkyKey> asList = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil(); + if (asList.size() < MAYBE_CHECK_THRESHOLD) { + Preconditions.checkState( + !asList.contains(reverseDep), + "Reverse dep %s already present in %s for %s", + reverseDep, + asList, + entry); + } + } + + @SuppressWarnings("unchecked") // Cast to list. + private static int getCurrentReverseDepSize(InMemoryNodeEntry entry) { + return isSingleReverseDep(entry) + ? 1 + : ((List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil()).size(); + } + + /** + * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are + * dominant over the number of nodes. + * + * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the + * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because + * we also have a decent number of nodes for which the reverseDeps are huge (for example almost + * everything depends on BuildInfo node). + * + * <p>We also optimize for the case where we have only one dependency. In that case we keep the + * object directly instead of a wrapper list. + */ + @SuppressWarnings("unchecked") // Cast to SkyKey and List. + static void addReverseDeps(InMemoryNodeEntry entry, Collection<SkyKey> newReverseDeps) { + if (newReverseDeps.isEmpty()) { + return; + } + List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil(); + if (dataToConsolidate != null) { + maybeDelayReverseDepOp(entry, newReverseDeps, Op.ADD); + return; + } + Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil(); + int reverseDepsSize = isSingleReverseDep(entry) ? 1 : ((List<SkyKey>) reverseDeps).size(); + int newSize = reverseDepsSize + newReverseDeps.size(); + if (newSize == 1) { + entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(newReverseDeps)); + } else if (reverseDepsSize == 0) { + entry.setReverseDepsForReverseDepsUtil(Lists.newArrayList(newReverseDeps)); + } else if (reverseDepsSize == 1) { + List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize); + newList.add((SkyKey) reverseDeps); + newList.addAll(newReverseDeps); + entry.setReverseDepsForReverseDepsUtil(newList); + } else { + ((List<SkyKey>) reverseDeps).addAll(newReverseDeps); + } + } + + static void checkReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) { + maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.CHECK); + } + + /** See {@code addReverseDeps} method. */ + static void removeReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) { + maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.REMOVE); + } + + static ImmutableSet<SkyKey> getReverseDeps(InMemoryNodeEntry entry) { + consolidateData(entry); + + // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side + // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted, + // and we can't handle that right now. + if (isSingleReverseDep(entry)) { + return ImmutableSet.of((SkyKey) entry.getReverseDepsRawForReverseDepsUtil()); + } else { + @SuppressWarnings("unchecked") + List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil(); + ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps); + Preconditions.checkState( + set.size() == reverseDeps.size(), + "Duplicate reverse deps present in %s: %s", + reverseDeps, + entry); + return set; + } + } + + static Set<SkyKey> returnNewElements(InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) { + return consolidateDataAndReturnNewElements(entry, false, opToStoreBare); + } + + @SuppressWarnings("unchecked") // List and bare SkyKey casts. + private static Set<SkyKey> consolidateDataAndReturnNewElements( + InMemoryNodeEntry entry, boolean mutateObject, OpToStoreBare opToStoreBare) { + List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil(); + if (dataToConsolidate == null) { + return ImmutableSet.of(); + } + Set<SkyKey> reverseDepsAsSet; + Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil(); + if (isSingleReverseDep(entry)) { + reverseDepsAsSet = CompactHashSet.create((SkyKey) reverseDeps); + } else { + List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; + reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList); + } + Set<SkyKey> newData = CompactHashSet.create(); + for (Object keyToConsolidate : dataToConsolidate) { + SkyKey key = KeyToConsolidate.key(keyToConsolidate); + switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) { + case CHECK: + Preconditions.checkState( + reverseDepsAsSet.contains(key), + "Reverse dep not present: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + Preconditions.checkState( + newData.add(key), + "Duplicate new reverse dep: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + break; + case REMOVE: + Preconditions.checkState( + reverseDepsAsSet.remove(key), + "Reverse dep to be removed not present: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + Preconditions.checkState( + newData.remove(key), + "Reverse dep to be removed not present: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + break; + case REMOVE_OLD: + Preconditions.checkState( + reverseDepsAsSet.remove(key), + "Reverse dep to be removed not present: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + Preconditions.checkState( + !newData.contains(key), + "Reverse dep shouldn't have been added to new: %s %s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + newData, + dataToConsolidate, + entry); + break; + case ADD: + Preconditions.checkState( + reverseDepsAsSet.add(key), + "Duplicate reverse deps: %s %s %s %s %s", + keyToConsolidate, + reverseDeps, + newData, + dataToConsolidate, + entry); + Preconditions.checkState( + newData.add(key), + "Duplicate new reverse deps: %s %s %s %s %s", + keyToConsolidate, + reverseDeps, + newData, + dataToConsolidate, + entry); + break; + default: + throw new IllegalStateException( + keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry); + } + } + if (mutateObject) { + entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null); + writeReverseDepsSet(entry, reverseDepsAsSet); + } + return newData; + } + + static Set<SkyKey> consolidateDataAndReturnNewElements( + InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) { + return consolidateDataAndReturnNewElements(entry, true, opToStoreBare); + } + + @SuppressWarnings("unchecked") // Casts to SkyKey and List. + private static void consolidateData(InMemoryNodeEntry entry) { + List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil(); + if (dataToConsolidate == null) { + return; + } + entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null); + Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil(); + if (isSingleReverseDep(entry)) { + Preconditions.checkState( + dataToConsolidate.size() == 1, + "dataToConsolidate not size 1 even though only one rdep: %s %s %s", + dataToConsolidate, + reverseDeps, + entry); + Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate); + SkyKey key = KeyToConsolidate.key(keyToConsolidate); + switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) { + case REMOVE: + entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of()); + // Fall through to check. + case CHECK: + Preconditions.checkState( + key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, entry); + break; + case ADD: + throw new IllegalStateException( + "Shouldn't delay add if only one element: " + + keyToConsolidate + + ", " + + reverseDeps + + ", " + + entry); + case REMOVE_OLD: + throw new IllegalStateException( + "Shouldn't be removing old deps if node already done: " + + keyToConsolidate + + ", " + + reverseDeps + + ", " + + entry); + default: + throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + entry); + } + return; + } + List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; + Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList); + + for (Object keyToConsolidate : dataToConsolidate) { + SkyKey key = KeyToConsolidate.key(keyToConsolidate); + switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) { + case CHECK: + Preconditions.checkState( + reverseDepsAsSet.contains(key), + "%s %s %s %s", + keyToConsolidate, + reverseDepsAsSet, + dataToConsolidate, + entry); + break; + case REMOVE: + Preconditions.checkState( + reverseDepsAsSet.remove(key), + "%s %s %s %s", + keyToConsolidate, + reverseDeps, + dataToConsolidate, + entry); + break; + case ADD: + Preconditions.checkState( + reverseDepsAsSet.add(key), + "%s %s %s %s", + keyToConsolidate, + reverseDeps, + dataToConsolidate, + entry); + break; + case REMOVE_OLD: + throw new IllegalStateException( + "Shouldn't be removing old deps if node already done: " + + keyToConsolidate + + ", " + + reverseDeps + + ", " + + dataToConsolidate + + ", " + + entry); + default: + throw new IllegalStateException( + keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry); + } + } + writeReverseDepsSet(entry, reverseDepsAsSet); + } + + private static void writeReverseDepsSet(InMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) { + if (reverseDepsAsSet.isEmpty()) { + entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of()); + } else if (reverseDepsAsSet.size() == 1) { + entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet)); + } else { + entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet)); + } + } + + private static Set<SkyKey> getReverseDepsSet( + InMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) { + Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList); + + if (reverseDepsAsSet.size() != reverseDepsAsList.size()) { + // We're about to crash. Try to print an informative error message. + Set<SkyKey> seen = new HashSet<>(); + List<SkyKey> duplicates = new ArrayList<>(); + for (SkyKey key : reverseDepsAsList) { + if (!seen.add(key)) { + duplicates.add(key); + } + } + throw new IllegalStateException( + (reverseDepsAsList.size() - reverseDepsAsSet.size()) + + " duplicates: " + + duplicates + + " for " + + entry); + } + return reverseDepsAsSet; + } + + static String toString(InMemoryNodeEntry entry) { + return MoreObjects.toStringHelper("ReverseDeps") + .add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil()) + .add("singleReverseDep", isSingleReverseDep(entry)) + .add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil()) + .toString(); + } +} diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java index 49db9cdc0b..7876d57100 100644 --- a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java +++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java @@ -135,9 +135,10 @@ public class DeterministicHelper extends NotifyingHelper { } @Override - public synchronized Collection<SkyKey> getReverseDeps() throws InterruptedException { + public synchronized Collection<SkyKey> getReverseDepsForDoneEntry() + throws InterruptedException { TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR); - Iterables.addAll(result, super.getReverseDeps()); + Iterables.addAll(result, super.getReverseDepsForDoneEntry()); return result; } diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java index cfb656bf56..2ab03467ba 100644 --- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java @@ -337,12 +337,12 @@ public class EagerInvalidatorTest { .setComputedValue(CONCATENATE); eval(false, skyKey("ab_c"), skyKey("bc")); - assertThat(graph.get(null, Reason.OTHER, skyKey("a")) - .getReverseDeps()).containsExactly(skyKey("ab")); - assertThat(graph.get(null, Reason.OTHER, skyKey("b")) - .getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc")); - assertThat(graph.get(null, Reason.OTHER, skyKey("c")) - .getReverseDeps()).containsExactly(skyKey("ab_c"), skyKey("bc")); + assertThat(graph.get(null, Reason.OTHER, skyKey("a")).getReverseDepsForDoneEntry()) + .containsExactly(skyKey("ab")); + assertThat(graph.get(null, Reason.OTHER, skyKey("b")).getReverseDepsForDoneEntry()) + .containsExactly(skyKey("ab"), skyKey("bc")); + assertThat(graph.get(null, Reason.OTHER, skyKey("c")).getReverseDepsForDoneEntry()) + .containsExactly(skyKey("ab_c"), skyKey("bc")); invalidateWithoutError(new DirtyTrackingProgressReceiver(null), skyKey("ab")); eval(false); @@ -356,18 +356,18 @@ public class EagerInvalidatorTest { if (reverseDepsPresent()) { reverseDeps.add(skyKey("ab")); } - assertThat(graph.get(null, Reason.OTHER, skyKey("a")) - .getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("a")).getReverseDepsForDoneEntry()) + .containsExactlyElementsIn(reverseDeps); reverseDeps.add(skyKey("bc")); - assertThat(graph.get(null, Reason.OTHER, skyKey("b")) - .getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("b")).getReverseDepsForDoneEntry()) + .containsExactlyElementsIn(reverseDeps); reverseDeps.clear(); if (reverseDepsPresent()) { reverseDeps.add(skyKey("ab_c")); } reverseDeps.add(skyKey("bc")); - assertThat(graph.get(null, Reason.OTHER, skyKey("c")) - .getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("c")).getReverseDepsForDoneEntry()) + .containsExactlyElementsIn(reverseDeps); } @Test diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java index 0510523cbe..932878fbe2 100644 --- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java @@ -197,7 +197,7 @@ public abstract class GraphTest { for (int k = chunkSize; k <= numIterations; k++) { entry.removeReverseDep(key("rdep" + j)); entry.addReverseDepAndCheckIfDone(key("rdep" + j)); - entry.getReverseDeps(); + entry.getReverseDepsForDoneEntry(); } } catch (InterruptedException e) { fail("Test failed: " + e.toString()); @@ -213,7 +213,9 @@ public abstract class GraphTest { wrapper.waitForTasksAndMaybeThrow(); assertFalse(ExecutorUtil.interruptibleShutdown(pool)); assertEquals(new StringValue("foo1"), graph.get(null, Reason.OTHER, key).getValue()); - assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps())); + assertEquals( + numKeys + 1, + Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDepsForDoneEntry())); graph = getGraph(getNextVersion(startingVersion)); NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(null, Reason.OTHER, key)); @@ -223,7 +225,9 @@ public abstract class GraphTest { sameEntry.markRebuilding(); sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion)); assertEquals(new StringValue("foo2"), graph.get(null, Reason.OTHER, key).getValue()); - assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps())); + assertEquals( + numKeys + 1, + Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDepsForDoneEntry())); } // Tests adding inflight nodes with a given key while an existing node with the same key @@ -451,7 +455,7 @@ public abstract class GraphTest { NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + i)); assertThat(entry.getValue()).isEqualTo(new StringValue("bar" + i)); assertThat(entry.getVersion()).isEqualTo(getNextVersion(startingVersion)); - for (SkyKey key : entry.getReverseDeps()) { + for (SkyKey key : entry.getReverseDepsForDoneEntry()) { assertEquals(key("rdep"), key); } for (SkyKey key : entry.getDirectDeps()) { diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java index 8b8fb81c8c..5829329452 100644 --- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java @@ -101,10 +101,10 @@ public class InMemoryNodeEntryTest { assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(father)); assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father); - assertThat(entry.getReverseDeps()).containsExactly(mother, father); + assertThat(entry.getReverseDepsForDoneEntry()).containsExactly(mother, father); assertTrue(entry.isDone()); entry.removeReverseDep(mother); - assertFalse(Iterables.contains(entry.getReverseDeps(), mother)); + assertFalse(Iterables.contains(entry.getReverseDepsForDoneEntry(), mother)); } @Test @@ -337,7 +337,7 @@ public class InMemoryNodeEntryTest { try { entry.addReverseDepAndCheckIfDone(parent); // We only check for duplicates when we request all the reverse deps. - entry.getReverseDeps(); + entry.getReverseDepsForDoneEntry(); fail("Cannot add same dep twice"); } catch (IllegalStateException e) { // Expected. @@ -353,7 +353,7 @@ public class InMemoryNodeEntryTest { try { entry.addReverseDepAndCheckIfDone(parent); // We only check for duplicates when we request all the reverse deps. - entry.getReverseDeps(); + entry.getReverseDepsForDoneEntry(); fail("Cannot add same dep twice"); } catch (IllegalStateException e) { // Expected. @@ -692,9 +692,9 @@ public class InMemoryNodeEntryTest { assertThat(clone1.getDirectDeps()).containsExactly(originalChild); assertThat(clone2.getDirectDeps()).containsExactly(newChild); - assertThat(entry.getReverseDeps()).hasSize(0); - assertThat(clone1.getReverseDeps()).containsExactly(key("parent1")); - assertThat(clone2.getReverseDeps()).containsExactly(key("parent1"), key("parent2")); + assertThat(entry.getReverseDepsForDoneEntry()).hasSize(0); + assertThat(clone1.getReverseDepsForDoneEntry()).containsExactly(key("parent1")); + assertThat(clone2.getReverseDepsForDoneEntry()).containsExactly(key("parent1"), key("parent2")); } @Test diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java deleted file mode 100644 index d66dc6762a..0000000000 --- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java +++ /dev/null @@ -1,199 +0,0 @@ -// Copyright 2014 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.skyframe; - -import static com.google.common.truth.Truth.assertThat; - -import com.google.common.collect.ImmutableList; - -import org.junit.Assert; -import org.junit.Test; -import org.junit.runner.RunWith; -import org.junit.runners.Parameterized; -import org.junit.runners.Parameterized.Parameters; - -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; - -/** - * Test for {@code ReverseDepsUtilImpl}. - */ -@RunWith(Parameterized.class) -public class ReverseDepsUtilImplTest { - - private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type"); - private final int numElements; - - @Parameters(name = "numElements-{0}") - public static List<Object[]> paramenters() { - List<Object[]> params = new ArrayList<>(); - for (int i = 0; i < 20; i++) { - params.add(new Object[] {i}); - } - return params; - } - - public ReverseDepsUtilImplTest(int numElements) { - this.numElements = numElements; - } - - private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL = - new ReverseDepsUtilImpl<Example>() { - @Override - void setReverseDepsObject(Example container, Object object) { - container.reverseDeps = object; - } - - @Override - void setDataToConsolidate(Example container, List<Object> dataToConsolidate) { - container.dataToConsolidate = dataToConsolidate; - } - - @Override - Object getReverseDepsObject(Example container) { - return container.reverseDeps; - } - - @Override - List<Object> getDataToConsolidate(Example container) { - return container.dataToConsolidate; - } - }; - - private class Example { - - Object reverseDeps = ImmutableList.of(); - boolean single; - List<Object> dataToConsolidate; - - @Override - public String toString() { - return "Example: " + reverseDeps + ", " + single + ", " + dataToConsolidate; - } - } - - @Test - public void testAddAndRemove() { - for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) { - Example example = new Example(); - for (int j = 0; j < numElements; j++) { - REVERSE_DEPS_UTIL.addReverseDeps( - example, Collections.singleton(SkyKey.create(NODE_TYPE, j))); - } - // Not a big test but at least check that it does not blow up. - assertThat(REVERSE_DEPS_UTIL.toString(example)).isNotEmpty(); - assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements); - for (int i = 0; i < numRemovals; i++) { - REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i)); - } - assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals); - assertThat(example.dataToConsolidate).isNull(); - } - } - - // Same as testAdditionAndRemoval but we add all the reverse deps in one call. - @Test - public void testAddAllAndRemove() { - for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) { - Example example = new Example(); - List<SkyKey> toAdd = new ArrayList<>(); - for (int j = 0; j < numElements; j++) { - toAdd.add(SkyKey.create(NODE_TYPE, j)); - } - REVERSE_DEPS_UTIL.addReverseDeps(example, toAdd); - assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements); - for (int i = 0; i < numRemovals; i++) { - REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i)); - } - assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals); - assertThat(example.dataToConsolidate).isNull(); - } - } - - @Test - public void testDuplicateCheckOnGetReverseDeps() { - Example example = new Example(); - for (int i = 0; i < numElements; i++) { - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i))); - } - // Should only fail when we call getReverseDeps(). - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0))); - try { - REVERSE_DEPS_UTIL.getReverseDeps(example); - assertThat(numElements).isEqualTo(0); - } catch (Exception expected) { - } - } - - @Test - public void doubleAddThenRemove() { - Example example = new Example(); - SkyKey key = SkyKey.create(NODE_TYPE, 0); - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key)); - // Should only fail when we call getReverseDeps(). - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key)); - REVERSE_DEPS_UTIL.removeReverseDep(example, key); - try { - REVERSE_DEPS_UTIL.getReverseDeps(example); - Assert.fail(); - } catch (IllegalStateException expected) { - } - } - - @Test - public void doubleAddThenRemoveCheckedOnSize() { - Example example = new Example(); - SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0); - SkyKey key = SkyKey.create(NODE_TYPE, 1); - REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key)); - // Should only fail when we reach the limit. - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key)); - REVERSE_DEPS_UTIL.removeReverseDep(example, key); - REVERSE_DEPS_UTIL.checkReverseDep(example, fixedKey); - try { - REVERSE_DEPS_UTIL.checkReverseDep(example, fixedKey); - Assert.fail(); - } catch (IllegalStateException expected) { - } - } - - @Test - public void addRemoveAdd() { - Example example = new Example(); - SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0); - SkyKey key = SkyKey.create(NODE_TYPE, 1); - REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key)); - REVERSE_DEPS_UTIL.removeReverseDep(example, key); - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key)); - assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).containsExactly(fixedKey, key); - } - - @Test - public void testMaybeCheck() { - Example example = new Example(); - for (int i = 0; i < numElements; i++) { - REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i))); - // This should always succeed, since the next element is still not present. - REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1)); - } - try { - REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0)); - // Should only fail if empty or above the checking threshold. - assertThat(numElements == 0 || numElements >= ReverseDepsUtilImpl.MAYBE_CHECK_THRESHOLD) - .isTrue(); - } catch (Exception expected) { - } - } -} diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java new file mode 100644 index 0000000000..3001c2a43f --- /dev/null +++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java @@ -0,0 +1,162 @@ +// Copyright 2014 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.skyframe; + +import static com.google.common.truth.Truth.assertThat; + +import com.google.common.collect.ImmutableList; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import org.junit.Assert; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; +import org.junit.runners.Parameterized.Parameters; + +/** Test for {@code ReverseDepsUtility}. */ +@RunWith(Parameterized.class) +public class ReverseDepsUtilityTest { + + private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type"); + private final int numElements; + + @Parameters(name = "numElements-{0}") + public static List<Object[]> paramenters() { + List<Object[]> params = new ArrayList<>(); + for (int i = 0; i < 20; i++) { + params.add(new Object[] {i}); + } + return params; + } + + public ReverseDepsUtilityTest(int numElements) { + this.numElements = numElements; + } + + @Test + public void testAddAndRemove() { + for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + for (int j = 0; j < numElements; j++) { + ReverseDepsUtility.addReverseDeps( + example, Collections.singleton(SkyKey.create(NODE_TYPE, j))); + } + // Not a big test but at least check that it does not blow up. + assertThat(ReverseDepsUtility.toString(example)).isNotEmpty(); + assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements); + for (int i = 0; i < numRemovals; i++) { + ReverseDepsUtility.removeReverseDep(example, SkyKey.create(NODE_TYPE, i)); + } + assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals); + assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull(); + } + } + + // Same as testAdditionAndRemoval but we add all the reverse deps in one call. + @Test + public void testAddAllAndRemove() { + for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + List<SkyKey> toAdd = new ArrayList<>(); + for (int j = 0; j < numElements; j++) { + toAdd.add(SkyKey.create(NODE_TYPE, j)); + } + ReverseDepsUtility.addReverseDeps(example, toAdd); + assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements); + for (int i = 0; i < numRemovals; i++) { + ReverseDepsUtility.removeReverseDep(example, SkyKey.create(NODE_TYPE, i)); + } + assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals); + assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull(); + } + } + + @Test + public void testDuplicateCheckOnGetReverseDeps() { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + for (int i = 0; i < numElements; i++) { + ReverseDepsUtility.addReverseDeps( + example, Collections.singleton(SkyKey.create(NODE_TYPE, i))); + } + // Should only fail when we call getReverseDeps(). + ReverseDepsUtility.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0))); + try { + ReverseDepsUtility.getReverseDeps(example); + assertThat(numElements).isEqualTo(0); + } catch (Exception expected) { + } + } + + @Test + public void doubleAddThenRemove() { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + SkyKey key = SkyKey.create(NODE_TYPE, 0); + ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key)); + // Should only fail when we call getReverseDeps(). + ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key)); + ReverseDepsUtility.removeReverseDep(example, key); + try { + ReverseDepsUtility.getReverseDeps(example); + Assert.fail(); + } catch (IllegalStateException expected) { + } + } + + @Test + public void doubleAddThenRemoveCheckedOnSize() { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0); + SkyKey key = SkyKey.create(NODE_TYPE, 1); + ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key)); + // Should only fail when we reach the limit. + ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key)); + ReverseDepsUtility.removeReverseDep(example, key); + ReverseDepsUtility.checkReverseDep(example, fixedKey); + try { + ReverseDepsUtility.checkReverseDep(example, fixedKey); + Assert.fail(); + } catch (IllegalStateException expected) { + } + } + + @Test + public void addRemoveAdd() { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0); + SkyKey key = SkyKey.create(NODE_TYPE, 1); + ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key)); + ReverseDepsUtility.removeReverseDep(example, key); + ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key)); + assertThat(ReverseDepsUtility.getReverseDeps(example)).containsExactly(fixedKey, key); + } + + @Test + public void testMaybeCheck() { + InMemoryNodeEntry example = new InMemoryNodeEntry(); + for (int i = 0; i < numElements; i++) { + ReverseDepsUtility.addReverseDeps( + example, Collections.singleton(SkyKey.create(NODE_TYPE, i))); + // This should always succeed, since the next element is still not present. + ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1)); + } + try { + ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0)); + // Should only fail if empty or above the checking threshold. + assertThat(numElements == 0 || numElements >= ReverseDepsUtility.MAYBE_CHECK_THRESHOLD) + .isTrue(); + } catch (Exception expected) { + } + } +} |