10 ms·

Futurelock: A subtle risk in async Rust

449 points by bcantrill 11mo ago

This RFD describes our distillation of a really gnarly issue that we hit in the Oxide control plane.[0] Not unlike our discovery of the async cancellation issue[1][2][3], this is larger than the issue itself -- and worse, the program that hits futurelock is correct from the programmer's point of view. Fortunately, the surface area here is smaller than that of async cancellation and the conditions required to hit it can be relatively easily mitigated. Still, this is a pretty deep issue -- and something that took some very seasoned Rust hands quite a while to find. [0] https://github.com/oxidecomputer/omicron/issues/9259 https://github.com/oxidecomputer/omicron/issues/9259 [1] https://rfd.shared.oxide.computer/rfd/397 https://rfd.shared.oxide.computer/rfd/397 [2] https://rfd.shared.oxide.computer/rfd/400 https://rfd.shared.oxide.computer/rfd/400 [3] https://www.youtube.com/watch?v=zrv5Cy1R7r4 https://www.youtube.com/watch?v=zrv5Cy1R7r4

deleted 11mo ago
[deleted]
Sytten 11mo ago
I am wondering if there is a larger RFC for Rust to force users to not hold a variable across await points. In my mind futurelock is similar to keeping a sync lock across an await point. We have nothing right now to force a drop and I think the solution to that problem would help here.
- cogman10 11mo ago
  The ideas that have been batted around is called "async drop" [1] And it looks like it's still just an unaddressed well known problem [2]. Honestly, once the Mozilla sackening of rust devs happened it seems like the language has been practically rudderless. The RFC system seems almost dead as a lot of the main contributors are no longer working on rust. This initiative hasn't had motion since 2021. [3] [1] https://rust-lang.github.io/async-fundamentals-initiative/roadmap/async_drop.html https://rust-lang.github.io/async-fundamentals-initiative/ro... [2] https://rust-lang.github.io/async-fundamentals-initiative/ https://rust-lang.github.io/async-fundamentals-initiative/ [3] https://github.com/rust-lang/async-fundamentals-initiative https://github.com/rust-lang/async-fundamentals-initiative
  - raggi 11mo ago
    Those pages are out of date, and AsyncDrop is in progress: https://github.com/rust-lang/rust/issues/126482 https://github.com/rust-lang/rust/issues/126482 I think "practically rudderless" here is fairly misinformed and a little harmful/rude to all the folks doing tons of great work still. It's a shame there are some stale pages around and so on, but they're not good measures of the state of the project or ecosystem. The problem of holding objects across async points is also partially implemented in this unstable lint marker which is used by some projects: https://dev-doc.rust-lang.org/unstable-book/language-features/must-not-suspend.html https://dev-doc.rust-lang.org/unstable-book/language-feature... You also get a similar effect in multi-threaded runtimes by not arbitrarily making everything in your object model Send and instead designing your architecture so that most things between wake-ups don't become arbitrarily movable references. These aren't perfect mitigations, but some tools.
    - bigstrat2003 11mo ago
      In fairness, if you're a layman to the rust development process (as I am, so I'm speaking from personal experience here) it's damn near impossible to figure out the status of things. There tracking issues, RFCs, etc which is very confusing as an outsider and gives no obvious place to look to find out the current status of a proposal. I'm sure there is a logic to it and that if I spent the time to learn it would make sense. But it is really hard to approach for someone like me.
      - kibwen 11mo ago
        If you want to find out the status of something, the best bet is to go to the Rust Zulip and ask around: https://rust-lang.zulipchat.com/ https://rust-lang.zulipchat.com/ . Most Rust initiatives are pushed forward by volunteers who are happy to talk about what they're working on, but who only periodically write status reports on tracking issues (usually in response to someone asking them what the status is). Rust isn't a company where documentation is anyone's job, it's just a bunch of people working on stuff, for better or worse.
        11mo ago
- sunshowers 11mo ago
  Note that forcing a drop of a lock guard has its own issues, particularly around leaving the guarded data in an invalid state. I cover this a bit in my talk that Bryan linked to in the OP [1]. [1] timestamped: https://youtu.be/zrv5Cy1R7r4?t=1067 https://youtu.be/zrv5Cy1R7r4?t=1067
- ameliaquining 11mo ago
  There's an existing lint that lets you prohibit instances of specific types from being held across await points: https://rust-lang.github.io/rust-clippy/stable/index.html#await_holding_invalid_type https://rust-lang.github.io/rust-clippy/stable/index.html#aw...
- amluto 11mo ago
  I’m not convinced that this can help in a meaningful way. Fundamentally, if you have two coroutines (or cooperatively scheduled threads or whatever), and one of them holds a lock, and the other one is awaiting the lock, and you don’t schedule the first one, you’re stuck. I wonder if there’s a form of structured concurrency that would help. If I create two futures and start both of them (in Rust this means polling each one once) but do not continue to poll both, then I’m sort of making a mistake. So imagine a world where, to poll a future at all, I need to have a nursery, and the nursery is passed in from my task and down the call stack. When I create a future, I can pass in my nursery, but that future then gets an exclusive reference to my future until it’s complete or cancelled. If I want to create more than one future that are live concurrently, I need to create a FutureGroup (that gets an exclusive reference to my nursery) and that allows me to create multiple sub-nurseries that can be used to make futures but cannot be used to poll them — instead I poll the FutureGroup. (I have yet to try using an async/await system or a reactor or anything of the sort that is not very easy to screw up. My current pet peeve is this pattern: data = await thingy.read() What if thingy.read() succeeds but I am cancelled? This gets nasty is most programming languages. Python: the docs on when I can get cancelled are almost nonexistent, and it’s not obviously possible to catch the CancelledError such that I still have data and can therefore save it somewhere so it’s not lost. Rust: what if thingy thinks it has returned the data but I’m never polled again? Maybe this can’t happen if I’m careful, but that requires more thought than I’m really happy with.)
- mechanical_berk 11mo ago
  I agree. It seems like this bug arises because one Future is awaited while another is ignored. I have seen this sort of bug a lot. So maybe all that is needed is a lint that warns if you keep a Future (or a reference to one) across an await point? The Future you are awaiting wouldn't count of course. Is there some case where this doesn't work?
orthecreedence 11mo ago
Great read, and the example code makes sense. This stuff can be a nightmare to find, but once you do it's like a giant 1000 piece puzzle just clicks together instantly.
- bcantrill 11mo ago
  Indeed. One of the interesting side effects of being a remote company that records everything[0] is that we have the instant where the "1000 piece puzzle just clicks together" recorded, and it's honestly pretty wild. In this case, it was very much a shared brainstorming between four engineers (Eliza, Sean, John and Dave) -- and there is almost a passing of the baton where they start to imagine the kind of scenario that could induce this and then realize that those are exactly the conditions that exist in the software. We are (on brand?) going to do a podcast episode on this on Monday[1]; ahead of that conversation I'm going to get a clip of that video out, just because it's interesting to see the team work together to debug it. [0] https://rfd.shared.oxide.computer/rfd/0537 https://rfd.shared.oxide.computer/rfd/0537 [1] https://discord.gg/QrcKGTTPrF?event=1433923627988029462 https://discord.gg/QrcKGTTPrF?event=1433923627988029462
  - mycoliza 11mo ago
    As a member of (Eliza, Sean, John, and Dave), I can second that debugging this was certainly an adventure. I'm not going to go as far as to say that we had fun, since...you can't have a heroic narrative without real struggle. But it was certainly rewarding to be in the room for that "a-ha!" moment, in which all the pieces really did begin to fit together very quickly. It was like the climax of a detective story --- and it was particularly well-scripted the way each of us contributed a little piece of the puzzle.
    - littlestymaar 11mo ago
      Since you are of of the people working directly on this codebase, may I ask you why is select! being used/allowed in the first place? Its footgun-y nature has been known for years (IIRC even the first version of the tokio documentation warned against that) and as such I don't really understand why people are still using it. (For context I was the lead of a Rust team working on a pretty complex async networking program and we had banned select! very early in the project and never regretted this decision once).
oconnor663 11mo ago
> FAQ: doesn’t future1 get cancelled? I guess cancellation is really two different things, which usually happen at the ~same time, but not in this case: 1) the future stops getting polled, and 2) the future gets dropped. In this example the drop is delayed, and because the future is holding a guard,* the delay has side effects. So the future "has been cancelled" in the sense that it will never again make forward progress, but it "hasn't been cancelled yet" in the sense that it's still holding resources. I wonder if it's practical to say "make sure those two things always happen together"? * Technically a Tokio-internal `Acquire` future that owns a queue position to get a guard, but it sounds like the exact same bug could manifest after it got the guard too, so let's call it a guard.
jacquesm 11mo ago
If any rust designers are lurking about here: what made you decide to go for the async design pattern instead of the actor pattern, which - to me at least - seems so much cleaner and so much harder to get wrong? Ever since I started using Erlang it felt like I finally found 'the right way' when before then I did a lot of work with sockets and asynchronous worker threads. But even though it usually worked as advertised it had a large number of really nasty pitfalls which the actor model seemed to - effortlessy - step aside. So I'm seriously wondering what the motivation was. I get why JS uses async, there isn't any other way there, by the time they added async it was too late to change the fundamentals of the language to such a degree. But rust was a clean slate.
- sunshowers 11mo ago
  Not a Rust designer, but a big motivation for Rust's async design was wanting it to work on embedded, meaning no malloc and no threads. This unfortunately precludes the vast majority of the design space here, from active futures as seen in JS/C#/Go to the actor model. You can write code using the actor model with Tokio. But it's not natural to do so.
  - lll-o-lll 11mo ago
    As a curious bystander, it will be interesting to see how the Zig async implementation pans out. They have the advantage of getting to see the pitfalls of those that have come before. Getting back to Rust, even if not natural, I agree with the parent that the actor model is simply the better paradigm. Zero runtime allocation should still be possible, you just have to accept some constraints. I think async looks simple because it looks like writing imperative code; unfortunately it is just obfuscating the complex reality underlying. The actor model makes things easier to reason about, even if it looks more complicated initially.
    - sunshowers 11mo ago
      I think you can do a static list of actors or tasks in embedded, but it's hard to dynamically spin up new ones. That's where intra-task concurrency is helpful.
moralestapia 11mo ago
Hmm, curious to see if this could happen on JS. I'll reproduce the code.
- raggi 11mo ago
  yes, you can produce similar issues with promise guarded states and so on as well, it's a fairly common issue in async programming, but can be surprising when it's hidden by layers of abstraction / far up/down a call-chain.
- comex 11mo ago
  JS shouldn't have a direct equivalent because JS async functions are eager. Once you call an async function, it will keep running even if the caller doesn't await it, or stops awaiting it. So in the scenario described, the function next in line for the lock would always have a chance to acquire and release it. The problem in Rust is that async functions are lazy and only run while they're being polled/awaited (unless wrapped in tasks). A function that's next in line for the lock might never acquire it if it's not being polled, blocking progress for other functions that are being polled.
dvt 11mo ago
> &mut future1 is dropped, but this is just a reference and so has no effect. Importantly, the future itself (future1) is not dropped. There's a lot of talk about Rust's await implementation, but I don't really think that's the issue here. After all, Rust doesn't guarantee convergence. Tokio, on the other hand (being a library that handles multi-threading), should (at least when using its own constructs, e.g. the `select!` macro). So, since the crux of the problem is the `tokio::select!` macro, it seems like a pretty clear tokio bug. Side note, I never looked at it before, but the macro[1] is absolutely hideous. [1] https://docs.rs/tokio/1.34.0/src/tokio/macros/select.rs.html https://docs.rs/tokio/1.34.0/src/tokio/macros/select.rs.html
- raggi 11mo ago
  i forget if this part unwinds to the exact same place, but some of this kind of design constraint in tokio stems from the much earlier language capabilities and is prohibitive to adjust without breaking the user ecosystem. one of the key advertised selling points in some of the other runtimes was specifically around behavior of tasks on drop of their join handles for example, for reasons closely related to this post.
- oconnor663 11mo ago
  There's nothing `select!` could do here to force `future1` to drop, because it doesn't receive ownership of `future1`. If we wanted to force this, we'd have to forbid `select!` from polling futures by reference, but that's a pretty fundamental capability that we often rely on to `select!` in a loop for example. The blanket `impl<F> Future for &mut F where F: Future ...` isn't a Tokio thing either; that's in the standard library.
  - kibwen 11mo ago
    Surely not every use of `select!` needs this ability. If you can design a more restrictive interface that makes correctness easier to determine, then you should use that interface where you can, and reserve `select!` for only those cases where you can't.
- mycoliza 11mo ago
OptionOfT 11mo ago
- wrong -
- DAlperin 11mo ago
  I think the next sentence clarifies pretty well. > In this case, what’s dropped is &mut future1. But future1 is not dropped, so the actual future is not cancelled.
- oconnor663 11mo ago
  The author clearly understands these details. I think it's just a question of wording: did we "drop a reference (which has no effect)" or did we "not drop anything (because references don't implement Drop)"?
- deleted 11mo ago
  [deleted]
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.
arjie 11mo ago
Wow, that makes sense afterwards but I would not have guessed at it immediately looking at the code. Very insidious. Great blogpost.
keyliejener 11mo ago
[dead]
wbl 11mo ago
Sadly I'm away from my bookshelf but I think Concurrent ML solved this issue.
forrestthewoods 11mo ago
I feel like I’m pretty good at writing multithreaded code. I’ve done it a lot. As long as you use primitives like Rust Mutex that enforce correctness for data access (ie no accessing data without the lock) it’s pretty simple. Define a clean boundary API and you’re off to the races. async code is so so so much more complex. It’s so hard to read and rationalize. I could not follow this post. I tried. But it’s just a full extra order of complexity. Which is a shame because async code is supposed to make code simpler! But I’m increasingly unconfident that’s true.
- amelius 11mo ago
  Async code is simpler because you're implicitly holding a lock on the CPU. That's also why you should stay away from it: it increases latency. Especially since Rust is about speed and responsiveness. In general, async programming in Rust makes little sense.
  - forrestthewoods 11mo ago
    I love Rust. But I’m 100% convinced Rust chose the wrong tradeoffs with their async model. Just give me green threads and use malloc to grow the stack. It’s fine. That would have been better imho.
    - mjevans 11mo ago
      Hell, even force threads to be allocated from a bucket of N threads defined at compile time. Surely that'd work for embedded / GPU space?
    - gf000 11mo ago
      You can't have a low-level language and green threads at the same time.
      - forrestthewoods 11mo ago
        Why not?
octoberfranklin 11mo ago
It’s really important to understand what’s happening here Then maybe you should take a moment to pick more descriptive identifiers than future1, future2, future3, do_stuff, and do_async_thing. This coding style is atrocious.
- dap 11mo ago
  Is it possible that those names are intentionally chosen and actually do carry meaning?
- gpm 11mo ago
  If you prefer "real" names you can always look at the actual code that had a bug - here it is before the bug was fixed: https://github.com/oxidecomputer/omicron/blob/a253f541a4a32a4326d7ddfc04df27c0e47de42b/nexus/src/app/background/tasks/support_bundle_collector.rs#L496-L551 https://github.com/oxidecomputer/omicron/blob/a253f541a4a32a...
Matthias247 11mo ago
As far as I remember from building these things with others within the async rust ecosystem (hey Eliza!) was that there was a certain tradeoff: if you wouldn’t be able to select on references, you couldn’t run into this issue. However you also wouldn’t be able run use select! in a while loop and try to acquire the same lock (or read from the same channel) without losing your position in the queue. I fully agree that this and the cancellation issues discussed before can lead to surprising issues even to seasoned Rust experts. But I’m not sure what really can be improved under the main operating model of async rust (every future can be dropped). But compared to working with callbacks the amount of surprising things is still rather low :)
- octoberfranklin 11mo ago
  > However you also wouldn’t be able run use select! in a while loop and try to acquire the same lock (or read from the same channel) without losing your position in the queue. No, just have select!() on a bunch of owned Futures return the futures that weren't selected instead of dropping them. Then you don't lose state. Yes, this is awkward, but it's the only logically coherent way. There is probably some macro voodoo that makes it ergonomic. But even this doesn't fix the root cause because dropping an owned Future isn't guaranteed to cancel it cleanly. For the real root cause: https://news.ycombinator.com/item?id=45777234 https://news.ycombinator.com/item?id=45777234
  - mycoliza 11mo ago
    > No, just have select!() on a bunch of owned Futures return the futures that weren't selected instead of dropping them. Then you don't lose state. How does that prevent this kind of deadlock? If the owned future has acquired a mutex, and you return that future from the select so that it might be polled again, and the user assigns it to a variable, then the future that has acquired the mutex but has not completed is still not dropped. This is basically the same as polling an `&mut future`, but with more steps.
    - octoberfranklin 11mo ago
octoberfranklin 11mo ago
For anybody who wants to cut to the chase, it's this: > The behavior of tokio::select! is to poll all branches' futures only until one of them returns `Ready`. At that point, it drops the other branches' futures and only runs the body of the branch that’s ready. This is, unfortunately, doing what it's supposed to do: acting as a footgun. The design of tokio::select!() implicitly assumes it can cancel tasks cleanly by simply dropping them. We learned the hard way back in the Java days that you cannot kill threads cleanly all the time. Unsurprisingly, the same thing is true for async tasks. But I guess every generation of programmers has to re-learn this lesson. Because, you know, actually learning from history would be too easy. Unfortunately there are a bunch of footguns in tokio (and async-std too). The state-machine transformation inside rustc is a thing of beauty, but the libraries and APIs layered on top of that should have been iterated many more times before being rolled out into widespread use.
- littlestymaar 11mo ago
  I genuinely don't understand why people use select! at all given how much of a footgun it is.
  - octoberfranklin 11mo ago
    Well the less-footgun-ish alternative would look something like a Stream API, but the last time I checked tokio-stream wasn't stable yet. Then you could merge a `Stream<A>` and `Stream<B>` into a `Stream<Either<A,B>>` and pull from that. Since you're dealing with owned streams, dropping the stream forces some degree of cleanup. There are still ways to make a mess, but they take more effort. .................................... Ratelimit so I have to reply to mycoliza with an edit here: That example calls `do_thing()`, whose body does not appear anywhere in the webpage. Use better identifiers. If you meant `do_stuff()`, you haven't replaced select!() with streams, since `do_stuff()` calls `select!()`. The problem is `select!()`; if you keep using `select!()` but just slather on a bunch of streams that isn't going to fix anything. You have to get rid of select!() by replacing it with streams.
    - 11mo ago
hitekker 11mo ago
Skimming through, this document feels thorough and transparent. Clearly, a hard lesson learned. The footnotes, in particular, caught my eye https://rfd.shared.oxide.computer/rfd/397#_external_references https://rfd.shared.oxide.computer/rfd/397#_external_referenc... > Why does this situation suck? It’s clear that many of us haven’t been aware of cancellation safety and it seems likely there are many cancellation issues all over Omicron. It’s awfully stressful to find out while we’re working so hard to ship a product ASAP that we have some unknown number of arbitrarily bad bugs that we cannot easily even find. It’s also frustrating that this feels just like the memory safety issues in C that we adopted Rust to get away from: there’s some dynamic property that the programmer is responsible for guaranteeing, the compiler is unable to provide any help with it, the failure mode for getting it wrong is often undebuggable (by construction, the program has not done something it should have, so it’s not like there’s a log message or residual state you could see in a debugger or console), and the failure mode for getting it wrong can be arbitrarily damaging (crashes, hangs, data corruption, you name it). Add on that this behavior is apparently mostly undocumented outside of one macro in one (popular) crate in the async/await ecosystem and yeah, this is frustrating. This feels antithetical to what many of us understood to be a core principle of Rust, that we avoid such insidious runtime behavior by forcing the programmer to demonstrate at compile-time that the code is well-formed
- rtpg 11mo ago
  I guess one big question here is whether there's a higher layer abstraction that is available to wrap around patterns to avoid this. It does feel like there's still generally possibilities of deadlocks in Rust concurrency right? I understand the feeling here that it feels like ... uhh... RAII-style _something_ should be preventing this, because it feels like statically we should be able to identify this issue in this simple case. I still have a hard time understanding how much of this is incidental and how much of this is just downstream of the Rust/Tokio model not having enough to work on here.
  - embedding-shape 11mo ago
    > I guess one big question here is whether there's a higher layer abstraction that is available to wrap around patterns to avoid this. Something like Actors, on top of Tokio, would be one way: https://ryhl.io/blog/actors-with-tokio/ https://ryhl.io/blog/actors-with-tokio/
Dagonfly 11mo ago
That's a really subtle version of the deadlock described in withoutboats FuturesUnordered post [0] When using “intra-task” concurrency, you really have to ensure that none of the futures are starving. Spawning task should probably be the default. For timeouts use tokio::select! but make sure all pending futures are owned by it. I would never recommend FuturesUnordered unless you really test all edge-cases. [0] https://without.boats/blog/futures-unordered/ https://without.boats/blog/futures-unordered/
quietbritishjim 11mo ago
Wow, it is simply outrageous that Rust doesn't just allow all active tasks to make progress. It creates a whole class of incomprehensible bugs, like this one, for no reason. Can any Rust experts explain why it's done this way? It seems like an unforced error. In Python, I often use the Trio library, which offers "structured, concurrency": tasks are (only) spawned into lexical scopes, and they are all completed (waited for) before that scope is left. That includes waiting for any cancelled tasks (which are allowed to do useful async work, including waiting for any of their own task scopes to complete). Could Rust do something like that? It's far easier to reason about than traditional async programs, which seems up Rust's street. As a bonus it seems to solve this problem, since a Rust equivalent would presumably have all tasks implicitly polled by their owning scope.
- duped 11mo ago
  So there's a distinction between a task and a future. A future doesn't do anything until it's polled, and since there's nothing special about async runtimes (it's just user level code), it's always possible to create futures and never poll them, or stop polling them. A task is a different construct and usually tied to the runtime. If you look at the suggestions in the RFD they call out using a task explicitly instead of polling a future in place. There's some debate to be had over what constitutes "cancellation." The article and most colloquial definitions I've heard define it as a future being dropped before being polled to completion. Which is very clean - if you want to cancel a future, just drop it. Since Rust strongly encourages RAII, cleanup can go in drop implementations. A much tougher definition of cancellation is "the future is never polled again" which is what the article hits on. The future isn't dropped but its poll is also unreachable, hence the deadlock.
  - wrs 11mo ago
    I wish "cancellation" wasn't used for both of those. It seems to obfuscate understanding quite a bit. We should call them "dropped" and "abandoned" or something.
    - duped 11mo ago
levodelellis 11mo ago
In October alone I seen 5+ articles and comments about multi-threading and I don't know why I always said if your code locks or use atomics, it's wrong. Everyone says I'm wrong but you get things like what's described in the article. I'd like to recommend a solution but there's pretty much no reasonable way to implement multi-threading when you're not an expert. I heard Erlang and Elixir are good but I haven't tried them so I can't really comment
- umvi 11mo ago
  > I always said if your code locks or use atomics, it's wrong. Everyone says I'm wrong but you get things like what's described in the article. Ok so say you are simulating high energy photons (x-rays) flowing through a 3d patient volume. You need to simulate 2 billion particles propagating through the patient in order to get an accurate estimation of how the radiation is distributed. How do you accomplish this without locks or atomics without the simulation taking 100 hours to run? Obviously it would take forever to simulate 1 particle at a time, but without locks or atomics the particles will step on each others' toes when updating radiation distribution in the patient. I suppose you could have 2 billion copies of the patient's volume in memory and each particle gets its own private copy and then you merge them all at the end...
  - levodelellis 11mo ago
    From my understanding this talk describes how he implemented a solution for a similar problem https://www.youtube.com/watch?v=Kvsvd67XUKw https://www.youtube.com/watch?v=Kvsvd67XUKw I'm saying if you're not writing multi-threaded code everyday, use a library. It can use atomics/locks but you shouldn't use it directly. If the library is designed well it'd be impossible to deadlock.
    - jstimpfle 11mo ago
      If you take programming serious, learn it. With a library that encapsulates a low number of patterns (like message passing) you'll be very limited. If you never start learning about lower level multi-threading issues you'll never learn it. And it's not _that_ hard. I'm not writing multi threaded every day (by far), but often enough that I can write useful things (using shared memory, atomics, mutexes, condition variables, etc). And I'm looking forward to learn more, better understand various issues, learn new patterns.
mdasen 11mo ago
I rewrote this in Go and it also deadlocks. It doesn't seem to be something that's Rust specific. I'm going to write down the order of events. 1. Background task takes the lock and holds it for 5 seconds. 2. Async Thing 1 tries to take the lock, but must wait for background task to release it. It is next in line to get the lock. 3. We fire off a goroutine that's just sleeping for a second. 4. Select wants to find a channel that is finished. The sleepChan finishes first (since it's sleeping for 1 second) while Async Thing 1 is still waiting 4 more seconds for the lock. So select will execute the sleepChan case. 5. That case fires off Async Thing 2. Async Thing 2 is waiting for the lock, but it is second in line to get the lock after Async Thing 1. 6. Async Thing 1 gets the lock and is ready to write to its channel - but the main is paused trying to read from c2, not c1. Main is "awaiting" on c2 via "<-c2". Async Thing 1 can't give up its lock until it writes to c1. It can't write to c1 until c1 is "awaited" via "<-c1". But the program has already gone into the other case and until the sleepChan case finishes, it won't try to await c1. But it will never finish its case because its case depends on c1 finishing first. You can use buffered channels in Go so that Async Thing 1 can write to c1 without main reading from it, but as the article notes you could use join_all in Rust. But the issue is that you're saying with "select" in either Go or Rust "get me the first one that finishes" and then in the branch that finishes first, you are awaiting a lock that will get resolved when you read the other branch. It just doesn't feel like something that is Rust specific. func main() { lock := sync.Mutex{} c1 := make(chan string) c2 := make(chan string) sleepChan := make(chan bool) go start_background_task(&lock) time.Sleep(1 * time.Millisecond) //make sure it schedules start_background_task first go do_async_thing(c1, "op1", &lock) go func() { time.Sleep(1 * time.Second) sleepChan <- true }() for range 2 { select { case msg1 := <-c1: fmt.Println("In the c1 case") fmt.Printf("received %s\n", msg1) case _ = <-sleepChan: fmt.Println("In the sleepChan case") go do_async_thing(c2, "op2", &lock) fmt.Printf("received %s\n", <-c2) // "awaiting" on c2 here, but c1's lock won't be given up until we read it } } fmt.Println("all done") } func start_background_task(lock *sync.Mutex) { fmt.Println("starting background task") lock.Lock() fmt.Println("acquired background task lock") defer lock.Unlock() time.Sleep(5 * time.Second) fmt.Println("dropping background task lock") } func do_async_thing(c chan string, label string, lock *sync.Mutex) { fmt.Printf("%s: started\n", label) lock.Lock() fmt.Printf("%s: acuired lock\n", label) defer lock.Unlock() fmt.Printf("%s: done\n", label) c <- label }
jhhh 11mo ago
I read this once over and the part that doesn't seem to make sense to me is why the runtime chose, when there are two execution contexts up to the lock() in both future1 and future3, to wake up the main thread instead? I get why in a fair lock it would pick future1 but I don't get how that causes a different thread than the one holding the lock to execute.
tick_tock_tick 11mo ago
It seems more and more clear every day that async was rushed out the door way to quickly in Rust.
- kibwen 11mo ago
  There's a lot of improvements I could think of for async Rust, but there's basically nothing I would change about the fundamentals that underlie it (other than some tweaks to Pin, maybe, and I could quibble over some syntax). There's nothing rushed about it; it's a great foundation that demonstrably just needs someone to finish building the house on top of it (and, to continue the analogy, needs someone to finish building the sub-basement (cough, generalized coroutines)).
  - tick_tock_tick 11mo ago
    A foundation full of warts belongs in experimental. I don't know how by your own confession of the house and the sub-basement not yet being finished doesn't instantly mean it should have stayed in experimental.
    - kibwen 11mo ago
      Your assertion is that it was "rushed". And yet here we are today, talking about how much we wish were implemented. That's not rushed--that's the polar opposite of rushed. Almost nothing about what we currently have on stable would have been better if it was still percolating on nightly, and would have the downside of having almost no feedback from real-world use. I remember the pre-async days, nesting callbacks by hand. What we have now is a great improvement, and just needs more niceties stacked on top of it, not any sort of fundamental overhaul.
- clarkmcc 11mo ago
  I can’t say whether it was rushed out, but it’s clearly not everything it was advertised to be. Early on, the big talking point was that the async implementation was so modular you could swap runtimes like Lego bricks. In reality, that’s nowhere near true. Changing runtimes means changing every I/O dependency (mutexes, networking, fs), because everything is tightly coupled to the runtime. I raised this in a Reddit thread some time ago, and the feedback there reinforced that I'm not the only one with a sour Rust async taste in my mouth. https://www.reddit.com/r/rust/comments/1f4z84r/is_it_fair_to_say_that_asyncawait_is_a_leaky/ https://www.reddit.com/r/rust/comments/1f4z84r/is_it_fair_to...
qouteall 11mo ago
Simplify: tokio::select! will discard other futures when one future progress. The discarded futures will never be run again. Normally when a future is discarded it's dropped. When a future holding lock is dropped, lock is released, but it's passing future borrow to select so the discarded future is not dropped while holding lock. So it leaves a future that holds a lock that will never run again.
mleonhard 11mo ago
> // Start a background task that takes the lock and holds it for a few seconds. Holding a lock while waiting for IO can destroy a system's performance. With async Rust, we can prevent this by making the MutexGuard !Send, so it cannot be held across an await. Specifically, because it is !Send, it cannot be stored in the Future [2], so it must be dropped immediately, freeing the lock. This also prevents Futurelock deadlock. This is how I wrote safina::sync::Mutex [0]. I did try to make it Send, like Tokio's MutexGuard, but stopped when I realized that it would become very complicated or require unsafe. > You could imagine an unfair Mutex that always woke up all waiters and let them race to grab the lock again. That would not suffer from risk of futurelock, but it would have the thundering herd problem plus all the liveness issues associated with unfair synchronization primitives. Thundering herd is when clients overload servers. This simple Mutex has O(n^2) runtime: every task must acquire and release the mutex, which adds all waiting tasks to the scheduler queue. In practice, scheduling a task is very fast (~600ns). As long as polling the lock-mutex-future is fast and you have <500 waiting tasks, then the O(n^2) runtime is fine. Performance is hard to predict. I wrote Safina using the simplest possible implementations and assumed they would be slow. Then I wrote some micro-benchmarks and found that some parts (like the async Mutex) actually outperform Tokio's complicated versions [1]. I spent days coding optimizations that did not improve performance (work stealing) or even reduced performance (thread affinity). Now I'm hesitant to believe assumptions and predictions about performance, even if they are based on profiling data. [0] https://docs.rs/safina/latest/safina/sync/struct.MutexGuard.html https://docs.rs/safina/latest/safina/sync/struct.MutexGuard.... [1] https://docs.rs/safina/latest/safina/index.html#benchmark https://docs.rs/safina/latest/safina/index.html#benchmark [2] Multi-threaded async executors require futures to be Send.
- dvratil 11mo ago
  I would guess this is just to make the explanation of the bug easier. In real world, the futurelock could occur even with very short locks, it just wouldn't be so deterministic. Having a minimal reproducer that you have to run a thousand times and it will maybe futurelock doesn't really make for a good example :)
  - 11mo ago
bilbo-b-baggins 11mo ago
I’m just gonna make a new language that has future borrowing semantics and future lifetimes to solve this.
ideaformlabs 11mo ago
It’s kind of wild how even the most careful Rust code can run into issues like this, really shows how deep async programming goes.
- 24f0bacc7c72d0a 11mo ago
  This is why I use a threadpool instead. Cant deal with the complexity of async code.
jcalvinowens 11mo ago
I have very little Rust experience... but I'm hung up on this: > The lock is given to future1 > future1 cannot run (and therefore cannot drop the Mutex) until the task starts running it. This seems like a contradiction to me. How can future1 acquire the Mutex in the first place, if it cannot run? The word "given" is really odd to me. Why would do_async_thing() not immediately run the prints, return, and drop the lock after acquiring it? Why does future1 need to be "polled" for that to happen? I get that due to the select! behavior, the result of future1 is not consumed, but I don't understand how that prevents it from releasing the mutex. It's more typical in my experience that the act of granting the lock to a thread is what makes it runnable, and it runs right then. Having to take some explicit second action to make that happen seems fundamentally broken to me... EDIT: Rephrased for clarity.
- oconnor663 11mo ago
  > This seems like a contradiction to me. How can future1 acquire the Mutex in the first place, if it cannot run? The word "given" is really odd to me. `future1` did run for a bit, and it got far enough to acquire the mutex. (As the article mentioned, technically it took a position in a queue that means it will get the mutex, but that's morally the same thing here.) Then it was "paused". I put "paused" in scare quotes because it kind of makes futures sound like processes or threads, which have a "life of their own" until/unless something "interrupts" them, but an important part of this story is that Rust futures aren't really like that. When you get down to the details, they're more like a struct or a class that just sits there being data unless you call certain methods on it (repeatedly). That's what the `.await` keyword does for you, but when you use more interesting constructs like `select!`, you start to get more of the details in your face. It's hard to be more concrete than that without getting into an overwhelming amount of detail. I wrote a set of blog posts that try to cover it without hand-waving the details away, but they're not short, and they do require some Rust background: https://jacko.io/async_intro.html https://jacko.io/async_intro.html
  - jcalvinowens 11mo ago
    So my understanding was correct, it requires the programmer to deal with scheduling explicitly in userspace. If I'm writing bare metal code for e.g. a little cortex M0, I can very much see the utility of this abstraction. But it seems like an absolutely absurd exercise for code running in userspace on a "real" OS like Linux. There should be some simpler intermediate abstraction... this seems like a case of forcing a too-complex interface on users who don't really require it.
samdoesnothing 11mo ago
LOL. All the Rust evangelists talk about safety when stuff like this exists? JFC. Can we stop calling Rust safe now? Finally? I mean we all know deep in our hearts that trivial memory safety doesn't mean programs are correct or "safe" by any means but its nice to have proof that Rust is fundamentally unsafe for asynchronous tasks at least. Or at least "unsound". Structured concurrency will always win IMO.
- mustache_kimono 11mo ago
  > All the Rust evangelists talk about safety when stuff like this exists? JFC. Deadlocks can happen anywhere? You can replicate this pattern in golang.
  - yxhuvud 11mo ago
    While I don't like the tone of the grandparent, comparing to Go is kinda irrelevant when it used structured concurrency as the example of how to solve it. It is of course also not a panacea..
  - samdoesnothing 11mo ago
    Golang doesn't have legions of evangelicals claiming it's a safe language and everything should be written in it.
    - mustache_kimono 11mo ago
      > Golang doesn't have legions of evangelicals claiming it's a safe language and everything should be written in it. But, to be very clear, Rust has never claimed to prevent deadlocks? See: https://doc.rust-lang.org/reference/behavior-not-considered-unsafe.html?highlight=deadlock#behavior-not-considered-unsafe https://doc.rust-lang.org/reference/behavior-not-considered-...
lowbloodsugar 11mo ago
I know this is going to sound trite, but “don’t do that”. It’s no different than deciding to poll the win32 event queue inside an a method you executed in response to polling the event queue. Nested shit is always going to cause a bug. I guess each new generation just has to learn.
- wngr 11mo ago
  It’s not nested, that’s the thing.
- dap 11mo ago
  Don't do ... what, exactly? The RFD answers this more precisely and provides suggestions for alternatives. But it's not very simple because the things that can cause this are all common patterns individually and it's only the confluence (which can be spread across layers of the program) that introduces this problem. In our case, it wasn't a Mutex, but an mpsc channel (that was working correctly! it just got very briefly saturated) and it was 3-4 modules lower in the stack than the code with the `tokio::select!` that induced this.
crabmusket 11mo ago
This feels like the sort of thing that has led to the development of deterministic simulation testing (DST) techniques as pioneered by FoundationDB and TigerBeetle. https://notes.eatonphil.com/2024-08-20-deterministic-simulation-testing.html https://notes.eatonphil.com/2024-08-20-deterministic-simulat... I hope something like this becomes popular in the Rust/Tokio space. It seems like Turmoil is that? https://tokio.rs/blog/2023-01-03-announcing-turmoil https://tokio.rs/blog/2023-01-03-announcing-turmoil
imtringued 11mo ago
Based on the description: >This RFD describes futurelock: a type of deadlock where a resource owned by Future A is required for another Future B to proceed, while the Task responsible for both Futures is no longer polling A. Futurelock is a particularly subtle risk in writing asynchronous Rust. I was honestly wondering how you could possibly cause this in any sane code base. How can an async task hold a lock and keep it open? It sounds illogical, because critical sections are meant to be short and never interrupted by anything. You're also never allowed to panic, which means you have to write no panic Rust code inside a critical section. Critical sections are very similar to unsafe blocks, but with the caveat that they cannot cause complete take over of your application. So how exactly did they bring about the impossible? They put an await call inside the critical section. The part of the code base that is not allowed to be subject to arbitrary delays. Massive facepalm. When you invoke await inside a critical section, you're essentially saying "I hereby accept that this critical section will last an indeterminate amount of time, I am fully aware of what the code I'm calling is doing and I am willing to accept the possibility that the release of the lock may never come, even if my own code is one hundred percent correct, since the await call may contain an explicit or implicit deadlock"
- dap 11mo ago
  > So how exactly did they bring about the impossible? They put an await call inside the critical section. The part of the code base that is not allowed to be subject to arbitrary delays. Massive facepalm. I'm not sure where you got the impression that the example code was where we found the problem. That's a minimal reproducer trying to explain the problem from first principles because most people look at that code and think "that shouldn't deadlock". It uses a Mutex because people are familiar with Mutexes and `sleep` just to control the interleaving of execution. The RFD shows the problem in other examples without Mutexes. Here's a reproducer that futurelocks even though nobody uses `await` with the lock held: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=8948dd2144a0ff42d59d92c03d132011 https://play.rust-lang.org/?version=stable&mode=debug&editio... > I was honestly wondering how you could possibly cause this in any sane code base. The actual issue is linked at the very top of the RFD. In our cases, we had a bounded mpsc channel used to send messages to an actor running in a separate task. That actor was working fine. But the channel did become briefly saturated (i.e., at capacity) at a point where someone tried to send on it via a `tokio::select!` similar to the one in the example.
ajross 11mo ago
Trying to get my head around this. It seems like the "rootest" cause here is a paradigm clash between lock fairness and async futures. A fair lock[1] is designed to wake up the longest-waiting task, since it got to the queue first and might otherwise be starved if the algorithm doesn't guarantee it gets to the head of the queue. BUT CRITICALLY: a future isn't a task. It's not a thread, it's not guaranteed to "run". It's just a flag that gets set somewhere. But it can consume that wakeup nonetheless. So it's possible to "wake up"[2] a future that isn't actually being polled, and won't be, until something else that is waiting on the resource that just tried to wake it up. I don't see that these concepts are ever going to work together. You can't have locks generating wakeup events that aren't consumed. If you're going to use them with async, you need to do something like a broadcast to guarantee that every waiter sees an event. Stated differently: the lock is signalling an edge-triggered interrupt, but rust async demands level sensititivity. [1] In one sense of fair. There are others, like "switch now" vs. "defer context switch", but that's not relevant here. [2] Which doesn't actually wake anything up, thus the bug.
e-dant 11mo ago
A masterclass in debugging
mpeklar 11mo ago
When considering this issue alongside with RFD 397, it seems to me that the problem is actually using future drops as an implicit (!) cancellation signal. This makes drop handlers responsible for handling every cancellation-related task, which they are not very good at. If a future is not immediately dropped after selecting on it, you get futurelock, and if it is, you get an async cancellation correctness problem, where the only way to try and interact with the cancellation execution flow is to use drop handlers (maybe in the form of scope guards). Sadly, the only solution I know of is to use an explicit cancellation signal, and to modify ~everything to work with it. In that world, almost all async functions would need to accept a cancellation parameter of some sort, like a Go Context or like the tokio-utils CancellationToken, and explicitly check it every time they await a function. The new select!-equivalent would need to signal cancellations and then keep polling all unfinished cancellation-aware futures in a loop until they finished, and maybe immediately drop all non-aware futures to prevent futurelock. The entire Tokio API would need to be wrapped to take into account cancellation tokens, as well as any other async library you would want to use. A lot of work, and you would need to do something if cancel-aware futures get dropped anyway. What a mess.
pshirshov 11mo ago
In my experience, almost any asynchronous runtime faced similar issue at some point (e.g. we helped to find and fix such issue in ZIO). It's hard to verify these protocols and very easy to write something fragile.

449 points by bcantrill 11mo ago

deleted 11mo ago

[deleted]

Sytten 11mo ago

I am wondering if there is a larger RFC for Rust to force users to not hold a variable across await points. In my mind futurelock is similar to keeping a sync lock across an await point. We have nothing right now to force a drop and I think the solution to that problem would help here.

cogman10 11mo ago
The ideas that have been batted around is called "async drop" [1] And it looks like it's still just an unaddressed well known problem [2]. Honestly, once the Mozilla sackening of rust devs happened it seems like the language has been practically rudderless. The RFC system seems almost dead as a lot of the main contributors are no longer working on rust. This initiative hasn't had motion since 2021. [3] [1] https://rust-lang.github.io/async-fundamentals-initiative/roadmap/async_drop.html https://rust-lang.github.io/async-fundamentals-initiative/ro... [2] https://rust-lang.github.io/async-fundamentals-initiative/ https://rust-lang.github.io/async-fundamentals-initiative/ [3] https://github.com/rust-lang/async-fundamentals-initiative https://github.com/rust-lang/async-fundamentals-initiative
- raggi 11mo ago
  Those pages are out of date, and AsyncDrop is in progress: https://github.com/rust-lang/rust/issues/126482 https://github.com/rust-lang/rust/issues/126482 I think "practically rudderless" here is fairly misinformed and a little harmful/rude to all the folks doing tons of great work still. It's a shame there are some stale pages around and so on, but they're not good measures of the state of the project or ecosystem. The problem of holding objects across async points is also partially implemented in this unstable lint marker which is used by some projects: https://dev-doc.rust-lang.org/unstable-book/language-features/must-not-suspend.html https://dev-doc.rust-lang.org/unstable-book/language-feature... You also get a similar effect in multi-threaded runtimes by not arbitrarily making everything in your object model Send and instead designing your architecture so that most things between wake-ups don't become arbitrarily movable references. These aren't perfect mitigations, but some tools.
  - bigstrat2003 11mo ago
    In fairness, if you're a layman to the rust development process (as I am, so I'm speaking from personal experience here) it's damn near impossible to figure out the status of things. There tracking issues, RFCs, etc which is very confusing as an outsider and gives no obvious place to look to find out the current status of a proposal. I'm sure there is a logic to it and that if I spent the time to learn it would make sense. But it is really hard to approach for someone like me.
    - kibwen 11mo ago
      If you want to find out the status of something, the best bet is to go to the Rust Zulip and ask around: https://rust-lang.zulipchat.com/ https://rust-lang.zulipchat.com/ . Most Rust initiatives are pushed forward by volunteers who are happy to talk about what they're working on, but who only periodically write status reports on tracking issues (usually in response to someone asking them what the status is). Rust isn't a company where documentation is anyone's job, it's just a bunch of people working on stuff, for better or worse.
      - 11mo ago
sunshowers 11mo ago
Note that forcing a drop of a lock guard has its own issues, particularly around leaving the guarded data in an invalid state. I cover this a bit in my talk that Bryan linked to in the OP [1]. [1] timestamped: https://youtu.be/zrv5Cy1R7r4?t=1067 https://youtu.be/zrv5Cy1R7r4?t=1067
ameliaquining 11mo ago
There's an existing lint that lets you prohibit instances of specific types from being held across await points: https://rust-lang.github.io/rust-clippy/stable/index.html#await_holding_invalid_type https://rust-lang.github.io/rust-clippy/stable/index.html#aw...
amluto 11mo ago
I’m not convinced that this can help in a meaningful way. Fundamentally, if you have two coroutines (or cooperatively scheduled threads or whatever), and one of them holds a lock, and the other one is awaiting the lock, and you don’t schedule the first one, you’re stuck. I wonder if there’s a form of structured concurrency that would help. If I create two futures and start both of them (in Rust this means polling each one once) but do not continue to poll both, then I’m sort of making a mistake. So imagine a world where, to poll a future at all, I need to have a nursery, and the nursery is passed in from my task and down the call stack. When I create a future, I can pass in my nursery, but that future then gets an exclusive reference to my future until it’s complete or cancelled. If I want to create more than one future that are live concurrently, I need to create a FutureGroup (that gets an exclusive reference to my nursery) and that allows me to create multiple sub-nurseries that can be used to make futures but cannot be used to poll them — instead I poll the FutureGroup. (I have yet to try using an async/await system or a reactor or anything of the sort that is not very easy to screw up. My current pet peeve is this pattern: data = await thingy.read() What if thingy.read() succeeds but I am cancelled? This gets nasty is most programming languages. Python: the docs on when I can get cancelled are almost nonexistent, and it’s not obviously possible to catch the CancelledError such that I still have data and can therefore save it somewhere so it’s not lost. Rust: what if thingy thinks it has returned the data but I’m never polled again? Maybe this can’t happen if I’m careful, but that requires more thought than I’m really happy with.)
mechanical_berk 11mo ago
I agree. It seems like this bug arises because one Future is awaited while another is ignored. I have seen this sort of bug a lot. So maybe all that is needed is a lint that warns if you keep a Future (or a reference to one) across an await point? The Future you are awaiting wouldn't count of course. Is there some case where this doesn't work?

orthecreedence 11mo ago

Great read, and the example code makes sense. This stuff can be a nightmare to find, but once you do it's like a giant 1000 piece puzzle just clicks together instantly.

bcantrill 11mo ago
Indeed. One of the interesting side effects of being a remote company that records everything[0] is that we have the instant where the "1000 piece puzzle just clicks together" recorded, and it's honestly pretty wild. In this case, it was very much a shared brainstorming between four engineers (Eliza, Sean, John and Dave) -- and there is almost a passing of the baton where they start to imagine the kind of scenario that could induce this and then realize that those are exactly the conditions that exist in the software. We are (on brand?) going to do a podcast episode on this on Monday[1]; ahead of that conversation I'm going to get a clip of that video out, just because it's interesting to see the team work together to debug it. [0] https://rfd.shared.oxide.computer/rfd/0537 https://rfd.shared.oxide.computer/rfd/0537 [1] https://discord.gg/QrcKGTTPrF?event=1433923627988029462 https://discord.gg/QrcKGTTPrF?event=1433923627988029462
- mycoliza 11mo ago
  As a member of (Eliza, Sean, John, and Dave), I can second that debugging this was certainly an adventure. I'm not going to go as far as to say that we had fun, since...you can't have a heroic narrative without real struggle. But it was certainly rewarding to be in the room for that "a-ha!" moment, in which all the pieces really did begin to fit together very quickly. It was like the climax of a detective story --- and it was particularly well-scripted the way each of us contributed a little piece of the puzzle.
  - littlestymaar 11mo ago
    Since you are of of the people working directly on this codebase, may I ask you why is select! being used/allowed in the first place? Its footgun-y nature has been known for years (IIRC even the first version of the tokio documentation warned against that) and as such I don't really understand why people are still using it. (For context I was the lead of a Rust team working on a pretty complex async networking program and we had banned select! very early in the project and never regretted this decision once).

oconnor663 11mo ago

> FAQ: doesn’t future1 get cancelled? I guess cancellation is really two different things, which usually happen at the ~same time, but not in this case: 1) the future stops getting polled, and 2) the future gets dropped. In this example the drop is delayed, and because the future is holding a guard,* the delay has side effects. So the future "has been cancelled" in the sense that it will never again make forward progress, but it "hasn't been cancelled yet" in the sense that it's still holding resources. I wonder if it's practical to say "make sure those two things always happen together"? * Technically a Tokio-internal `Acquire` future that owns a queue position to get a guard, but it sounds like the exact same bug could manifest after it got the guard too, so let's call it a guard.

jacquesm 11mo ago

If any rust designers are lurking about here: what made you decide to go for the async design pattern instead of the actor pattern, which - to me at least - seems so much cleaner and so much harder to get wrong? Ever since I started using Erlang it felt like I finally found 'the right way' when before then I did a lot of work with sockets and asynchronous worker threads. But even though it usually worked as advertised it had a large number of really nasty pitfalls which the actor model seemed to - effortlessy - step aside. So I'm seriously wondering what the motivation was. I get why JS uses async, there isn't any other way there, by the time they added async it was too late to change the fundamentals of the language to such a degree. But rust was a clean slate.

sunshowers 11mo ago
Not a Rust designer, but a big motivation for Rust's async design was wanting it to work on embedded, meaning no malloc and no threads. This unfortunately precludes the vast majority of the design space here, from active futures as seen in JS/C#/Go to the actor model. You can write code using the actor model with Tokio. But it's not natural to do so.
- lll-o-lll 11mo ago
  As a curious bystander, it will be interesting to see how the Zig async implementation pans out. They have the advantage of getting to see the pitfalls of those that have come before. Getting back to Rust, even if not natural, I agree with the parent that the actor model is simply the better paradigm. Zero runtime allocation should still be possible, you just have to accept some constraints. I think async looks simple because it looks like writing imperative code; unfortunately it is just obfuscating the complex reality underlying. The actor model makes things easier to reason about, even if it looks more complicated initially.
  - sunshowers 11mo ago
    I think you can do a static list of actors or tasks in embedded, but it's hard to dynamically spin up new ones. That's where intra-task concurrency is helpful.

