0 capacity bounded channel?

Quoting bounded in async_std::channel - Rust

Capacity must be a positive number. If cap is zero, this function will panic.

In GoLang, there are situations where two goroutines sync up at a channel, one sending, one receiving.

Is it possible to emulate this behavior in Rust? My first thought was to use a 0-cap channel, but documentation says this will panic.

crossbeam channels support this (non-async) and there is an old discussion saying that this is not possible to transfer over to async in this issue. There might be more to it (?) but that's what I found so far.

1 Like

Thanks. The crux of that argument seems to be:

[context: 'that argument' referring to why Rust/async tasks can't have GoRoutine style sync channels]

With the latter you can block a whole thread, rather than just a "task", but this is significant because...?)

Because with threads pairing send-receive operations can really happen simultaneously, whereas this is not possible with tasks.

With tasks, the sending task can "offer" a send to the receiving task, yield with Poll::Pending , and then the receiving side can accept the offer and "commit" the operation by receiving the message, then return `Poll::Ready. But now the sending task can still drop the send future and thus cancel it.

What I'm getting at is, the sending and receiving side can't agree on whether an operation has been executed or was canceled with certainty. With threads, we can do that.

======================

The crux of the crux is then this sentence:

With tasks, the sending task can "offer" a send to the receiving task, yield with Poll::Pending , and then the receiving side can accept the offer and "commit" the operation by receiving the message, then return `Poll::Ready. But now the sending task can still drop the send future and thus cancel it.

So I understand the definition of the individual words in the sentence above, but I don't understand what is going on.

Can anyone lend a hand ?

In a case where channel size is 0 there is no intermediate space where the messages are being stored (like it is with normal channels), and in Rust's async-await implementation there is no way to guarantee that one of the parties doesn't disappear out of the blue (asynchronously) and so it's hard to synchronize the message being passed from one side to the other atomically (which has correctness and even memory safety consequences).

Sorry I don't understand this line. What is a situation where a GoRoutine can't disappear but a Rust async task can ?

I'm guessing this is referring to cancellation. If both the send and recv appear in a different select!, then it's not possible to have both of the following guarantees:

  1. If the sender select! chose a different branch than the send, then the recv branch in the receiver select! was not chosen.
  2. If the receiver select! chose a different branch than the recv, then the send branch in the sender select! was not chosen.

I'm pretty sure it's possible to make a channel that has either one, but a single channel implementation must choose, and cannot have both guarantees.

I'm guessing go is somehow able to circumvent this for their selects.

1 Like

c = bounded(0); // hypothetical

async fn receiver(c: channel) {   // r1
  select! {                       // r2
    x = c.next().await => { ... } // r3
    receiver_other_branch         // r4
  }
}

async fn sender(c: channel) {  // s1
  select! {                    // s2
    c.send(x).await => { ... } // s3
    sender_other_branch        // s4
  }
}

task::spawn(receiver(c.clone()));
task::spawn(sender(c.clone()));

Is the above a minimal 'this can fail example' ? It is still not clear to me how this can fail; because it seems either (1) s3, r3 are both run or (2) neither runs, by definition of 0 capacity channel.

The fact that it's impossible to implement a channel where you must get both of s3 and r3 if you get one of them is why you aren't finding any capacity-zero channels out there. No implementation gives you what you want.

I guess my question is:

  1. Is this impossible to do.

or

  1. This is possible, but no Rust async impl chooses to do it ?

====

If the answer is 1, what I don't understand is: why can GoRoutines do this ?

If the answer is 2, I can accept the answer as is.

The answer is 1. It's not possible. As for how Go can do it, well, their selects only work with channels, so its easier to augment them with extra features that you can't really have in async Rust.

I believe the formal model behind GoRoutines is Communicating sequential processes - Wikipedia .

Is there a formal model behind Rust's async tasks ? So in particular, if this is 'formally impossible' we should be able to construct some type of argument of the form:

Let A be any 'algorithm' that tries to do go-lang style sync channels in Rust:

Given A, we now construct a set of valid moves (with respect to the formal model for Rust's async tasks), and show how this leads to UB.

===

Not trying to be pedantic here, genuinely curious. I previously thought GoRoutines and Rust async tasks were quite similar; but now you are claiming there is some fundamental difference in terms of something that is possible to represent in one and impossible to represent in another.

Rust Futures only make progress when polled, which is a pretty fundamental difference from how similar things work in other languages -- Tasks in C# start running immediately and continue to do so in the background, for example.

I'd look into how goroutines are cancelled. Can they be externally cancelled? Or are they only cancelled via something like a CancellationToken Struct (System.Threading) | Microsoft Docs ?

1 Like

The model is just that futures are structs with a poll method and a waker, and that the runtime promises to poll your task "soon" if you wake the waker. Additionally, you can drop stuff instead of polling it, and this is valid even if it was woken.

The reason the channel can't guarantee something like this is that the channel has no influence on when other code drops its send or recv future. When the channel decides to exchange the message, if your runtime polls the send half first, followed by the recv half, then if the send half returns Ready you can't undo that even if the future containing the recv half decides to drop the recv future instead of polling it. Similarly the other way around. The only thing you can control is whether send or recv will return Ready first.

2 Likes

Ah, so the main difference is:

  1. go routines have to 'run to completion', they can't just suddenly get dropped in the middle of execution

  2. Once an Rust async task blocks, there is no guarantee it runs to completion. It is entirely possible it gets dropped.

If we go back to the example:

c = bounded(0); // hypothetical

async fn receiver(c: channel) {   // r1
  select! {                       // r2
    x = c.next().await => { ... } // r3
    receiver_other_branch         // r4
  }
}

async fn sender(c: channel) {  // s1
  select! {                    // s2
    c.send(x).await => { ... } // s3
    sender_other_branch        // s4
  }
}

task::spawn(receiver(c.clone()));
task::spawn(sender(c.clone()));

Suppose someone has a counter argument, it would go something like this?

At some point, the algorithm A has to unblock s3 or r3.

If it unblocks s3, we drop the receiver (still blocked).
It it unblocks r3, we drop the sender (still blocked).

The difference here between Rust async tasks and GoLang routines is:

  1. a blocked Rust async task may get dropped
  2. GoLang routines 'run to completion'

====

@alice @scottmcm : is the above logic the gist of the argument ?

Yeah, the existence of cancellation is basically the problem. It is possible to implement a channel that works like this if you also create a custom select! statement for it so you can have the channel internals communicate with the select statement, but it could still break if there's a normal select! anywhere above it in the callstack, because the ordinary select can cancel it at random times.

1 Like

One more thing: is there any reason the select!'s can't coordinate ? The logic above assumes that we can inject a drop in between the two select!'s .We can imagine an alternative runtime that works something like:

  1. select! holds a ref to everything, so nothing gets dropped until after select! is done

  2. the two select!'s agree to both wake up s3, r3; the data is copied into x = ...

  3. both select! then returns

You can use Barrier if you need to synchronize the sender and the receiver. When both tasks are at the barrier, a channel with capacity 1 can be used to send the message.

They can. That's essentially what I described when I talked about a custom select for the channel. But to do that, the select has to know about the specific channel you're using.

It's interesting to note how this falls into the same impossibility situation I described above. Essentially, the receiver might get cancelled during the recv call on the channel after passing the barrier, and the sender would never know.

1 Like

@alice: I think I finally understand the subtleties of all the async comments you were making now. Thanks for your patience in walking me through all this.

You're welcome.