Move signaledDeps to DirtyBuildingState
This requires using DirtyBuildingState also for the initial evaluation
of a node. As a side effect, this reduces the set of possible states,
which might make it easier to reason about the state.
States: previously, NodeEntry distinguished between initial evaluation
and incremental update, with 2 different states (just created / marked
and evaluating) for each case. With this change, the case distinction
goes away.
This subtly changes the semantics of isDirty(): previously, isDirty
returned false for new nodes; now it returns true for new nodes after
their computation is triggered.
This change should reduce memory consumption of InMemoryNodeEntry
objects per instance for nodes that are done, but at the expense of
additional temporary DirtyBuildingState instances for nodes that are
not done.
I am making this change in preparation for adding another field to the
dirty state, which would otherwise increase memory consumption of all
done nodes.
= Memory consumption
While this decreases the memory consumption of Skyframe nodes in the
done state, it also increases the memory consumption of Skyframe nodes
that have to be recomputed, especially for new nodes, but also for
incrementally updated nodes.
New nodes now have to allocate a DirtyBuildingState instance while they
are in-flight, and incrementally updated nodes now have an additional
field in the DirtyBuildingState. For incrementally updated nodes, the
difference is a wash - we save some in InMemoryNodeEntry and lose the
same amount in DirtyBuildingState.
For clean builds, whether or not this is a reduction in memory use
depends on the ratio of in-flight to done nodes. The higher the ratio,
the higher the memory consumption. Note that the ratio goes to zero at
the end of a build, so this is a strict win for memory consumption at
rest (i.e., between builds), and only a concern while Bazel is active.
For some representative target, I saw ratios of less than 25% at max
during the loading+analysis phase, and dropping off sharply as packages
were completed. During the execution phase, the ratio only barely got
above 10% and usually stayed below 5%.
Assuming a memory difference of 8 bytes per done node (since the Jvm
performs 8-byte alignment), and an increase of 24 bytes per in-flight
node, any ratio below 1/3 is a net win for post-gc memory consumption,
although at the cost of slightly higher gc pressure. This is clearly the
case from the numbers I collected.
For incremental builds, the number of invalidated and recomputed nodes
is usually much, much lower (I saw numbers as low as 0.02%), which
virtually guarantees that this change is a net win.
PiperOrigin-RevId: 233899818
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
index b3d5324..b200e95 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -671,19 +671,18 @@
Preconditions.checkState(
newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry);
if (prevEntry.isDirty()) {
+ // Get the node in the state where it is able to accept a value.
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.
+ // If there was a node in the graph before, 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.markRebuilding();
}
+ prevEntry.markRebuilding();
prevEntry.setValue(
value,
version,
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index 84e5ff7..7115951 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -199,9 +199,6 @@
}
private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) throws InterruptedException {
- if (!state.isDirty()) {
- return DirtyOutcome.NEEDS_EVALUATION;
- }
while (state.getDirtyState().equals(DirtyState.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.
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index b110ab0..977f31f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -21,6 +21,7 @@
import com.google.devtools.build.skyframe.ThinNodeEntry.DirtyType;
import java.util.List;
import java.util.Set;
+import javax.annotation.Nullable;
/**
* State for a node that has been dirtied, and will be checked to see if it needs re-evaluation, and
@@ -30,6 +31,17 @@
* package.
*/
public abstract class DirtyBuildingState {
+ private static final int NOT_EVALUATING_SENTINEL = -1;
+
+ static DirtyBuildingState create(
+ DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
+ return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue);
+ }
+
+ static DirtyBuildingState createNew() {
+ return new FullDirtyBuildingState(DirtyType.CHANGE, null, null);
+ }
+
/**
* The state of a dirty node. A node is marked dirty in the DirtyBuildingState constructor, and
* goes into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link
@@ -39,6 +51,29 @@
private DirtyState dirtyState;
/**
+ * The number of dependencies that are known to be done in a {@link NodeEntry}.
+ *
+ * <p>There is a potential check-then-act race here during evaluation, so we need to make sure
+ * that when this is increased, we always check if the new value is equal to the number of
+ * required dependencies, and if so, we must re-schedule the node for evaluation.
+ *
+ * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close
+ * succession, this node should be scheduled exactly once. 2) If a thread is still working on this
+ * node, it should not be scheduled.
+ *
+ * <p>To solve the first problem, the {@link NodeEntry#signalDep} method also returns if the node
+ * needs to be re-scheduled, and ensures that only one thread gets a true return value.
+ *
+ * <p>The second problem is solved by first adding the newly discovered deps to a node's {@link
+ * InMemoryNodeEntry#directDeps}, and then looping through the direct deps and registering this
+ * node as a reverse dependency. This ensures that the signaledDeps counter can only reach {@link
+ * InMemoryNodeEntry#directDeps#numElements} on the very last iteration of the loop, i.e., the
+ * thread is not working on the node anymore. Note that this requires that there is no code after
+ * the loop in {@link ParallelEvaluator.Evaluate#run}.
+ */
+ private int signaledDeps = NOT_EVALUATING_SENTINEL;
+
+ /**
* The dependencies requested (with group markers) last time the node was built (and below, the
* value last time the node was built). They will be compared to dependencies requested on this
* build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
@@ -47,6 +82,7 @@
*
* <p>Public only for the use of alternative graph implementations.
*/
+ @Nullable
public abstract GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException;
/**
@@ -64,12 +100,13 @@
*
* <p>Public only for the use of alternative graph implementations.
*/
+ @Nullable
public abstract SkyValue getLastBuildValue() throws InterruptedException;
/**
* Group of children to be checked next in the process of determining if this entry needs to be
* re-evaluated. Used by {@link DirtyBuildingState#getNextDirtyDirectDeps} and {@link
- * #signalDepInternal}.
+ * #signalDepPostProcess}.
*/
protected int dirtyDirectDepIndex;
@@ -80,10 +117,8 @@
dirtyDirectDepIndex = 0;
}
- static DirtyBuildingState create(
- DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
- return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue);
- }
+ /** Returns true if this state does have information about a previously built version. */
+ protected abstract boolean isDirty();
final void markChanged() {
Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
@@ -97,7 +132,8 @@
}
}
- final void forceRebuild() {
+ final void forceRebuild(int numTemporaryDirectDeps) {
+ Preconditions.checkState(numTemporaryDirectDeps == signaledDeps, this);
Preconditions.checkState(
(dirtyState == DirtyState.CHECK_DEPENDENCIES
&& getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex)
@@ -106,6 +142,10 @@
dirtyState = DirtyState.FORCED_REBUILDING;
}
+ final boolean isEvaluating() {
+ return signaledDeps > NOT_EVALUATING_SENTINEL;
+ }
+
final boolean isChanged() {
return dirtyState == DirtyState.NEEDS_REBUILDING
|| dirtyState == DirtyState.NEEDS_FORCED_REBUILDING
@@ -122,6 +162,11 @@
this);
}
+ final void signalDep() {
+ Preconditions.checkState(isEvaluating());
+ signaledDeps++;
+ }
+
/**
* If this node is not yet known to need rebuilding, sets {@link #dirtyState} to {@link
* DirtyState#NEEDS_REBUILDING} if the child has changed, and {@link DirtyState#VERIFIED_CLEAN} if
@@ -129,7 +174,7 @@
* isReady} and comparing {@link #dirtyDirectDepIndex} and {@link
* DirtyBuildingState#getNumOfGroupsInLastBuildDirectDeps()}.
*/
- final void signalDepInternal(boolean childChanged, boolean isReady) {
+ final void signalDepPostProcess(boolean childChanged, int numTemporaryDirectDeps) {
Preconditions.checkState(
isChanged() || (dirtyState == DirtyState.CHECK_DEPENDENCIES && dirtyDirectDepIndex > 0),
"Unexpected not evaluating: %s",
@@ -140,7 +185,7 @@
if (childChanged) {
dirtyState = DirtyState.NEEDS_REBUILDING;
} else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
- && isReady
+ && isReady(numTemporaryDirectDeps)
&& getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex) {
// No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
// the last block of deps to be checked.
@@ -167,7 +212,9 @@
*/
public final boolean unchangedFromLastBuild(SkyValue newValue) throws InterruptedException {
checkFinishedBuildingWhenAboutToSetValue();
- return !(newValue instanceof NotComparableSkyValue) && getLastBuildValue().equals(newValue);
+ return !(newValue instanceof NotComparableSkyValue)
+ && getLastBuildValue() != null
+ && getLastBuildValue().equals(newValue);
}
/**
@@ -206,8 +253,10 @@
* process the returned set, and so subsequent calls to this method will return the empty set.
*/
Set<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) throws InterruptedException {
+ if (getLastBuildDirectDeps() == null) {
+ return ImmutableSet.of();
+ }
ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
-
for (int ind = dirtyDirectDepIndex; ind < getNumOfGroupsInLastBuildDirectDeps(); ind++) {
result.addAll(getLastBuildDirectDeps().get(ind));
}
@@ -220,6 +269,7 @@
final void resetForRestartFromScratch() {
Preconditions.checkState(
dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
+ signaledDeps = 0;
dirtyDirectDepIndex = 0;
}
@@ -228,13 +278,29 @@
dirtyState = DirtyState.REBUILDING;
}
+ void startEvaluating() {
+ Preconditions.checkState(!isEvaluating(), this);
+ signaledDeps = 0;
+ }
+
public int getLastDirtyDirectDepIndex() {
return dirtyDirectDepIndex - 1;
}
+ public int getSignaledDeps() {
+ return signaledDeps;
+ }
+
+ /** Returns whether all known children of this node have signaled that they are done. */
+ boolean isReady(int numDirectDeps) {
+ Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this);
+ return signaledDeps == numDirectDeps;
+ }
+
protected MoreObjects.ToStringHelper getStringHelper() {
return MoreObjects.toStringHelper(this)
.add("dirtyState", dirtyState)
+ .add("signaledDeps", signaledDeps)
.add("dirtyDirectDepIndex", dirtyDirectDepIndex);
}
@@ -259,6 +325,11 @@
}
@Override
+ protected boolean isDirty() {
+ return lastBuildDirectDeps != null;
+ }
+
+ @Override
public SkyValue getLastBuildValue() {
return lastBuildValue;
}
@@ -270,7 +341,7 @@
@Override
protected int getNumOfGroupsInLastBuildDirectDeps() {
- return lastBuildDirectDeps.listSize();
+ return lastBuildDirectDeps == null ? 0 : lastBuildDirectDeps.listSize();
}
@Override
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 bf76f6d..058a3dc 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -44,14 +44,9 @@
*
* <ol>
* <li>Non-existent
- * <li>Just created ({@link #isEvaluating} is false)
- * <li>Evaluating ({@link #isEvaluating} is true)
- * <li>Done ({@link #isDone} is true)
- * <li>Just created (when it is dirtied: {@link #dirtyBuildingState} is not null)
- * <li>Reset (just before it is re-evaluated: {@link #dirtyBuildingState#getDirtyState} returns
- * {@link DirtyState#NEEDS_REBUILDING})
- * <li>Evaluating
- * <li>Done
+ * <li>Just created or marked as affected ({@link #isDone} is false; {@link #isDirty} is false)
+ * <li>Evaluating ({@link #isDone} is false; {@link #isDirty} is true)
+ * <li>Done ({@link #isDone} is true; {@link #isDirty} is false)
* </ol>
*
* <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch} and
@@ -65,6 +60,8 @@
* that is never actually built (for instance, a dirty node that is verified as clean) is in the
* "evaluating" state until it is done.
*
+ * <p>From the "Done" state, the node can go back to the "marked as affected" state.
+ *
* <p>This class is public only for the benefit of alternative graph implementations outside of the
* package.
*/
@@ -141,31 +138,6 @@
*/
@Nullable protected volatile DirtyBuildingState dirtyBuildingState = null;
- private 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.
- * There is a potential check-then-act race here during evaluation, so we need to make sure that
- * when this is increased, we always check if the new value is equal to the number of required
- * dependencies, and if so, we must re-schedule the node for evaluation.
- *
- * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close
- * succession, this node should be scheduled exactly once. 2) If a thread is still working on this
- * node, it should not be scheduled.
- *
- * <p>The first problem is solved by the {@link #signalDep} method, which also returns if the node
- * needs to be re-scheduled, and ensures that only one thread gets a true return value.
- *
- * <p>The second problem is solved by first adding the newly discovered deps to a node's {@link
- * #directDeps}, and then looping through the direct deps and registering this node as a reverse
- * dependency. This ensures that the signaledDeps counter can only reach {@link
- * #directDeps#numElements} on the very last iteration of the loop, i.e., the 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}.
- */
- private int signaledDeps = NOT_EVALUATING_SENTINEL;
-
/**
* Construct a InMemoryNodeEntry. Use ONLY in Skyframe evaluation and graph implementations.
*/
@@ -181,9 +153,30 @@
return keepEdges() == KeepEdgesPolicy.ALL;
}
+ private boolean isEvaluating() {
+ return dirtyBuildingState != null;
+ }
+
@Override
public boolean isDone() {
- return value != null && !isEvaluating();
+ return value != null && dirtyBuildingState == null;
+ }
+
+ @Override
+ public synchronized boolean isReady() {
+ Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
+ Preconditions.checkState(isEvaluating(), this);
+ return dirtyBuildingState.isReady(getNumTemporaryDirectDeps());
+ }
+
+ @Override
+ public synchronized boolean isDirty() {
+ return !isDone() && dirtyBuildingState != null;
+ }
+
+ @Override
+ public synchronized boolean isChanged() {
+ return !isDone() && dirtyBuildingState != null && dirtyBuildingState.isChanged();
}
@Override
@@ -205,7 +198,7 @@
} else if (isChanged() || isDirty()) {
SkyValue lastBuildValue = null;
try {
- lastBuildValue = getDirtyBuildingState().getLastBuildValue();
+ lastBuildValue = dirtyBuildingState.getLastBuildValue();
} catch (InterruptedException e) {
throw new IllegalStateException("Interruption unexpected: " + this, e);
}
@@ -243,17 +236,12 @@
return ValueWithMetadata.getMaybeErrorInfo(value);
}
- protected DirtyBuildingState getDirtyBuildingState() {
- return Preconditions.checkNotNull(dirtyBuildingState, "Didn't have state: %s", this);
- }
-
/**
* Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one may
* need to override the other.
*/
protected void markDone() {
dirtyBuildingState = null;
- signaledDeps = NOT_EVALUATING_SENTINEL;
}
protected final synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
@@ -311,13 +299,12 @@
if (!isEligibleForChangePruningOnUnchangedValue()) {
this.lastChangedVersion = version;
this.value = value;
- } else if (isDirty() && getDirtyBuildingState().unchangedFromLastBuild(value)) {
+ } else if (dirtyBuildingState.unchangedFromLastBuild(value)) {
// If the value is the same as before, just use the old value. Note that we don't use the new
// value, because preserving == equality is even better than .equals() equality.
- this.value = getDirtyBuildingState().getLastBuildValue();
+ this.value = dirtyBuildingState.getLastBuildValue();
} else {
- boolean forcedRebuild =
- isDirty() && getDirtyBuildingState().getDirtyState() == DirtyState.FORCED_REBUILDING;
+ boolean forcedRebuild = dirtyBuildingState.getDirtyState() == DirtyState.FORCED_REBUILDING;
if (!forcedRebuild && this.lastChangedVersion.equals(version)) {
logError(
new ChangedValueAtSameVersionException(this.lastChangedVersion, version, value, this));
@@ -378,8 +365,9 @@
@Override
public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
+ boolean done = isDone();
if (reverseDep != null) {
- if (isDone()) {
+ if (done) {
if (keepReverseDeps()) {
ReverseDepsUtility.addReverseDeps(this, ImmutableList.of(reverseDep));
}
@@ -387,12 +375,15 @@
appendToReverseDepOperations(reverseDep, Op.ADD);
}
}
- if (isDone()) {
+ if (done) {
return DependencyState.DONE;
}
- boolean result = !isEvaluating();
+ if (dirtyBuildingState == null) {
+ dirtyBuildingState = DirtyBuildingState.createNew();
+ }
+ boolean result = !dirtyBuildingState.isEvaluating();
if (result) {
- signaledDeps = 0;
+ dirtyBuildingState.startEvaluating();
}
return result ? DependencyState.NEEDS_SCHEDULING : DependencyState.ALREADY_EVALUATING;
}
@@ -431,8 +422,15 @@
reverseDepsDataToConsolidate.add(KeyToConsolidate.create(reverseDep, op, getOpToStoreBare()));
}
+ /**
+ * In order to reduce memory consumption, we want to store reverse deps 'bare', i.e., without
+ * wrapping them in a KeyToConsolidate object. To that end, we define a bare op that is used for
+ * both storing and retrieving the deps. This method returns said op, and may adjust it depending
+ * on whether this is a new node entry (where all deps must be new) or an existing node entry
+ * (which most likely checks deps rather than adding new deps).
+ */
protected OpToStoreBare getOpToStoreBare() {
- return isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD;
+ return isDirty() && dirtyBuildingState.isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD;
}
@Override
@@ -494,26 +492,15 @@
public synchronized boolean signalDep(Version childVersion, @Nullable SkyKey childForDebugging) {
Preconditions.checkState(
!isDone(), "Value must not be done in signalDep %s child=%s", this, childForDebugging);
- Preconditions.checkState(isEvaluating(), "%s %s", this, childForDebugging);
- signaledDeps++;
- if (isDirty()) {
- dirtyBuildingState.signalDepInternal(
- childCausesReevaluation(lastEvaluatedVersion, childVersion, childForDebugging),
- isReady());
- }
+ Preconditions.checkNotNull(dirtyBuildingState, "%s %s", this, childForDebugging);
+ Preconditions.checkState(dirtyBuildingState.isEvaluating(), "%s %s", this, childForDebugging);
+ dirtyBuildingState.signalDep();
+ dirtyBuildingState.signalDepPostProcess(
+ childCausesReevaluation(lastEvaluatedVersion, childVersion, childForDebugging),
+ getNumTemporaryDirectDeps());
return isReady();
}
- @Override
- public synchronized boolean isDirty() {
- return !isDone() && dirtyBuildingState != null;
- }
-
- @Override
- public synchronized boolean isChanged() {
- return !isDone() && dirtyBuildingState != null && dirtyBuildingState.isChanged();
- }
-
/** Checks that a caller is not trying to access not-stored graph edges. */
private void assertKeepDeps() {
Preconditions.checkState(keepEdges() != KeepEdgesPolicy.NONE, "Not keeping deps: %s", this);
@@ -536,7 +523,8 @@
return new MarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this));
}
if (dirtyType.equals(DirtyType.FORCE_REBUILD)) {
- getDirtyBuildingState().markForceRebuild();
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ dirtyBuildingState.markForceRebuild();
return null;
}
// The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
@@ -549,19 +537,21 @@
this);
Preconditions.checkState(value == null, "Value should have been reset already %s", this);
if (dirtyType.equals(DirtyType.CHANGE)) {
+ Preconditions.checkNotNull(dirtyBuildingState);
// 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.
- getDirtyBuildingState().markChanged();
+ dirtyBuildingState.markChanged();
}
return null;
}
@Override
public synchronized Set<SkyKey> markClean() throws InterruptedException {
- this.value = getDirtyBuildingState().getLastBuildValue();
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ this.value = Preconditions.checkNotNull(dirtyBuildingState.getLastBuildValue());
Preconditions.checkState(isReady(), "Should be ready when clean: %s", this);
Preconditions.checkState(
- getDirtyBuildingState().depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
+ dirtyBuildingState.depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
"Direct deps must be the same as those found last build for node to be marked clean: %s",
this);
Preconditions.checkState(isDirty(), this);
@@ -571,8 +561,9 @@
@Override
public synchronized void forceRebuild() {
- Preconditions.checkState(getNumTemporaryDirectDeps() == signaledDeps, this);
- getDirtyBuildingState().forceRebuild();
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ Preconditions.checkState(isEvaluating(), this);
+ dirtyBuildingState.forceRebuild(getNumTemporaryDirectDeps());
}
@Override
@@ -582,16 +573,18 @@
@Override
public synchronized NodeEntry.DirtyState getDirtyState() {
- Preconditions.checkState(isEvaluating(), "Not evaluating for dirty state? %s", this);
- return getDirtyBuildingState().getDirtyState();
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ return dirtyBuildingState.getDirtyState();
}
/** @see DirtyBuildingState#getNextDirtyDirectDeps() */
@Override
public synchronized List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
Preconditions.checkState(isReady(), this);
- Preconditions.checkState(isEvaluating(), "Not evaluating during getNextDirty? %s", this);
- return getDirtyBuildingState().getNextDirtyDirectDeps();
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ Preconditions.checkState(
+ dirtyBuildingState.isEvaluating(), "Not evaluating during getNextDirty? %s", this);
+ return dirtyBuildingState.getNextDirtyDirectDeps();
}
@Override
@@ -606,20 +599,21 @@
for (Iterable<SkyKey> group : getTemporaryDirectDeps()) {
result.addAll(group);
}
- result.addAll(
- getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
+ result.addAll(dirtyBuildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
return result.build();
}
}
@Override
public synchronized Set<SkyKey> getAllRemainingDirtyDirectDeps() throws InterruptedException {
- Preconditions.checkState(isEvaluating(), "Not evaluating for remaining dirty? %s", this);
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ Preconditions.checkState(
+ dirtyBuildingState.isEvaluating(), "Not evaluating for remaining dirty? %s", this);
if (isDirty()) {
- DirtyState dirtyState = getDirtyBuildingState().getDirtyState();
+ DirtyState dirtyState = dirtyBuildingState.getDirtyState();
Preconditions.checkState(
dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
- return getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
+ return dirtyBuildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
} else {
return ImmutableSet.of();
}
@@ -655,7 +649,8 @@
@Override
public synchronized void markRebuilding() {
- getDirtyBuildingState().markRebuilding(isEligibleForChangePruningOnUnchangedValue());
+ Preconditions.checkNotNull(dirtyBuildingState, this);
+ dirtyBuildingState.markRebuilding(isEligibleForChangePruningOnUnchangedValue());
}
@SuppressWarnings("unchecked")
@@ -675,7 +670,8 @@
@Override
public synchronized boolean noDepsLastBuild() {
- return getDirtyBuildingState().noDepsLastBuild();
+ Preconditions.checkState(isEvaluating(), this);
+ return dirtyBuildingState.noDepsLastBuild();
}
/**
@@ -693,11 +689,9 @@
@Override
public synchronized void resetForRestartFromScratch() {
Preconditions.checkState(!isDone(), "Reset entry can't be done: %s", this);
+ Preconditions.checkState(isEvaluating());
directDeps = null;
- signaledDeps = 0;
- if (dirtyBuildingState != null) {
- dirtyBuildingState.resetForRestartFromScratch();
- }
+ dirtyBuildingState.resetForRestartFromScratch();
}
@Override
@@ -712,18 +706,6 @@
getTemporaryDirectDeps().appendGroup(group);
}
- @Override
- public synchronized boolean isReady() {
- Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
- return isReady(getNumTemporaryDirectDeps());
- }
-
- /** Returns whether all known children of this node have signaled that they are done. */
- private boolean isReady(int numDirectDeps) {
- Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this);
- return signaledDeps == numDirectDeps;
- }
-
/** True if the child should cause re-evaluation of this node. */
protected boolean childCausesReevaluation(
Version lastEvaluatedVersion,
@@ -733,18 +715,10 @@
return !childVersion.atMost(lastEvaluatedVersion);
}
- protected int getSignaledDeps() {
- return signaledDeps;
- }
-
protected void logError(RuntimeException error) {
throw error;
}
- private boolean isEvaluating() {
- return signaledDeps > NOT_EVALUATING_SENTINEL;
- }
-
protected synchronized MoreObjects.ToStringHelper toStringHelper() {
return MoreObjects.toStringHelper(this)
.add("identity", System.identityHashCode(this))
@@ -756,7 +730,6 @@
isDone() && keepEdges() != KeepEdgesPolicy.NONE
? GroupedList.create(directDeps)
: directDeps)
- .add("signaledDeps", signaledDeps)
.add("reverseDeps", ReverseDepsUtility.toString(this))
.add("dirtyBuildingState", dirtyBuildingState);
}
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 4e11b93..cffbc22 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -32,8 +32,8 @@
boolean isDone();
/**
- * Returns true if the entry is marked dirty, meaning that at least one of its transitive
- * dependencies is marked changed.
+ * Returns true if the entry is new or marked as dirty. This includes the case where its deps are
+ * still being checked for up-to-dateness.
*/
@ThreadSafe
boolean isDirty();
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 216d077..e541316 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -210,6 +210,7 @@
}
waitForStart.countDown();
waitForAddedRdep.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+ entry.markRebuilding();
entry.setValue(new StringValue("foo1"), startingVersion, null);
waitForSetValue.countDown();
wrapper.waitForTasksAndMaybeThrow();
@@ -280,6 +281,7 @@
// NEEDS_SCHEDULING at most once.
try {
if (startEvaluation(entry).equals(DependencyState.NEEDS_SCHEDULING)) {
+ entry.markRebuilding();
assertThat(valuesSet.add(key)).isTrue();
// Set to done.
entry.setValue(new StringValue("bar" + keyNum), startingVersion, null);
@@ -332,6 +334,7 @@
for (int i = 0; i < numKeys; i++) {
NodeEntry entry = entries.get(key("foo" + i));
startEvaluation(entry);
+ entry.markRebuilding();
entry.setValue(new StringValue("bar"), startingVersion, null);
}
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 6e8fb52..a344ab2 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -61,8 +61,8 @@
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
assertThat(entry.isDone()).isFalse();
assertThat(entry.isReady()).isTrue();
- assertThat(entry.isDirty()).isFalse();
- assertThat(entry.isChanged()).isFalse();
+ assertThat(entry.isDirty()).isTrue();
+ assertThat(entry.isChanged()).isTrue();
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
}
@@ -73,6 +73,7 @@
public void signalEntry() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep1 = key("dep1");
addTemporaryDirectDep(entry, dep1);
assertThat(entry.isReady()).isFalse();
@@ -106,6 +107,7 @@
.isEqualTo(DependencyState.ALREADY_EVALUATING);
assertThat(entry.addReverseDepAndCheckIfDone(father))
.isEqualTo(DependencyState.ALREADY_EVALUATING);
+ entry.markRebuilding();
assertThat(setValue(entry, new SkyValue() {},
/*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father);
assertThat(entry.getReverseDepsForDoneEntry()).containsExactly(mother, father);
@@ -118,6 +120,7 @@
public void errorValue() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
key("cause"));
@@ -132,6 +135,7 @@
public void errorAndValue() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
key("cause"));
@@ -145,6 +149,7 @@
public void crashOnNullErrorAndValue() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
try {
setValue(entry, /*value=*/null, /*errorInfo=*/null, /*graphVersion=*/0L);
fail();
@@ -157,6 +162,7 @@
public void crashOnTooManySignals() {
InMemoryNodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
try {
entry.signalDep(ZERO_VERSION, null);
fail();
@@ -169,6 +175,7 @@
public void crashOnSetValueWhenDone() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
assertThat(entry.isDone()).isTrue();
try {
@@ -183,6 +190,7 @@
public void crashOnChangedValueAtSameVersion() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null);
+ entry.markRebuilding();
setValue(entry, new IntegerValue(1), /*errorInfo=*/ null, /*graphVersion=*/ 0L);
entry.markDirty(DirtyType.CHANGE);
entry.addReverseDepAndCheckIfDone(null);
@@ -199,6 +207,7 @@
public void dirtyLifecycle() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -223,14 +232,15 @@
assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
assertThat(entry.isReady()).isTrue();
entry.markRebuilding();
- assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
- /*graphVersion=*/1L)).containsExactly(parent);
+ assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 1L))
+ .containsExactly(parent);
}
@Test
public void changedLifecycle() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -260,6 +270,7 @@
public void forceRebuildLifecycle() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -295,6 +306,7 @@
public void markDirtyThenChanged() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -320,6 +332,7 @@
public void markChangedThenDirty() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -344,6 +357,7 @@
public void crashOnTwiceMarkedChanged() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
assertThat(entry.isDirty()).isFalse();
assertThat(entry.isDone()).isTrue();
@@ -360,6 +374,7 @@
public void crashOnTwiceMarkedDirty() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -377,6 +392,7 @@
public void allowTwiceMarkedForceRebuild() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
assertThat(entry.isDirty()).isFalse();
assertThat(entry.isDone()).isTrue();
@@ -395,6 +411,7 @@
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
try {
entry.addReverseDepAndCheckIfDone(parent);
+ entry.markRebuilding();
assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L))
.containsExactly(parent);
fail("Cannot add same dep twice");
@@ -407,6 +424,7 @@
public void crashOnAddReverseDepTwiceAfterDone() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
SkyKey parent = key("parent");
assertThat(entry.addReverseDepAndCheckIfDone(parent)).isEqualTo(DependencyState.DONE);
@@ -426,6 +444,7 @@
SkyKey parent = key("parent");
assertThat(entry.addReverseDepAndCheckIfDone(parent))
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
try {
entry.addReverseDepAndCheckIfDone(parent);
@@ -442,6 +461,7 @@
NodeEntry entry = new InMemoryNodeEntry();
SkyKey dep = key("dep");
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
@@ -489,6 +509,7 @@
public void pruneAfterBuild() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -512,6 +533,7 @@
public void noPruneWhenDetailsChange() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -550,6 +572,7 @@
public void pruneWhenDepGroupReordered() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
SkyKey dep1InGroup = key("dep1InGroup");
SkyKey dep2InGroup = key("dep2InGroup");
@@ -591,6 +614,7 @@
public void errorInfoCannotBePruned() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -636,6 +660,7 @@
public void getDependencyGroup() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
SkyKey dep2 = key("dep2");
SkyKey dep3 = key("dep3");
@@ -660,6 +685,7 @@
public void maintainDependencyGroupAfterRemoval() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
SkyKey dep2 = key("dep2");
SkyKey dep3 = key("dep3");
@@ -690,6 +716,7 @@
public void pruneWhenDepsChange() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
SkyKey dep = key("dep");
addTemporaryDirectDep(entry, dep);
entry.signalDep(ZERO_VERSION, dep);
@@ -714,6 +741,7 @@
public void checkDepsOneByOne() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+ entry.markRebuilding();
List<SkyKey> deps = new ArrayList<>();
for (int ii = 0; ii < 10; ii++) {
SkyKey dep = key(Integer.toString(ii));
@@ -741,12 +769,14 @@
public void signalOnlyNewParents() throws InterruptedException {
NodeEntry entry = new InMemoryNodeEntry();
entry.addReverseDepAndCheckIfDone(key("parent"));
+ entry.markRebuilding();
setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
entry.markDirty(DirtyType.CHANGE);
SkyKey newParent = key("new parent");
entry.addReverseDepAndCheckIfDone(newParent);
assertThat(entry.getDirtyState()).isEqualTo(NodeEntry.DirtyState.NEEDS_REBUILDING);
entry.markRebuilding();
+ assertThat(entry.getDirtyState()).isEqualTo(NodeEntry.DirtyState.REBUILDING);
assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
/*graphVersion=*/1L)).containsExactly(newParent);
}
@@ -760,6 +790,7 @@
assertThatNodeEntry(entry)
.addReverseDepAndCheckIfDone(null)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
+ entry.markRebuilding();
addTemporaryDirectDep(entry, originalChild);
entry.signalDep(ZERO_VERSION, originalChild);
entry.setValue(originalValue, version, null);
@@ -806,6 +837,7 @@
assertThatNodeEntry(entry)
.addReverseDepAndCheckIfDone(null)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
+ entry.markRebuilding();
for (Set<SkyKey> depGroup : groupedDirectDeps) {
GroupedListHelper<SkyKey> helper = new GroupedListHelper<>();
helper.startGroup();
