From d9e61e8ceafe8c3f6ad936979719ca7c446ce228 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 7 Aug 2000 17:21:34 -0300 Subject: new algorithm for traversing in GC to avoid deep recursion calls --- lgc.c | 148 ++++++++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 86 insertions(+), 62 deletions(-) (limited to 'lgc.c') diff --git a/lgc.c b/lgc.c index 7bdc5790..d884d224 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 1.58 2000/06/26 19:28:31 roberto Exp roberto $ +** $Id: lgc.c,v 1.59 2000/06/30 14:35:17 roberto Exp roberto $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -20,97 +20,94 @@ #include "ltm.h" +typedef struct GCState { + Hash *tmark; /* list of marked tables to be visited */ + Closure *cmark; /* list of marked closures to be visited */ +} GCState; -static int markobject (lua_State *L, TObject *o); + +static int markobject (GCState *st, TObject *o); /* mark a string; marks larger than 1 cannot be changed */ -#define strmark(L, s) {if ((s)->marked == 0) (s)->marked = 1;} +#define strmark(s) {if ((s)->marked == 0) (s)->marked = 1;} -static void protomark (lua_State *L, Proto *f) { +static void protomark (Proto *f) { if (!f->marked) { int i; f->marked = 1; - strmark(L, f->source); + strmark(f->source); for (i=0; inkstr; i++) - strmark(L, f->kstr[i]); + strmark(f->kstr[i]); for (i=0; inkproto; i++) - protomark(L, f->kproto[i]); + protomark(f->kproto[i]); if (f->locvars) { /* is there debug information? */ LocVar *lv; for (lv=f->locvars; lv->pc != -1; lv++) /* mark local-variable names */ - if (lv->varname) strmark(L, lv->varname); + if (lv->varname) strmark(lv->varname); } } } -static void closuremark (lua_State *L, Closure *f) { - if (!f->marked) { - int i = f->nupvalues; - f->marked = 1; - while (i--) - markobject(L, &f->upvalue[i]); - } -} - - -static void tablemark (lua_State *L, Hash *h) { - if (!h->marked) { - int i; - h->marked = 1; - for (i=h->size-1; i>=0; i--) { - Node *n = node(h,i); - if (ttype(key(n)) != TAG_NIL) { - if (ttype(val(n)) == TAG_NIL) - luaH_remove(h, key(n)); /* dead element; try to remove it */ - markobject(L, &n->key); - markobject(L, &n->val); - } - } - } -} - - -static void travstack (lua_State *L) { +static void markstack (lua_State *L, GCState *st) { StkId o; for (o=L->stack; otop; o++) - markobject(L, o); + markobject(st, o); } -static void travlock (lua_State *L) { +static void marklock (lua_State *L, GCState *st) { int i; for (i=0; irefSize; i++) { if (L->refArray[i].st == LOCK) - markobject(L, &L->refArray[i].o); + markobject(st, &L->refArray[i].o); + } +} + + +static void marktagmethods (lua_State *L, GCState *st) { + int e; + for (e=0; elast_tag; t++) + markobject(st, luaT_getim(L, t,e)); } } -static int markobject (lua_State *L, TObject *o) { +static int markobject (GCState *st, TObject *o) { switch (ttype(o)) { case TAG_USERDATA: case TAG_STRING: - strmark(L, tsvalue(o)); - break; - case TAG_TABLE: - tablemark(L, hvalue(o)); + strmark(tsvalue(o)); break; - case TAG_LCLOSURE: - protomark(L, clvalue(o)->f.l); - closuremark(L, clvalue(o)); + case TAG_TABLE: { + if (!ismarked(hvalue(o))) { + hvalue(o)->mark = st->tmark; /* chain it in list of marked */ + st->tmark = hvalue(o); + } break; + } case TAG_LMARK: { Closure *cl = infovalue(o)->func; - protomark(L, cl->f.l); - closuremark(L, cl); + if (!ismarked(cl)) { + protomark(cl->f.l); + cl->mark = st->cmark; /* chain it for later traversal */ + st->cmark = cl; + } break; } + case TAG_LCLOSURE: + protomark(clvalue(o)->f.l); + /* go through */ case TAG_CCLOSURE: case TAG_CMARK: - closuremark(L, clvalue(o)); + if (!ismarked(clvalue(o))) { + clvalue(o)->mark = st->cmark; /* chain it for later traversal */ + st->cmark = clvalue(o); + } break; default: break; /* numbers, etc */ } @@ -118,6 +115,41 @@ static int markobject (lua_State *L, TObject *o) { } +static void markall (lua_State *L) { + GCState st; + st.cmark = NULL; + st.tmark = L->gt; /* put table of globals in mark list */ + L->gt->mark = NULL; + marktagmethods(L, &st); /* mark tag methods */ + markstack(L, &st); /* mark stack objects */ + marklock(L, &st); /* mark locked objects */ + for (;;) { /* mark tables and closures */ + if (st.cmark) { + int i; + Closure *f = st.cmark; /* get first closure from list */ + st.cmark = f->mark; /* remove it from list */ + for (i=0; inupvalues; i++) /* mark its upvalues */ + markobject(&st, &f->upvalue[i]); + } + else if (st.tmark) { + int i; + Hash *h = st.tmark; /* get first table from list */ + st.tmark = h->mark; /* remove it from list */ + for (i=0; isize; i++) { + Node *n = node(h, i); + if (ttype(key(n)) != TAG_NIL) { + if (ttype(val(n)) == TAG_NIL) + luaH_remove(h, key(n)); /* dead element; try to remove it */ + markobject(&st, &n->key); + markobject(&st, &n->val); + } + } + } + else break; /* nothing else to mark */ + } +} + + static void collectproto (lua_State *L) { Proto **p = &L->rootproto; Proto *next; @@ -138,8 +170,8 @@ static void collectclosure (lua_State *L) { Closure **p = &L->rootcl; Closure *next; while ((next = *p) != NULL) { - if (next->marked) { - next->marked = 0; + if (ismarked(next)) { + next->mark = next; /* unmark */ p = &next->next; } else { @@ -154,8 +186,8 @@ static void collecttable (lua_State *L) { Hash **p = &L->roottable; Hash *next; while ((next = *p) != NULL) { - if (next->marked) { - next->marked = 0; + if (ismarked(next)) { + next->mark = next; /* unmark */ p = &next->next; } else { @@ -256,14 +288,6 @@ static void callgcTMudata (lua_State *L) { } -static void markall (lua_State *L) { - luaT_travtagmethods(L, markobject); /* mark tag methods */ - travstack(L); /* mark stack objects */ - tablemark(L, L->gt); /* mark global variables */ - travlock(L); /* mark locked objects */ -} - - void luaC_collect (lua_State *L, int all) { int oldah = L->allowhooks; L->allowhooks = 0; /* stop debug hooks during GC */ -- cgit v1.2.3-55-g6feb