outside-dispatch-lock handlers

[Havoc Pennington]

Hi,

On Wed, 2006-03-01 at 11:14 +0100, Thiago Macieira wrote:
> >I _think_ that if we didn't have out-of-memory handling,
> >dbus_connection_dispatch() could simply pop_message() at the top and not
> >hold the dispatch lock while running handlers. The bus daemon does need
> >OOM handling though.
> 
> That would be my suggestion.
> 

The problem is that the bus daemons need OOM robustness (since if they
crash you have to reboot - for systemwide - or log out - for session,
and their untrusted clients can ask them to allocate memory).

Also, for example the Maemo/Nokia770 which uses dbus runs out of memory
every time you open more than 1 web page at a time in my experience...
they would have their bus daemon crashing if we used the normal GLib
policy of just exiting on OOM.

I am pretty confident that dbus handles OOM cleanly in almost all cases,
because the bus daemon test suite runs the tests over and over, failing
each allocation that the tests do and verifying correct behavior. When I
first coded that into the test suite I had to fix huge quantities of OOM
handling bugs, but I think it's pretty good now.

Anyway, it's pretty painful but for the most part the work is already
done. The GLib bindings apply the normal GLib policy as part of wrapping
dbus though (if they get OOM from dbus, they just exit). I would expect
that most bindings do something like this, e.g. Java would throw its
normal OutOfMemoryException, etc.

> The way things are, pop_message is probably the best for me right now, 
> since we're in "uncooperative mode" with other bindings. This would solve 
> the deadlocking and reentrancy problems for me.

Certainly that would work fine if you do a private connection. Just
never register filters/object-vtables. Though I'd still like to figure
out this dispatch() thing.

> I'm not sure if this applies here, though. Aside from handlers returning 
> out-of-memory conditions, how else can we run out of memory? Are we 
> trying to duplicate the message in memory (which could be a large chunk 
> of memory)?

The messages are the only thing that's large, but the bus daemon also
has to worry about clients forcing it to alloc lots of small things, or
evil clients carefully planning to successfully alloc a huge message and
then try a bunch of small mallocs until they get the failure. So the
library tries to handle failure of all allocations by atomically rolling
back whatever the public API did, and then returning a failure from the
public API.

The application has to do a ton of _additional_ work to handle OOM, and
I expect the bus daemon will be the only app that ever does this work.
For desktop apps I would think they'll always just want to exit if an
allocation fails, maybe with large messages as the only exception.

> >There may be an ordering problem also... 
> 
> However, a signal can be delivered many times to user code, through many 
> handlers. If any of the user functions recurse, we may end up processing 
> message 2 before all handlers had the chance to see message 1. That in 
> turn means the handlers could see the messages in this order: 1, 2, 2, 1.

Thinking through the idea of a "handler queue" seems to illustrate some
of the conceptual issues here, though I'm not sure it works as a real
implementation approach.

If you look at dbus_connection_dispatch() right now, it copies the list
of filters, then traverses the list. This is a simple way to be safe
against changes to the list while traversing it (if a handler
adds/removes handlers), though as I noted there's a bug in the current
code where we need to skip handlers that are removed during traversal,
which is easy enough.

The "handler queue" idea is that for each message, we build a list of
handlers to run like this, but also including the object path handlers
and (conceptually at least) any default handlers.

Instead of keeping this list only inside dbus_connection_dispatch(),
store it in the DBusConnection object.

Let's define "processing the handler queue" as:
 - for each handler in the queue that applies to the same
   message, run the handler
 - if a handler returns NEED_MEMORY, put it back in 
   the queue and return from dbus_connection_dispatch()
   (this is how you can get handlers for multiple distinct
   messages in the queue at the same time)
 - if a handler returns HANDLED, drop the rest of the queue 
   that applies to the same message, and return
 - if a handler returns NOT_YET_HANDLED, remove the handler
   and run the next handler

The overall dbus_connection_dispatch() algorithm then is:
 - if the handler queue is not empty, process the handler 
   queue and return. This runs handlers for at most one 
   message, possibly leaving handlers for more messages
   in the queue.
 - if the handler queue is empty, and the message queue
   is not empty, borrow the next message (take dispatch lock)
 - add all handlers for that message to the handler queue;
   if we run out of memory here, remove handlers and 
   return the message and return from dispatch
   (i.e. fail atomically)
 - once we've queued all handlers, steal the message
   (drop dispatch lock)
 - process the handler queue as defined earlier

OK so say we have signals A, B, C, with handlers:

A: 1, 2, 3
B: 4, 5, 6
C: 7, 8, 9

while dispatching A, inside handler 2 we dispatch again twice; we'd
first run handler 3, and then queue and run 4, 5, 6.

But the problem is that we don't know whether we should run 3 until we
know the return value of 2. i.e. right now there's a requirement that we
always _complete_ each handler before we can run the next.

The "outside handler" idea essentially splits each handler into two
halves:
 - the "will I handle this?" half
 - the "actually handle this" half

If we did that, we could run the "will I handle this?" half when we
build the handler queue, and the "actually handle this" half could be
run when we process the handler queue. This means that in the above
example, we would know whether 3 should be run or not, before 2 has
returned.

One way to think of this is that we're keeping all the state of
dbus_connection_dispatch() in the DBusConnection instead of local
variables. Whenever you call dbus_connection_dispatch(), it just
"resumes" where it was last. 

Keeping the above example, what if handler 2 decides to return
NEED_MEMORY after 3, 4, 5, 6 were already run recursively inside it... I
would say that 2 goes back on the head of the queue and gets re-run
until it succeeds, just because it seems as plausible as any other
behavior.

