Resolve unsound interaction between noalias and self-referential data (incl. generators, async fn)

View all comments

Self-referential generators violate LLVM's expectations for noalias due to the overlapping bounds of the interior references and the &mut self argument to the Generator::resume function.

Original issue description: async/await is possibly unsound -- I don't consider myself an authority here, so feel free to edit this top post with relevant information.

Current discussion happened in #63209

@comex

cc @rust-lang/lang @comex @rkruppe @RalfJung

@RalfJung

Responding to @RalfJung's post from #63209:

I think this is fundamental. Adding derive(Debug) makes the exact content of local variables at any yield point observable. Interesting optimizations based on mutable references being unique rely on the content mutable references point to to not be observable by any other alias.

Those hypothetical optimizations could be disabled in async fns across suspend points, though, couldn't they? I can't think of any case where this would force the compiler to pessimize all code because of the mere possibility of async being involved. Therefore, the question is whether those optimizations being performed on async fns specifically is more valuable than derive(Debug) is.

(By the way, I still want async fns to be able to derive(Clone), although that would obviously require pretty severe restrictions on the body of the function.)

@comex

I've not weighed in on this but I wanted to leave a few thoughts. Let me know if I'm confused about something.

First off, the conflict here is between the reference to a generator type G and some &mut reference T contained within the generator. What we don't have is two &mut A and &mut B references that overlap where neither A nor B gives any indication of arising from a generator.

This seems important: it means that, in principle, we ought to be able to understand that the &mut G reference is somehow special. It is certainly true that the self-referential nature of generators will require extending "stacked borrows" to be more flexible. But I think that generators are something we want to have, and it doesn't seem surprising that our aliasing rules may need to be extended to accommodate and understand them. (If though we have conflict between two random types &mut A and &mut B, that seems more worrisome, though it is likely still true that we want generators regardless.)

Also, of course, this problem isn't really specific to generators but is rather a pattern that emerges with any self-referential setup. Presently, safe Rust has no way to express self-referential structs (apart from generators), but I think it's something we would eventually like to support.

So let's posit that we find a version of stacked borrows that understands self-referential structs. Clearly, this doesn't mean we can add noalias to &mut references everywhere, we'll either have to extend LLVM or be selective in some other way (as e.g. @comex suggests here).

Does this all sound correct?

I think it's very important for generators to be able to print out their locals in a Debug implementation. With all of the effort that's gone into making async functions and futures zero-cost, it would be a shame if they became intrinsically less debuggable than a hand-written state machine.

Those hypothetical optimizations could be disabled in async fns across suspend points, though, couldn't they?

Possibly. I am not sure what the memory would look like though. Specifically...

First off, the conflict here is between the reference to a generator type G and some &mut reference T contained within the generator. What we don't have is two &mut A and &mut B references that overlap where neither A nor B gives any indication of arising from a generator.

... it is not enough, in general, if only "one side" of a conflict is informed. &mut T expects everyone else to respect its rules. If we allow &mut T and *mut T to conflict arbitrarily (because *mut T "knows" to expect conflicts), we get basically no optimizations.

Also, of course, this problem isn't really specific to generators but is rather a pattern that emerges with any self-referential setup. Presently, safe Rust has no way to express self-referential structs (apart from generators), but I think it's something we would eventually like to support.

Agreed. I do not have a concrete idea for how to do that, though.

I think it's very important for generators to be able to print out their locals in a Debug implementation. With all of the effort that's gone into making async functions and futures zero-cost, it would be a shame if they became intrinsically less debuggable than a hand-written state machine.

The question is, zero-cost when compared with what? Disabling optimizations to enable debug printing does have a cost, async fn then get optimized less than other functions.

And even if we rule out optimizations across yield points, we'd still require a non-trivial extension to Stacked Borrows to permit debug printing. That extension will likely have cost elsewhere, in terms of code getting optimized less.

In my view, the only solution one could really call zero-cost is the one that disallows debug printing.

I discovered a potentially problematic interaction between self-referential generators and the dereferenceable attribute: rust-lang/unsafe-code-guidelines#381.

@comex

@comex found an actual compilation result that can be explained by saying that dereferenceable is like having a "fake read" when the function starts, and that read is relevant for noalias concerns. (Another solution has been proposed in that thread but I think it has major issues, and discussion has not continued since I pointed those out.)

I feel like we should remove the dereferenceable from !Unpin mutable references. Right now that is the only clear way I see to ensure that Miri detects all the LLVM UB here. Hence I made a PR: #106180.

The RFC in rust-lang/rfcs#3467 should pave the way for resolving this issue properly.

Turns out just making !Unpin references not noalias is insufficient, one can still cause unintended UB with self-referential futures as discovered in rust-lang/miri#3780. Just like we had to make UnsafeCell block niches to discriminant reads causing aliasing trouble with the UnsafeCell contents, we also need to block niches for fields of a future that are references by other fields. IOW, async lowering should wrap such fields in UnsafePinned, and that type needs to block niches the same way UnsafeCell does.

