Merge "Add support for (explicitly) parallel sync-groups" into udc-dev

12 files changed, 470 insertions, 71 deletions

diff --git a/data/etc/services.core.protolog.json b/data/etc/services.core.protolog.json
index 549ac5858d1d..eb2412c0d598 100644
--- a/data/etc/services.core.protolog.json
+++ b/data/etc/services.core.protolog.json
@@ -307,6 +307,12 @@
       "group": "WM_DEBUG_REMOTE_ANIMATIONS",
       "at": "com\/android\/server\/wm\/RemoteAnimationController.java"
     },
+    "-1828118576": {
+      "message": "SyncGroup %d: Started %sfor listener: %s",
+      "level": "VERBOSE",
+      "group": "WM_DEBUG_SYNC_ENGINE",
+      "at": "com\/android\/server\/wm\/BLASTSyncEngine.java"
+    },
     "-1824578273": {
       "message": "Reporting new frame to %s: %s",
       "level": "VERBOSE",
@@ -2893,12 +2899,6 @@
       "group": "WM_DEBUG_BOOT",
       "at": "com\/android\/server\/wm\/WindowManagerService.java"
     },
-    "550717438": {
-      "message": "SyncGroup %d: Started for listener: %s",
-      "level": "VERBOSE",
-      "group": "WM_DEBUG_SYNC_ENGINE",
-      "at": "com\/android\/server\/wm\/BLASTSyncEngine.java"
-    },
     "556758086": {
       "message": "Applying new update lock state '%s' for %s",
       "level": "DEBUG",
@@ -4129,6 +4129,12 @@
       "group": "WM_DEBUG_ANIM",
       "at": "com\/android\/server\/wm\/WindowStateAnimator.java"
     },
+    "1820873642": {
+      "message": "SyncGroup %d:  Unfinished dependencies: %s",
+      "level": "VERBOSE",
+      "group": "WM_DEBUG_SYNC_ENGINE",
+      "at": "com\/android\/server\/wm\/BLASTSyncEngine.java"
+    },
     "1822314934": {
       "message": "Expected target rootTask=%s to restored behind rootTask=%s but it is behind rootTask=%s",
       "level": "WARN",
diff --git a/services/core/java/com/android/server/wm/ActivityRecord.java b/services/core/java/com/android/server/wm/ActivityRecord.java
index c6a2e0e51227..bc3a1a238c08 100644
--- a/services/core/java/com/android/server/wm/ActivityRecord.java
+++ b/services/core/java/com/android/server/wm/ActivityRecord.java
@@ -10551,8 +10551,8 @@ final class ActivityRecord extends WindowToken implements WindowManagerService.A
     }
 
     @Override
