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 4f69a748ab820c6a8bd204f94d13d970847f575c Mon Sep 17 00:00:00 2001
From: RPM Builder <rpmbuild@livingsocial.com>
Date: Thu, 29 Dec 2011 19:48:52 +0000
Subject: [PATCH] Backport randomized hash patch from upstream
---
source/inits.c | 4 ++
source/random.c | 74 ++++++++++++++++++++++++++++++---------
source/st.c | 14 +++++++-
source/string.c | 7 +++-
source/test/ruby/test_string.rb | 13 +++++++
source/version.c | 2 +-
6 files changed, 94 insertions(+), 20 deletions(-)
diff --git a/source/inits.c b/source/inits.c
index 947bbbe..a0e061f 100644
--- a/source/inits.c
+++ b/source/inits.c
@@ -38,6 +38,7 @@ void Init_Precision _((void));
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_Struct _((void));
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/source/random.c b/source/random.c
index 258b0b2..790eda8 100644
--- a/source/random.c
+++ b/source/random.c
@@ -189,6 +189,7 @@ rb_genrand_real(void)
#include <fcntl.h>
#endif
+static int seed_initialized = 0;
static VALUE saved_seed = INT2FIX(0);
static VALUE
@@ -250,27 +251,22 @@ rand_init(vseed)
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 @@ random_seed()
#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 @@ random_seed()
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 @@ rb_f_rand(argc, argv, obj)
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,10 +513,27 @@ rb_f_rand(argc, argv, obj)
return LONG2NUM(val);
}
+static char initial_seed[DEFAULT_SEED_LEN];
+
+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/source/st.c b/source/st.c
index c16c310..21e157a 100644
--- a/source/st.c
+++ b/source/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 @@ st_foreach(table, func, arg)
return 0;
}
+static unsigned long hash_seed = 0;
+
static int
strhash(string)
register const char *string;
@@ -550,10 +553,11 @@ strhash(string)
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 @@ numhash(n)
{
return n;
}
+
+extern unsigned long rb_genrand_int32(void);
+
+void
+Init_st(void)
+{
+ hash_seed = rb_genrand_int32();
+}
diff --git a/source/string.c b/source/string.c
index c6b2301..94a0281 100644
--- a/source/string.c
+++ b/source/string.c
@@ -875,13 +875,15 @@ rb_str_concat(str1, str2)
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 @@ rb_str_hash(str)
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 @@ Init_String()
rb_fs = Qnil;
rb_define_variable("$;", &rb_fs);
rb_define_variable("$-F", &rb_fs);
+
+ hash_seed = rb_genrand_int32();
}
diff --git a/source/test/ruby/test_string.rb b/source/test/ruby/test_string.rb
index 5f2c54f..4d97182 100644
--- a/source/test/ruby/test_string.rb
+++ b/source/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 @@ class TestString < Test::Unit::TestCase
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
diff --git a/source/version.c b/source/version.c
index 8b41cc9..5781cab 100644
--- a/source/version.c
+++ b/source/version.c
@@ -46,7 +46,7 @@ Init_version()
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.6.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.