Mojo EDK: Circulate MojoArmWatcher outputs to avoid starvation

mojo/edk/system/watcher_dispatcher.cc

Index: mojo/edk/system/watcher_dispatcher.cc
diff --git a/mojo/edk/system/watcher_dispatcher.cc b/mojo/edk/system/watcher_dispatcher.cc
index e4cc875580ad3f82322cf6559dc3f4ac677d1e71..409dd2a9229cff2cfa5041826545bd7f08544c69 100644
--- a/mojo/edk/system/watcher_dispatcher.cc
+++ b/mojo/edk/system/watcher_dispatcher.cc
@@ -4,6 +4,7 @@
 
 #include "mojo/edk/system/watcher_dispatcher.h"
 
+#include <algorithm>
 #include <limits>
 #include <map>
 
@@ -193,20 +194,32 @@ MojoResult WatcherDispatcher::Arm(
   }
 
   if (num_ready_contexts) {
-    uint32_t max_ready_contexts = *num_ready_contexts;
-    *num_ready_contexts = 0;
-    for (auto& entry : watched_handles_) {
-      if (max_ready_contexts == *num_ready_contexts)
-        break;
-
-      const Watch* watch = entry.second.get();
-      if (!watch->ready())
-        continue;
-
-      *(ready_contexts++) = watch->context();
-      *(ready_results++) = watch->last_known_result();
-      *(ready_signals_states++) = watch->last_known_signals_state();
-      ++(*num_ready_contexts);
+    DCHECK_LE(ready_watches_.size(), std::numeric_limits<uint32_t>::max());
+    *num_ready_contexts = std::min(
+        *num_ready_contexts, static_cast<uint32_t>(ready_watches_.size()));
+
+    WatchSet::const_iterator next_ready_iter = ready_watches_.begin();
+    if (last_watch_to_block_arming_) {
+      // Find the next watch to notify in simple round-robin order on the
+      // |ready_watches_| map, wrapping around to the beginning if necessary.
+      next_ready_iter = ready_watches_.find(last_watch_to_block_arming_);
+      if (next_ready_iter != ready_watches_.end())
+        ++next_ready_iter;
+      if (next_ready_iter == ready_watches_.end())
+        next_ready_iter = ready_watches_.begin();
+    }
+
+    for (size_t i = 0; i < *num_ready_contexts; ++i) {
+      const Watch* const watch = *next_ready_iter;
+      ready_contexts[i] = watch->context();
+      ready_results[i] = watch->last_known_result();
+      ready_signals_states[i] = watch->last_known_signals_state();
+
+      // Iterate and wrap around.
+      last_watch_to_block_arming_ = watch;

[yzshen1, 2017/03/16 21:06:17]

nit: it might further simplify the code by:
============================
Calculate |last_ready_iter| from |last_watch_to_block_arming_|.

for (...) {
  Calculate next and assign it to |last_read_iter|.
  Assign to output param.
}

Update |last_watch_to_block_arming_| from |last_read_iter|.

[Ken Rockot(use gerrit already), 2017/03/16 21:17:35]

It seems like a simplification at first, but in practice I think it's kind of a
wash either way.

The issue is that last_watch_to_block_arming_ may be invalid, and in that case
we don't really have a valid notion of a "last ready" iterator.

We could in that case initialize it to end() before entering the loop, but then
the loop logic gets gnarly. You could start the loop by resetting to begin() if
at end(), but normally you want to start the loop by iterating (and potentially
wrapping around) - so what you end up with would look something like:

for (...) {
  if (iter == end()) {
    iter = begin()
  } else {
    ++iter;
    if (iter == end())
      iter = begin();
  }
}

or

you could default to begin() when there's no last_watch:

if (last_watch) { ... }
else iter = begin();

for (...) {
  ++iter;
  if (iter == end())
    iter = begin();
  // ...
}

which looks much nicer, but can incorrectly skip the first entry in the
collection, so it's not correct.

For now I will land as-is and maybe we can talk about a cleaner way to do this
if I've missed something. Thanks!

+      ++next_ready_iter;
+      if (next_ready_iter == ready_watches_.end())
+        next_ready_iter = ready_watches_.begin();
     }
   }