manishearth / rust-gc Goto Github PK

It seems that if I try to derive both Copy and Trace in a simple structure, I get this error:

The Copy trait was implemented on a type with a Drop implementation.

Erroneous code example:

#[derive(Copy)]
struct Foo; // error!

impl Drop for Foo {
    fn drop(&mut self) {
    }
}

Explicitly implementing both Drop and Copy trait on a type is currently
disallowed. This feature can make some sense in theory, but the current
implementation is incorrect and can lead to memory unsafety (see
issue #20126), so it has been disabled for now.

But from my understanding, a simple Copy structure such as:

#[derive(Debug, Clone, Copy, Trace)]
struct Sym(usize);

should be easy to implement, and the Trace implementation could be empty, right? Is there a proper way to do this? It's currently blocking doing type-safe string interning in Boa.

The fact that GcCell uses RefCell internally is currently part of the exposed API. In my opinion it should not be, and we should be free to change the backing representation without breaking consumers.

I started using this crate for my prolog interpreter (it's great, thank you for making it!).

I'd to make my interpreter do hash consing of the terms. Actually, I already made this change, but since there is no weak version of the Gc type, my interpreter now never collects anything. The reason is because the HashSet I use to store terms has a strong reference so once a term is inserted into my heap, it lives forever. Normally, when implementing hash-consing you store weak references in the hashset.

Basically, I want to write code like this:

type TermSet   = HashSet<WeakGc<Term>>;
pub struct Heap {
    terms:   TermSet,
}
// Check if `t` is already in the HashSet. If it is, then return
// a strong reference to it.
// if `t` is not in the HashSet, add it and return a strong reference to it.
fn insert_thing<A>(heap: &mut HashSet<Gc<A>>, t: A) -> Gc<A>
    where A: Trace,
          Gc<A>: Eq,
          Gc<A>: Hash
{
        let gc_thing = Gc::new(t);
        match heap.get(&gc_thing.downgrade()) {
            Some(gc) => return gc.upgrade().unwrap_or(gc_thing.clone()),
            None     => ()
        }
        heap.insert(gc_thing.downgrade());
        gc_thing
}
impl Heap {
    pub fn new() -> Self {
        Heap {
            terms:   HashSet::new(),
        }
    }

    pub fn insert_term(&mut self, t: Term) -> Gc<Term>
    {
        insert_thing(&mut self.terms, t)
    }
}

I tried something similar using Rc and Weak from std (even though cycles would cause issues), but I noticed Weak doesn't implement Hash and Eq so they can't be used as keys in a HashMap (and by extension, a HashSet). I don't know if that is due to the way dereferening Weak works or what. Perhaps I'll also need a custom collection type. Anyway, do you think that would be an issue here as well?

Would a weak version of Gc be hard to add? I haven't looked at the code yet, but if it's not too hard I might try adding one.

The first example in README.md is

#[macro_use]
extern crate gc_derive;
extern crate gc;

use gc::Gc;

#[derive(Trace, Finalize)]
struct Foo {
    x: Gc<Foo>,
    y: u8,
    // ...
}

// now, `Gc<Foo>` may be used

Though it has caused some confusion because how can you construct an instance of Foo (safely)? Perhaps the type of x should be Option<Gc<Foo>>?

This might be very difficult but I think it is worth considering how the GC can work with closures.

Currently moving a Gc into a closure causes problems because it can't be found in the trace. Also it will probably cause a panic on cleanup if the closure is stored in a GCed object because it will be rooted which will cause assert!(finalizer_safe()) to trigger.

I don't know if it would be possible to add support for tracing closures, I'm pretty sure this isn't possible in current Rust but maybe a compiler plugin could accomplish it. That being said some "tracing" traits aren't implemented for closure (Debug) but that might be for another reason.

There are other problems as well. Due to moving being so transparent there is no way to mark a "field" as #[unsafe_ignore_trace] if you want to capture a non-Gc containing object as well. This seems like it would make it impossible to choose the right "default".

That being said it would be very nice to be able to close over values and have them automatically traced if something could be worked out.

Can you wrap a trait object in a Gc? I would like to be able to write something like this. As a workaround, I am currently creating a Gc<Box<dyn MyTrait>>, but I don't really like the indirection. I am trying to use Gc the way you would use a Box or Rc with trait objects.

I've got a type Expr<C>, where C is a phantom type, that I'm trying to GC. The derive generates:

        unsafe impl<C: 'static + Context> ::gc::Trace for Expr<C>
        where
            Gc<Expr<C>>: ::gc::Trace,
            C: ::gc::Trace,
            Vec<Gc<Expr<C>>>: ::gc::Trace,
            Gc<Args<C>>: ::gc::Trace,
            Gc<Value<C>>: ::gc::Trace,
// ...

The C: ::gc::Trace bound is incorrect; I'd like there to be an attribute to disable it, for example:

#[derive(Finalize, Trace)]
#[gc_derive(phantom = "C")]
pub enum Expr<C: 'static + Context> {
// ...

I think this is a case of https://xkcd.com/1172/, because it used to work (while now I get a compiler stack overflow).

EDIT: Confirmed as a regression from gc_derive 0.3.1; setting the Cargo.toml version to =0.3.1 resolves this, as a short term fix.

The following can and should panic:

• Calling Gc::deref within force_collect
• Calling Gc::clone within force_collect
• Calling Gc::new within GcState::drop

The following would ideally panic, but might have to abort due to double panic, unspecified TLS drop order, or the inability to access TLS values during or after their destruction:

• Calling Gc::deref within GcState::drop
• Calling Gc::clone within GcState::drop
• Calling Gc::new within GcState::drop

The following currently panic, but could also be made to work:

• Calling force_collect within force_collect (would do nothing if nightly's RefCell::try_borrow_mut method indicates that a borrow is already outstanding)
• Calling Gc::new within force_collect

https://crates.io/crates/gc/0.1.0

The version in the repo is now 0.0.9.

Is there a way to ergonomically add impls for other crates? Possibly via optional deps on e.g. either, void, smallvec, etc.

The gc_plugin v0.0.4 on crates.io has the following error on nightly:

Compiling gc_plugin v0.0.4
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:29:21: 68:6 error: missing field: `is_unsafe` [E0063]
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:29     let trait_def = TraitDef {
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:30         span: span,
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:31         attributes: Vec::new(),
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:32         path: ty::Path::new(vec!("gc", "Trace")),
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:33         additional_bounds: Vec::new(),
/home/andrew/.cargo/registry/src/github.com-0a35038f75765ae4/gc_plugin-0.0.4/src/lib.rs:34         generics: ty::LifetimeBounds::empty(),

I was trying to derive Trace on an enumeration where one of the members is a Box<[T]> where T: Trace. This comes from a Vec::into_boxed_slice(), that allows reducing the memory footprint of a Vec.

The current implementation of Trace for Box<T>, requires for T to be both Trace and ?Sized.

The following compiles successfully and exhibits the same issue as rust-lang/rust#21160:

#![feature(custom_derive)]
#![feature(plugin)]

#![plugin(gc_plugin)]

extern crate gc;

#[derive(Trace)]
pub struct Foo(Bar);

pub struct Bar;

impl Bar { // not a real `Trace` impl
    fn trace(&self) {}
    fn root(&self) {}
    fn unroot(&self) {}
}

http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rust-ismm-2016.pdf

It's just a backend, and should be possible to seamlessly integrate.

Just a meta bug for now.

The sweep phase of the collector doesn't correctly update the pointer to point to the new boxes_end value.

The following code doesn't work

use gc::Trace;
use gc_derive::{Finalize, Trace};

#[derive(Trace, Finalize)]
struct X(Box<dyn Trace>);

This is because gc_derive doesn't support dyn keyword.

Right now, the only way to allocate is through the safe Gc::new() interface which allocates based on a generic type parameter. It would be nice to also have an unsafe Gc::alloc() interface or similar which allows allocating objects whose size isn't known at compile time.

I have written the code attached and got an exception:

exp(56347,0x7fff79809300) malloc: *** error for object 0x7fefa3c04dd0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
An unknown error occurred

It seems like there is another free happened. While some other issues talked about similar problems, but I am not sure what the problem truly is, or if the way I wrote the code is itself wrong.

Welcome any comments or guidance

#![feature(plugin, custom_derive)]

#![plugin(gc_plugin)]
extern crate gc;

#[macro_use]
use gc::*;

#[derive(Trace)]
struct Foo;

#[derive(Trace)]
struct Bar {
    foo : Foo,
}

impl Drop for Bar {
    fn drop(&mut self) {
        println!("Dropping");
    }
}

fn main() {
    let bar = Bar{ foo : Foo };

    let gced = Gc::new(bar);

}

When the thread unwinds, and the thread-local state variable is being destroyed, the GC_SWEEPING value isn't set - we should somehow make sure that it is set during that destruction, because otherwise an invalid pointer could be followed during the destruction sequence.

We also need to be sure that no collection can be triggered during the destruction of the thread local storage, because there's no way that would turn out well.

The following code exhibits two invalid reads and two invalid writes to a freed GcBox's root count (via root_inner and unroot_inner):

extern crate gc;

use gc::{Gc, GcCell, Trace};

struct Foo(GcCell<Option<Gc<Trace>>>);

unsafe impl Trace for Foo {
    unsafe fn trace(&self) {
        self.0.trace();
    }

    unsafe fn root(&self) {
        self.0.root();
    }

    unsafe fn unroot(&self) {
        self.0.unroot();
    }
}

impl Drop for Foo {
    fn drop(&mut self) {
        self.0.borrow().clone();
    }
}

fn main() {
    let a = Gc::new(Foo(GcCell::new(None)));
    let b = Gc::new(1);
    *a.0.borrow_mut() = Some(b);
}

This example depends on the order in which a and b are destroyed.

Like other pointers (Rc and friends) we should implement some pass-through traits.

Hi!
I was wondering if there is any reason why Display is not implemented for GcCellRef<T> and GcCellRefMut<T> if T: Display?

This is:

• BTreeMap
• BTreeSet
• BinaryHeap
• HashMap
• HashSet
• LinkedList
• VecDeque

I think {BTree,Hash}{Map,Set} should be the priority, but BinaryHeap and VecDeque would be nice.

It'd probably make some sense to make a custom GcLinkedList type instead of using Gc<LinkedList>.

I'm working on this at https://github.com/remexre/rust-gc/tree/container-impls, will PR if anyone wants me to (or after #58 is accepted; it's in my history since I need both for a project).

Printing a Gc with the {:#?} format string doesn't pretty print the string inside (see https://is.gd/OBukfz for a demo, uncommenting the fmt::Debug::fmt(...) gives the correct result

Trace is unsafe to implement, because it could be implemented incorrectly very easily. Trace should be an unsafe trait.

The current blocker on this is that it is impossible to generate unsafe trait impls in compiler plugins. I'm working on a patch for that, and will link the PR here when I file it against rust.

Are there any plans to continue this project? Or is work continuing in a fork? I admire the work done so far, but I am not sure if I can expect updates to this project 😐

I've got a big string, and I want to be able to have lots of references to slices of it. &str references don't work with Gc (or Rc or Arc), but it seems like it'd be fairly simple to implement it.

I think this'd just be:

struct GcStr {
    string: Gc<String>,
    start: usize,
    end: usize,
}

That said, I wanted to check here if there was a more efficient way that'd be worth putting in this crate.

Also, it'd make sense to do the same for CString/OsString (pending #58) and Vec.

GcCell should support try_borrow and try_borrow_mut.

extern crate gc;

use gc::{Gc, GcCell, Trace};

struct Foo(GcCell<Option<Gc<Trace>>>);

unsafe impl Trace for Foo {
    unsafe fn trace(&self) {
        self.0.trace();
    }

    unsafe fn root(&self) {
        self.0.root();
    }

    unsafe fn unroot(&self) {
        self.0.unroot();
    }
}

impl Drop for Foo {
    fn drop(&mut self) {
        self.0.borrow_mut();
    }
}

fn main() {
    let a = Gc::new(Foo(GcCell::new(None)));
    let b = Gc::new(1);
    *a.0.borrow_mut() = Some(b);
}

The call to GcCell::borrow_mut in Foo's destructor performs an invalid read-write by calling root, and GcCellRefMut's destructor performs another invalid read-write by calling unroot.

There have been multiple updates in this repository, and it would be nice to have them in crates.io.

As of rust-lang/rust#41064 there are some fairly large changes to the Shared and Unique types, which break rust-gc on nightly. Once the latest nightly includes these changes, we should update our use in the nightly version of the rust-gc code.

I got some code using this crate that panics with "Can't double-unroot a Gc". Debugging this will be a lot of work (it's an interpreter for a language and only some input programs trigger this), so I'd like to ask first: Is that assertion supposed to be an invariant (i.e. the crash is a bug in the Gc crate), or does it protect against incorrect usage (i.e. my calling code is violating some contract)?

Similar to std::cell::Ref::map.

We use a bunch of unstable features in rust-gc, most notably our support for custom derive.

As custom derive is coming to stable "soon":tm:, we should look into how difficult it would be to make a version of the core rust-gc library which doesn't require unstable features, and put the unstable features behind a feature flag.

Running the following in release mode causes a segfault:

extern crate gc;

use gc::Gc;
use std::{mem, usize};

fn main() {
    let a = Gc::new("abc".to_string());
    let a2 = a.clone();

    for _ in 0..usize::MAX {
        mem::forget(a.clone());
    }

    drop(a2);
    gc::force_collect();
    println!("{:?}", *a);
}

This is the same issue that was fixed in rust-lang/rust#27174. I have a fix incoming.

Have you considered using reference counts for early predictable cleanup, but then also the GC for cycle detection? I think that is similar to what python does under the hood.

That might make gc'd code behave more like normal rust, which may be desirable. Feel free to close this, I was just wondering if anyone has any thoughts on that.

#![feature(plugin, custom_derive)]

#![plugin(gc_plugin)]
extern crate gc;

use gc::{GcCell, Gc, force_collect};

#[derive(Trace)]
struct Droppable {
    thing: Gc<GcCell<u8>>
}

impl Drop for Droppable {
    fn drop(&mut self) {
        let mut thing = self.thing.borrow_mut();
        *thing = *thing + 1;
    }
}

#[test]
fn test_drop() {
    {
        let x = Gc::new(Droppable {thing: Gc::new(GcCell::new(0))});
    }   
    force_collect()
}

Here, the panic on GcBox::value is triggered because drop() is called while GC_SWEEPING is true.

We should probably make GC_SWEEPING a tristate, and set it to the third state when we need to run destructors (the mem::swap). In this stage, GC manipulations are allowed, however a sweep cannot be triggered.

Then again, that might not fix the problem, since it's possible to clone the GC in its destructor and pop it into TLS or something. Hmm.

cc @mystor

Hi guys,

I am interesting what is the LICENSE for rust-gc ?
Could you please add LICENSE file ??

Because the plugin infra doesn't let us derive unsafe functions (I will fix this)

Tracking issue to mark the places this needs to be fixed in-code

Hi,
at the moment drop for GcState deletes all nodes irrespective of whether or not they are rooted or connected to a root, which I think can lead to invalid references.

I came across this while trying to store a Gc<T> in a LocalKey, code like this terminates with
free(): invalid pointer

thread_local!(static EL: Gc<i64> = Gc::new(0));

fn main() {
    thread::spawn(|| {
        println!("{}", EL.with(|el| **el));
    } ).join().unwrap();
}

In this case the problem seems to be that EL is dropped after GC_STATE.

A related problem comes from leaking a Gc pointer, code like

let b = thread::spawn(|| {
    let leaked = Box::leak(Box::new(Gc::new(0)));
    let v = & **leaked;
    v
}).join().unwrap();

seems to result in a reference to freed memory.

In both cases the underlying problem seems to be that when GcState is dropped it cannot assume that there are no live references. In both cases just triggering a collection and leak any object with a live reference would solve the problem, but there might be better strategies.

Would there be significant downsides/dangers to having methods:

fn into_raw(gc: Gc<T>) -> *const T { ... }
unsafe fn from_raw(ptr: *const T) -> Gc<T> { ... }

analogously to Rc::into_raw, Rc::from_raw?

I want to store a Gc'd value across an FFI boundary (for use in a callback), while keeping it rooted; are there any huge dangers here versus doing the same with an Rc?

The alternative would be boxing up the Gc, then going Box<Gc<T>> -> *const Gc<T> and converting it back to a Box<Gc<T>> once I'm on the Rust side, I suppose. Either way, it'd be nice to have the {into,from}_raw functions.

RFC: 1681-macros-1.1.md
Implementation: rust-lang/rust#35957

i128 is now stable.

Hi, it would be really neat if some more arrays sizes than just the numbers 0 to 31 implemented Trace and Finalize. Would you be open to adding the next few powers of two as well?

(I actually only need [T; 32], having to wrap these in a newtype when the crate supports arrays up to 31 is oddly frustrating. And [T; 32], [T; 64] etc are probably more common than, say, [T; 29].)

Omitting fields from all of the trace methods is actually safe, due to the design of this garbage collector. It just means that any Gc<T>s which are hidden by these impls will not ever be unrooted, and thus will not be collected if they participate in a cycle.

As leaking is safe, these should be renamed from unsafe_ignore_trace to just ignore_trace and unsafe_empty_trace to just empty_trace.