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

Gc type does not implement Send or Sync #49

Open
Frawstcrabs opened this issue Feb 12, 2021 · 3 comments
Open

Gc type does not implement Send or Sync #49

Frawstcrabs opened this issue Feb 12, 2021 · 3 comments

Comments

@Frawstcrabs
Copy link

Frawstcrabs commented Feb 12, 2021

There's currently an issue where the Gc type requires its inner type be Send and Sync, but the type itself does not implement these traits. As a result, any type which contains Gc pointers cannot itself be held inside a Gc pointer (at least not without explicitly implementing the traits).

Example:

struct Example(usize, Option<Gc<Example>>)

fn main() {
    let ptr = Gc::new(Example(5, None));
}

This code would fail to typecheck, as the type NonNull<gc::GcBox<Example>> does not implement Send or Sync. Manually implementing the traits on the Example type allows this program to run.

Is it possible to have Gc itself implement Send and Sync, or are these workarounds required?

@jacob-hughes
Copy link
Contributor

jacob-hughes commented Feb 12, 2021

I can sympathise with this example. The transitive nature of the Send + Sync traits can make self-referential structs a pain. However, I'm reluctant at this stage to implement Send + Sync for Gc<T> because doing so would imply that it's safe to pass a Gc between threads. This isn't true (yet!). For now, I think you'll have to make do with manually implementing them for Gc<Example>. Sorry!

There's a similar problem that you might encounter with this change also: You'll likely have rustc complain that you need to use a Mutex or RwLock if you want interior mutability. This can be especially annoying when you have to pay the synchronisation penalty for something that's only used in a single-threaded context. In such cases, it's ok to implement Send and Sync for Cell<T> or RefCell<T> iff fields of those types are never dereferenced inside a Drop method.

@Frawstcrabs
Copy link
Author

In such cases, it's ok to implement Send and Sync for Cell<T> or RefCell<T> iff fields of those types are never dereferenced inside a Drop method.

Would you mind if I ask how one would go about adding this to a project? By default Rust raises an error about defining traits for types outside the current crate, and enabling the specialisation feature causes an issue with RefCell having both a positive and negative implementation of the traits. Is some other nightly feature required?

@jacob-hughes
Copy link
Contributor

Gah, sorry, I'd forgotten about the orphan rule. Yes this is a bit of a pain. You can use the newtype hack to get around this. See playground link for an example.

But I hadn't fully considered the implications on the ergonomics here, perhaps this motivates a GcCell / GcRefCell API. I need to think that through a little first though.

bors bot added a commit that referenced this issue Apr 9, 2021
54: Fix the concurrency semantics for `Gc<T>`. r=ltratt a=jacob-hughes

This makes two major changes to the API:

1. It removes the requirement that `T: Sync` for `Gc<T>`.
2. It makes `Gc<T> : Send + Sync` if `T: Send + Sync`, fixing the ergonomic problems raised in #49.

`Sync`'s purpose is to ensure that two threads can access the data in `T` in a thread-safe way. In other words, it implies that `T` has synchronisation guarantees. Originally, this was added as a constraint on `T` because any finalizer for `T` would run on a separate thread. However, it's now safe to remove this as a constraint because softdevteam/alloy#30 guarantees that a finalizer won't run early. This means that even without synchronized access, a race can't happen, because it's impossible for the finalizer to access `T`'s data while it's still in use by the mutator.

However, even though `Gc<T>` can now implement `Send` -- [thanks to multi-threaded collection support](softdevteam/alloy#31) -- `Gc<T>` still requires that `T: Send`, because `T` could be a type with shared ownership which aliases. This is necessary because off-thread finalization could mutate shared memory without synchronisation. An example using `Rc` makes this clear: 
```rust

struct Inner(Rc<usize>);

fn foo() {
    let rc = Rc::new(123);
    {
        let gc = Gc::new(Inner::new(Rc::clone(rc)));
    } 
    // Assume `gc` is dead here, so it will be finalized in parallel on a separate thread.
    // This means `Rc::drop` gets called which has the potential to race with
    // any `Rc` increment / decrement on the main thread.
    force_gc();
    
    // Might race with gc's finalizer
    bar(Rc::clone(rc));
}

```

Since finalizing any non-`Send` value can cause UB, we still disallow the construction of `Gc<T: !Send>` completely. This is certainly the most conservative approach. There are others:

- Not invoking finalizers for non-`Send` values. This is valid, since finalizers are not guaranteed to run. However, it's not exactly practical, it would mean that any `Gc<Rc<...>>` type structure would _always_ leak.
- Finalize `!Send` values on their mutator thread. This is really dangerous in the general case, because if any locks are held on the shared data by the mutator, this will deadlock (it's basically a variant of the async-signal-safe problem). However, if `T` is `!Send`, deadlocking is unlikely [although not impossible!], and could be an acceptable compromise. It's out of the scope of this PR, but it's something I've been playing around with.

Co-authored-by: Jake Hughes <[email protected]>
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