From: Markus <markus@...>
Date: 2004-09-01T00:55:30+09:00
Subject: (Final) [PATCH] Subtle bug in bignum.c

This is a repost of the original problem description (edited to take
into account feedback from ruby-talk), with a new patch that is much
preferred that the original.  To the best of my knowledge this patch is
correct and complete and ready for incorporation.

--------------------------------------------------------------------------------------


I have found a rather subtle bug in the bitwise operators defined in
bignum.c.  With the kind and insightful assistance of Guy Decoux, the
cause was traced to gc reaping of temporary values used when one or more
of the arguments were negative.

TO DEMONSTRATE THE PROBLEM:

Run the following script.  It should produce no output (and occasionally
this is what happens).  But frequently, the values of a and b differ. 
This should not happen, but it does.  I have reproduced the problem on
several different machines, running several different flavors of linux. 

10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) & 0xFFFFFFFF
        b = (i*-12345) & 0xFFFFFFFF
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{b.to_s(2)}\n" if a != b
        }
    }

A similar problem can b shown with bitwise-or


10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) | 0
        b = (i*-12345) | 0
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{{b.to_s(2)}\n" if a != b
        }
    }


But the problem does NOT occur with bitwise-xor:

10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) ^ 0
        b = (i*-12345) ^ 0
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{{b.to_s(2)}\n" if a != b
        }
    }


OUR PATCH:

--- ruby-1.8.1.org/bignum.c	2003-12-22 02:25:49.000000000 -0700
+++ ruby-1.8.1/bignum.c	2004-08-31 08:40:03.000000000 -0700
@@ -1611,10 +1611,12 @@
  */
 
 VALUE
-rb_big_and(x, y)
-    VALUE x, y;
+rb_big_and(x_, y_)
+    VALUE x_, y_;
 {
     VALUE z;
+    volatile VALUE y = y_;  /* volatile to prevent garbage collector reaping */
+    volatile VALUE x = x_;
     BDIGIT *ds1, *ds2, *zds;
     long i, l1, l2;
     char sign;
@@ -1666,10 +1668,12 @@
  */
 
 VALUE
-rb_big_or(x, y)
-    VALUE x, y;
+rb_big_or(x_, y_)
+    VALUE x_, y_;
 {
     VALUE z;
+    volatile VALUE y = y_;  /* volatile to prevent garbage collector reaping */
+    volatile VALUE x = x_;
     BDIGIT *ds1, *ds2, *zds;
     long i, l1, l2;
     char sign;


I used GCC 3.2.2 & 3.3.2 when compiling ruby, from otherwise unmodified
1.8.1 sources.  I looked in CVS and saw no post 1.8.1 changes that
appeared relevant.
 
-- Markus (MQR) Roberts