Bug #953

深い入れ子の配列の取り扱いで落ちる

Added by tadayoshi funaba over 6 years ago. Updated almost 2 years ago.

[ruby-dev:37664]
Status:Closed
Priority:Normal
Assignee:Koichi Sasada
ruby -v:ruby 1.9.1 (2008-12-30 patchlevel-5000 trunk 21202) [i686-linux] Backport:

Description

=begin
以下のスクリプトを実行すると Segmentation fault で落ちました。

$ cat ./nest.rb
a = [0]
10000.times do
a = [a]
end
p a

$ ./ruby -v ./nest.rb
ruby 1.9.1 (2008-12-30 patchlevel-5000 trunk 21202) [i686-linux]
Segmentation fault

(gdb) bt
#0 0x08111407 in vm_get_ruby_level_next_cfp (th=0x81ae758, cfp=0xb7c734a8)
at vm.c:131
#1 0x0811159b in rb_sourceline () at vm.c:757
#2 0x0814ead7 in rb_bug (fmt=0x81737d3 "Segmentation fault") at error.c:230
#3 0x080d49e6 in sigsegv (sig=11, info=0x82152fc, ctx=0x821537c)
at signal.c:600
#4
#5 frame_func_id (cfp=0xb7c734a8) at eval.c:730
#6 0x0812696a in rb_exec_recursive (func=0x812d040 ,
obj=135994660, arg=0) at thread.c:3237
#7 0x0812d01a in rb_ary_inspect (ary=4) at array.c:1574
#8 0x0811d854 in vm_call0 (th=0x81ae758, klass=136124880, recv=135994660,
id=760, oid=760, argc=0, argv=0x0, body=0x81d1818, nosuper=0)
at vm_eval.c:70
#9 0x0811ddb2 in rb_funcall (recv=, mid=760, n=0)
at vm_eval.c:248
#10 0x080840aa in rb_inspect (obj=135994660) at object.c:312
#11 0x0812d0f3 in inspect_ary (ary=135994500, dummy=0, recur=0) at array.c:1550
#12 0x08126b5f in rb_exec_recursive (func=0x812d040 ,
obj=135994500, arg=0) at thread.c:3273
#13 0x0812d01a in rb_ary_inspect (ary=4) at array.c:1574
#14 0x0811d854 in vm_call0 (th=0x81ae758, klass=136124880, recv=135994500,
id=760, oid=760, argc=0, argv=0x0, body=0x81d1818, nosuper=0)
---Type to continue, or q to quit---
=end


Related issues

Related to Ruby trunk - Bug #7141: ALT_STACK_SIZE is not enough Closed 10/11/2012

History

#1 Updated by Yusuke Endoh about 6 years ago

=begin
遠藤です。

以下のスクリプトを実行すると 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 mame@tsg.ne.jp

=end

#2 Updated by Shyouhei Urabe about 6 years ago

  • Assignee set to Koichi Sasada
  • ruby -v set to ruby 1.9.1 (2008-12-30 patchlevel-5000 trunk 21202) [i686-linux]

=begin

=end

#3 Updated by Yusuke Endoh about 5 years ago

  • Status changed from Open to Closed

=begin
遠藤です。

以下のスクリプトを実行すると Segmentation fault で落ちました。

$ cat ./nest.rb
a = [0]
10000.times do
a = [a]
end
p a

現在はもう落ちないようなので、close します。

rb_exec_recursive のあたりはたぶん結構いろいろ変わっているので、
何のおかげで落ちなくなったのかはよくわかりません。すみません。

まだ再現するようなら reopen してください。

--
Yusuke Endoh mame@tsg.ne.jp
=end

#4 Updated by Kazuki Tsujimoto about 3 years ago

  • Target version set to 2.0.0
  • Status changed from Closed to Open
  • Assignee deleted (Koichi Sasada)

=begin
辻本です。

trunkで再現するようになっているのでreopenしておきます。

$ ./ruby -v ./nest.rb
ruby 2.0.0dev (2012-03-03 trunk 34892) [x86_64-linux]
./nest.rb:5: [BUG] Segmentation fault
=end

#5 Updated by Koichi Sasada about 3 years ago

  • Assignee set to Koichi Sasada

頑張ります.

#6 Updated by Shyouhei Urabe about 3 years ago

  • Status changed from Open to Assigned

#7 Updated by Koichi Sasada almost 3 years ago

  • Status changed from Assigned to Feedback

