Revert "Improve performance of partial backtraces"

This reverts commit f2d7461e85053cb084e10999b0b8019b0c29e66e.

Some CI machines are reporting issues with backtrace_mark, so I'm
going to revert this for now.

1 files changed, 71 insertions, 159 deletions

diff --git a/vm_backtrace.c b/vm_backtrace.c
index 50cc57457e..04b696c638 100644
--- a/vm_backtrace.c
+++ b/vm_backtrace.c
@@ -29,9 +29,6 @@ id2str(ID id)
 }
 #define rb_id2str(id) id2str(id)
 
-#define BACKTRACE_START 0
-#define ALL_BACKTRACE_LINES -1
-
 inline static int
 calc_lineno(const rb_iseq_t *iseq, const VALUE *pc)
 {
@@ -129,10 +126,6 @@ location_mark_entry(rb_backtrace_location_t *fi)
 	rb_gc_mark_movable((VALUE)fi->body.iseq.iseq);
 	break;
       case LOCATION_TYPE_CFUNC:
-        if (fi->body.cfunc.prev_loc) {
-            location_mark_entry(fi->body.cfunc.prev_loc);
-        }
-        break;
       case LOCATION_TYPE_IFUNC:
       default:
 	break;
@@ -491,47 +484,22 @@ backtrace_alloc(VALUE klass)
     return obj;
 }
 
