random seed used in the hash of all strings to avoid intentional

collisions

5 files changed, 49 insertions, 12 deletions

diff --git a/lstate.c b/lstate.c
index bc13897b..5031a0a1 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,11 +1,12 @@
 /*
-** $Id: lstate.c,v 2.91 2011/08/23 17:24:34 roberto Exp roberto $
+** $Id: lstate.c,v 2.92 2011/10/03 17:54:25 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
 
 
 #include <stddef.h>
+#include <string.h>
 
 #define lstate_c
 #define LUA_CORE
@@ -42,6 +43,17 @@
 
 
 /*
+** a macro to help the creation of a unique random seed when a state is
+** created; the seed is used to randomize hashes.
+*/
+#if !defined(luai_makeseed)
+#include <time.h>
+#define luai_makeseed(L)        cast(size_t, time(NULL))
+#endif
+
+
+
+/*
 ** thread state + extra space
 */
 typedef struct LX {
@@ -66,6 +78,28 @@ typedef struct LG {
 
 
 /*
+** Compute an initial seed as random as possible. In ANSI, rely on
+** Address Space Layour Randomization (if present) to increase
+** randomness..
+*/
+#define addbuff(b,p,e) \
+  { size_t t = cast(size_t, e); \
+    memcpy(buff + p, &t, sizeof(t)); p += sizeof(t); }
+
+static unsigned int makeseed (lua_State *L) {
+  char buff[4 * sizeof(size_t)];
+  unsigned int h = luai_makeseed();
+  int p = 0;
+  addbuff(buff, p, L);  /* heap variable */
+  addbuff(buff, p, &h);  /* local variable */
+  addbuff(buff, p, luaO_nilobject);  /* global variable */
+  addbuff(buff, p, &lua_newstate);  /* public function */
+  lua_assert(p == sizeof(buff));
+  return luaS_hash(buff, p, h);
+}
+
+
+/*
 ** set GCdebt to a new value keeping the value (totalbytes + GCdebt)
 ** invariant
 */
@@ -242,6 +276,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
   g->frealloc = f;
   g->ud = ud;
   g->mainthread = L;
+  g->seed = makeseed(L);
   g->uvhead.u.l.prev = &g->uvhead;
   g->uvhead.u.l.next = &g->uvhead;
   g->gcrunning = 0;  /* no GC while building state */
diff --git a/lstate.h b/lstate.h
index 38a7fb36..f6c093b3 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.75 2012/01/20 22:05:50 roberto Exp roberto $
+** $Id: lstate.h,v 2.76 2012/01/25 21:05:40 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -116,6 +116,7 @@ typedef struct global_State {
   lu_mem lastmajormem;  /* memory in use after last major collection */
   stringtable strt;  /* hash table for strings */
   TValue l_registry;
+  unsigned int seed;  /* randomized seed for hashes */
   lu_byte currentwhite;
   lu_byte gcstate;  /* state of garbage collector */
   lu_byte gckind;  /* kind of GC running */
diff --git a/lstring.c b/lstring.c
index 75861cf4..a704af4e 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 2.19 2011/05/03 16:01:57 roberto Exp roberto $
+** $Id: lstring.c,v 2.21 2012/01/25 21:05:40 roberto Exp roberto $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -37,8 +37,8 @@ int luaS_eqstr (TString *a, TString *b) {
 }
 
 
-unsigned int luaS_hash (const char *str, size_t l) {
-  unsigned int h = cast(unsigned int, l);  /* seed */
+unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
+  unsigned int h = seed ^ l;
   size_t l1;
   for (l1 = 0; l1 < l; l1++)
     h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1]));
@@ -120,8 +120,9 @@ static TString *newshrstr (lua_State *L, const char *str, size_t l,
 */
 static TString *internshrstr (lua_State *L, const char *str, size_t l) {
   GCObject *o;
-  unsigned int h = luaS_hash(str, l);
-  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
+  global_State *g = G(L);
+  unsigned int h = luaS_hash(str, l, g->seed);
+  for (o = g->strt.hash[lmod(h, g->strt.size)];
        o != NULL;
        o = gch(o)->next) {
     TString *ts = rawgco2ts(o);
@@ -146,7 +147,7 @@ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
   else {
     if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
       luaM_toobig(L);
-    return createstrobj(L, str, l, LUA_TLNGSTR, 0, NULL);
+    return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL);
   }
 }
 
diff --git a/lstring.h b/lstring.h
index 6cfcbfcc..b52a9356 100644
--- a/lstring.h
+++ b/lstring.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.h,v 1.46 2010/04/05 16:26:37 roberto Exp roberto $
+** $Id: lstring.h,v 1.48 2012/01/25 21:05:40 roberto Exp roberto $
 ** String table (keep all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -34,7 +34,7 @@
 #define eqshrstr(a,b)   check_exp((a)->tsv.tt == LUA_TSHRSTR, (a) == (b))
 
 
-LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l);
+LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l, unsigned int seed);
 LUAI_FUNC int luaS_eqlngstr (TString *a, TString *b);
 LUAI_FUNC int luaS_eqstr (TString *a, TString *b);
 LUAI_FUNC void luaS_resize (lua_State *L, int newsize);
diff --git a/ltable.c b/ltable.c
index 3683fe60..adccb0a7 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltable.c,v 2.67 2011/11/30 12:41:45 roberto Exp roberto $
+** $Id: ltable.c,v 2.69 2012/01/25 21:05:40 roberto Exp roberto $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -101,7 +101,7 @@ static Node *mainposition (const Table *t, const TValue *key) {
     case LUA_TLNGSTR: {
       TString *s = rawtsvalue(key);
       if (s->tsv.extra == 0) {  /* no hash? */
-        s->tsv.hash = luaS_hash(getstr(s), s->tsv.len);
+        s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash);
         s->tsv.extra = 1;  /* now it has its hash */
       }
       return hashstr(t, rawtsvalue(key));