gc: Add stack walker for new garbage collector.

Safe points are exported in a per-module list via the crate map. A C
runtime call walks the crate map at startup and aggregates the list of
safe points for the program.

Currently the GC doesn't actually deallocate memory on malloc and
free. Adding the GC at this stage is primarily of testing value.

The GC does attempt to clean up exchange heap and stack-allocated
resource on failure.

A result of this patch is that the user now needs to be careful about
what code they write in destructors, because the GC and/or failure
cleanup may need to call destructors. Specifically, calls to malloc
are considered unsafe and may result in infinite loops or segfaults.

3 files changed, 161 insertions, 1 deletions

diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index 6cf9c82a511..4da21d7f5af 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -40,7 +40,7 @@ export uint, u8, u16, u32, u64;
 export float, f32, f64;
 export box, char, str, ptr, vec, at_vec, bool;
 export either, option, result, iter;
-export libc, os, io, run, rand, sys, unsafe, logging;
+export gc, io, libc, os, run, rand, sys, unsafe, logging;
 export comm, task, future, pipes;
 export extfmt;
 // The test harness links against core, so don't include runtime in tests.
@@ -216,6 +216,7 @@ mod pipes;
 
 // Runtime and language-primitive support
 
+mod gc;
 mod io;
 mod libc;
 mod os;
