Signal and Message Reordering #200

Closed zeenix closed 1 year ago

In GitLab by @danieldg on Aug 13, 2021, 01:30

At the moment, if two Proxy objects and wait on both of them for a signal or property change, the order in which you get the signals is not defined. This could be an issue if there is in fact a caused-by relationship between the two signals resulting that the user code relies on.

Possible concrete example: the Inner part of an Interface is updated by a task that polls the NameAcquiredStream to get a list of all names of a certain pattern (say, org.mpris.MediaPlayer2.*). A client registers a name, waits for dbus to acknowledge it, then sends a request to the interface that expects it to be registered using that name. However, the task scheduler decides to run the ObjectServer task first and so the interface will reject the request - even though it's valid.

Caching after lazy activation has the same issue - the NameAcquired on the well-known name might be processed after the first signal from the owner of that name, resulting in the proxy rejecting the mismatching signal.

~~Not sure how much of a problem this is, but it does have the ability to cause problems in some code - and it may become more important depending on how property caching works.~~

Related: #178

A possible solution to both #178 and this would be to run the connect_foo closures in the MessageReceiverTask. Then you just need to document that all of the Stream APIs have the potential to lose or reorder inbound messages.

Update: this also applies to method returns that populate a cache, such as GetAll for properties cache or GetNameOwner/NameAcquired on proxies associated with a well-known name.

The D-Bus spec doesn't not have an requirements on the order of messages so I don't think you can even rely on the order of messages received from the bus/broker itself. If you can't rely on that, zbus has no means of guaranteeing the order of messages.

So I'd not worry too much about it and document this fact at best so app developers don't rely on order of messages and/or callbacks etc.

Aparently there was a unfinished attempt to add ordering requirement to the spec 4 years ago.

In GitLab by @danieldg on Aug 13, 2021, 15:47

That issue seems to say that ordering requirements are mostly met by the current bus implementations and that a number of applications rely on them. Do we want to require applications using zbus to be robust to reordering of messages, even when the bus itself doesn't do that?

yeah, I forgot to follow-up. Seems the reference bus implementation does guarantee message ordering. The thing is that on the low-level zbus also guarantees that for each connection/stream. The two (or rather N) different connections/signals OTOH are not guaranteed to receive their messages in a specific order. I'm also unsure if the broker guarantees this between multiple connections (could be the same app even) either though. i-e if message M1 is sent before M2, is a connection C1 guaranteed to receive M1 before connection C2 receives M2? :thinking:

In GitLab by @danieldg on Aug 14, 2021, 01:43

If the high-level API you are providing is that every Connection, Proxy, PropertyStream, and SignalStream act like independent dbus connections, then yes: the reordering behavior matches what would happen if that was what was happening, except for any interactions with DBusProxy.

Another example: it should be possible to cache the output of DBusProxy::list_names by subscribing to name_acquired, name_lost, and name_owner_changed, and then running list_names once to populate the cache. However, if you use the receive_* API, you'll eventually observe some short-lived client (busctl, for example) whose add and remove events are processed in the wrong order.

This is an inherent problem with the Stream-based API, and I'm not sure it can be fixed without changing the entire duplicate-and-broadcast backing that zbus uses. The connect_* API doesn't have this issue at the per-Proxy level, but it does (currently) have it between Proxy instances - but it's possible to address that.

Another example: it should be possible to cache the output of DBusProxy::list_names by subscribing to name_acquired, name_lost, and name_owner_changed, and then running list_names once to populate the cache. However, if you use the receive_* API, you'll eventually observe some short-lived client (busctl, for example) whose add and remove events are processed in the wrong order.

True. There is a serial number of every message though so maybe we can provide some mechanism to user to identify which came first at least?

Just FYI, this also meant I had to cater for one signal being handled before another for !367.

In GitLab by @smcv on Sep 7, 2021, 21:23

Seems the reference bus implementation does guarantee message ordering

The reference dbus-daemon provides "total ordering", which is probably the strongest ordering requirement that is practically implementable (strongest = easiest for D-Bus users = most difficult for message bus implementers).

The reference dbus-daemon processes all messages in some order of its choice, so you can point to any pair of messages and say either "A happened before B" or "B happened before A". Each connection sees some subset of the complete message stream (depending on its match rules, monitor status, etc.), so it will not necessarily see both A and B - but if it does, then they appear in the same order that the dbus-daemon processed them, for every recipient.

I think the weakest ordering requirement that makes sense is "causal ordering", which roughly means you always see cause before effect, but the order of unrelated messages might vary. More formally, if a connection sends message A, and another connection receives message A and then sends message B, then any third connection that sees both A and B will see them in that order; but if one connection sends message C and another connection sends message D at about the same time, then an observer might see either C,D or D,C.

