[ruby-dev:37671] [Bug #953] 深い入れ子の配列の取り扱いで落ちる

チケット #953 が更新されました。 (by Yusuke Endoh)


遠藤です。

> 以下のスクリプトを実行すると Segmentation fault で落ちました。
>
> $ cat ./nest.rb 
> a = [0]
> 10000.times do
>   a = [a]
> end
> p a

どうも、C 関数の再帰が多すぎてマシンスタックが壊れてるような気がします。
なので仕様といわれれば仕様なのかもしれません。

しかし p が動かないのは不便なので、再帰が 100 回以上になったら Fiber を
使ってマシンスタックを伸びなくするパッチを書いてみました。
make test-all は通ったみたいです。再帰が 100 回を超えた場合はそれなりに
遅くなると思いますが、そんな場合はあんまりないかと思います。


Index: thread.c
===================================================================
--- thread.c	(revision 21208)
+++ thread.c	(working copy)
@@ -3191,13 +3191,13 @@
 static ID recursive_key;
 
 static VALUE
-recursive_check(VALUE hash, VALUE obj)
+recursive_check(VALUE hash, VALUE obj, VALUE sym)
 {
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
 	return Qfalse;
     }
     else {
-	VALUE list = rb_hash_aref(hash, ID2SYM(rb_frame_this_func()));
+	VALUE list = rb_hash_aref(hash, sym);
 
 	if (NIL_P(list) || TYPE(list) != T_HASH)
 	    return Qfalse;
@@ -3208,11 +3208,10 @@
 }
 
 static VALUE
-recursive_push(VALUE hash, VALUE obj)
+recursive_push(VALUE hash, VALUE obj, VALUE sym)
 {
-    VALUE list, sym;
+    VALUE list;
 
-    sym = ID2SYM(rb_frame_this_func());
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
 	hash = rb_hash_new();
 	rb_thread_local_aset(rb_thread_current(), recursive_key, hash);
@@ -3230,11 +3229,10 @@
 }
 
 static void
-recursive_pop(VALUE hash, VALUE obj)
+recursive_pop(VALUE hash, VALUE obj, VALUE sym)
 {
-    VALUE list, sym;
+    VALUE list;
 
-    sym = ID2SYM(rb_frame_this_func());
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
 	VALUE symname;
 	VALUE thrname;
@@ -3254,32 +3252,145 @@
     rb_hash_delete(list, obj);
 }
 
-VALUE
-rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+static long
+recursive_count(VALUE hash, VALUE sym)
 {
+    if (NIL_P(hash) || TYPE(hash) != T_HASH) {
+	return 0;
+    }
+    else {
+	VALUE list = rb_hash_aref(hash, sym);
+
+	if (NIL_P(list) || TYPE(list) != T_HASH)
+	    return 0;
+
+	if (!RHASH(list)->ntbl)
+	    return 0;
+	return RHASH(list)->ntbl->num_entries;
+    }
+}
+
+static VALUE
+exec_recursive_call(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg, VALUE sym)
+{
     VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
     VALUE objid = rb_obj_id(obj);
 
-    if (recursive_check(hash, objid)) {
+    if (recursive_check(hash, objid, sym)) {
 	return (*func) (obj, arg, Qtrue);
     }
     else {
 	VALUE result = Qundef;
 	int state;
 
-	hash = recursive_push(hash, objid);
+	hash = recursive_push(hash, objid, sym);
 	PUSH_TAG();
 	if ((state = EXEC_TAG()) == 0) {
 	    result = (*func) (obj, arg, Qfalse);
 	}
 	POP_TAG();
-	recursive_pop(hash, objid);
+	recursive_pop(hash, objid, sym);
 	if (state)
 	    JUMP_TAG(state);
 	return result;
     }
 }
 
+static VALUE
+exec_recursive_i(VALUE ctn, VALUE data)
+{
+    VALUE fiber = RARRAY_PTR(ctn)[0];
+    VALUE obj = RARRAY_PTR(ctn)[1];
+    VALUE arg = RARRAY_PTR(ctn)[2];
+    VALUE (*func) (VALUE, VALUE, int);
+    VALUE sym, hash, ret = Qundef;
+    int state;
+
+    sym = RARRAY_PTR(data)[0];
+    func = GC_GUARDED_PTR_REF(RARRAY_PTR(data)[1]);
+    hash = RARRAY_PTR(data)[2];
+
+    rb_thread_local_aset(rb_thread_current(), recursive_key, hash);
+
+    if (NIL_P(fiber)) {
+	return exec_recursive_call(func, obj, arg, sym);
+    }
+
+    PUSH_TAG();
+    if ((state = EXEC_TAG()) == 0) {
+	ret = exec_recursive_call(func, obj, arg, sym);
+    }
+    POP_TAG();
+    ret = ret == Qundef ? rb_ary_new3(2, INT2FIX(state), rb_errinfo()) : rb_ary_new3(1, ret);
+    return rb_fiber_resume(fiber, 1, &ret);
+}
+
+#define EXEC_RECURSIVE_CUTOFF 100
+#define EXEC_RECURSIVE_UNIT 30
+
+VALUE
+rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+{
+    VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
+    VALUE sym = ID2SYM(rb_frame_this_func());
+    int count = recursive_count(hash, sym);
+
+    if (count == EXEC_RECURSIVE_CUTOFF) {
+	/* recursive call depth is too deep; detach machine stack by using fibers */
+	VALUE ctn = rb_ary_new3(3, Qnil, obj, arg); /* initial continuation */
+	VALUE data = rb_ary_new3(3, sym, GC_GUARDED_PTR(func), hash);
+	int state;
+	VALUE result = Qundef;
+
+	PUSH_TAG();
+	if ((state = EXEC_TAG()) == 0) {
+	    while (1) {
+		VALUE fiber = rb_fiber_new(exec_recursive_i, data);
+		VALUE val = rb_fiber_resume(fiber, 1, &ctn);
+		if (RBASIC(val)->klass == 0) {
+		    /* next continuation is returned */
+		    ctn = rb_ary_new3(3, fiber, RARRAY_PTR(val)[0], RARRAY_PTR(val)[1]);
+		}
+		else {
+		    /* all calls are completed */
+		    result = val;
+		    break;
+		}
+	    }
+	}
+	POP_TAG();
+	if (state) {
+	    /* propagate exception throwing */
+	    VALUE mesg = rb_errinfo();
+	    VALUE rb_make_backtrace(void);
+	    VALUE bt = rb_make_backtrace();
+	    if (OBJ_FROZEN(mesg)) {
+		mesg = rb_obj_dup(mesg);
+	    }
+	    rb_funcall(mesg, rb_intern("set_backtrace"), 1, bt);
+	    GET_THREAD()->errinfo = mesg;
+	    JUMP_TAG(state);
+	}
+	return result;
+    }
+    else if (count < EXEC_RECURSIVE_CUTOFF || count % EXEC_RECURSIVE_UNIT != 0) {
+	/* normal recursive call */
+	return exec_recursive_call(func, obj, arg, sym);
+    }
+    else {
+	/* call depth of the fiber is too deep; yield continuation into main fiber */
+	VALUE ctn = rb_ary_new3(2, obj, arg);
+	VALUE ret;
+	RBASIC(ctn)->klass = 0;
+	ret = rb_fiber_yield(1, &ctn);
+	if (RARRAY_LEN(ret) == 0) {
+	    return RARRAY_PTR(ret)[0];
+	}
+	GET_THREAD()->errinfo = RARRAY_PTR(ret)[1];
+	JUMP_TAG(FIX2INT(RARRAY_PTR(ret)[0]));
+    }
+}
+
 /* tracer */
 
 static rb_event_hook_t *

-- 
Yusuke ENDOH <[e-mail]>

----------------------------------------
http://redmine.ruby-lang.org/issues/show/953

----------------------------------------
http://redmine.ruby-lang.org