commit 678c1255c92eed9c2c7564d340a5563b17395158
parent a4b96ce9a3305ae3585c0bb143fa7342c140f20b
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Wed, 1 Feb 2012 19:56:51 -0200
random seed used in the hash of all strings to avoid intentional
collisions
Diffstat:
5 files changed, 49 insertions(+), 12 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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));