Messages from the same sender are also ordered: if the same sender sends A followed by B, then any observer that sees both A and B received by the same connection will see A,B, and never B,A.

One reason why the attempt to add the ordering requirement to the spec stalled is that it wasn't entirely clear what is guaranteed and what is implementation detail.

I'm also unsure if the broker guarantees this between multiple connections (could be the same app even) either though. i-e if message M1 is sent before M2, is a connection C1 guaranteed to receive M1 before connection C2 receives M2?

No, this cannot be guaranteed. You might find that M1 spends 20ms passing through user-space buffers, the kernel, user-space buffers again, and the recipient's event loop, while M2 only takes 10ms, resulting in M2 being processed by C2 before M1 can be processed by C1.

Similarly, if a sender sends M1, and 5ms later, a different sender sends M2, you might find that M1 takes 20ms to get through to the dbus-daemon and M2 only takes 10ms, resulting in M2 being processed by the dbus-daemon before M1.

The thing is that on the low-level zbus also guarantees that for each connection/stream. The two (or rather N) different connections/signals OTOH are not guaranteed to receive their messages in a specific order.

If you poll multiple AF_UNIX stream connections with poll() or equivalent, you cannot guarantee what order they will be processed in. This is why, if two senders submit messages to dbus-daemon at about the same time, we cannot say which one the dbus-daemon will deal with first. We can only say that whichever arbitrary order the dbus-daemon has chosen to process them in is consistent between all observers.

If you take messages from one AF_UNIX stream connection and demultiplex them in user code in a way that does not preserve order, then that will break some (perhaps even most!) D-Bus interfaces. Telepathy is definitely an example of a protocol that relies on this not happening.

it should be possible to cache the output of DBusProxy::list_names by subscribing to name_acquired, name_lost, and name_owner_changed, and then running list_names once to populate the cache

Many (perhaps even most!) D-Bus interfaces rely on this sort of thing being possible, sometimes involving more than one object path in the same service.

There is a serial number of every message

Even in sender implementations that treat the "serial number" as ... serial, it is only unique and only ordered per-sender, not globally. You might find that gnome-shell is sending messages 23, 24, 25 at around the same time that pulseaudio is sending 137, 138, 139.

However, sender implementations are not required to assign consecutive serial numbers to their messages, and can even go backwards. sd-bus refers to it as a "cookie" rather than "serial number" in APIs, because it isn't guaranteed to be serial.

The (only) intended use for the "serial number" is to match up method calls with method replies: if :1.23 sends message 123 to :1.42, we can remember the triple (:1.23, 123, :1.42), and match it up with a subsequent method reply sent by :1.42 to :1.23 with "in reply to serial number 123" in its header.

@smcv Thanks so much for all the detailed insights. Much appreciated!

A possible solution to both #178 and this would be to run the connect_foo closures in the MessageReceiverTask.

We do that now so I wonder if that solves the problem. :thinking:

Then you just need to document that all of the Stream APIs have the potential to lose or reorder inbound messages.

We also don't lose messages on the stream anymore since overflow mode was disabled. Can the message be re-ordered on the same stream still? :thinking:

A possible solution to both #178 and this would be to run the connect_foo closures in the MessageReceiverTask.

We do that now so I wonder if that solves the problem. :thinking:

Hmm... this change:

diff --git a/zbus/src/azync/proxy.rs b/zbus/src/azync/proxy.rs
index e4ae207e..fbe0bbe5 100644
--- a/zbus/src/azync/proxy.rs
+++ b/zbus/src/azync/proxy.rs
@@ -278,26 +277,12 @@ impl<'a> ProxyInner<'a> {
             return Ok(None);
         }