-    boolean isSyncFinished() {
-        if (!super.isSyncFinished()) return false;
+    boolean isSyncFinished(BLASTSyncEngine.SyncGroup group) {
+        if (!super.isSyncFinished(group)) return false;
         if (mDisplayContent != null && mDisplayContent.mUnknownAppVisibilityController
                 .isVisibilityUnknown(this)) {
             return false;
@@ -10572,11 +10572,14 @@ final class ActivityRecord extends WindowToken implements WindowManagerService.A
     }
 
     @Override
-    void finishSync(Transaction outMergedTransaction, boolean cancel) {
+    void finishSync(Transaction outMergedTransaction, BLASTSyncEngine.SyncGroup group,
+            boolean cancel) {
         // This override is just for getting metrics. allFinished needs to be checked before
         // finish because finish resets all the states.
+        final BLASTSyncEngine.SyncGroup syncGroup = getSyncGroup();
+        if (syncGroup != null && group != getSyncGroup()) return;
         mLastAllReadyAtSync = allSyncFinished();
-        super.finishSync(outMergedTransaction, cancel);
+        super.finishSync(outMergedTransaction, group, cancel);
     }
 
     @Nullable
diff --git a/services/core/java/com/android/server/wm/BLASTSyncEngine.java b/services/core/java/com/android/server/wm/BLASTSyncEngine.java
index 7ecc0839fe53..778951a545fa 100644
--- a/services/core/java/com/android/server/wm/BLASTSyncEngine.java
+++ b/services/core/java/com/android/server/wm/BLASTSyncEngine.java
@@ -27,7 +27,6 @@ import android.os.Handler;
 import android.os.Trace;
 import android.util.ArraySet;
 import android.util.Slog;
-import android.util.SparseArray;
 import android.view.SurfaceControl;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -61,6 +60,26 @@ import java.util.ArrayList;
  * This works primarily by setting-up state and then watching/waiting for the registered subtrees
  * to enter into a "finished" state (either by receiving drawn content or by disappearing). This
  * checks the subtrees during surface-placement.
+ *
+ * By default, all Syncs will be serialized (and it is an error to start one while another is
+ * active). However, a sync can be explicitly started in "parallel". This does not guarantee that
+ * it will run in parallel; however, it will run in parallel as long as it's watched hierarchy
+ * doesn't overlap with any other syncs' watched hierarchies.
+ *
+ * Currently, a sync that is started as "parallel" implicitly ignores the subtree below it's
+ * direct members unless those members are activities (WindowStates are considered "part of" the
+ * activity). This allows "stratified" parallelism where, eg, a sync that is only at Task-level
+ * can run in parallel with another sync that includes only the task's activities.
+ *
+ * If, at any time, a container is added to a parallel sync that *is* watched by another sync, it
+ * will be forced to serialize with it. This is done by adding a dependency. A sync will only
+ * finish if it has no active dependencies. At this point it is effectively not parallel anymore.
+ *
+ * To avoid dependency cycles, if a sync B ultimately depends on a sync A and a container is added
+ * to A which is watched by B, that container will, instead, be moved from B to A instead of
+ * creating a cyclic dependency.
+ *
+ * When syncs overlap, this will attempt to finish everything in the order they were started.
  */
 class BLASTSyncEngine {
     private static final String TAG = "BLASTSyncEngine";
@@ -104,6 +123,18 @@ class BLASTSyncEngine {
         private SurfaceControl.Transaction mOrphanTransaction = null;
         private String mTraceName;
 
+        private static final ArrayList<SyncGroup> NO_DEPENDENCIES = new ArrayList<>();
+
+        /**
+         * When `true`, this SyncGroup will only wait for mRootMembers to draw; otherwise,
+         * it waits for the whole subtree(s) rooted at the mRootMembers.
+         */
+        boolean mIgnoreIndirectMembers = false;
+
+        /** List of SyncGroups that must finish before this one can. */
+        @NonNull
+        ArrayList<SyncGroup> mDependencies = NO_DEPENDENCIES;
+
         private SyncGroup(TransactionReadyListener listener, int id, String name) {
             mSyncId = id;
             mListener = listener;
@@ -133,19 +164,43 @@ class BLASTSyncEngine {
             return mOrphanTransaction;
         }
 
-        private void tryFinish() {
-            if (!mReady) return;
+        /**
+         * Check if the sync-group ignores a particular container. This is used to allow syncs at
+         * different levels to run in parallel. The primary example is Recents while an activity
+         * sync is happening.
+         */
+        boolean isIgnoring(WindowContainer wc) {
+            // Some heuristics to avoid unnecessary work:
+            // 1. For now, require an explicit acknowledgement of potential "parallelism" across
+            //    hierarchy levels (horizontal).
+            if (!mIgnoreIndirectMembers) return false;
+            // 2. Don't check WindowStates since they are below the relevant abstraction level (
+            //    anything activity/token and above).
+            if (wc.asWindowState() != null) return false;
+            // Obviously, don't ignore anything that is directly part of this group.
+            return wc.mSyncGroup != this;
+        }
+
+        /** @return `true` if it finished. */
+        private boolean tryFinish() {
+            if (!mReady) return false;
             ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d: onSurfacePlacement checking %s",
                     mSyncId, mRootMembers);
+            if (!mDependencies.isEmpty()) {
+                ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d:  Unfinished dependencies: %s",
+                        mSyncId, mDependencies);
+                return false;
+            }
             for (int i = mRootMembers.size() - 1; i >= 0; --i) {
                 final WindowContainer wc = mRootMembers.valueAt(i);
-                if (!wc.isSyncFinished()) {
+                if (!wc.isSyncFinished(this)) {
                     ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d:  Unfinished container: %s",
                             mSyncId, wc);
-                    return;
+                    return false;
                 }
             }
             finishNow();
+            return true;
         }
 
         private void finishNow() {
@@ -158,7 +213,7 @@ class BLASTSyncEngine {
                 merged.merge(mOrphanTransaction);
             }
             for (WindowContainer wc : mRootMembers) {
-                wc.finishSync(merged, false /* cancel */);
+                wc.finishSync(merged, this, false /* cancel */);
             }
 
             final ArraySet<WindowContainer> wcAwaitingCommit = new ArraySet<>();
@@ -204,7 +259,7 @@ class BLASTSyncEngine {
             Trace.traceBegin(TRACE_TAG_WINDOW_MANAGER, "onTransactionReady");
             mListener.onTransactionReady(mSyncId, merged);
             Trace.traceEnd(TRACE_TAG_WINDOW_MANAGER);
-            mActiveSyncs.remove(mSyncId);
+            mActiveSyncs.remove(this);
             mHandler.removeCallbacks(mOnTimeout);
 
             // Immediately start the next pending sync-transaction if there is one.
@@ -230,54 +285,115 @@ class BLASTSyncEngine {
             }
         }
 
-        private void setReady(boolean ready) {
+        /** returns true if readiness changed. */
+        private boolean setReady(boolean ready) {
             if (mReady == ready) {
-                return;
+                return false;
             }
             ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d: Set ready %b", mSyncId, ready);
             mReady = ready;
-            if (!ready) return;
-            mWm.mWindowPlacerLocked.requestTraversal();
+            if (ready) {
+                mWm.mWindowPlacerLocked.requestTraversal();
+            }
+            return true;
         }
 
         private void addToSync(WindowContainer wc) {
-            if (!mRootMembers.add(wc)) {
+            if (mRootMembers.contains(wc)) {
                 return;
             }
             ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d: Adding to group: %s", mSyncId, wc);
-            wc.setSyncGroup(this);
+            final SyncGroup dependency = wc.getSyncGroup();
+            if (dependency != null && dependency != this && !dependency.isIgnoring(wc)) {
+                // This syncgroup now conflicts with another one, so the whole group now must
+                // wait on the other group.
+                Slog.w(TAG, "SyncGroup " + mSyncId + " conflicts with " + dependency.mSyncId
+                        + ": Making " + mSyncId + " depend on " + dependency.mSyncId);
+                if (mDependencies.contains(dependency)) {
+                    // nothing, it's already a dependency.
+                } else if (dependency.dependsOn(this)) {
+                    Slog.w(TAG, " Detected dependency cycle between " + mSyncId + " and "
+                            + dependency.mSyncId + ": Moving " + wc + " to " + mSyncId);
+                    // Since dependency already depends on this, make this now `wc`'s watcher
+                    if (wc.mSyncGroup == null) {
+                        wc.setSyncGroup(this);
+                    } else {
+                        // Explicit replacement.
+                        wc.mSyncGroup.mRootMembers.remove(wc);
+                        mRootMembers.add(wc);
+                        wc.mSyncGroup = this;
+                    }
+                } else {
+                    if (mDependencies == NO_DEPENDENCIES) {
+                        mDependencies = new ArrayList<>();
+                    }
+                    mDependencies.add(dependency);
+                }
+            } else {
+                mRootMembers.add(wc);
+                wc.setSyncGroup(this);
+            }
             wc.prepareSync();
             if (mReady) {
                 mWm.mWindowPlacerLocked.requestTraversal();
             }
         }
 
+        private boolean dependsOn(SyncGroup group) {
+            if (mDependencies.isEmpty()) return false;
+            // BFS search with membership check. We don't expect cycle here (since this is
+            // explicitly called to avoid cycles) but just to be safe.
+            final ArrayList<SyncGroup> fringe = mTmpFringe;
+            fringe.clear();
+            fringe.add(this);
+            for (int head = 0; head < fringe.size(); ++head) {
+                final SyncGroup next = fringe.get(head);
+                if (next == group) {
+                    fringe.clear();
+                    return true;
+                }
+                for (int i = 0; i < next.mDependencies.size(); ++i) {
+                    if (fringe.contains(next.mDependencies.get(i))) continue;
+                    fringe.add(next.mDependencies.get(i));
+                }
+            }
+            fringe.clear();
+            return false;
+        }
+
         void onCancelSync(WindowContainer wc) {
             mRootMembers.remove(wc);
         }
 
         private void onTimeout() {
-            if (!mActiveSyncs.contains(mSyncId)) return;
+            if (!mActiveSyncs.contains(this)) return;
             boolean allFinished = true;
             for (int i = mRootMembers.size() - 1; i >= 0; --i) {
                 final WindowContainer<?> wc = mRootMembers.valueAt(i);
-                if (!wc.isSyncFinished()) {
+                if (!wc.isSyncFinished(this)) {
                     allFinished = false;
                     Slog.i(TAG, "Unfinished container: " + wc);
                 }
             }
+            for (int i = mDependencies.size() - 1; i >= 0; --i) {
+                allFinished = false;
+                Slog.i(TAG, "Unfinished dependency: " + mDependencies.get(i).mSyncId);
+            }
             if (allFinished && !mReady) {
                 Slog.w(TAG, "Sync group " + mSyncId + " timed-out because not ready. If you see "
                         + "this, please file a bug.");
             }
             finishNow();
+            removeFromDependencies(this);
         }
     }
 
     private final WindowManagerService mWm;
     private final Handler mHandler;
     private int mNextSyncId = 0;
-    private final SparseArray<SyncGroup> mActiveSyncs = new SparseArray<>();
+
+    /** Currently active syncs. Intentionally ordered by start time. */
+    private final ArrayList<SyncGroup> mActiveSyncs = new ArrayList<>();
 
     /**
      * A queue of pending sync-sets waiting for their turn to run.
@@ -288,6 +404,9 @@ class BLASTSyncEngine {
 
     private final ArrayList<Runnable> mOnIdleListeners = new ArrayList<>();
 
+    private final ArrayList<SyncGroup> mTmpFinishQueue = new ArrayList<>();
+    private final ArrayList<SyncGroup> mTmpFringe = new ArrayList<>();
+
     BLASTSyncEngine(WindowManagerService wms) {
         this(wms, wms.mH);
     }
@@ -306,32 +425,39 @@ class BLASTSyncEngine {
         return new SyncGroup(listener, mNextSyncId++, name);
     }
 
-    int startSyncSet(TransactionReadyListener listener, long timeoutMs, String name) {
+    int startSyncSet(TransactionReadyListener listener, long timeoutMs, String name,
+            boolean parallel) {
         final SyncGroup s = prepareSyncSet(listener, name);
-        startSyncSet(s, timeoutMs);
+        startSyncSet(s, timeoutMs, parallel);
         return s.mSyncId;
     }
 
     void startSyncSet(SyncGroup s) {
-        startSyncSet(s, BLAST_TIMEOUT_DURATION);
+        startSyncSet(s, BLAST_TIMEOUT_DURATION, false /* parallel */);
     }
 
-    void startSyncSet(SyncGroup s, long timeoutMs) {
-        if (mActiveSyncs.size() != 0) {
-            // We currently only support one sync at a time, so start a new SyncGroup when there is
-            // another may cause issue.
+    void startSyncSet(SyncGroup s, long timeoutMs, boolean parallel) {
+        final boolean alreadyRunning = mActiveSyncs.size() > 0;
+        if (!parallel && alreadyRunning) {
+            // We only support overlapping syncs when explicitly declared `parallel`.
             Slog.e(TAG, "SyncGroup " + s.mSyncId
                     + ": Started when there is other active SyncGroup");
         }
-        mActiveSyncs.put(s.mSyncId, s);
-        ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d: Started for listener: %s",
-                s.mSyncId, s.mListener);
+        mActiveSyncs.add(s);
+        // For now, parallel implies this.
+        s.mIgnoreIndirectMembers = parallel;
+        ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "SyncGroup %d: Started %sfor listener: %s",
+                s.mSyncId, (parallel && alreadyRunning ? "(in parallel) " : ""), s.mListener);
         scheduleTimeout(s, timeoutMs);
     }
 
     @Nullable
     SyncGroup getSyncSet(int id) {
-        return mActiveSyncs.get(id);
+        for (int i = 0; i < mActiveSyncs.size(); ++i) {
+            if (mActiveSyncs.get(i).mSyncId != id) continue;
+            return mActiveSyncs.get(i);
+        }
+        return null;
     }
 
     boolean hasActiveSync() {
@@ -356,8 +482,8 @@ class BLASTSyncEngine {
         syncGroup.mSyncMethod = method;
     }
 
-    void setReady(int id, boolean ready) {
-        getSyncGroup(id).setReady(ready);
+    boolean setReady(int id, boolean ready) {
+        return getSyncGroup(id).setReady(ready);
     }
 
     void setReady(int id) {
@@ -372,21 +498,68 @@ class BLASTSyncEngine {
      * Aborts the sync (ie. it doesn't wait for ready or anything to finish)
      */
     void abort(int id) {
-        getSyncGroup(id).finishNow();
+        final SyncGroup group = getSyncGroup(id);
+        group.finishNow();
+        removeFromDependencies(group);
     }
 
     private SyncGroup getSyncGroup(int id) {
-        final SyncGroup syncGroup = mActiveSyncs.get(id);
+        final SyncGroup syncGroup = getSyncSet(id);
         if (syncGroup == null) {
             throw new IllegalStateException("SyncGroup is not started yet id=" + id);
         }
         return syncGroup;
     }
 
+    /**
+     * Just removes `group` from any dependency lists. Does not try to evaluate anything. However,
+     * it will schedule traversals if any groups were changed in a way that could make them ready.
+     */
+    private void removeFromDependencies(SyncGroup group) {
+        boolean anyChange = false;
+        for (int i = 0; i < mActiveSyncs.size(); ++i) {
+            final SyncGroup active = mActiveSyncs.get(i);
+            if (!active.mDependencies.remove(group)) continue;
+            if (!active.mDependencies.isEmpty()) continue;
+            anyChange = true;
+        }
+        if (!anyChange) return;
+        mWm.mWindowPlacerLocked.requestTraversal();
+    }
+
     void onSurfacePlacement() {
-        // backwards since each state can remove itself if finished
-        for (int i = mActiveSyncs.size() - 1; i >= 0; --i) {
-            mActiveSyncs.valueAt(i).tryFinish();
+        if (mActiveSyncs.isEmpty()) return;
+        // queue in-order since we want interdependent syncs to become ready in the same order they
+        // started in.
+        mTmpFinishQueue.addAll(mActiveSyncs);
+        // There shouldn't be any dependency cycles or duplicates, but add an upper-bound just
+        // in case. Assuming absolute worst case, each visit will try and revisit everything
+        // before it, so n + (n-1) + (n-2) ... = (n+1)*n/2
+        int visitBounds = ((mActiveSyncs.size() + 1) * mActiveSyncs.size()) / 2;
+        while (!mTmpFinishQueue.isEmpty()) {
+            if (visitBounds <= 0) {
+                Slog.e(TAG, "Trying to finish more syncs than theoretically possible. This "
+                        + "should never happen. Most likely a dependency cycle wasn't detected.");
+            }
+            --visitBounds;
+            final SyncGroup group = mTmpFinishQueue.remove(0);
+            final int grpIdx = mActiveSyncs.indexOf(group);
+            // Skip if it's already finished:
+            if (grpIdx < 0) continue;
+            if (!group.tryFinish()) continue;
+            // Finished, so update dependencies of any prior groups and retry if unblocked.
+            int insertAt = 0;
+            for (int i = 0; i < mActiveSyncs.size(); ++i) {
+                final SyncGroup active = mActiveSyncs.get(i);
+                if (!active.mDependencies.remove(group)) continue;
+                // Anything afterwards is already in queue.
+                if (i >= grpIdx) continue;
+                if (!active.mDependencies.isEmpty()) continue;
+                // `active` became unblocked so it can finish, since it started earlier, it should
+                // be checked next to maintain order.
+                mTmpFinishQueue.add(insertAt, mActiveSyncs.get(i));
+                insertAt += 1;
+            }
         }
     }
 
diff --git a/services/core/java/com/android/server/wm/DisplayContent.java b/services/core/java/com/android/server/wm/DisplayContent.java
index 76d6951c438e..f478e9bee18a 100644
--- a/services/core/java/com/android/server/wm/DisplayContent.java
+++ b/services/core/java/com/android/server/wm/DisplayContent.java
@@ -1755,7 +1755,7 @@ class DisplayContent extends RootDisplayArea implements WindowManagerPolicy.Disp
     }
 
     @Override
-    boolean isSyncFinished() {
+    boolean isSyncFinished(BLASTSyncEngine.SyncGroup group) {
         // Do not consider children because if they are requested to be synced, they should be
         // added to sync group explicitly.
         return !mRemoteDisplayChangeController.isWaitingForRemoteDisplayChange();
diff --git a/services/core/java/com/android/server/wm/TaskFragment.java b/services/core/java/com/android/server/wm/TaskFragment.java
index 3f7ab14d02be..c6c3b14bf98b 100644
--- a/services/core/java/com/android/server/wm/TaskFragment.java
+++ b/services/core/java/com/android/server/wm/TaskFragment.java
@@ -2547,8 +2547,8 @@ class TaskFragment extends WindowContainer<WindowContainer> {
     }
 
     @Override
-    boolean isSyncFinished() {
-        return super.isSyncFinished() && isReadyToTransit();
+    boolean isSyncFinished(BLASTSyncEngine.SyncGroup group) {
+        return super.isSyncFinished(group) && isReadyToTransit();
     }
 
     @Override
diff --git a/services/core/java/com/android/server/wm/Transition.java b/services/core/java/com/android/server/wm/Transition.java
index 452bd6d7b347..b314ed17244c 100644
--- a/services/core/java/com/android/server/wm/Transition.java
+++ b/services/core/java/com/android/server/wm/Transition.java
@@ -447,7 +447,7 @@ class Transition implements BLASTSyncEngine.TransactionReadyListener {
             throw new IllegalStateException("Attempting to re-use a transition");
         }
         mState = STATE_COLLECTING;
-        mSyncId = mSyncEngine.startSyncSet(this, timeoutMs, TAG);
+        mSyncId = mSyncEngine.startSyncSet(this, timeoutMs, TAG, false /* parallel */);
         mSyncEngine.setSyncMethod(mSyncId, TransitionController.SYNC_METHOD);
 
         mLogger.mSyncId = mSyncId;
diff --git a/services/core/java/com/android/server/wm/WindowContainer.java b/services/core/java/com/android/server/wm/WindowContainer.java
index cf6efd28acb7..f4a1765d4663 100644
--- a/services/core/java/com/android/server/wm/WindowContainer.java
+++ b/services/core/java/com/android/server/wm/WindowContainer.java
@@ -3835,13 +3835,11 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
 
     void setSyncGroup(@NonNull BLASTSyncEngine.SyncGroup group) {
         ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "setSyncGroup #%d on %s", group.mSyncId, this);
-        if (group != null) {
-            if (mSyncGroup != null && mSyncGroup != group) {
-                // This can still happen if WMCore starts a new transition when there is ongoing
-                // sync transaction from Shell. Please file a bug if it happens.
-                throw new IllegalStateException("Can't sync on 2 engines simultaneously"
-                        + " currentSyncId=" + mSyncGroup.mSyncId + " newSyncId=" + group.mSyncId);
-            }
+        if (mSyncGroup != null && mSyncGroup != group) {
+            // This can still happen if WMCore starts a new transition when there is ongoing
+            // sync transaction from Shell. Please file a bug if it happens.
+            throw new IllegalStateException("Can't sync on 2 groups simultaneously"
+                    + " currentSyncId=" + mSyncGroup.mSyncId + " newSyncId=" + group.mSyncId);
         }
         mSyncGroup = group;
     }
@@ -3883,12 +3881,16 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
      * @param cancel If true, this is being finished because it is leaving the sync group rather
      *               than due to the sync group completing.
      */
-    void finishSync(Transaction outMergedTransaction, boolean cancel) {
+    void finishSync(Transaction outMergedTransaction, BLASTSyncEngine.SyncGroup group,
+            boolean cancel) {
         if (mSyncState == SYNC_STATE_NONE) return;
+        final BLASTSyncEngine.SyncGroup syncGroup = getSyncGroup();
+        // If it's null, then we need to clean-up anyways.
+        if (syncGroup != null && group != syncGroup) return;
         ProtoLog.v(WM_DEBUG_SYNC_ENGINE, "finishSync cancel=%b for %s", cancel, this);
         outMergedTransaction.merge(mSyncTransaction);
         for (int i = mChildren.size() - 1; i >= 0; --i) {
-            mChildren.get(i).finishSync(outMergedTransaction, cancel);
+            mChildren.get(i).finishSync(outMergedTransaction, group, cancel);
         }
         if (cancel && mSyncGroup != null) mSyncGroup.onCancelSync(this);
         mSyncState = SYNC_STATE_NONE;
@@ -3903,7 +3905,7 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
      *
      * @return {@code true} if this subtree is finished waiting for sync participants.
      */
-    boolean isSyncFinished() {
+    boolean isSyncFinished(BLASTSyncEngine.SyncGroup group) {
         if (!isVisibleRequested()) {
             return true;
         }
@@ -3917,7 +3919,7 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
         // Loop from top-down.
         for (int i = mChildren.size() - 1; i >= 0; --i) {
             final WindowContainer child = mChildren.get(i);
-            final boolean childFinished = child.isSyncFinished();
+            final boolean childFinished = group.isIgnoring(child) || child.isSyncFinished(group);
             if (childFinished && child.isVisibleRequested() && child.fillsParent()) {
                 // Any lower children will be covered-up, so we can consider this finished.
                 return true;
@@ -3968,11 +3970,11 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
                 // This is getting removed.
                 if (oldParent.mSyncState != SYNC_STATE_NONE) {
                     // In order to keep the transaction in sync, merge it into the parent.
-                    finishSync(oldParent.mSyncTransaction, true /* cancel */);
+                    finishSync(oldParent.mSyncTransaction, getSyncGroup(), true /* cancel */);
                 } else if (mSyncGroup != null) {
                     // This is watched directly by the sync-group, so merge this transaction into
                     // into the sync-group so it isn't lost
-                    finishSync(mSyncGroup.getOrphanTransaction(), true /* cancel */);
+                    finishSync(mSyncGroup.getOrphanTransaction(), mSyncGroup, true /* cancel */);
                 } else {
                     throw new IllegalStateException("This container is in sync mode without a sync"
                             + " group: " + this);
@@ -3981,7 +3983,7 @@ class WindowContainer<E extends WindowContainer> extends ConfigurationContainer<
             } else if (mSyncGroup == null) {
                 // This is being reparented out of the sync-group. To prevent ordering issues on
                 // this container, immediately apply/cancel sync on it.
-                finishSync(getPendingTransaction(), true /* cancel */);
+                finishSync(getPendingTransaction(), getSyncGroup(), true /* cancel */);
                 return;
             }
             // Otherwise this is the "root" of a synced subtree, so continue on to preparation.
diff --git a/services/core/java/com/android/server/wm/WindowState.java b/services/core/java/com/android/server/wm/WindowState.java
index f3b338294393..2920652674d3 100644
--- a/services/core/java/com/android/server/wm/WindowState.java
+++ b/services/core/java/com/android/server/wm/WindowState.java
@@ -5678,7 +5678,7 @@ class WindowState extends WindowContainer<WindowState> implements WindowManagerP
     }
 
     @Override
-    boolean isSyncFinished() {
+    boolean isSyncFinished(BLASTSyncEngine.SyncGroup group) {
         if (!isVisibleRequested() || isFullyTransparent()) {
             // Don't wait for invisible windows. However, we don't alter the state in case the
             // window becomes visible while the sync group is still active.
@@ -5689,11 +5689,14 @@ class WindowState extends WindowContainer<WindowState> implements WindowManagerP
             // Complete the sync state immediately for a drawn window that doesn't need to redraw.
             onSyncFinishedDrawing();
         }
-        return super.isSyncFinished();
+        return super.isSyncFinished(group);
     }
 
     @Override
-    void finishSync(Transaction outMergedTransaction, boolean cancel) {
+    void finishSync(Transaction outMergedTransaction, BLASTSyncEngine.SyncGroup group,
+            boolean cancel) {
+        final BLASTSyncEngine.SyncGroup syncGroup = getSyncGroup();
+        if (syncGroup != null && group != syncGroup) return;
         mPrepareSyncSeqId = 0;
         if (cancel) {
             // This is leaving sync so any buffers left in the sync have a chance of
@@ -5701,7 +5704,7 @@ class WindowState extends WindowContainer<WindowState> implements WindowManagerP
             // window. To prevent this, drop the buffer.
             dropBufferFrom(mSyncTransaction);
         }
-        super.finishSync(outMergedTransaction, cancel);
+        super.finishSync(outMergedTransaction, group, cancel);
     }
 
     boolean finishDrawing(SurfaceControl.Transaction postDrawTransaction, int syncSeqId) {
diff --git a/services/tests/wmtests/src/com/android/server/wm/SyncEngineTests.java b/services/tests/wmtests/src/com/android/server/wm/SyncEngineTests.java
index 77efc4b0d561..ddd630ee8635 100644
--- a/services/tests/wmtests/src/com/android/server/wm/SyncEngineTests.java
+++ b/services/tests/wmtests/src/com/android/server/wm/SyncEngineTests.java
@@ -48,6 +48,8 @@ import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.mockito.ArgumentCaptor;
+import org.mockito.InOrder;
+import org.mockito.Mockito;
 
 /**
  * Test class for {@link BLASTSyncEngine}.
@@ -225,7 +227,7 @@ public class SyncEngineTests extends WindowTestsBase {
         parentWC.onSyncFinishedDrawing();
         topChildWC.onSyncFinishedDrawing();
         // Even though bottom isn't finished, we should see callback because it is occluded by top.
-        assertFalse(botChildWC.isSyncFinished());
+        assertFalse(botChildWC.isSyncFinished(botChildWC.getSyncGroup()));
         bse.onSurfacePlacement();
         verify(listener, times(1)).onTransactionReady(eq(id), notNull());
 
@@ -416,9 +418,217 @@ public class SyncEngineTests extends WindowTestsBase {
         assertTrue(bse.isReady(nextId[0]));
     }
 
+    @Test
+    public void testStratifiedParallel() {
+        TestWindowContainer parentWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC = new TestWindowContainer(mWm, true /* waiter */);
+        parentWC.addChild(childWC, POSITION_TOP);
+        childWC.mVisibleRequested = true;
+        childWC.mFillsParent = true;
+
+        final BLASTSyncEngine bse = createTestBLASTSyncEngine();
+
+        BLASTSyncEngine.TransactionReadyListener listenerChild = mock(
+                BLASTSyncEngine.TransactionReadyListener.class);
+        BLASTSyncEngine.TransactionReadyListener listenerParent = mock(
+                BLASTSyncEngine.TransactionReadyListener.class);
+
+        // Start a sync-set for the "inner" stuff
+        int childSync = startSyncSet(bse, listenerChild);
+        bse.addToSyncSet(childSync, childWC);
+        bse.setReady(childSync);
+
+        // Start sync-set for the "outer" stuff but explicitly parallel (it should ignore child)
+        int parentSync = startSyncSet(bse, listenerParent, true /* parallel */);
+        bse.addToSyncSet(parentSync, parentWC);
+        bse.setReady(parentSync);
+
+        bse.onSurfacePlacement();
+        // Nothing should have happened yet
+        verify(listenerChild, times(0)).onTransactionReady(anyInt(), any());
+        verify(listenerParent, times(0)).onTransactionReady(anyInt(), any());
+
+        // Now, make PARENT ready, since they are in parallel, this should work
+        parentWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        // Parent should become ready while child is still waiting.
+        verify(listenerParent, times(1)).onTransactionReady(eq(parentSync), notNull());
+        verify(listenerChild, times(0)).onTransactionReady(anyInt(), any());
+
+        // Child should still work
+        childWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+        verify(listenerChild, times(1)).onTransactionReady(eq(childSync), notNull());
+    }
+
+    @Test
+    public void testDependencies() {
+        TestWindowContainer parentWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC2 = new TestWindowContainer(mWm, true /* waiter */);
+        parentWC.addChild(childWC, POSITION_TOP);
+        childWC.mVisibleRequested = true;
+        childWC.mFillsParent = true;
+        childWC2.mVisibleRequested = true;
+        childWC2.mFillsParent = true;
+
+        final BLASTSyncEngine bse = createTestBLASTSyncEngine();
+
+        BLASTSyncEngine.TransactionReadyListener listener = mock(
+                BLASTSyncEngine.TransactionReadyListener.class);
+
+        // This is non-parallel, so it is waiting on the child as-well
+        int sync1 = startSyncSet(bse, listener);
+        bse.addToSyncSet(sync1, parentWC);
+        bse.setReady(sync1);
+
+        // Create one which will end-up depending on the *next* sync
+        int sync2 = startSyncSet(bse, listener, true /* parallel */);
+
+        // If another sync tries to sync on the same subtree, it must now serialize with the other.
+        int sync3 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync3, childWC);
+        bse.addToSyncSet(sync3, childWC2);
+        bse.setReady(sync3);
+
+        // This will depend on sync3.
+        int sync4 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync4, childWC2);
+        bse.setReady(sync4);
+
+        // This makes sync2 depend on sync3. Since both sync2 and sync4 depend on sync3, when sync3
+        // finishes, sync2 should run first since it was created first.
+        bse.addToSyncSet(sync2, childWC2);
+        bse.setReady(sync2);
+
+        childWC.onSyncFinishedDrawing();
+        childWC2.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        // Nothing should be ready yet since everything ultimately depends on sync1.
+        verify(listener, times(0)).onTransactionReady(anyInt(), any());
+
+        parentWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        // They should all be ready, now, so just verify that the order is expected
+        InOrder readyOrder = Mockito.inOrder(listener);
+        // sync1 is the first one, so it should call ready first.
+        readyOrder.verify(listener).onTransactionReady(eq(sync1), any());
+        // everything else depends on sync3, so it should call ready next.
+        readyOrder.verify(listener).onTransactionReady(eq(sync3), any());
+        // both sync2 and sync4 depend on sync3, but sync2 started first, so it should go next.
+        readyOrder.verify(listener).onTransactionReady(eq(sync2), any());
+        readyOrder.verify(listener).onTransactionReady(eq(sync4), any());
+    }
+
+    @Test
+    public void testStratifiedParallelParentFirst() {
+        TestWindowContainer parentWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC = new TestWindowContainer(mWm, true /* waiter */);
+        parentWC.addChild(childWC, POSITION_TOP);
+        childWC.mVisibleRequested = true;
+        childWC.mFillsParent = true;
+
+        final BLASTSyncEngine bse = createTestBLASTSyncEngine();
+
+        BLASTSyncEngine.TransactionReadyListener listener = mock(
+                BLASTSyncEngine.TransactionReadyListener.class);
+
+        // This is parallel, so it should ignore children
+        int sync1 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync1, parentWC);
+        bse.setReady(sync1);
+
+        int sync2 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync2, childWC);
+        bse.setReady(sync2);
+
+        childWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        // Sync2 should have run in parallel
+        verify(listener, times(1)).onTransactionReady(eq(sync2), any());
+        verify(listener, times(0)).onTransactionReady(eq(sync1), any());
+
+        parentWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        verify(listener, times(1)).onTransactionReady(eq(sync1), any());
+    }
+
+    @Test
+    public void testDependencyCycle() {
+        TestWindowContainer parentWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC2 = new TestWindowContainer(mWm, true /* waiter */);
+        TestWindowContainer childWC3 = new TestWindowContainer(mWm, true /* waiter */);
+        parentWC.addChild(childWC, POSITION_TOP);
+        childWC.mVisibleRequested = true;
+        childWC.mFillsParent = true;
+        childWC2.mVisibleRequested = true;
+        childWC2.mFillsParent = true;
+        childWC3.mVisibleRequested = true;
+        childWC3.mFillsParent = true;
+
+        final BLASTSyncEngine bse = createTestBLASTSyncEngine();
+
+        BLASTSyncEngine.TransactionReadyListener listener = mock(
+                BLASTSyncEngine.TransactionReadyListener.class);
+
+        // This is non-parallel, so it is waiting on the child as-well
+        int sync1 = startSyncSet(bse, listener);
+        bse.addToSyncSet(sync1, parentWC);
+        bse.setReady(sync1);
+
+        // Sync 2 depends on sync1 AND childWC2
+        int sync2 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync2, childWC);
+        bse.addToSyncSet(sync2, childWC2);
+        bse.setReady(sync2);
+
+        // Sync 3 depends on sync2 AND childWC3
+        int sync3 = startSyncSet(bse, listener, true /* parallel */);
+        bse.addToSyncSet(sync3, childWC2);
+        bse.addToSyncSet(sync3, childWC3);
+        bse.setReady(sync3);
+
+        // Now make sync1 depend on WC3 (which would make it depend on sync3). This would form
+        // a cycle, so it should instead move childWC3 into sync1.
+        bse.addToSyncSet(sync1, childWC3);
+
+        // Sync3 should no-longer have childWC3 as a root-member since a window can currently only
+        // be directly watched by 1 syncgroup maximum (due to implementation of isSyncFinished).
+        assertFalse(bse.getSyncSet(sync3).mRootMembers.contains(childWC3));
+
+        childWC3.onSyncFinishedDrawing();
+        childWC2.onSyncFinishedDrawing();
+        parentWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        // make sure sync3 hasn't run even though all its (original) members are ready
+        verify(listener, times(0)).onTransactionReady(anyInt(), any());
+
+        // Now finish the last container and make sure everything finishes (didn't "deadlock" due
+        // to a dependency cycle.
+        childWC.onSyncFinishedDrawing();
+        bse.onSurfacePlacement();
+
+        InOrder readyOrder = Mockito.inOrder(listener);
+        readyOrder.verify(listener).onTransactionReady(eq(sync1), any());
+        readyOrder.verify(listener).onTransactionReady(eq(sync2), any());
+        readyOrder.verify(listener).onTransactionReady(eq(sync3), any());
+    }
+
     static int startSyncSet(BLASTSyncEngine engine,
             BLASTSyncEngine.TransactionReadyListener listener) {
-        return engine.startSyncSet(listener, BLAST_TIMEOUT_DURATION, "Test");
+        return engine.startSyncSet(listener, BLAST_TIMEOUT_DURATION, "Test", false /* parallel */);
+    }
+
+    static int startSyncSet(BLASTSyncEngine engine,
+            BLASTSyncEngine.TransactionReadyListener listener, boolean parallel) {
+        return engine.startSyncSet(listener, BLAST_TIMEOUT_DURATION, "Test", parallel);
     }
 
     static class TestWindowContainer extends WindowContainer {
diff --git a/services/tests/wmtests/src/com/android/server/wm/TransitionTests.java b/services/tests/wmtests/src/com/android/server/wm/TransitionTests.java
index 653b52b06720..0dac346bb717 100644
--- a/services/tests/wmtests/src/com/android/server/wm/TransitionTests.java
+++ b/services/tests/wmtests/src/com/android/server/wm/TransitionTests.java
@@ -1196,7 +1196,8 @@ public class TransitionTests extends WindowTestsBase {
 
         player.start();
         player.finish();
-        app.getTask().finishSync(mWm.mTransactionFactory.get(), false /* cancel */);
+        app.getTask().finishSync(mWm.mTransactionFactory.get(), app.getTask().getSyncGroup(),
+                false /* cancel */);
 
         // The open transition is finished. Continue to play seamless display change transition,
         // so the previous async rotation controller should still exist.
diff --git a/services/tests/wmtests/src/com/android/server/wm/WallpaperControllerTests.java b/services/tests/wmtests/src/com/android/server/wm/WallpaperControllerTests.java
index 984b868ab67f..453096306694 100644
--- a/services/tests/wmtests/src/com/android/server/wm/WallpaperControllerTests.java
+++ b/services/tests/wmtests/src/com/android/server/wm/WallpaperControllerTests.java
@@ -394,7 +394,7 @@ public class WallpaperControllerTests extends WindowTestsBase {
         assertTrue(token.isVisible());
 
         final SurfaceControl.Transaction t = mock(SurfaceControl.Transaction.class);
-        token.finishSync(t, false /* cancel */);
+        token.finishSync(t, token.getSyncGroup(), false /* cancel */);
         transit.onTransactionReady(transit.getSyncId(), t);
         dc.mTransitionController.finishTransition(transit);
         assertFalse(wallpaperWindow.isVisible());
diff --git a/services/tests/wmtests/src/com/android/server/wm/WindowOrganizerTests.java b/services/tests/wmtests/src/com/android/server/wm/WindowOrganizerTests.java
index d19c996ce939..600681fb332c 100644
--- a/services/tests/wmtests/src/com/android/server/wm/WindowOrganizerTests.java
+++ b/services/tests/wmtests/src/com/android/server/wm/WindowOrganizerTests.java
@@ -1006,7 +1006,8 @@ public class WindowOrganizerTests extends WindowTestsBase {
         BLASTSyncEngine.TransactionReadyListener transactionListener =
                 mock(BLASTSyncEngine.TransactionReadyListener.class);
 
-        final int id = bse.startSyncSet(transactionListener, BLAST_TIMEOUT_DURATION, "Test");
+        final int id = bse.startSyncSet(transactionListener, BLAST_TIMEOUT_DURATION, "Test",
+                false /* parallel */);
         bse.addToSyncSet(id, task);
         bse.setReady(id);
         bse.onSurfacePlacement();