Redesign and harden string interning.

Up to 40% faster on hash-intensive benchmarks.
With some ideas from Sokolov Yura.

22 files changed, 394 insertions, 202 deletions

diff --git a/src/Makefile b/src/Makefile
index 6a9de5db..178a5acd 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -132,7 +132,6 @@ XCFLAGS=
 #
 # This define is required to run LuaJIT under Valgrind. The Valgrind
 # header files must be installed. You should enable debug information, too.
-# Use --suppressions=lj.supp to avoid some false positives.
 #XCFLAGS+= -DLUAJIT_USE_VALGRIND
 #
 # This is the client for the GDB JIT API. GDB 7.0 or higher is required
diff --git a/src/lj.supp b/src/lj.supp
deleted file mode 100644
index 217f7c89..00000000
--- a/src/lj.supp
+++ /dev/null
@@ -1,41 +0,0 @@
-# Valgrind suppression file for LuaJIT 2.0.
-{
-   Optimized string compare
-   Memcheck:Addr4
-   fun:lj_str_cmp
-}
-{
-   Optimized string compare
-   Memcheck:Addr1
-   fun:lj_str_cmp
-}
-{
-   Optimized string compare
-   Memcheck:Addr4
-   fun:lj_str_new
-}
-{
-   Optimized string compare
-   Memcheck:Addr1
-   fun:lj_str_new
-}
-{
-   Optimized string compare
-   Memcheck:Cond
-   fun:lj_str_new
-}
-{
-   Optimized string compare
-   Memcheck:Addr4
-   fun:str_fastcmp
-}
-{
-   Optimized string compare
-   Memcheck:Addr1
-   fun:str_fastcmp
-}
-{
-   Optimized string compare
-   Memcheck:Cond
-   fun:str_fastcmp
-}
diff --git a/src/lj_arch.h b/src/lj_arch.h
index 626f6c13..f148b3f7 100644
--- a/src/lj_arch.h
+++ b/src/lj_arch.h
@@ -637,14 +637,31 @@ extern void *LJ_WIN_LOADLIBA(const char *path);
 
 /* Don't make any changes here. Instead build with:
 **   make "XCFLAGS=-DLUAJIT_SECURITY_flag=value"
+**
+** Important note to distro maintainers: DO NOT change the defaults for a
+** regular distro build -- neither upwards, nor downwards!
+** These build-time configurable security flags are intended for embedders
+** who may have specific needs wrt. security vs. performance.
 */
 
 /* Security defaults. */
 #ifndef LUAJIT_SECURITY_PRNG
+/* PRNG init: 0 = fixed/insecure, 1 = secure from OS. */
 #define LUAJIT_SECURITY_PRNG    1
 #endif
 
+#ifndef LUAJIT_SECURITY_STRHASH
+/* String hash: 0 = sparse only, 1 = sparse + dense. */
+#define LUAJIT_SECURITY_STRHASH 1
+#endif
+
+#ifndef LUAJIT_SECURITY_STRID
+/* String IDs: 0 = linear, 1 = reseed < 255, 2 = reseed < 15, 3 = random. */
+#define LUAJIT_SECURITY_STRID   1
+#endif
+
 #ifndef LUAJIT_SECURITY_MCODE
+/* Machine code page protection: 0 = insecure RWX, 1 = secure RW^X. */
 #define LUAJIT_SECURITY_MCODE   1
 #endif
 
