Return rdeps when marking a node dirty
The thread that succeeds at marking a node dirty during invalidation
must then schedule that node's reverse deps for invalidation. Providing
the set of reverse deps as a return value from marking a node dirty
makes some future optimizations possible.
--
MOS_MIGRATED_REVID=108045473
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 637787a..326635d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -330,13 +330,13 @@
}
@Override
- public synchronized boolean markDirty(boolean isChanged) {
+ public synchronized MarkedDirtyResult markDirty(boolean isChanged) {
assertKeepEdges();
if (isDone()) {
buildingState =
BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
value = null;
- return true;
+ return new MarkedDirtyResult(REVERSE_DEPS_UTIL.getReverseDeps(this));
}
// The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
// thread may have lost the race, but it is the caller's responsibility not to try to mark
@@ -350,7 +350,7 @@
// other work was done by the dirty marker.
buildingState.markChanged();
}
- return false;
+ return null;
}
@Override
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 676b537..ab8e0dc 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -27,6 +27,7 @@
import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.util.Pair;
+import com.google.devtools.build.skyframe.ThinNodeEntry.MarkedDirtyResult;
import java.util.Collections;
import java.util.Map;
@@ -418,14 +419,15 @@
// It is not safe to interrupt the logic from this point until the end of the method.
// Any exception thrown should be unrecoverable.
// This entry remains in the graph in this dirty state until it is re-evaluated.
- if (!entry.markDirty(isChanged)) {
+ MarkedDirtyResult markedDirtyResult = entry.markDirty(isChanged);
+ if (markedDirtyResult == null) {
// 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).
- for (SkyKey reverseDep : entry.getReverseDeps()) {
+ for (SkyKey reverseDep : markedDirtyResult.getReverseDepsUnsafe()) {
visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST);
}
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 566bc50..55ec6cb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -89,11 +89,29 @@
* 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 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.
+ * @return A {@link ThinNodeEntry.MarkedDirtyResult} if the node was previously clean, and
+ * {@code null} 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
- boolean markDirty(boolean isChanged);
+ MarkedDirtyResult markDirty(boolean isChanged);
+
+ /**
+ * Returned by {@link #markDirty} if that call changed the node from clean to dirty. Contains an
+ * iterable of the node's reverse deps for efficiency, because the single use case for {@link
+ * #markDirty} is during invalidation, and if such an invalidation call wins, the invalidator
+ * must immediately afterwards schedule the invalidation of the node's reverse deps.
+ */
+ class MarkedDirtyResult {
+ private final Iterable<SkyKey> reverseDepsUnsafe;
+
+ public MarkedDirtyResult(Iterable<SkyKey> reverseDepsUnsafe) {
+ this.reverseDepsUnsafe = reverseDepsUnsafe;
+ }
+
+ public Iterable<SkyKey> getReverseDepsUnsafe() {
+ return reverseDepsUnsafe;
+ }
+ }
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
index 1ff4fce..d553dd1 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
@@ -106,6 +106,15 @@
AFTER
}
+ /**
+ * Note that the methods in this class intentionally do not have the {@code synchronized}
+ * keyword! Each of them invokes the synchronized method on {@link InMemoryNodeEntry} it
+ * overrides, which provides the required synchronization for state owned by that base class.
+ *
+ * <p>These methods are not synchronized because several test cases control the flow of
+ * execution by blocking until notified by the callbacks executed in these methods. If these
+ * overrides were synchronized, they wouldn't get the chance to execute these callbacks.
+ */
protected class NotifyingNodeEntry extends InMemoryNodeEntry {
private final SkyKey myKey;
@@ -113,8 +122,7 @@
myKey = key;
}
- // Note that these methods are not synchronized. Necessary synchronization happens when calling
- // the super() methods.
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
graphListener.accept(myKey, EventType.ADD_REVERSE_DEP, Order.BEFORE, reverseDep);
@@ -123,13 +131,15 @@
return result;
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
- public synchronized void removeReverseDep(SkyKey reverseDep) {
+ public void removeReverseDep(SkyKey reverseDep) {
graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.BEFORE, reverseDep);
super.removeReverseDep(reverseDep);
graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.AFTER, reverseDep);
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public boolean signalDep(Version childVersion) {
graphListener.accept(myKey, EventType.SIGNAL, Order.BEFORE, childVersion);
@@ -138,6 +148,7 @@
return result;
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public Set<SkyKey> setValue(SkyValue value, Version version) {
graphListener.accept(myKey, EventType.SET_VALUE, Order.BEFORE, value);
@@ -146,14 +157,16 @@
return result;
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
- public boolean markDirty(boolean isChanged) {
+ public MarkedDirtyResult markDirty(boolean isChanged) {
graphListener.accept(myKey, EventType.MARK_DIRTY, Order.BEFORE, isChanged);
- boolean result = super.markDirty(isChanged);
+ MarkedDirtyResult result = super.markDirty(isChanged);
graphListener.accept(myKey, EventType.MARK_DIRTY, Order.AFTER, isChanged);
return result;
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public Set<SkyKey> markClean() {
graphListener.accept(myKey, EventType.MARK_CLEAN, Order.BEFORE, this);
@@ -162,38 +175,44 @@
return result;
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public boolean isChanged() {
graphListener.accept(myKey, EventType.IS_CHANGED, Order.BEFORE, this);
return super.isChanged();
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public boolean isDirty() {
graphListener.accept(myKey, EventType.IS_DIRTY, Order.BEFORE, this);
return super.isDirty();
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
- public synchronized boolean isReady() {
+ public boolean isReady() {
graphListener.accept(myKey, EventType.IS_READY, Order.BEFORE, this);
return super.isReady();
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
public SkyValue getValueMaybeWithMetadata() {
graphListener.accept(myKey, EventType.GET_VALUE_WITH_METADATA, Order.BEFORE, this);
return super.getValueMaybeWithMetadata();
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
- public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+ public DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
graphListener.accept(myKey, EventType.CHECK_IF_DONE, Order.BEFORE, reverseDep);
return super.checkIfDoneForDirtyReverseDep(reverseDep);
}
+ @SuppressWarnings("UnsynchronizedOverridesSynchronized") // See the class doc for details.
@Override
- public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+ public Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
graphListener.accept(
myKey, EventType.GET_ALL_DIRECT_DEPS_FOR_INCOMPLETE_NODE, Order.BEFORE, this);
return super.getAllDirectDepsForIncompleteNode();
