I modified the patch at
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/151854 to
work with 1.8.7-p72, but it dies with the following error:

ruby-1.8.7-p72 aman$ ruby -e 'o = Object.new; p GC.reachability_paths(o)'
-e:1:in `inspect': method `inspect' called on terminated object
(0x13cd38) (NotImplementedError)
       from -e:1:in `p'
       from -e:1

The patch (http://gist.github.com/14471):

diff --git a/gc.c b/gc.c
index 45facf0..a246ce9 100644
--- a/gc.c
+++ b/gc.c
@@ -74,7 +74,12 @@ static unsigned long malloc_increase = 0;
 static unsigned long malloc_limit = GC_MALLOC_LIMIT;
 static void run_final();
 static VALUE nomem_error;
+#ifdef DEBUG_REACHABILITY
+static VALUE garbage_collect0 _((VALUE));
+#define garbage_collect() garbage_collect0(0)
+#else
 static void garbage_collect();
+#endif

 int ruby_gc_stress = 0;

@@ -761,16 +766,55 @@ rb_gc_mark_maybe(obj)

 #define GC_LEVEL_MAX 250

+#ifdef DEBUG_REACHABILITY
+VALUE rb_reach_test_obj      = Qnil;
+VALUE rb_reach_test_result   = Qnil;
+VALUE rb_reach_test_path     = Qnil;
+
+static void
+rb_gc_unmark()
+{
+    RVALUE *p, *pend;
+    int i, used = heaps_used;
+
+    for (i = 0; i < used; i++) {
+       p = heaps[i].slot; pend = p + heaps[i].limit;
+       while (p < pend) {
+           RBASIC(p)->flags &= ~FL_MARK;
+           p++;
+       }
+    }
+}
+#endif
+
 static void
 gc_mark(ptr, lev)
    VALUE ptr;
    int lev;
 {
    register RVALUE *obj;
+#ifdef DEBUG_REACHABILITY
+    long saved_len = 0;
+    VALUE inspect = rb_intern("inspect");
+#endif

    obj = RANY(ptr);
    if (rb_special_const_p(ptr)) return; /* special const not marked */
    if (obj->as.basic.flags == 0) return;       /* free cell */
+#ifdef DEBUG_REACHABILITY
+    if (!NIL_P(rb_reach_test_obj) &&
+        (obj->as.basic.flags & T_MASK) != T_NODE) {
+       saved_len = RARRAY(rb_reach_test_path)->len;
+       if ((VALUE)obj == rb_reach_test_obj) {
+           rb_warn("  ...found, after %ld steps!", saved_len);
+           rb_ary_push(rb_reach_test_result,
+                       rb_ary_dup(rb_reach_test_path));
+       }
+       else if (!(obj->as.basic.flags & FL_MARK)) {
+           rb_ary_push(rb_reach_test_path, (VALUE)obj);
+       }
+    }
+#endif
    if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
    obj->as.basic.flags |= FL_MARK;

@@ -787,6 +831,11 @@ gc_mark(ptr, lev)
       return;
    }
    gc_mark_children(ptr, lev+1);
+#ifdef DEBUG_REACHABILITY
+    if (!NIL_P(rb_reach_test_path)) {
+       RARRAY(rb_reach_test_path)->len = saved_len;
+    }
+#endif
 }

 void
@@ -1369,9 +1418,25 @@ int rb_setjmp (rb_jmp_buf);
 #endif /* __human68k__ or DJGPP */
 #endif /* __GNUC__ */

+#ifdef DEBUG_REACHABILITY
+#define IF_DEBUG_REACHABILITY(does) if (obj) {does;}
+#else
+#define IF_DEBUG_REACHABILITY(does)
+#endif
+
+#ifdef DEBUG_REACHABILITY
+static VALUE
+garbage_collect0(obj)
+    VALUE obj;
+#else
 static void
 garbage_collect()
+#endif
 {
+#ifdef DEBUG_REACHABILITY
+    int i = 0;
+    VALUE result;
+#endif
    struct gc_list *list;
    struct FRAME * volatile frame; /* gcc 2.7.2.3 -O2 bug??  */
    jmp_buf save_regs_gc_mark;
@@ -1382,40 +1447,84 @@ garbage_collect()
       rb_bug("cross-thread violation on rb_gc()");
    }
 #endif
-    if (dont_gc || during_gc) {
-       if (!freelist) {
-           add_heap();
+
+#ifdef DEBUG_REACHABILITY
+    if (obj) {
+       if (!NIL_P(rb_reach_test_obj) ||
+           !NIL_P(rb_reach_test_result) ||
+           !NIL_P(rb_reach_test_path)) {
+           rb_raise(rb_eRuntimeError, "reachability_paths called recursively");
       }
-       return;
+
+       rb_reach_test_obj    = obj;
+       rb_reach_test_result = rb_ary_new();
+       rb_reach_test_path   = rb_ary_new();
+    }
+    else
+#endif
+    {
+    if (dont_gc || during_gc) {
+      if (!freelist) {
+          add_heap();
+      }
+#ifdef DEBUG_REACHABILITY
+      return 0;
+#else
+      return;
+#endif
    }
-    if (during_gc) return;
    during_gc++;
+    }

    init_mark_stack();

    gc_mark((VALUE)ruby_current_node, 0);

    /* mark frame stack */
+    IF_DEBUG_REACHABILITY(rb_warn("Checking frame stack..."));
    for (frame = ruby_frame; frame; frame = frame->prev) {
+       IF_DEBUG_REACHABILITY(
+           NODE *node = frame->node;
+           if (node) {
+               rb_ary_push(rb_reach_test_path,
+                           rb_sprintf("frame %d: %s line %d", i,
node->nd_file, nd_line(node)));
+           });
       rb_gc_mark_frame(frame);
+       IF_DEBUG_REACHABILITY((rb_ary_pop(rb_reach_test_path), i++));
       if (frame->tmp) {
           struct FRAME *tmp = frame->tmp;
+#ifdef DEBUG_REACHABILITY
+           int ti = 0;
+#endif
           while (tmp) {
+               IF_DEBUG_REACHABILITY(
+                   NODE *node = tmp->node;
+                   if (node) {
+                       rb_ary_push(rb_reach_test_path,
+                                   rb_sprintf("tmp frame %d: %s line %d",
+                                              ti, node->nd_file,
nd_line(node)));
+                   });
               rb_gc_mark_frame(tmp);
+               IF_DEBUG_REACHABILITY((rb_ary_pop(rb_reach_test_path), ti++));
               tmp = tmp->prev;
           }
       }
    }
+    IF_DEBUG_REACHABILITY(rb_warn("Checking ruby_class..."));
    gc_mark((VALUE)ruby_scope, 0);
+    IF_DEBUG_REACHABILITY(rb_warn("Checking ruby_scope..."));
    gc_mark((VALUE)ruby_dyna_vars, 0);
    if (finalizer_table) {
+       IF_DEBUG_REACHABILITY(rb_warn("Checking finalizer_table..."));
       mark_tbl(finalizer_table, 0);
    }

    FLUSH_REGISTER_WINDOWS;
    /* This assumes that all registers are saved into the jmp_buf
(and stack) */
    rb_setjmp(save_regs_gc_mark);
+    IF_DEBUG_REACHABILITY(rb_warn("Checking save_regs_gc_mark..."));
    mark_locations_array((VALUE*)save_regs_gc_mark,
sizeof(save_regs_gc_mark) / sizeof(VALUE *));
+    IF_DEBUG_REACHABILITY(rb_warn("Checking stack_start..."));
 #if STACK_GROW_DIRECTION < 0
    rb_gc_mark_locations((VALUE*)STACK_END, rb_gc_stack_start);
 #elif STACK_GROW_DIRECTION > 0
@@ -1435,24 +1544,35 @@ garbage_collect()
    rb_gc_mark_locations((VALUE*)((char*)STACK_END + 2),
                        (VALUE*)((char*)rb_gc_stack_start + 2));
 #endif
+    IF_DEBUG_REACHABILITY(rb_warn("Checking threads..."));
    rb_gc_mark_threads();

    /* mark protected global variables */
+    IF_DEBUG_REACHABILITY(rb_warn("Checking C globals..."));
    for (list = global_List; list; list = list->next) {
+       IF_DEBUG_REACHABILITY(rb_ary_push(rb_reach_test_path, rb_sprintf("C
global %d", i)));
       rb_gc_mark_maybe(*list->varptr);
+       IF_DEBUG_REACHABILITY((rb_ary_pop(rb_reach_test_path), i++));
    }
+    IF_DEBUG_REACHABILITY(rb_warn("Checking end_proc..."));
    rb_mark_end_proc();
+    IF_DEBUG_REACHABILITY(rb_warn("Checking global_tbl..."));
    rb_gc_mark_global_tbl();

+    IF_DEBUG_REACHABILITY(rb_warn("Checking class_tbl..."));
    rb_mark_tbl(rb_class_tbl);
+    IF_DEBUG_REACHABILITY(rb_warn("Checking trap_list..."));
    rb_gc_mark_trap_list();

    /* mark generic instance variables for special constants */
+    IF_DEBUG_REACHABILITY(rb_warn("Checking generic_ivar_tbl..."));
    rb_mark_generic_ivar_tbl();

+    IF_DEBUG_REACHABILITY(rb_warn("Checking mark parser..."));
    rb_gc_mark_parser();

    /* gc_mark objects whose marking are not completed*/
+    IF_DEBUG_REACHABILITY(rb_warn("Checking mark stack..."));
    do {
       while (!MARK_STACK_EMPTY) {
           if (mark_stack_overflow){
@@ -1465,6 +1585,20 @@ garbage_collect()
       rb_gc_abort_threads();
    } while (!MARK_STACK_EMPTY);

+    IF_DEBUG_REACHABILITY(
+       rb_warn("Unmarking...");
+       rb_gc_unmark();
+
+       rb_warn("Done.");
+
+       result = rb_reach_test_result;
+
+        rb_reach_test_obj    = Qnil;
+        rb_reach_test_result = Qnil;
+        rb_reach_test_path   = Qnil;
+
+       return result);
+
    gc_sweep();
 }

@@ -2075,6 +2209,15 @@ rb_obj_id(VALUE obj)
    return (VALUE)((long)obj|FIXNUM_FLAG);
 }

+static VALUE
+rbx_reachability_paths(mod, obj)
+    VALUE mod;
+    VALUE obj;
+{
+    if (rb_special_const_p(obj)) return Qnil;
+    return garbage_collect0(obj);
+}
+
 /*
 *  The <code>GC</code> module provides an interface to Ruby's mark and
 *  sweep garbage collection mechanism. Some of the underlying methods
@@ -2092,6 +2235,9 @@ Init_GC()
    rb_define_singleton_method(rb_mGC, "disable", rb_gc_disable, 0);
    rb_define_singleton_method(rb_mGC, "stress", gc_stress_get, 0);
    rb_define_singleton_method(rb_mGC, "stress=", gc_stress_set, 1);
+#ifdef DEBUG_REACHABILITY
+    rb_define_singleton_method(rb_mGC, "reachability_paths",
rbx_reachability_paths, 1);
+#endif
    rb_define_method(rb_mGC, "garbage_collect", rb_gc_start, 0);

    rb_mObSpace = rb_define_module("ObjectSpace");
@@ -2115,6 +2261,10 @@ Init_GC()
    source_filenames = st_init_strtable();

    rb_global_variable(&nomem_error);
+#ifdef DEBUG_REACHABILITY
+    rb_global_variable(&rb_reach_test_result);
+    rb_global_variable(&rb_reach_test_path);
+#endif
    nomem_error = rb_exc_new3(rb_eNoMemError,
                             rb_obj_freeze(rb_str_new2("failed to
allocate memory")));
    OBJ_TAINT(nomem_error);
diff --git a/sprintf.c b/sprintf.c
index 9cdf8bc..d3104b7 100644
--- a/sprintf.c
+++ b/sprintf.c
@@ -846,3 +846,41 @@ fmt_setup(buf, c, flags, width, prec)
    *buf++ = c;
    *buf = '\0';
 }
+
+#undef FILE
+#define FILE rb_printf_buffer
+#define __sbuf rb_printf_sbuf
+#define __sFILE rb_printf_sfile
+#undef feof
+#undef ferror
+#undef clearerr
+#undef fileno
+#if SIZEOF_LONG < SIZEOF_VOIDP
+# if  SIZEOF_LONG_LONG == SIZEOF_VOIDP
+#  define _HAVE_SANE_QUAD_
+#  define _HAVE_LLP64_
+#  define quad_t LONG_LONG
+#  define u_quad_t unsigned LONG_LONG
+# endif
+#endif
+#undef vsnprintf
+#undef snprintf
+#include "missing/vsnprintf.c"
+
+VALUE
+rb_sprintf(const char *format, ...)
+{
+    VALUE result;
+    va_list ap;
+    char *str;
+
+    va_start(ap, format);
+    vasprintf(&str, format, ap);
+    va_end(ap);
+
+    printf("STRING: %s\n", str);
+    result = rb_str_new2(str);
+    free(str);
+
+    return result;
+}
\ No newline at end of file
diff --git a/variable.c b/variable.c
index 50ecf04..b0ef111 100644
--- a/variable.c
+++ b/variable.c
@@ -458,6 +458,13 @@ readonly_setter(val, id, var)
    rb_name_error(id, "%s is a read-only variable", rb_id2name(id));
 }

+#ifdef DEBUG_REACHABILITY
+extern VALUE rb_reach_test_path;
+#define IF_DEBUG_REACHABILITY(does) do {if
(!NIL_P(rb_reach_test_path)) {does;}} while (0)
+#else
+#define IF_DEBUG_REACHABILITY(does)
+#endif
+
 static int
 mark_global_entry(key, entry)
    ID key;
@@ -465,11 +472,25 @@ mark_global_entry(key, entry)
 {
    struct trace_var *trace;
    struct global_variable *var = entry->var;
+#ifdef DEBUG_REACHABILITY
+    int i = 0;
+#endif

+    IF_DEBUG_REACHABILITY(
+       rb_ary_push(rb_reach_test_path,
+                   rb_sprintf("Ruby global %s", rb_id2name(key))));
    (*var->marker)(var->data);
+    IF_DEBUG_REACHABILITY(rb_ary_pop(rb_reach_test_path));
+
    trace = var->trace;
    while (trace) {
-       if (trace->data) rb_gc_mark_maybe(trace->data);
+       if (trace->data) {
+           IF_DEBUG_REACHABILITY(
+               rb_ary_push(rb_reach_test_path,
+                           rb_sprintf("Ruby global %s trace %d",
rb_id2name(key), i++)));
+           rb_gc_mark_maybe(trace->data);
+           IF_DEBUG_REACHABILITY(rb_ary_pop(rb_reach_test_path));
+       }
       trace = trace->next;
    }
    return ST_CONTINUE;


 Aman Gupta