public

Ruby EE 2011.03 Hash Collision Fix

  • Download Gist
ruby-1.8.7-hash-randomize.patch
Diff
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
From e19bd3eaa8bd71cfc9e5bf436527f015b093f31e Mon Sep 17 00:00:00 2001
From: shyouhei <shyouhei@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Wed, 28 Dec 2011 12:47:15 +0000
Subject: [PATCH] -This line, and those below, will be ignored--
 
M ruby_1_8_7/inits.c
M ruby_1_8_7/string.c
M ruby_1_8_7/st.c
M ruby_1_8_7/test/ruby/test_string.rb
M ruby_1_8_7/random.c
 
 
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_8_7@34151 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
---
ChangeLog | 26 ++++++++++++++++
inits.c | 4 ++
random.c | 74 +++++++++++++++++++++++++++++++++++----------
st.c | 14 ++++++++-
string.c | 7 ++++-
test/ruby/test_string.rb | 13 ++++++++
version.h | 8 ++--
7 files changed, 123 insertions(+), 23 deletions(-)
 
diff --git a/inits.c b/inits.c
index 947bbbe..a0e061f 100644
--- a/inits.c
+++ b/inits.c
@@ -38,6 +38,7 @@
void Init_sym _((void));
void Init_process _((void));
void Init_Random _((void));
+void Init_RandomSeed _((void));
void Init_Range _((void));
void Init_Regexp _((void));
void Init_signal _((void));
@@ -46,10 +47,13 @@
void Init_Time _((void));
void Init_var_tables _((void));
void Init_version _((void));
+void Init_st _((void));
void
rb_call_inits()
{
+ Init_RandomSeed();
+ Init_st();
Init_sym();
Init_var_tables();
Init_Object();
diff --git a/random.c b/random.c
index c0560e3..24a0787 100644
--- a/random.c
+++ b/random.c
@@ -189,6 +189,7 @@
#include <fcntl.h>
#endif
+static int seed_initialized = 0;
static VALUE saved_seed = INT2FIX(0);
static VALUE
@@ -250,27 +251,22 @@
return old;
}
-static VALUE
-random_seed()
+#define DEFAULT_SEED_LEN (4 * sizeof(long))
+
+static void
+fill_random_seed(ptr)
+ char *ptr;
{
static int n = 0;
+ unsigned long *seed;
struct timeval tv;
int fd;
struct stat statbuf;
+ char *buf = (char*)ptr;
- int seed_len;
- BDIGIT *digits;
- unsigned long *seed;
- NEWOBJ(big, struct RBignum);
- OBJSETUP(big, rb_cBignum, T_BIGNUM);
-
- seed_len = 4 * sizeof(long);
- big->sign = 1;
- big->len = seed_len / SIZEOF_BDIGITS + 1;
- digits = big->digits = ALLOC_N(BDIGIT, big->len);
- seed = (unsigned long *)big->digits;
+ seed = (unsigned long *)buf;
- memset(digits, 0, big->len * SIZEOF_BDIGITS);
+ memset(buf, 0, DEFAULT_SEED_LEN);
#ifdef S_ISCHR
if ((fd = open("/dev/urandom", O_RDONLY
@@ -285,7 +281,7 @@
#endif
)) >= 0) {
if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) {
- read(fd, seed, seed_len);
+ read(fd, seed, DEFAULT_SEED_LEN);
}
close(fd);
}
@@ -296,13 +292,37 @@
seed[1] ^= tv.tv_sec;
seed[2] ^= getpid() ^ (n++ << 16);
seed[3] ^= (unsigned long)&seed;
+}
+
+static VALUE
+make_seed_value(char *ptr)
+{
+ BDIGIT *digits;
+ NEWOBJ(big, struct RBignum);
+ OBJSETUP(big, rb_cBignum, T_BIGNUM);
+
+ RBIGNUM_SET_SIGN(big, 1);
+
+ digits = ALLOC_N(char, DEFAULT_SEED_LEN);
+ RBIGNUM(big)->digits = digits;
+ RBIGNUM(big)->len = DEFAULT_SEED_LEN / SIZEOF_BDIGITS;
+
+ MEMCPY(digits, ptr, char, DEFAULT_SEED_LEN);
/* set leading-zero-guard if need. */
- digits[big->len-1] = digits[big->len-2] <= 1 ? 1 : 0;
+ digits[RBIGNUM_LEN(big)-1] = digits[RBIGNUM_LEN(big)-2] <= 1 ? 1 : 0;
return rb_big_norm((VALUE)big);
}
+static VALUE
+random_seed(void)
+{
+ char buf[DEFAULT_SEED_LEN];
+ fill_random_seed(buf);
+ return make_seed_value(buf);
+}
+
/*
* call-seq:
* srand(number=0) => old_seed
@@ -443,6 +463,9 @@
long val, max;
rb_scan_args(argc, argv, "01", &vmax);
+ if (!seed_initialized) {
+ rand_init(random_seed());
+ }
switch (TYPE(vmax)) {
case T_FLOAT:
if (RFLOAT(vmax)->value <= LONG_MAX && RFLOAT(vmax)->value >= LONG_MIN) {
@@ -490,6 +513,8 @@
return LONG2NUM(val);
}
+static char initial_seed[DEFAULT_SEED_LEN];
+
void
rb_reset_random_seed()
{
@@ -497,9 +522,24 @@
}
void
+Init_RandomSeed(void)
+{
+ fill_random_seed(initial_seed);
+ init_by_array((unsigned long*)initial_seed, DEFAULT_SEED_LEN/sizeof(unsigned long));
+ seed_initialized = 1;
+}
+
+static void
+Init_RandomSeed2(void)
+{
+ saved_seed = make_seed_value(initial_seed);
+ memset(initial_seed, 0, DEFAULT_SEED_LEN);
+}
+
+void
Init_Random()
{
- rand_init(random_seed());
+ Init_RandomSeed2();
rb_define_global_function("srand", rb_f_srand, -1);
rb_define_global_function("rand", rb_f_rand, -1);
rb_global_variable(&saved_seed);
diff --git a/st.c b/st.c
index c16c310..21e157a 100644
--- a/st.c
+++ b/st.c
@@ -9,6 +9,7 @@
#include <stdlib.h>
#endif
#include <string.h>
+#include <limits.h>
#include "st.h"
typedef struct st_table_entry st_table_entry;
@@ -521,6 +522,8 @@ struct st_table_entry {
return 0;
}
+static unsigned long hash_seed = 0;
+
static int
strhash(string)
register const char *string;
@@ -550,10 +553,11 @@ struct st_table_entry {
return val + (val << 15);
#else
- register int val = 0;
+ register unsigned long val = hash_seed;
while ((c = *string++) != '\0') {
val = val*997 + c;
+ val = (val << 13) | (val >> (sizeof(st_data_t) * CHAR_BIT - 13));
}
return val + (val>>5);
@@ -573,3 +577,11 @@ struct st_table_entry {
{
return n;
}
+
+extern unsigned long rb_genrand_int32(void);
+
+void
+Init_st(void)
+{
+ hash_seed = rb_genrand_int32();
+}
diff --git a/string.c b/string.c
index c6b2301..94a0281 100644
--- a/string.c
+++ b/string.c
@@ -875,13 +875,15 @@
return str1;
}
+static unsigned long hash_seed;
+
int
rb_str_hash(str)
VALUE str;
{
register long len = RSTRING(str)->len;
register char *p = RSTRING(str)->ptr;
- register int key = 0;
+ register unsigned long key = hash_seed;
#if defined(HASH_ELFHASH)
register unsigned int g;
@@ -905,6 +907,7 @@
while (len--) {
key = key*65599 + *p;
p++;
+ key = (key << 13) | (key >> ((sizeof(unsigned long) * CHAR_BIT) - 13));
}
key = key + (key>>5);
#endif
@@ -5062,4 +5065,6 @@ struct tr {
rb_fs = Qnil;
rb_define_variable("$;", &rb_fs);
rb_define_variable("$-F", &rb_fs);
+
+ hash_seed = rb_genrand_int32();
}
diff --git a/test/ruby/test_string.rb b/test/ruby/test_string.rb
index 5f2c54f..4d97182 100644
--- a/test/ruby/test_string.rb
+++ b/test/ruby/test_string.rb
@@ -1,4 +1,5 @@
require 'test/unit'
+require File.expand_path('envutil', File.dirname(__FILE__))
class TestString < Test::Unit::TestCase
def check_sum(str, bits=16)
@@ -29,4 +30,16 @@ def test_inspect
ensure
$KCODE = original_kcode
end
+
+ def test_hash_random
+ str = 'abc'
+ a = [str.hash.to_s]
+ cmd = sprintf("%s -e 'print %s.hash'", EnvUtil.rubybin, str.dump)
+ 3.times {
+ IO.popen(cmd, "rb") {|o|
+ a << o.read
+ }
+ }
+ assert_not_equal([str.hash.to_s], a.uniq)
+ end
end
 
--- a/version.c 2011-12-19 03:22:43.000000000 +0000
+++ b/version.c 2011-12-29 18:18:58.000000000 +0000
@@ -46,7 +46,7 @@
rb_define_global_const("RUBY_PATCHLEVEL", INT2FIX(RUBY_PATCHLEVEL));
snprintf(description, sizeof(description),
- "ruby %s (%s %s %d) [%s], MBARI 0x%x, Ruby Enterprise Edition %s",
+ "ruby %s (%s %s %d) [%s], MBARI 0x%x, Ruby Enterprise Edition %s (with hash random)",
RUBY_VERSION, RUBY_RELEASE_DATE, RUBY_RELEASE_STR,
RUBY_RELEASE_NUM, RUBY_PLATFORM,
STACK_WIPE_SITES, REE_VERSION);
--
1.7.5.4

I'm trying to apply this to 1.8.7-2009.10, but I get an error in st.c:

gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c random.c
random.c: In function ‘make_seed_value’:
random.c:306: warning: assignment from incompatible pointer type
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c range.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c re.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c regex.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c ruby.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c signal.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c sprintf.c
gcc -g -Os -fno-strict-aliasing -DRUBY_EXPORT -D_GNU_SOURCE=1 -I. -I. -c st.c
st.c:230:49: error: '#' is not followed by a macro parameter
make: *** [st.o] Error 1

Any idea what the problem could be? Or, am I missing some compiler flags maybe?

The patch is for 2011.03.

I saw that. I looks like it should be fine, but I must be missing something.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.