commit 3010eb05365e77065009db39d20ef9a4110479a6
parent 2f91f95d94d3a27fee6b45c31ea9ab631924a8bf
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Wed, 13 Nov 2002 09:48:57 -0200
all objects with several children (tables, closures, stacks, prototypes)
go to `gray' queue
Diffstat:
M | lgc.c | | | 288 | ++++++++++++++++++++++++++++++++++++++++++++----------------------------------- |
M | lobject.h | | | 16 | ++++++++-------- |
2 files changed, 170 insertions(+), 134 deletions(-)
diff --git 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 */
- Table *wk; /* list of visited key-weak tables (to be cleared after GC) */
- Table *wv; /* list of visited value-weak tables */
- Table *wkv; /* list of visited key-value weak tables */
- lua_State *L;
+ GCObject *tmark; /* list of marked objects to be traversed */
+ GCObject *wk; /* list of traversed key-weak tables (to be cleared) */
+ GCObject *wv; /* list of traversed value-weak tables */
+ GCObject *wkv; /* list of traversed key-value weak tables */
+ 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))) \
- reallymarkobject(st, cast(GCObject *, (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));
-}
+#define markvalue(st,t) { if (!ismarked(valtogco(t))) \
+ reallymarkobject(st, valtogco(t)); }
-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: {
- markclosure(st, &o->cl);
+ case LUA_TUSERDATA: {
+ markvalue(st, gcotou(o)->uv.metatable);
break;
}
- case LUA_TUSERDATA: {
- marktable(st, (&o->u)->uv.metatable);
+ case LUA_TFUNCTION: {
+ gcotocl(o)->c.gclist = st->tmark;
+ st->tmark = o;
break;
}
case LUA_TTABLE: {
- (&o->h)->gclist = st->tmark; /* chain it for later traversal */
- st->tmark = &o->h;
+ gcotoh(o)->gclist = st->tmark;
+ 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))
- p = &curr->uv.next; /* don't bother with them */
+ if (ismarked(curr) || isfinalized(gcotou(curr)))
+ p = &curr->gch.next; /* don't bother with them */
- else if (fasttm(L, (&curr->u)->uv.metatable, TM_GC) == NULL) {
- markfinalized(&curr->u); /* don't need finalization */
- p = &curr->uv.next;
+ else if (fasttm(L, gcotou(curr)->uv.metatable, TM_GC) == NULL) {
+ markfinalized(gcotou(curr)); /* don't need finalization */
+ p = &curr->gch.next;
}
else { /* must call its gc method */
- *p = curr->uv.next;
- curr->uv.next = NULL; /* link `curr' at the end of `collected' list */
+ *p = curr->gch.next;
+ 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);
- lua_assert(h->lsizenode || h->node == G(st->L)->dummynode);
+ markvalue(st, h->metatable);
+ 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 */
- Table *h = st->tmark; /* get first table from list */
- st->tmark = h->gclist; /* remove it from list */
- traversetable(st, h);
+ while (st->tmark) { /* traverse marked objects */
+ switch (st->tmark->gch.tt) {
+ case LUA_TTABLE: {
+ 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) {
- for (; h; h = h->gclist) {
+static void cleartablekeys (GCObject *l) {
+ 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) {
- for (; h; h = h->gclist) {
+static void cleartablevalues (GCObject *l) {
+ 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_TFUNCTION: luaF_freeclosure(L, &o->cl); break;
- case LUA_TUPVAL: luaM_freelem(L, &o->uv); break;
- case LUA_TTABLE: luaH_free(L, &o->h); break;
+ case LUA_TPROTO: luaF_freeproto(L, gcotop(o)); break;
+ case LUA_TFUNCTION: luaF_freeclosure(L, gcotocl(o)); break;
+ case LUA_TUPVAL: luaM_freelem(L, gcotouv(o)); break;
+ case LUA_TTABLE: luaH_free(L, gcotoh(o)); break;
case LUA_TTHREAD: {
- lua_assert(&o->th != L && &o->th != G(L)->mainthread);
- luaE_freethread(L, &o->th);
+ lua_assert(gcototh(o) != L && gcototh(o) != G(L)->mainthread);
+ 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;
- setuvalue(L->top - 1, &udata->u); /* keep a reference to it */
- unmark(udata);
- markfinalized(&udata->u);
- do1gcTM(L, &udata->u);
+ G(L)->rootudata = o;
+ setuvalue(L->top - 1, udata); /* keep a reference to it */
+ unmark(o);
+ markfinalized(udata);
+ 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) {
- lua_State *L = st->L;
+static void markroot (GCState *st, lua_State *L) {
+ global_State *G = st->G;
markobject(st, defaultmeta(L));
markobject(st, registry(L));
- markstack(st, G(L)->mainthread);
- if (L != G(L)->mainthread) /* another thread is running? */
- reallymarkobject(st, cast(GCObject *, L)); /* cannot collect it */
+ traversestack(st, G->mainthread);
+ if (L != G->mainthread) /* another thread is running? */
+ markvalue(st, L); /* cannot collect it */
}
static void mark (lua_State *L) {
GCState st;
- Table *wkv;
- st.L = L;
+ GCObject *wkv;
+ 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);
diff --git a/lobject.h b/lobject.h
@@ -1,5 +1,5 @@
/*
-** $Id: lobject.h,v 1.151 2002/11/04 12:31:44 roberto Exp roberto $
+** $Id: lobject.h,v 1.152 2002/11/07 15:37:10 roberto Exp roberto $
** Type definitions for Lua objects
** See Copyright Notice in lua.h
*/
@@ -219,6 +219,7 @@ typedef struct Proto {
int sizep; /* size of `p' */
int sizelocvars;
int lineDefined;
+ GCObject *gclist;
lu_byte nupvalues;
lu_byte numparams;
lu_byte is_vararg;
@@ -249,19 +250,18 @@ typedef struct UpVal {
** Closures
*/
+#define ClosureHeader \
+ CommonHeader; lu_byte isC; lu_byte nupvalues; GCObject *gclist
+
typedef struct CClosure {
- CommonHeader;
- lu_byte isC; /* 0 for Lua functions, 1 for C functions */
- lu_byte nupvalues;
+ ClosureHeader;
lua_CFunction f;
TObject upvalue[1];
} CClosure;
typedef struct LClosure {
- CommonHeader;
- lu_byte isC;
- lu_byte nupvalues; /* first five fields must be equal to CClosure!! */
+ ClosureHeader;
struct Proto *p;
TObject g; /* global table for this closure */
UpVal *upvals[1];
@@ -298,7 +298,7 @@ typedef struct Table {
TObject *array; /* array part */
Node *node;
Node *firstfree; /* this position is free; all positions after it are full */
- struct Table *gclist;
+ GCObject *gclist;
int sizearray; /* size of `array' array */
} Table;