Auto merge of rust-lang#129313 - RalfJung:coroutine-niches, r=compile…

Auto merge of #129313 - RalfJung:coroutine-niches, r=compiler-errors

(Related issue got moved to #159443)

Just like we had to make UnsafeCell block niches to discriminant reads causing aliasing trouble with the UnsafeCell contents, we also need to block niches for fields of a future that are references by other fields. IOW, async lowering should wrap such fields in UnsafePinned, and that type needs to block niches the same way UnsafeCell does.

Unfortunately, doing this turns out to have an extremely high performance cost, because after you do this, the aliasing model is no longer able to prove that references stored within the fields of a future that represent local variables do not alias the future itself.

Code like the following is accepted in Tree Borrows (and although Stacked Borrows complains, there's probably some way to create this sort of self-referential future there too):

#![feature(unsafe_pinned)]

use core::mem::transmute;
use core::pin::{Pin, UnsafePinned};
use core::ptr::null_mut;

#[repr(C)]
pub struct F<'a> {
    a: UnsafePinned<&'a mut [*mut usize; 1024]>,
    b: UnsafePinned<&'a mut [*mut usize; 1024]>
}

#[inline(never)]
pub fn poll<'a>(p: Pin<&'a mut F<'a>>) {
    let p = unsafe { p.get_unchecked_mut() };
    for i in 0..1024 {
        unsafe {(*p.a.get())[i] = (*p.b.get())[i]};
    }
}

pub fn main() {
    let mut a_storage = [null_mut() as *mut usize; 1024];
    let mut b_storage = [null_mut() as *mut usize; 1024];
    let mut c_storage = [null_mut() as *mut usize; 1024];
    a_storage[20] = &raw mut a_storage as *mut usize;
    a_storage[21] = &raw mut b_storage as *mut usize;
    b_storage[20] = &raw mut c_storage as *mut usize;
    b_storage[21] = &raw mut c_storage as *mut usize;
    let f = unsafe { Pin::new_unchecked(
        transmute::<*mut *mut usize, &mut F<'static>>(
        &raw mut a_storage[20] as *mut *mut usize)) };
    poll(f);
}

Here, F is supposed to represent the sort of code generated by lowering a future that looks like this (imagine that this is part of a larger future in which a and b were borrowed at some point, and thus require the UnsafePinned wrapper):

async fn MakeF(a: &mut [*mut usize; 1024], b: &mut [*mut usize; 1024]) {
    for i in 0..1024 { a[i] = b[i]; }
}

Due to the possibility that someone could have created this somewhat ridiculous future (in which the copy from b to a ends up overwriting the reference a mid-copy – you can also create a version that overwrites b), LLVM is not able to do any aliasing-based optimization at all in the loop; it reads the values of a and b from memory every time they are used, and does each loop iteration separately and in order (the only optimization applied to the code is a small amount of unrolling). Without the UnsafePinned, the code is much faster (it does a pointer comparison to determine whether a and b alias, and if it determines that they don't, does the equivalent of a memcpy). If this sort of code were written using narrower data types, it could easily become over 50× slower on CPU-bound code as a consequence of the inability to vectorize the loop and the need to reread the future's local variables from memory on every iteration (32× slower from the inability to vectorize, and an extra 1⅔× slower because each loop iteration now requires three reads and a write rather than one read and one write – on many modern processors, a read instruction is about twice as fast as a write instruction).

I suspect that it's possible to find a solution that does not lose the optimization hint that a mutable reference a (that's a local variable of a closure) is not stored within the memory *a that it points to: setting up this situation is clearly impossible in safe Rust (and undesirable in unsafe Rust). It would clearly be desirable to make this undefined behavior if possible, because the optimizations permitted by doing so are in general very valuable.

(Context: I've been working on my own aliasing model, and was using async { for i in 0...1024 { a[i] = b[i] }} as a test to ensure that it optimizes properly. In current Rust, this optimizes into a memcpy after first checking for the possibility that a and b are overlapping references (which neither Stacked Borrows nor Tree Borrows rules out). But I realized that this proposed solution to the existing unsoundness would make the optimization situation much worse, so thought it was worth mentioning in case we can find a solution with less performance impact.)

Navigation Menu

Repository navigation

Resolve unsound interaction between noalias and self-referential data (incl. generators, async fn) #63818

61 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Resolve unsound interaction between noalias and self-referential data (incl. generators, async fn) #63818

Description

Activity

Mark-Simulacrum commented on Aug 22, 2019

comex commented on Aug 22, 2019

nikomatsakis commented on Aug 22, 2019

Aaron1011 commented on Aug 22, 2019

RalfJung commented on Aug 23, 2019

61 remaining items

RalfJung commented on Dec 3, 2022

RalfJung commented on Dec 27, 2022

RalfJung commented on Aug 6, 2023

RalfJung commented on Aug 2, 2024

ais523 commented on Jul 16, 2026

saethlin commented on Jul 17, 2026

RalfJung commented on Jul 17, 2026

RalfJung commented on Jul 17, 2026

ais523 commented on Aug 14, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions