Repository: gluon-lang/gluon
Pull request #758 (2019-07-21 10:26:38)

fix: Ensure that threads are dropped when using child threads
Uses a very naive approach to determine if there still exists thread
references by scanning every thread. Could be faster but this fixes the
immediate issue.


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index d8d345ef..a7612229 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1073,6 +1073,7 @@ dependencies = [
  "serde_derive_state 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 1.0.39 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_state 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "slab 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)",
  "typed-arena 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
diff --git a/vm/Cargo.toml b/vm/Cargo.toml
index 0e652291..50ad44d9 100644
--- a/vm/Cargo.toml
+++ b/vm/Cargo.toml
@@ -30,6 +30,7 @@ ordered-float = "1"
 pretty = "0.5"
 quick-error = "1.1.0"
 smallvec = "0.6"
+slab = "0.4"
 typed-arena = "1.2.0"
 
 serde = { version = "1.0.0", optional = true }
diff --git a/vm/src/api/mod.rs b/vm/src/api/mod.rs
index 4938bb3f..a7f9f023 100644
--- a/vm/src/api/mod.rs
+++ b/vm/src/api/mod.rs
@@ -279,6 +279,15 @@ pub enum IO<T> {
     Exception(String),
 }
 
+impl<T> Into<StdResult<T, String>> for IO<T> {
+    fn into(self) -> StdResult<T, String> {
+        match self {
+            IO::Value(x) => Ok(x),
+            IO::Exception(x) => Err(x),
+        }
+    }
+}
+
 impl<T, E> From<StdResult<T, E>> for IO<T>
 where
     E: fmt::Display,
diff --git a/vm/src/gc.rs b/vm/src/gc.rs
index 4e138184..78813572 100644
--- a/vm/src/gc.rs
+++ b/vm/src/gc.rs
@@ -186,6 +186,19 @@ pub struct Gc {
     generation: Generation,
 }
 
+impl Drop for Gc {
+    fn drop(&mut self) {
+        if let Some(values) = self.values.take() {
+            mem::forget(values);
+            if std::thread::panicking() {
+                eprintln!("Gc values were not dropped explicitly. Leaking the allocatons!");
+            } else {
+                panic!("Gc values were not dropped explicitly. Leaking the allocatons!");
+            }
+        }
+    }
+}
+
 /// Trait which creates a typed pointer from a *mut () pointer.
 /// For `Sized` types this is just a cast but for unsized types some more metadata must be taken
 /// from the provided `D` value to make it initialize correctly.
@@ -348,12 +361,35 @@ impl GcHeader {
     }
 }
 
+pub struct OwnedPtr<T: ?Sized>(NonNull<T>);
+
+impl<T: ?Sized> Deref for OwnedPtr<T> {
+    type Target = T;
+    fn deref(&self) -> &T {
+        unsafe { self.0.as_ref() }
+    }
+}
+
+impl<T: ?Sized> DerefMut for OwnedPtr<T> {
+    fn deref_mut(&mut self) -> &mut T {
+        unsafe { self.0.as_mut() }
+    }
+}
+
+impl<T: ?Sized> From<OwnedPtr<T>> for GcPtr<T> {
+    /// Freezes `self` into a shared pointer
+    fn from(ptr: OwnedPtr<T>) -> GcPtr<T> {
+        GcPtr(ptr.0)
+    }
+}
+
 /// A pointer to a garbage collected value.
 ///
 /// It is only safe to access data through a `GcPtr` if the value is rooted (stored in a place
 /// where the garbage collector will find it during the mark phase).
 pub struct GcPtr<T: ?Sized>(NonNull<T>);
 
+// SAFETY Copied from `Arc`
 unsafe impl<T: ?Sized + Send + Sync> Send for GcPtr<T> {}
 unsafe impl<T: ?Sized + Send + Sync> Sync for GcPtr<T> {}
 
@@ -697,7 +733,7 @@ impl Gc {
     /// will occur.
     ///
     /// Unsafe since `roots` must be able to trace all accesible `GcPtr` values.
-    pub unsafe fn alloc_and_collect<R, D>(&mut self, roots: R, def: D) -> Result<GcPtr<D::Value>>
+    pub unsafe fn alloc_and_collect<R, D>(&mut self, roots: R, def: D) -> Result<OwnedPtr<D::Value>>
     where
         R: Trace + CollectScope,
         D: DataDef + Trace,
@@ -720,11 +756,19 @@ impl Gc {
         }
 
         self.check_collect(Scope1(roots, &def));
-        self.alloc(def)
+        self.alloc_owned(def)
     }
 
     /// Allocates a new object.
     pub fn alloc<D>(&mut self, def: D) -> Result<GcPtr<D::Value>>
+    where
+        D: DataDef,
+        D::Value: Sized + Any,
+    {
+        self.alloc_owned(def).map(GcPtr::from)
+    }
+
+    pub fn alloc_owned<D>(&mut self, def: D) -> Result<OwnedPtr<D::Value>>
     where
         D: DataDef,
         D::Value: Sized + Any,
@@ -745,7 +789,7 @@ impl Gc {
         D: DataDef,
         D::Value: Sized + Any,
     {
-        self.alloc_ignore_limit_(def.size(), def)
+        GcPtr::from(self.alloc_ignore_limit_(def.size(), def))
     }
 
     fn get_type_info(
@@ -802,7 +846,7 @@ impl Gc {
         }
     }
 
-    fn alloc_ignore_limit_<D>(&mut self, size: usize, def: D) -> GcPtr<D::Value>
+    fn alloc_ignore_limit_<D>(&mut self, size: usize, def: D) -> OwnedPtr<D::Value>
     where
         D: DataDef,
         D::Value: Sized + Any,
@@ -828,7 +872,7 @@ impl Gc {
             // that the pointer was initialized
             assert!(ret == p);
             self.values = Some(ptr);
-            let ptr = GcPtr(NonNull::new_unchecked(p));
+            let ptr = OwnedPtr(NonNull::new_unchecked(p));
             D::Value::unroot(&ptr);
             ptr
         }
@@ -921,6 +965,13 @@ impl Gc {
         self.values = first;
     }
 
+    // Drop all values.
+    //
+    // SAFETY: No `GcPtr` allocated from this Gc must be reachable after calling this
+    pub unsafe fn clear(&mut self) {
+        self.values = None;
+    }
+
     fn free(&mut self, header: Option<AllocPtr>) {
         if let Some(ref ptr) = header {
             self.allocated_memory -= ptr.size();
@@ -1026,6 +1077,8 @@ mod tests {
         let other: &mut GcHeader = gc.values.as_mut().unwrap();
         assert_eq!(&*ptr as *const _ as *const (), other.value());
         assert_eq!(header, other as *const _);
+
+        unsafe { gc.clear() }
     }
 
     #[test]
@@ -1054,6 +1107,8 @@ mod tests {
             gc.collect(&mut *stack);
         }
         assert_eq!(object_count(&gc), 0);
+
+        unsafe { gc.clear() }
     }
 
     #[derive(Trace)]
@@ -1085,5 +1140,7 @@ mod tests {
             gc.collect(());
         }
         assert_eq!(true, dropped.get());
+
+        unsafe { gc.clear() }
     }
 }
diff --git a/vm/src/serialization.rs b/vm/src/serialization.rs
index a55c1e4e..9199221f 100644
--- a/vm/src/serialization.rs
+++ b/vm/src/serialization.rs
@@ -15,12 +15,12 @@ use crate::base::symbol::{Symbol, Symbols};
 use crate::base::types::ArcType;
 
 use crate::array::Array;
-use crate::gc::{DataDef, GcPtr, WriteOnly};
-use crate::thread::{RootedThread, Thread, ThreadInternal};
+use crate::gc::{DataDef, GcPtr, OwnedPtr, WriteOnly};
+use crate::thread::{RootedThread, RootedValue, Thread, ThreadInternal};
 use crate::types::VmIndex;
 use crate::value::{
     BytecodeFunction, Callable, ClosureData, ExternFunction, PartialApplicationData,
-    PartialApplicationDataDef, Value, ValueRepr,
+    PartialApplicationDataDef, Value, ValueArray, ValueRepr,
 };
 use crate::Variants;
 
@@ -106,13 +106,17 @@ impl<T> From<DeSeed> for Seed<T> {
 
 pub mod gc {
     use super::*;
-    use crate::serde::de::{Deserialize, DeserializeState, Deserializer};
-    use crate::serde::ser::{Serialize, SerializeState, Serializer};
-
-    use crate::interner::InternedStr;
-    use crate::thread::ThreadInternal;
-    use crate::types::VmTag;
-    use crate::value::{DataStruct, GcStr, ValueArray};
+    use crate::serde::{
+        de::{Deserialize, DeserializeState, Deserializer},
+        ser::{Serialize, SerializeState, Serializer},
+    };
+
+    use crate::{
+        interner::InternedStr,
+        thread::ThreadInternal,
+        types::VmTag,
+        value::{DataStruct, GcStr, ValueArray},
+    };
 
     impl Serialize for GcStr {
         fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
@@ -125,7 +129,7 @@ pub mod gc {
 
     impl<'de, T> DeserializeState<'de, DeSeed> for crate::gc::Move<T>
     where
-        T: crate::gc::Trace,
+        T: crate::gc::Trace + PostDeserialize,
         T: DeserializeState<'de, DeSeed>,
     {
         fn deserialize_state<D>(seed: &mut DeSeed, deserializer: D) -> Result<Self, D::Error>
@@ -138,7 +142,7 @@ pub mod gc {
 
     impl<'de, T> DeserializeState<'de, DeSeed> for GcPtr<T>
     where
-        T: crate::gc::Trace + 'static,
+        T: crate::gc::Trace + PostDeserialize + 'static,
         T: DeserializeState<'de, DeSeed>,
     {
         fn deserialize_state<D>(seed: &mut DeSeed, deserializer: D) -> Result<Self, D::Error>
@@ -648,12 +652,51 @@ where
     )
 }
 
+pub trait PostDeserialize {
+    fn init(parent: &Thread, ptr: OwnedPtr<Self>) -> GcPtr<Self>;
+}
+
+impl PostDeserialize for PartialApplicationData {
+    fn init(_parent: &Thread, ptr: OwnedPtr<Self>) -> GcPtr<Self> {
+        ptr.into()
+    }
+}
+
+impl PostDeserialize for ValueArray {
+    fn init(_parent: &Thread, ptr: OwnedPtr<Self>) -> GcPtr<Self> {
+        ptr.into()
+    }
+}
+
+impl PostDeserialize for ExternFunction {
+    fn init(_parent: &Thread, ptr: OwnedPtr<Self>) -> GcPtr<Self> {
+        ptr.into()
+    }
+}
+
+impl PostDeserialize for BytecodeFunction {
+    fn init(_parent: &Thread, ptr: OwnedPtr<Self>) -> GcPtr<Self> {
+        ptr.into()
+    }
+}
+
+impl PostDeserialize for Thread {
+    fn init(parent: &Thread, mut ptr: OwnedPtr<Self>) -> GcPtr<Self> {
+        let mut parent_threads = parent.child_threads.write().unwrap();
+        let entry = parent_threads.vacant_entry();
+        ptr.thread_index = entry.key();
+        let ptr = ptr.into();
+        entry.insert((ptr, 0));
+        ptr
+    }
+}
+
 struct DataDefSeed<T>(PhantomData<T>);
 
 impl<'de, T> DeserializeSeed<'de> for crate::serialization::Seed<DataDefSeed<T>>
 where
     T: DataDef + 'static,
-    <T as DataDef>::Value: Sized,
+    <T as DataDef>::Value: Sized + PostDeserialize,
     T: DeserializeState<'de, DeSeed>,
 {
     type Value = GcPtr<<T as DataDef>::Value>;
@@ -677,7 +720,7 @@ where
         impl<'de, T> DeserializeState<'de, GcSeed<T>> for GcPtr<T::Value>
         where
             T: DataDef + 'static,
-            <T as DataDef>::Value: Sized,
+            <T as DataDef>::Value: PostDeserialize + Sized,
             T: DeserializeState<'de, DeSeed>,
         {
             fn deserialize_state<D>(seed: &mut GcSeed<T>, deserializer: D) -> Result<Self, D::Error>
@@ -685,12 +728,14 @@ where
                 D: Deserializer<'de>,
             {
                 let def = T::deserialize_state(&mut seed.state, deserializer)?;
-                seed.state
+                let ptr = seed
+                    .state
                     .thread
                     .context()
                     .gc
-                    .alloc(def)
-                    .map_err(D::Error::custom)
+                    .alloc_owned(def)
+                    .map_err(D::Error::custom)?;
+                Ok(T::Value::init(&seed.state.thread, ptr))
             }
         }
 
@@ -788,6 +833,24 @@ impl<'a> crate::serde::ser::SerializeState<crate::serialization::SeSeed> for Var
     }
 }
 
+impl<'de> DeserializeState<'de, DeSeed> for RootedValue<RootedThread> {
+    fn deserialize_state<D>(seed: &mut DeSeed, deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        eprintln!("before value ");
+        let value = Value::deserialize_state(seed, deserializer)?;
+        // TODO Prevent Value from being deserialized directly so we don't need to have this unsafe
+        eprintln!("after value ");
+        unsafe {
+            let x = Ok(seed.thread.root_value(Variants::new(&value)));
+
+            eprintln!("after value 2");
+            x
+        }
+    }
+}
+
 #[cfg(test)]
 mod tests {
     extern crate serde_json;
diff --git a/vm/src/stack.rs b/vm/src/stack.rs
index 2e870f53..716b859a 100644
--- a/vm/src/stack.rs
+++ b/vm/src/stack.rs
@@ -965,6 +965,8 @@ mod tests {
         }
         // Panic as it attempts to access past the lock
         StackFrame::frame(&mut stack, 1, State::Unknown);
+
+        unsafe { gc.clear() }
     }
 
     #[test]
@@ -984,6 +986,8 @@ mod tests {
         }
         // Panic as it attempts to pop a locked value
         stack.pop();
+
+        unsafe { gc.clear() }
     }
 
     #[test]
@@ -1010,6 +1014,8 @@ mod tests {
         stack.release_lock(lock);
         let mut frame = StackFrame::<State>::current(&mut stack);
         assert_eq!(frame.pop(), Value::from(Int(2)));
+
+        unsafe { gc.clear() }
     }
 
     #[test]
diff --git a/vm/src/thread.rs b/vm/src/thread.rs
index 6e6622f0..ec039f67 100644
--- a/vm/src/thread.rs
+++ b/vm/src/thread.rs
@@ -4,11 +4,13 @@ use std::{
     cmp::Ordering,
     fmt, mem,
     ops::{Add, Deref, DerefMut, Div, Mul, Sub},
+    ptr,
     result::Result as StdResult,
     string::String as StdString,
     sync::{
+        self,
         atomic::{self, AtomicBool},
-        Arc, Mutex, MutexGuard, RwLock, RwLockReadGuard, RwLockWriteGuard,
+        Arc, Mutex, MutexGuard, RwLock,
     },
     usize,
 };
@@ -28,25 +30,28 @@ use crate::base::{
     types::{self, Alias, ArcType},
 };
 
-use crate::api::{Getable, Pushable, ValueRef, VmType};
-use crate::compiler::UpvarInfo;
-use crate::gc::{DataDef, Gc, GcPtr, Generation, Move};
-use crate::interner::InternedStr;
-use crate::macros::MacroEnv;
-use crate::source_map::LocalIter;
-use crate::stack::{
-    ClosureState, ExternCallState, ExternState, Frame, Stack, StackFrame, StackState, State,
-};
-use crate::types::*;
-use crate::value::{
-    BytecodeFunction, Callable, ClosureData, ClosureDataDef, ClosureInitDef, Def, ExternFunction,
-    PartialApplicationDataDef, RecordDef, UninitializedRecord, UninitializedVariantDef, Userdata,
-    Value, ValueRepr, VariantDef,
+use crate::{
+    api::{Getable, Pushable, ValueRef, VmType},
+    compiler::UpvarInfo,
+    gc,
+    gc::{DataDef, Gc, GcPtr, Generation, Move},
+    interner::InternedStr,
+    macros::MacroEnv,
+    source_map::LocalIter,
+    stack::{
+        ClosureState, ExternCallState, ExternState, Frame, Stack, StackFrame, StackState, State,
+    },
+    types::*,
+    value::{
+        BytecodeFunction, Callable, ClosureData, ClosureDataDef, ClosureInitDef, Def,
+        ExternFunction, PartialApplicationDataDef, RecordDef, UninitializedRecord,
+        UninitializedVariantDef, Userdata, Value, ValueRepr,
+        ValueRepr::{Closure, Data, Float, Function, Int, PartialApplication, String},
+        VariantDef,
+    },
+    vm::{GlobalVmState, GlobalVmStateBuilder, ThreadSlab, VmEnv},
+    BoxFuture, Error, Result, Variants,
 };
-use crate::vm::{GlobalVmState, GlobalVmStateBuilder, VmEnv};
-use crate::{BoxFuture, Error, Result, Variants};
-
-use crate::value::ValueRepr::{Closure, Data, Float, Function, Int, PartialApplication, String};
 
 pub use crate::gc::Trace;
 
@@ -364,7 +369,7 @@ impl<'b> Roots<'b> {
         &self,
         gc: &mut Gc,
     ) -> Vec<(
-        RwLockReadGuard<Vec<GcPtr<Thread>>>,
+        sync::RwLockReadGuard<ThreadSlab>,
         MutexGuard<Context>,
         GcPtr<Thread>,
     )> {
@@ -372,7 +377,7 @@ impl<'b> Roots<'b> {
         let mut locks: Vec<(_, _, GcPtr<Thread>)> = Vec::new();
 
         let child_threads = self.vm.child_threads.read().unwrap();
-        stack.extend(child_threads.iter().cloned());
+        stack.extend(child_threads.iter().map(|(_, (t, _))| t.clone()));
 
         while let Some(thread_ptr) = stack.pop() {
             if locks.iter().any(|&(_, _, lock_thread)| {
@@ -383,7 +388,7 @@ impl<'b> Roots<'b> {
 
             let thread = mem::transmute::<&Thread, &'static Thread>(&*thread_ptr);
             let child_threads = thread.child_threads.read().unwrap();
-            stack.extend(child_threads.iter().cloned());
+            stack.extend(child_threads.iter().map(|(_, (t, _))| t.clone()));
 
             let context = thread.context.lock().unwrap();
 
@@ -424,16 +429,23 @@ pub struct Thread {
     // The parent of this thread, if it exists must live at least as long as this thread as this
     // thread can refer to any value in the parent thread
     #[cfg_attr(feature = "serde_derive", serde(state))]
-    parent: Option<RootedThread>,
+    parent: Option<GcPtr<Thread>>,
+
     #[cfg_attr(feature = "serde_derive", serde(state))]
     rooted_values: RwLock<Vec<Value>>,
+
     /// All threads which this thread have spawned in turn. Necessary as this thread needs to scan
     /// the roots of all its children as well since those may contain references to this threads
     /// garbage collected values
-    #[cfg_attr(feature = "serde_derive", serde(state))]
-    child_threads: RwLock<Vec<GcPtr<Thread>>>,
+    #[cfg_attr(feature = "serde_derive", serde(skip))]
+    pub(crate) child_threads: RwLock<ThreadSlab>,
+    // Default to an invalid index so we panic reliably if it is not filled in when deserializing
+    #[cfg_attr(feature = "serde_derive", serde(skip, default = "usize::max_value"))]
+    pub(crate) thread_index: usize,
+
     #[cfg_attr(feature = "serde_derive", serde(state))]
     context: Mutex<Context>,
+
     #[cfg_attr(feature = "serde_derive", serde(skip))]
     interrupt: AtomicBool,
 }
@@ -502,10 +514,7 @@ impl<'vm, 'value> Getable<'vm, 'value> for RootedThread {
 pub struct RootedThread {
     #[cfg_attr(feature = "serde_derive", serde(state))]
     thread: GcPtr<Thread>,
-    #[cfg_attr(
-        feature = "serde_derive",
-        serde(serialize_with = "crate::serialization::atomic_cell::serialize")
-    )]
+    #[cfg_attr(feature = "serde_derive", serde(skip))]
     rooted: AtomicCell<bool>,
 }
 
@@ -527,18 +536,39 @@ impl<'de> serde::de::DeserializeState<'de, crate::serialization::DeSeed> for Roo
         pub struct RootedThreadProxy {
             #[serde(state)]
             thread: GcPtr<Thread>,
-            #[serde(deserialize_with = "crate::serialization::atomic_cell::deserialize")]
-            rooted: AtomicCell<bool>,
         }
 
-        let RootedThreadProxy { thread, rooted } =
+        let RootedThreadProxy { thread } =
             RootedThreadProxy::deserialize_state(seed, deserializer)?;
-        let mut rooted_thread = RootedThread { thread, rooted };
-        if *rooted_thread.rooted.get_mut() {
-            rooted_thread.parent_threads().push(thread);
+
+        Ok(thread.root_thread())
+    }
+}
+
+impl Drop for Thread {
+    fn drop(&mut self) {
+        // The child threads need to refer to `self` so drop the gc (and thus the child threads)
+        // first so that `self` is valid while dropping them
+        let context = self.context.get_mut().unwrap_or_else(|err| {
+            // Ignore poisoning since we don't need to interact with the Gc values, only
+            // drop them
+            err.into_inner()
+        });
+        let mut gc_to_drop =
+            ::std::mem::replace(&mut context.gc, Gc::new(Generation::default(), 0));
+        // Make sure that the RefMut is dropped before the Gc itself as the RwLock is dropped
+        // when the Gc is dropped
+        drop(context);
+
+        // SAFETY GcPtr's may not leak outside of the `Thread` so we can safely clear it when
+        // droppting the thread
+        unsafe {
+            gc_to_drop.clear();
         }
 
-        Ok(rooted_thread)
+        let mut parent_threads = self.parent_threads();
+        debug_assert!(parent_threads[self.thread_index].1 == 0);
+        parent_threads.remove(self.thread_index);
     }
 }
 
@@ -546,23 +576,25 @@ impl Drop for RootedThread {
     fn drop(&mut self) {
         if *self.rooted.get_mut() {
             let is_empty = self.unroot_();
-            if self.parent.is_none() && is_empty {
+            if is_empty {
                 // The last RootedThread was dropped, there is no way to refer to the global state any
                 // longer so drop everything
-                let mut gc_ref = self
-                    .thread
-                    .global_state
-                    .gc
-                    .lock()
+                let mut gc_ref = self.thread.global_state.gc.lock().unwrap_or_else(|err| {
                     // Ignore poisoning since we don't need to interact with the Gc values, only
                     // drop them
-                    .unwrap_or_else(|err| err.into_inner());
-                let gc_to_drop =
+                    err.into_inner()
+                });
+                let mut gc_to_drop =
                     ::std::mem::replace(&mut *gc_ref, Gc::new(Generation::default(), 0));
                 // Make sure that the RefMut is dropped before the Gc itself as the RwLock is dropped
                 // when the Gc is dropped
                 drop(gc_ref);
-                drop(gc_to_drop);
+
+                // SAFETY GcPtr's may not leak outside of the `Thread` so we can safely clear it when
+                // droppting the thread
+                unsafe {
+                    gc_to_drop.clear();
+                }
             }
         }
     }
@@ -600,22 +632,36 @@ impl RootedThread {
     }
 
     pub fn with_global_state(mut global_state: GlobalVmState) -> RootedThread {
+        let context = Mutex::new(Context::new(
+            global_state.gc.get_mut().unwrap().new_child_gc(),
+        ));
+        let global_state = Arc::new(global_state);
         let thread = Thread {
             parent: None,
-            context: Mutex::new(Context::new(
-                global_state.gc.get_mut().unwrap().new_child_gc(),
-            )),
-            global_state: Arc::new(global_state),
+            context,
+            global_state: global_state.clone(),
             rooted_values: RwLock::new(Vec::new()),
-            child_threads: RwLock::new(Vec::new()),
+            child_threads: Default::default(),
             interrupt: AtomicBool::new(false),
+            thread_index: usize::max_value(),
         };
         let mut gc = Gc::new(Generation::default(), usize::MAX);
-        let vm = gc
-            .alloc(Move(thread))
-            .expect("Not enough memory to allocate thread")
-            .root_thread();
-        *vm.global_state.gc.lock().unwrap() = gc;
+        let mut ptr = gc
+            .alloc_owned(Move(thread))
+            .expect("Not enough memory to allocate thread");
+        *ptr.global_state.gc.lock().unwrap() = gc;
+
+        let ptr = {
+            let mut parent_threads = global_state.generation_0_threads.write().unwrap();
+            let entry = parent_threads.vacant_entry();
+            ptr.thread_index = entry.key();
+            let ptr = ptr.into();
+            entry.insert((ptr, 0));
+            ptr
+        };
+
+        let vm = ptr.root_thread();
+
         // Enter the top level scope
         {
             let mut context = vm.context.lock().unwrap();
@@ -647,19 +693,40 @@ impl RootedThread {
         let mut parent_threads_lock = self.parent_threads();
         assert!(!self.rooted.load());
         self.rooted.store(true);
-        parent_threads_lock.push(self.thread);
+        parent_threads_lock[self.thread_index].1 += 1;
     }
 
     fn unroot_(&self) -> bool {
         assert!(self.rooted.load());
-        let mut roots = self.parent_threads();
-        self.rooted.store(false);
-        let index = roots
-            .iter()
-            .position(|p| &**p as *const Thread == &*self.thread as *const Thread)
-            .expect("VM ptr");
-        roots.swap_remove(index);
-        roots.is_empty()
+        let root_count = {
+            let mut roots = self.parent_threads();
+            self.rooted.store(false);
+            let (_, root_count) = &mut roots[self.thread_index];
+            assert!(*root_count > 0);
+            *root_count -= 1;
+            *root_count
+        };
+
+        if root_count == 0 {
+            fn is_unrooted(thread: &Thread) -> bool {
+                let child_threads = thread.child_threads.read().unwrap();
+                child_threads
+                    .iter()
+                    .all(|(_, (t, count))| *count == 0 && is_unrooted(t))
+            }
+
+            let mut top = &**self;
+            while let Some(thread) = &top.parent {
+                top = thread;
+            }
+
+            let child_threads = top.parent_threads_read();
+            child_threads
+                .iter()
+                .all(|(_, (t, count))| *count == 0 && is_unrooted(t))
+        } else {
+            false
+        }
     }
 }
 
@@ -669,18 +736,28 @@ impl Thread {
     pub fn new_thread(&self) -> Result<RootedThread> {
         let vm = Thread {
             global_state: self.global_state.clone(),
-            parent: Some(self.root_thread()),
+            parent: Some(unsafe { GcPtr::from_raw(self) }),
             context: Mutex::new(Context::new(self.owned_context().gc.new_child_gc())),
             rooted_values: RwLock::new(Vec::new()),
-            child_threads: RwLock::new(Vec::new()),
+            child_threads: Default::default(),
             interrupt: AtomicBool::new(false),
+            thread_index: usize::max_value(),
         };
         // Enter the top level scope
         {
             let mut context = vm.owned_context();
             StackFrame::<State>::frame(&mut context.stack, 0, State::Unknown);
         }
-        let ptr = self.context().alloc(Move(vm))?;
+        let mut ptr = self.context().alloc_owned(Move(vm))?;
+
+        let ptr = {
+            let mut parent_threads = self.child_threads.write().unwrap();
+            let entry = parent_threads.vacant_entry();
+            ptr.thread_index = entry.key();
+            let ptr = ptr.into();
+            entry.insert((ptr, 0));
+            ptr
+        };
 
         Ok(ptr.root_thread())
     }
@@ -690,7 +767,7 @@ impl Thread {
     pub fn root_thread(&self) -> RootedThread {
         unsafe {
             let thread = GcPtr::from_raw(self);
-            self.parent_threads().push(thread);
+            self.parent_threads()[self.thread_index].1 += 1;
             RootedThread {
                 thread,
                 rooted: AtomicCell::new(true),
@@ -841,7 +918,7 @@ impl Thread {
     }
 
     /// Locks and retrieves the global environment of the vm
-    pub fn get_env<'b>(&'b self) -> RwLockReadGuard<'b, VmEnv> {
+    pub fn get_env<'b>(&'b self) -> sync::RwLockReadGuard<'b, VmEnv> {
         self.global_env().get_env()
     }
 
@@ -853,7 +930,12 @@ impl Thread {
     /// Runs a garbage collection.
     pub fn collect(&self) {
         let mut context = self.owned_context();
-        self.with_roots(&mut context, |gc, roots| unsafe {
+        self.collect_with_context(&mut context);
+    }
+
+    fn collect_with_context(&self, context: &mut OwnedContext) {
+        debug_assert!(ptr::eq::<Thread>(self, context.thread));
+        self.with_roots(context, |gc, roots| unsafe {
             gc.collect(roots);
         })
     }
@@ -910,13 +992,20 @@ impl Thread {
         self.child_threads.read().unwrap().trace(gc);
     }
 
-    fn parent_threads(&self) -> RwLockWriteGuard<Vec<GcPtr<Thread>>> {
+    pub(crate) fn parent_threads(&self) -> sync::RwLockWriteGuard<ThreadSlab> {
         match self.parent {
             Some(ref parent) => parent.child_threads.write().unwrap(),
             None => self.global_state.generation_0_threads.write().unwrap(),
         }
     }
 
+    fn parent_threads_read(&self) -> sync::RwLockReadGuard<ThreadSlab> {
+        match self.parent {
+            Some(ref parent) => parent.child_threads.read().unwrap(),
+            None => self.global_state.generation_0_threads.read().unwrap(),
+        }
+    }
+
     fn with_roots<F, R>(&self, context: &mut Context, f: F) -> R
     where
         F: for<'b> FnOnce(&mut Gc, Roots<'b>) -> R,
@@ -1529,6 +1618,14 @@ impl Context {
 
 impl<'b> OwnedContext<'b> {
     pub fn alloc<D>(&mut self, data: D) -> Result<GcPtr<D::Value>>
+    where
+        D: DataDef + Trace,
+        D::Value: Sized + Any,
+    {
+        self.alloc_owned(data).map(GcPtr::from)
+    }
+
+    pub fn alloc_owned<D>(&mut self, data: D) -> Result<gc::OwnedPtr<D::Value>>
     where
         D: DataDef + Trace,
         D::Value: Sized + Any,
@@ -1539,7 +1636,7 @@ impl<'b> OwnedContext<'b> {
             ref stack,
             ..
         } = **self;
-        alloc(gc, thread, &stack, data)
+        alloc_owned(gc, thread, &stack, data)
     }
 
     pub fn debug_info(&self) -> DebugInfo {
@@ -1567,6 +1664,19 @@ pub(crate) fn alloc<D>(
     stack: &Stack,
     def: D,
 ) -> Result<GcPtr<D::Value>>
+where
+    D: DataDef + Trace,
+    D::Value: Sized + Any,
+{
+    alloc_owned(gc, thread, stack, def).map(GcPtr::from)
+}
+
+pub(crate) fn alloc_owned<D>(
+    gc: &mut Gc,
+    thread: &Thread,
+    stack: &Stack,
+    def: D,
+) -> Result<gc::OwnedPtr<D::Value>>
 where
     D: DataDef + Trace,
     D::Value: Sized + Any,
@@ -2017,20 +2127,16 @@ impl<'b> ExecuteContext<'b> {
                             ValueRepr::Tag(0)
                         } else {
                             let fields = &self.stack[self.stack.len() - args..];
-                            unsafe {
-                                let roots = Roots {
-                                    vm: GcPtr::from_raw(self.thread),
-                                    stack: &self.stack.stack,
-                                };
-                                let field_names = &function.records[record as usize];
-                                Data(self.gc.alloc_and_collect(
-                                    roots,
-                                    RecordDef {
-                                        elems: fields,
-                                        fields: field_names,
-                                    },
-                                )?)
-                            }
+                            let field_names = &function.records[record as usize];
+                            Data(alloc(
+                                self.gc,
+                                self.thread,
+                                &self.stack.stack,
+                                RecordDef {
+                                    elems: fields,
+                                    fields: field_names,
+                                },
+                            )?)
                         }
                     };
                     self.stack.pop_many(args);
@@ -2059,20 +2165,16 @@ impl<'b> ExecuteContext<'b> {
                         if args == 0 {
                             ValueRepr::Tag(0)
                         } else {
-                            unsafe {
-                                let roots = Roots {
-                                    vm: GcPtr::from_raw(self.thread),
-                                    stack: &self.stack.stack,
-                                };
-                                let field_names = &function.records[record as usize];
-                                Data(self.gc.alloc_and_collect(
-                                    roots,
-                                    UninitializedRecord {
-                                        elems: args as usize,
-                                        fields: field_names,
-                                    },
-                                )?)
-                            }
+                            let field_names = &function.records[record as usize];
+                            Data(alloc(
+                                &mut self.gc,
+                                self.thread,
+                                &self.stack.stack,
+                                UninitializedRecord {
+                                    elems: args as usize,
+                                    fields: field_names,
+                                },
+                            )?)
                         }
                     };
                     self.stack.push(d);
diff --git a/vm/src/value.rs b/vm/src/value.rs
index ef254c24..dd16230d 100644
--- a/vm/src/value.rs
+++ b/vm/src/value.rs
@@ -1637,6 +1637,8 @@ mod tests {
             ),
             "Cons 0 (Cons 123 Nil)"
         );
+
+        unsafe { gc.clear() }
     }
 
     #[test]
@@ -1660,6 +1662,8 @@ mod tests {
             ),
             "[1, 2, 3]"
         );
+
+        unsafe { gc.clear() }
     }
 
     #[test]
diff --git a/vm/src/vm.rs b/vm/src/vm.rs
index 5de96614..c705b21d 100644
--- a/vm/src/vm.rs
+++ b/vm/src/vm.rs
@@ -37,6 +37,16 @@ pub use crate::{
     value::Userdata,
 };
 
+pub(crate) type ThreadSlab = slab::Slab<(GcPtr<Thread>, usize)>;
+
+unsafe impl Trace for ThreadSlab {
+    impl_trace! { self, gc,
+        for x in self {
+            mark(&x, gc);
+        }
+    }
+}
+
 fn new_bytecode(
     env: &VmEnv,
     interner: &mut Interner,
@@ -175,8 +185,8 @@ pub struct GlobalVmState {
     // List of all generation 0 threads (ie, threads allocated by the global gc). when doing a
     // generation 0 sweep these threads are scanned as generation 0 values may be refered to by any
     // thread
-    #[cfg_attr(feature = "serde_derive", serde(state))]
-    pub generation_0_threads: RwLock<Vec<GcPtr<Thread>>>,
+    #[cfg_attr(feature = "serde_derive", serde(skip))]
+    pub generation_0_threads: RwLock<ThreadSlab>,
 
     #[cfg_attr(feature = "serde_derive", serde(skip))]
     debug_level: RwLock<DebugLevel>,
@@ -427,7 +437,7 @@ impl GlobalVmStateBuilder {
             gc: Mutex::new(Gc::new(Generation::default(), usize::MAX)),
             macros: MacroEnv::new(),
             type_cache: TypeCache::default(),
-            generation_0_threads: RwLock::new(Vec::new()),
+            generation_0_threads: Default::default(),
             debug_level: RwLock::new(DebugLevel::default()),
         };
         vm.add_types().unwrap();


Test patch:
diff --git a/tests/api.rs b/tests/api.rs
index c9be6d4e..d90c2544 100644
--- a/tests/api.rs
+++ b/tests/api.rs
@@ -541,7 +541,7 @@ impl VmType for NoisyDrop {
 }
 
 #[test]
-fn cyclic_userdata() {
+fn cyclic_userdata_simple() {
     let _ = ::env_logger::try_init();
 
     #[derive(Debug, Userdata, Trace)]
@@ -639,3 +639,69 @@ fn cyclic_userdata_mutable() {
         "The virtual machine and its values were not dropped"
     );
 }
+
+#[test]
+fn child_vm_do_not_cause_undroppable_cycle_normal_drop_order() {
+    let _ = ::env_logger::try_init();
+
+    let mut noisy_drop = NoisyDrop::default();
+    {
+        let vm = make_vm();
+        let child_vm = vm.new_thread().unwrap();
+
+        vm.register_type::<NoisyDrop>("NoisyDrop", &[])
+            .unwrap_or_else(|_| panic!("Could not add type"));
+
+        Compiler::new()
+            .load_script(&vm, "function", "\\x -> ()")
+            .unwrap();
+
+        {
+            let mut f: FunctionRef<fn(NoisyDrop)> = vm
+                .get_global("function")
+                .unwrap_or_else(|err| panic!("{}", err));
+            f.call(noisy_drop.clone()).unwrap();
+        }
+
+        drop(child_vm);
+        drop(vm);
+    }
+
+    assert!(
+        Arc::get_mut(&mut noisy_drop.0).is_some(),
+        "The virtual machine and its values were not dropped"
+    );
+}
+
+#[test]
+fn child_vm_do_not_cause_undroppable_cycle_reverse_drop_order() {
+    let _ = ::env_logger::try_init();
+
+    let mut noisy_drop = NoisyDrop::default();
+    {
+        let vm = make_vm();
+        let child_vm = vm.new_thread().unwrap();
+
+        vm.register_type::<NoisyDrop>("NoisyDrop", &[])
+            .unwrap_or_else(|_| panic!("Could not add type"));
+
+        Compiler::new()
+            .load_script(&vm, "function", "\\x -> ()")
+            .unwrap();
+
+        {
+            let mut f: FunctionRef<fn(NoisyDrop)> = vm
+                .get_global("function")
+                .unwrap_or_else(|err| panic!("{}", err));
+            f.call(noisy_drop.clone()).unwrap();
+        }
+
+        drop(vm);
+        drop(child_vm);
+    }
+
+    assert!(
+        Arc::get_mut(&mut noisy_drop.0).is_some(),
+        "The virtual machine and its values were not dropped"
+    );
+}
diff --git a/tests/io.rs b/tests/io.rs
index f25f2140..3540b4f3 100644
--- a/tests/io.rs
+++ b/tests/io.rs
@@ -1,13 +1,15 @@
-extern crate env_logger;
-extern crate gluon;
-extern crate tempfile;
-extern crate tokio;
-
-use gluon::vm::api::{Hole, OpaqueValue, OwnedFunction, ValueRef, IO};
-use gluon::{new_vm, Compiler, Thread};
 use std::fs;
+
 use tempfile::NamedTempFile;
 
+use gluon::{
+    new_vm,
+    vm::api::{Hole, OpaqueValue, OwnedFunction, ValueRef, IO},
+    Compiler, Thread,
+};
+
+use tokio::runtime::current_thread::Runtime;
+
 #[macro_use]
 mod support;
 
@@ -164,7 +166,7 @@ fn spawn_on_twice() {
         action
     "#;
 
-    let mut runtime = self::tokio::runtime::Runtime::new().unwrap();
+    let mut runtime = Runtime::new().unwrap();
     let vm = make_vm();
     let (result, _) = runtime
         .block_on(
@@ -210,7 +212,7 @@ fn spawn_on_runexpr() {
         wrap x.value
     "#;
 
-    let mut runtime = self::tokio::runtime::Runtime::new().unwrap();
+    let mut runtime = Runtime::new().unwrap();
     let vm = make_vm();
     let (result, _) = runtime
         .block_on(
@@ -249,7 +251,7 @@ fn spawn_on_do_action_twice() {
         wrap (load counter)
     "#;
 
-    let mut runtime = self::tokio::runtime::Runtime::new().unwrap();
+    let mut runtime = Runtime::new().unwrap();
     let vm = make_vm();
     let (result, _) = runtime
         .block_on(
@@ -282,7 +284,7 @@ fn spawn_on_force_action_twice() {
         wrap (load counter)
     "#;
 
-    let mut runtime = self::tokio::runtime::Runtime::new().unwrap();
+    let mut runtime = Runtime::new().unwrap();
     let vm = make_vm();
     let (result, _) = runtime
         .block_on(
@@ -314,7 +316,7 @@ fn spawn_on_runexpr_in_catch() {
         (io.catch action wrap >>= io.println) *> wrap "123"
     "#;
 
-    let mut runtime = self::tokio::runtime::Runtime::new().unwrap();
+    let mut runtime = Runtime::new().unwrap();
     let vm = make_vm();
     let (result, _) = runtime
         .block_on(
diff --git a/tests/serialization.rs b/tests/serialization.rs
index bf119e0e..2dc296df 100644
--- a/tests/serialization.rs
+++ b/tests/serialization.rs
@@ -7,18 +7,22 @@ extern crate walkdir;
 
 extern crate gluon;
 
-use std::fs::File;
-use std::io::Read;
+use std::{fs::File, io::Read};
 
 use futures::Future;
 
 use crate::serde::ser::SerializeState;
 
-use gluon::vm::api::{Hole, OpaqueValue};
-use gluon::vm::serialization::{DeSeed, SeSeed};
-use gluon::vm::thread::{RootedThread, RootedValue, Thread, ThreadInternal};
-use gluon::vm::Variants;
-use gluon::{new_vm, Compiler};
+use gluon::{
+    new_vm,
+    vm::{
+        api::{Hole, OpaqueValue, IO},
+        serialization::{DeSeed, SeSeed},
+        thread::{RootedThread, RootedValue, Thread},
+        Variants,
+    },
+    Compiler,
+};
 
 fn serialize_value(value: Variants) {
     let mut buffer = Vec::new();
@@ -30,10 +34,10 @@ fn serialize_value(value: Variants) {
     String::from_utf8(buffer).unwrap();
 }
 
-fn roundtrip<'t>(
-    thread: &'t RootedThread,
+fn roundtrip(
+    thread: &RootedThread,
     value: &OpaqueValue<&Thread, Hole>,
-) -> RootedValue<&'t Thread> {
+) -> RootedValue<RootedThread> {
     use std::str::from_utf8;
 
     let value = value.get_variant();
@@ -51,7 +55,6 @@ fn roundtrip<'t>(
     let deserialize_value = DeSeed::new(thread)
         .deserialize(&mut de)
         .unwrap_or_else(|err| panic!("{}\n{}", err, buffer));
-    let deserialize_value = thread.root_value(unsafe { Variants::new(&deserialize_value) });
 
     // We can't compare functions for equality so serialize again and check that for equality with
     // the first serialization
@@ -61,6 +64,7 @@ fn roundtrip<'t>(
         let ser_state = SeSeed::new();
         value.serialize_state(&mut ser, &ser_state).unwrap();
     }
+    eprintln!("{}", buffer);
     assert_eq!(buffer, from_utf8(&buffer2).unwrap());
 
     deserialize_value
@@ -199,7 +203,7 @@ fn roundtrip_lazy() {
 }
 
 #[test]
-fn roundtrip_thread() {
+fn roundtrip_std_thread() {
     let thread = new_vm();
     let expr = r#" import! std.thread "#;
     let (value, _) = Compiler::new()
@@ -207,3 +211,15 @@ fn roundtrip_thread() {
         .unwrap_or_else(|err| panic!("{}", err));
     roundtrip(&thread, &value);
 }
+
+#[test]
+#[ignore] // Unimplemented so far
+fn roundtrip_thread() {
+    let thread = new_vm();
+    let expr = r#" let t = import! std.thread in t.new_thread ()"#;
+    let (value, _) = Compiler::new()
+        .run_io(true)
+        .run_expr::<IO<OpaqueValue<&Thread, Hole>>>(&thread, "test", &expr)
+        .unwrap_or_else(|err| panic!("{}", err));
+    roundtrip(&thread, &Into::<Result<_, _>>::into(value).unwrap());
+}