diff --git a/src/libcore/gc.rs b/src/libcore/gc.rs
new file mode 100644
index 00000000000..eacd0bc62d3
--- /dev/null
+++ b/src/libcore/gc.rs
@@ -0,0 +1,155 @@
+import stackwalk::Word;
+import libc::size_t;
+
+extern mod rustrt {
+    fn rust_annihilate_box(ptr: *Word);
+
+    #[rust_stack]
+    fn rust_gc_metadata() -> *Word;
+
+    #[rust_stack]
+    fn rust_call_tydesc_glue(root: *Word, tydesc: *Word, field: size_t);
+}
+
+type SafePoint = { sp_meta: *Word, fn_meta: *Word };
+
+unsafe fn is_safe_point(pc: *Word) -> Option<SafePoint> {
+    let module_meta = rustrt::rust_gc_metadata();
+    let num_safe_points_ptr: *u32 = unsafe::reinterpret_cast(&module_meta);
+    let num_safe_points = *num_safe_points_ptr as Word;
+    let safe_points: *Word =
+        ptr::offset(unsafe::reinterpret_cast(&module_meta), 1);
+
+    if ptr::is_null(pc) {
+        return None;
+    }
+
+    let mut sp = 0 as Word;
+    while sp < num_safe_points {
+        let sp_loc = *ptr::offset(safe_points, sp*3) as *Word;
+        if sp_loc == pc {
+            return Some(
+                {sp_meta: *ptr::offset(safe_points, sp*3 + 1) as *Word,
+                 fn_meta: *ptr::offset(safe_points, sp*3 + 2) as *Word});
+        }
+        sp += 1;
+    }
+    return None;
+}
+
+type Visitor = fn(root: **Word, tydesc: *Word);
+
+unsafe fn walk_safe_point(fp: *Word, sp: SafePoint, visitor: Visitor) {
+    let fp_bytes: *u8 = unsafe::reinterpret_cast(&fp);
+    let sp_meta_u32s: *u32 = unsafe::reinterpret_cast(&sp.sp_meta);
+
+    let num_stack_roots = *sp_meta_u32s as uint;
+    let num_reg_roots = *ptr::offset(sp_meta_u32s, 1) as uint;
+
+    let stack_roots: *u32 =
+        unsafe::reinterpret_cast(&ptr::offset(sp_meta_u32s, 2));
+    let reg_roots: *u8 =
+        unsafe::reinterpret_cast(&ptr::offset(stack_roots, num_stack_roots));
+    let addrspaces: *Word =
+        unsafe::reinterpret_cast(&ptr::offset(reg_roots, num_reg_roots));
+    let tydescs: ***Word =
+        unsafe::reinterpret_cast(&ptr::offset(addrspaces, num_stack_roots));
+
+    // Stack roots
+    let mut sri = 0;
+    while sri < num_stack_roots {
+        if *ptr::offset(addrspaces, sri) >= 1 {
+            let root =
+                ptr::offset(fp_bytes, *ptr::offset(stack_roots, sri) as Word)
+                as **Word;
+            let tydescpp = ptr::offset(tydescs, sri);
+            let tydesc = if ptr::is_not_null(tydescpp) &&
+                ptr::is_not_null(*tydescpp) {
+                **tydescpp
+            } else {
+                ptr::null()
+            };
+            visitor(root, tydesc);
+        }
+        sri += 1;
+    }
+
+    // Register roots
+    let mut rri = 0;
+    while rri < num_reg_roots {
+        if *ptr::offset(addrspaces, num_stack_roots + rri) == 1 {
+            // FIXME(#2997): Need to find callee saved registers on the stack.
+        }
+        rri += 1;
+    }
+}
+
+type Memory = uint;
+
+const task_local_heap: Memory = 1;
+const exchange_heap:   Memory = 2;
+const stack:           Memory = 4;
+
+const need_cleanup:    Memory = exchange_heap | stack;
+
+unsafe fn walk_gc_roots(mem: Memory, visitor: Visitor) {
+    let mut last_ret: *Word = ptr::null();
+    do stackwalk::walk_stack |frame| {
+        unsafe {
+            if ptr::is_not_null(last_ret) {
+                let sp = is_safe_point(last_ret);
+                match sp {
+                  Some(sp_info) => {
+                    do walk_safe_point(frame.fp, sp_info) |root, tydesc| {
+                        if ptr::is_null(tydesc) {
+                            // Root is a generic box.
+                            let refcount = **root;
+                            if mem | task_local_heap != 0 && refcount != -1 {
+                                visitor(root, tydesc);
+                            } else if mem | exchange_heap != 0 {
+                                visitor(root, tydesc);
+                            }
+                        } else {
+                            // Root is a non-immediate.
+                            if mem | stack != 0 {
+                                visitor(root, tydesc);
+                            }
+                        }
+                    }
+                  }
+                  None => ()
+                }
+            }
+            last_ret = *ptr::offset(frame.fp, 1) as *Word;
+        }
+        true
+    }
+}
+
+fn gc() {
+    unsafe {
+        let mut i = 0;
+        do walk_gc_roots(task_local_heap) |_root, _tydesc| {
+            // FIXME(#2997): Walk roots and mark them.
+            io::stdout().write([46]); // .
+            i += 1;
+        }
+    }
+}
+
+// This should only be called from fail, as it will drop the roots
+// which are *live* on the stack, rather than dropping those that are
+// dead.
+fn cleanup_stack_for_failure() {
+    unsafe {
+        let mut i = 0;
+        do walk_gc_roots(need_cleanup) |root, tydesc| {
+            if ptr::is_null(tydesc) {
+                rustrt::rust_annihilate_box(*root);
+            } else {
+                rustrt::rust_call_tydesc_glue(*root, tydesc, 3 as size_t);
+            }
+            i += 1;
+        }
+    }
+}
diff --git a/src/libcore/rt.rs b/src/libcore/rt.rs
index 60253f0c0dd..0f074bc5c1d 100644
--- a/src/libcore/rt.rs
+++ b/src/libcore/rt.rs
@@ -8,6 +8,9 @@ use libc::c_void;
 use libc::size_t;
 use libc::uintptr_t;
 
+import gc::gc;
+import gc::cleanup_stack_for_failure;
+
 #[allow(non_camel_case_types)]
 type rust_task = c_void;
 
@@ -33,6 +36,7 @@ extern mod rustrt {
 // gather_rust_rtcalls.
 #[rt(fail)]
 fn rt_fail(expr: *c_char, file: *c_char, line: size_t) {
+    cleanup_stack_for_failure();
     rustrt::rust_upcall_fail(expr, file, line);
 }