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

4 files changed, 56 insertions, 17 deletions

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 637787a12d..326635dc37 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 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @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 @@ public class InMemoryNodeEntry implements NodeEntry {
       // 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 676b5374d4..ab8e0dcf43 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.ForkJoinQuiescingExecutor;
 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 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
               // 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 566bc504f0..55ec6cb493 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 @@ 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 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 1ff4fce1b8..d553dd1420 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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
     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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
       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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
       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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
       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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
       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 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
       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();