-static long
-backtrace_size(const rb_execution_context_t *ec)
-{
-    const rb_control_frame_t *last_cfp = ec->cfp;
-    const rb_control_frame_t *start_cfp = RUBY_VM_END_CONTROL_FRAME(ec);
-
-    if (start_cfp == NULL) {
-        return -1;
-    }
-
-    start_cfp =
-      RUBY_VM_NEXT_CONTROL_FRAME(
-          RUBY_VM_NEXT_CONTROL_FRAME(start_cfp)); /* skip top frames */
-
-    if (start_cfp < last_cfp) {
-        return 0;
-    }
-
-    return start_cfp - last_cfp + 1;
-}
-
-static int
+static void
 backtrace_each(const rb_execution_context_t *ec,
-               ptrdiff_t from_last,
-               long num_frames,
 	       void (*init)(void *arg, size_t size),
 	       void (*iter_iseq)(void *arg, const rb_control_frame_t *cfp),
 	       void (*iter_cfunc)(void *arg, const rb_control_frame_t *cfp, ID mid),
-               void (*iter_skip)(void *arg, const rb_control_frame_t *cfp),
 	       void *arg)
 {
     const rb_control_frame_t *last_cfp = ec->cfp;
     const rb_control_frame_t *start_cfp = RUBY_VM_END_CONTROL_FRAME(ec);
     const rb_control_frame_t *cfp;
-    ptrdiff_t size, i, last, start = 0;
-    int ret = 0;
+    ptrdiff_t size, i;
 
     // In the case the thread vm_stack or cfp is not initialized, there is no backtrace.
     if (start_cfp == NULL) {
         init(arg, 0);
-        return ret;
+        return;
     }
 
     /*                <- start_cfp (end control frame)
@@ -549,43 +517,16 @@ backtrace_each(const rb_execution_context_t *ec,
 	  RUBY_VM_NEXT_CONTROL_FRAME(start_cfp)); /* skip top frames */
 
     if (start_cfp < last_cfp) {
-        size = last = 0;
+	size = 0;
     }
     else {
 	size = start_cfp - last_cfp + 1;
-
-        if (from_last > size) {
-            size = last = 0;
-            ret = 1;
-        }
-        else if (num_frames >= 0 && num_frames < size) {
-            if (from_last + num_frames > size) {
-                size -= from_last;
-                last = size;
-            }
-            else {
-                start = size - from_last - num_frames;
-                size = num_frames;
-                last = start + size;
-            }
-        }
-        else {
-            size -= from_last;
-            last = size;
-        }
     }
 
     init(arg, size);
 
     /* SDR(); */
-    for (i=0, cfp = start_cfp; i<last; i++, cfp = RUBY_VM_NEXT_CONTROL_FRAME(cfp)) {
-        if (i < start) {
-            if (iter_skip) {
-                iter_skip(arg, cfp);
-            }
-            continue;
-        }
-
+    for (i=0, cfp = start_cfp; i<size; i++, cfp = RUBY_VM_NEXT_CONTROL_FRAME(cfp)) {
 	/* fprintf(stderr, "cfp: %d\n", (rb_control_frame_t *)(ec->vm_stack + ec->vm_stack_size) - cfp); */
 	if (cfp->iseq) {
 	    if (cfp->pc) {
@@ -599,16 +540,12 @@ backtrace_each(const rb_execution_context_t *ec,
 	    iter_cfunc(arg, cfp, mid);
 	}
     }
-
-    return ret;
 }
 
 struct bt_iter_arg {
     rb_backtrace_t *bt;
     VALUE btobj;
     rb_backtrace_location_t *prev_loc;
-    const rb_control_frame_t *prev_cfp;
-    rb_backtrace_location_t *init_loc;
 };
 
 static void
@@ -617,11 +554,8 @@ bt_init(void *ptr, size_t size)
     struct bt_iter_arg *arg = (struct bt_iter_arg *)ptr;
     arg->btobj = backtrace_alloc(rb_cBacktrace);
     GetCoreDataFromValue(arg->btobj, rb_backtrace_t, arg->bt);
-    arg->bt->backtrace_base = arg->bt->backtrace = ALLOC_N(rb_backtrace_location_t, size+1);
-    arg->bt->backtrace_size = 1;
-    arg->prev_cfp = NULL;
-    arg->init_loc = &arg->bt->backtrace_base[size];
-    arg->init_loc->type = 0;
+    arg->bt->backtrace_base = arg->bt->backtrace = ALLOC_N(rb_backtrace_location_t, size);
+    arg->bt->backtrace_size = 0;
 }
 
 static void
@@ -630,7 +564,7 @@ bt_iter_iseq(void *ptr, const rb_control_frame_t *cfp)
     const rb_iseq_t *iseq = cfp->iseq;
     const VALUE *pc = cfp->pc;
     struct bt_iter_arg *arg = (struct bt_iter_arg *)ptr;
-    rb_backtrace_location_t *loc = &arg->bt->backtrace[arg->bt->backtrace_size++-1];
+    rb_backtrace_location_t *loc = &arg->bt->backtrace[arg->bt->backtrace_size++];
     loc->type = LOCATION_TYPE_ISEQ;
     loc->body.iseq.iseq = iseq;
     loc->body.iseq.lineno.pc = pc;
@@ -641,69 +575,41 @@ static void
 bt_iter_cfunc(void *ptr, const rb_control_frame_t *cfp, ID mid)
 {
     struct bt_iter_arg *arg = (struct bt_iter_arg *)ptr;
-    rb_backtrace_location_t *loc = &arg->bt->backtrace[arg->bt->backtrace_size++-1];
+    rb_backtrace_location_t *loc = &arg->bt->backtrace[arg->bt->backtrace_size++];
     loc->type = LOCATION_TYPE_CFUNC;
     loc->body.cfunc.mid = mid;
-    if (arg->prev_loc) {
-        loc->body.cfunc.prev_loc = arg->prev_loc;
-    }
-    else if (arg->prev_cfp) {
-        const rb_iseq_t *iseq = arg->prev_cfp->iseq;
-        const VALUE *pc = arg->prev_cfp->pc;
-        arg->init_loc->type = LOCATION_TYPE_ISEQ;
-        arg->init_loc->body.iseq.iseq = iseq;
-        arg->init_loc->body.iseq.lineno.pc = pc;
-        loc->body.cfunc.prev_loc = arg->prev_loc = arg->init_loc;
-    } else {
-        loc->body.cfunc.prev_loc = NULL;
-    }
-}
-
-static void
-bt_iter_skip(void *ptr, const rb_control_frame_t *cfp)
-{
-    if (cfp->iseq && cfp->pc) {
-        ((struct bt_iter_arg *)ptr)->prev_cfp = cfp;
-    }
+    loc->body.cfunc.prev_loc = arg->prev_loc;
 }
 
-static VALUE
-rb_ec_partial_backtrace_object(const rb_execution_context_t *ec, long lev, long n, int* level_too_large)
+MJIT_FUNC_EXPORTED VALUE
+rb_ec_backtrace_object(const rb_execution_context_t *ec)
 {
     struct bt_iter_arg arg;
-    int too_large;
     arg.prev_loc = 0;
 
-    too_large = backtrace_each(ec,
-                               lev,
-                               n,
-                               bt_init,
-                               bt_iter_iseq,
-                               bt_iter_cfunc,
-                               bt_iter_skip,
-                               &arg);
-
-    if (level_too_large) *level_too_large = too_large;
+    backtrace_each(ec,
+		   bt_init,
+		   bt_iter_iseq,
+		   bt_iter_cfunc,
+		   &arg);
 
     return arg.btobj;
 }
 
-MJIT_FUNC_EXPORTED VALUE
-rb_ec_backtrace_object(const rb_execution_context_t *ec)
-{
-    return rb_ec_partial_backtrace_object(ec, BACKTRACE_START, ALL_BACKTRACE_LINES, NULL);
-}
-
 static VALUE
-backtrace_collect(rb_backtrace_t *bt, VALUE (*func)(rb_backtrace_location_t *, void *arg), void *arg)
+backtrace_collect(rb_backtrace_t *bt, long lev, long n, VALUE (*func)(rb_backtrace_location_t *, void *arg), void *arg)
 {
     VALUE btary;
     int i;
 
-    btary = rb_ary_new2(bt->backtrace_size-1);
+    if (UNLIKELY(lev < 0 || n < 0)) {
+	rb_bug("backtrace_collect: unreachable");
+    }
 
-    for (i=0; i<bt->backtrace_size-1; i++) {
-        rb_backtrace_location_t *loc = &bt->backtrace[bt->backtrace_size - 2 - i];
+    btary = rb_ary_new2(n);
+
+    for (i=0; i+lev<bt->backtrace_size && i<n; i++) {
+	rb_backtrace_location_t *loc = &bt->backtrace[bt->backtrace_size - 1 - (lev+i)];
 	rb_ary_push(btary, func(loc, arg));
     }
 
@@ -717,12 +623,23 @@ location_to_str_dmyarg(rb_backtrace_location_t *loc, void *dmy)
 }
 
 static VALUE
-backtrace_to_str_ary(VALUE self)
+backtrace_to_str_ary(VALUE self, long lev, long n)
 {
-    VALUE r;
     rb_backtrace_t *bt;
+    int size;
+    VALUE r;
+
     GetCoreDataFromValue(self, rb_backtrace_t, bt);
-    r = backtrace_collect(bt, location_to_str_dmyarg, 0);
+    size = bt->backtrace_size;
+
+    if (n == 0) {
+	n = size;
+    }
+    if (lev > size) {
+	return Qnil;
+    }
+
+    r = backtrace_collect(bt, lev, n, location_to_str_dmyarg, 0);
     RB_GC_GUARD(self);
     return r;
 }
@@ -734,7 +651,7 @@ rb_backtrace_to_str_ary(VALUE self)
     GetCoreDataFromValue(self, rb_backtrace_t, bt);
 
     if (!bt->strary) {
-        bt->strary = backtrace_to_str_ary(self);
+	bt->strary = backtrace_to_str_ary(self, 0, bt->backtrace_size);
     }
     return bt->strary;
 }
@@ -747,9 +664,9 @@ rb_backtrace_use_iseq_first_lineno_for_last_location(VALUE self)
     rb_backtrace_location_t *loc;
 
     GetCoreDataFromValue(self, rb_backtrace_t, bt);
-    VM_ASSERT(bt->backtrace_size > 1);
+    VM_ASSERT(bt->backtrace_size > 0);
 
-    loc = &bt->backtrace[bt->backtrace_size - 2];
+    loc = &bt->backtrace[bt->backtrace_size - 1];
     iseq = loc->body.iseq.iseq;
 
     VM_ASSERT(loc->type == LOCATION_TYPE_ISEQ);
@@ -772,12 +689,23 @@ location_create(rb_backtrace_location_t *srcloc, void *btobj)
 }
 
 static VALUE
-backtrace_to_location_ary(VALUE self)
+backtrace_to_location_ary(VALUE self, long lev, long n)
 {
-    VALUE r;
     rb_backtrace_t *bt;
+    int size;
+    VALUE r;
+
     GetCoreDataFromValue(self, rb_backtrace_t, bt);
-    r = backtrace_collect(bt, location_create, (void *)self);
+    size = bt->backtrace_size;
+
+    if (n == 0) {
+	n = size;
+    }
+    if (lev > size) {
+	return Qnil;
+    }
+
+    r = backtrace_collect(bt, lev, n, location_create, (void *)self);
     RB_GC_GUARD(self);
     return r;
 }
@@ -789,7 +717,7 @@ rb_backtrace_to_location_ary(VALUE self)
     GetCoreDataFromValue(self, rb_backtrace_t, bt);
 
     if (!bt->locary) {
-        bt->locary = backtrace_to_location_ary(self);
+	bt->locary = backtrace_to_location_ary(self, 0, 0);
     }
     return bt->locary;
 }
@@ -813,13 +741,13 @@ backtrace_load_data(VALUE self, VALUE str)
 VALUE
 rb_ec_backtrace_str_ary(const rb_execution_context_t *ec, long lev, long n)
 {
-    return backtrace_to_str_ary(rb_ec_partial_backtrace_object(ec, lev, n, NULL));
+    return backtrace_to_str_ary(rb_ec_backtrace_object(ec), lev, n);
 }
 
 VALUE
 rb_ec_backtrace_location_ary(const rb_execution_context_t *ec, long lev, long n)
 {
-    return backtrace_to_location_ary(rb_ec_partial_backtrace_object(ec, lev, n, NULL));
+    return backtrace_to_location_ary(rb_ec_backtrace_object(ec), lev, n);
 }
 
 /* make old style backtrace directly */
@@ -886,12 +814,9 @@ vm_backtrace_print(FILE *fp)
     arg.func = oldbt_print;
     arg.data = (void *)fp;
     backtrace_each(GET_EC(),
-                   BACKTRACE_START,
-                   ALL_BACKTRACE_LINES,
 		   oldbt_init,
 		   oldbt_iter_iseq,
 		   oldbt_iter_cfunc,
-                   NULL,
 		   &arg);
 }
 
@@ -922,12 +847,9 @@ rb_backtrace_print_as_bugreport(void)
     arg.data = (int *)&i;
 
     backtrace_each(GET_EC(),
-                   BACKTRACE_START,
-                   ALL_BACKTRACE_LINES,
 		   oldbt_init,
 		   oldbt_iter_iseq,
 		   oldbt_iter_cfunc,
-                   NULL,
 		   &arg);
 }
 
