diff options
author | Janak Ramakrishnan <janakr@google.com> | 2015-09-22 17:37:10 +0000 |
---|---|---|
committer | Lukacs Berki <lberki@google.com> | 2015-09-23 10:31:45 +0000 |
commit | 5877b8b39a7d88f4501ab1736f8ac2fe65431579 (patch) | |
tree | 946f1ee782e403e9de737a63ee66f79c0e9432df /src/main/java/com/google | |
parent | 095190962d6ddf91bd8378ff7fe4e0543f74091f (diff) |
Don't remove reverse deps until node is known to be changed. This helps avoid mutating the deps of nodes that are still going to be deps after evaluation is finished.
--
MOS_MIGRATED_REVID=103659429
Diffstat (limited to 'src/main/java/com/google')
8 files changed, 664 insertions, 320 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 547549e07a..41b94ad137 100644 --- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java +++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java @@ -73,9 +73,10 @@ public class BuildingState { /** * The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes - * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link DirtyState#REBUILDING}, - * depending on whether the caller specified that the node was itself changed or not. A non-null - * {@code dirtyState} indicates that the node {@link #isDirty} in some way. + * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or + * {@link DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node + * was itself changed or not. A non-null {@code dirtyState} indicates that the node + * {@link #isDirty} in some way. */ private DirtyState dirtyState = null; @@ -118,41 +119,41 @@ public class BuildingState { // node will be removed by the time evaluation starts, so reverse deps to signal can just be // reverse deps in the main ValueEntry object. private Object reverseDepsToSignal = ImmutableList.of(); - private List<SkyKey> reverseDepsToRemove = null; + private Object reverseDepsDataToConsolidate = null; private boolean reverseDepIsSingleObject = false; private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL = new ReverseDepsUtil<BuildingState>() { - @Override - void setReverseDepsObject(BuildingState container, Object object) { - container.reverseDepsToSignal = object; - } - - @Override - void setSingleReverseDep(BuildingState container, boolean singleObject) { - container.reverseDepIsSingleObject = singleObject; - } - - @Override - void setReverseDepsToRemove(BuildingState container, List<SkyKey> object) { - container.reverseDepsToRemove = object; - } - - @Override - Object getReverseDepsObject(BuildingState container) { - return container.reverseDepsToSignal; - } - - @Override - boolean isSingleReverseDep(BuildingState container) { - return container.reverseDepIsSingleObject; - } - - @Override - List<SkyKey> getReverseDepsToRemove(BuildingState container) { - return container.reverseDepsToRemove; - } - }; + @Override + void setReverseDepsObject(BuildingState container, Object object) { + container.reverseDepsToSignal = object; + } + + @Override + void setSingleReverseDep(BuildingState container, boolean singleObject) { + container.reverseDepIsSingleObject = singleObject; + } + + @Override + void setDataToConsolidate(BuildingState container, Object dataToConsolidate) { + container.reverseDepsDataToConsolidate = dataToConsolidate; + } + + @Override + Object getReverseDepsObject(BuildingState container) { + return container.reverseDepsToSignal; + } + + @Override + boolean isSingleReverseDep(BuildingState container) { + return container.reverseDepIsSingleObject; + } + + @Override + Object getDataToConsolidate(BuildingState container) { + return container.reverseDepsDataToConsolidate; + } + }; // Below are fields that are used for dirty nodes. @@ -180,12 +181,10 @@ public class BuildingState { Preconditions.checkState(isChanged || !this.lastBuildDirectDeps.isEmpty(), "%s is being marked dirty, not changed, but has no children that could have dirtied it", this); - dirtyState = isChanged ? DirtyState.REBUILDING - : DirtyState.CHECK_DEPENDENCIES; - if (dirtyState == DirtyState.CHECK_DEPENDENCIES) { - // We need to iterate through the deps to see if they have changed. Initialize the iterator. - dirtyDirectDepIterator = lastBuildDirectDeps.iterator(); - } + dirtyState = isChanged ? DirtyState.NEEDS_REBUILDING : DirtyState.CHECK_DEPENDENCIES; + // We need to iterate through the deps to see if they have changed, or to remove them if one + // has. Initialize the iterator. + dirtyDirectDepIterator = lastBuildDirectDeps.iterator(); } static BuildingState newDirtyState(boolean isChanged, @@ -197,7 +196,7 @@ public class BuildingState { Preconditions.checkState(isDirty(), this); Preconditions.checkState(!isChanged(), this); Preconditions.checkState(!evaluating, this); - dirtyState = DirtyState.REBUILDING; + dirtyState = DirtyState.NEEDS_REBUILDING; } void forceChanged() { @@ -234,11 +233,7 @@ public class BuildingState { * @see NodeEntry#isChanged() */ boolean isChanged() { - return dirtyState == DirtyState.REBUILDING; - } - - private boolean rebuilding() { - return dirtyState == DirtyState.REBUILDING; + return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING; } /** @@ -246,10 +241,14 @@ public class BuildingState { * actually like to check that the node has been evaluated, but that is not available in * this context. */ - private void checkNotProcessing() { + private void checkFinishedBuildingWhenAboutToSetValue() { Preconditions.checkState(evaluating, "not started building %s", this); - Preconditions.checkState(!isDirty() || dirtyState == DirtyState.VERIFIED_CLEAN - || rebuilding(), "not done building %s", this); + Preconditions.checkState( + !isDirty() + || dirtyState == DirtyState.VERIFIED_CLEAN + || dirtyState == DirtyState.REBUILDING, + "not done building %s", + this); Preconditions.checkState(isReady(), "not done building %s", this); } @@ -269,7 +268,7 @@ public class BuildingState { * finished is equal to the number of known children. * * <p>If the node is dirty and checking its deps for changes, this also updates {@link - * #dirtyState} as needed -- {@link DirtyState#REBUILDING} if the child has changed, + * #dirtyState} as needed -- {@link DirtyState#NEEDS_REBUILDING} if the child has changed, * and {@link DirtyState#VERIFIED_CLEAN} if the child has not changed and this was the * last child to be checked (as determined by {@link #dirtyDirectDepIterator}.hasNext() and * isReady()). @@ -278,15 +277,15 @@ public class BuildingState { */ boolean signalDep(boolean childChanged) { signaledDeps++; - if (isDirty() && !rebuilding()) { - // Synchronization isn't needed here because the only caller is ValueEntry, which does it - // through the synchronized method signalDep(long). + if (isDirty() && !isChanged()) { + // Synchronization isn't needed here because the only caller is NodeEntry, which does it + // through the synchronized method signalDep(Version). if (childChanged) { - dirtyState = DirtyState.REBUILDING; + dirtyState = DirtyState.NEEDS_REBUILDING; } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES && isReady() && !dirtyDirectDepIterator.hasNext()) { - // No other dep already marked this as REBUILDING, no deps outstanding, and this was + // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was // the last block of deps to be checked. dirtyState = DirtyState.VERIFIED_CLEAN; } @@ -300,7 +299,7 @@ public class BuildingState { * was built, in the same order. Should only be used by {@link NodeEntry#setValue}. */ boolean unchangedFromLastBuild(SkyValue newValue) { - checkNotProcessing(); + checkFinishedBuildingWhenAboutToSetValue(); return getLastBuildValue().equals(newValue) && lastBuildDirectDeps.equals(directDeps); } @@ -341,6 +340,22 @@ public class BuildingState { return nextDeps; } + Collection<SkyKey> getAllRemainingDirtyDirectDeps() { + Preconditions.checkState(isDirty(), this); + ImmutableList.Builder<SkyKey> result = ImmutableList.builder(); + while (dirtyDirectDepIterator.hasNext()) { + result.addAll(dirtyDirectDepIterator.next()); + } + return result.build(); + } + + Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() { + Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this); + Collection<SkyKey> result = getAllRemainingDirtyDirectDeps(); + dirtyState = DirtyState.REBUILDING; + return result; + } + void addDirectDeps(GroupedListHelper<SkyKey> depsThisRun) { directDeps.append(depsThisRun); } @@ -380,7 +395,7 @@ public class BuildingState { * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey) */ void addReverseDepToSignal(SkyKey newReverseDep) { - REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this); + REVERSE_DEPS_UTIL.consolidateData(this); REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep)); } diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java index ad50bea196..9e346ebcb5 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java @@ -27,7 +27,6 @@ import com.google.devtools.build.skyframe.Differencer.Diff; import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingInvalidationState; import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvalidationState; import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState; -import com.google.devtools.build.skyframe.NodeEntry.DependencyState; import com.google.devtools.build.skyframe.ParallelEvaluator.Receiver; import java.io.PrintStream; @@ -224,29 +223,8 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { return; } for (Entry<SkyKey, SkyValue> entry : valuesToInject.entrySet()) { - SkyKey key = entry.getKey(); - SkyValue value = entry.getValue(); - Preconditions.checkState(value != null, key); - NodeEntry prevEntry = graph.createIfAbsent(key); - if (prevEntry.isDirty()) { - // There was an existing entry for this key in the graph. - // Get the node in the state where it is able to accept a value. - Preconditions.checkState(prevEntry.getTemporaryDirectDeps().isEmpty(), key); - - DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null); - Preconditions.checkState(newState == DependencyState.NEEDS_SCHEDULING, key); - - // Check that the previous node has no dependencies. Overwriting a value with deps with an - // injected value (which is by definition deps-free) needs a little additional bookkeeping - // (removing reverse deps from the dependencies), but more importantly it's something that - // we want to avoid, because it indicates confusion of input values and derived values. - Preconditions.checkState(prevEntry.noDepsLastBuild(), - "existing entry for %s has deps: %s", key, prevEntry); - } - prevEntry.setValue(value, version); - // The evaluate method previously invalidated all keys in valuesToInject that survived the - // pruneInjectedValues call. Now that this key's injected value is set, it is no longer dirty. - dirtyKeyTracker.notDirty(key); + ParallelEvaluator.injectValue( + entry.getKey(), entry.getValue(), version, graph, dirtyKeyTracker); } // Start with a new map to avoid bloat since clear() does not downsize the map. valuesToInject = new HashMap<>(); 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 fa8e3082a6..f3a6a8111a 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java @@ -18,11 +18,11 @@ import com.google.common.base.MoreObjects; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterables; import com.google.devtools.build.lib.util.GroupedList; import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import java.util.Collection; -import java.util.List; import java.util.Set; import javax.annotation.Nullable; @@ -82,49 +82,49 @@ public class InMemoryNodeEntry implements NodeEntry { protected boolean reverseDepIsSingleObject = false; /** - * During the invalidation we keep the reverse deps to be removed in this list instead of directly - * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N). + * When reverse deps are removed or checked for presence, we store them in this object instead of + * directly removing/checking them. 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>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call - * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done - * more effectively than trying to remove each dirty reverse dependency individually (O(N) each - * time). + * {@code consolidateData} first. 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). */ - private List<SkyKey> reverseDepsToRemove = null; + private Object reverseDepsDataToConsolidate = null; protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL = new ReverseDepsUtil<InMemoryNodeEntry>() { - @Override - void setReverseDepsObject(InMemoryNodeEntry container, Object object) { - container.reverseDeps = object; - } + @Override + void setReverseDepsObject(InMemoryNodeEntry container, Object object) { + container.reverseDeps = object; + } - @Override - void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) { - container.reverseDepIsSingleObject = singleObject; - } + @Override + void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) { + container.reverseDepIsSingleObject = singleObject; + } - @Override - void setReverseDepsToRemove(InMemoryNodeEntry container, List<SkyKey> object) { - container.reverseDepsToRemove = object; - } + @Override + void setDataToConsolidate(InMemoryNodeEntry container, Object dataToConsolidate) { + container.reverseDepsDataToConsolidate = dataToConsolidate; + } - @Override - Object getReverseDepsObject(InMemoryNodeEntry container) { - return container.reverseDeps; - } + @Override + Object getReverseDepsObject(InMemoryNodeEntry container) { + return container.reverseDeps; + } - @Override - boolean isSingleReverseDep(InMemoryNodeEntry container) { - return container.reverseDepIsSingleObject; - } + @Override + boolean isSingleReverseDep(InMemoryNodeEntry container) { + return container.reverseDepIsSingleObject; + } - @Override - List<SkyKey> getReverseDepsToRemove(InMemoryNodeEntry container) { - return container.reverseDepsToRemove; - } - }; + @Override + 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 @@ -202,7 +202,7 @@ public class InMemoryNodeEntry implements NodeEntry { private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() { // Get reverse deps that need to be signaled. ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal(); - REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this); + REVERSE_DEPS_UTIL.consolidateData(this); REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal); this.directDeps = buildingState.getFinishedDirectDeps().compress(); @@ -247,7 +247,7 @@ public class InMemoryNodeEntry implements NodeEntry { public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) { if (reverseDep != null) { if (keepEdges()) { - REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this); + REVERSE_DEPS_UTIL.consolidateData(this); REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep); } if (isDone()) { @@ -263,7 +263,20 @@ public class InMemoryNodeEntry implements NodeEntry { return DependencyState.DONE; } return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING - : DependencyState.ADDED_DEP; + : DependencyState.ALREADY_EVALUATING; + } + + @Override + public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) { + Preconditions.checkNotNull(reverseDep, this); + Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this); + if (!isDone()) { + REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); + buildingState.addReverseDepToSignal(reverseDep); + } else { + REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep); + } + return addReverseDepAndCheckIfDone(null); } @Override @@ -271,19 +284,23 @@ public class InMemoryNodeEntry implements NodeEntry { if (!keepEdges()) { return; } - if (REVERSE_DEPS_UTIL.reverseDepsIsEmpty(this)) { - // If an entry has no existing reverse deps, all its reverse deps are to signal, and vice - // versa. - buildingState.removeReverseDepToSignal(reverseDep); - } else { - REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); - } + REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); + } + + @Override + public synchronized void removeInProgressReverseDep(SkyKey reverseDep) { + buildingState.removeReverseDepToSignal(reverseDep); } @Override - public synchronized Collection<SkyKey> getReverseDeps() { + public synchronized Iterable<SkyKey> getReverseDeps() { assertKeepEdges(); - return REVERSE_DEPS_UTIL.getReverseDeps(this); + Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this); + if (isDone()) { + return reverseDeps; + } else { + return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal()); + } } @Override @@ -313,15 +330,13 @@ public class InMemoryNodeEntry implements NodeEntry { } @Override - @Nullable - public synchronized Iterable<SkyKey> markDirty(boolean isChanged) { + public synchronized boolean markDirty(boolean isChanged) { assertKeepEdges(); if (isDone()) { - GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps); - buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value); + buildingState = + BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value); value = null; - directDeps = null; - return lastDirectDeps.toSet(); + return true; } // 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 @@ -330,13 +345,12 @@ public class InMemoryNodeEntry implements NodeEntry { Preconditions.checkState(isChanged != isChanged(), "Cannot mark node dirty twice or changed twice: %s", this); Preconditions.checkState(value == null, "Value should have been reset already %s", this); - Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this); if (isChanged) { // If the changed marker lost the race, we just need to mark changed in this method -- all // other work was done by the dirty marker. buildingState.markChanged(); } - return null; + return false; } @Override @@ -371,10 +385,27 @@ public class InMemoryNodeEntry implements NodeEntry { /** @see BuildingState#getNextDirtyDirectDeps() */ @Override public synchronized Collection<SkyKey> getNextDirtyDirectDeps() { + Preconditions.checkState(isReady(), this); return buildingState.getNextDirtyDirectDeps(); } @Override + public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() { + Preconditions.checkState(!isDone(), this); + if (!isDirty()) { + return getTemporaryDirectDeps(); + } else { + return Iterables.concat( + getTemporaryDirectDeps(), buildingState.getAllRemainingDirtyDirectDeps()); + } + } + + @Override + public synchronized Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() { + return buildingState.markRebuildingAndGetAllRemainingDirtyDirectDeps(); + } + + @Override public synchronized Set<SkyKey> getTemporaryDirectDeps() { Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this); return buildingState.getDirectDepsForBuild(); @@ -403,13 +434,15 @@ public class InMemoryNodeEntry implements NodeEntry { } @Override - public String toString() { + public synchronized String toString() { return MoreObjects.toStringHelper(this) + .add("identity", System.identityHashCode(this)) .add("value", value) .add("version", version) .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps)) .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this)) - .add("buildingState", buildingState).toString(); + .add("buildingState", buildingState) + .toString(); } /** 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 791155a7dd..659f8f6665 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java +++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java @@ -239,17 +239,39 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr for (SkyKey reverseDep : entry.getReverseDeps()) { visit(reverseDep, InvalidationType.DELETED, !MUST_EXIST); } + + // 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 node as an + // "in-progress" rdep to be signaled, or just as a known rdep, we look at the deps + // that this node declared during its last (presumably interrupted) evaluation. If a + // dep is in this set, then it was notified to signal this node, and so the rdep + // will be an in-progress rdep, if the dep itself isn't done. Otherwise it will be a + // normal rdep. That information is used to remove this node as an rdep from the + // correct list of rdeps in the child -- because of our compact storage of rdeps, + // checking which list contains this parent could be expensive. + Set<SkyKey> signalingDeps = + entry.isDone() ? ImmutableSet.<SkyKey>of() : entry.getTemporaryDirectDeps(); Iterable<SkyKey> directDeps = - entry.isDone() ? entry.getDirectDeps() : entry.getTemporaryDirectDeps(); - // Unregister this node from direct deps, since reverse dep edges cannot point to - // non-existent nodes. - for (SkyKey directDep : directDeps) { - NodeEntry dep = graph.get(directDep); + entry.isDone() + ? entry.getDirectDeps() + : entry.getAllDirectDepsForIncompleteNode(); + Map<SkyKey, NodeEntry> depMap = graph.getBatch(directDeps); + for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) { + NodeEntry dep = directDepEntry.getValue(); if (dep != null) { - dep.removeReverseDep(key); + if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) { + dep.removeReverseDep(key); + } else { + // This step is not strictly necessary, since all in-progress nodes are + // deleted during graph cleaning, which happens in a single + // DeletingNodeVisitor visitation, aka the one right now. We leave this here + // in case the logic changes. + dep.removeInProgressReverseDep(key); + } } } } + // Allow custom key-specific logic to update dirtiness status. informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DELETED); // Actually remove the node. @@ -343,40 +365,20 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr return; } - // This entry remains in the graph in this dirty state until it is re-evaluated. - Iterable<SkyKey> deps = entry.markDirty(isChanged); // It is not safe to interrupt the logic from this point until the end of the method. // Any exception thrown should be unrecoverable. - if (deps == null) { + // This entry remains in the graph in this dirty state until it is re-evaluated. + if (!entry.markDirty(isChanged)) { // Another thread has already dirtied this node. Don't do anything in this thread. pendingVisitations.remove(invalidationPair); return; } - // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps - // should only be marked dirty (because only a dependency of theirs has changed). + // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps should + // only be marked dirty (because only a dependency of theirs has changed). for (SkyKey reverseDep : entry.getReverseDeps()) { visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST); } - // Remove this node as a reverse dep from its children, since we have reset it and - // it no longer lists its children as direct deps. - Map<SkyKey, ? extends ThinNodeEntry> children = graph.getBatch(deps); - if (children.size() != Iterables.size(deps)) { - Set<SkyKey> depsSet = ImmutableSet.copyOf(deps); - throw new IllegalStateException( - "Mismatch in getBatch: " - + key - + ", " - + entry - + "\n" - + Sets.difference(depsSet, children.keySet()) - + "\n" - + Sets.difference(children.keySet(), depsSet)); - } - for (ThinNodeEntry child : children.values()) { - child.removeReverseDep(key); - } - informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY); dirtyKeyTracker.dirty(key); // Remove the node from the set as the last operation. 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 56f89978ae..9f45ad4ede 100644 --- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java @@ -29,15 +29,17 @@ import javax.annotation.Nullable; */ public interface NodeEntry extends ThinNodeEntry { /** - * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}. + * Return code for {@link #addReverseDepAndCheckIfDone} and + * {@link #checkIfDoneForDirtyReverseDep}. */ enum DependencyState { /** The node is done. */ DONE, /** - * The node was just created and needs to be scheduled for its first evaluation pass. The - * evaluator is responsible for signaling the reverse dependency node. + * The node has not started evaluating, and needs to be scheduled for its first evaluation pass. + * The caller getting this return value is responsible for scheduling its evaluation and + * signaling the reverse dependency node when this node is done. */ NEEDS_SCHEDULING, @@ -45,7 +47,7 @@ public interface NodeEntry extends ThinNodeEntry { * The node was already created, but isn't done yet. The evaluator is responsible for * signaling the reverse dependency node. */ - ADDED_DEP; + ALREADY_EVALUATING; } /** @@ -63,9 +65,11 @@ public interface NodeEntry extends ThinNodeEntry { */ VERIFIED_CLEAN, /** - * A rebuilding is required or in progress, because either the node itself changed or one of - * its dependencies did. + * A rebuilding is required, because either the node itself changed or one of its dependencies + * did. */ + NEEDS_REBUILDING, + /** A rebuilding is in progress. */ REBUILDING } @@ -149,7 +153,17 @@ public interface NodeEntry extends ThinNodeEntry { * if the node needs to be scheduled. */ @ThreadSafe - DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep); + DependencyState addReverseDepAndCheckIfDone(@Nullable SkyKey reverseDep); + + /** + * Similar to {@link #addReverseDepAndCheckIfDone}, except that {@param reverseDep} must already + * be a reverse dep of this entry. Should be used when reverseDep has been marked dirty and is + * checking its dependencies for changes. The caller must treat the return value just as they + * would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this node for + * evaluation if needed. + */ + @ThreadSafe + DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep); /** * Tell this node that one of its dependencies is now done. Callers must check the return value, @@ -169,7 +183,7 @@ public interface NodeEntry extends ThinNodeEntry { * {@link #getVersion()}, then this entry records that one of its children has changed since it * was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the * child was last evaluated at {@code childVersion}. Thus, the next call to - * {@link #getDirtyState()} will return {@link DirtyState#REBUILDING}. + * {@link #getDirtyState()} will return {@link DirtyState#NEEDS_REBUILDING}. */ @ThreadSafe boolean signalDep(Version childVersion); @@ -230,6 +244,37 @@ public interface NodeEntry extends ThinNodeEntry { Collection<SkyKey> getNextDirtyDirectDeps(); /** + * Returns all deps of a node that has not yet finished evaluating. In other words, if a node has + * a reverse dep on this node, its key will be in the returned set here. If this node was freshly + * created, this is just any elements that were added using {@link #addTemporaryDirectDeps} (so it + * is the same as {@link #getTemporaryDirectDeps}). If this node is marked dirty, this includes + * all the elements that would have been returned by successive calls to + * {@link #getNextDirtyDirectDeps}. + * + * <p>This method should only be called when this node is about to be deleted after an aborted + * evaluation. After such an evaluation, any nodes that did not finish evaluating are deleted, as + * are any nodes that depend on them, which are necessarily also not done. If this node is to be + * deleted because of this, we must delete it as a reverse dep from other nodes. This method + * returns that list of other nodes. This method may not be called on done nodes, since they do + * not need to be deleted after aborted evaluations. + * + * <p>This method must not be called twice: the next thing done to this node after this method is + * called should be the removal of the node from the graph. + */ + Iterable<SkyKey> getAllDirectDepsForIncompleteNode(); + + /** + * Notifies a node that it is about to be rebuilt. This method can only be called if the node + * {@link DirtyState#NEEDS_REBUILDING}. It returns the remaining deps of the node that had not + * yet been checked: all the keys that would be returned by successive calls to + * {@link #getNextDirtyDirectDeps}. It is the caller's responsibility to (uninterruptibly) remove + * the reverse deps those deps have on this node in order to keep the graph consistent. After this + * call, this node no longer has a dep on the nodes whose keys were returned by this call and + * is ready to be rebuilt (it will be in {@link DirtyState#REBUILDING}). + */ + Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps(); + + /** * Returns the set of direct dependencies. This may only be called while the node is being * evaluated, that is, before {@link #setValue} and after {@link #markDirty}. */ 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 12cc1dd0cb..a2df93a2ed 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java @@ -40,6 +40,7 @@ import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState; import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState; import com.google.devtools.build.skyframe.NodeEntry.DependencyState; +import com.google.devtools.build.skyframe.NodeEntry.DirtyState; import com.google.devtools.build.skyframe.Scheduler.SchedulerException; import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException; @@ -582,6 +583,32 @@ public final class ParallelEvaluator implements Evaluator { } /** + * If the entry is dirty and not already rebuilding, puts it in a state that it can rebuild, and + * removes it as a reverse dep from any dirty direct deps it had yet to check. + */ + private void maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(SkyKey key, NodeEntry entry) { + if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) { + Collection<SkyKey> depsToRemove = entry.markRebuildingAndGetAllRemainingDirtyDirectDeps(); + Map<SkyKey, NodeEntry> depsToClearFrom = graph.getBatch(depsToRemove); + Preconditions.checkState( + depsToRemove.size() == depsToClearFrom.size(), + "%s %s: %s %s", + key, + entry, + depsToRemove, + depsToClearFrom); + for (NodeEntry depEntry : depsToClearFrom.values()) { + depEntry.removeReverseDep(key); + } + } + } + + private enum DirtyOutcome { + ALREADY_PROCESSED, + NEEDS_EVALUATION + } + + /** * An action that evaluates a value. */ private class Evaluate implements Runnable { @@ -594,20 +621,24 @@ public final class ParallelEvaluator implements Evaluator { this.skyKey = skyKey; } - private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child) { + private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, boolean dirtyParent) { Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry); NodeEntry depEntry = graph.createIfAbsent(child); - switch (depEntry.addReverseDepAndCheckIfDone(skyKey)) { - case DONE : + DependencyState dependencyState = + dirtyParent + ? depEntry.checkIfDoneForDirtyReverseDep(skyKey) + : depEntry.addReverseDepAndCheckIfDone(skyKey); + switch (dependencyState) { + case DONE: if (entry.signalDep(depEntry.getVersion())) { // This can only happen if there are no more children to be added. visitor.enqueueEvaluation(skyKey); } break; - case ADDED_DEP : + case ALREADY_EVALUATING: break; - case NEEDS_SCHEDULING : + case NEEDS_SCHEDULING: visitor.enqueueEvaluation(child); break; } @@ -623,97 +654,116 @@ public final class ParallelEvaluator implements Evaluator { && !graph.get(ErrorTransienceValue.key()).getVersion().atMost(entry.getVersion()); } - @Override - public void run() { - NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey); - Preconditions.checkState(state.isReady(), "%s %s", skyKey, state); - - if (state.isDirty()) { - switch (state.getDirtyState()) { - case CHECK_DEPENDENCIES: - // Evaluating a dirty node for the first time, and checking its children to see if any - // of them have changed. Note that there must be dirty children for this to happen. - - // Check the children group by group -- we don't want to evaluate a value that is no - // longer needed because an earlier dependency changed. For example, //foo:foo depends - // on target //bar:bar and is built. Then foo/BUILD is modified to remove the dependence - // on bar, and bar/BUILD is deleted. Reloading //bar:bar would incorrectly throw an - // exception. To avoid this, we must reload foo/BUILD first, at which point we will - // discover that it has changed, and re-evaluate target //foo:foo from scratch. - // On the other hand, when an action requests all of its inputs, we can safely check all - // of them in parallel on a subsequent build. So we allow checking an entire group in - // parallel here, if the node builder requested a group last build. - Collection<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps(); - - if (invalidatedByErrorTransience(directDepsToCheck, state)) { - // If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been - // updated then we need to force a rebuild. We would like to just signal the entry as - // usual, but we can't, because then the ErrorTransienceValue would remain as a dep, - // which would be incorrect if, for instance, the value re-evaluated to a non-error. - state.forceRebuild(); - break; // Fall through to re-evaluation. - } - if (!keepGoing) { - // This check ensures that we maintain the invariant that if a node with an error is - // reached during a no-keep-going build, none of its currently building parents - // finishes building. If the child isn't done building yet, it will detect on its own - // that it has an error (see the VERIFIED_CLEAN case below). On the other hand, if it - // is done, then it is the parent's responsibility to notice that, which we do here. - // We check the deps for errors so that we don't continue building this node if it has - // a child error. - for (Map.Entry<SkyKey, NodeEntry> entry : - graph.getBatch(directDepsToCheck).entrySet()) { - if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) { - // If any child has an error, we arbitrarily add a dep on the first one (needed - // for error bubbling) and throw an exception coming from it. - if (!visitor.preventNewEvaluations()) { - // An error was already thrown in the evaluator. Don't do anything here. - return; + private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) { + if (!state.isDirty()) { + return DirtyOutcome.NEEDS_EVALUATION; + } + switch (state.getDirtyState()) { + case CHECK_DEPENDENCIES: + // Evaluating a dirty node for the first time, and checking its children to see if any + // of them have changed. Note that there must be dirty children for this to happen. + + // Check the children group by group -- we don't want to evaluate a value that is no + // longer needed because an earlier dependency changed. For example, //foo:foo depends + // on target //bar:bar and is built. Then foo/BUILD is modified to remove the dependence + // on bar, and bar/BUILD is deleted. Reloading //bar:bar would incorrectly throw an + // exception. To avoid this, we must reload foo/BUILD first, at which point we will + // discover that it has changed, and re-evaluate target //foo:foo from scratch. + // On the other hand, when an action requests all of its inputs, we can safely check all + // of them in parallel on a subsequent build. So we allow checking an entire group in + // parallel here, if the node builder requested a group last build. + // Note: every dep returned here must either have this node re-registered for it (using + // checkIfDoneForDirtyReverseDep) and be registered as a direct dep of this node, or have + // its reverse dep on this node removed. Failing to do either one of these would result in + // a graph inconsistency, where the child had a reverse dep on this node, but this node + // had no kind of dependency on the child. + Collection<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps(); + + if (invalidatedByErrorTransience(directDepsToCheck, state)) { + // If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been + // updated then we need to force a rebuild. We would like to just signal the entry as + // usual, but we can't, because then the ErrorTransienceValue would remain as a dep, + // which would be incorrect if, for instance, the value re-evaluated to a non-error. + state.forceRebuild(); + graph.get(ErrorTransienceValue.key()).removeReverseDep(skyKey); + return DirtyOutcome.NEEDS_EVALUATION; + } + if (!keepGoing) { + // This check ensures that we maintain the invariant that if a node with an error is + // reached during a no-keep-going build, none of its currently building parents + // finishes building. If the child isn't done building yet, it will detect on its own + // that it has an error (see the VERIFIED_CLEAN case below). On the other hand, if it + // is done, then it is the parent's responsibility to notice that, which we do here. + // We check the deps for errors so that we don't continue building this node if it has + // a child error. + Map<SkyKey, NodeEntry> entriesToCheck = graph.getBatch(directDepsToCheck); + for (Map.Entry<SkyKey, NodeEntry> entry : entriesToCheck.entrySet()) { + if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) { + // If any child has an error, we arbitrarily add a dep on the first one (needed + // for error bubbling) and throw an exception coming from it. + SkyKey errorKey = entry.getKey(); + NodeEntry errorEntry = entry.getValue(); + state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(errorKey))); + errorEntry.checkIfDoneForDirtyReverseDep(skyKey); + // Perform the necessary bookkeeping for any deps that are not being used. + for (Map.Entry<SkyKey, NodeEntry> depEntry : entriesToCheck.entrySet()) { + if (!depEntry.getKey().equals(errorKey)) { + depEntry.getValue().removeReverseDep(skyKey); } - SkyKey errorKey = entry.getKey(); - NodeEntry errorEntry = entry.getValue(); - state.addTemporaryDirectDeps( - GroupedListHelper.create(ImmutableList.of(errorKey))); - DependencyState errorState = entry.getValue().addReverseDepAndCheckIfDone(skyKey); - Preconditions.checkState(errorState == DependencyState.DONE, "%s %s %s %s", - skyKey, state, errorKey, errorEntry); - throw SchedulerException.ofError(errorEntry.getErrorInfo(), entry.getKey()); } + if (!visitor.preventNewEvaluations()) { + // An error was already thrown in the evaluator. Don't do anything here. + return DirtyOutcome.ALREADY_PROCESSED; + } + throw SchedulerException.ofError(errorEntry.getErrorInfo(), entry.getKey()); } } - // It is safe to add these deps back to the node -- even if one of them has changed, the - // contract of pruning is that the node will request these deps again when it rebuilds. - // We must add these deps before enqueuing them, so that the node knows that it depends - // on them. If one of these deps is the error transience node, the check we did above - // in #invalidatedByErrorTransience means that the error transience node is not newer - // than this node, so we are going to mark it clean (since the error transience node is - // always the last dep). - state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck)); - for (SkyKey directDep : directDepsToCheck) { - enqueueChild(skyKey, state, directDep); - } - return; - case VERIFIED_CLEAN: - // No child has a changed value. This node can be marked done and its parents signaled - // without any re-evaluation. - visitor.notifyDone(skyKey); - Set<SkyKey> reverseDeps = state.markClean(); - if (progressReceiver != null) { - // Tell the receiver that the value was not actually changed this run. - progressReceiver.evaluated(skyKey, new SkyValueSupplier(state), - EvaluationState.CLEAN); - } - if (!keepGoing && state.getErrorInfo() != null) { - if (!visitor.preventNewEvaluations()) { - return; - } - throw SchedulerException.ofError(state.getErrorInfo(), skyKey); + } + // It is safe to add these deps back to the node -- even if one of them has changed, the + // contract of pruning is that the node will request these deps again when it rebuilds. + // We must add these deps before enqueuing them, so that the node knows that it depends + // on them. If one of these deps is the error transience node, the check we did above + // in #invalidatedByErrorTransience means that the error transience node is not newer + // than this node, so we are going to mark it clean (since the error transience node is + // always the last dep). + state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck)); + for (SkyKey directDep : directDepsToCheck) { + enqueueChild(skyKey, state, directDep, /*dirtyParent=*/ true); + } + return DirtyOutcome.ALREADY_PROCESSED; + case VERIFIED_CLEAN: + // No child has a changed value. This node can be marked done and its parents signaled + // without any re-evaluation. + visitor.notifyDone(skyKey); + Set<SkyKey> reverseDeps = state.markClean(); + if (progressReceiver != null) { + // Tell the receiver that the value was not actually changed this run. + progressReceiver.evaluated(skyKey, new SkyValueSupplier(state), EvaluationState.CLEAN); + } + if (!keepGoing && state.getErrorInfo() != null) { + if (!visitor.preventNewEvaluations()) { + return DirtyOutcome.ALREADY_PROCESSED; } - signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion()); - return; - case REBUILDING: - // Nothing to be done if we are already rebuilding. - } + throw SchedulerException.ofError(state.getErrorInfo(), skyKey); + } + signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion()); + return DirtyOutcome.ALREADY_PROCESSED; + case NEEDS_REBUILDING: + maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(skyKey, state); + // Fall through to REBUILDING case. + case REBUILDING: + return DirtyOutcome.NEEDS_EVALUATION; + default: + throw new IllegalStateException("key: " + skyKey + ", entry: " + state); + } + } + + @Override + public void run() { + NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey); + Preconditions.checkState(state.isReady(), "%s %s", skyKey, state); + if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) { + return; } // TODO(bazel-team): Once deps are requested in a deterministic order within a group, or the @@ -850,7 +900,7 @@ public final class ParallelEvaluator implements Evaluator { } for (SkyKey newDirectDep : newDirectDeps) { - enqueueChild(skyKey, state, newDirectDep); + enqueueChild(skyKey, state, newDirectDep, /*dirtyParent=*/ false); } // It is critical that there is no code below this point. } @@ -904,13 +954,13 @@ public final class ParallelEvaluator implements Evaluator { } /** - * If child is not done, removes key from child's reverse deps. Returns whether child should be - * removed from key's entry's direct deps. + * If child is not done, removes {@param inProgressParent} from {@param child}'s reverse deps. + * Returns whether child should be removed from inProgressParent's entry's direct deps. */ - private boolean removeIncompleteChild(SkyKey key, SkyKey child) { + private boolean removeIncompleteChild(SkyKey inProgressParent, SkyKey child) { NodeEntry childEntry = graph.get(child); if (!isDoneForBuild(childEntry)) { - childEntry.removeReverseDep(key); + childEntry.removeInProgressReverseDep(inProgressParent); return true; } return false; @@ -1021,18 +1071,13 @@ public final class ParallelEvaluator implements Evaluator { // in the graph, by the time that it is needed. Creating it on demand in a parallel context sets // up a race condition, because there is no way to atomically create a node and set its value. NodeEntry errorTransienceEntry = graph.createIfAbsent(ErrorTransienceValue.key()); - DependencyState triState = errorTransienceEntry.addReverseDepAndCheckIfDone(null); - Preconditions.checkState(triState != DependencyState.ADDED_DEP, - "%s %s", errorTransienceEntry, triState); - if (triState != DependencyState.DONE) { - errorTransienceEntry.setValue(new ErrorTransienceValue(), graphVersion); - // The error transience entry is always invalidated by the RecordingDifferencer. - // Now that the entry's value is set, it is no longer dirty. - dirtyKeyTracker.notDirty(ErrorTransienceValue.key()); - - Preconditions.checkState( - errorTransienceEntry.addReverseDepAndCheckIfDone(null) != DependencyState.ADDED_DEP, - errorTransienceEntry); + if (!errorTransienceEntry.isDone()) { + injectValue( + ErrorTransienceValue.key(), + new ErrorTransienceValue(), + graphVersion, + graph, + dirtyKeyTracker); } for (SkyKey skyKey : skyKeys) { NodeEntry entry = graph.createIfAbsent(skyKey); @@ -1044,7 +1089,7 @@ public final class ParallelEvaluator implements Evaluator { case DONE: informProgressReceiverThatValueIsDone(skyKey); break; - case ADDED_DEP: + case ALREADY_EVALUATING: break; default: throw new IllegalStateException(entry + " for " + skyKey + " in unknown state"); @@ -1135,7 +1180,7 @@ public final class ParallelEvaluator implements Evaluator { Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>(); boolean externalInterrupt = false; while (true) { - NodeEntry errorEntry = graph.get(errorKey); + NodeEntry errorEntry = Preconditions.checkNotNull(graph.get(errorKey), errorKey); Iterable<SkyKey> reverseDeps = errorEntry.isDone() ? errorEntry.getReverseDeps() : errorEntry.getInProgressReverseDeps(); @@ -1178,15 +1223,27 @@ public final class ParallelEvaluator implements Evaluator { bubbleParent, bubbleParentEntry, parentVersion, graphVersion); continue; } - // Arbitrarily pick the first in-flight parent. - Preconditions.checkState(visitor.isInflight(bubbleParent), - "errorKey: %s, errorEntry: %s, bubbleParent: %s, bubbleParentEntry: %s", errorKey, - errorEntry, bubbleParent, bubbleParentEntry); - parent = bubbleParent; - parentEntry = bubbleParentEntry; + if (visitor.isInflight(bubbleParent) + && bubbleParentEntry.getTemporaryDirectDeps().contains(errorKey)) { + // Only bubble up to parent if it's part of this build. If this node was dirtied and + // re-evaluated, but in a build without this parent, we may try to bubble up to that + // parent. Don't -- it's not part of the build. + // Similarly, the parent may not yet have requested this dep in its dirtiness-checking + // process. Don't bubble up to it in that case either. + parent = bubbleParent; + parentEntry = bubbleParentEntry; + break; + } + } + if (parent == null) { + Preconditions.checkState( + rootValues.contains(errorKey), + "Current key %s has to be a top-level key: %s, %s", + errorKey, + rootValues, + errorEntry); break; } - Preconditions.checkNotNull(parent, "%s %s", errorKey, bubbleErrorInfo); errorKey = parent; SkyFunction factory = skyFunctions.get(parent.functionName()); if (parentEntry.isDirty()) { @@ -1195,9 +1252,11 @@ public final class ParallelEvaluator implements Evaluator { // If this value's child was bubbled up to, it did not signal this value, and so we must // manually make it ready to build. parentEntry.signalDep(); - // Fall through to REBUILDING, since state is now REBUILDING. + // Fall through to NEEDS_REBUILDING, since state is now NEEDS_REBUILDING. + case NEEDS_REBUILDING: + maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(parent, parentEntry); + // Fall through to REBUILDING. case REBUILDING: - // Nothing to be done. break; default: throw new AssertionError(parent + " not in valid dirty state: " + parentEntry); @@ -1392,6 +1451,7 @@ public final class ParallelEvaluator implements Evaluator { } else if (!entry.isReady()) { removeIncompleteChildrenForCycle(key, entry, entry.getTemporaryDirectDeps()); } + maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry); Set<SkyKey> directDeps = entry.getTemporaryDirectDeps(); // Find out which children have errors. Similar logic to that in Evaluate#run(). List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(directDeps); @@ -1425,6 +1485,7 @@ public final class ParallelEvaluator implements Evaluator { // cycles, and this is the only missing one). Thus, it will not be removed below in // removeDescendantsOfCycleValue, so it is safe here to signal that it is done. entry.signalDep(); + maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry); } if (keepGoing) { // Any children of this node that we haven't already visited are not worth visiting, @@ -1560,6 +1621,7 @@ public final class ParallelEvaluator implements Evaluator { // that the entry can conceivably be ready if its cycleChild already found a different cycle // and was built. entry.signalDep(); + maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry); } Preconditions.checkState(entry.isReady(), "%s %s %s", key, cycleChild, entry); Iterator<SkyKey> it = toVisit.iterator(); @@ -1645,4 +1707,39 @@ public final class ParallelEvaluator implements Evaluator { private boolean isDoneForBuild(@Nullable NodeEntry entry) { return entry != null && entry.isDone(); } + + static void injectValue( + SkyKey key, + SkyValue value, + Version version, + EvaluableGraph graph, + DirtyKeyTracker dirtyKeyTracker) { + Preconditions.checkNotNull(value, key); + NodeEntry prevEntry = graph.createIfAbsent(key); + DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null); + Preconditions.checkState( + newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry); + if (prevEntry.isDirty()) { + Preconditions.checkState( + newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry); + // There was an existing entry for this key in the graph. + // Get the node in the state where it is able to accept a value. + + // Check that the previous node has no dependencies. Overwriting a value with deps with an + // injected value (which is by definition deps-free) needs a little additional bookkeeping + // (removing reverse deps from the dependencies), but more importantly it's something that + // we want to avoid, because it indicates confusion of input values and derived values. + Preconditions.checkState( + prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry); + // Put the node into a "rebuilding" state and verify that there were no dirty deps remaining. + Preconditions.checkState( + prevEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps().isEmpty(), + "%s %s", + key, + prevEntry); + } + prevEntry.setValue(value, version); + // Now that this key's injected value is set, it is no longer dirty. + dirtyKeyTracker.notDirty(key); + } } diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java index 807aa8c440..ed8d724af9 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java +++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java @@ -21,10 +21,14 @@ import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.common.collect.Sets; +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 @@ -46,13 +50,126 @@ public abstract class ReverseDepsUtil<T> { abstract void setSingleReverseDep(T container, boolean singleObject); - abstract void setReverseDepsToRemove(T container, List<SkyKey> object); + abstract void setDataToConsolidate(T container, Object dataToConsolidate); abstract Object getReverseDepsObject(T container); abstract boolean isSingleReverseDep(T container); - abstract List<SkyKey> getReverseDepsToRemove(T container); + abstract Object getDataToConsolidate(T container); + + private enum DataState { + NULL, + CHECK_ONLY, + BOTH + } + + private static class RDepsToCheckAndRemove { + // reverseDepstoCheck may be null, but not toRemove, because we store a bare list if + // we have only toCheck. + @Nullable List<SkyKey> toCheck; + List<SkyKey> toRemove; + + RDepsToCheckAndRemove(List<SkyKey> toCheck, List<SkyKey> toRemove) { + this.toCheck = toCheck; + this.toRemove = Preconditions.checkNotNull(toRemove); + } + + static RDepsToCheckAndRemove justRemove(List<SkyKey> toRemove) { + return new RDepsToCheckAndRemove(null, toRemove); + } + + static RDepsToCheckAndRemove replaceRemove( + RDepsToCheckAndRemove original, List<SkyKey> toRemove) { + return new RDepsToCheckAndRemove(original.toCheck, toRemove); + } + + static RDepsToCheckAndRemove replaceCheck( + RDepsToCheckAndRemove original, List<SkyKey> toCheck) { + return new RDepsToCheckAndRemove(toCheck, original.toRemove); + } + } + + private static DataState getDataState(Object reverseDepsToCheckAndRemove) { + if (reverseDepsToCheckAndRemove == null) { + return DataState.NULL; + } else if (reverseDepsToCheckAndRemove instanceof List) { + return DataState.CHECK_ONLY; + } else { + Preconditions.checkState( + reverseDepsToCheckAndRemove instanceof RDepsToCheckAndRemove, + reverseDepsToCheckAndRemove); + return DataState.BOTH; + } + } + + private void setReverseDepsToRemove(T container, List<SkyKey> toRemove) { + Object reverseDepsToCheckAndRemove = getDataToConsolidate(container); + switch (getDataState(reverseDepsToCheckAndRemove)) { + case NULL: + reverseDepsToCheckAndRemove = RDepsToCheckAndRemove.justRemove(toRemove); + break; + case CHECK_ONLY: + reverseDepsToCheckAndRemove = + new RDepsToCheckAndRemove(((List<SkyKey>) reverseDepsToCheckAndRemove), toRemove); + break; + case BOTH: + reverseDepsToCheckAndRemove = + RDepsToCheckAndRemove.replaceRemove( + (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toRemove); + break; + default: + throw new IllegalStateException(container + ", " + toRemove); + } + setDataToConsolidate(container, reverseDepsToCheckAndRemove); + } + + private void setReverseDepsToCheck(T container, List<SkyKey> toCheck) { + Object reverseDepsToCheckAndRemove = getDataToConsolidate(container); + switch (getDataState(reverseDepsToCheckAndRemove)) { + case NULL: + case CHECK_ONLY: + reverseDepsToCheckAndRemove = toCheck; + break; + case BOTH: + reverseDepsToCheckAndRemove = + RDepsToCheckAndRemove.replaceCheck( + (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toCheck); + break; + default: + throw new IllegalStateException(container + ", " + toCheck); + } + setDataToConsolidate(container, reverseDepsToCheckAndRemove); + } + + @Nullable + private List<SkyKey> getReverseDepsToRemove(T container) { + Object reverseDepsToCheckAndRemove = getDataToConsolidate(container); + switch (getDataState(reverseDepsToCheckAndRemove)) { + case NULL: + case CHECK_ONLY: + return null; + case BOTH: + return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toRemove; + default: + throw new IllegalStateException(reverseDepsToCheckAndRemove.toString()); + } + } + + @Nullable + private List<SkyKey> getReverseDepsToCheck(T container) { + Object reverseDepsToCheckAndRemove = getDataToConsolidate(container); + switch (getDataState(reverseDepsToCheckAndRemove)) { + case NULL: + return null; + case CHECK_ONLY: + return (List<SkyKey>) reverseDepsToCheckAndRemove; + case BOTH: + return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toCheck; + default: + throw new IllegalStateException(reverseDepsToCheckAndRemove.toString()); + } + } /** * We check that the reverse dependency is not already present. We only do that if reverseDeps is @@ -60,15 +177,22 @@ public abstract class ReverseDepsUtil<T> { */ void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) { if (isSingleReverseDep(container)) { - Preconditions.checkState(!getReverseDepsObject(container).equals(reverseDep), - "Reverse dep %s already present", reverseDep); + 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", reverseDep, asList); + Preconditions.checkState( + !asList.contains(reverseDep), + "Reverse dep %s already present in %s for %s", + reverseDep, + asList, + container); } } @@ -106,9 +230,29 @@ public abstract class ReverseDepsUtil<T> { } } - boolean reverseDepsIsEmpty(T container) { - return !isSingleReverseDep(container) - && ((List<SkyKey>) getReverseDepsObject(container)).isEmpty(); + void checkReverseDep(T container, SkyKey reverseDep) { + Object reverseDepsObject = getReverseDepsObject(container); + if (isSingleReverseDep(container)) { + Preconditions.checkState( + reverseDepsObject.equals(reverseDep), + "%s %s %s", + reverseDep, + reverseDepsObject, + container); + return; + } + List<SkyKey> asList = (List<SkyKey>) reverseDepsObject; + if (asList.size() < MAYBE_CHECK_THRESHOLD) { + Preconditions.checkState( + asList.contains(reverseDep), "%s not in %s for %s", reverseDep, asList, container); + } else { + List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container); + if (reverseDepsToCheck == null) { + reverseDepsToCheck = new ArrayList<>(); + setReverseDepsToCheck(container, reverseDepsToCheck); + } + reverseDepsToCheck.add(reverseDep); + } } /** @@ -122,7 +266,7 @@ public abstract class ReverseDepsUtil<T> { "toRemove: %s container: %s", reverseDep, container); - overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); + overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); return; } @SuppressWarnings("unchecked") @@ -138,7 +282,7 @@ public abstract class ReverseDepsUtil<T> { } ImmutableSet<SkyKey> getReverseDeps(T container) { - consolidateReverseDepsRemovals(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, @@ -155,19 +299,38 @@ public abstract class ReverseDepsUtil<T> { } } - void consolidateReverseDepsRemovals(T container) { - List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container); + void consolidateData(T container) { Object reverseDeps = getReverseDepsObject(container); + List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container); + List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container); + if (reverseDepsToRemove == null && reverseDepsToCheck == null) { + return; + } + Preconditions.checkState( + !isSingleReverseDep(container), + "We do not delay removals/checks for single lists: %s %s %s", + container, + reverseDepsToRemove, + reverseDepsToCheck); + @SuppressWarnings("unchecked") + List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; + // Should not happen, as we only create reverseDepsToRemove/Check in case we have at least one + // reverse dep to remove/check. + Preconditions.checkState( + !reverseDepsAsList.isEmpty(), + "Could not do delayed removal/check for %s elements from %s.\n" + + "Reverse deps to check: %s. Container: %s", + reverseDepsToRemove, + reverseDeps, + reverseDepsToCheck, + container); if (reverseDepsToRemove == null) { + Set<SkyKey> reverseDepsAsSet = new HashSet<>(reverseDepsAsList); + Preconditions.checkState( + reverseDepsAsSet.containsAll(reverseDepsToCheck), "%s %s", reverseDepsToCheck, container); + setDataToConsolidate(container, null); return; } - Preconditions.checkState(!isSingleReverseDep(container), - "We do not use reverseDepsToRemove for single lists: %s", container); - // Should not happen, as we only create reverseDepsToRemove in case we have at least one - // reverse dep to remove. - Preconditions.checkState((!((List<?>) reverseDeps).isEmpty()), - "Could not remove %s elements from %s.\nReverse deps to remove: %s. %s", - reverseDepsToRemove.size(), reverseDeps, reverseDepsToRemove, container); Set<SkyKey> toRemove = Sets.newHashSet(reverseDepsToRemove); int expectedRemovals = toRemove.size(); @@ -175,12 +338,13 @@ public abstract class ReverseDepsUtil<T> { "A reverse dependency tried to remove itself twice: %s. %s", reverseDepsToRemove, container); - @SuppressWarnings("unchecked") - List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; + Set<SkyKey> toCheck = + reverseDepsToCheck == null ? new HashSet<SkyKey>() : new HashSet<>(reverseDepsToCheck); List<SkyKey> newReverseDeps = Lists .newArrayListWithExpectedSize(Math.max(0, reverseDepsAsList.size() - expectedRemovals)); for (SkyKey reverseDep : reverseDepsAsList) { + toCheck.remove(reverseDep); if (!toRemove.contains(reverseDep)) { newReverseDeps.add(reverseDep); } @@ -188,6 +352,7 @@ public abstract class ReverseDepsUtil<T> { Preconditions.checkState(newReverseDeps.size() == reverseDepsAsList.size() - expectedRemovals, "Could not remove some elements from %s.\nReverse deps to remove: %s. %s", reverseDeps, toRemove, container); + Preconditions.checkState(toCheck.isEmpty(), "%s %s", toCheck, container); if (newReverseDeps.isEmpty()) { overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); @@ -196,14 +361,14 @@ public abstract class ReverseDepsUtil<T> { } else { overwriteReverseDepsList(container, newReverseDeps); } - setReverseDepsToRemove(container, null); + setDataToConsolidate(container, null); } String toString(T container) { return MoreObjects.toStringHelper("ReverseDeps") .add("reverseDeps", getReverseDepsObject(container)) .add("singleReverseDep", isSingleReverseDep(container)) - .add("reverseDepsToRemove", getReverseDepsToRemove(container)) + .add("dataToConsolidate", getDataToConsolidate(container)) .toString(); } diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java index 661b52141d..8cd16f0695 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java @@ -49,6 +49,15 @@ public interface ThinNodeEntry { void removeReverseDep(SkyKey reverseDep); /** + * 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} + */ + @ThreadSafe + void removeInProgressReverseDep(SkyKey reverseDep); + + /** * 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. */ @@ -80,11 +89,11 @@ public interface ThinNodeEntry { * the caller will only ever want to call {@code markDirty()} a second time if a transition from a * dirty-unchanged state to a dirty-changed state is required. * - * @return The direct deps of this entry, or null if the entry has already been marked - * dirty. In the latter case, the caller should abort its handling of this node, since another - * thread is already dealing with it. + * @return true if the node was previously clean, and false if it was already dirty. If it was + * already dirty, the caller should abort its handling of this node, since another thread is + * already dealing with it. */ @Nullable @ThreadSafe - Iterable<SkyKey> markDirty(boolean isChanged); + boolean markDirty(boolean isChanged); } |