Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

miri accepts when embedded UnsafeCell in mutable Pin reference is changed #1860

Closed
godmar opened this issue Jul 26, 2021 · 14 comments
Closed

Comments

@godmar
Copy link

godmar commented Jul 26, 2021

It's my understanding that changing a memory location through a pointer that is an alias of a mutable reference is disallowed in Rust, and that miri could/should help detecting such scenarios.

Consider this playground reproduced here:

use std::ptr;
use std::pin::Pin;
use std::cell::UnsafeCell;

struct A {
    x:  UnsafeCell<isize>,
    ptr_x: *mut isize,
}

impl A {
    fn new(x: isize) -> Pin<Box<A>> {
        let mut a = Box::pin(A { x: UnsafeCell::new(x), 
                             ptr_x: ptr::null_mut() 
        });
        a.ptr_x = a.x.get_mut();
        a
    }

    fn change_x(self: &mut Pin<Box<A>>) {
        unsafe {
            self.ptr_x.write(0);
        }
    }

    #[inline(never)]
    fn wait_for_x(self: &mut Pin<Box<A>>) {
        while unsafe { *self.x.get() == 42 } {
            self.change_x();
        }
    }
}

fn main()
{
    let mut a = Box::new(A::new(42));
    println!("waiting for Godot");
    a.wait_for_x(); 
    println!("done");
}

Should miri flag UB in this code?

ps: compare to this similar playground that does not use Pin. Here, miri flags UB and the release/nightly compiler correctly exploits the UB by emitting an infinite loop.

@godmar
Copy link
Author

godmar commented Jul 26, 2021

Is this a duplicate of #1665?

@RalfJung
Copy link
Member

Note that your example also is flagged by Miri with -Zmiri-track-raw-pointers:

error: Undefined Behavior: no item granting write access to tag <3057> at alloc1393 found in borrow stack.
   --> /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    |