@@ -968,19 +890,16 @@ rb_backtrace_each(VALUE (*iter)(VALUE recv, VALUE str), VALUE output)
     arg.func = oldbt_print_to;
     arg.data = &parg;
     backtrace_each(GET_EC(),
-                   BACKTRACE_START,
-                   ALL_BACKTRACE_LINES,
 		   oldbt_init,
 		   oldbt_iter_iseq,
 		   oldbt_iter_cfunc,
-                   NULL,
 		   &arg);
 }
 
 VALUE
 rb_make_backtrace(void)
 {
-    return rb_ec_backtrace_str_ary(GET_EC(), BACKTRACE_START, ALL_BACKTRACE_LINES);
+    return rb_ec_backtrace_str_ary(GET_EC(), 0, 0);
 }
 
 static VALUE
@@ -988,9 +907,11 @@ ec_backtrace_to_ary(const rb_execution_context_t *ec, int argc, const VALUE *arg
 {
     VALUE level, vn;
     long lev, n;
-    VALUE btval;
+    VALUE btval = rb_ec_backtrace_object(ec);
     VALUE r;
-    int too_large;
+    rb_backtrace_t *bt;
+
+    GetCoreDataFromValue(btval, rb_backtrace_t, bt);
 
     rb_scan_args(argc, argv, "02", &level, &vn);
 
@@ -999,19 +920,19 @@ ec_backtrace_to_ary(const rb_execution_context_t *ec, int argc, const VALUE *arg
     switch (argc) {
       case 0:
 	lev = lev_default + lev_plus;
-        n = ALL_BACKTRACE_LINES;
+	n = bt->backtrace_size - lev;
 	break;
       case 1:
 	{
-            long beg, len, bt_size = backtrace_size(ec);
-            switch (rb_range_beg_len(level, &beg, &len, bt_size - lev_plus, 0)) {
+	    long beg, len;
+	    switch (rb_range_beg_len(level, &beg, &len, bt->backtrace_size - lev_plus, 0)) {
 	      case Qfalse:
 		lev = NUM2LONG(level);
 		if (lev < 0) {
 		    rb_raise(rb_eArgError, "negative level (%ld)", lev);
 		}
 		lev += lev_plus;
-                n = ALL_BACKTRACE_LINES;
+		n = bt->backtrace_size - lev;
 		break;
 	      case Qnil:
 		return Qnil;
@@ -1042,17 +963,11 @@ ec_backtrace_to_ary(const rb_execution_context_t *ec, int argc, const VALUE *arg
 	return rb_ary_new();
     }
 
-    btval = rb_ec_partial_backtrace_object(ec, lev, n, &too_large);
-
-    if (too_large) {
-        return Qnil;
-    }
-
     if (to_str) {
-        r = backtrace_to_str_ary(btval);
+	r = backtrace_to_str_ary(btval, lev, n);
     }
     else {
-        r = backtrace_to_location_ary(btval);
+	r = backtrace_to_location_ary(btval, lev, n);
     }
     RB_GC_GUARD(btval);
     return r;
@@ -1314,12 +1229,9 @@ collect_caller_bindings(const rb_execution_context_t *ec)
     data.ary = rb_ary_new();
 
     backtrace_each(ec,
-                   BACKTRACE_START,
-                   ALL_BACKTRACE_LINES,
 		   collect_caller_bindings_init,
 		   collect_caller_bindings_iseq,
 		   collect_caller_bindings_cfunc,
-                   NULL,
 		   &data);
 
     result = rb_ary_reverse(data.ary);
@@ -1356,7 +1268,7 @@ rb_debug_inspector_open(rb_debug_inspector_func_t func, void *data)
 
     dbg_context.ec = ec;
     dbg_context.cfp = dbg_context.ec->cfp;
-    dbg_context.backtrace = rb_ec_backtrace_location_ary(ec, BACKTRACE_START, ALL_BACKTRACE_LINES);
+    dbg_context.backtrace = rb_ec_backtrace_location_ary(ec, 0, 0);
     dbg_context.backtrace_size = RARRAY_LEN(dbg_context.backtrace);
     dbg_context.contexts = collect_caller_bindings(ec);