[PATCH] Re: Symbols overlap ordinary objects, especially on OS X (Was: Re: Problem with weak references on OS X 10.3)

On Mon, Feb 27, 2006 at 06:03:58PM +0900, Tanaka Akira wrote:
> In article <20060226171117.GB29508@tux-chan>,
>   Mauricio Fernandez <[e-mail]> writes:
> 
> >> so there can be a collision for VALUEs x such that x & 0x1f == 0x1c.
> >                                                          ====
> > 							 0xff
> 
> 0x1ff, I think.

Of course, but a second self-reply would have been too much noise.

I've tried to fix the bug by partitioning the ID space as follows:

                                         LSB
false       00000000000000000000000000000001      
true        00000000000000000000000000000101      
nil         00000000000000000000000000001001      
Fixnum  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx10001   |
symbol     ssssssssssssssssssssssss000011101   | expanded to Bignum when needed
object      oooooooooooooooooooooooooooooo11


The patch is not pretty but it seems to work:


Index: gc.c
===================================================================
RCS file: /src/ruby/gc.c,v
retrieving revision 1.233
diff -p -u -r1.233 gc.c
--- gc.c	13 Feb 2006 04:53:21 -0000	1.233
+++ gc.c	27 Feb 2006 11:47:00 -0000
@@ -1914,20 +1914,41 @@ id2ref(VALUE obj, VALUE id)
 #endif
     VALUE ptr;
     void *p0;
+    BDIGIT *digit;
 
     rb_secure(4);
