On Mon, Feb 27, 2006 at 06:03:58PM +0900, Tanaka Akira wrote:
> In article <20060226171117.GB29508 / tux-chan>,
>   Mauricio Fernandez <mfp / acm.org> 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