No longer let the GC replace dead keys with the LJ_TDEADKEY tag.

Important: this changes the semantics of the write barrier! Carefully read the big comment block in lj_obj.h This helps HREFK key slot specialization and allows safely hoisting HREF/HREFK across GC steps, too (fix for a barely reproducible bug). Dead keys are only removed during a table resize (as before).
author: Mike Pall <mike> 2010-04-21 01:45:58 +0200
committer: Mike Pall <mike> 2010-04-21 01:45:58 +0200
commit: ab45481199e9c9dd3efec922647bcec122504bcb (patch)
tree: 0484341edff50a0afe98133ad66fb6a59915996a /src
parent: d8cb69ed076c3444258f63314662451c9d117cae (diff)
download: luajit-ab45481199e9c9dd3efec922647bcec122504bcb.tar.gz
luajit-ab45481199e9c9dd3efec922647bcec122504bcb.tar.bz2
luajit-ab45481199e9c9dd3efec922647bcec122504bcb.zip
13 files changed, 65 insertions, 43 deletions
diff --git a/src/lib_base.c b/src/lib_base.c
index e85b7264..cbfd818a 100644
--- a/src/lib_base.c
+++ b/src/lib_base.c
@@ -54,7 +54,7 @@ LJLIB_PUSH("upval")
 LJLIB_PUSH("thread")
 LJLIB_PUSH("proto")
 LJLIB_PUSH("function")
-LJLIB_PUSH("deadkey")
+LJLIB_PUSH("")  /* Unused. */
 LJLIB_PUSH("table")
 LJLIB_PUSH(top-8)  /* userdata */
 LJLIB_PUSH("number")
diff --git a/src/lj_api.c b/src/lj_api.c
index a19f0b33..aac3b4c9 100644
--- a/src/lj_api.c
+++ b/src/lj_api.c
@@ -196,7 +196,8 @@ LUA_API int lua_type(lua_State *L, int idx)
    return LUA_TNONE;
  } else {  /* Magic internal/external tag conversion. ORDER LJ_T */
    int t = ~itype(o);
-    return (int)(((t < 8 ? 0x98a42110 : 0x75b6) >> 4*(t&7)) & 15u);
+    lua_assert(itype(o) != LJ_TUPVAL);
+    return (int)(((t < 8 ? 0x98042110 : 0x7506) >> 4*(t&7)) & 15u);
  }
 }
@@ -631,7 +632,7 @@ LUALIB_API int luaL_newmetatable(lua_State *L, const char *tname)
    GCtab *mt = lj_tab_new(L, 0, 1);
    settabV(L, tv, mt);
    settabV(L, L->top++, mt);
-    lj_gc_objbarriert(L, regt, mt);
+    lj_gc_anybarriert(L, regt);
    return 1;
  } else {
    copyTV(L, L->top++, tv);
@@ -899,7 +900,7 @@ LUA_API void lua_rawset(lua_State *L, int idx)
  key = L->top-2;
  dst = lj_tab_set(L, t, key);
  copyTV(L, dst, key+1);
-  lj_gc_barriert(L, t, dst);
+  lj_gc_anybarriert(L, t);
  L->top = key;
 }
diff --git a/src/lj_gc.c b/src/lj_gc.c
index b97fb955..b457c424 100644
--- a/src/lj_gc.c
+++ b/src/lj_gc.c
@@ -186,13 +186,10 @@ static int gc_traverse_tab(global_State *g, GCtab *t)
    MSize i, hmask = t->hmask;
    for (i = 0; i <= hmask; i++) {
      Node *n = &node[i];
-      lua_assert(itype(&n->key) != LJ_TDEADKEY || tvisnil(&n->val));
      if (!tvisnil(&n->val)) {  /* Mark non-empty slot. */
        lua_assert(!tvisnil(&n->key));
        if (!(weak & LJ_GC_WEAKKEY)) gc_marktv(g, &n->key);
        if (!(weak & LJ_GC_WEAKVAL)) gc_marktv(g, &n->val);
-      } else if (tvisgcv(&n->key)) {  /* Leave GC key in, but mark as dead. */
-        setitype(&n->key, LJ_TDEADKEY);
      }
    }
  }