随分前のチケットに対してすみません.
こちら,まだ再現するでしょうか.手元の環境では,
動いちゃったり,stack level too deep (SystemStackError)
だったりで,それなりにちゃんと動いているような気がしております.

#8 Updated by Yui NARUSE almost 3 years ago

わたしの FreeBSD 9.0 amd64 や Ubuntu 10.04 x64 では再現しますね

#9 Updated by Kazuki Tsujimoto almost 3 years ago

手元のUbuntu 10.04 x64ではr35333でも再現しました。

ですが、一からOSをインストールし直した環境では正常に動作しているので
正確な再現条件は不明です。

#10 Updated by Kazuki Tsujimoto almost 3 years ago

ulimit -s 4096とすることで、Ubuntu {10.04,11.10} {x86,x64}で再現できましたが
どうでしょうか。

#11 Updated by Koichi Sasada over 2 years ago

  • Target version changed from 2.0.0 to next minor

タイムアップとして次に回します.

#12 Updated by Yusuke Endoh over 2 years ago

  • Target version changed from next minor to 2.0.0
  • Status changed from Feedback to Assigned

ulimit -s 4096 で Ubuntu 12.10 x64 で再現できませんでしたが、
たぶん特に状況は変わってないんですよね。

再現性のある SEGV ということで、2.0.0 で直したほうがいいと思います。

ささださんが修正方針を示して、再現環境のある成瀬さんや ktsj さんが
パッチを作るのいいかも知れない?

Yusuke Endoh mame@tsg.ne.jp

#13 Updated by Kazuki Tsujimoto over 2 years ago

=begin
ulimit -s 4096 / Ubuntu 12.04 x64 でtrunk(r38279)で追試してみたところ、
状況が変わっていて、SystemStackErrorにはなるものの
MALLOC_CHECK_で落ちるようになっています。

$ ./ruby nest.rb
nest.rb:5: stack level too deep (SystemStackError)
*** glibc detected *** ./ruby: munmap_chunk(): invalid pointer: 0x0000555555a55f40 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x7e626)[0x7ffff6f3f626]
./ruby(+0x1af3e0)[0x5555557033e0]
./ruby(ruby_vm_destruct+0x75)[0x555555702c56]
./ruby(ruby_cleanup+0x382)[0x5555555b29c2]
./ruby(ruby_run_node+0x45)[0x5555555b2b7b]
./ruby(+0x20f09)[0x555555574f09]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed)[0x7ffff6ee276d]
./ruby(+0x20dd9)[0x555555574dd9]

この際のバックトレースは以下の通りです。

Program received signal SIGABRT, Aborted.
0x00007ffff6ef7445 in raise () from /lib/x86_64-linux-gnu/libc.so.6
(gdb) bt
#0 0x00007ffff6ef7445 in raise () from /lib/x86_64-linux-gnu/libc.so.6
#1 0x00007ffff6efabab in abort () from /lib/x86_64-linux-gnu/libc.so.6
#2 0x00007ffff6f34e2e in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#3 0x00007ffff6f3f626 in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#4 0x000055555570344d in thread_free (ptr=0x5555559ee570) at vm.c:1762
#5 0x0000555555702cc3 in ruby_vm_destruct (vm=0x5555559edf20) at vm.c:1570
#6 0x00005555555b29c2 in ruby_cleanup (ex=1) at eval.c:233
#7 0x00005555555b2b7b in ruby_run_node (n=0x555555dbd030) at eval.c:307
#8 0x0000555555574f09 in main (argc=5, argv=0x7fffffffe018) at main.c:36
(gdb) fr 4
#4 0x000055555570344d in thread_free (ptr=0x5555559ee570) at vm.c:1762
1762 free(th->altstack);
(gdb) p th->altstack
$3 = (void *) 0x555555a55f40