diff --git a/src/lj_asm.c b/src/lj_asm.c
index 2659c8a2..cc7841c0 100644
--- a/src/lj_asm.c
+++ b/src/lj_asm.c
@@ -1029,7 +1029,7 @@ static uint32_t ir_khash(ASMState *as, IRIns *ir)
   uint32_t lo, hi;
   UNUSED(as);
   if (irt_isstr(ir->t)) {
-    return ir_kstr(ir)->hash;
+    return ir_kstr(ir)->sid;
   } else if (irt_isnum(ir->t)) {
     lo = ir_knum(ir)->u32.lo;
     hi = ir_knum(ir)->u32.hi << 1;
diff --git a/src/lj_asm_arm.h b/src/lj_asm_arm.h
index d2fad141..e7d2bf17 100644
--- a/src/lj_asm_arm.h
+++ b/src/lj_asm_arm.h
@@ -825,10 +825,10 @@ static void asm_href(ASMState *as, IRIns *ir, IROp merge)
   } else {
     emit_dnm(as, ARMI_ADD|ARMF_SH(ARMSH_LSL, 3), dest, dest, tmp);
     emit_dnm(as, ARMI_ADD|ARMF_SH(ARMSH_LSL, 1), tmp, tmp, tmp);
-    if (irt_isstr(kt)) {  /* Fetch of str->hash is cheaper than ra_allock. */
+    if (irt_isstr(kt)) {  /* Fetch of str->sid is cheaper than ra_allock. */
       emit_dnm(as, ARMI_AND, tmp, tmp+1, RID_TMP);
       emit_lso(as, ARMI_LDR, dest, tab, (int32_t)offsetof(GCtab, node));
-      emit_lso(as, ARMI_LDR, tmp+1, key, (int32_t)offsetof(GCstr, hash));
+      emit_lso(as, ARMI_LDR, tmp+1, key, (int32_t)offsetof(GCstr, sid));
       emit_lso(as, ARMI_LDR, RID_TMP, tab, (int32_t)offsetof(GCtab, hmask));
     } else if (irref_isk(refkey)) {
       emit_opk(as, ARMI_AND, tmp, RID_TMP, (int32_t)khash,
diff --git a/src/lj_asm_arm64.h b/src/lj_asm_arm64.h
index 0729a3a5..b1fd3acc 100644
--- a/src/lj_asm_arm64.h
+++ b/src/lj_asm_arm64.h
@@ -847,9 +847,9 @@ static void asm_href(ASMState *as, IRIns *ir, IROp merge)
       emit_dnm(as, A64I_ANDw, dest, dest, tmphash);
       emit_lso(as, A64I_LDRw, dest, tab, offsetof(GCtab, hmask));
     } else if (irt_isstr(kt)) {
-      /* Fetch of str->hash is cheaper than ra_allock. */
+      /* Fetch of str->sid is cheaper than ra_allock. */
       emit_dnm(as, A64I_ANDw, dest, dest, tmp);
-      emit_lso(as, A64I_LDRw, tmp, key, offsetof(GCstr, hash));
+      emit_lso(as, A64I_LDRw, tmp, key, offsetof(GCstr, sid));
       emit_lso(as, A64I_LDRw, dest, tab, offsetof(GCtab, hmask));
     } else {  /* Must match with hash*() in lj_tab.c. */
       emit_dnm(as, A64I_ANDw, dest, dest, tmp);
diff --git a/src/lj_asm_mips.h b/src/lj_asm_mips.h
index a2b8d8e0..513bd5ca 100644
--- a/src/lj_asm_mips.h
+++ b/src/lj_asm_mips.h
@@ -1041,7 +1041,7 @@ static void asm_href(ASMState *as, IRIns *ir, IROp merge)
     if (isk) {
       /* Nothing to do. */
     } else if (irt_isstr(kt)) {
-      emit_tsi(as, MIPSI_LW, tmp1, key, (int32_t)offsetof(GCstr, hash));
+      emit_tsi(as, MIPSI_LW, tmp1, key, (int32_t)offsetof(GCstr, sid));
     } else {  /* Must match with hash*() in lj_tab.c. */
       emit_dst(as, MIPSI_SUBU, tmp1, tmp1, tmp2);
       emit_rotr(as, tmp2, tmp2, dest, (-HASH_ROT3)&31);
diff --git a/src/lj_asm_ppc.h b/src/lj_asm_ppc.h
index 498fdac3..77ab09d6 100644
--- a/src/lj_asm_ppc.h
+++ b/src/lj_asm_ppc.h
@@ -721,7 +721,7 @@ static void asm_href(ASMState *as, IRIns *ir, IROp merge)
     if (isk) {
       /* Nothing to do. */
     } else if (irt_isstr(kt)) {
-      emit_tai(as, PPCI_LWZ, tmp1, key, (int32_t)offsetof(GCstr, hash));
+      emit_tai(as, PPCI_LWZ, tmp1, key, (int32_t)offsetof(GCstr, sid));
     } else {  /* Must match with hash*() in lj_tab.c. */
       emit_tab(as, PPCI_SUBF, tmp1, tmp2, tmp1);
       emit_rotlwi(as, tmp2, tmp2, HASH_ROT3);
diff --git a/src/lj_asm_x86.h b/src/lj_asm_x86.h
index a3adee14..e40b5e54 100644
--- a/src/lj_asm_x86.h
+++ b/src/lj_asm_x86.h
@@ -1228,7 +1228,7 @@ static void asm_href(ASMState *as, IRIns *ir, IROp merge)
       emit_gri(as, XG_ARITHi(XOg_AND), dest, (int32_t)khash);
       emit_rmro(as, XO_MOV, dest, tab, offsetof(GCtab, hmask));
     } else if (irt_isstr(kt)) {
-      emit_rmro(as, XO_ARITH(XOg_AND), dest, key, offsetof(GCstr, hash));
+      emit_rmro(as, XO_ARITH(XOg_AND), dest, key, offsetof(GCstr, sid));
       emit_rmro(as, XO_MOV, dest, tab, offsetof(GCtab, hmask));
     } else {  /* Must match with hashrot() in lj_tab.c. */
       emit_rmro(as, XO_ARITH(XOg_AND), dest, tab, offsetof(GCtab, hmask));
diff --git a/src/lj_gc.c b/src/lj_gc.c
index 671b5983..cc4232a6 100644
--- a/src/lj_gc.c
+++ b/src/lj_gc.c
@@ -417,6 +417,32 @@ static GCRef *gc_sweep(global_State *g, GCRef *p, uint32_t lim)
   return p;
 }
 
+/* Sweep one string interning table chain. Preserves hashalg bit. */
+static void gc_sweepstr(global_State *g, GCRef *chain)
+{
+  /* Mask with other white and LJ_GC_FIXED. Or LJ_GC_SFIXED on shutdown. */
+  int ow = otherwhite(g);
+  uintptr_t u = gcrefu(*chain);
+  GCRef q;
+  GCRef *p = &q;
+  GCobj *o;
+  setgcrefp(q, (u & ~(uintptr_t)1));
+  while ((o = gcref(*p)) != NULL) {
+    if (((o->gch.marked ^ LJ_GC_WHITES) & ow)) {  /* Black or current white? */
+      lj_assertG(!isdead(g, o) || (o->gch.marked & LJ_GC_FIXED),
+                 "sweep of undead string");
+      makewhite(g, o);  /* String is alive, change to the current white. */
+      p = &o->gch.nextgc;
+    } else {  /* Otherwise string is dead, free it. */
+      lj_assertG(isdead(g, o) || ow == LJ_GC_SFIXED,
+                 "sweep of unlive string");
+      setgcrefr(*p, o->gch.nextgc);
+      lj_str_free(g, gco2str(o));
+    }
+  }
+  setgcrefp(*chain, (gcrefu(q) | (u & 1)));
+}
+
 /* Check whether we can clear a key or a value slot from a table. */
 static int gc_mayclear(cTValue *o, int val)
 {
@@ -571,9 +597,9 @@ void lj_gc_freeall(global_State *g)
   /* Free everything, except super-fixed objects (the main thread). */
   g->gc.currentwhite = LJ_GC_WHITES | LJ_GC_SFIXED;
   gc_fullsweep(g, &g->gc.root);
-  strmask = g->strmask;
+  strmask = g->str.mask;
   for (i = 0; i <= strmask; i++)  /* Free all string hash chains. */
-    gc_fullsweep(g, &g->strhash[i]);
+    gc_sweepstr(g, &g->str.tab[i]);
 }
 
 /* -- Collector ----------------------------------------------------------- */
@@ -636,8 +662,8 @@ static size_t gc_onestep(lua_State *L)
     return 0;
   case GCSsweepstring: {
     GCSize old = g->gc.total;
-    gc_fullsweep(g, &g->strhash[g->gc.sweepstr++]);  /* Sweep one chain. */
-    if (g->gc.sweepstr > g->strmask)
+    gc_sweepstr(g, &g->str.tab[g->gc.sweepstr++]);  /* Sweep one chain. */
+    if (g->gc.sweepstr > g->str.mask)
       g->gc.state = GCSsweep;  /* All string hash chains sweeped. */
     lj_assertG(old >= g->gc.total, "sweep increased memory");
     g->gc.estimate -= old - g->gc.total;
@@ -649,8 +675,8 @@ static size_t gc_onestep(lua_State *L)
     lj_assertG(old >= g->gc.total, "sweep increased memory");
     g->gc.estimate -= old - g->gc.total;
     if (gcref(*mref(g->gc.sweep, GCRef)) == NULL) {
-      if (g->strnum <= (g->strmask >> 2) && g->strmask > LJ_MIN_STRTAB*2-1)
-        lj_str_resize(L, g->strmask >> 1);  /* Shrink string table. */
+      if (g->str.num <= (g->str.mask >> 2) && g->str.mask > LJ_MIN_STRTAB*2-1)
+        lj_str_resize(L, g->str.mask >> 1);  /* Shrink string table. */
       if (gcref(g->gc.mmudata)) {  /* Need any finalizations? */
         g->gc.state = GCSfinalize;
 #if LJ_HASFFI
diff --git a/src/lj_obj.h b/src/lj_obj.h
index 6c974812..9d4bec08 100644
--- a/src/lj_obj.h
+++ b/src/lj_obj.h
@@ -13,7 +13,7 @@
 #include "lj_def.h"
 #include "lj_arch.h"
 
-/* -- Memory references (32 bit address space) ---------------------------- */
+/* -- Memory references --------------------------------------------------- */
 
 /* Memory and GC object sizes. */
 typedef uint32_t MSize;
@@ -44,7 +44,7 @@ typedef struct MRef {
 #define setmrefr(r, v)  ((r).ptr32 = (v).ptr32)
 #endif
 
-/* -- GC object references (32 bit address space) ------------------------- */
+/* -- GC object references ------------------------------------------------ */
 
 /* GCobj reference */
 typedef struct GCRef {
@@ -287,12 +287,16 @@ typedef const TValue cTValue;
 
 /* -- String object ------------------------------------------------------- */
 
+typedef uint32_t StrHash;       /* String hash value. */
+typedef uint32_t StrID;         /* String ID. */
+
 /* String object header. String payload follows. */
 typedef struct GCstr {
   GCHeader;
   uint8_t reserved;     /* Used by lexer for fast lookup of reserved words. */
-  uint8_t unused;
-  MSize hash;           /* Hash of string. */
+  uint8_t hashalg;      /* Hash algorithm. */
+  StrID sid;            /* Interned string ID. */
+  StrHash hash;         /* Hash of string. */
   MSize len;            /* Size of string. */
 } GCstr;
 
@@ -300,7 +304,6 @@ typedef struct GCstr {
 #define strdata(s)      ((const char *)((s)+1))
 #define strdatawr(s)    ((char *)((s)+1))
 #define strVdata(o)     strdata(strV(o))
-#define sizestring(s)   (sizeof(struct GCstr)+(s)->len+1)
 
 /* -- Userdata object ----------------------------------------------------- */
 
@@ -570,6 +573,7 @@ typedef enum {
 #define basemt_obj(g, o)        ((g)->gcroot[GCROOT_BASEMT+itypemap(o)])
 #define mmname_str(g, mm)       (strref((g)->gcroot[GCROOT_MMNAME+(mm)]))
 
+/* Garbage collector state. */
 typedef struct GCState {
   GCSize total;         /* Memory currently allocated. */
   GCSize threshold;     /* Memory threshold. */
@@ -590,25 +594,36 @@ typedef struct GCState {
   MSize pause;          /* Pause between successive GC cycles. */
 } GCState;
 
+/* String interning state. */
+typedef struct StrInternState {
+  GCRef *tab;           /* String hash table anchors. */
+  MSize mask;           /* String hash mask (size of hash table - 1). */
+  MSize num;            /* Number of strings in hash table. */
+  StrID id;             /* Next string ID. */
+  uint8_t idreseed;     /* String ID reseed counter. */
+  uint8_t second;       /* String interning table uses secondary hashing. */
+  uint8_t unused1;
+  uint8_t unused2;
+  LJ_ALIGN(8) uint64_t seed;    /* Random string seed. */
+} StrInternState;
+
 /* Global state, shared by all threads of a Lua universe. */
 typedef struct global_State {
-  GCRef *strhash;       /* String hash table (hash chain anchors). */
-  MSize strmask;        /* String hash mask (size of hash table - 1). */
-  MSize strnum;         /* Number of strings in hash table. */
   lua_Alloc allocf;     /* Memory allocator. */
   void *allocd;         /* Memory allocator data. */
   GCState gc;           /* Garbage collector. */
-  volatile int32_t vmstate;  /* VM state or current JIT code trace number. */
-  SBuf tmpbuf;          /* Temporary string buffer. */
   GCstr strempty;       /* Empty string. */
   uint8_t stremptyz;    /* Zero terminator of empty string. */
   uint8_t hookmask;     /* Hook mask. */
   uint8_t dispatchmode; /* Dispatch mode. */
   uint8_t vmevmask;     /* VM event mask. */
+  StrInternState str;   /* String interning. */
+  volatile int32_t vmstate;  /* VM state or current JIT code trace number. */
   GCRef mainthref;      /* Link to main thread. */
-  TValue registrytv;    /* Anchor for registry. */
+  SBuf tmpbuf;          /* Temporary string buffer. */
   TValue tmptv, tmptv2; /* Temporary TValues. */
   Node nilnode;         /* Fallback 1-element hash part (nil key and value). */
+  TValue registrytv;    /* Anchor for registry. */
   GCupval uvhead;       /* Head of double-linked list of all open upvalues. */
   int32_t hookcount;    /* Instruction hook countdown. */
   int32_t hookcstart;   /* Start count for instruction hook counter. */
diff --git a/src/lj_state.c b/src/lj_state.c
index a4d072be..4f77e71f 100644
--- a/src/lj_state.c
+++ b/src/lj_state.c
@@ -150,7 +150,7 @@ static TValue *cpluaopen(lua_State *L, lua_CFunction dummy, void *ud)
   /* NOBARRIER: State initialization, all objects are white. */
   setgcref(L->env, obj2gco(lj_tab_new(L, 0, LJ_MIN_GLOBAL)));
   settabV(L, registry(L), lj_tab_new(L, 0, LJ_MIN_REGISTRY));
-  lj_str_resize(L, LJ_MIN_STRTAB-1);
+  lj_str_init(L);
   lj_meta_init(L);
   lj_lex_init(L);
   fixstring(lj_err_str(L, LJ_ERR_ERRMEM));  /* Preallocate memory error msg. */
@@ -166,12 +166,12 @@ static void close_state(lua_State *L)
   lj_gc_freeall(g);
   lj_assertG(gcref(g->gc.root) == obj2gco(L),
              "main thread is not first GC object");
-  lj_assertG(g->strnum == 0, "leaked %d strings", g->strnum);
+  lj_assertG(g->str.num == 0, "leaked %d strings", g->str.num);
   lj_trace_freestate(g);
 #if LJ_HASFFI
   lj_ctype_freestate(g);
 #endif
-  lj_mem_freevec(g, g->strhash, g->strmask+1, GCRef);
+  lj_str_freetab(g);
   lj_buf_free(g, &g->tmpbuf);
   lj_mem_freevec(g, tvref(L->stack), L->stacksize, TValue);
   lj_assertG(g->gc.total == sizeof(GG_State),
@@ -231,7 +231,7 @@ LUA_API lua_State *lua_newstate(lua_Alloc allocf, void *allocd)
   setgcref(g->mainthref, obj2gco(L));
   setgcref(g->uvhead.prev, obj2gco(&g->uvhead));
   setgcref(g->uvhead.next, obj2gco(&g->uvhead));
-  g->strmask = ~(MSize)0;
+  g->str.mask = ~(MSize)0;
   setnilV(registry(L));
   setnilV(&g->nilnode.val);
   setnilV(&g->nilnode.key);
diff --git a/src/lj_str.c b/src/lj_str.c
index 0253c15e..5bf8426c 100644
--- a/src/lj_str.c
+++ b/src/lj_str.c
@@ -11,6 +11,7 @@
 #include "lj_err.h"
 #include "lj_str.h"
 #include "lj_char.h"
+#include "lj_prng.h"
 
 /* -- String helpers ------------------------------------------------------ */
 
@@ -37,28 +38,6 @@ int32_t LJ_FASTCALL lj_str_cmp(GCstr *a, GCstr *b)
   return (int32_t)(a->len - b->len);
 }
 
-/* Fast string data comparison. Caveat: unaligned access to 1st string! */
-static LJ_AINLINE int str_fastcmp(const char *a, const char *b, MSize len)
-{
-  MSize i = 0;
-  lj_assertX(len > 0, "fast string compare with zero length");
-  lj_assertX((((uintptr_t)a+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4,
-             "fast string compare crossing page boundary");
-  do {  /* Note: innocuous access up to end of string + 3. */
-    uint32_t v = lj_getu32(a+i) ^ *(const uint32_t *)(b+i);
-    if (v) {
-      i -= len;
-#if LJ_LE
-      return (int32_t)i >= -3 ? (v << (32+(i<<3))) : 1;
-#else
-      return (int32_t)i >= -3 ? (v >> (32+(i<<3))) : 1;
-#endif
-    }
-    i += 4;
-  } while (i < len);
-  return 0;
-}
-
 /* Find fixed string p inside string s. */
 const char *lj_str_find(const char *s, const char *p, MSize slen, MSize plen)
 {
@@ -91,108 +70,301 @@ int lj_str_haspattern(GCstr *s)
   return 0;  /* No pattern matching chars found. */
 }
 
-/* -- String interning ---------------------------------------------------- */
-
-/* Resize the string hash table (grow and shrink). */
-void lj_str_resize(lua_State *L, MSize newmask)
-{
-  global_State *g = G(L);
-  GCRef *newhash;
-  MSize i;
-  if (g->gc.state == GCSsweepstring || newmask >= LJ_MAX_STRTAB-1)
-    return;  /* No resizing during GC traversal or if already too big. */
-  newhash = lj_mem_newvec(L, newmask+1, GCRef);
-  memset(newhash, 0, (newmask+1)*sizeof(GCRef));
-  for (i = g->strmask; i != ~(MSize)0; i--) {  /* Rehash old table. */
-    GCobj *p = gcref(g->strhash[i]);
-    while (p) {  /* Follow each hash chain and reinsert all strings. */
-      MSize h = gco2str(p)->hash & newmask;
-      GCobj *next = gcnext(p);
-      /* NOBARRIER: The string table is a GC root. */
-      setgcrefr(p->gch.nextgc, newhash[h]);
-      setgcref(newhash[h], p);
-      p = next;
-    }
-  }
-  lj_mem_freevec(g, g->strhash, g->strmask+1, GCRef);
-  g->strmask = newmask;
-  g->strhash = newhash;
-}
+/* -- String hashing ------------------------------------------------------ */
 
-/* Intern a string and return string object. */
-GCstr *lj_str_new(lua_State *L, const char *str, size_t lenx)
+/* Keyed sparse ARX string hash. Constant time. */
+static StrHash hash_sparse(uint64_t seed, const char *str, MSize len)
 {
-  global_State *g;
-  GCstr *s;
-  GCobj *o;
-  MSize len = (MSize)lenx;
-  MSize a, b, h = len;
-  if (lenx >= LJ_MAX_STR)
-    lj_err_msg(L, LJ_ERR_STROV);
-  g = G(L);
-  /* Compute string hash. Constants taken from lookup3 hash by Bob Jenkins. */
+  /* Constants taken from lookup3 hash by Bob Jenkins. */
+  StrHash a, b, h = len ^ (StrHash)seed;
   if (len >= 4) {  /* Caveat: unaligned access! */
     a = lj_getu32(str);
     h ^= lj_getu32(str+len-4);
     b = lj_getu32(str+(len>>1)-2);
     h ^= b; h -= lj_rol(b, 14);
     b += lj_getu32(str+(len>>2)-1);
-  } else if (len > 0) {
+  } else {
     a = *(const uint8_t *)str;
     h ^= *(const uint8_t *)(str+len-1);
     b = *(const uint8_t *)(str+(len>>1));
     h ^= b; h -= lj_rol(b, 14);
-  } else {
-    return &g->strempty;
   }
   a ^= h; a -= lj_rol(h, 11);
   b ^= a; b -= lj_rol(a, 25);
   h ^= b; h -= lj_rol(b, 16);
-  /* Check if the string has already been interned. */
-  o = gcref(g->strhash[h & g->strmask]);
-  if (LJ_LIKELY((((uintptr_t)str+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4)) {
-    while (o != NULL) {
-      GCstr *sx = gco2str(o);
-      if (sx->len == len && str_fastcmp(str, strdata(sx), len) == 0) {
-        /* Resurrect if dead. Can only happen with fixstring() (keywords). */
-        if (isdead(g, o)) flipwhite(o);
-        return sx;  /* Return existing string. */
+  return h;
+}
+
+#if LUAJIT_SECURITY_STRHASH
+/* Keyed dense ARX string hash. Linear time. */
+static LJ_NOINLINE StrHash hash_dense(uint64_t seed, StrHash h,
+                                      const char *str, MSize len)
+{
+  StrHash b = lj_bswap(lj_rol(h ^ (StrHash)(seed >> 32), 4));
+  if (len > 12) {
+    StrHash a = (StrHash)seed;
+    const char *pe = str+len-12, *p = pe, *q = str;
+    do {
+      a += lj_getu32(p);
+      b += lj_getu32(p+4);
+      h += lj_getu32(p+8);
+      p = q; q += 12;
+      h ^= b; h -= lj_rol(b, 14);
+      a ^= h; a -= lj_rol(h, 11);
+      b ^= a; b -= lj_rol(a, 25);
+    } while (p < pe);
+    h ^= b; h -= lj_rol(b, 16);
+    a ^= h; a -= lj_rol(h, 4);
+    b ^= a; b -= lj_rol(a, 14);
+  }
+  return b;
+}
+#endif
+
+/* -- String interning ---------------------------------------------------- */
+
+#define LJ_STR_MAXCOLL          32
+
+/* Resize the string interning hash table (grow and shrink). */
+void lj_str_resize(lua_State *L, MSize newmask)
+{
+  global_State *g = G(L);
+  GCRef *newtab, *oldtab = g->str.tab;
+  MSize i;
+
+  /* No resizing during GC traversal or if already too big. */
+  if (g->gc.state == GCSsweepstring || newmask >= LJ_MAX_STRTAB-1)
+    return;
+
+  newtab = lj_mem_newvec(L, newmask+1, GCRef);
+  memset(newtab, 0, (newmask+1)*sizeof(GCRef));
+
+#if LUAJIT_SECURITY_STRHASH
+  /* Check which chains need secondary hashes. */
+  if (g->str.second) {
+    int newsecond = 0;
+    /* Compute primary chain lengths. */
+    for (i = g->str.mask; i != ~(MSize)0; i--) {
+      GCobj *o = (GCobj *)(gcrefu(oldtab[i]) & ~(uintptr_t)1);
+      while (o) {
+        GCstr *s = gco2str(o);
+        MSize hash = s->hashalg ? hash_sparse(g->str.seed, strdata(s), s->len) :
+                                  s->hash;
+        hash &= newmask;
+        setgcrefp(newtab[hash], gcrefu(newtab[hash]) + 1);
+        o = gcnext(o);
       }
-      o = gcnext(o);
     }
-  } else {  /* Slow path: end of string is too close to a page boundary. */
-    while (o != NULL) {
-      GCstr *sx = gco2str(o);
-      if (sx->len == len && memcmp(str, strdata(sx), len) == 0) {
-        /* Resurrect if dead. Can only happen with fixstring() (keywords). */
-        if (isdead(g, o)) flipwhite(o);
-        return sx;  /* Return existing string. */
+    /* Mark secondary chains. */
+    for (i = newmask; i != ~(MSize)0; i--) {
+      int secondary = gcrefu(newtab[i]) > LJ_STR_MAXCOLL;
+      newsecond |= secondary;
+      setgcrefp(newtab[i], secondary);
+    }
+    g->str.second = newsecond;
+  }
+#endif
+
+  /* Reinsert all strings from the old table into the new table. */
+  for (i = g->str.mask; i != ~(MSize)0; i--) {
+    GCobj *o = (GCobj *)(gcrefu(oldtab[i]) & ~(uintptr_t)1);
+    while (o) {
+      GCobj *next = gcnext(o);
+      GCstr *s = gco2str(o);
+      MSize hash = s->hash;
+#if LUAJIT_SECURITY_STRHASH
+      uintptr_t u;
+      if (LJ_LIKELY(!s->hashalg)) {  /* String hashed with primary hash. */
+        hash &= newmask;
+        u = gcrefu(newtab[hash]);
+        if (LJ_UNLIKELY(u & 1)) {  /* Switch string to secondary hash. */
+          s->hash = hash = hash_dense(g->str.seed, s->hash, strdata(s), s->len);
+          s->hashalg = 1;
+          hash &= newmask;
+          u = gcrefu(newtab[hash]);
+        }
+      } else {  /* String hashed with secondary hash. */
+        MSize shash = hash_sparse(g->str.seed, strdata(s), s->len);
+        u = gcrefu(newtab[shash & newmask]);
+        if (u & 1) {
+          hash &= newmask;
+          u = gcrefu(newtab[hash]);
+        } else {  /* Revert string back to primary hash. */
+          s->hash = shash;
+          s->hashalg = 0;
+          hash = (shash & newmask);
+        }
+      }
+      /* NOBARRIER: The string table is a GC root. */
+      setgcrefp(o->gch.nextgc, (u & ~(uintptr_t)1));
+      setgcrefp(newtab[hash], ((uintptr_t)o | (u & 1)));
+#else
+      hash &= newmask;
+      /* NOBARRIER: The string table is a GC root. */
+      setgcrefr(o->gch.nextgc, newtab[hash]);
+      setgcref(newtab[hash], o);
+#endif
+      o = next;
+    }
+  }
+
+  /* Free old table and replace with new table. */
+  lj_str_freetab(g);
+  g->str.tab = newtab;
+  g->str.mask = newmask;
+}
+
+#if LUAJIT_SECURITY_STRHASH
+/* Rehash and rechain all strings in a chain. */
+static LJ_NOINLINE GCstr *lj_str_rehash_chain(lua_State *L, StrHash hashc,
+                                              const char *str, MSize len)
+{
+  global_State *g = G(L);
+  int ow = g->gc.state == GCSsweepstring ? otherwhite(g) : 0;  /* Sweeping? */
+  GCRef *strtab = g->str.tab;
+  MSize strmask = g->str.mask;
+  GCobj *o = gcref(strtab[hashc & strmask]);
+  setgcrefp(strtab[hashc & strmask], (void *)((uintptr_t)1));
+  g->str.second = 1;
+  while (o) {
+    uintptr_t u;
+    GCobj *next = gcnext(o);
+    GCstr *s = gco2str(o);
+    StrHash hash;
+    if (ow) {  /* Must sweep while rechaining. */
+      if (((o->gch.marked ^ LJ_GC_WHITES) & ow)) {  /* String alive? */
+        lj_assertG(!isdead(g, o) || (o->gch.marked & LJ_GC_FIXED),
+                   "sweep of undead string");
+        makewhite(g, o);
+      } else {  /* Free dead string. */
+        lj_assertG(isdead(g, o) || ow == LJ_GC_SFIXED,
+                   "sweep of unlive string");
+        lj_str_free(g, s);
+        o = next;
+        continue;
       }
-      o = gcnext(o);
     }
+    hash = s->hash;
+    if (!s->hashalg) {  /* Rehash with secondary hash. */
+      hash = hash_dense(g->str.seed, hash, strdata(s), s->len);
+      s->hash = hash;
+      s->hashalg = 1;
+    }
+    /* Rechain. */
+    hash &= strmask;
+    u = gcrefu(strtab[hash]);
+    setgcrefp(o->gch.nextgc, (u & ~(uintptr_t)1));
+    setgcrefp(strtab[hash], ((uintptr_t)o | (u & 1)));
+    o = next;
   }
-  /* Nope, create a new string. */
-  s = lj_mem_newt(L, sizeof(GCstr)+len+1, GCstr);
+  /* Try to insert the pending string again. */
+  return lj_str_new(L, str, len);
+}
+#endif
+
+/* Reseed String ID from PRNG after random interval < 2^bits. */
+#if LUAJIT_SECURITY_STRID == 1
+#define STRID_RESEED_INTERVAL   8
+#elif LUAJIT_SECURITY_STRID == 2
+#define STRID_RESEED_INTERVAL   4
+#elif LUAJIT_SECURITY_STRID >= 3
+#define STRID_RESEED_INTERVAL   0
+#endif
+
+/* Allocate a new string and add to string interning table. */
+static GCstr *lj_str_alloc(lua_State *L, const char *str, MSize len,
+                           StrHash hash, int hashalg)
+{
+  GCstr *s = lj_mem_newt(L, lj_str_size(len), GCstr);
+  global_State *g = G(L);
+  uintptr_t u;
   newwhite(g, s);
   s->gct = ~LJ_TSTR;
   s->len = len;
-  s->hash = h;
+  s->hash = hash;
+#ifndef STRID_RESEED_INTERVAL
+  s->sid = g->str.id++;
+#elif STRID_RESEED_INTERVAL
+  if (!g->str.idreseed--) {
+    uint64_t r = lj_prng_u64(&g->prng);
+    g->str.id = (StrID)r;
+    g->str.idreseed = (uint8_t)(r >> (64 - STRID_RESEED_INTERVAL));
+  }
+  s->sid = g->str.id++;
+#else
+  s->sid = (StrID)lj_prng_u64(&g->prng);
+#endif
   s->reserved = 0;
+  s->hashalg = (uint8_t)hashalg;
+  /* Clear last 4 bytes of allocated memory. Implies zero-termination, too. */
+  *(uint32_t *)(strdatawr(s)+(len & ~(MSize)3)) = 0;
   memcpy(strdatawr(s), str, len);
-  strdatawr(s)[len] = '\0';  /* Zero-terminate string. */
-  /* Add it to string hash table. */
-  h &= g->strmask;
-  s->nextgc = g->strhash[h];
+  /* Add to string hash table. */
+  hash &= g->str.mask;
+  u = gcrefu(g->str.tab[hash]);
+  setgcrefp(s->nextgc, (u & ~(uintptr_t)1));
   /* NOBARRIER: The string table is a GC root. */
-  setgcref(g->strhash[h], obj2gco(s));
-  if (g->strnum++ > g->strmask)  /* Allow a 100% load factor. */
-    lj_str_resize(L, (g->strmask<<1)+1);  /* Grow string table. */
+  setgcrefp(g->str.tab[hash], ((uintptr_t)s | (u & 1)));
+  if (g->str.num++ > g->str.mask)  /* Allow a 100% load factor. */
+    lj_str_resize(L, (g->str.mask<<1)+1);  /* Grow string table. */
   return s;  /* Return newly interned string. */
 }
 
+/* Intern a string and return string object. */
+GCstr *lj_str_new(lua_State *L, const char *str, size_t lenx)
+{
+  global_State *g = G(L);
+  if (lenx-1 < LJ_MAX_STR-1) {
+    MSize len = (MSize)lenx;
+    StrHash hash = hash_sparse(g->str.seed, str, len);
+    MSize coll = 0;
+    int hashalg = 0;
+    /* Check if the string has already been interned. */
+    GCobj *o = gcref(g->str.tab[hash & g->str.mask]);
+#if LUAJIT_SECURITY_STRHASH
+    if (LJ_UNLIKELY((uintptr_t)o & 1)) {  /* Secondary hash for this chain? */
+      hashalg = 1;
+      hash = hash_dense(g->str.seed, hash, str, len);
+      o = (GCobj *)(gcrefu(g->str.tab[hash & g->str.mask]) & ~(uintptr_t)1);
+    }
+#endif
+    while (o != NULL) {
+      GCstr *sx = gco2str(o);
+      if (sx->hash == hash && sx->len == len) {
+        if (memcmp(str, strdata(sx), len) == 0) {
+          if (isdead(g, o)) flipwhite(o);  /* Resurrect if dead. */
+          return sx;  /* Return existing string. */
+        }
+        coll++;
+      }
+      coll++;
+      o = gcnext(o);
+    }
+#if LUAJIT_SECURITY_STRHASH
+    /* Rehash chain if there are too many collisions. */
+    if (LJ_UNLIKELY(coll > LJ_STR_MAXCOLL) && !hashalg) {
+      return lj_str_rehash_chain(L, hash, str, len);
+    }
+#endif
+    /* Otherwise allocate a new string. */
+    return lj_str_alloc(L, str, len, hash, hashalg);
+  } else {
+    if (lenx)
+      lj_err_msg(L, LJ_ERR_STROV);
+    return &g->strempty;
+  }
+}
+
 void LJ_FASTCALL lj_str_free(global_State *g, GCstr *s)
 {
-  g->strnum--;
-  lj_mem_free(g, s, sizestring(s));
+  g->str.num--;
+  lj_mem_free(g, s, lj_str_size(s->len));
+}
+
+void LJ_FASTCALL lj_str_init(lua_State *L)
+{
+  global_State *g = G(L);
+  g->str.seed = lj_prng_u64(&g->prng);
+  lj_str_resize(L, LJ_MIN_STRTAB-1);
 }
 
diff --git a/src/lj_str.h b/src/lj_str.h
index 2e9bfc1d..01c6ba6b 100644
--- a/src/lj_str.h
+++ b/src/lj_str.h
@@ -20,8 +20,12 @@ LJ_FUNC int lj_str_haspattern(GCstr *s);
 LJ_FUNC void lj_str_resize(lua_State *L, MSize newmask);
 LJ_FUNCA GCstr *lj_str_new(lua_State *L, const char *str, size_t len);
 LJ_FUNC void LJ_FASTCALL lj_str_free(global_State *g, GCstr *s);
+LJ_FUNC void LJ_FASTCALL lj_str_init(lua_State *L);
+#define lj_str_freetab(g) \
+  (lj_mem_freevec(g, g->str.tab, g->str.mask+1, GCRef))
 
 #define lj_str_newz(L, s)       (lj_str_new(L, s, strlen(s)))
 #define lj_str_newlit(L, s)     (lj_str_new(L, "" s, sizeof(s)-1))
+#define lj_str_size(len)        (sizeof(GCstr) + (((len)+4) & ~(MSize)3))
 
 #endif
diff --git a/src/lj_tab.c b/src/lj_tab.c
index efc423cb..982b0763 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -23,8 +23,8 @@ static LJ_AINLINE Node *hashmask(const GCtab *t, uint32_t hash)
   return &n[hash & t->hmask];
 }
 
-/* String hashes are precomputed when they are interned. */
-#define hashstr(t, s)           hashmask(t, (s)->hash)
+/* String IDs are generated when a string is interned. */
+#define hashstr(t, s)           hashmask(t, (s)->sid)
 
 #define hashlohi(t, lo, hi)     hashmask((t), hashrot((lo), (hi)))
 #define hashnum(t, o)           hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1))
diff --git a/src/vm_arm.dasc b/src/vm_arm.dasc
index 013688fb..770a8e21 100644
--- a/src/vm_arm.dasc
+++ b/src/vm_arm.dasc
@@ -1012,9 +1012,9 @@ static void build_subroutines(BuildCtx *ctx)
   |  cmp TAB:RB, #0
   |  beq ->fff_restv
   |  ldr CARG3, TAB:RB->hmask
-  |   ldr CARG4, STR:RC->hash
+  |   ldr CARG4, STR:RC->sid
   |    ldr NODE:INS, TAB:RB->node
-  |  and CARG3, CARG3, CARG4            // idx = str->hash & tab->hmask
+  |  and CARG3, CARG3, CARG4            // idx = str->sid & tab->hmask
   |  add CARG3, CARG3, CARG3, lsl #1
   |    add NODE:INS, NODE:INS, CARG3, lsl #3    // node = tab->node + idx*3*8
   |3:  // Rearranged logic, because we expect _not_ to find the key.
@@ -3500,10 +3500,10 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TGETS_Z:
     |  // (TAB:RB =) TAB:CARG1 = GCtab *, STR:RC = GCstr *, RA = dst*8
     |  ldr CARG3, TAB:CARG1->hmask
-    |   ldr CARG4, STR:RC->hash
+    |   ldr CARG4, STR:RC->sid
     |    ldr NODE:INS, TAB:CARG1->node
     |     mov TAB:RB, TAB:CARG1
-    |  and CARG3, CARG3, CARG4                  // idx = str->hash & tab->hmask
+    |  and CARG3, CARG3, CARG4                  // idx = str->sid & tab->hmask
     |  add CARG3, CARG3, CARG3, lsl #1
     |    add NODE:INS, NODE:INS, CARG3, lsl #3  // node = tab->node + idx*3*8
     |1:
@@ -3647,10 +3647,10 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TSETS_Z:
     |  // (TAB:RB =) TAB:CARG1 = GCtab *, STR:RC = GCstr *, RA = dst*8
     |  ldr CARG3, TAB:CARG1->hmask
-    |   ldr CARG4, STR:RC->hash
+    |   ldr CARG4, STR:RC->sid
     |    ldr NODE:INS, TAB:CARG1->node
     |     mov TAB:RB, TAB:CARG1
-    |  and CARG3, CARG3, CARG4                  // idx = str->hash & tab->hmask
+    |  and CARG3, CARG3, CARG4                  // idx = str->sid & tab->hmask
     |  add CARG3, CARG3, CARG3, lsl #1
     |   mov CARG4, #0
     |    add NODE:INS, NODE:INS, CARG3, lsl #3  // node = tab->node + idx*3*8
diff --git a/src/vm_arm64.dasc b/src/vm_arm64.dasc
index c157696c..4a729f65 100644
--- a/src/vm_arm64.dasc
+++ b/src/vm_arm64.dasc
@@ -993,9 +993,9 @@ static void build_subroutines(BuildCtx *ctx)
   |   ldr STR:RC, GL->gcroot[GCROOT_MMNAME+MM_metatable]
   |  cbz TAB:RB, ->fff_restv
   |  ldr TMP1w, TAB:RB->hmask
-  |   ldr TMP2w, STR:RC->hash
+  |   ldr TMP2w, STR:RC->sid
   |    ldr NODE:CARG3, TAB:RB->node
-  |  and TMP1w, TMP1w, TMP2w            // idx = str->hash & tab->hmask
+  |  and TMP1w, TMP1w, TMP2w            // idx = str->sid & tab->hmask
   |  add TMP1, TMP1, TMP1, lsl #1
   |  movn CARG4, #~LJ_TSTR
   |    add NODE:CARG3, NODE:CARG3, TMP1, lsl #3  // node = tab->node + idx*3*8
@@ -2943,9 +2943,9 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TGETS_Z:
     |  // TAB:CARG2 = GCtab *, STR:RC = GCstr *, RA = dst
     |  ldr TMP1w, TAB:CARG2->hmask
-    |   ldr TMP2w, STR:RC->hash
+    |   ldr TMP2w, STR:RC->sid
     |    ldr NODE:CARG3, TAB:CARG2->node
-    |  and TMP1w, TMP1w, TMP2w          // idx = str->hash & tab->hmask
+    |  and TMP1w, TMP1w, TMP2w          // idx = str->sid & tab->hmask
     |  add TMP1, TMP1, TMP1, lsl #1
     |  movn CARG4, #~LJ_TSTR
     |    add NODE:CARG3, NODE:CARG3, TMP1, lsl #3  // node = tab->node + idx*3*8
@@ -3069,9 +3069,9 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TSETS_Z:
     |  // TAB:CARG2 = GCtab *, STR:RC = GCstr *, RA = src
     |  ldr TMP1w, TAB:CARG2->hmask
-    |   ldr TMP2w, STR:RC->hash
+    |   ldr TMP2w, STR:RC->sid
     |    ldr NODE:CARG3, TAB:CARG2->node
-    |  and TMP1w, TMP1w, TMP2w          // idx = str->hash & tab->hmask
+    |  and TMP1w, TMP1w, TMP2w          // idx = str->sid & tab->hmask
     |  add TMP1, TMP1, TMP1, lsl #1
     |  movn CARG4, #~LJ_TSTR
     |    add NODE:CARG3, NODE:CARG3, TMP1, lsl #3  // node = tab->node + idx*3*8
diff --git a/src/vm_mips.dasc b/src/vm_mips.dasc
index 0c84c13b..91de4b5c 100644
--- a/src/vm_mips.dasc
+++ b/src/vm_mips.dasc
@@ -1152,9 +1152,9 @@ static void build_subroutines(BuildCtx *ctx)
   |.  li SFARG1HI, LJ_TNIL
   |  lw TMP0, TAB:SFARG1LO->hmask
   |   li SFARG1HI, LJ_TTAB              // Use metatable as default result.
-  |  lw TMP1, STR:RC->hash
+  |  lw TMP1, STR:RC->sid
   |  lw NODE:TMP2, TAB:SFARG1LO->node
-  |  and TMP1, TMP1, TMP0               // idx = str->hash & tab->hmask
+  |  and TMP1, TMP1, TMP0               // idx = str->sid & tab->hmask
   |  sll TMP0, TMP1, 5
   |  sll TMP1, TMP1, 3
   |  subu TMP1, TMP0, TMP1
@@ -4029,9 +4029,9 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TGETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = dst*8
     |  lw TMP0, TAB:RB->hmask
-    |  lw TMP1, STR:RC->hash
+    |  lw TMP1, STR:RC->sid
     |  lw NODE:TMP2, TAB:RB->node
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |  sll TMP0, TMP1, 5
     |  sll TMP1, TMP1, 3
     |  subu TMP1, TMP0, TMP1
@@ -4203,10 +4203,10 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TSETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = BASE+src*8
     |  lw TMP0, TAB:RB->hmask
-    |  lw TMP1, STR:RC->hash
+    |  lw TMP1, STR:RC->sid
     |  lw NODE:TMP2, TAB:RB->node
     |   sb r0, TAB:RB->nomm             // Clear metamethod cache.
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |  sll TMP0, TMP1, 5
     |  sll TMP1, TMP1, 3
     |  subu TMP1, TMP0, TMP1
diff --git a/src/vm_mips64.dasc b/src/vm_mips64.dasc
index dac143a4..71acf9ed 100644
--- a/src/vm_mips64.dasc
+++ b/src/vm_mips64.dasc
@@ -1201,9 +1201,9 @@ static void build_subroutines(BuildCtx *ctx)
   |  beqz TAB:RB, ->fff_restv
   |.  li CARG1, LJ_TNIL
   |  lw TMP0, TAB:RB->hmask
-  |   lw TMP1, STR:RC->hash
+  |   lw TMP1, STR:RC->sid
   |    ld NODE:TMP2, TAB:RB->node
-  |  and TMP1, TMP1, TMP0               // idx = str->hash & tab->hmask
+  |  and TMP1, TMP1, TMP0               // idx = str->sid & tab->hmask
   |  dsll TMP0, TMP1, 5
   |  dsll TMP1, TMP1, 3
   |  dsubu TMP1, TMP0, TMP1
@@ -4239,9 +4239,9 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TGETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = dst*8
     |  lw TMP0, TAB:RB->hmask
-    |   lw TMP1, STR:RC->hash
+    |   lw TMP1, STR:RC->sid
     |    ld NODE:TMP2, TAB:RB->node
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |  sll TMP0, TMP1, 5
     |  sll TMP1, TMP1, 3
     |  subu TMP1, TMP0, TMP1
@@ -4402,10 +4402,10 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TSETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = BASE+src*8
     |  lw TMP0, TAB:RB->hmask
-    |   lw TMP1, STR:RC->hash
+    |   lw TMP1, STR:RC->sid
     |    ld NODE:TMP2, TAB:RB->node
     |   sb r0, TAB:RB->nomm             // Clear metamethod cache.
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |  sll TMP0, TMP1, 5
     |  sll TMP1, TMP1, 3
     |  subu TMP1, TMP0, TMP1
diff --git a/src/vm_ppc.dasc b/src/vm_ppc.dasc
index 7a2d321e..18fc6f93 100644
--- a/src/vm_ppc.dasc
+++ b/src/vm_ppc.dasc
@@ -1447,9 +1447,9 @@ static void build_subroutines(BuildCtx *ctx)
   |   beq ->fff_restv
   |  lwz TMP0, TAB:CARG1->hmask
   |   li CARG3, LJ_TTAB                 // Use metatable as default result.
-  |  lwz TMP1, STR:RC->hash
+  |  lwz TMP1, STR:RC->sid
   |  lwz NODE:TMP2, TAB:CARG1->node
-  |  and TMP1, TMP1, TMP0               // idx = str->hash & tab->hmask
+  |  and TMP1, TMP1, TMP0               // idx = str->sid & tab->hmask
   |  slwi TMP0, TMP1, 5
   |  slwi TMP1, TMP1, 3
   |  sub TMP1, TMP0, TMP1
@@ -4588,9 +4588,9 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TGETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = dst*8
     |  lwz TMP0, TAB:RB->hmask
-    |  lwz TMP1, STR:RC->hash
+    |  lwz TMP1, STR:RC->sid
     |  lwz NODE:TMP2, TAB:RB->node
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |  slwi TMP0, TMP1, 5
     |  slwi TMP1, TMP1, 3
     |  sub TMP1, TMP0, TMP1
@@ -4784,10 +4784,10 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |->BC_TSETS_Z:
     |  // TAB:RB = GCtab *, STR:RC = GCstr *, RA = src*8
     |  lwz TMP0, TAB:RB->hmask
-    |  lwz TMP1, STR:RC->hash
+    |  lwz TMP1, STR:RC->sid
     |  lwz NODE:TMP2, TAB:RB->node
     |    stb ZERO, TAB:RB->nomm         // Clear metamethod cache.
-    |  and TMP1, TMP1, TMP0             // idx = str->hash & tab->hmask
+    |  and TMP1, TMP1, TMP0             // idx = str->sid & tab->hmask
     |.if FPU
     |    lfdx f14, BASE, RA
     |.else
diff --git a/src/vm_x64.dasc b/src/vm_x64.dasc
index 77a579d5..14a54e34 100644
--- a/src/vm_x64.dasc
+++ b/src/vm_x64.dasc
@@ -1230,7 +1230,7 @@ static void build_subroutines(BuildCtx *ctx)
   |  mov [BASE-16], TAB:RC              // Store metatable as default result.
   |  mov STR:RC, [DISPATCH+DISPATCH_GL(gcroot)+8*(GCROOT_MMNAME+MM_metatable)]
   |  mov RAd, TAB:RB->hmask
-  |  and RAd, STR:RC->hash
+  |  and RAd, STR:RC->sid
   |  settp STR:RC, LJ_TSTR
   |  imul RAd, #NODE
   |  add NODE:RA, TAB:RB->node
@@ -3674,7 +3674,7 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |  checktab TAB:RB, ->vmeta_tgets
     |->BC_TGETS_Z:      // RB = GCtab *, RC = GCstr *
     |  mov TMPRd, TAB:RB->hmask
-    |  and TMPRd, STR:RC->hash
+    |  and TMPRd, STR:RC->sid
     |  imul TMPRd, #NODE
     |  add NODE:TMPR, TAB:RB->node
     |  settp ITYPE, STR:RC, LJ_TSTR
@@ -3806,7 +3806,7 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |  checktab TAB:RB, ->vmeta_tsets
     |->BC_TSETS_Z:      // RB = GCtab *, RC = GCstr *
     |  mov TMPRd, TAB:RB->hmask
-    |  and TMPRd, STR:RC->hash
+    |  and TMPRd, STR:RC->sid
     |  imul TMPRd, #NODE
     |  mov byte TAB:RB->nomm, 0         // Clear metamethod cache.
     |  add NODE:TMPR, TAB:RB->node
diff --git a/src/vm_x86.dasc b/src/vm_x86.dasc
index 57c8e4fc..f9bea426 100644
--- a/src/vm_x86.dasc
+++ b/src/vm_x86.dasc
@@ -1522,7 +1522,7 @@ static void build_subroutines(BuildCtx *ctx)
   |  mov dword [BASE-4], LJ_TTAB        // Store metatable as default result.
   |  mov [BASE-8], TAB:RB
   |  mov RA, TAB:RB->hmask
-  |  and RA, STR:RC->hash
+  |  and RA, STR:RC->sid
   |  imul RA, #NODE
   |  add NODE:RA, TAB:RB->node
   |3:  // Rearranged logic, because we expect _not_ to find the key.
@@ -4286,7 +4286,7 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |  mov TAB:RB, [BASE+RB*8]
     |->BC_TGETS_Z:      // RB = GCtab *, RC = GCstr *, refetches PC_RA.
     |  mov RA, TAB:RB->hmask
-    |  and RA, STR:RC->hash
+    |  and RA, STR:RC->sid
     |  imul RA, #NODE
     |  add NODE:RA, TAB:RB->node
     |1:
@@ -4457,7 +4457,7 @@ static void build_ins(BuildCtx *ctx, BCOp op, int defop)
     |  mov TAB:RB, [BASE+RB*8]
     |->BC_TSETS_Z:      // RB = GCtab *, RC = GCstr *, refetches PC_RA.
     |  mov RA, TAB:RB->hmask
-    |  and RA, STR:RC->hash
+    |  and RA, STR:RC->sid
     |  imul RA, #NODE
     |  mov byte TAB:RB->nomm, 0         // Clear metamethod cache.
     |  add NODE:RA, TAB:RB->node