Mojo EDK: Circulate MojoArmWatcher outputs to avoid starvation

mojo/edk/system/watcher_dispatcher.cc

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "mojo/edk/system/watcher_dispatcher.h"
 
+#include <algorithm>
 #include <limits>
 #include <map>
 
 #include "base/macros.h"
 #include "base/memory/ptr_util.h"
 #include "mojo/edk/system/watch.h"
 
 namespace mojo {
 namespace edk {
 
@@ skipping 169 matching lines @@
   if (watched_handles_.empty())
     return MOJO_RESULT_NOT_FOUND;
 
   if (ready_watches_.empty()) {
     // Fast path: No watches are ready to notify, so we're done.
     armed_ = true;
     return MOJO_RESULT_OK;
   }
 
   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;
+    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()));
 
-      const Watch* watch = entry.second.get();
-      if (!watch->ready())
-        continue;
+    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();
+    }
 
-      *(ready_contexts++) = watch->context();
-      *(ready_results++) = watch->last_known_result();
-      *(ready_signals_states++) = watch->last_known_signals_state();
-      ++(*num_ready_contexts);
+    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();
     }
   }
 
   return MOJO_RESULT_FAILED_PRECONDITION;
 }
 
 WatcherDispatcher::~WatcherDispatcher() {}
 
 }  // namespace edk
 }  // namespace mojo