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

std::thread::JoinGuard (and scoped) are unsound because of reference cycles #24292

Closed
arielb1 opened this issue Apr 10, 2015 · 60 comments
Closed

std::thread::JoinGuard (and scoped) are unsound because of reference cycles #24292

arielb1 opened this issue Apr 10, 2015 · 60 comments
Labels

Comments

@arielb1
Copy link
Contributor

@arielb1 arielb1 commented Apr 10, 2015

You can use a reference cycle to leak a JoinGuard and then the scoped thread can access freed memory:

use std::thread;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering::SeqCst;
use std::rc::Rc;
use std::cell::RefCell;

struct Evil<'a> {
    link: RefCell<Option<Rc<Rc<Evil<'a>>>>>,
    arm: thread::JoinGuard<'a, ()>
}

// This reliably observes an immutable reference mutating.
fn bad(g: &AtomicBool, v: &u64) {
    let jg = thread::scoped(move || {
        while !g.load(SeqCst) { }; // Wait for the reference to change
        println!("{}", *v);        // Observe it
        g.store(false, SeqCst);    // Safely exit without crashing
    });
    let e = Rc::new(Evil {
        link: RefCell::new(None),
        arm: jg
    });
    *e.link.borrow_mut() = Some(Rc::new(e.clone())); // Create a cycle
}

#[inline(never)] // Prevent DSE
fn helper(v: &mut Result<u64, &'static str>) {
    let g = AtomicBool::new(false); // Used as a barrier to ensure reliable execution
    if let &mut Ok(ref v) = v { bad(&g, &v) };
    *v = Err("foo");

    g.store(true, SeqCst);
    while g.load(SeqCst) {};
}

fn main() {
    helper(&mut Ok(4));
}
@arielb1 arielb1 changed the title std::thread::JoinGuard is unsound because of reference cycles std::thread::JoinGuard (and scoped) are unsound because of reference cycles Apr 10, 2015
@sfackler
Copy link
Member

@sfackler sfackler commented Apr 10, 2015

Seems pretty bad, nominating.

@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Apr 10, 2015

Sigh. Good point! This seems very similar to the dropck rules, I suspect we can address it in a similar fashion to how we addressed Arena. But I have to have a bit more caffeine and try to work it through to make sure I'm correct. :)

cc @pnkfelix

UPDATE: Spelled out what I meant a bit more.

@arielb1
Copy link
Contributor Author

@arielb1 arielb1 commented Apr 10, 2015

@sfackler

I don't think this is so bad, because I can't really think of this happening accidentally. I think the best way to fix this would be to add a Leak OIBIT and make Rc/Arc require it. We may want to make it a by-default bound (like Sized), through, to prevent massive annotation burden.

@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Apr 10, 2015

triage: P-backcompat-libs (1.0)

I definitely think we need to address this for 1.0. I'm still not sure the best way to do it.

@rust-highfive rust-highfive added this to the 1.0 milestone Apr 10, 2015
aturon added a commit to aturon/rust that referenced this issue Apr 13, 2015
Issue rust-lang#24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)
aturon added a commit to aturon/rust that referenced this issue Apr 13, 2015
Issue rust-lang#24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

[breaking-change]
bors added a commit that referenced this issue Apr 13, 2015
Issue #24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

r? @alexcrichton
bors added a commit that referenced this issue Apr 13, 2015
Issue #24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

r? @alexcrichton
bors added a commit that referenced this issue Apr 14, 2015
Issue #24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

r? @alexcrichton
bors added a commit that referenced this issue Apr 14, 2015
Issue #24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

r? @alexcrichton
@pythonesque
Copy link
Contributor

@pythonesque pythonesque commented Apr 14, 2015

