more and better tools (assertions & inspectors) to check incremental GC

8 files changed, 249 insertions, 42 deletions

diff --git a/lfunc.c b/lfunc.c
index af27bf0d..36bf3f32 100644
--- a/lfunc.c
+++ b/lfunc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.c,v 1.74 2003/12/09 16:56:11 roberto Exp roberto $
+** $Id: lfunc.c,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -57,7 +57,7 @@ UpVal *luaF_findupval (lua_State *L, StkId level) {
   }
   uv = luaM_new(L, UpVal);  /* not found: create a new one */
   uv->tt = LUA_TUPVAL;
-  uv->marked = bitmask(FIXEDBIT);  /* open upvalues cannot be collected */
+  uv->marked = luaC_white(G(L));
   uv->v = level;  /* current value lives in the stack */
   uv->next = *pp;  /* chain it in the proper position */
   *pp = obj2gco(uv);
@@ -68,11 +68,16 @@ UpVal *luaF_findupval (lua_State *L, StkId level) {
 void luaF_close (lua_State *L, StkId level) {
   UpVal *uv;
   while ((uv = ngcotouv(L->openupval)) != NULL && uv->v >= level) {
+    lu_byte mark = uv->marked;
+    lua_assert(!isblack(obj2gco(uv)));
     setobj(L, &uv->value, uv->v);
     luaC_barrier(L, uv, uv->v);
     uv->v = &uv->value;  /* now current value lives here */
     L->openupval = uv->next;  /* remove from `open' list */
     luaC_link(L, obj2gco(uv), LUA_TUPVAL);
+    if (G(L)->gcstate == GCSpropagate)
+      uv->marked = mark;  /* preserve previous mark */
+    lua_assert(!isdead(G(L), obj2gco(uv)));
   }
 }
 
diff --git a/lgc.c b/lgc.c
index fe6461c0..ae5cd686 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
+** $Id: lgc.c,v 2.2 2003/12/12 18:29:34 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -60,6 +60,7 @@
 
 
 
+
 /*
 ** computes the size of a collectible object
 */
@@ -152,7 +153,7 @@ static void marktmu (global_State *g) {
 
 
 /* move `dead' udata that need finalization to list `tmudata' */
-size_t luaC_separateudata (lua_State *L) {
+size_t luaC_separateudata (lua_State *L, int all) {
   size_t deadmem = 0;
   GCObject **p = &G(L)->firstudata;
   GCObject *curr;
@@ -160,7 +161,7 @@ size_t luaC_separateudata (lua_State *L) {
   GCObject **lastcollected = &collected;
   while ((curr = *p) != NULL) {
     lua_assert(curr->gch.tt == LUA_TUSERDATA);
-    if (!iswhite(curr) || isfinalized(gco2u(curr)))
+    if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
       p = &curr->gch.next;  /* don't bother with them */
     else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
       markfinalized(gco2u(curr));  /* don't need finalization */
@@ -182,7 +183,7 @@ size_t luaC_separateudata (lua_State *L) {
 }
 
 
-static void traversetable (global_State *g, Table *h) {
+static int traversetable (global_State *g, Table *h) {
   int i;
   int weakkey = 0;
   int weakvalue = 0;
@@ -202,7 +203,7 @@ static void traversetable (global_State *g, Table *h) {
       g->weak = obj2gco(h);  /* ... so put in the appropriate list */
     }
   }
-  if (weakkey && weakvalue) return;
+  if (weakkey && weakvalue) return 1;
   if (!weakvalue) {
     i = h->sizearray;
     while (i--)
@@ -217,6 +218,7 @@ static void traversetable (global_State *g, Table *h) {
       condmarkobject(g, gval(n), !weakvalue);
     }
   }
+  return weakkey || weakvalue;
 }
 
 
@@ -227,10 +229,8 @@ static void traversetable (global_State *g, Table *h) {
 static void traverseproto (global_State *g, Proto *f) {
   int i;
   if (f->source) stringmark(f->source);
-  for (i=0; i<f->sizek; i++) {  /* mark literal strings */
-    if (ttisstring(f->k+i))
-      stringmark(rawtsvalue(f->k+i));
-  }
+  for (i=0; i<f->sizek; i++)  /* mark literals */
+    markvalue(g, &f->k[i]);
   for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
     if (f->upvalues[i])
       stringmark(f->upvalues[i]);
@@ -258,9 +258,8 @@ static void traverseclosure (global_State *g, Closure *cl) {
     lua_assert(cl->l.nupvalues == cl->l.p->nups);
     markobject(g, hvalue(&cl->l.g));
     markobject(g, cl->l.p);
-    for (i=0; i<cl->l.nupvalues; i++) {  /* mark its upvalues */
+    for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
       markobject(g, cl->l.upvals[i]);
-    }
   }
 }
 
@@ -307,7 +306,8 @@ static l_mem propagatemarks (global_State *g, l_mem lim) {
       case LUA_TTABLE: {
         Table *h = gco2h(o);
         g->gray = h->gclist;
-        traversetable(g, h);
+        if (traversetable(g, h))  /* table is weak? */
+          black2gray(o);  /* keep it gray */
         break;
       }
       case LUA_TFUNCTION: {
@@ -339,7 +339,8 @@ static l_mem propagatemarks (global_State *g, l_mem lim) {
           g->grayagain = o;
           black2gray(o);
         }
-        markvalue(g, &uv->value);
+        else
+          markvalue(g, &uv->value);
         break;
       }
       default: lua_assert(0);
@@ -428,6 +429,13 @@ static void freeobj (lua_State *L, GCObject *o) {
 }
 
 
+static void sweepupvalues (global_State *g, lua_State *L1) {
+  GCObject *curr;
+  for (curr = L1->openupval; curr != NULL; curr = curr->gch.next)
+    makewhite(g, curr);
+}
+
+
 static GCObject **sweeplist (lua_State *L, GCObject **p, int all,
                              l_mem *plim) {
   GCObject *curr;
@@ -439,10 +447,14 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, int all,
     lim -= objsize(curr);
     if (!all && (!(mark & dead) || testbit(mark, FIXEDBIT))) {
       makewhite(g, curr);
+      if (curr->gch.tt == LUA_TTHREAD)
+        sweepupvalues(g, gco2th(curr));
       p = &curr->gch.next;
     }
     else {
       *p = curr->gch.next;
+      if (curr == g->rootgc)  /* is the first element of the list? */
+        g->rootgc = curr->gch.next;  /* adjust first */
       freeobj(L, curr);
     }
     if (lim <= 0) break;
@@ -537,7 +549,8 @@ void luaC_sweepall (lua_State *L) {
 /* mark root set */
 static void markroot (lua_State *L) {
   global_State *g = G(L);
-  lua_assert(g->gray == NULL && g->grayagain == NULL);
+  lua_assert(g->gray == NULL);
+  g->grayagain = NULL;
   g->weak = NULL;
   makewhite(g, obj2gco(g->mainthread));
   markobject(g, g->mainthread);
@@ -550,28 +563,30 @@ static void markroot (lua_State *L) {
 static void atomic (lua_State *L) {
   global_State *g = G(L);
   lua_assert(g->gray == NULL);
+  /* remark weak tables */
+  g->gray = g->weak;
+  g->weak = NULL;
+  propagatemarks(g, MAXLMEM);
+  /* remark gray again */
   g->gray = g->grayagain;
   g->grayagain = NULL;
   propagatemarks(g, MAXLMEM);
-  luaC_separateudata(L);  /* separate userdata to be preserved */
+  luaC_separateudata(L, 0);  /* separate userdata to be preserved */
   marktmu(g);  /* mark `preserved' userdata */
   propagatemarks(g, MAXLMEM);  /* remark, to propagate `preserveness' */
   cleartable(g->weak);  /* remove collected objects from weak tables */
   /* flip current white */
   g->currentwhite = otherwhite(g);
-  /* first element of root list will be used as temporary head for sweep
-     phase, so it won't be swept */
-  makewhite(g, g->rootgc);
-  g->sweepgc = &g->rootgc->gch.next;
+  g->sweepgc = &g->rootgc;
   g->sweepstrgc = 0;
   g->gcstate = GCSsweepstring;
-  g->grayagain = NULL;
 }
 
 
 void luaC_step (lua_State *L) {
   global_State *g = G(L);
   l_mem lim = (g->nblocks - (g->GCthreshold - GCSTEPSIZE)) * 2;
+luaC_checkall(L);
   switch (g->gcstate) {
     case GCSpropagate: {
       if (g->gray)
@@ -593,8 +608,9 @@ void luaC_step (lua_State *L) {
     case GCSsweep: {
       g->sweepgc = sweeplist(L, g->sweepgc, 0, &lim);
       if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
-        g->gcstate = GCSfinalize;  /* end sweep phase */
         checkSizes(L);
+        sweepupvalues(g, g->mainthread);
+        g->gcstate = GCSfinalize;  /* end sweep phase */
       }
       break;
     }
@@ -610,13 +626,14 @@ void luaC_step (lua_State *L) {
     default: lua_assert(0);
   }
   g->GCthreshold = g->nblocks + GCSTEPSIZE - lim/2;
+luaC_checkall(L);
 }
 
 
 void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
   global_State *g = G(L);
   lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
-  if (g->gcstate >= GCSsweepstring)  /* sweeping phases? */
+  if (g->gcstate != GCSpropagate)  /* sweeping phases? */
     black2gray(o);  /* just mark as gray to avoid other barriers */
   else  /* breaking invariant! */
     reallymarkobject(g, v);  /* restore it */
diff --git a/lgc.h b/lgc.h
index bd8bdadc..a6901076 100644
--- a/lgc.h
+++ b/lgc.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.h,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
+** $Id: lgc.h,v 2.2 2003/12/12 18:29:34 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -81,7 +81,7 @@
         { if (iswhite(obj2gco(o)) && isblack(obj2gco(p))) \
                 luaC_barrierf(L,obj2gco(p),obj2gco(o)); }
 
-size_t luaC_separateudata (lua_State *L);
+size_t luaC_separateudata (lua_State *L, int all);
 void luaC_callGCTM (lua_State *L);
 void luaC_sweepall (lua_State *L);
 void luaC_step (lua_State *L);
diff --git a/lobject.h b/lobject.h
index fa5364c2..4cdb1701 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 1.162 2003/11/18 14:55:11 roberto Exp roberto $
+** $Id: lobject.h,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -99,9 +99,9 @@ typedef struct lua_TValue {
 #define checkconsistency(obj) \
   lua_assert(!iscollectable(obj) || (ttype(obj) == (obj)->value.gc->gch.tt))
 
-#define checkliveness(L,obj) \
+#define checkliveness(g,obj) \
   lua_assert(!iscollectable(obj) || \
-  ((ttype(obj) == (obj)->value.gc->gch.tt) && !isdead(G(L), (obj)->value.gc)))
+  ((ttype(obj) == (obj)->value.gc->gch.tt) && !isdead(g, (obj)->value.gc)))
 
 
 /* Macros to set values */
@@ -122,32 +122,32 @@ typedef struct lua_TValue {
 #define setsvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TSTRING; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 #define setuvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TUSERDATA; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 #define setthvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TTHREAD; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 #define setclvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TFUNCTION; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 #define sethvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TTABLE; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 #define setptvalue(L,obj,x) \
   { TValue *i_o=(obj); \
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TPROTO; \
-    checkliveness(L,i_o); }
+    checkliveness(G(L),i_o); }
 
 
 
@@ -155,7 +155,7 @@ typedef struct lua_TValue {
 #define setobj(L,obj1,obj2) \
   { const TValue *o2=(obj2); TValue *o1=(obj1); \
     o1->tt=o2->tt; o1->value = o2->value; \
-    checkliveness(L,o1); }
+    checkliveness(G(L),o1); }
 
 
 /*
diff --git a/lstate.c b/lstate.c
index 13b15f6f..36e7d9c3 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.c,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
+** $Id: lstate.c,v 2.2 2003/12/12 18:29:34 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -200,7 +200,7 @@ LUA_API void lua_close (lua_State *L) {
   lua_lock(L);
   L = G(L)->mainthread;  /* only the main thread can be closed */
   luaF_close(L, L->stack);  /* close all upvalues for this thread */
-  luaC_separateudata(L);  /* separate udata that have GC metamethods */
+  luaC_separateudata(L, 1);  /* separate udata that have GC metamethods */
   L->errfunc = 0;  /* no error function during GC metamethods */
   do {  /* repeat until no more errors */
     L->ci = L->base_ci;
diff --git a/ltests.c b/ltests.c
index 05093162..581b47ff 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 1.169 2003/11/19 12:21:57 roberto Exp roberto $
+** $Id: ltests.c,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -143,6 +143,188 @@ void *debug_realloc (void *ud, void *block, size_t oldsize, size_t size) {
 
 /*
 ** {======================================================
+** Functions to check memory consistency
+** =======================================================
+*/
+
+static int testobjref1 (global_State *g, GCObject *f, GCObject *t) {
+  if (isdead(g,t)) return 0;
+  if (g->gcstate == GCSpropagate)
+    return !isblack(f) || !iswhite(t);
+  else if (g->gcstate == GCSfinalize)
+    return iswhite(f);
+  else
+    return 1;
+}
+
+
+static void printobj (global_State *g, GCObject *o) {
+int i = 0;
+GCObject *p;
+for (p = g->rootgc; p != o && p != NULL; p = p->gch.next) i++;
+if (p == NULL) i = -1;
+printf("%d:%s(%p)-%c",
+i, luaT_typenames[o->gch.tt], (void *)o,
+isdead(g,o)?'d':isblack(o)?'b':iswhite(o)?'w':'g');
+}
+
+
+static int testobjref (global_State *g, GCObject *f, GCObject *t) {
+  int r = testobjref1(g,f,t);
+if (!r) {
+printf("%d - ", g->gcstate);
+printobj(g, f);
+printf("\t-> ");
+printobj(g, t);
+printf("\n");
+}
+  return r;
+}
+
+#define checkobjref(g,f,t) lua_assert(testobjref(g,f,obj2gco(t)))
+
+#define checkvalref(g,f,t) lua_assert(!iscollectable(t) || \
+        ((ttype(t) == (t)->value.gc->gch.tt) && testobjref(g,f,gcvalue(t))))
+
+
+
+static void checktable (global_State *g, Table *h) {
+  int i;
+  int weakkey = 0;
+  int weakvalue = 0;
+  const TValue *mode;
+  GCObject *hgc = obj2gco(h);
+  if (h->metatable)
+    checkobjref(g, hgc, h->metatable);
+  lua_assert(h->lsizenode || h->node == g->dummynode);
+  mode = gfasttm(g, h->metatable, TM_MODE);
+  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
+    weakkey = (strchr(svalue(mode), 'k') != NULL);
+    weakvalue = (strchr(svalue(mode), 'v') != NULL);
+  }
+  i = h->sizearray;
+  while (i--)
+    checkvalref(g, hgc, &h->array[i]);
+  i = sizenode(h);
+  while (i--) {
+    Node *n = gnode(h, i);
+    if (!ttisnil(gval(n))) {
+      lua_assert(!ttisnil(gkey(n)));
+      checkvalref(g, hgc, gkey(n));
+      checkvalref(g, hgc, gval(n));
+    }
+  }
+}
+
+
+/*
+** All marks are conditional because a GC may happen while the
+** prototype is still being created
+*/
+static void checkproto (global_State *g, Proto *f) {
+  int i;
+  GCObject *fgc = obj2gco(f);
+  if (f->source) checkobjref(g, fgc, f->source);
+  for (i=0; i<f->sizek; i++) {
+    if (ttisstring(f->k+i))
+      checkobjref(g, fgc, rawtsvalue(f->k+i));
+  }
+  for (i=0; i<f->sizeupvalues; i++) {
+    if (f->upvalues[i])
+      checkobjref(g, fgc, f->upvalues[i]);
+  }
+  for (i=0; i<f->sizep; i++) {
+    if (f->p[i])
+      checkobjref(g, fgc, f->p[i]);
+  }
+  for (i=0; i<f->sizelocvars; i++) {
+    if (f->locvars[i].varname)
+      checkobjref(g, fgc, f->locvars[i].varname);
+  }
+}
+
+
+
+static void checkclosure (global_State *g, Closure *cl) {
+  GCObject *clgc = obj2gco(cl);
+  if (cl->c.isC) {
+    int i;
+    for (i=0; i<cl->c.nupvalues; i++)
+      checkvalref(g, clgc, &cl->c.upvalue[i]);
+  }
+  else {
+    int i;
+    lua_assert(cl->l.nupvalues == cl->l.p->nups);
+    checkobjref(g, clgc, hvalue(&cl->l.g));
+    checkobjref(g, clgc, cl->l.p);
+    for (i=0; i<cl->l.nupvalues; i++) {
+      lua_assert(cl->l.upvals[i]->tt == LUA_TUPVAL);
+      checkobjref(g, clgc, cl->l.upvals[i]);
+    }
+  }
+}
+
+
+static void checkstack (global_State *g, lua_State *L1) {
+  StkId o;
+  CallInfo *ci;
+  lua_assert(!isdead(g, obj2gco(L1)));
+  checkliveness(g, gt(L1));
+  for (ci = L1->base_ci; ci <= L1->ci; ci++)
+    lua_assert(ci->top <= L1->stack_last);
+  for (o = L1->stack; o < L1->top; o++)
+    checkliveness(g, o);
+}
+
+
+void luaC_checkall (lua_State *L) {
+  global_State *g = G(L);
+  GCObject *o;
+  checkstack(g, g->mainthread);
+  for (o = g->rootgc; o; o = o->gch.next) {
+    if (isdead(g, o))
+      lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
+    else {
+      switch (o->gch.tt) {
+        case LUA_TUPVAL: {
+          UpVal *uv = gco2uv(o);
+          lua_assert(uv->v == &uv->value);  /* must be closed */
+          checkvalref(g, o, uv->v);
+          break;
+        }
+        case LUA_TUSERDATA: {
+          Table *mt = gco2u(o)->metatable;
+          if (mt) checkobjref(g, o, mt);
+          break;
+        }
+        case LUA_TTABLE: {
+          checktable(g, gco2h(o));
+          break;
+        }
+        case LUA_TTHREAD: {
+          checkstack(g, gco2th(o));
+          break;
+        }
+        case LUA_TFUNCTION: {
+          checkclosure(g, gco2cl(o));
+          break;
+        }
+        case LUA_TPROTO: {
+          checkproto(g, gco2p(o));
+          break;
+        }
+        default: lua_assert(0);
+      }
+    }
+  }
+}
+
+/* }====================================================== */
+
+
+
+/*
+** {======================================================
 ** Disassembler
 ** =======================================================
 */
diff --git a/ltests.h b/ltests.h
index 2fc73fda..648b351f 100644
--- a/ltests.h
+++ b/ltests.h
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.h,v 1.21 2003/10/02 20:31:17 roberto Exp roberto $
+** $Id: ltests.h,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
 ** Internal Header for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -42,6 +42,8 @@ void *debug_realloc (void *ud, void *block, size_t osize, size_t nsize);
 #endif
 
 
+void luaC_checkall (lua_State *L);
+
 
 /* test for lock/unlock */
 extern int islocked;
diff --git a/ltm.c b/ltm.c
index 230fbba6..389cd7c4 100644
--- a/ltm.c
+++ b/ltm.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltm.c,v 1.107 2003/12/01 18:22:56 roberto Exp roberto $
+** $Id: ltm.c,v 2.1 2003/12/10 12:13:36 roberto Exp roberto $
 ** Tag methods
 ** See Copyright Notice in lua.h
 */
@@ -21,7 +21,8 @@
 
 const char *const luaT_typenames[] = {
   "nil", "boolean", "userdata", "number",
-  "string", "table", "function", "userdata", "thread"
+  "string", "table", "function", "userdata", "thread",
+  "proto", "upval"
 };