Use new traversal function when order doesn't matter

The new traversal function just handles traversing children and ignores relative layers. It also doesn't care about the z order. We continue to use the traverseInZOrder functions
for cases when z order matters.

This optimization reduces total CPU time spent in SurfaceFlinger.
Total ~2% savings

The savings where measured sampling over a 20 second period while TouchLatency
bouncy ball app was running.

Baseline
https://pprof.corp.google.com/?id=2ec0b6ac8e24e1571a3173c763ecd7e1&focus=LayerVector%3A%3AtraverseInZOrder

Optimized
https://pprof.corp.google.com/?id=23596aeb3e9db163956dc621dd19d7a4&focus=LayerVector%3A%3Atraverse

Test: manual. checked that normal use on the phone did not have graphical corruptions.
Test: atest SurfaceFlinger_test libcompositionengine_test libsurfaceflinger_unittest
Test: go/wm-smoke

Port from ag/10112179

Change-Id: I60cc6b58efc0e95c5ccc204830a3d76d2e7633c7

6 files changed, 46 insertions, 15 deletions

diff --git a/services/surfaceflinger/Layer.cpp b/services/surfaceflinger/Layer.cpp
index f4d4329f6d..4ac868e6a5 100644
--- a/services/surfaceflinger/Layer.cpp
+++ b/services/surfaceflinger/Layer.cpp
@@ -1795,6 +1795,15 @@ void Layer::traverseInReverseZOrder(LayerVector::StateSet stateSet,
     }
 }
 
+void Layer::traverse(LayerVector::StateSet state, const LayerVector::Visitor& visitor) {
+    visitor(this);
+    const LayerVector& children =
+            state == LayerVector::StateSet::Drawing ? mDrawingChildren : mCurrentChildren;
+    for (const sp<Layer>& child : children) {
+        child->traverse(state, visitor);
+    }
+}
+
 LayerVector Layer::makeChildrenTraversalList(LayerVector::StateSet stateSet,
                                              const std::vector<Layer*>& layersInTree) {
     LOG_ALWAYS_FATAL_IF(stateSet == LayerVector::StateSet::Invalid,
diff --git a/services/surfaceflinger/Layer.h b/services/surfaceflinger/Layer.h
index ffe004f9e9..70532e9fd1 100644
--- a/services/surfaceflinger/Layer.h
+++ b/services/surfaceflinger/Layer.h
@@ -678,6 +678,15 @@ public:
 
     renderengine::ShadowSettings getShadowSettings(const Rect& viewport) const;
 
+    /**
+     * Traverse this layer and it's hierarchy of children directly. Unlike traverseInZOrder
+     * which will not emit children who have relativeZOrder to another layer, this method
+     * just directly emits all children. It also emits them in no particular order.
+     * So this method is not suitable for graphical operations, as it doesn't represent
+     * the scene state, but it's also more efficient than traverseInZOrder and so useful for
+     * book-keeping.
+     */
+    void traverse(LayerVector::StateSet stateSet, const LayerVector::Visitor& visitor);
     void traverseInReverseZOrder(LayerVector::StateSet stateSet,
                                  const LayerVector::Visitor& visitor);
     void traverseInZOrder(LayerVector::StateSet stateSet, const LayerVector::Visitor& visitor);
diff --git a/services/surfaceflinger/LayerVector.cpp b/services/surfaceflinger/LayerVector.cpp
index 7c959b9e56..9b94920408 100644
--- a/services/surfaceflinger/LayerVector.cpp
+++ b/services/surfaceflinger/LayerVector.cpp
@@ -86,6 +86,14 @@ void LayerVector::traverseInReverseZOrder(StateSet stateSet, const Visitor& visi
         layer->traverseInReverseZOrder(stateSet, visitor);
      }
 }
+
+void LayerVector::traverse(const Visitor& visitor) const {
+    for (auto i = static_cast<int64_t>(size()) - 1; i >= 0; i--) {
+        const auto& layer = (*this)[i];
+        layer->traverse(mStateSet, visitor);
+    }
+}
+
 } // namespace android
 
 // TODO(b/129481165): remove the #pragma below and fix conversion issues