moralestapia 11mo ago

Hmm, curious to see if this could happen on JS. I'll reproduce the code.

raggi 11mo ago
yes, you can produce similar issues with promise guarded states and so on as well, it's a fairly common issue in async programming, but can be surprising when it's hidden by layers of abstraction / far up/down a call-chain.
comex 11mo ago
JS shouldn't have a direct equivalent because JS async functions are eager. Once you call an async function, it will keep running even if the caller doesn't await it, or stops awaiting it. So in the scenario described, the function next in line for the lock would always have a chance to acquire and release it. The problem in Rust is that async functions are lazy and only run while they're being polled/awaited (unless wrapped in tasks). A function that's next in line for the lock might never acquire it if it's not being polled, blocking progress for other functions that are being polled.

dvt 11mo ago

> &mut future1 is dropped, but this is just a reference and so has no effect. Importantly, the future itself (future1) is not dropped. There's a lot of talk about Rust's await implementation, but I don't really think that's the issue here. After all, Rust doesn't guarantee convergence. Tokio, on the other hand (being a library that handles multi-threading), should (at least when using its own constructs, e.g. the `select!` macro). So, since the crux of the problem is the `tokio::select!` macro, it seems like a pretty clear tokio bug. Side note, I never looked at it before, but the macro[1] is absolutely hideous. [1] https://docs.rs/tokio/1.34.0/src/tokio/macros/select.rs.html https://docs.rs/tokio/1.34.0/src/tokio/macros/select.rs.html

