5 ms·

This sounds very similar to priority inversion. E.g. if you have Thread T_high running at high priority and thread T_low running at low priority, and T_low hold

by singron 11mo ago

This sounds very similar to priority inversion. E.g. if you have Thread T_high running at high priority and thread T_low running at low priority, and T_low holds a lock that T_high wants to acquire, T_high won't get to run until T_low gets scheduled. The OS can detect this and make T_low "inherit" the priority of T_high. I wonder if there is a similar idea possible with tokio? E.g. if you are awaiting a Mutex held by a future that "can't run", then poll that future instead. I would guess detecting the "can't run" case would require quite a bit of overhead, but maybe it can be done. I think an especially difficult factor is that you don't even need to use a direct await. let future1 = do_async_thing("op1", lock.clone()).boxed(); tokio::select! { _ = &mut future1 => { println!("do_stuff: arm1 future finished"); } _ = sleep(Duration::from_millis(500)) => { // No .await, but both will futurelock on future1. tokio::select! { _ = do_async_thing("op2", lock.clone()) => {}, _ = do_async_thing("op3", lock.clone()) => {}, }; } }; I.e. so "can't run" detector needs to determine that no other task will run the future, and the future isn't in the current set of things being polled by this task.

oconnor663 11mo ago
> I wonder if there is a similar idea possible with tokio? E.g. if you are awaiting a Mutex held by a future that "can't run", then poll that future instead. Something like this could make sense for Tokio tasks. (I don't know how complicated their task scheduler is; maybe it already does stuff like this?) But it's not possible for futures within a task, as in this post. This goes all the way back to the "futures are inert" design of async Rust: You don't necessarily need to communicate with the runtime at all to create a future or to poll it or to stop polling it. You only need to talk to the runtime at the task level, either to spawn new tasks, or to wake up your own task. Futures are pretty much just plain old structs, and Tokio doesn't know how many futures my async function creates internally, any more than it knows about my integers or strings or hash maps.
- mycoliza 11mo ago
  Yeah, a coworker coming from Go asked a similar question about why Rust doesn't have something like the Go runtime's deadlock detector. Your comment is quite similar to the explanation I gave him. Go, unlike Rust, does not really have a notion of intra-task concurrency; goroutines are the fundamental unit of concurrency and parallelism. So, the Go runtime can reason about dependencies between goroutines quite easily, since goroutines are the things which it is responsible for scheduling. The fact that channels are a language construct, rather than a library construct implemented in the language, is necessary for this too. In (async) Rust, on the other hand, tasks are the fundamental unit of parallelism, but not of concurrency; concurrency emerges from the composition of `Future`s, and a single task is a state machine which may execute any number of futures concurrently (but not in parallel), by polling them until they cannot proceed without waiting and then moving on to poll another future until it cannot proceed without waiting. But critically, this is not what the task scheduler sees; it interacts with these tasks as a single top-level `Future`, and is not able to look inside at the nested futures they are composed of. This specific failure mode can actually only happen when multiple futures are polled concurrently but not in parallel within a single Tokio task. So, there is actually no way for the Tokio scheduler to have insight into this problem. You could imagine a deadlock detector in the Tokio runtime that operates on the task level, but it actually could never detect this problem, because when these operations execute in parallel, it actually cannot occur. In fact, one of the suggestions for how to avoid this issue is to select over spawned tasks rather than futures within the same task.
  - mjevans 11mo ago
    Thank you. Every time I've tried to approach the concept of Rust's parallelism this is what rubs me the wrong way. I haven't yet read a way to prove it's correct, or even to reasonably prove a given program's use is not going to block. With more traditional threads my mental model is that _everything_ always has to be interrupt-able, have some form of engineer chosen timeout for a parallel operation, and address failure of operation in design. I never see any of that in the toy examples that are presented as educational material. Maybe Rust's async also requires such careful design to be safely utilized.
    - 11mo ago
- newpavlov 11mo ago
  >This goes all the way back to the "futures are inert" design of async Rust Yeap. And this footgun is yet another addition to the long list of reasons why I consider the Rust async model with its "inert" futures managed in user space a fundamentally flawed un-Rusty design.
  - filleduchaos 11mo ago
    I feel there's a difference between a preference and a flaw. Rust has targets that make anything except inert futures simply unworkable, and in my opinion it's entirely valid for a programming language to prioritise those targets.
    - Rusky 11mo ago
      The requirement is that the futures are not separate heap allocations, not that they are inert. It's not at all obvious that Rust's is the only possible design that would work here. I strongly suspect it is not. In fact, early Rust did some experimentation with exactly the sort of stack layout tricks you would need to approach this differently. For example, see Graydon's post here about the original implementation of iterators, as lightweight coroutines: https://old.reddit.com/r/ProgrammingLanguages/comments/141qm6g/the_rust_i_wanted_had_no_future_graydon_hoare/jyldotb/?context=8 https://old.reddit.com/r/ProgrammingLanguages/comments/141qm...
      - filleduchaos 11mo ago
        On the other hand, early Rust also for instance had a tracing garbage collector; it's far from obvious to me how relevant its discarded design decisions are supposed to be to the language it is today.
        Rusky 11mo ago
        This one is relevant because it avoids heap allocation while running the iterator and for loop body concurrently. Which is exactly the kind of thing that `async` does.
Veserv 11mo ago
I thought Rust async is a colored stackless coroutine model and thus it would be unsafe to continue execution of previously executing async functions. To explain, generally speaking, stackless coroutine async only need coloring because they are actually “independent stack”less coroutines. What they actually do is that they share the stack for their local state. This forces async function execution to proceed in LIFO order so you do not blow away the stack of the async function executing immediately after which demands state machine transforms to be safe. This is why you need coloring unlike stackful coroutine models which can execute, yield, and complete in arbitrary order since their local state is preserved in a safe location.
- treyd 11mo ago
  > thus it would be unsafe to continue execution of previously executing async functions. There's more nuance than this. You can keep polling futures as often as you want. When an async fn gets converted into the state machine, yielding is just expressed as the poll fn returning as not ready. So it is actually possible for "a little bit" of work to happen, although that's limited and gets tricky because the way wakers work ensure that normally futures only get polled by the runtime when there's actually work for them to do.
- oconnor663 11mo ago
  Rust futures are "just" structs with a poll() method. The poll() method is a function like any other, so it can have local variables on the stack as usual, but anything it wants to save between calls needs to be a field of the struct instead of a stack local. The magic of async/await is that the compiler figures out which of your async function's variables need to be fields on that struct, and it generated the struct and the poll method for you. I have a blog series that goes into the concrete details if you like: https://jacko.io/async_intro.html https://jacko.io/async_intro.html
  - Veserv 11mo ago
    I see. The Rust implementation effectively splats out the transitive closure of all your callee stack frames upfront which would enable continuing previously executing async functions.
DevelopingElk 11mo ago
My view of this is that its closer to the basic 2 lock Deadlock. Thread 1 acquires A. Thread 2 acquires B. Thread 1 tries to acquire B. Thread 2 tries to acquire A. In this case, the role "A" is being played by the front of the Mutex's lock queue. Role "B" is being played by the Tokio's actively executed task. Based on this understanding, I agree that the surprising behavior is due to Tokio's Mutex/Lock Queue implementation. If this was an OS Mutex, and a thread waiting for the Mutex can't wake for some reason, the OS can wake a different thread waiting for that Mutex. I think the difficulty in this approach has to do with how Rust's async is implemented. My guess is the algorithm for releasing a lock goes something like this: 1. Pop the head of the wait queue. 2. Poll the top level tokio::spawn'ed task of the Future that is holding the Mutex. What you want is something like this For each Future in the wait queue (Front to Back): Poll the Future. If Success - Break ???Something if everything fails??? The reason this doesn't work has to do with how futures compose. Futures compile to states within a state machine. What happens when a future polled within the wait queue completes? How is control flow handed back to the caller? I guess you might be able to have some fallback that polls the futures independently then polls the top level future to try and get things unstuck. But this could cause confusing behavior where futures are being polled even though no code path within your code is await'ing them. Maybe this is better though?
johnisgood 11mo ago
Off-topic but that code looks quite... complicated as opposed to what I would write in Erlang, Elixir, Go, or even C. Maybe it is just me.
- jerf 11mo ago
  Erlang/Elixir and Go "solve" this problem by basically not giving you the rope to hang yourself in this particular way in the first place. This is a perfectly valid and sensible solution... but it is not the only solution. It means you're paying for some relatively expensive full locks that the Rust async task management is trying to elide, for what can be quite significant performance gains if you're doing a lot of small tasks. It is good that not every language gives you this much control and gives some easier options for when those are adequate, but it is also good that there is some set of decent languages that do give you this degree of control for when it is necessary, and it is good that we are not surrendering that space to just C and/or C++. Unfortunately such control comes with footguns, at least over certain spans of time. Perhaps someone will figure out a way to solve this problem in Rust in the future.
  - johnisgood 11mo ago
    > It means you're paying for some relatively expensive full locks that the Rust async task management is trying to elide, for what can be quite significant performance gains if you're doing a lot of small tasks. The point of Erlang/Elixir is that it is as performant as possible, and Erlang's history is a testament to this. BEAM is wonderful, and really fast, along with the languages on it being ergonomic (OTP behaviors, supervisors, etc.).
    - jerf 11mo ago
      This is a myth, from the old days when BEAM was the only thing that could juggle thousands of "processes" without losing performance, and even back then, people routinely missed that while BEAM could juggle those thousands of processes, each of them was individually not that fast. That is, BEAM's extremely high performance was only in one isolated thing, not high performance across the board. Now BEAM is far from the only runtime juggling that many processes, but it remains a relatively slow VM. I rule-of-thumb it at 10x slower than C, making it a medium performance VM at best, and you want to watch your abstraction layers in those nicer languages like Gleam because further multiplicative slow downs can really start to bite. The first serious Go program I wrote was a replacement for something written in Erlang, there was no significant architectural improvement in the rewrite (it was already reasonably well-architected), and from the first deployment, we went from 4 systems, sometimes struggling with the load spikes, to where just one could handle it all, even with BEAM being over a decade more mature and the Go clustering code being something I wrote over a few weeks rather than battle tested, optimized code. BEAM is good at managing concurrency, but it is slowish in other ways. It's better than the dynamic scripting languages like Python by a good amount but it is not performance-competitive with a modern compiled language.
dboreham 11mo ago
Which is why "async" is a pox on our house. System threads can and do address these edge issues. User level concurrency generally doesn't (perhaps with the exceptions of golang and erlang).

by singron 11mo ago

oconnor663 11mo ago

> I wonder if there is a similar idea possible with tokio? E.g. if you are awaiting a Mutex held by a future that "can't run", then poll that future instead. Something like this could make sense for Tokio tasks. (I don't know how complicated their task scheduler is; maybe it already does stuff like this?) But it's not possible for futures within a task, as in this post. This goes all the way back to the "futures are inert" design of async Rust: You don't necessarily need to communicate with the runtime at all to create a future or to poll it or to stop polling it. You only need to talk to the runtime at the task level, either to spawn new tasks, or to wake up your own task. Futures are pretty much just plain old structs, and Tokio doesn't know how many futures my async function creates internally, any more than it knows about my integers or strings or hash maps.

mycoliza 11mo ago
Yeah, a coworker coming from Go asked a similar question about why Rust doesn't have something like the Go runtime's deadlock detector. Your comment is quite similar to the explanation I gave him. Go, unlike Rust, does not really have a notion of intra-task concurrency; goroutines are the fundamental unit of concurrency and parallelism. So, the Go runtime can reason about dependencies between goroutines quite easily, since goroutines are the things which it is responsible for scheduling. The fact that channels are a language construct, rather than a library construct implemented in the language, is necessary for this too. In (async) Rust, on the other hand, tasks are the fundamental unit of parallelism, but not of concurrency; concurrency emerges from the composition of `Future`s, and a single task is a state machine which may execute any number of futures concurrently (but not in parallel), by polling them until they cannot proceed without waiting and then moving on to poll another future until it cannot proceed without waiting. But critically, this is not what the task scheduler sees; it interacts with these tasks as a single top-level `Future`, and is not able to look inside at the nested futures they are composed of. This specific failure mode can actually only happen when multiple futures are polled concurrently but not in parallel within a single Tokio task. So, there is actually no way for the Tokio scheduler to have insight into this problem. You could imagine a deadlock detector in the Tokio runtime that operates on the task level, but it actually could never detect this problem, because when these operations execute in parallel, it actually cannot occur. In fact, one of the suggestions for how to avoid this issue is to select over spawned tasks rather than futures within the same task.
- mjevans 11mo ago
  Thank you. Every time I've tried to approach the concept of Rust's parallelism this is what rubs me the wrong way. I haven't yet read a way to prove it's correct, or even to reasonably prove a given program's use is not going to block. With more traditional threads my mental model is that _everything_ always has to be interrupt-able, have some form of engineer chosen timeout for a parallel operation, and address failure of operation in design. I never see any of that in the toy examples that are presented as educational material. Maybe Rust's async also requires such careful design to be safely utilized.
  - 11mo ago
newpavlov 11mo ago
>This goes all the way back to the "futures are inert" design of async Rust Yeap. And this footgun is yet another addition to the long list of reasons why I consider the Rust async model with its "inert" futures managed in user space a fundamentally flawed un-Rusty design.
- filleduchaos 11mo ago
  I feel there's a difference between a preference and a flaw. Rust has targets that make anything except inert futures simply unworkable, and in my opinion it's entirely valid for a programming language to prioritise those targets.
  - Rusky 11mo ago
    The requirement is that the futures are not separate heap allocations, not that they are inert. It's not at all obvious that Rust's is the only possible design that would work here. I strongly suspect it is not. In fact, early Rust did some experimentation with exactly the sort of stack layout tricks you would need to approach this differently. For example, see Graydon's post here about the original implementation of iterators, as lightweight coroutines: https://old.reddit.com/r/ProgrammingLanguages/comments/141qm6g/the_rust_i_wanted_had_no_future_graydon_hoare/jyldotb/?context=8 https://old.reddit.com/r/ProgrammingLanguages/comments/141qm...
    - filleduchaos 11mo ago
      On the other hand, early Rust also for instance had a tracing garbage collector; it's far from obvious to me how relevant its discarded design decisions are supposed to be to the language it is today.
      - Rusky 11mo ago
        This one is relevant because it avoids heap allocation while running the iterator and for loop body concurrently. Which is exactly the kind of thing that `async` does.

Veserv 11mo ago

I thought Rust async is a colored stackless coroutine model and thus it would be unsafe to continue execution of previously executing async functions. To explain, generally speaking, stackless coroutine async only need coloring because they are actually “independent stack”less coroutines. What they actually do is that they share the stack for their local state. This forces async function execution to proceed in LIFO order so you do not blow away the stack of the async function executing immediately after which demands state machine transforms to be safe. This is why you need coloring unlike stackful coroutine models which can execute, yield, and complete in arbitrary order since their local state is preserved in a safe location.

treyd 11mo ago
> thus it would be unsafe to continue execution of previously executing async functions. There's more nuance than this. You can keep polling futures as often as you want. When an async fn gets converted into the state machine, yielding is just expressed as the poll fn returning as not ready. So it is actually possible for "a little bit" of work to happen, although that's limited and gets tricky because the way wakers work ensure that normally futures only get polled by the runtime when there's actually work for them to do.
oconnor663 11mo ago
Rust futures are "just" structs with a poll() method. The poll() method is a function like any other, so it can have local variables on the stack as usual, but anything it wants to save between calls needs to be a field of the struct instead of a stack local. The magic of async/await is that the compiler figures out which of your async function's variables need to be fields on that struct, and it generated the struct and the poll method for you. I have a blog series that goes into the concrete details if you like: https://jacko.io/async_intro.html https://jacko.io/async_intro.html
- Veserv 11mo ago
  I see. The Rust implementation effectively splats out the transitive closure of all your callee stack frames upfront which would enable continuing previously executing async functions.

DevelopingElk 11mo ago

My view of this is that its closer to the basic 2 lock Deadlock. Thread 1 acquires A. Thread 2 acquires B. Thread 1 tries to acquire B. Thread 2 tries to acquire A. In this case, the role "A" is being played by the front of the Mutex's lock queue. Role "B" is being played by the Tokio's actively executed task. Based on this understanding, I agree that the surprising behavior is due to Tokio's Mutex/Lock Queue implementation. If this was an OS Mutex, and a thread waiting for the Mutex can't wake for some reason, the OS can wake a different thread waiting for that Mutex. I think the difficulty in this approach has to do with how Rust's async is implemented. My guess is the algorithm for releasing a lock goes something like this: 1. Pop the head of the wait queue. 2. Poll the top level tokio::spawn'ed task of the Future that is holding the Mutex. What you want is something like this For each Future in the wait queue (Front to Back): Poll the Future. If Success - Break ???Something if everything fails??? The reason this doesn't work has to do with how futures compose. Futures compile to states within a state machine. What happens when a future polled within the wait queue completes? How is control flow handed back to the caller? I guess you might be able to have some fallback that polls the futures independently then polls the top level future to try and get things unstuck. But this could cause confusing behavior where futures are being polled even though no code path within your code is await'ing them. Maybe this is better though?

johnisgood 11mo ago

Off-topic but that code looks quite... complicated as opposed to what I would write in Erlang, Elixir, Go, or even C. Maybe it is just me.

jerf 11mo ago
Erlang/Elixir and Go "solve" this problem by basically not giving you the rope to hang yourself in this particular way in the first place. This is a perfectly valid and sensible solution... but it is not the only solution. It means you're paying for some relatively expensive full locks that the Rust async task management is trying to elide, for what can be quite significant performance gains if you're doing a lot of small tasks. It is good that not every language gives you this much control and gives some easier options for when those are adequate, but it is also good that there is some set of decent languages that do give you this degree of control for when it is necessary, and it is good that we are not surrendering that space to just C and/or C++. Unfortunately such control comes with footguns, at least over certain spans of time. Perhaps someone will figure out a way to solve this problem in Rust in the future.
- johnisgood 11mo ago
  > It means you're paying for some relatively expensive full locks that the Rust async task management is trying to elide, for what can be quite significant performance gains if you're doing a lot of small tasks. The point of Erlang/Elixir is that it is as performant as possible, and Erlang's history is a testament to this. BEAM is wonderful, and really fast, along with the languages on it being ergonomic (OTP behaviors, supervisors, etc.).
  - jerf 11mo ago
    This is a myth, from the old days when BEAM was the only thing that could juggle thousands of "processes" without losing performance, and even back then, people routinely missed that while BEAM could juggle those thousands of processes, each of them was individually not that fast. That is, BEAM's extremely high performance was only in one isolated thing, not high performance across the board. Now BEAM is far from the only runtime juggling that many processes, but it remains a relatively slow VM. I rule-of-thumb it at 10x slower than C, making it a medium performance VM at best, and you want to watch your abstraction layers in those nicer languages like Gleam because further multiplicative slow downs can really start to bite. The first serious Go program I wrote was a replacement for something written in Erlang, there was no significant architectural improvement in the rewrite (it was already reasonably well-architected), and from the first deployment, we went from 4 systems, sometimes struggling with the load spikes, to where just one could handle it all, even with BEAM being over a decade more mature and the Go clustering code being something I wrote over a few weeks rather than battle tested, optimized code. BEAM is good at managing concurrency, but it is slowish in other ways. It's better than the dynamic scripting languages like Python by a good amount but it is not performance-competitive with a modern compiled language.

dboreham 11mo ago

Which is why "async" is a pox on our house. System threads can and do address these edge issues. User level concurrency generally doesn't (perhaps with the exceptions of golang and erlang).