manishearth / rust-gc Goto Github PK
View Code? Open in Web Editor NEWSimple tracing (mark and sweep) garbage collector for Rust
License: Mozilla Public License 2.0
Simple tracing (mark and sweep) garbage collector for Rust
License: Mozilla Public License 2.0
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 aDrop
implementation.Erroneous code example:
#[derive(Copy)] struct Foo; // error! impl Drop for Foo { fn drop(&mut self) { } }Explicitly implementing both
Drop
andCopy
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:
Gc::deref
within force_collect
Gc::clone
within force_collect
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:
Gc::deref
within GcState::drop
Gc::clone
within GcState::drop
Gc::new
within GcState::drop
The following currently panic, but could also be made to work:
force_collect
within force_collect
(would do nothing if nightly's RefCell::try_borrow_mut
method indicates that a borrow is already outstanding)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.
error[E0599]: no function or associated item named `new_unchecked` found for type `std::ptr::Shared<_>` in the current scope
--> /home/kevincox/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.3.2/src/lib.rs:87:37
|
87 | ptr_root: Cell::new(Shared::new_unchecked(ptr.as_ptr())),
| ^^^^^^^^^^^^^^^^^^^^^
error[E0599]: no function or associated item named `new_unchecked` found for type `std::ptr::Shared<_>` in the current scope
--> /home/kevincox/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.3.2/src/lib.rs:101:5
|
101 | Shared::new_unchecked(ptr)
| ^^^^^^^^^^^^^^^^^^^^^
error[E0599]: no function or associated item named `new_unchecked` found for type `std::ptr::Shared<_>` in the current scope
--> /home/kevincox/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.3.2/src/lib.rs:112:27
|
112 | self.ptr_root.set(Shared::new_unchecked(ptr));
| ^^^^^^^^^^^^^^^^^^^^^
error[E0599]: no function or associated item named `new_unchecked` found for type `std::ptr::Shared<_>` in the current scope
--> /home/kevincox/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.3.2/src/gc.rs:114:44
|
114 | st.boxes_start = Some(unsafe { Shared::new_unchecked(gcbox) });
| ^^^^^^^^^^^^^^^^^^^^^
error[E0599]: no function or associated item named `new_unchecked` found for type `std::ptr::Shared<_>` in the current scope
--> /home/kevincox/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.3.2/src/gc.rs:120:22
|
120 | unsafe { Shared::new_unchecked(gcbox) }
|
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:
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.
Compiling gc_plugin v0.0.6
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:37:13: 37:22 error: missing field `unify_fieldless_variants` in initializer of `syntax_ext::deriving::generic::MethodDef<'_>` [E0063]
/home/xyzl/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:37 MethodDef {
^~~~~~~~~
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:36:18: 67:10 note: in this expansion of vec! (defined in <std macros>)
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:37:13: 37:22 help: run `rustc --explain E0063` to see a detailed explanation
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:47:13: 47:22 error: missing field `unify_fieldless_variants` in initializer of `syntax_ext::deriving::generic::MethodDef<'_>` [E0063]
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:47 MethodDef {
^~~~~~~~~
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:36:18: 67:10 note: in this expansion of vec! (defined in <std macros>)
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:47:13: 47:22 help: run `rustc --explain E0063` to see a detailed explanation
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:57:13: 57:22 error: missing field `unify_fieldless_variants` in initializer of `syntax_ext::deriving::generic::MethodDef<'_>` [E0063]
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:57 MethodDef {
^~~~~~~~~
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:36:18: 67:10 note: in this expansion of vec! (defined in <std macros>)
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:57:13: 57:22 help: run `rustc --explain E0063` to see a detailed explanation
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:84:9: 84:23 error: this pattern has 1 field, but the corresponding variant has 2 fields [E0023]
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:84 Struct(ref fs) | EnumMatching(_, _, ref fs) => fs,
^~~~~~~~~~~~~~
/home/xyz/.cargo/registry/src/github.com-1ecc6299db9ec823/gc_plugin-0.0.6/src/lib.rs:84:9: 84:23 help: run `rustc --explain E0023` to see a detailed explanation
error: aborting due to 4 previous errors
error: Could not compile `gc_plugin`.
To learn more, run the command again with --verbose.
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
.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.