raggi 11mo ago
i forget if this part unwinds to the exact same place, but some of this kind of design constraint in tokio stems from the much earlier language capabilities and is prohibitive to adjust without breaking the user ecosystem. one of the key advertised selling points in some of the other runtimes was specifically around behavior of tasks on drop of their join handles for example, for reasons closely related to this post.
oconnor663 11mo ago
There's nothing `select!` could do here to force `future1` to drop, because it doesn't receive ownership of `future1`. If we wanted to force this, we'd have to forbid `select!` from polling futures by reference, but that's a pretty fundamental capability that we often rely on to `select!` in a loop for example. The blanket `impl<F> Future for &mut F where F: Future ...` isn't a Tokio thing either; that's in the standard library.
- kibwen 11mo ago
  Surely not every use of `select!` needs this ability. If you can design a more restrictive interface that makes correctness easier to determine, then you should use that interface where you can, and reserve `select!` for only those cases where you can't.
mycoliza 11mo ago

OptionOfT 11mo ago

- wrong -

DAlperin 11mo ago
I think the next sentence clarifies pretty well. > In this case, what’s dropped is &mut future1. But future1 is not dropped, so the actual future is not cancelled.
oconnor663 11mo ago
The author clearly understands these details. I think it's just a question of wording: did we "drop a reference (which has no effect)" or did we "not drop anything (because references don't implement Drop)"?
deleted 11mo ago
[deleted]

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.

arjie 11mo ago

Wow, that makes sense afterwards but I would not have guessed at it immediately looking at the code. Very insidious. Great blogpost.

keyliejener 11mo ago

[dead]

wbl 11mo ago

Sadly I'm away from my bookshelf but I think Concurrent ML solved this issue.

forrestthewoods 11mo ago

I feel like I’m pretty good at writing multithreaded code. I’ve done it a lot. As long as you use primitives like Rust Mutex that enforce correctness for data access (ie no accessing data without the lock) it’s pretty simple. Define a clean boundary API and you’re off to the races. async code is so so so much more complex. It’s so hard to read and rationalize. I could not follow this post. I tried. But it’s just a full extra order of complexity. Which is a shame because async code is supposed to make code simpler! But I’m increasingly unconfident that’s true.

amelius 11mo ago
Async code is simpler because you're implicitly holding a lock on the CPU. That's also why you should stay away from it: it increases latency. Especially since Rust is about speed and responsiveness. In general, async programming in Rust makes little sense.
- forrestthewoods 11mo ago
  I love Rust. But I’m 100% convinced Rust chose the wrong tradeoffs with their async model. Just give me green threads and use malloc to grow the stack. It’s fine. That would have been better imho.
  - mjevans 11mo ago
    Hell, even force threads to be allocated from a bucket of N threads defined at compile time. Surely that'd work for embedded / GPU space?
  - gf000 11mo ago
    You can't have a low-level language and green threads at the same time.
    - forrestthewoods 11mo ago
      Why not?

octoberfranklin 11mo ago

It’s really important to understand what’s happening here Then maybe you should take a moment to pick more descriptive identifiers than future1, future2, future3, do_stuff, and do_async_thing. This coding style is atrocious.

dap 11mo ago
Is it possible that those names are intentionally chosen and actually do carry meaning?
gpm 11mo ago
If you prefer "real" names you can always look at the actual code that had a bug - here it is before the bug was fixed: https://github.com/oxidecomputer/omicron/blob/a253f541a4a32a4326d7ddfc04df27c0e47de42b/nexus/src/app/background/tasks/support_bundle_collector.rs#L496-L551 https://github.com/oxidecomputer/omicron/blob/a253f541a4a32a...

Matthias247 11mo ago

As far as I remember from building these things with others within the async rust ecosystem (hey Eliza!) was that there was a certain tradeoff: if you wouldn’t be able to select on references, you couldn’t run into this issue. However you also wouldn’t be able run use select! in a while loop and try to acquire the same lock (or read from the same channel) without losing your position in the queue. I fully agree that this and the cancellation issues discussed before can lead to surprising issues even to seasoned Rust experts. But I’m not sure what really can be improved under the main operating model of async rust (every future can be dropped). But compared to working with callbacks the amount of surprising things is still rather low :)

octoberfranklin 11mo ago
> However you also wouldn’t be able run use select! in a while loop and try to acquire the same lock (or read from the same channel) without losing your position in the queue. No, just have select!() on a bunch of owned Futures return the futures that weren't selected instead of dropping them. Then you don't lose state. Yes, this is awkward, but it's the only logically coherent way. There is probably some macro voodoo that makes it ergonomic. But even this doesn't fix the root cause because dropping an owned Future isn't guaranteed to cancel it cleanly. For the real root cause: https://news.ycombinator.com/item?id=45777234 https://news.ycombinator.com/item?id=45777234
- mycoliza 11mo ago
  > No, just have select!() on a bunch of owned Futures return the futures that weren't selected instead of dropping them. Then you don't lose state. How does that prevent this kind of deadlock? If the owned future has acquired a mutex, and you return that future from the select so that it might be polled again, and the user assigns it to a variable, then the future that has acquired the mutex but has not completed is still not dropped. This is basically the same as polling an `&mut future`, but with more steps.
  - octoberfranklin 11mo ago

octoberfranklin 11mo ago

For anybody who wants to cut to the chase, it's this: > The behavior of tokio::select! is to poll all branches' futures only until one of them returns `Ready`. At that point, it drops the other branches' futures and only runs the body of the branch that’s ready. This is, unfortunately, doing what it's supposed to do: acting as a footgun. The design of tokio::select!() implicitly assumes it can cancel tasks cleanly by simply dropping them. We learned the hard way back in the Java days that you cannot kill threads cleanly all the time. Unsurprisingly, the same thing is true for async tasks. But I guess every generation of programmers has to re-learn this lesson. Because, you know, actually learning from history would be too easy. Unfortunately there are a bunch of footguns in tokio (and async-std too). The state-machine transformation inside rustc is a thing of beauty, but the libraries and APIs layered on top of that should have been iterated many more times before being rolled out into widespread use.

littlestymaar 11mo ago
I genuinely don't understand why people use select! at all given how much of a footgun it is.
- octoberfranklin 11mo ago
  Well the less-footgun-ish alternative would look something like a Stream API, but the last time I checked tokio-stream wasn't stable yet. Then you could merge a `Stream<A>` and `Stream<B>` into a `Stream<Either<A,B>>` and pull from that. Since you're dealing with owned streams, dropping the stream forces some degree of cleanup. There are still ways to make a mess, but they take more effort. .................................... Ratelimit so I have to reply to mycoliza with an edit here: That example calls `do_thing()`, whose body does not appear anywhere in the webpage. Use better identifiers. If you meant `do_stuff()`, you haven't replaced select!() with streams, since `do_stuff()` calls `select!()`. The problem is `select!()`; if you keep using `select!()` but just slather on a bunch of streams that isn't going to fix anything. You have to get rid of select!() by replacing it with streams.
  - 11mo ago

hitekker 11mo ago

Skimming through, this document feels thorough and transparent. Clearly, a hard lesson learned. The footnotes, in particular, caught my eye https://rfd.shared.oxide.computer/rfd/397#_external_references https://rfd.shared.oxide.computer/rfd/397#_external_referenc... > Why does this situation suck? It’s clear that many of us haven’t been aware of cancellation safety and it seems likely there are many cancellation issues all over Omicron. It’s awfully stressful to find out while we’re working so hard to ship a product ASAP that we have some unknown number of arbitrarily bad bugs that we cannot easily even find. It’s also frustrating that this feels just like the memory safety issues in C that we adopted Rust to get away from: there’s some dynamic property that the programmer is responsible for guaranteeing, the compiler is unable to provide any help with it, the failure mode for getting it wrong is often undebuggable (by construction, the program has not done something it should have, so it’s not like there’s a log message or residual state you could see in a debugger or console), and the failure mode for getting it wrong can be arbitrarily damaging (crashes, hangs, data corruption, you name it). Add on that this behavior is apparently mostly undocumented outside of one macro in one (popular) crate in the async/await ecosystem and yeah, this is frustrating. This feels antithetical to what many of us understood to be a core principle of Rust, that we avoid such insidious runtime behavior by forcing the programmer to demonstrate at compile-time that the code is well-formed

rtpg 11mo ago
I guess one big question here is whether there's a higher layer abstraction that is available to wrap around patterns to avoid this. It does feel like there's still generally possibilities of deadlocks in Rust concurrency right? I understand the feeling here that it feels like ... uhh... RAII-style _something_ should be preventing this, because it feels like statically we should be able to identify this issue in this simple case. I still have a hard time understanding how much of this is incidental and how much of this is just downstream of the Rust/Tokio model not having enough to work on here.
- embedding-shape 11mo ago
  > I guess one big question here is whether there's a higher layer abstraction that is available to wrap around patterns to avoid this. Something like Actors, on top of Tokio, would be one way: https://ryhl.io/blog/actors-with-tokio/ https://ryhl.io/blog/actors-with-tokio/

Dagonfly 11mo ago

