Add a mechanism to extend a libevent based message pump.

Add a mechanism to extend a libevent based message pump.

Added an API to allow additional event sources to be injected
into the message pump to be polled on each iteration.  This is
part of a change to ensure that the X11 event queue is serviced
in a timely manner.

Bug: 661

BUG=
R=abarth@google.com, jamesr@chromium.org

Committed: efbff4237a8fb7075af1e98fee674b77d8580753

[jeffbrown, 2016-04-26 02:42:31]

jeffbrown@google.com changed reviewers:
+ abarth@google.com, jamesr@chromium.org

[abarth, 2016-04-26 02:45:01]

How does Chromium solve this problem on Linux?

[abarth, 2016-04-26 04:44:53]

LGTM but I'm not a base expert.  Probably should get input from James.

[jamesr, 2016-04-26 23:52:14]

On 2016/04/26 at 02:45:01, abarth wrote:
> How does Chromium solve this problem on Linux?

Chromium uses glib to talk to X11

[jamesr, 2016-04-26 23:53:31]

This is a really hot place in the loop to add an extra dispatch.  When do you
want DispatchXEvents() to be called, precisely?  Where's the corresponding code
in glib?

[jamesr, 2016-04-27 00:39:56]

(copying from email back to the review for posterity)

jeffbrown says:
> Glib does exactly this.
>
> Basically we need to pump X events before we block

Well, that's not what this patch does.  It pumps much more often

> And if we want the loop to be responsive (not get starved by other work), we
need to pump on every iteration.

Hm, do you need to pump even when the file descriptor isn't marked as readable? 
In other words, XPending can become true at any time without further
notification? 
https://lists.freedesktop.org/archives/xdg/2004-November/003690.html claims it
can, which seems frustrating.

That aside, there are two things that I think should be improved.  First, going
through an observer list (and then virtual dispatch on top) is very expensive to
do in the pump's core loop, especially when you really don't need that level of
generality.  If you're using this pump with X11 then there's only 1 thing you
could possibly be doing to service the X11 messages.  You should wire that up
more directly - i.e. have a delegate that can be wired up when using X that is
called.  In chromium several things use base::ObserverLists because a large
number of different codebases have to collaborate only through base but we have
a much smaller set of use cases so we should optimize for those.

Second, for the pump to work well it should do exactly 1 unit of work in each of
these calls.  The X11EventSource code (in the other patch) drains the X queue
completely in this call.  There's a path for it to stop draining when the
dispatcher is overridden, but that path appears unreachable in our codebase.  I
think you should make the delegate's contract clear in this layer that the call
should do either zero or one units of work and return a bool.  The pump will not
sleep until the delegate returns false so it'll drain just as promptly if there
is no other work to do but it won't be able to starve the rest of the loop.

[jeffbrown, 2016-04-27 06:14:21]

> > And if we want the loop to be responsive (not get starved by other work), we
> need to pump on every iteration.
> 
> Hm, do you need to pump even when the file descriptor isn't marked as
readable? 
> In other words, XPending can become true at any time without further
> notification? 
> https://lists.freedesktop.org/archives/xdg/2004-November/003690.html claims it
> can, which seems frustrating.

Yes, we need to pump even when the file descriptor isn't marked readable.  The
old code was assuming we didn't and that wasn't good enough.  So yes, we have to
call XPending on each iteration (unless we have reason to know there *still* is
stuff pending because we haven't dispatched everything, in which case we could
skip the check).

> That aside, there are two things that I think should be improved.  First,
going
> through an observer list (and then virtual dispatch on top) is very expensive
to
> do in the pump's core loop, especially when you really don't need that level
of
> generality.  If you're using this pump with X11 then there's only 1 thing you
> could possibly be doing to service the X11 messages.  You should wire that up
> more directly - i.e. have a delegate that can be wired up when using X that is
> called.  In chromium several things use base::ObserverLists because a large
> number of different codebases have to collaborate only through base but we
have
> a much smaller set of use cases so we should optimize for those.

Given how the code is structured today, we could have multiple X11 event sources
running in the same TYPE_UI message loop listening for events.  There's only
weak coupling here (using base as a rendezvous).  That's excess abstraction for
our purposes.  (We would be just fine with an X11-specialized MessageLoop; even
libevent is kind of overkill.)

So if you really want me to, I can replace the base::ObserverList with a
base::Callback and a CHECK for singularity, though I can't imagine it'll have a
noticeable performance impact.

> Second, for the pump to work well it should do exactly 1 unit of work in each
of
> these calls.  The X11EventSource code (in the other patch) drains the X queue
> completely in this call.  There's a path for it to stop draining when the
> dispatcher is overridden, but that path appears unreachable in our codebase. 
I
> think you should make the delegate's contract clear in this layer that the
call
> should do either zero or one units of work and return a bool.  The pump will
not
> sleep until the delegate returns false so it'll drain just as promptly if
there
> is no other work to do but it won't be able to starve the rest of the loop.

I think this is more debatable.  I'd argue that the X11 events are more timing
sensitive than many other things happening on that loop.  I'm more worried about
other tasks starving X11 than the other way around.

How would you feel about just catching up to the head of the X11 event queue on
each iteration?

bool Poll() {
  int count = XPending();
  if (!count) return false;
  while (count--) {
    XNextEvent(...)
    dispatch...
  }
  return true;
}

This is unfair (in terms of one-for-one interleaving of units of work) but
guarantees the pump will not starve (since the pending work is always finite).

[jamesr, 2016-04-27 17:19:31]