diff --git a/services/surfaceflinger/LayerVector.h b/services/surfaceflinger/LayerVector.h
index 88d7711bb8..a531f4fd95 100644
--- a/services/surfaceflinger/LayerVector.h
+++ b/services/surfaceflinger/LayerVector.h
@@ -50,7 +50,7 @@ public:
     using Visitor = std::function<void(Layer*)>;
     void traverseInReverseZOrder(StateSet stateSet, const Visitor& visitor) const;
     void traverseInZOrder(StateSet stateSet, const Visitor& visitor) const;
-
+    void traverse(const Visitor& visitor) const;
 private:
     const StateSet mStateSet;
 };
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index 6d18922a78..9136593d01 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -2039,7 +2039,7 @@ void SurfaceFlinger::postComposition()
         compositorTiming = getBE().mCompositorTiming;
     }
 
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    mDrawingState.traverse([&](Layer* layer) {
         bool frameLatched = layer->onPostComposition(displayDevice, glCompositionDoneFenceTime,
                                                      presentFenceTime, compositorTiming);
         if (frameLatched) {
@@ -2463,7 +2463,7 @@ void SurfaceFlinger::handleTransactionLocked(uint32_t transactionFlags)
     const nsecs_t expectedPresentTime = mExpectedPresentTime.load();
 
     // Notify all layers of available frames
-    mCurrentState.traverseInZOrder([expectedPresentTime](Layer* layer) {
+    mCurrentState.traverse([expectedPresentTime](Layer* layer) {
         layer->notifyAvailableFrames(expectedPresentTime);
     });
 
@@ -2473,7 +2473,7 @@ void SurfaceFlinger::handleTransactionLocked(uint32_t transactionFlags)
      */
 
     if ((transactionFlags & eTraversalNeeded) || mTraversalNeededMainThread) {
-        mCurrentState.traverseInZOrder([&](Layer* layer) {
+        mCurrentState.traverse([&](Layer* layer) {
             uint32_t trFlags = layer->getTransactionFlags(eTransactionNeeded);
             if (!trFlags) return;
 
@@ -2520,7 +2520,7 @@ void SurfaceFlinger::handleTransactionLocked(uint32_t transactionFlags)
         sp<const DisplayDevice> hintDisplay;
         uint32_t currentlayerStack = 0;
         bool first = true;
-        mCurrentState.traverseInZOrder([&](Layer* layer) {
+        mCurrentState.traverse([&](Layer* layer) {
             // NOTE: we rely on the fact that layers are sorted by
             // layerStack first (so we don't have to traverse the list
             // of displays for every layer).
@@ -2744,7 +2744,7 @@ void SurfaceFlinger::commitTransactionLocked() {
     // clear the "changed" flags in current state
     mCurrentState.colorMatrixChanged = false;
 
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    mDrawingState.traverse([&](Layer* layer) {
         layer->commitChildList();
 
         // If the layer can be reached when traversing mDrawingState, then the layer is no
@@ -2755,7 +2755,7 @@ void SurfaceFlinger::commitTransactionLocked() {
     });
 
     commitOffscreenLayers();
-    mDrawingState.traverseInZOrder([&](Layer* layer) { layer->updateMirrorInfo(); });
+    mDrawingState.traverse([&](Layer* layer) { layer->updateMirrorInfo(); });
 }
 
 void SurfaceFlinger::withTracingLock(std::function<void()> lockedOperation) {
@@ -2780,7 +2780,7 @@ void SurfaceFlinger::withTracingLock(std::function<void()> lockedOperation) {
 
 void SurfaceFlinger::commitOffscreenLayers() {
     for (Layer* offscreenLayer : mOffscreenLayers) {
-        offscreenLayer->traverseInZOrder(LayerVector::StateSet::Drawing, [](Layer* layer) {
+        offscreenLayer->traverse(LayerVector::StateSet::Drawing, [](Layer* layer) {
             uint32_t trFlags = layer->getTransactionFlags(eTransactionNeeded);
             if (!trFlags) return;
 
@@ -2821,7 +2821,7 @@ bool SurfaceFlinger::handlePageFlip()
     // 3.) Layer 1 is latched.
     // Display is now waiting on Layer 1's frame, which is behind layer 0's
     // second frame. But layer 0's second frame could be waiting on display.
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    mDrawingState.traverse([&](Layer* layer) {
         if (layer->hasReadyFrame()) {
             frameQueued = true;
             if (layer->shouldPresentNow(expectedPresentTime)) {
@@ -2839,7 +2839,7 @@ bool SurfaceFlinger::handlePageFlip()
     // be shown on screen. Therefore, we need to latch and release buffers of offscreen
     // layers to ensure dequeueBuffer doesn't block indefinitely.
     for (Layer* offscreenLayer : mOffscreenLayers) {
-        offscreenLayer->traverseInZOrder(LayerVector::StateSet::Drawing,
+        offscreenLayer->traverse(LayerVector::StateSet::Drawing,
                                          [&](Layer* l) { l->latchAndReleaseBuffer(); });
     }
 
@@ -2874,7 +2874,7 @@ bool SurfaceFlinger::handlePageFlip()
         mBootStage = BootStage::BOOTANIMATION;
     }
 
-    mDrawingState.traverseInZOrder([&](Layer* layer) { layer->updateCloneBufferInfo(); });
+    mDrawingState.traverse([&](Layer* layer) { layer->updateCloneBufferInfo(); });
 
     // Only continue with the refresh if there is actually new work to do
     return !mLayersWithQueuedFrames.empty() && newDataLatched;
@@ -3696,7 +3696,7 @@ std::string SurfaceFlinger::getUniqueLayerName(const char* name) {
     bool matchFound = true;
     while (matchFound) {
         matchFound = false;
-        mCurrentState.traverseInZOrder([&](Layer* layer) {
+        mCurrentState.traverse([&](Layer* layer) {
             if (layer->getName() == uniqueName) {
                 matchFound = true;
                 uniqueName = base::StringPrintf("%s#%u", name, ++dupeCounter);
@@ -4067,7 +4067,7 @@ void SurfaceFlinger::clearStatsLocked(const DumpArgs& args, std::string&) {
     const bool clearAll = args.size() < 2;
     const auto name = clearAll ? String8() : String8(args[1]);
 
-    mCurrentState.traverseInZOrder([&](Layer* layer) {
+    mCurrentState.traverse([&](Layer* layer) {
         if (clearAll || layer->getName() == name.string()) {
             layer->clearFrameStats();
         }
@@ -4083,7 +4083,7 @@ void SurfaceFlinger::dumpTimeStats(const DumpArgs& args, bool asProto, std::stri
 // This should only be called from the main thread.  Otherwise it would need
 // the lock and should use mCurrentState rather than mDrawingState.
 void SurfaceFlinger::logFrameStats() {
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    mDrawingState.traverse([&](Layer* layer) {
         layer->logFrameStats();
     });
 
@@ -4318,7 +4318,7 @@ void SurfaceFlinger::dumpOffscreenLayers(std::string& result) {
     result.append("Offscreen Layers:\n");
     postMessageSync(new LambdaMessage([&]() {
         for (Layer* offscreenLayer : mOffscreenLayers) {
-            offscreenLayer->traverseInZOrder(LayerVector::StateSet::Drawing, [&](Layer* layer) {
+            offscreenLayer->traverse(LayerVector::StateSet::Drawing, [&](Layer* layer) {
                 layer->dumpCallingUidPid(result);
             });
         }
@@ -5544,6 +5544,10 @@ void SurfaceFlinger::setInputWindowsFinished() {
 
 // ---------------------------------------------------------------------------
 
+void SurfaceFlinger::State::traverse(const LayerVector::Visitor& visitor) const {
+    layersSortedByZ.traverse(visitor);
+}
+
 void SurfaceFlinger::State::traverseInZOrder(const LayerVector::Visitor& visitor) const {
     layersSortedByZ.traverseInZOrder(stateSet, visitor);
 }
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index 7f7d8da245..43cc50f04c 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -380,6 +380,7 @@ private:
 
         renderengine::ShadowSettings globalShadowSettings;
 
+        void traverse(const LayerVector::Visitor& visitor) const;
         void traverseInZOrder(const LayerVector::Visitor& visitor) const;
         void traverseInReverseZOrder(const LayerVector::Visitor& visitor) const;
     };