Hmm.

I think the effect of all this is that when a handler recurses, it
"jumps itself ahead" in the handler queue. i.e. if I'm handler 2, when I
recurse any number of the other handlers 3-9 could be called. When the
recursive dispatch returns, then handler 2 would be running _after_
handler 9. However, a handler does not jump _other_ handlers out of
order - handler 3 still runs before 4.

Say you are crazy and now you start calling dispatch() from several
threads at once... first theory is "don't do that then" but say we
wanted to invent something 'sane' to happen, my best suggestion is:
 - we hold a recursive lock when invoking a handler
 - that handler can recurse normally, other threads wait
this preserves ordering of handlers and still allows recursive dispatch.

Right now, there's another special case, which is
send_with_reply_and_block() (and the async version with
DBusPendingCall). This function simply queues up all messages *without*
dispatching them until it gets the method call reply; then it pulls the
method reply out of the queue (*without* dispatching it). In the handler
queue thought experiment, nothing would ever be added to the handler
queue for the reply message, and we would not run any handlers while
blocking for the reply.

I think this is normally a lot safer and nicer for apps than running all
the intermediate handlers up to the message reply, if they just want to
block for the message reply. But if you want to also process incoming
method calls etc. while blocking you would just avoid ever using
send_with_reply_and_block() from your current thread, only use
dispatch() or pop().

> Which brings us back to the problem of self-thread recursing. If the user 
> code recurses and wants to process more messages, there can only be two 
> possible outcomes: either we find the specific message that the user 
> wants to process among the many messages we're receiving, or we process 
> them all.
> 
> I chose solution #2 for the Qt bindings for the moment. DCOP's solution is 
> #1.

If I understand you correctly, my opinion is that solution #2 is right
for method calls and signals, and solution #1 is right for method
replies. Note that send_with_reply_and_block()/DBusPendingCall implement
solution #1 for method replies. Solution #2 I'm theorizing should work
as I just described above (the "handler queue" model)

> If you want to be cooperative to other bindings, you shouldn't call 
> dispatch but you should let whoever has the event loop to do it.

Yes, I think I agree. It really makes sense for only a single thread to
dispatch at a time. I think this means we do want a dispatch lock, and
if we want to support recursive handlers it should be a recursive lock.
The "handler queue" discussion above is an attempt to define how
recursion works in a sane/predictable way.
 
> >A more plausible scenario to me is that there's a main loop thread that
> >always calls dispatch(), and then some other threads that do
> >send_with_reply_and_block() so they need to watch the message queue for
> >their reply, but not dispatch the whole queue.
> 
> That sounds like a plausible scenario. Does d_c_s_w_r_a_b also block other 
> threads while waiting for its reply? I'm not that familiar with the code, 
> but I think it's using a wait condition and waiting for a wake-all event.

The wait condition is for an IO lock on the socket, which only needs to
be acquired to read/write from the socket. So it takes the IO lock in
order to then block on the socket. If several threads try to
send_with_reply_and_block, then one will block on the socket and the
others will block on the IO lock until they get woken up. The dispatch()
thread also participates in this, so whenever it needs to block it can
block either on the socket or on the IO lock. All these threads will be
queuing up messages as they read from the socket, but only the dispatch
thread will drain the queue - the send_with_reply_and_block threads will
just pull out the exact message they are waiting for, and otherwise
ignore everything.



Anyway, considering all this what concrete changes would be needed to
implement the "handler queue" semantics:
 - we need each handler to have both "will I handle?" and
   "actually handle" operations (ideally not provided by the app 
   programmer - bindings should be able to do these most of the time)
 - when calling the "will I handle?", recursion is not allowed/sensible,
   a non-recursive lock would be fine around these calls
 - when calling the "actually handle", recursion is allowed in the same 
   thread, a recursive lock would be used around these calls

We would have to work out the specific API changes to get the two
operations for each handler, or some clever way to avoid these changes.

The HANDLED_OUTSIDE_DISPATCH change effectively does add the two
operations, though in a sort of strange way. 

The current handler function becomes "will I handle?" and it returns
HANDLED_OUTSIDE_DISPATCH if yes, and NOT_YET_HANDLED if no.
If yes, then no further handlers are added to the handler queue for the
message, if no then this handler is added but others may be also.
(We could add a third value for "skip me" as an optimization, equivalent
to having a no-op "actually handle")
This function can't recursively dispatch.

The new "outside function" becomes "actually handle" and it really
doesn't need a return value at all, except to indicate whether it ran
out of memory. This function can recursively dispatch.

A "legacy" handler not aware of the new setup will behave a bit oddly,
since it will "actually handle" when asked "will you handle?" - this
means it will be ordered incorrectly with respect to handlers in new
code that get postponed until the handler queue is processed, and it
means that recursion won't be allowed inside a "legacy" handler.

If we ignored back compat, we could probably make this a lot less
confusing. Something like:

 enum HandlerCheckResult {
    INVOKE_HANDLER,
    INVOKE_HANDLER_THEN_STOP_PROCESSING,
    DO_NOT_INVOKE_HANDLER,
    NEED_MEMORY
 }

 enum HandlerInvokeResult {
    SUCCESS,
    NEED_MEMORY
 }

 class Handler {
   HandlerCheckResult check();
   HandlerInvokeResult invoke();
 }

Again, DO_NOT_INVOKE_HANDLER is just an optimization, equivalent to a
no-op invoke().

If we adopted these semantics, I think you could get your desired
bindings behavior without having to keep your own queue or anything -
recursion would work "out of the box" using dbus_connection_dispatch().

I have no idea if this mail makes sense to anyone but me though.

Havoc