@@ -424,11 +421,8 @@ static void gc_clearweak(GCobj *o)
        Node *n = &node[i];
        /* Clear hash slot when key or value is about to be collected. */
        if (!tvisnil(&n->val) && (gc_mayclear(&n->key, 0) ||
-                                  gc_mayclear(&n->val, 1))) {
+                                  gc_mayclear(&n->val, 1)))
          setnilV(&n->val);
-          if (tvisgcv(&n->key))  /* Leave GC key in, but mark as dead. */
-            setitype(&n->key, LJ_TDEADKEY);
-        }
      }
    }
    o = gcref(t->gclist);
diff --git a/src/lj_gc.h b/src/lj_gc.h
index 7279b93c..3d213eb3 100644
--- a/src/lj_gc.h
+++ b/src/lj_gc.h
@@ -69,6 +69,8 @@ LJ_FUNC void lj_gc_barriertrace(global_State *g, void *T);
 #endif
 /* Barrier for stores to table objects. TValue and GCobj variant. */
+#define lj_gc_anybarriert(L, t)  \
+  { if (isblack(obj2gco(t))) lj_gc_barrierback(G(L), (t)); }
 #define lj_gc_barriert(L, t, tv) \
  { if (tviswhite(tv) && isblack(obj2gco(t))) \
      lj_gc_barrierback(G(L), (t)); }