From a pragmatic perspective, I like the idea of ?Leak like ?Sized, but I'm not sure it's really justifiable since (1) it's not a language-level feature like Sized is, (2) we don't have builtin support for Leak, (3) it puts a lot of emphasis on Rc / Arc, since those are (IIRC) the only Rust constructs that can leak anything in the first place. Making Leak an OIBIT and opting out for JoinGuard seems sufficient to me; Arc already requires two trait bounds on its generic type parameter and I've never really seen anyone complain about it, so I suspect the annotation burden isn't too severe.

bors added a commit that referenced this issue Apr 14, 2015
Issue #24292 demonstrates that the `scoped` API as currently offered can
be memory-unsafe: the `JoinGuard` can be moved into a context that will
fail to execute destructors prior to the stack frame being popped (for
example, by creating an `Rc` cycle).

This commit reverts the APIs to `unstable` status while a long-term
solution is worked out.

(There are several possible ways to address this issue; it's not a
fundamental problem with the `scoped` idea, but rather an indication
that Rust doesn't currently provide a good way to ensure that
destructors are run within a particular stack frame.)

r? @alexcrichton
@joshtriplett
Copy link
Member

@joshtriplett joshtriplett commented Apr 15, 2015

This doesn't seem like innate unsoundness so much as a way to turn one form of unsoundness (the ability to cause a leak) into a worse form of unsoundness (the ability to cause a crash).

Have there been any previous efforts to eliminate the uncollectability of reference cycles?

@pnkfelix
Copy link
Member

@pnkfelix pnkfelix commented Apr 15, 2015

@joshtriplett raw memory leaks explicitly do not qualify as unsound, or at least, "unsafe", under Rust's use of the term, as explicitly discussed here:

http://doc.rust-lang.org/1.0.0-beta/reference.html#behaviour-not-considered-unsafe

There is further detailed discussion on an internals thread here:

http://internals.rust-lang.org/t/are-memory-leaks-considered-to-violate-memory-safety/1674

I point this out merely to establish that is not a gradient; it is a firm boolean condition, marking a line beyond which one risks undefined behavior.


In any case, a garbage collector is part of our future goals for Rust. That, when used, will allow cycles using Gc<T> to be reclaimed. But it won't resolve the problem in this issue, because garbage collectors reclaim storage at unpredictable times, and thus are not suitable for RAII guards.

@theemathas
Copy link

@theemathas theemathas commented Apr 15, 2015

@reem and @nikomatsakis proposed different solutions for solving this on IRC

@reem's solution: make Rc and Arc require 'static and specify that leaking memory for non-'static data is unsafe. (Optional: create unsafe variants for Rc and Arc that allow non-'static content) (logs)

@nikomatsakis's solution: create a new scoped() API that is tolerent to memory leaks (logs, prototype type signatures)

@reem
Copy link
Contributor

@reem reem commented Apr 15, 2015

I changed my mind about the "make Rc require 'static" solution after @nikomatsakis demonstrated compelling use cases for Rc of non-'static data and reminded me that it would break code like fn x<T>(...) -> Rc<T>.

@reem
Copy link
Contributor

@reem reem commented Apr 15, 2015

Note that a hypothetical Gc type would naturally require 'static, since the destructor can run at any time in the future. Rc is very similar in this sense, which is what inspired me to say we should just bound by 'static, but pragmatism might have to prevail here, since it's useful to Rc non-'static data.

@pnkfelix
Copy link
Member

@pnkfelix pnkfelix commented Apr 15, 2015

@reem (well there might be some other bound we come up with in the future that is more flexible than 'static for Gc's purposes, at least if the collector ends up being thread-local, as originally planned for @T ... something that encodes that the data does not outlive the task ...)

@arielb1
Copy link
Contributor Author

@arielb1 arielb1 commented Apr 15, 2015

Well making Rc require T: 'static would be really bad (as in, librustc would require a pretty deep refactoring).

I think we do want to introduce Leak someday, but that would be a breaking change. We may have to settle for an ST-like with_scope API.

@alexcrichton
Copy link
Member

@alexcrichton alexcrichton commented Apr 15, 2015

After thinking about this for a bit, I think that dealing with Rc/'static/Leak may be a bit of a red herring. Upon investigating, we actually have a few known sources of memory leaks today in the standard library and the compiler itself, all of which can lead to the same form of memory unsafety as exposed through Rc:

Each of these can definitely be classified as a bug in its own right, but it goes to show that a targeted solution at Rc/Arc may not totally fit the bill as it's often pretty convenient to just assume it's ok that destructors do not run.

@Gankra
Copy link
Contributor

@Gankra Gankra commented Apr 15, 2015

Yeah I'm a bit confused that std:🧵:JoinGuard is getting the blame here. It seems to me that the real problem is that Rc+RefCell enables writing mem::forget in safe code:

fn safe_forget<T>(data: T) {
    use std::rc::Rc;
    use std::cell::RefCell;

    struct Leak<T> {
        cycle: RefCell<Option<Rc<Rc<Leak<T>>>>>,
        data: T,
    }

    let e = Rc::new(Leak {
        cycle: RefCell::new(None),
        data: data,
    });
    *e.cycle.borrow_mut() = Some(Rc::new(e.clone())); // Create a cycle
}

fn main() {
    struct Foo<'a>(&'a mut i32);

    impl<'a> Drop for Foo<'a> {
        fn drop(&mut self) {
            *self.0 += 1;
        }
    }

    let mut data = 0;

    {
        let foo = Foo(&mut data);
        safe_forget(foo);
    }

    data += 1; // super make sure there's no outstanding borrows

    println!("{:?}", data); // prints 1, should print 2
}

Planned features like Vec::drain_range rely on the fact that the destructor of the iterator will be called before the parent Vec becomes accessible again for memory safety. (rough sketch: data in the middle of the Vec is moved out (becoming logically uninitialized) and elements are only back-shifted in the iterator's destructor).

@nicola-gigante
Copy link

@nicola-gigante nicola-gigante commented Sep 5, 2015

Hi all.
I don't know if I should open a separate issue about this but: the blog post about "Fearless Concurrency" in Rust mentions std:🧵:scoped, which is now deprecated as a result of this issue. Is it possible for someone to update the post? It is misleading for novices (like me).

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Sep 5, 2015

The API is coming back, so this is mostly a temporary state.

@nicola-gigante
Copy link

@nicola-gigante nicola-gigante commented Sep 5, 2015

Interesting! Can you point me to the place (if any) where people are discussing how to safely implement it?

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Sep 5, 2015

I can't find it right now, but there already were some working scoped threads designs posted on the RfC. Not sure what the timeline for bringing this back is.

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Sep 5, 2015

@bluss
Copy link
Member

@bluss bluss commented Sep 5, 2015

Crate crossbeam implements scoped threads.

huonw added a commit to huonw/simple_parallel that referenced this issue Oct 11, 2015
This converts `map`, `unordered_map`, `Pool::map` and
`Pool::unordered_map` to take a `crossbeam::Scope` argument, instead of
using the API of the old `thread::scoped` to return a guard (where the
destructor was required to run to ensure safety, something not
guaranteed). See rust-lang/rust#24292 for more
discussion of the issues with that API.
@antrik
Copy link
Contributor

@antrik antrik commented Oct 30, 2015

[...] the blog post about "Fearless Concurrency" in Rust mentions std:🧵:scoped, which is now deprecated as a result of this issue. Is it possible for someone to update the post? It is misleading for novices (like me).

The API is coming back, so this is mostly a temporary state.

Guys, do you realise how ridiculous this looks? Let's see:

"Hi, I read about this amazing scoped threads feature in Rust, but... I can't actually find it? What's the deal?"

"Oh, that... The thing is... [wiggle squirm] We actually dropped it like half a year ago... But it's just temporary! We have ideas for a replacement! In fact, if you spend half a day wading through discussions on issues and pull requests, perhaps you will ultimately stumble upon a crate far away called Crossbeam that indeed implements a viable replacement, stuffed in along with various other experimental features... And surely something along these lines will someday somehow end up in the standard library again in some form (even though nothing actually seems to be happening regarding that right now)... So you see, it's all temporary! No need to even mention it in existing literature!"

"Riiiiiight.... [slowly backing away] You know, I think I'll actually look for some other language... But you kids keep having fun!"

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Oct 30, 2015

You don't need crossbeam. This is an old thread, the state of scoped threads has moved past this since then.

https://crates.io/crates/scoped_threadpool gives you the functionality. That's it. It's in an external crate which works and is sound, there's no pressing need to include it in the standard library.

@steveklabnik
Copy link
Member

@steveklabnik steveklabnik commented Oct 30, 2015

@antrik please try to be a bit more substantial and less sarcastic with your criticism. This kind of comment isn't particularly welcome here.

@antrik
Copy link
Contributor

@antrik antrik commented Oct 31, 2015

You don't need crossbeam. [...] https://crates.io/crates/scoped_threadpool gives you the functionality.

Pools are nice; yet crossbeam::Scope seems a more straightforward replacement for the old functionality?...

Anyway, debating this actually serves to demonstrate the existing confusion and lack of communication regarding this situation; creating an unacceptable story for any newcomer. thread::scoped() is prominently featured in a major piece of Rust advocacy (the mentioned blog post), without any hint that it's gone, or where to look for replacements; nor am I aware of any other clear communication regarding this, that people looking for thread::scoped() are likely to find -- and nobody seems to be willing to even acknowledge that there is a communication problem...

If my post wasn't substantial in illustrating how this feels to people outside the bubble, I really don't know what would be.

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Oct 31, 2015

Sure, that's a straightforward thing to propose. You could have just done that. Your initial comment didn't complain about the communication error, it just ranted unconstructively without anything really helpful.

@alexcrichton could you update the blog post with a note about scoped threads being moved out of the standard library to scoped_threadpool and Crossbeam?

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Oct 31, 2015

@antrik
Copy link
Contributor

@antrik antrik commented Oct 31, 2015

Thanks.

I was frustrated that the last person who suggested updating the post was brushed off, so I tried to illustrate why this is serious problem... Sorry that I failed to make my motivation clear.

Note though that updating this blog post only solves part of the problem. The Why Rust? "report" for example only vaguely hints at changes; and there might be other mentions out there as well -- so it would be helpful to have some kind of "landing page" for people looking for thread::scoped(). (Ideally right in the standard library documentation where it used to live -- though I guess that might be technically impossible after it has been dropped for good?...)

@Manishearth
Copy link
Member

@Manishearth Manishearth commented Oct 31, 2015

We could add a dummy documentation page or something. Or just add a note in the thread module. Not sure what to do in this case, @steveklabnik

As for Why Rust I think the author was informed about this later, not sure if he changed anything.

@steveklabnik
Copy link
Member

@steveklabnik steveklabnik commented Oct 31, 2015

I'm not aware of anyone being brushed off, but I think editing the post is a great idea. Merged.

I wouldn't be a fan of adding dummy doc pages.

Sent from my iPhone

On Oct 30, 2015, at 20:50, Manish Goregaokar notifications@github.com wrote:

We could add a dummy documentation page or something. Or just add a note in the thread module. Not sure what to do in this case, @steveklabnik

As for Why Rust I think the author was informed about this later, not sure if he changed anything.


Reply to this email directly or view it on GitHub.

@jimblandy
Copy link
Contributor

@jimblandy jimblandy commented Oct 31, 2015

I'll update the Why Rust? report. (I used both scoped_threadpool and crossbeam::scope in my presentation at OSCON Amsterdam last week; they're great.)

(In the future, please feel free to contact me directly about these things, rather than just mention me obliquely!)

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

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.