-    ptr = NUM2PTR(id);
-    p0 = (void *)ptr;
+    
+    if (TYPE(id) == T_BIGNUM) {
+	digit = ((BDIGIT*)RBIGNUM(id)->digits);
+	if((*digit & 0xf) == FIXNUM_ID_MASK) {
+	    return rb_big_lshift(id, INT2FIX(-(FIXNUM_ID_SHIFT+1)));
+	}
+	else {
+	    ptr = NUM2PTR(id);
+	    p0 = (void *)ptr;
+	    if (SYMBOL_P(ptr) && rb_id2name(SYM2ID((VALUE)ptr)) != 0) {
+		return (VALUE)ptr;
+	    }
+	}
+    }
+    else {
+	ptr = NUM2PTR(id);
+	p0 = (void *)ptr;
+
+	if (ptr == Qtrue) return Qtrue;
+	if (ptr == Qfalse) return Qfalse;
+	if (ptr == Qnil) return Qnil;
+	if (SYMBOL_P(ptr) && rb_id2name(SYM2ID((VALUE)ptr)) != 0) {
+	    return (VALUE)ptr;
+	}
+	
+	if ((ptr & 0xf) == FIXNUM_ID_MASK) {
+	    return (VALUE)(ptr >> FIXNUM_ID_SHIFT);
+	}
 
-    if (ptr == Qtrue) return Qtrue;
-    if (ptr == Qfalse) return Qfalse;
-    if (ptr == Qnil) return Qnil;
-    if (FIXNUM_P(ptr)) return (VALUE)ptr;
-    if (SYMBOL_P(ptr) && rb_id2name(SYM2ID((VALUE)ptr)) != 0) {
-	return (VALUE)ptr;
+	ptr = id ^ IMMEDIATE_MASK;	/* unset IMMEDIATE_MASK */
     }
 
-    ptr = id ^ FIXNUM_FLAG;	/* unset FIXNUM_FLAG */
     if (!is_pointer_to_heap((void *)ptr)|| BUILTIN_TYPE(ptr) >= T_BLOCK) {
 	rb_raise(rb_eRangeError, "%p is not id value", p0);
     }
Index: object.c
===================================================================
RCS file: /src/ruby/object.c,v
retrieving revision 1.183
diff -p -u -r1.183 object.c
--- object.c	17 Jan 2006 14:05:49 -0000	1.183
+++ object.c	27 Feb 2006 11:47:01 -0000
@@ -128,10 +128,13 @@ rb_obj_equal(VALUE obj1, VALUE obj2)
 VALUE
 rb_obj_id(VALUE obj)
 {
-    if (SPECIAL_CONST_P(obj)) {
+    if (FIXNUM_P(obj)) {
+	return rb_big_lshift(rb_int2big(obj), INT2FIX(FIXNUM_ID_SHIFT));
+    }
+    if (SPECIAL_CONST_P(obj)) { /* will not include Fixnums */
 	return LONG2NUM((long)obj);
     }
-    return (VALUE)((long)obj|FIXNUM_FLAG);
+    return (VALUE)((long)obj|IMMEDIATE_MASK);
 }
 
 VALUE
Index: ruby.h
===================================================================
RCS file: /src/ruby/ruby.h,v
retrieving revision 1.133
diff -p -u -r1.133 ruby.h
--- ruby.h	5 Feb 2006 15:06:41 -0000	1.133
+++ ruby.h	27 Feb 2006 11:47:01 -0000
@@ -181,10 +181,13 @@ VALUE rb_ull2inum(unsigned LONG_LONG);
 #define IMMEDIATE_MASK 0x03
 #define IMMEDIATE_P(x) ((VALUE)(x) & IMMEDIATE_MASK)
 
+#define FIXNUM_ID_MASK 0x08
+#define FIXNUM_ID_SHIFT 3 
+
 #define SYMBOL_FLAG 0x0e
 #define SYMBOL_P(x) (((VALUE)(x)&0xff)==SYMBOL_FLAG)
 #define ID2SYM(x) ((VALUE)(((long)(x))<<8|SYMBOL_FLAG))
-#define SYM2ID(x) RSHIFT((long)x,8)
+#define SYM2ID(x) RSHIFT((unsigned long)x,8)
 
 /* special contants - i.e. non-zero and non-fixnum constants */
 #define Qfalse ((VALUE)0)




With this patch, object_id works as follows:

$ cat idtest.rb
def VALUE(obj)
  Object.instance_method(:to_s).bind(obj).call[/0x([a-f0-9]+)>/,1].to_i(16)
end

[true, false, nil, :has_key?, :fdsadddf, Object.new,
 2**30-1, 2**40, *(0..16).to_a].each do |x|
  i = x.object_id
  value = case i
    when Fixnum: VALUE(i)
    when Bignum: i
  end
  puts "%20s -> id(%s) %16d   ...%12s %s" % [x.inspect, i.class, i, (value & 0xfff).to_s(2),
                                    ObjectSpace._id2ref(i).inspect]
end

$ ./ruby19 idtest.rb
                true -> id(Fixnum)                2   ...         101 true
               false -> id(Fixnum)                0   ...           1 false
                 nil -> id(Fixnum)                4   ...        1001 nil
           :has_key? -> id(Fixnum)          1810190   ...111000011101 :has_key?
           :fdsadddf -> id(Fixnum)          2738446   ...  1000011101 :fdsadddf
#<Object:0xb7da3ea4> -> id(Fixnum)       -605216941   ...111010100111 #<Object:0xb7da3ea4>
          1073741823 -> id(Bignum)      17179869176   ...111111111000 1073741823
       1099511627776 -> id(Fixnum)       -605217151   ...110100000011 1099511627776
                   0 -> id(Fixnum)                8   ...       10001 0
                   1 -> id(Fixnum)               24   ...      110001 1
                   2 -> id(Fixnum)               40   ...     1010001 2
                   3 -> id(Fixnum)               56   ...     1110001 3
                   4 -> id(Fixnum)               72   ...    10010001 4
                   5 -> id(Fixnum)               88   ...    10110001 5
                   6 -> id(Fixnum)              104   ...    11010001 6
                   7 -> id(Fixnum)              120   ...    11110001 7
                   8 -> id(Fixnum)              136   ...   100010001 8
                   9 -> id(Fixnum)              152   ...   100110001 9
                  10 -> id(Fixnum)              168   ...   101010001 10
                  11 -> id(Fixnum)              184   ...   101110001 11
                  12 -> id(Fixnum)              200   ...   110010001 12
                  13 -> id(Fixnum)              216   ...   110110001 13
                  14 -> id(Fixnum)              232   ...   111010001 14
                  15 -> id(Fixnum)              248   ...   111110001 15
                  16 -> id(Fixnum)              264   ...  1000010001 16



-- 
Mauricio Fernandez  -   http://eigenclass.org   -  non-trivial Ruby