Improve the specification and implementation of `NodeEntry#toValue`.
The only semantic change is that a `NonIncrementalInMemoryNodeEntry` that is rewound stores its previous value so that `toValue()` can return it while it is rewinding. This is consistent with how an `IncrementalInMemoryNodeEntry` already works, and since the implementation is now the same, `toValue()` is moved to the shared `AbstractInMemoryNodeEntry`.
The motivation for this is b/314117358: currently, `ArtifactNestedSetFunction` maintains a big map of built artifacts that is mostly redundant with data in the Skyframe graph. One exception is that currently artifacts in the big map are not evicted when their generating action is rewound, so a simultaneously executing action can still read them. Allowing `toValue()` to return a non-null value even for a rewound node makes it work consistently with how the big artifact map is currently used.
An alternative is to treat an unexpectedly-null value as a "lost input" under the assumption that it was rewound, and do more rewinding to recover from that. This may be more principled, however it is much more difficult to implement (we'd need to introduce the possibility of lost inputs before even attempting to executing the action) and is also inferior in the case of an action that generates multiple outputs: if only one output is lost, the entire action is rewound, although another output may still be available. In this case, the alternative approach could result in more rewinding than necessary.
Assertions for `toValue()` are peppered around various unit tests, and one new unit test case is added for the possibility of a node that is rewound and then reset.
PiperOrigin-RevId: 588122054
Change-Id: Ic3f4d7acff85fa626f13430658b7b832763955b1
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryNodeEntry.java
index 470b24e..3fc16be 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryNodeEntry.java
@@ -133,6 +133,29 @@
@Override
@Nullable
+ public final SkyValue toValue() {
+ SkyValue lastBuildValue = value;
+ if (lastBuildValue == null) {
+ synchronized (this) {
+ if (value != null) {
+ lastBuildValue = value;
+ } else if (dirtyBuildingState != null) {
+ try {
+ lastBuildValue = dirtyBuildingState.getLastBuildValue();
+ } catch (InterruptedException e) {
+ throw new IllegalStateException("Interruption unexpected: " + this, e);
+ }
+ } else {
+ return null; // An evaluation was never started.
+ }
+ }
+ }
+
+ return lastBuildValue != null ? ValueWithMetadata.justValue(lastBuildValue) : null;
+ }
+
+ @Override
+ @Nullable
public final synchronized ErrorInfo getErrorInfo() {
checkState(isDone(), "no errors until done. NodeEntry: %s", this);
return ValueWithMetadata.getMaybeErrorInfo(value);
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 66c6af9..b664dfb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -25,8 +25,9 @@
/**
* State for a node that either has not been built yet or has been dirtied.
*
- * <p>If the node has previously been built, {@link #isIncremental} returns true. Deps are checked
- * to see if re-evaluation is needed, and the node will either marked clean or re-evaluated.
+ * <p>If the node has previously been built and the state tracks the previous value and dependencies
+ * for purposes of pruning, {@link #isIncremental} returns true. Deps are checked to see if
+ * re-evaluation is needed, and the node will either marked clean or re-evaluated.
*
* <p>This class does not attempt to synchronize operations. It is assumed that the calling {@link
* InMemoryNodeEntry} performs the appropriate synchronization when necessary.
diff --git a/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java
index 08af9dc..a87bfad 100644
--- a/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java
@@ -88,29 +88,6 @@
return true;
}
- @Nullable
- @Override
- public SkyValue toValue() {
- SkyValue lastBuildValue = value;
- if (lastBuildValue == null) {
- synchronized (this) {
- if (value != null) {
- lastBuildValue = value;
- } else if (dirtyBuildingState != null) {
- try {
- lastBuildValue = dirtyBuildingState.getLastBuildValue();
- } catch (InterruptedException e) {
- throw new IllegalStateException("Interruption unexpected: " + this, e);
- }
- } else {
- return null; // An evaluation was never started.
- }
- }
- }
-
- return lastBuildValue != null ? ValueWithMetadata.justValue(lastBuildValue) : null;
- }
-
@Override
public Iterable<SkyKey> getDirectDeps() {
return GroupedDeps.compressedToIterable(getCompressedDirectDepsForDoneEntry());
diff --git a/src/main/java/com/google/devtools/build/skyframe/InitialBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/InitialBuildingState.java
index 5be44d9..f1b6c71 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InitialBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InitialBuildingState.java
@@ -18,7 +18,7 @@
/**
* {@link DirtyBuildingState} for a node on its initial build or a {@link
- * NonIncrementalInMemoryNodeEntry} being {@linkplain NodeEntry#forceRebuild force rebuilt}.
+ * NonIncrementalInMemoryNodeEntry} that was {@linkplain DirtyType#REWIND rewound}.
*/
class InitialBuildingState extends DirtyBuildingState {
@@ -39,7 +39,7 @@
@Nullable
@Override
- public final SkyValue getLastBuildValue() {
+ public SkyValue getLastBuildValue() {
return null;
}
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 7449e5f..942f321 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -290,8 +290,14 @@
@Nullable
SkyValue getValueMaybeWithMetadata() throws InterruptedException;
- /** Returns the value, even if dirty or changed. Returns null otherwise. */
+ /**
+ * Returns the last known value of this node, even if it was {@linkplain #markDirty marked dirty}.
+ *
+ * <p>Unlike {@link #getValue}, this method may be called at any point in the node's lifecycle.
+ * Returns {@code null} if this node was never built or has no value because it is in error.
+ */
@ThreadSafe
+ @Nullable
SkyValue toValue() throws InterruptedException;
/**
diff --git a/src/main/java/com/google/devtools/build/skyframe/NonIncrementalInMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NonIncrementalInMemoryNodeEntry.java
index 8e84aaa..fe1c492 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NonIncrementalInMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NonIncrementalInMemoryNodeEntry.java
@@ -65,12 +65,6 @@
}
@Override
- @Nullable
- public final SkyValue toValue() {
- return ValueWithMetadata.justValue(value);
- }
-
- @Override
@CanIgnoreReturnValue
public final DependencyState addReverseDepAndCheckIfDone(@Nullable SkyKey reverseDep) {
// Fast path check before locking. If this node is already done, there is nothing to do since we
@@ -121,7 +115,11 @@
@Override
public final synchronized void resetEvaluationFromScratch() {
checkState(!hasUnsignaledDeps(), this);
- var newBuildingState = new NonIncrementalBuildingState();
+ SkyValue rewoundValue = dirtyBuildingState.getLastBuildValue();
+ var newBuildingState =
+ rewoundValue == null
+ ? new NonIncrementalBuildingState()
+ : new RewoundNonIncrementalBuildingState(rewoundValue);
newBuildingState.reverseDeps = dirtyBuildingState.reverseDeps;
newBuildingState.markRebuilding();
newBuildingState.startEvaluating();
@@ -149,7 +147,7 @@
if (!isDone()) {
return null; // Tolerate concurrent requests to rewind.
}
- dirtyBuildingState = new NonIncrementalBuildingState();
+ dirtyBuildingState = new RewoundNonIncrementalBuildingState(value);
value = null;
return MarkedDirtyResult.forRewinding();
}
@@ -241,33 +239,33 @@
* in {@link NonIncrementalInMemoryNodeEntry} since they are not needed after the node is done.
* This way we don't pay the memory cost of the fields for a done node.
*/
- static final class NonIncrementalBuildingState extends InitialBuildingState {
+ static class NonIncrementalBuildingState extends InitialBuildingState {
@Nullable private GroupedDeps directDeps = null;
@Nullable private List<SkyKey> reverseDeps = null;
private NonIncrementalBuildingState() {}
- GroupedDeps getTemporaryDirectDeps(NonIncrementalInMemoryNodeEntry entry) {
+ final GroupedDeps getTemporaryDirectDeps(NonIncrementalInMemoryNodeEntry entry) {
if (directDeps == null) {
directDeps = entry.newGroupedDeps();
}
return directDeps;
}
- void addReverseDep(SkyKey reverseDep) {
+ final void addReverseDep(SkyKey reverseDep) {
if (reverseDeps == null) {
reverseDeps = new ArrayList<>();
}
reverseDeps.add(reverseDep);
}
- void removeReverseDep(SkyKey reverseDep) {
+ final void removeReverseDep(SkyKey reverseDep) {
// Reverse dep removal on a non-incremental node is rare (only for cycles), so we can live
// with inefficiently calling remove on an ArrayList.
checkState(reverseDeps.remove(reverseDep), "Reverse dep not present: %s", reverseDep);
}
- ImmutableSet<SkyKey> getReverseDeps(NonIncrementalInMemoryNodeEntry entry) {
+ final ImmutableSet<SkyKey> getReverseDeps(NonIncrementalInMemoryNodeEntry entry) {
if (reverseDeps == null) {
return ImmutableSet.of();
}
@@ -281,4 +279,28 @@
return super.getStringHelper().add("directDeps", directDeps).add("reverseDeps", reverseDeps);
}
}
+
+ /**
+ * State for a non-incremental node that was previously {@linkplain #isDone done} but was
+ * {@linkplain com.google.devtools.build.skyframe.NodeEntry.DirtyType#REWIND rewound}. Stores the
+ * previously built value for the sole purpose of servicing {@link #toValue}.
+ */
+ private static final class RewoundNonIncrementalBuildingState
+ extends NonIncrementalBuildingState {
+ private final SkyValue rewoundValue;
+
+ RewoundNonIncrementalBuildingState(SkyValue rewoundValue) {
+ this.rewoundValue = rewoundValue;
+ }
+
+ @Override
+ public SkyValue getLastBuildValue() {
+ return rewoundValue;
+ }
+
+ @Override
+ protected MoreObjects.ToStringHelper getStringHelper() {
+ return super.getStringHelper().add("rewoundValue", rewoundValue);
+ }
+ }
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
index f8d0cb9..0336bb4 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -73,7 +73,7 @@
if (dirtyBuildingState == null) {
return Op.CHECK;
}
- return entry.keepsEdges() && dirtyBuildingState.isIncremental() ? Op.CHECK : Op.ADD;
+ return dirtyBuildingState.isIncremental() ? Op.CHECK : Op.ADD;
}
private static void maybeDelayReverseDepOp(
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 b9ff086..dd0b374 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -187,6 +187,7 @@
assertThat(entry.isDone()).isTrue();
assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.DONE);
assertThat(entry.getValue()).isNull();
+ assertThat(entry.toValue()).isNull();
assertThat(entry.getErrorInfo()).isEqualTo(errorInfo);
}
@@ -267,6 +268,11 @@
public int hashCode() {
return value;
}
+
+ @Override
+ public String toString() {
+ return "IntegerValue{" + value + "}";
+ }
}
@Test
@@ -441,11 +447,14 @@
.addReverseDepAndCheckIfDone(resetParent)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
entry.markRebuilding();
+
// Node completes.
- assertThat(setValue(entry, new IntegerValue(1), /* errorInfo= */ null, initialVersion))
+ SkyValue oldValue = new IntegerValue(1);
+ assertThat(setValue(entry, oldValue, /* errorInfo= */ null, initialVersion))
.containsExactly(resetParent);
assertThat(entry.isDirty()).isFalse();
assertThat(entry.isDone()).isTrue();
+
// Rewinding initiated.
entry.markDirty(DirtyType.REWIND);
assertThat(entry.isDirty()).isTrue();
@@ -453,6 +462,8 @@
assertThat(entry.isDone()).isFalse();
assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
.isEqualTo(isPartialReevaluation);
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
// Parent declares dep again after resetting.
var dependencyState =
entry.keepsEdges()
@@ -465,10 +476,77 @@
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
entry.markRebuilding();
assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.REBUILDING);
+
// Rewound evaluation completes. The parent that initiated rewinding is signalled.
- assertThat(setValue(entry, new IntegerValue(2), /* errorInfo= */ null, initialVersion))
+ SkyValue newValue = new IntegerValue(2);
+ assertThat(setValue(entry, newValue, /* errorInfo= */ null, initialVersion))
.containsExactly(resetParent);
- assertThat(entry.getValue()).isEqualTo(new IntegerValue(2));
+ assertThat(entry.getValue()).isEqualTo(newValue);
+ assertThat(entry.toValue()).isEqualTo(newValue);
+ assertThat(entry.getVersion()).isEqualTo(initialVersion);
+ }
+
+ @Test
+ public void resetAfterRewind() throws InterruptedException {
+ InMemoryNodeEntry entry = createEntry();
+ // Rdep that will eventually rewind the entry.
+ SkyKey resetParent = key("resetParent");
+ assertThatNodeEntry(entry)
+ .addReverseDepAndCheckIfDone(resetParent)
+ .isEqualTo(DependencyState.NEEDS_SCHEDULING);
+ entry.markRebuilding();
+
+ // One dep declared.
+ SkyKey dep = key("dep");
+ entry.addSingletonTemporaryDirectDep(dep);
+ entry.signalDep(initialVersion, dep);
+
+ // Node completes.
+ SkyValue oldValue = new IntegerValue(1);
+ assertThat(setValue(entry, oldValue, /* errorInfo= */ null, initialVersion))
+ .containsExactly(resetParent);
+ assertThat(entry.isDirty()).isFalse();
+ assertThat(entry.isDone()).isTrue();
+
+ // Rewinding initiated.
+ entry.markDirty(DirtyType.REWIND);
+ assertThat(entry.isDirty()).isTrue();
+ assertThat(entry.isChanged()).isTrue();
+ assertThat(entry.isDone()).isFalse();
+ assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
+ .isEqualTo(isPartialReevaluation);
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
+ // Parent declares dep again after resetting.
+ var dependencyState =
+ entry.keepsEdges()
+ ? entry.checkIfDoneForDirtyReverseDep(resetParent)
+ : entry.addReverseDepAndCheckIfDone(resetParent);
+ assertThat(dependencyState).isEqualTo(DependencyState.NEEDS_SCHEDULING);
+ assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.NEEDS_REBUILDING);
+ assertThat(entry.isReadyToEvaluate()).isTrue();
+ assertThat(entry.hasUnsignaledDeps()).isFalse();
+ assertThat(entry.getTemporaryDirectDeps()).isEmpty();
+ entry.markRebuilding();
+ assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.REBUILDING);
+
+ // Dep declared again, then there's a reset.
+ entry.addSingletonTemporaryDirectDep(dep);
+ entry.signalDep(initialVersion, dep);
+ entry.resetEvaluationFromScratch();
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
+ // Dep declared again post-reset.
+ entry.addSingletonTemporaryDirectDep(dep);
+ entry.signalDep(initialVersion, dep);
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
+ // Rewound evaluation completes. The parent that initiated rewinding is signalled.
+ SkyValue newValue = new IntegerValue(2);
+ assertThat(setValue(entry, newValue, /* errorInfo= */ null, initialVersion))
+ .containsExactly(resetParent);
+ assertThat(entry.getValue()).isEqualTo(newValue);
+ assertThat(entry.toValue()).isEqualTo(newValue);
assertThat(entry.getVersion()).isEqualTo(initialVersion);
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntryTest.java
index fa60384..512bcc7 100644
--- a/src/test/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntryTest.java
@@ -56,13 +56,17 @@
SkyKey dep = key("dep");
entry.addSingletonTemporaryDirectDep(dep);
entry.signalDep(initialVersion, dep);
- setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion);
+ SkyValue oldValue = new IntegerValue(1);
+ setValue(entry, oldValue, /* errorInfo= */ null, initialVersion);
assertThat(entry.isDirty()).isFalse();
assertThat(entry.isDone()).isTrue();
+
entry.markDirty(DirtyType.DIRTY);
assertThat(entry.isDirty()).isTrue();
assertThat(entry.isChanged()).isFalse();
assertThat(entry.isDone()).isFalse();
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
assertThatNodeEntry(entry)
.addReverseDepAndCheckIfDone(null)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
@@ -71,18 +75,22 @@
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
.isEqualTo(isPartialReevaluation);
+
SkyKey parent = key("parent");
entry.addReverseDepAndCheckIfDone(parent);
assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.CHECK_DEPENDENCIES);
+
assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
entry.addSingletonTemporaryDirectDep(dep);
entry.signalDep(incrementalVersion, dep);
assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
assertThat(entry.isReadyToEvaluate()).isTrue();
assertThat(entry.hasUnsignaledDeps()).isFalse();
+
entry.markRebuilding();
- assertThat(setValue(entry, new SkyValue() {}, /* errorInfo= */ null, incrementalVersion))
+ assertThat(setValue(entry, new IntegerValue(2), /* errorInfo= */ null, incrementalVersion))
.containsExactly(parent);
+ assertThat(entry.getVersion()).isEqualTo(incrementalVersion);
}
@Test
@@ -93,24 +101,30 @@
SkyKey dep = key("dep");
entry.addSingletonTemporaryDirectDep(dep);
entry.signalDep(initialVersion, dep);
- setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion);
+ SkyValue oldValue = new IntegerValue(1);
+ setValue(entry, oldValue, /* errorInfo= */ null, initialVersion);
assertThat(entry.isDirty()).isFalse();
assertThat(entry.isDone()).isTrue();
+
entry.markDirty(DirtyType.CHANGE);
assertThat(entry.isDirty()).isTrue();
assertThat(entry.isChanged()).isTrue();
assertThat(entry.isDone()).isFalse();
+ assertThat(entry.toValue()).isEqualTo(oldValue);
+
assertThatNodeEntry(entry)
.addReverseDepAndCheckIfDone(null)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
assertThat(entry.isReadyToEvaluate()).isTrue();
assertThat(entry.hasUnsignaledDeps()).isFalse();
+
SkyKey parent = key("parent");
entry.addReverseDepAndCheckIfDone(parent);
assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.NEEDS_REBUILDING);
assertThat(entry.isReadyToEvaluate()).isTrue();
assertThat(entry.hasUnsignaledDeps()).isFalse();
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
+
entry.markRebuilding();
assertThat(setValue(entry, new SkyValue() {}, /* errorInfo= */ null, incrementalVersion))
.containsExactly(parent);
@@ -745,12 +759,13 @@
entry.markRebuilding();
assertThat(entry.getResetDirectDeps()).isEmpty();
- // Reset clears temporary direct deps.
+ // Reset clears temporary direct deps, but preserves the dirty value.
entry.resetEvaluationFromScratch();
assertThat(entry.getLifecycleState()).isEqualTo(LifecycleState.REBUILDING);
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
.isEqualTo(isPartialReevaluation);
+ assertThat(entry.toValue()).isEqualTo(oldValue);
// Add back same dep.
entry.addSingletonTemporaryDirectDep(oldAndNewDep);
@@ -822,6 +837,7 @@
assertThat(entry.checkIfDoneForDirtyReverseDep(resetDirtyParent))
.isEqualTo(DependencyState.DONE);
assertThat(entry.markDirty(DirtyType.REWIND)).isNotNull();
+ assertThat(entry.toValue()).isEqualTo(oldValue);
// Parent declares dep again after resetting.
assertThat(entry.checkIfDoneForDirtyReverseDep(resetDirtyParent))