これは[Bug #7141]と同件のようなので、まずはそちらの対応待ちということでどうでしょうか。

  • 「altstackの周りをmprotectして確認」するパッチを当てるとSEGVするようになる。
  • 「ALT_STACK_SIZEを5倍くらいする」パッチを当てると、単にSystemStackErrorで終わるようになる。(MALLOC_CHECK_にもかからない) =end

#14 Updated by Kazuki Tsujimoto over 2 years ago

  • Status changed from Assigned to Closed

r38409にて問題が修正されたことを確認できたのでクローズしておきます。(Ubuntu 11.10/12.06 x64)

成瀬さんの環境で直っていないようであれば、再オープンしていただけますか。

#15 Updated by Motohiro KOSAKI over 2 years ago

うーん、r38409はSIGSEGVが起きた「後」、もう一回SIGSEGしてしまってバックトレースが正しく採取できない問題に対するパッチなのでSIGSEGVを起きなくさせる効果はないはずなんですが・・・・

#16 Updated by Kazuki Tsujimoto over 2 years ago

の詳細は以下のようになります。

  1. rb_exec_recursive等により一回マシンスタックを突き破ってSIGSEGVが発生。
    (ちなみに、このときのメモリレイアウトをhttps://gist.github.com/4249318の「#953のnest.rb実行時にSystemStackErrorとなった際の例」にまとめています)

  2. sigsegv関数が呼ばれるがその処理の中でaltstackを突き破っておそらくmalloc headerを破壊。

    Hardware watchpoint 5: (((char)(0x555555a55f40))-3)
    Old value = 0 '\000'
    New value = 85 'U'
    GET_THREAD () at vm_core.h:839
    (gdb) i f
    Stack level 0, frame at 0x555555a55f40:
    rip = 0x55555567d91b in GET_THREAD (vm_core.h:839); saved rip 0x55555567d93c
    called by frame at 0x555555a55f50
    source language c.
    Arglist at 0x555555a55f30, args:
    Locals at 0x555555a55f30, Previous frame's sp is 0x555555a55f40
    Saved registers:
    rip at 0x555555a55f38
    (gdb) p ruby_current_thread->altstack
    $31 = (void *) 0x555555a55f40
    (gdb) bt
    #0 GET_THREAD () at vm_core.h:839
    #1 0x000055555567d93c in rb_safe_level () at safe.c:30
    #2 0x000055555569296e in str_modifiable (str=93824999742280) at string.c:1313
    #3 0x00005555556929ab in str_independent (str=93824999742280) at string.c:1320
    #4 0x0000555555694949 in rb_str_resize (str=93824999742280, len=120) at string.c:1835
    #5 0x0000555555686c82 in ruby_sfvwrite (fp=0x555555a566b0, uio=0x555555a56150) at sprintf.c:1168
    #6 0x0000555555683c6b in BSD
    sprint (fp=0x555555a566b0, uio=0x555555a56150) at vsnprintf.c:333
    #7 0x00005555556865cb in BSD_vfprintf (fp=0x555555a566b0, fmt0=0x55555571d379 "%s:%d", ap=0x555555a56720) at vsnprintf.c:1194
    #8 0x000055555568705e in rb_enc_vsprintf (enc=0x5555559f3a80, fmt=0x55555571d379 "%s:%d", ap=0x555555a56720) at sprintf.c:1242
    #9 0x0000555555687158 in rb_enc_sprintf (enc=0x5555559f3a80, format=0x55555571d379 "%s:%d") at sprintf.c:1257
    #10 0x00005555555b2f1d in setup_exception (th=0x5555559ee570, tag=6, mesg=93824997401520) at eval.c:447
    #11 0x00005555555b3456 in rb_longjmp (tag=6, mesg=93824997401520) at eval.c:519
    #12 0x00005555555b34bb in rb_exc_raise (mesg=93824997401520) at eval.c:532
    #13 0x000055555570f174 in ruby
    thread_stack_overflow (th=0x5555559ee570) at thread.c:1937
    #14 0x000055555567e650 in sigsegv (sig=11, info=0x555555a56b30, ctx=0x555555a56a00) at signal.c:618
    #15
    #16 0x0000555555712d89 in exec_recursive (func=, obj=,
    pairid=, arg=,
    outer=) at thread.c:4710

  3. この時点では動作に直接的な影響は起きず、SystemStackError扱いのままプロセスの終了処理へ。

  4. altstackのfree時にmalloc headerが壊れているためabort。

r38409にて2.が起こらなくなったので、きれいにSystemStackErrorで終了するようになったものと理解しています。

なお、で報告した際にはそもそもSystemStackErrorにすらならなかったので
そのときに起きていた問題に対しr38409は有効ではない、というのはその通りだと思います。
こちらは詳細を追っていないので原因は分かっていません。

何か勘違いしてますかね?

#17 Updated by Yui NARUSE almost 2 years ago

SystemStackError になることを確認しました

% ./ruby -v nest.rb
ruby 2.1.0dev (2013-04-11 trunk 40238) [x86_64-freebsd9.1]
nest.rb:5: stack level too deep (SystemStackError)

Also available in: Atom PDF