-        if h.interface() == Ok(Some(&self.interface)) && h.path() == Ok(Some(&self.path)) {
-            for _ in 0..2 {
-                let listener = self.dest_name_update_event.listen();
-                if h.sender()
-                    == Ok(self
-                        .dest_unique_name
-                        .read()
-                        .expect("lock poisoned")
-                        .as_deref())
-                {
-                    return Ok(h.member().ok().flatten());
-                }
-
-                // Due to signal and task run not being orderered (see issue#190), we can easily end
-                // up with handling a signal here **before** the destination's name ownership signal
-                // from the bus is handled. Therefore, if all other parameters of the signal match
-                // except for sender, we wait a bit for the possible name update before calling it
-                // a non-match.
-                select(listener, Timer::after(Duration::from_millis(100))).await;
-            }
+        let dest_name = self.dest_unique_name.read().expect("lock poisoned");
+        if h.interface() == Ok(Some(&self.interface))
+            && h.path() == Ok(Some(&self.path))
+            && h.sender() == Ok(dest_name.as_deref())
+        {
+            return Ok(h.member().ok().flatten());
         }

         Ok(None)

breaks this testcase though (1/4 times on my machine), which was the reason I added that waiting code.

In GitLab by @danieldg on Sep 8, 2021, 14:36

We do that now so I wonder if that solves the problem.

No, the most recent change just moves the connect_foo closures to the executor, which is still allowed to reorder its tasks.

Can the message be re-ordered on the same stream still?

Messages within a single stream could never be reordered, but using select on two streams to join them allows reordering (and there's no way to prevent that, it's just part of the Stream API).

mentioned in commit ae8c5f26421e5e1e29db4e8c8bd3455efbd8c1c7

Can the message be re-ordered on the same stream still?

Messages within a single stream could never be reordered, but using select on two streams to join them allows reordering (and there's no way to prevent that, it's just part of the Stream API).

We probably already discussed this but is this also true if the async runtimes involved are fair? If so, it's not something zbus needs to ensure. From what I understand from this blog post tokio does ensure fairness by default, for example (or at least attempts to). Now that you've changed the SignalStream to not rely on async-executor's scheduling (I'm not sure if that's also ensuring fairness or not but let's assume it's not), perhaps we can declare SignalStream to be ordered from our POV and leave the rest to the runtimes?

My main desire here is to ditch the signal connection API, which as you know has a deadlocking footgun, even though I've made it less severe in !408.

In GitLab by @danieldg on Oct 15, 2021, 16:09

Fairness might fix the simplest case where only two signals are involved, but if you add a third signal you can still get a mis-ordering:

Proper input is sigA, sigB, sigA; this gets processed in the receiver task, which runs until it returns Pending. Two tasks are waiting on sigA and sigB; due to fairness, A runs first, and reads both sigA messages before B runs.

And this gets worse if you use a multi-threaded runtime (in which case you can still race with only two signals).

hmm.. right. I'm still wondering if this is in any way specific to D-Bus or zbus, for us to provide a complete solution (especially if it comes with caveats). I'm fine with the complications inside the zbus code (i think it's still fairly clean) but providing two very different APIs for the same exact thing will confuse users and goes against our "easy" goal/slogan. Also keeping in mind, typically the signal order isn't important and as I said, with your recent changes we do send out the signals in the correct order on the streams.

In GitLab by @danieldg on Oct 15, 2021, 16:42

The "cache update signal" + "cache population method return" race still needs either a callback or another dedicated mechanism to address it. This is a general problem when you have split one stream (the dbus messages) into two (signals that actually modify the same conceptual object) but want to reassemble it in order. It's possible to solve this in other ways - by, for example, not splitting the stream in the first place and having a stream of parsed messages. That gets more complicated still (as mentioned in #188) because it requires the user to create the enum of the possible parsed messages.

In GitLab by @danieldg on Oct 15, 2021, 16:48

Another solution would be to have zbus itself add a sequence number to the Message objects and provide a recombination function that made sure to keep ordering. It would require the parsed-signal object to expose either the Message or this sequence number via a trait.

The "cache update signal" + "cache population method return" race still needs either a callback or another dedicated mechanism to address it.

That can still use the internal signal handler mechanism. I wasn't suggesting we ditch that completely, just not exposed in the pub API.

Another solution would be to have zbus itself add a sequence number to the Message objects and provide a recombination function that made sure to keep ordering. It would require the parsed-signal object to expose either the Message or this sequence number via a trait.

That actually doesn't sound bad to me and AFAICT doesn't require API breakage even. i-e we can design this solution and implement it post 2.0.

We could even re-use the D-Bus sequence number field as the one set by the bus doesn't really give anything to the user anyway.

In GitLab by @danieldg on Oct 15, 2021, 17:25

That actually doesn't sound bad to me and AFAICT doesn't require API breakage even. i-e we can design this solution and implement it post 2.0.

Yes, we could do that. Eliminate both connect_* and dispatch_* and maybe add a receive_* for method calls (which would also serve as giving them an ability to return non-owned types, in addition to ordering)

We could even re-use the D-Bus sequence number field as the one set by the bus doesn't really give anything to the user anyway.

I don't think this is suitable - that makes it an in-band signalling mechanism that is very likely to cause confusion. Also, putting it in Message means we can use u64 instead, which means we don't need to artificially limit our message count (even if a bus normally wouldn't allow hitting this, p2p on a long-running connection might hit it).

That actually doesn't sound bad to me and AFAICT doesn't require API breakage even. i-e we can design this solution and implement it post 2.0.

Yes, we could do that. Eliminate both connect_* and dispatch_*

Great. I'll modify !408 to do that. I'll also finish my wip branch to add blocking::{SignalStream, PropertyStream} as part of that.

and maybe add a receive_* for method calls (which would also serve as giving them an ability to return non-owned types, in addition to ordering)

You mean in server-side (dbus_interface)?

We could even re-use the D-Bus sequence number field as the one set by the bus doesn't really give anything to the user anyway.

I don't think this is suitable - that makes it an in-band signalling mechanism that is very likely to cause confusion. Also, putting it in Message means we can use u64 instead, which means we don't need to artificially limit our message count (even if a bus normally wouldn't allow hitting this, p2p on a long-running connection might hit it).

Sure. If it's supposed to be independent from the existing sequence number, I'd just make it a timestamp instead. That gives user more info and could potentially be used for some other niche use cases other than re-sequencing.

In GitLab by @danieldg on Oct 15, 2021, 19:07

You mean in server-side (dbus_interface)?

No, on dbus_proxy. Right now, all proxied calls must return owned types; if they could use a receive_* wrapper, they could return borrowed types instead (because the actual return type would be a struct wrapping a Arc<Message> that is parsed on demand, as is done for signals). Actually using non-owned types would require a separate helper declaration as in ffe0d43eada28681cf16b2c97bd8e4b7787ac2af.

Note this is another thing that can be deferred.

Sure. If it's supposed to be independent from the existing sequence number, I'd just make it a timestamp instead. That gives user more info and could potentially be used for some other niche use cases other than re-sequencing.

If it's a timestamp, it needs to be a monotonic timestamp (Instant) and also must be strictly increasing. I don't think Instant actually guarantees to increase between two successive calls - it will in practice on a system that provides nanosecond precision because I'm pretty sure there's no way zbus can parse a Message in a nanosecond, but some systems that rust supports might only provide millisecond timestamps.

It's possible to synthesize such a timestamp if needed (just hold the prior one and add 1ns if Instant::now is <= prev).

In GitLab by @smcv on Oct 15, 2021, 20:04

With D-Bus specification maintainer hat on:

Please don't overwrite the "serial number" that is in-band in the message header. I think it would be valid (although extremely unusual) for a D-Bus interface to have message content in the body that refers to previous messages by their "serial number".

(As I think I mentioned before, the "serial number" is not guaranteed to be increasing; systemd refers to it as the "cookie", which with hindsight would have been a more accurate name.)

In GitLab by @danieldg on Oct 15, 2021, 20:50

From a user's perspective, if I were going to use a timestamp, I would actually prefer an SO_TIMESTAMP from the socket and not a zbus-generated timestamp - especially as zbus's recv task can block (if the broadcast channel blocks) and will result in delayed timestamps if it does. Adding a timestamp to the protocol (added by the bus, like sender) would be even better, however; though if that's done then we still need our own sequence number to support existing buses.

Please don't overwrite the "serial number" that is in-band in the message header.

Thanks, gotcha. Won't do that. :) It was just me thinking out loud..

You mean in server-side (dbus_interface)?

No, on dbus_proxy. Right now, all proxied calls must return owned types; if they could use a receive_* wrapper, they could return borrowed types instead (because the actual return type would be a struct wrapping a Arc<Message> that is parsed on demand, as is done for signals). Actually using non-owned types would require a separate helper declaration as in ffe0d43eada28681cf16b2c97bd8e4b7787ac2af.

Ah, you wrote receive_* so I thought you meant a stream-creation API. We have #44 for exactly this.

From a user's perspective, if I were going to use a timestamp, I would actually prefer an SO_TIMESTAMP from the socket and not a zbus-generated timestamp

Sure. I don't know how portable that is but if we can't get it for a specific target platform, we can just fallback to producing it ourselves (which of course has the issue you pointed out but it's still better than nothing).

In GitLab by @danieldg on Oct 16, 2021, 02:16

See https://gitlab.freedesktop.org/danieldg/zbus/-/commits/issue-190 for a test of this issue.

In GitLab by @danieldg on Oct 16, 2021, 16:58

Unless we have a good reason to use a timestamp, I don't think it provides much value. If there was a timestamp added by the bus, I could see a good argument for synthesizing a timestamp from that and a local fallback, but otherwise it's just misleading - it's not directly related to when the message was sent.

mentioned in commit 864bae51316c0518f1fdded646eac05c13b5130f

dbus2 / zbus-old

Signal and Message Reordering #200