layers: Rewrite VerifyQueueStateToSeq to be less wasteful

When we have the same queue appearing multiple times in the dependency
tree of the operations between queue->seq and seq, we would scrub that
part of the submission list recursively, potentially to a great depth,
eventually blowing the stack.

[This used to work fine when it was done as part of RetireWorkOnQueue, as
we'd have brought queue->seq up as we went, and the recursive call would
end up doing no work.]

Instead, explicitly track where we're up to on each queue as well as
where we'd like to be, and use an explicit stack of work to do rather
than using the call stack.

Fixes crash in VkLayerTests.LongSemaphoreChain with 32k semaphores.

V2: Explain what's going on
V3: Tweak for windows build

1 files changed, 51 insertions, 25 deletions

diff --git a/layers/core_validation.cpp b/layers/core_validation.cpp
index 3fe1b0df..6710388e 100644
--- a/layers/core_validation.cpp
+++ b/layers/core_validation.cpp
@@ -3904,38 +3904,64 @@ static void incrementResources(layer_data *dev_data, GLOBAL_CB_NODE *cb_node) {
 // For the given queue, verify the queue state up to the given seq number.
 // Currently the only check is to make sure that if there are events to be waited on prior to
 //  a QueryReset, make sure that all such events have been signalled.
-static bool VerifyQueueStateToSeq(layer_data *dev_data, QUEUE_STATE *queue, uint64_t seq) {
+static bool VerifyQueueStateToSeq(layer_data *dev_data, QUEUE_STATE *initial_queue, uint64_t initial_seq) {
     bool skip = false;
-    auto queue_seq = queue->seq;
-    std::unordered_map<VkQueue, uint64_t> other_queue_seqs;
-    auto sub_it = queue->submissions.begin();
-    while (queue_seq < seq) {
-        for (auto &wait : sub_it->waitSemaphores) {
-            auto &last_seq = other_queue_seqs[wait.queue];
-            last_seq = std::max(last_seq, wait.seq);
-        }
-        for (auto cb : sub_it->cbs) {
-            auto cb_node = GetCBNode(dev_data, cb);
-            if (cb_node) {
-                for (auto queryEventsPair : cb_node->waitedEventsBeforeQueryReset) {
-                    for (auto event : queryEventsPair.second) {
-                        if (dev_data->eventMap[event].needsSignaled) {
-                            skip |= log_msg(dev_data->report_data, VK_DEBUG_REPORT_ERROR_BIT_EXT,
-                                            VK_DEBUG_REPORT_OBJECT_TYPE_QUERY_POOL_EXT, 0, 0, DRAWSTATE_INVALID_QUERY, "DS",
-                                            "Cannot get query results on queryPool 0x%" PRIx64
-                                            " with index %d which was guarded by unsignaled event 0x%" PRIx64 ".",
-                                            (uint64_t)(queryEventsPair.first.pool), queryEventsPair.first.index, (uint64_t)(event));
+
+    // sequence number we want to validate up to, per queue
+    std::unordered_map<QUEUE_STATE *, uint64_t> target_seqs { { initial_queue, initial_seq } };
+    // sequence number we've completed validation for, per queue
+    std::unordered_map<QUEUE_STATE *, uint64_t> done_seqs;
+    std::vector<QUEUE_STATE *> worklist { initial_queue };
+
+    while (worklist.size()) {
+        auto queue = worklist.back();
+        worklist.pop_back();
+
+        auto target_seq = target_seqs[queue];
+        auto seq = std::max(done_seqs[queue], queue->seq);
+        auto sub_it = queue->submissions.begin() + int(seq - queue->seq);  // seq >= queue->seq
+
+        for (; seq < target_seq; ++sub_it, ++seq) {
+            for (auto &wait : sub_it->waitSemaphores) {
+                auto other_queue = GetQueueState(dev_data, wait.queue);
+
+                if (other_queue == queue)
+                    continue;   // semaphores /always/ point backwards, so no point here.
+
+                auto other_target_seq = std::max(target_seqs[other_queue], wait.seq);
+                auto other_done_seq = std::max(done_seqs[other_queue], other_queue->seq);
+
+                // if this wait is for another queue, and covers new sequence
+                // numbers beyond what we've already validated, mark the new
+                // target seq and (possibly-re)add the queue to the worklist.
+                if (other_done_seq < other_target_seq) {
+                    target_seqs[other_queue] = other_target_seq;
+                    worklist.push_back(other_queue);
+                }
+            }
+
+            for (auto cb : sub_it->cbs) {
+                auto cb_node = GetCBNode(dev_data, cb);
+                if (cb_node) {
+                    for (auto queryEventsPair : cb_node->waitedEventsBeforeQueryReset) {
+                        for (auto event : queryEventsPair.second) {
+                            if (dev_data->eventMap[event].needsSignaled) {
+                                skip |= log_msg(dev_data->report_data, VK_DEBUG_REPORT_ERROR_BIT_EXT,
+                                                VK_DEBUG_REPORT_OBJECT_TYPE_QUERY_POOL_EXT, 0, 0, DRAWSTATE_INVALID_QUERY, "DS",
+                                                "Cannot get query results on queryPool 0x%" PRIx64
+                                                " with index %d which was guarded by unsignaled event 0x%" PRIx64 ".",
+                                                (uint64_t)(queryEventsPair.first.pool), queryEventsPair.first.index, (uint64_t)(event));
+                            }
                         }
                     }
                 }
             }
         }
-        sub_it++;
-        queue_seq++;
-    }
-    for (auto qs : other_queue_seqs) {
-        skip |= VerifyQueueStateToSeq(dev_data, GetQueueState(dev_data, qs.first), qs.second);
+
+        // finally mark the point we've now validated this queue to.
+        done_seqs[queue] = seq;
     }
+
     return skip;
 }