On 2016/04/27 at 06:14:21, jeffbrown wrote:
> > > And if we want the loop to be responsive (not get starved by other work),
we
> > need to pump on every iteration.
> > 
> > Hm, do you need to pump even when the file descriptor isn't marked as
readable? 
> > In other words, XPending can become true at any time without further
> > notification? 
> > https://lists.freedesktop.org/archives/xdg/2004-November/003690.html claims
it
> > can, which seems frustrating.
> 
> Yes, we need to pump even when the file descriptor isn't marked readable.  The
old code was assuming we didn't and that wasn't good enough.  So yes, we have to
call XPending on each iteration (unless we have reason to know there *still* is
stuff pending because we haven't dispatched everything, in which case we could
skip the check).

When XPending does return zero, this loop will (eventually) go to sleep until
one of the file descriptors it monitors becomes readable.  If XPending can
become true without the fd being readable, what ensures that we actually wake up
at all?

> 
> > That aside, there are two things that I think should be improved.  First,
going
> > through an observer list (and then virtual dispatch on top) is very
expensive to
> > do in the pump's core loop, especially when you really don't need that level
of
> > generality.  If you're using this pump with X11 then there's only 1 thing
you
> > could possibly be doing to service the X11 messages.  You should wire that
up
> > more directly - i.e. have a delegate that can be wired up when using X that
is
> > called.  In chromium several things use base::ObserverLists because a large
> > number of different codebases have to collaborate only through base but we
have
> > a much smaller set of use cases so we should optimize for those.
> 
> Given how the code is structured today, we could have multiple X11 event
sources running in the same TYPE_UI message loop listening for events.  There's
only weak coupling here (using base as a rendezvous).  That's excess abstraction
for our purposes.  (We would be just fine with an X11-specialized MessageLoop;
even libevent is kind of overkill.)
> 
> So if you really want me to, I can replace the base::ObserverList with a
base::Callback and a CHECK for singularity, though I can't imagine it'll have a
noticeable performance impact.

Using virtual dispatch will do the same thing at roughly equivalent cost to the
base::Callback but be less obscure.  Use a virtual.


> 
> > Second, for the pump to work well it should do exactly 1 unit of work in
each of
> > these calls.  The X11EventSource code (in the other patch) drains the X
queue
> > completely in this call.  There's a path for it to stop draining when the
> > dispatcher is overridden, but that path appears unreachable in our codebase.
 I
> > think you should make the delegate's contract clear in this layer that the
call
> > should do either zero or one units of work and return a bool.  The pump will
not
> > sleep until the delegate returns false so it'll drain just as promptly if
there
> > is no other work to do but it won't be able to starve the rest of the loop.
> 
> I think this is more debatable.  I'd argue that the X11 events are more timing
sensitive than many other things happening on that loop.  I'm more worried about
other tasks starving X11 than the other way around.
> 
> How would you feel about just catching up to the head of the X11 event queue
on each iteration?

No, don't do that.  Having this even type follow different rules from everything
else in the pump will lead to all sorts of problems.  If you follow the same
pattern as other task sources in the pump you'll get the exact same behavior
when other events are not pending (it'll drain the X11 queue before sleeping)
and better behavior in contention.  If you want prioritization, the proper way
to write that into a MessageLoop is by having different task sources and a
proper scheduler.

> 
> bool Poll() {
>   int count = XPending();
>   if (!count) return false;
>   while (count--) {
>     XNextEvent(...)
>     dispatch...
>   }
>   return true;
> }
> 
> This is unfair (in terms of one-for-one interleaving of units of work) but
guarantees the pump will not starve (since the pending work is always finite).

[jeffbrown, 2016-04-27 20:33:24]

Respectfully, both the old glib-based and libevent-based code prioritized
dispatching X11 events as soon as possible.  Based on experience with Android
input, I believe that's the right behavior for responsiveness.

We can talk later about how we should structure message loops to make such
prioritization more apparent.  There are deeper problems than make sense to
resolve in this patch set.

[jamesr, 2016-04-28 18:27:49]

I agree that prioritization can be important, but this implementation proposal
simply won't work on its own.  As proposed the pump will get easily overloaded
with unbalanced work queues in contended cases.  There are certainly other
approaches to scheduling that could work well but they would require deeper
changes.

Since I doubt we'll be doing detailed performance studies on X11, I think the
most important thing for this patch is for it to work reliably, which means
doing 1 unit of work in a call out from the pump.  If that produces unacceptable
performance in some cases we can analyse those cases and determine the best
course of action.

I am 100% not OK with landing broken code here just because something similar
produced good results in a different system.

[jamesr, 2016-04-28 20:52:47]

The policy decision is over in the X11 event source, so that doesn't have to be
resolved to land this.

The latest version looks fine although you should add a test to
message_pump_libevent_unittest.cc to verify that this call happens when you
expect.  You can run the base unit tests with 'mojob.py test' or by running
out/Debug/base_unittests.  Once you add that lgtm.

[jeffbrown, 2016-05-04 20:00:49]

Description was changed from

==========
Add a mechanism to extend a libevent based message pump.

Added an API to allow additional event sources to be injected
into the message pump to be polled on each iteration.  This is
part of a change to ensure that the X11 event queue is serviced
in a timely manner.

Bug: 661

BUG=
==========

to

==========
Add a mechanism to extend a libevent based message pump.

Added an API to allow additional event sources to be injected
into the message pump to be polled on each iteration.  This is
part of a change to ensure that the X11 event queue is serviced
in a timely manner.

Bug: 661

BUG=
R=abarth@google.com, jamesr@chromium.org

Committed: efbff4237a8fb7075af1e98fee674b77d8580753
==========

[jeffbrown, 2016-05-04 20:00:52]

Committed patchset #4 (id:60001) manually as
efbff4237a8fb7075af1e98fee674b77d8580753 (presubmit successful).