Created
December 29, 2011 18:51
-
-
Save kovyrin/1535569 to your computer and use it in GitHub Desktop.
Ruby EE 2011.03 Hash Collision Fix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
The patch is for 2011.03.
I saw that. I looks like it should be fine, but I must be missing something.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?