887 |         copy_nonoverlapping(&src as *const T, dst, 1);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access to tag <3057> at alloc1393 found in borrow stack.
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
            
    = note: inside `std::ptr::write::<isize>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    = note: inside `std::ptr::mut_ptr::<impl *mut isize>::write` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:1012:18
note: inside `A::change_x` at issue.rs:21:13
   --> issue.rs:21:13
    |
21  |             self.ptr_x.write(0);
    |             ^^^^^^^^^^^^^^^^^^^
note: inside `A::wait_for_x` at issue.rs:28:13
   --> issue.rs:28:13
    |
28  |             self.change_x();
    |             ^^^^^^^^^^^^^^^
note: inside `main` at issue.rs:37:5
   --> issue.rs:37:5
    |
37  |     a.wait_for_x(); 
    |     ^^^^^^^^^^^^^^

So I think this is a combination of rust-lang/unsafe-code-guidelines#125 (Box and Pin<Box> make a difference, since we currently do not recurse into fields of structs), and rust-lang/unsafe-code-guidelines#248 (by default we do not attempt to distinguish between raw pointers).

@godmar
Copy link
Author

godmar commented Jul 27, 2021

Naive question: given that wait_for_x takes a Box - is this code actually UB, or is this code ok? Or is it undecided whether this is/will be UB?

@RalfJung
Copy link
Member

wait_for_x takes an &mut Pin<Box<A>>.

Almost everything in this space is undecided. ;) But since it fails with -Zmiri-track-raw-pointers (and not due to integer-ptr-casts), I think this code is more likely to be UB than not.

@godmar
Copy link
Author

godmar commented Jul 28, 2021

Ok, what about if I replace the Box reference with a raw pointer, like in this playground.

use std::cell::UnsafeCell;
use std::ptr;

struct A {
    x: UnsafeCell<isize>,
    ptr_x: *mut isize,
}

impl A {
    fn new(x: isize) -> Box<A> {
        let mut a = Box::new(A {
            x: UnsafeCell::new(x),
            ptr_x: ptr::null_mut(),
        });
        a.ptr_x = a.x.get_mut();
        a
    }

    fn change_x(this: *mut A) {
        unsafe {
            (*this).ptr_x.write(0);
        }
    }

    #[inline(never)]
    fn wait_for_x(this: *mut A) {
        while unsafe { *(*this).x.get() == 42 } {
            A::change_x(this);
        }
    }
}

fn main() {
    let a = Box::into_raw(A::new(42));
    println!("waiting for Godot");
    A::wait_for_x(a);
    println!("done");
}

MIRI doesn't flag it by default, but does flag it when -Zmiri-track-raw-pointers is given.

Based on a previous post I read on Github (from you IIRC) I was under the assumption that I can basically write C-style unsafe code if I use raw pointers and do not mix mutable references and raw pointers (and follow C's aliasing rules.)

@RalfJung
Copy link
Member

Based on a previous post I read on Github (from you IIRC) I was under the assumption that I can basically write C-style unsafe code if I use raw pointers and do not mix mutable references and raw pointers (and follow C's aliasing rules.)

Yes, that is correct.
So you are probably mixing references/Boxes and raw pointers somewhere here. What is the error that Miri shows?

It is unfortunately rather easy to accidentally create a reference in Rust. For example, calling UnsafeCell::get creates a reference. You might have to use UnsafeCell::raw_get instead.

@godmar
Copy link
Author

godmar commented Jul 30, 2021

Based on a previous post I read on Github (from you IIRC) I was under the assumption that I can basically write C-style unsafe code if I use raw pointers and do not mix mutable references and raw pointers (and follow C's aliasing rules.)

Yes, that is correct.
So you are probably mixing references/Boxes and raw pointers somewhere here. What is the error that Miri shows?

    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `/home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri target/miri/x86_64-unknown-linux-gnu/debug/mutaliasraw`
waiting for Godot
error: Undefined Behavior: no item granting write access to tag <3034> at alloc1408 found in borrow stack.
   --> /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    |
887 |         copy_nonoverlapping(&src as *const T, dst, 1);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access to tag <3034> at alloc1408 found in borrow stack.
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
            
    = note: inside `std::ptr::write::<isize>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    = note: inside `std::ptr::mut_ptr::<impl *mut isize>::write` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:1012:18
note: inside `A::change_x` at src/bin/mutaliasraw.rs:21:13
   --> src/bin/mutaliasraw.rs:21:13
    |
21  |             (*this).ptr_x.write(0);
    |             ^^^^^^^^^^^^^^^^^^^^^^
note: inside `A::wait_for_x` at src/bin/mutaliasraw.rs:28:13
   --> src/bin/mutaliasraw.rs:28:13
    |
28  |             A::change_x(this);
    |             ^^^^^^^^^^^^^^^^^
note: inside `main` at src/bin/mutaliasraw.rs:36:5
   --> src/bin/mutaliasraw.rs:36:5
    |
36  |     A::wait_for_x(a);
    |     ^^^^^^^^^^^^^^^^
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:63:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside closure at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:48
    = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside `std::rt::lang_start_internal` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:20
    = note: inside `std::rt::lang_start::<()>` at /home/gback/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:62:5

error: aborting due to previous error

It is unfortunately rather easy to accidentally create a reference in Rust. For example, calling UnsafeCell::get creates a reference. You might have to use UnsafeCell::raw_get instead.

@RalfJung
Copy link
Member

RalfJung commented Jul 31, 2021

The problem is this line: Box::into_raw(A::new(42)). Here you are using a Box that aliases ptr_x. So you are mixing raw pointers and Box, and that violates the Box aliasing rules (which are basically the same as the &mut aliasing rules).

You basically must stop using the Box before creating ptr_x.

@RalfJung
Copy link
Member

Here is a version that truly uses only raw pointers, and this one is accepted even with -Zmiri-track-raw-pointers:

#![feature(unsafe_cell_raw_get)]
use std::cell::UnsafeCell;
use std::ptr;

struct A {
    x: isize,
    ptr_x: *mut isize,
}

impl A {
    fn new(x: isize) -> *mut A {
        let a = Box::new(A {
            x,
            ptr_x: ptr::null_mut(),
        });
        let a = Box::into_raw(a);
        unsafe { (*a).ptr_x = ptr::addr_of_mut!((*a).x); }
        a
    }

    fn change_x(this: *mut A) {
        unsafe {
            (*this).ptr_x.write(0);
        }
    }

    #[inline(never)]
    fn wait_for_x(this: *mut A) {
        while unsafe { (*this).x == 42 } {
            A::change_x(this);
        }
    }
}

fn main() {
    let a = A::new(42);
    println!("waiting for Godot");
    A::wait_for_x(a);
    println!("done");
}

@godmar
Copy link
Author

godmar commented Jul 31, 2021

Thanks, that makes sense, and that's good for my actual use case which doesn't have Boxes anyway.

Is there any receiver-style syntax in Rust for raw pointers or will I have to write most of the code using the A:: colon syntax?

@RalfJung
Copy link
Member

self: *mut Self is a thing in theory but I do not know its current status.

@godmar
Copy link
Author

godmar commented Jul 31, 2021

A side note (probably better suited for a discussion on IRLO or the user's forum). Rust is making it very hard to combine safe and (necessary) unsafe code in a way that makes one feel confident about the boundary between the two. Even "classic" data structures like an intrusive circular doubly-linked list appear to be unimplementable unless one stays exclusively in raw pointers, and in that case the boundary between the "raw pointer world" and (what I would really like to be the majority of the application) the safe world seems to be drifting in a way that favors the former and reduces the size of the latter, which is obviously not why we want to use Rust.

This diminishes the usefulness of Rust IMO if the resulting code is basically a C version built with raw pointers because it's so difficult to correctly cross the boundary into safe Rust. Rust has basically taken what is already a subtle subject (pointers) and squared its complexity. It's also a bit deceptive to present raw pointers, references, and smart pointers as pointer types in Rust when in fact writing code that crosses between the types is as difficult to write as it appears to be or at least to me.

@RalfJung
Copy link
Member

RalfJung commented Aug 1, 2021

Thanks for the feedback! The aliasing rules in Rust are not final yet, and concerns like this are indeed a major reason for that. Maybe there's a better model out there that is less fragile? More research is needed.

Intrusive circular doubly-linked lists are indeed a challenge in Rust. But with my verification lens on, I have to say that this is also a highly non-trivial data structure in terms of who is allow to perform which kinds of accesses to which memory when. So I am not surprised that this data structure is challenging -- you picked a really hard example! Many other data structures are a lot easier.

You might also be interested in rust-lang/rust#63818 -- solving this problem will possibly introduce a kind of Box and &mut that does not assert full uniqueness (similar to what UnsafeCell does with the read-only guarantee of shared references).

But yes, this is more of a UCG thing, as now we are talking about how the rules could be improved to make them easier to work with. There are already quite a few Stacked Borrows related discussions, and this comment is related to (at least) rust-lang/unsafe-code-guidelines#133 and rust-lang/unsafe-code-guidelines#148. I'll close the Miri issue now since Miri is working as intended and I think the concrete questions you had about Miri behavior were answered.

@RalfJung RalfJung closed this as completed Aug 1, 2021
@RalfJung
Copy link
Member

RalfJung commented Aug 1, 2021

Intrusive circular doubly-linked lists are indeed a challenge in Rust

To add to that point -- to my knowledge, even with Pin, it is not possible to give a fully safe API to an intrusive doubly-linked list (circular or not) that supports iteration. The best I know how to do is a list where you can pop off the head element.

(But if you want to discuss this further, maybe open a forum thread somewhere and ping me; this is not the right place.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants