all objects with several children (tables, closures, stacks, prototypes)

go to `gray' queue
author: Roberto Ierusalimschy <roberto@inf.puc-rio.br> 2002-11-13 09:49:19 -0200
committer: Roberto Ierusalimschy <roberto@inf.puc-rio.br> 2002-11-13 09:49:19 -0200
commit: 3010eb05365e77065009db39d20ef9a4110479a6 (patch)
tree: d880230c27289095a21a7350568b114b8c743242 /lgc.c
parent: 2f91f95d94d3a27fee6b45c31ea9ab631924a8bf (diff)
download: lua-3010eb05365e77065009db39d20ef9a4110479a6.tar.gz
lua-3010eb05365e77065009db39d20ef9a4110479a6.tar.bz2
lua-3010eb05365e77065009db39d20ef9a4110479a6.zip
1 files changed, 162 insertions, 126 deletions
diff --git a/lgc.c b/lgc.c
index 6fd41d34..72984d2a 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 1.155 2002/11/07 15:37:10 roberto Exp roberto $
+** $Id: lgc.c,v 1.156 2002/11/11 11:52:43 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -21,11 +21,11 @@
 typedef struct GCState {
-  Table *tmark;  /* list of marked tables to be visited */
+  GCObject *tmark;  /* list of marked objects to be traversed */
-  Table *wk;  /* list of visited key-weak tables (to be cleared after GC) */
+  GCObject *wk;  /* list of traversed key-weak tables (to be cleared) */
-  Table *wv;  /* list of visited value-weak tables */
+  GCObject *wv;  /* list of traversed value-weak tables */
-  Table *wkv;  /* list of visited key-value weak tables */
+  GCObject *wkv;  /* list of traversed key-value weak tables */
-  lua_State *L;
+  global_State *G;
 } GCState;
@@ -47,8 +47,6 @@ typedef struct GCState {
 #define markfinalized(u)        resetbit((u)->uv.marked, 1)
-static void reallymarkobject (GCState *st, GCObject *o);
 #define markobject(st,o) { checkconsistency(o); \
  if (iscollectable(o) && !ismarked(gcvalue(o))) reallymarkobject(st,gcvalue(o)); }
@@ -56,105 +54,50 @@ static void reallymarkobject (GCState *st, GCObject *o);
  if (iscollectable(o) && !ismarked(gcvalue(o)) && (c)) \
    reallymarkobject(st,gcvalue(o)); }
-#define marktable(st,t) { if (!ismarked(cast(GCObject *, t))) \
+#define markvalue(st,t) { if (!ismarked(valtogco(t))) \
-                reallymarkobject(st, cast(GCObject *, (t))); }
+                reallymarkobject(st, valtogco(t)); }
-static void markproto (Proto *f) {
-  if (!f->marked) {
-    int i;
-    f->marked = 1;
-    strmark(f->source);
-    for (i=0; i<f->sizek; i++) {
-      if (ttisstring(f->k+i))
-        strmark(tsvalue(f->k+i));
-    }
-    for (i=0; i<f->sizep; i++)
-      markproto(f->p[i]);
-    for (i=0; i<f->sizelocvars; i++)  /* mark local-variable names */
-      strmark(f->locvars[i].varname);
-  }
-  lua_assert(luaG_checkcode(f));
-}
-static void markclosure (GCState *st, Closure *cl) {
-  if (cl->c.isC) {
-    int i;
-    for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
-      markobject(st, &cl->c.upvalue[i]);
-  }
-  else {
-    int i;
-    lua_assert(cl->l.nupvalues == cl->l.p->nupvalues);
-    marktable(st, hvalue(&cl->l.g));
-    markproto(cl->l.p);
-    for (i=0; i<cl->l.nupvalues; i++) {  /* mark its upvalues */
-      UpVal *u = cl->l.upvals[i];
-      if (!u->marked) {
-        markobject(st, &u->value);
-        u->marked = 1;
-      }
-    }
-  }
-}
-static void checkstacksizes (lua_State *L, StkId max) {
-  int used = L->ci - L->base_ci;  /* number of `ci' in use */
-  if (4*used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
-    luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
-  used = max - L->stack;  /* part of stack in use */
-  if (4*used < L->stacksize && 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
-    luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
-}
-static void markstack (GCState *st, lua_State *L1) {
-  StkId o, lim;
-  CallInfo *ci;
-  markobject(st, gt(L1));
-  for (o=L1->stack; o<L1->top; o++)
-    markobject(st, o);
-  lim = o;
-  for (ci = L1->base_ci; ci <= L1->ci; ci++) {
-    lua_assert(ci->top <= L1->stack_last);
-    if (lim < ci->top) lim = ci->top;
-  }
-  for (; o<=lim; o++) setnilvalue(o);
-  checkstacksizes(L1, lim);
-}
 static void reallymarkobject (GCState *st, GCObject *o) {
+  lua_assert(!ismarked(o));
  setbit(o->gch.marked, 0);  /* mark object */
  switch (o->gch.tt) {
-    case LUA_TFUNCTION: {
+    case LUA_TUSERDATA: {
-      markclosure(st, &o->cl);
+      markvalue(st, gcotou(o)->uv.metatable);
      break;
    }
-    case LUA_TUSERDATA: {
+    case LUA_TFUNCTION: {
-      marktable(st, (&o->u)->uv.metatable);
+      gcotocl(o)->c.gclist = st->tmark;
+      st->tmark = o;
      break;
    }
    case LUA_TTABLE: {
-      (&o->h)->gclist = st->tmark;  /* chain it for later traversal */
+      gcotoh(o)->gclist = st->tmark;
-      st->tmark = &o->h;
+      st->tmark = o;
      break;
    }
    case LUA_TTHREAD: {
-      markstack(st, &o->th);
+      gcototh(o)->gclist = st->tmark;
+      st->tmark = o;
      break;
    }
+    case LUA_TPROTO: {
+      gcotop(o)->gclist = st->tmark;
+      st->tmark = o;
+      break;
+    }
+    default: lua_assert(o->gch.tt == LUA_TSTRING);
  }
 }
 static void marktmu (GCState *st) {
  GCObject *u;
-  for (u = G(st->L)->tmudata; u; u = u->uv.next)
+  for (u = st->G->tmudata; u; u = u->gch.next) {
+    unmark(u);  /* may be marked, if left from previous GC */
    reallymarkobject(st, u);
+  }
 }
@@ -166,18 +109,18 @@ static void separateudata (lua_State *L) {
  GCObject **lastcollected = &collected;
  while ((curr = *p) != NULL) {
    lua_assert(curr->gch.tt == LUA_TUSERDATA);
-    if (ismarked(curr) || isfinalized(&curr->u))
+    if (ismarked(curr) || isfinalized(gcotou(curr)))
-      p = &curr->uv.next;  /* don't bother with them */
+      p = &curr->gch.next;  /* don't bother with them */
-    else if (fasttm(L, (&curr->u)->uv.metatable, TM_GC) == NULL) {
+    else if (fasttm(L, gcotou(curr)->uv.metatable, TM_GC) == NULL) {
-      markfinalized(&curr->u);  /* don't need finalization */
+      markfinalized(gcotou(curr));  /* don't need finalization */
-      p = &curr->uv.next;
+      p = &curr->gch.next;
    }
    else {  /* must call its gc method */
-      *p = curr->uv.next;
+      *p = curr->gch.next;
-      curr->uv.next = NULL;  /* link `curr' at the end of `collected' list */
+      curr->gch.next = NULL;  /* link `curr' at the end of `collected' list */
      *lastcollected = curr;
-      lastcollected = &curr->uv.next;
+      lastcollected = &curr->gch.next;
    }
  }
  /* insert collected udata with gc event into `tmudata' list */
@@ -197,17 +140,17 @@ static void traversetable (GCState *st, Table *h) {
  int i;
  int weakkey = 0;
  int weakvalue = 0;
-  marktable(st, h->metatable);
+  markvalue(st, h->metatable);
-  lua_assert(h->lsizenode || h->node == G(st->L)->dummynode);
+  lua_assert(h->lsizenode || h->node == st->G->dummynode);
  if (h->mode & (WEAKKEY | WEAKVALUE)) {  /* weak table? */
-    Table **weaklist;
+    GCObject **weaklist;
    weakkey = h->mode & WEAKKEY;
    weakvalue = h->mode & WEAKVALUE;
    weaklist = (weakkey && weakvalue) ? &st->wkv :
                            (weakkey) ? &st->wk :
                                        &st->wv;
    h->gclist = *weaklist;  /* must be cleared after GC, ... */
-    *weaklist = h;  /* ... so put in the appropriate list */
+    *weaklist = valtogco(h);  /* ... so put in the appropriate list */
  }
  if (!weakvalue) {
    i = sizearray(h);
@@ -226,11 +169,99 @@ static void traversetable (GCState *st, Table *h) {
 }
+static void traverseproto (GCState *st, Proto *f) {
+  int i;
+  strmark(f->source);
+  for (i=0; i<f->sizek; i++) {
+    if (ttisstring(f->k+i))
+      strmark(tsvalue(f->k+i));
+  }
+  for (i=0; i<f->sizep; i++)
+    markvalue(st, f->p[i]);
+  for (i=0; i<f->sizelocvars; i++)  /* mark local-variable names */
+    strmark(f->locvars[i].varname);
+  lua_assert(luaG_checkcode(f));
+}
+static void traverseclosure (GCState *st, Closure *cl) {
+  if (cl->c.isC) {
+    int i;
+    for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
+      markobject(st, &cl->c.upvalue[i]);
+  }
+  else {
+    int i;
+    lua_assert(cl->l.nupvalues == cl->l.p->nupvalues);
+    markvalue(st, hvalue(&cl->l.g));
+    markvalue(st, cl->l.p);
+    for (i=0; i<cl->l.nupvalues; i++) {  /* mark its upvalues */
+      UpVal *u = cl->l.upvals[i];
+      if (!u->marked) {
+        markobject(st, &u->value);
+        u->marked = 1;
+      }
+    }
+  }
+}
+static void checkstacksizes (lua_State *L, StkId max) {
+  int used = L->ci - L->base_ci;  /* number of `ci' in use */
+  if (4*used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
+    luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
+  used = max - L->stack;  /* part of stack in use */
+  if (4*used < L->stacksize && 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
+    luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
+}
+static void traversestack (GCState *st, lua_State *L1) {
+  StkId o, lim;
+  CallInfo *ci;
+  markobject(st, gt(L1));
+  for (o=L1->stack; o<L1->top; o++)
+    markobject(st, o);
+  lim = o;
+  for (ci = L1->base_ci; ci <= L1->ci; ci++) {
+    lua_assert(ci->top <= L1->stack_last);
+    if (lim < ci->top) lim = ci->top;
+  }
+  for (; o<=lim; o++) setnilvalue(o);
+  checkstacksizes(L1, lim);
+}
 static void propagatemarks (GCState *st) {
-  while (st->tmark) {  /* traverse marked tables */
+  while (st->tmark) {  /* traverse marked objects */
-    Table *h = st->tmark;  /* get first table from list */
+    switch (st->tmark->gch.tt) {
-    st->tmark = h->gclist;  /* remove it from list */
+      case LUA_TTABLE: {
-    traversetable(st, h);
+        Table *h = gcotoh(st->tmark);
+        st->tmark = h->gclist;
+        traversetable(st, h);
+        break;
+      }
+      case LUA_TFUNCTION: {
+        Closure *cl = gcotocl(st->tmark);
+        st->tmark = cl->c.gclist;
+        traverseclosure(st, cl);
+        break;
+      }
+      case LUA_TTHREAD: {
+        lua_State *th = gcototh(st->tmark);
+        st->tmark = th->gclist;
+        traversestack(st, th);
+        break;
+      }
+      case LUA_TPROTO: {
+        Proto *p = gcotop(st->tmark);
+        st->tmark = p->gclist;
+        traverseproto(st, p);
+        break;
+      }
+      default: lua_assert(0);
+    }
  }
 }
@@ -245,8 +276,9 @@ static int valismarked (const TObject *o) {
 /*
 ** clear collected keys from weaktables
 */
-static void cleartablekeys (Table *h) {
+static void cleartablekeys (GCObject *l) {
-  for (; h; h = h->gclist) {
+  while (l) {
+    Table *h = gcotoh(l);
    int i = sizenode(h);
    lua_assert(h->mode & WEAKKEY);
    while (i--) {
@@ -254,6 +286,7 @@ static void cleartablekeys (Table *h) {
      if (!valismarked(key(n)))  /* key was collected? */
        removekey(n);  /* remove entry from table */
    }
+    l = h->gclist;
  }
 }
@@ -261,8 +294,9 @@ static void cleartablekeys (Table *h) {
 /*
 ** clear collected values from weaktables
 */
-static void cleartablevalues (Table *h) {
+static void cleartablevalues (GCObject *l) {
-  for (; h; h = h->gclist) {
+  while (l) {
+    Table *h = gcotoh(l);
    int i = sizearray(h);
    lua_assert(h->mode & WEAKVALUE);
    while (i--) {
@@ -276,27 +310,28 @@ static void cleartablevalues (Table *h) {
      if (!valismarked(val(n)))  /* value was collected? */
        removekey(n);  /* remove entry from table */
    }
+    l = h->gclist;
  }
 }
 static void freeobj (lua_State *L, GCObject *o) {
  switch (o->gch.tt) {
-    case LUA_TPROTO: luaF_freeproto(L, &o->p); break;
+    case LUA_TPROTO: luaF_freeproto(L, gcotop(o)); break;
-    case LUA_TFUNCTION: luaF_freeclosure(L, &o->cl); break;
+    case LUA_TFUNCTION: luaF_freeclosure(L, gcotocl(o)); break;
-    case LUA_TUPVAL: luaM_freelem(L, &o->uv); break;
+    case LUA_TUPVAL: luaM_freelem(L, gcotouv(o)); break;
-    case LUA_TTABLE: luaH_free(L, &o->h); break;
+    case LUA_TTABLE: luaH_free(L, gcotoh(o)); break;
    case LUA_TTHREAD: {
-      lua_assert(&o->th != L && &o->th != G(L)->mainthread);
+      lua_assert(gcototh(o) != L && gcototh(o) != G(L)->mainthread);
-      luaE_freethread(L, &o->th);
+      luaE_freethread(L, gcototh(o));
      break;
    }
    case LUA_TSTRING: {
-      luaM_free(L, o, sizestring((&o->ts)->tsv.len));
+      luaM_free(L, o, sizestring(gcotots(o)->tsv.len));
      break;
    }
    case LUA_TUSERDATA: {
-      luaM_free(L, o, sizeudata((&o->u)->uv.len));
+      luaM_free(L, o, sizeudata(gcotou(o)->uv.len));
      break;
    }
    default: lua_assert(0);
@@ -360,14 +395,15 @@ static void callGCTM (lua_State *L) {
  setallowhook(L, 0);  /* stop debug hooks during GC tag methods */
  L->top++;  /* reserve space to keep udata while runs its gc method */
  while (G(L)->tmudata != NULL) {
-    GCObject *udata = G(L)->tmudata;
+    GCObject *o = G(L)->tmudata;
+    Udata *udata = gcotou(o);
    G(L)->tmudata = udata->uv.next;  /* remove udata from `tmudata' */
    udata->uv.next = G(L)->rootudata;  /* return it to `root' list */
-    G(L)->rootudata = udata;
+    G(L)->rootudata = o;
-    setuvalue(L->top - 1, &udata->u);  /* keep a reference to it */
+    setuvalue(L->top - 1, udata);  /* keep a reference to it */
-    unmark(udata);
+    unmark(o);
-    markfinalized(&udata->u);
+    markfinalized(udata);
-    do1gcTM(L, &udata->u);
+    do1gcTM(L, udata);
  }
  L->top--;
  setallowhook(L, oldah);  /* restore hooks */
@@ -389,23 +425,23 @@ void luaC_sweep (lua_State *L, int all) {
 /* mark root set */
-static void markroot (GCState *st) {
+static void markroot (GCState *st, lua_State *L) {
-  lua_State *L = st->L;
+  global_State *G = st->G;
  markobject(st, defaultmeta(L));
  markobject(st, registry(L));
-  markstack(st, G(L)->mainthread);
+  traversestack(st, G->mainthread);
-  if (L != G(L)->mainthread)  /* another thread is running? */
+  if (L != G->mainthread)  /* another thread is running? */
-    reallymarkobject(st, cast(GCObject *, L));  /* cannot collect it */
+    markvalue(st, L);  /* cannot collect it */
 }
 static void mark (lua_State *L) {
  GCState st;
-  Table *wkv;
+  GCObject *wkv;
-  st.L = L;
+  st.G = G(L);
  st.tmark = NULL;
  st.wkv = st.wk = st.wv = NULL;
-  markroot(&st);
+  markroot(&st, L);
  propagatemarks(&st);  /* mark all reachable objects */
  cleartablevalues(st.wkv);
  cleartablevalues(st.wv);
author	Roberto Ierusalimschy <roberto@inf.puc-rio.br>	2002-11-13 09:49:19 -0200
committer	Roberto Ierusalimschy <roberto@inf.puc-rio.br>	2002-11-13 09:49:19 -0200
commit	3010eb05365e77065009db39d20ef9a4110479a6 (patch)
tree	d880230c27289095a21a7350568b114b8c743242 /lgc.c
parent	2f91f95d94d3a27fee6b45c31ea9ab631924a8bf (diff)
download	lua-3010eb05365e77065009db39d20ef9a4110479a6.tar.gz lua-3010eb05365e77065009db39d20ef9a4110479a6.tar.bz2 lua-3010eb05365e77065009db39d20ef9a4110479a6.zip