Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Ruby EE 2011.03 Hash Collision Fix
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
@rbriank

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?

@kovyrin
Owner

The patch is for 2011.03.

@rbriank

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
Something went wrong with that request. Please try again.