That's a really subtle version of the deadlock described in withoutboats FuturesUnordered post [0] When using “intra-task” concurrency, you really have to ensure that none of the futures are starving. Spawning task should probably be the default. For timeouts use tokio::select! but make sure all pending futures are owned by it. I would never recommend FuturesUnordered unless you really test all edge-cases. [0] https://without.boats/blog/futures-unordered/ https://without.boats/blog/futures-unordered/

quietbritishjim 11mo ago

Wow, it is simply outrageous that Rust doesn't just allow all active tasks to make progress. It creates a whole class of incomprehensible bugs, like this one, for no reason. Can any Rust experts explain why it's done this way? It seems like an unforced error. In Python, I often use the Trio library, which offers "structured, concurrency": tasks are (only) spawned into lexical scopes, and they are all completed (waited for) before that scope is left. That includes waiting for any cancelled tasks (which are allowed to do useful async work, including waiting for any of their own task scopes to complete). Could Rust do something like that? It's far easier to reason about than traditional async programs, which seems up Rust's street. As a bonus it seems to solve this problem, since a Rust equivalent would presumably have all tasks implicitly polled by their owning scope.

duped 11mo ago
So there's a distinction between a task and a future. A future doesn't do anything until it's polled, and since there's nothing special about async runtimes (it's just user level code), it's always possible to create futures and never poll them, or stop polling them. A task is a different construct and usually tied to the runtime. If you look at the suggestions in the RFD they call out using a task explicitly instead of polling a future in place. There's some debate to be had over what constitutes "cancellation." The article and most colloquial definitions I've heard define it as a future being dropped before being polled to completion. Which is very clean - if you want to cancel a future, just drop it. Since Rust strongly encourages RAII, cleanup can go in drop implementations. A much tougher definition of cancellation is "the future is never polled again" which is what the article hits on. The future isn't dropped but its poll is also unreachable, hence the deadlock.
- wrs 11mo ago
  I wish "cancellation" wasn't used for both of those. It seems to obfuscate understanding quite a bit. We should call them "dropped" and "abandoned" or something.
  - duped 11mo ago

levodelellis 11mo ago

In October alone I seen 5+ articles and comments about multi-threading and I don't know why I always said if your code locks or use atomics, it's wrong. Everyone says I'm wrong but you get things like what's described in the article. I'd like to recommend a solution but there's pretty much no reasonable way to implement multi-threading when you're not an expert. I heard Erlang and Elixir are good but I haven't tried them so I can't really comment

umvi 11mo ago
> I always said if your code locks or use atomics, it's wrong. Everyone says I'm wrong but you get things like what's described in the article. Ok so say you are simulating high energy photons (x-rays) flowing through a 3d patient volume. You need to simulate 2 billion particles propagating through the patient in order to get an accurate estimation of how the radiation is distributed. How do you accomplish this without locks or atomics without the simulation taking 100 hours to run? Obviously it would take forever to simulate 1 particle at a time, but without locks or atomics the particles will step on each others' toes when updating radiation distribution in the patient. I suppose you could have 2 billion copies of the patient's volume in memory and each particle gets its own private copy and then you merge them all at the end...
- levodelellis 11mo ago
  From my understanding this talk describes how he implemented a solution for a similar problem https://www.youtube.com/watch?v=Kvsvd67XUKw https://www.youtube.com/watch?v=Kvsvd67XUKw I'm saying if you're not writing multi-threaded code everyday, use a library. It can use atomics/locks but you shouldn't use it directly. If the library is designed well it'd be impossible to deadlock.
  - jstimpfle 11mo ago
    If you take programming serious, learn it. With a library that encapsulates a low number of patterns (like message passing) you'll be very limited. If you never start learning about lower level multi-threading issues you'll never learn it. And it's not _that_ hard. I'm not writing multi threaded every day (by far), but often enough that I can write useful things (using shared memory, atomics, mutexes, condition variables, etc). And I'm looking forward to learn more, better understand various issues, learn new patterns.

mdasen 11mo ago

I rewrote this in Go and it also deadlocks. It doesn't seem to be something that's Rust specific. I'm going to write down the order of events. 1. Background task takes the lock and holds it for 5 seconds. 2. Async Thing 1 tries to take the lock, but must wait for background task to release it. It is next in line to get the lock. 3. We fire off a goroutine that's just sleeping for a second. 4. Select wants to find a channel that is finished. The sleepChan finishes first (since it's sleeping for 1 second) while Async Thing 1 is still waiting 4 more seconds for the lock. So select will execute the sleepChan case. 5. That case fires off Async Thing 2. Async Thing 2 is waiting for the lock, but it is second in line to get the lock after Async Thing 1. 6. Async Thing 1 gets the lock and is ready to write to its channel - but the main is paused trying to read from c2, not c1. Main is "awaiting" on c2 via "<-c2". Async Thing 1 can't give up its lock until it writes to c1. It can't write to c1 until c1 is "awaited" via "<-c1". But the program has already gone into the other case and until the sleepChan case finishes, it won't try to await c1. But it will never finish its case because its case depends on c1 finishing first. You can use buffered channels in Go so that Async Thing 1 can write to c1 without main reading from it, but as the article notes you could use join_all in Rust. But the issue is that you're saying with "select" in either Go or Rust "get me the first one that finishes" and then in the branch that finishes first, you are awaiting a lock that will get resolved when you read the other branch. It just doesn't feel like something that is Rust specific. func main() { lock := sync.Mutex{} c1 := make(chan string) c2 := make(chan string) sleepChan := make(chan bool) go start_background_task(&lock) time.Sleep(1 * time.Millisecond) //make sure it schedules start_background_task first go do_async_thing(c1, "op1", &lock) go func() { time.Sleep(1 * time.Second) sleepChan <- true }() for range 2 { select { case msg1 := <-c1: fmt.Println("In the c1 case") fmt.Printf("received %s\n", msg1) case _ = <-sleepChan: fmt.Println("In the sleepChan case") go do_async_thing(c2, "op2", &lock) fmt.Printf("received %s\n", <-c2) // "awaiting" on c2 here, but c1's lock won't be given up until we read it } } fmt.Println("all done") } func start_background_task(lock *sync.Mutex) { fmt.Println("starting background task") lock.Lock() fmt.Println("acquired background task lock") defer lock.Unlock() time.Sleep(5 * time.Second) fmt.Println("dropping background task lock") } func do_async_thing(c chan string, label string, lock *sync.Mutex) { fmt.Printf("%s: started\n", label) lock.Lock() fmt.Printf("%s: acuired lock\n", label) defer lock.Unlock() fmt.Printf("%s: done\n", label) c <- label }

jhhh 11mo ago

I read this once over and the part that doesn't seem to make sense to me is why the runtime chose, when there are two execution contexts up to the lock() in both future1 and future3, to wake up the main thread instead? I get why in a fair lock it would pick future1 but I don't get how that causes a different thread than the one holding the lock to execute.

tick_tock_tick 11mo ago

It seems more and more clear every day that async was rushed out the door way to quickly in Rust.

kibwen 11mo ago
There's a lot of improvements I could think of for async Rust, but there's basically nothing I would change about the fundamentals that underlie it (other than some tweaks to Pin, maybe, and I could quibble over some syntax). There's nothing rushed about it; it's a great foundation that demonstrably just needs someone to finish building the house on top of it (and, to continue the analogy, needs someone to finish building the sub-basement (cough, generalized coroutines)).
- tick_tock_tick 11mo ago
  A foundation full of warts belongs in experimental. I don't know how by your own confession of the house and the sub-basement not yet being finished doesn't instantly mean it should have stayed in experimental.
  - kibwen 11mo ago
    Your assertion is that it was "rushed". And yet here we are today, talking about how much we wish were implemented. That's not rushed--that's the polar opposite of rushed. Almost nothing about what we currently have on stable would have been better if it was still percolating on nightly, and would have the downside of having almost no feedback from real-world use. I remember the pre-async days, nesting callbacks by hand. What we have now is a great improvement, and just needs more niceties stacked on top of it, not any sort of fundamental overhaul.
clarkmcc 11mo ago
I can’t say whether it was rushed out, but it’s clearly not everything it was advertised to be. Early on, the big talking point was that the async implementation was so modular you could swap runtimes like Lego bricks. In reality, that’s nowhere near true. Changing runtimes means changing every I/O dependency (mutexes, networking, fs), because everything is tightly coupled to the runtime. I raised this in a Reddit thread some time ago, and the feedback there reinforced that I'm not the only one with a sour Rust async taste in my mouth. https://www.reddit.com/r/rust/comments/1f4z84r/is_it_fair_to_say_that_asyncawait_is_a_leaky/ https://www.reddit.com/r/rust/comments/1f4z84r/is_it_fair_to...

qouteall 11mo ago

Simplify: tokio::select! will discard other futures when one future progress. The discarded futures will never be run again. Normally when a future is discarded it's dropped. When a future holding lock is dropped, lock is released, but it's passing future borrow to select so the discarded future is not dropped while holding lock. So it leaves a future that holds a lock that will never run again.

mleonhard 11mo ago

> // Start a background task that takes the lock and holds it for a few seconds. Holding a lock while waiting for IO can destroy a system's performance. With async Rust, we can prevent this by making the MutexGuard !Send, so it cannot be held across an await. Specifically, because it is !Send, it cannot be stored in the Future [2], so it must be dropped immediately, freeing the lock. This also prevents Futurelock deadlock. This is how I wrote safina::sync::Mutex [0]. I did try to make it Send, like Tokio's MutexGuard, but stopped when I realized that it would become very complicated or require unsafe. > You could imagine an unfair Mutex that always woke up all waiters and let them race to grab the lock again. That would not suffer from risk of futurelock, but it would have the thundering herd problem plus all the liveness issues associated with unfair synchronization primitives. Thundering herd is when clients overload servers. This simple Mutex has O(n^2) runtime: every task must acquire and release the mutex, which adds all waiting tasks to the scheduler queue. In practice, scheduling a task is very fast (~600ns). As long as polling the lock-mutex-future is fast and you have <500 waiting tasks, then the O(n^2) runtime is fine. Performance is hard to predict. I wrote Safina using the simplest possible implementations and assumed they would be slow. Then I wrote some micro-benchmarks and found that some parts (like the async Mutex) actually outperform Tokio's complicated versions [1]. I spent days coding optimizations that did not improve performance (work stealing) or even reduced performance (thread affinity). Now I'm hesitant to believe assumptions and predictions about performance, even if they are based on profiling data. [0] https://docs.rs/safina/latest/safina/sync/struct.MutexGuard.html https://docs.rs/safina/latest/safina/sync/struct.MutexGuard.... [1] https://docs.rs/safina/latest/safina/index.html#benchmark https://docs.rs/safina/latest/safina/index.html#benchmark [2] Multi-threaded async executors require futures to be Send.

dvratil 11mo ago
I would guess this is just to make the explanation of the bug easier. In real world, the futurelock could occur even with very short locks, it just wouldn't be so deterministic. Having a minimal reproducer that you have to run a thousand times and it will maybe futurelock doesn't really make for a good example :)
- 11mo ago

bilbo-b-baggins 11mo ago

I’m just gonna make a new language that has future borrowing semantics and future lifetimes to solve this.

ideaformlabs 11mo ago

It’s kind of wild how even the most careful Rust code can run into issues like this, really shows how deep async programming goes.

24f0bacc7c72d0a 11mo ago
This is why I use a threadpool instead. Cant deal with the complexity of async code.

jcalvinowens 11mo ago

I have very little Rust experience... but I'm hung up on this: > The lock is given to future1 > future1 cannot run (and therefore cannot drop the Mutex) until the task starts running it. This seems like a contradiction to me. How can future1 acquire the Mutex in the first place, if it cannot run? The word "given" is really odd to me. Why would do_async_thing() not immediately run the prints, return, and drop the lock after acquiring it? Why does future1 need to be "polled" for that to happen? I get that due to the select! behavior, the result of future1 is not consumed, but I don't understand how that prevents it from releasing the mutex. It's more typical in my experience that the act of granting the lock to a thread is what makes it runnable, and it runs right then. Having to take some explicit second action to make that happen seems fundamentally broken to me... EDIT: Rephrased for clarity.

oconnor663 11mo ago
> This seems like a contradiction to me. How can future1 acquire the Mutex in the first place, if it cannot run? The word "given" is really odd to me. `future1` did run for a bit, and it got far enough to acquire the mutex. (As the article mentioned, technically it took a position in a queue that means it will get the mutex, but that's morally the same thing here.) Then it was "paused". I put "paused" in scare quotes because it kind of makes futures sound like processes or threads, which have a "life of their own" until/unless something "interrupts" them, but an important part of this story is that Rust futures aren't really like that. When you get down to the details, they're more like a struct or a class that just sits there being data unless you call certain methods on it (repeatedly). That's what the `.await` keyword does for you, but when you use more interesting constructs like `select!`, you start to get more of the details in your face. It's hard to be more concrete than that without getting into an overwhelming amount of detail. I wrote a set of blog posts that try to cover it without hand-waving the details away, but they're not short, and they do require some Rust background: https://jacko.io/async_intro.html https://jacko.io/async_intro.html
- jcalvinowens 11mo ago
  So my understanding was correct, it requires the programmer to deal with scheduling explicitly in userspace. If I'm writing bare metal code for e.g. a little cortex M0, I can very much see the utility of this abstraction. But it seems like an absolutely absurd exercise for code running in userspace on a "real" OS like Linux. There should be some simpler intermediate abstraction... this seems like a case of forcing a too-complex interface on users who don't really require it.

samdoesnothing 11mo ago

LOL. All the Rust evangelists talk about safety when stuff like this exists? JFC. Can we stop calling Rust safe now? Finally? I mean we all know deep in our hearts that trivial memory safety doesn't mean programs are correct or "safe" by any means but its nice to have proof that Rust is fundamentally unsafe for asynchronous tasks at least. Or at least "unsound". Structured concurrency will always win IMO.

mustache_kimono 11mo ago
> All the Rust evangelists talk about safety when stuff like this exists? JFC. Deadlocks can happen anywhere? You can replicate this pattern in golang.
- yxhuvud 11mo ago
  While I don't like the tone of the grandparent, comparing to Go is kinda irrelevant when it used structured concurrency as the example of how to solve it. It is of course also not a panacea..
- samdoesnothing 11mo ago
  Golang doesn't have legions of evangelicals claiming it's a safe language and everything should be written in it.
  - mustache_kimono 11mo ago
    > Golang doesn't have legions of evangelicals claiming it's a safe language and everything should be written in it. But, to be very clear, Rust has never claimed to prevent deadlocks? See: https://doc.rust-lang.org/reference/behavior-not-considered-unsafe.html?highlight=deadlock#behavior-not-considered-unsafe https://doc.rust-lang.org/reference/behavior-not-considered-...

lowbloodsugar 11mo ago

I know this is going to sound trite, but “don’t do that”. It’s no different than deciding to poll the win32 event queue inside an a method you executed in response to polling the event queue. Nested shit is always going to cause a bug. I guess each new generation just has to learn.

wngr 11mo ago
It’s not nested, that’s the thing.
dap 11mo ago
Don't do ... what, exactly? The RFD answers this more precisely and provides suggestions for alternatives. But it's not very simple because the things that can cause this are all common patterns individually and it's only the confluence (which can be spread across layers of the program) that introduces this problem. In our case, it wasn't a Mutex, but an mpsc channel (that was working correctly! it just got very briefly saturated) and it was 3-4 modules lower in the stack than the code with the `tokio::select!` that induced this.

crabmusket 11mo ago

This feels like the sort of thing that has led to the development of deterministic simulation testing (DST) techniques as pioneered by FoundationDB and TigerBeetle. https://notes.eatonphil.com/2024-08-20-deterministic-simulation-testing.html https://notes.eatonphil.com/2024-08-20-deterministic-simulat... I hope something like this becomes popular in the Rust/Tokio space. It seems like Turmoil is that? https://tokio.rs/blog/2023-01-03-announcing-turmoil https://tokio.rs/blog/2023-01-03-announcing-turmoil

imtringued 11mo ago

Based on the description: >This RFD describes futurelock: a type of deadlock where a resource owned by Future A is required for another Future B to proceed, while the Task responsible for both Futures is no longer polling A. Futurelock is a particularly subtle risk in writing asynchronous Rust. I was honestly wondering how you could possibly cause this in any sane code base. How can an async task hold a lock and keep it open? It sounds illogical, because critical sections are meant to be short and never interrupted by anything. You're also never allowed to panic, which means you have to write no panic Rust code inside a critical section. Critical sections are very similar to unsafe blocks, but with the caveat that they cannot cause complete take over of your application. So how exactly did they bring about the impossible? They put an await call inside the critical section. The part of the code base that is not allowed to be subject to arbitrary delays. Massive facepalm. When you invoke await inside a critical section, you're essentially saying "I hereby accept that this critical section will last an indeterminate amount of time, I am fully aware of what the code I'm calling is doing and I am willing to accept the possibility that the release of the lock may never come, even if my own code is one hundred percent correct, since the await call may contain an explicit or implicit deadlock"

dap 11mo ago
> So how exactly did they bring about the impossible? They put an await call inside the critical section. The part of the code base that is not allowed to be subject to arbitrary delays. Massive facepalm. I'm not sure where you got the impression that the example code was where we found the problem. That's a minimal reproducer trying to explain the problem from first principles because most people look at that code and think "that shouldn't deadlock". It uses a Mutex because people are familiar with Mutexes and `sleep` just to control the interleaving of execution. The RFD shows the problem in other examples without Mutexes. Here's a reproducer that futurelocks even though nobody uses `await` with the lock held: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=8948dd2144a0ff42d59d92c03d132011 https://play.rust-lang.org/?version=stable&mode=debug&editio... > I was honestly wondering how you could possibly cause this in any sane code base. The actual issue is linked at the very top of the RFD. In our cases, we had a bounded mpsc channel used to send messages to an actor running in a separate task. That actor was working fine. But the channel did become briefly saturated (i.e., at capacity) at a point where someone tried to send on it via a `tokio::select!` similar to the one in the example.

ajross 11mo ago

Trying to get my head around this. It seems like the "rootest" cause here is a paradigm clash between lock fairness and async futures. A fair lock[1] is designed to wake up the longest-waiting task, since it got to the queue first and might otherwise be starved if the algorithm doesn't guarantee it gets to the head of the queue. BUT CRITICALLY: a future isn't a task. It's not a thread, it's not guaranteed to "run". It's just a flag that gets set somewhere. But it can consume that wakeup nonetheless. So it's possible to "wake up"[2] a future that isn't actually being polled, and won't be, until something else that is waiting on the resource that just tried to wake it up. I don't see that these concepts are ever going to work together. You can't have locks generating wakeup events that aren't consumed. If you're going to use them with async, you need to do something like a broadcast to guarantee that every waiter sees an event. Stated differently: the lock is signalling an edge-triggered interrupt, but rust async demands level sensititivity. [1] In one sense of fair. There are others, like "switch now" vs. "defer context switch", but that's not relevant here. [2] Which doesn't actually wake anything up, thus the bug.

e-dant 11mo ago

A masterclass in debugging

mpeklar 11mo ago

When considering this issue alongside with RFD 397, it seems to me that the problem is actually using future drops as an implicit (!) cancellation signal. This makes drop handlers responsible for handling every cancellation-related task, which they are not very good at. If a future is not immediately dropped after selecting on it, you get futurelock, and if it is, you get an async cancellation correctness problem, where the only way to try and interact with the cancellation execution flow is to use drop handlers (maybe in the form of scope guards). Sadly, the only solution I know of is to use an explicit cancellation signal, and to modify ~everything to work with it. In that world, almost all async functions would need to accept a cancellation parameter of some sort, like a Go Context or like the tokio-utils CancellationToken, and explicitly check it every time they await a function. The new select!-equivalent would need to signal cancellations and then keep polling all unfinished cancellation-aware futures in a loop until they finished, and maybe immediately drop all non-aware futures to prevent futurelock. The entire Tokio API would need to be wrapped to take into account cancellation tokens, as well as any other async library you would want to use. A lot of work, and you would need to do something if cancel-aware futures get dropped anyway. What a mess.

pshirshov 11mo ago

In my experience, almost any asynchronous runtime faced similar issue at some point (e.g. we helped to find and fix such issue in ZIO). It's hard to verify these protocols and very easy to write something fragile.