ruby-dev

In article <[email protected]>,
  Yukihiro Matsumoto <[email protected]> writes:

> |すでにほとんどソート済みの配列にたいしてはquick sortって不利では
> |なかったかと思うのですが。というか、void*同士の減算は規格上は不
> |可では。
>
> いや、気にならないでもなかったのですが、どうせそんなに大きな
> 配列にはなりそうになかったので、効率は無視しました。実装して
> くださったのでしたら断る理由はないのでコミットしてください。

その void* の減算は現実的に問題です。

手元の環境で、その変更以降、test-all で SEGV などの奇妙な挙
動が見られるのですが、原因がその減算でした。

以下のように assert をいれて確認したのですが、

Index: gc.c
===================================================================
--- gc.c	(revision 15675)
+++ gc.c	(working copy)
@@ -413,12 +413,24 @@ rb_gc_unregister_address(VALUE *addr)
     }
 }
 
+#include <assert.h>
 static int
 heap_cmp(const void *ap, const void *bp, void *dummy)
 {
     const struct heaps_slot *a = ap, *b = bp;
+    int ret;
 
-    return a->membase - b->membase;
+    ret = a->membase - b->membase;
+    if (a->membase < b->membase) {
+        assert(ret < 0);
+    }
+    if (a->membase > b->membase) {
+        assert(ret > 0);
+    }
+    if (a->membase == b->membase) {
+        assert(ret == 0);
+    }
+    return ret;
 }
 
 static void

手元の環境では、この減算で integer overflow が起きて、比較関
数として正しい値を返せていません。

Core was generated by `test/runner.rb test_gc(TestGc'.
Program terminated with signal 6, Aborted.
#0  0xb7f07410 in ?? ()
(gdb) up
#1  0xbf9eb3e8 in ?? ()
(gdb) 
#2  0x00000006 in ?? ()
(gdb) 
#3  0x00007d30 in ?? ()
(gdb) 
#4  0xb7d7c811 in raise () from /lib/tls/i686/cmov/libc.so.6
(gdb) 
#5  0xb7d7dfb9 in abort () from /lib/tls/i686/cmov/libc.so.6
(gdb) 
#6  0xb7d75fbf in __assert_fail () from /lib/tls/i686/cmov/libc.so.6
(gdb) 
#7  0x08062a21 in heap_cmp (ap=0x819dc20, bp=0x819dc38, dummy=0x0) at gc.c:428
428             assert(ret > 0);
(gdb) p ret
$1 = -1360121024
(gdb) p a->membase
$2 = (void *) 0xb79dc008
(gdb) p b->membase
$3 = (void *) 0x8af8cc8
(gdb) p a->membase - b->membase
$4 = -1360121024
(gdb) p a->membase > b->membase
$5 = 1
(gdb) 

つまり、
a->membase が 0xb79dc008 で、
b->membase が 0x8af8cc8 ですから、
b->membase のほうが小さくて、正の値を返すべきですが、
-1360121024 という負の値を返しています。

この結果として、正しくソートが行われず、is_pointer_to_heap
の2分探索がうまく動かずに不適切に偽を返し、回収すべきでない
オブジェクトが回収され、SEGV を含むいろいろと奇妙な現象が起
こっています。
-- 
[田中 哲][たなか あきら][Tanaka Akira]