diff --git a/src/lj_ir.h b/src/lj_ir.h
index ca871238..14f80ac5 100644
--- a/src/lj_ir.h
+++ b/src/lj_ir.h
@@ -317,7 +317,7 @@ typedef enum {
  IRT_THREAD,
  IRT_PROTO,
  IRT_FUNC,
-  IRT_9,                /* LJ_TDEADKEY is never used in the IR. */
+  IRT_9,                /* Never used in the IR. */
  IRT_TAB,
  IRT_UDATA,
  /* ... until here. */
diff --git a/src/lj_lib.c b/src/lj_lib.c
index 0ba0ecb1..9540772e 100644
--- a/src/lj_lib.c
+++ b/src/lj_lib.c
@@ -53,7 +53,7 @@ void lj_lib_register(lua_State *L, const char *libname,
  ptrdiff_t tpos = L->top - L->base;
  /* Avoid barriers further down. */
-  if (isblack(obj2gco(tab))) lj_gc_barrierback(G(L), tab);
+  lj_gc_anybarriert(L, tab);
  tab->nomm = 0;
  for (;;) {
diff --git a/src/lj_meta.c b/src/lj_meta.c
index c8ac18d6..41124fdc 100644
--- a/src/lj_meta.c
+++ b/src/lj_meta.c
@@ -134,7 +134,7 @@ TValue *lj_meta_tset(lua_State *L, cTValue *o, cTValue *k)
      TValue *tv = lj_tab_set(L, t, k);
      if (!tvisnil(tv) ||
          !(mo = lj_meta_fast(L, tabref(t->metatable), MM_newindex))) {
-        if (isblack(obj2gco(t))) lj_gc_barrierback(G(L), t);
+        lj_gc_anybarriert(L, t);
        return tv;
      }
    } else if (tvisnil(mo = lj_meta_lookup(L, o, MM_newindex))) {
diff --git a/src/lj_obj.c b/src/lj_obj.c
index 4363e790..0df51bc4 100644
--- a/src/lj_obj.c
+++ b/src/lj_obj.c
@@ -11,12 +11,12 @@
 /* Object type names. */
 LJ_DATADEF const char *const lj_obj_typename[] = {  /* ORDER LUA_T */
  "no value", "nil", "boolean", "userdata", "number", "string",
-  "table", "function", "userdata", "thread", "proto", "upval"
+  "table", "function", "userdata", "thread", "proto"
 };
 LJ_DATADEF const char *const lj_obj_itypename[] = {  /* ORDER LJ_T */
  "nil", "boolean", "boolean", "userdata", "string", "upval", "thread",
-  "proto", "function", "deadkey", "table", "userdata", "number"
+  "proto", "function", "" /* Unused */, "table", "userdata", "number"
 };
 /* Compare two objects without calling metamethods. */
@@ -25,14 +25,8 @@ int lj_obj_equal(cTValue *o1, cTValue *o2)
  if (itype(o1) == itype(o2)) {
    if (tvispri(o1))
      return 1;
-    if (!tvisnum(o1)) {
+    if (!tvisnum(o1))
-#if LJ_64
+      return gcrefeq(o1->gcr, o2->gcr);
-      if (tvislightud(o1))
-        return o1->u64 == o2->u64;
-      else
-#endif
-        return gcrefeq(o1->gcr, o2->gcr);
-    }
  } else if (!tvisnum(o1) || !tvisnum(o2)) {
    return 0;
  }
diff --git a/src/lj_obj.h b/src/lj_obj.h
index 048a74f9..71146dfc 100644
--- a/src/lj_obj.h
+++ b/src/lj_obj.h
@@ -75,9 +75,37 @@ typedef struct GCRef {
 ** a barrier has been omitted are annotated with a NOBARRIER comment.
 **
 ** The same logic applies for stores to table slots (array part or hash
-** part). ALL uses of lj_tab_set* require a barrier for the stored *value*
+** part). ALL uses of lj_tab_set* require a barrier for the stored value
-** (if it's a GC object). The barrier for the *key* is already handled
+** *and* the stored key, based on the above rules. In practice this means
-** internally by lj_tab_newkey.
+** a barrier is needed if *either* of the key or value are a GC object.
+**
+** It's ok to LEAVE OUT the write barrier in the following special cases:
+** - The stored value is nil. The key doesn't matter because it's either
+**   not resurrected or lj_tab_newkey() will take care of the key barrier.
+** - The key doesn't matter if the *previously* stored value is guaranteed
+**   to be non-nil (because the key is kept alive in the table).
+** - The key doesn't matter if it's guaranteed not to be part of the table,
+**   since lj_tab_newkey() takes care of the key barrier. This applies
+**   trivially to new tables, but watch out for resurrected keys. Storing
+**   a nil value leaves the key in the table!
+**
+** In case of doubt use lj_gc_anybarriert() as it's rather cheap. It's used
+** by the interpreter for all table stores.
+**
+** Note: In contrast to Lua's GC, LuaJIT's GC does *not* specially mark
+** dead keys in tables. The reference is left in, but it's guaranteed to
+** be never dereferenced as long as the value is nil. It's ok if the key is
+** freed or if any object subsequently gets the same address.
+**
+** Not destroying dead keys helps to keep key hash slots stable. This avoids
+** specialization back-off for HREFK when a value flips between nil and
+** non-nil and the GC gets in the way. It also allows safely hoisting
+** HREF/HREFK across GC steps. Dead keys are only removed if a table is
+** resized (i.e. by NEWREF) and xREF must not be CSEd across a resize.
+**
+** The trade-off is that a write barrier for tables must take the key into
+** account, too. Implicitly resurrecting the key by storing a non-nil value
+** may invalidate the incremental GC invariant.
 */
 /* -- Common type definitions --------------------------------------------- */
@@ -136,10 +164,7 @@ typedef const TValue cTValue;
 /* More external and GCobj tags for internal objects. */
 #define LAST_TT         LUA_TTHREAD
 #define LUA_TPROTO      (LAST_TT+1)
-#define LUA_TUPVAL      (LAST_TT+2)
-#define LUA_TDEADKEY    (LAST_TT+3)
 /* Internal object tags.
 **
@@ -170,7 +195,7 @@ typedef const TValue cTValue;
 #define LJ_TTHREAD              (-7)
 #define LJ_TPROTO               (-8)
 #define LJ_TFUNC                (-9)
-#define LJ_TDEADKEY             (-10)
+/* Unused                       (-10) */
 #define LJ_TTAB                 (-11)
 #define LJ_TUDATA               (-12)
 /* This is just the canonical number type used in some places. */
@@ -689,7 +714,7 @@ static LJ_AINLINE int32_t lj_num2bit(lua_Number n)
 /* -- Miscellaneous object handling --------------------------------------- */
 /* Names and maps for internal and external object tags. */
-LJ_DATA const char *const lj_obj_typename[1+LUA_TUPVAL+1];
+LJ_DATA const char *const lj_obj_typename[1+LUA_TPROTO+1];
 LJ_DATA const char *const lj_obj_itypename[~LJ_TNUMX+1];
 #define typename(o)     (lj_obj_itypename[itypemap(o)])
diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
index c91f3382..69ade882 100644
--- a/src/lj_opt_fold.c
+++ b/src/lj_opt_fold.c
@@ -1351,8 +1351,9 @@ LJFOLDF(fwd_xload)
 /* Write barriers are amenable to CSE, but not across any incremental
 ** GC steps.
 **
-** The same logic applies to open upvalue references, because the stack
+** The same logic applies to open upvalue references, because a stack
-** may be resized during a GC step.
+** may be resized during a GC step (not the current stack, but maybe that
+** of a coroutine).
 */
 LJFOLD(TBAR any)
 LJFOLD(OBAR any any)
diff --git a/src/lj_parse.c b/src/lj_parse.c
index 31a70d38..b5bd7baf 100644
--- a/src/lj_parse.c
+++ b/src/lj_parse.c
@@ -189,6 +189,7 @@ static BCReg const_gc(FuncState *fs, GCobj *gc, int itype)
  lua_State *L = fs->L;
  TValue o, *val;
  setgcV(L, &o, &gc->gch, itype);
+  /* NOBARRIER: the key is new or kept alive. */
  val = lj_tab_set(L, fs->kt, &o);
  if (tvisnum(val))
    return val->u32.lo;
@@ -206,6 +207,7 @@ static BCReg const_str(FuncState *fs, ExpDesc *e)
 /* Anchor string constant to avoid GC. */
 GCstr *lj_parse_keepstr(LexState *ls, const char *str, size_t len)
 {
+  /* NOBARRIER: the key is new or kept alive. */
  lua_State *L = ls->L;
  GCstr *s = lj_str_new(L, str, len);
  TValue *tv = lj_tab_setstr(L, ls->fs->kt, s);
@@ -1202,6 +1204,7 @@ static GCproto *fs_finish(LexState *ls, BCLine line)
  lua_assert(ls->fs != NULL || ls->token == TK_eof);
  /* Re-anchor last string token to avoid GC. */
  if (ls->token == TK_name || ls->token == TK_string) {
+    /* NOBARRIER: the key is new or kept alive. */
    TValue *tv = lj_tab_setstr(ls->L, ls->fs->kt, strV(&ls->tokenval));
    if (tvisnil(tv)) setboolV(tv, 1);
  }
@@ -1346,8 +1349,7 @@ static void expr_table(LexState *ls, ExpDesc *e)
      vcall = 0;
      expr_kvalue(&k, &key);
      expr_kvalue(lj_tab_set(fs->L, t, &k), &val);
-      if (val.k == VKSTR)
+      lj_gc_anybarriert(fs->L, t);
-        lj_gc_objbarriert(fs->L, t, val.u.sval);
    } else {
      if (val.k != VCALL) { expr_toanyreg(fs, &val); vcall = 0; }
      if (expr_isk(&key)) expr_index(fs, e, &key);
diff --git a/src/lj_record.c b/src/lj_record.c
index 206eedca..c13c67fd 100644
--- a/src/lj_record.c
+++ b/src/lj_record.c
@@ -994,6 +994,7 @@ static TRef rec_idx(jit_State *J, RecordIndex *ix)
    return res;
  } else {  /* Indexed store. */
    GCtab *mt = tabref(tabV(&ix->tabv)->metatable);
+    int keybarrier = tref_isgcv(ix->key) && !tref_isnil(ix->val);
    if (tvisnil(oldv)) {  /* Previous value was nil? */
      /* Need to duplicate the hasmm check for the early guards. */
      int hasmm = 0;
@@ -1004,7 +1005,8 @@ static TRef rec_idx(jit_State *J, RecordIndex *ix)
      if (hasmm)
        emitir(IRTG(loadop, IRT_NIL), xref, 0);  /* Guard for nil value. */
      else if (xrefop == IR_HREF)
-        emitir(IRTG(oldv == niltvg(J2G(J)) ? IR_EQ : IR_NE, IRT_PTR), xref, lj_ir_kptr(J, niltvg(J2G(J))));
+        emitir(IRTG(oldv == niltvg(J2G(J)) ? IR_EQ : IR_NE, IRT_PTR),
+               xref, lj_ir_kptr(J, niltvg(J2G(J))));
      if (ix->idxchain && rec_mm_lookup(J, ix, MM_newindex)) { /* Metamethod? */
        lua_assert(hasmm);
        goto handlemm;
@@ -1015,6 +1017,7 @@ static TRef rec_idx(jit_State *J, RecordIndex *ix)
        if (tref_isinteger(key))  /* NEWREF needs a TValue as a key. */
          key = emitir(IRTN(IR_TONUM), key, 0);
        xref = emitir(IRT(IR_NEWREF, IRT_PTR), ix->tab, key);
+        keybarrier = 0;  /* NEWREF already takes care of the key barrier. */
      }
    } else if (!lj_opt_fwd_wasnonnil(J, loadop, tref_ref(xref))) {
      /* Cannot derive that the previous value was non-nil, must do checks. */
@@ -1030,11 +1033,13 @@ static TRef rec_idx(jit_State *J, RecordIndex *ix)
          emitir(IRTG(loadop, t), xref, 0);  /* Guard for non-nil value. */
        }
      }
+    } else {
+      keybarrier = 0;  /* Previous non-nil value kept the key alive. */
    }
    if (tref_isinteger(ix->val))  /* Convert int to number before storing. */
      ix->val = emitir(IRTN(IR_TONUM), ix->val, 0);
    emitir(IRT(loadop+IRDELTA_L2S, tref_type(ix->val)), xref, ix->val);
-    if (tref_isgcv(ix->val))
+    if (keybarrier || tref_isgcv(ix->val))
      emitir(IRT(IR_TBAR, IRT_NIL), ix->tab, 0);
    /* Invalidate neg. metamethod cache for stores with certain string keys. */
    if (!nommstr(J, ix->key)) {
diff --git a/src/lj_tab.c b/src/lj_tab.c
index d77aa05a..5d68cc54 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -192,7 +192,7 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
      Node *kn = &knode[i];
      Node *n = &node[i];
      Node *next = nextnode(kn);
-      /* Don't use copyTV here, since it asserts on a copy of a DEADKEY. */
+      /* Don't use copyTV here, since it asserts on a copy of a dead key. */
      n->val = kn->val; n->key = kn->key;
      setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
    }
@@ -448,7 +448,7 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
  n->key.u64 = key->u64;
  if (LJ_UNLIKELY(tvismzero(&n->key)))
    n->key.u64 = 0;
-  lj_gc_barriert(L, t, key);
+  lj_gc_anybarriert(L, t);
  lua_assert(tvisnil(&n->val));
  return &n->val;
 }
@@ -517,9 +517,7 @@ static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
  if (!tvisnil(key)) {
    Node *n = hashkey(t, key);
    do {
-      if (lj_obj_equal(&n->key, key) ||
+      if (lj_obj_equal(&n->key, key))
-          (itype(&n->key) == LJ_TDEADKEY && tvisgcv(key) &&
-           gcV(&n->key) == gcV(key)))
        return t->asize + (uint32_t)(n - noderef(t->node));
        /* Hash key indexes: [t->asize..t->asize+t->nmask] */
    } while ((n = nextnode(n)));
author	Mike Pall <mike>	2010-04-21 01:45:58 +0200
committer	Mike Pall <mike>	2010-04-21 01:45:58 +0200
commit	ab45481199e9c9dd3efec922647bcec122504bcb (patch)
tree	0484341edff50a0afe98133ad66fb6a59915996a /src
parent	d8cb69ed076c3444258f63314662451c9d117cae (diff)
download	luajit-ab45481199e9c9dd3efec922647bcec122504bcb.tar.gz luajit-ab45481199e9c9dd3efec922647bcec122504bcb.tar.bz2 luajit-ab45481199e9c9dd3efec922647bcec122504bcb.zip