Create a gist now

Instantly share code, notes, and snippets.

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
rbriank commented Jan 3, 2012

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
kovyrin commented Jan 3, 2012

The patch is for 2011.03.

@rbriank
rbriank commented Jan 3, 2012

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