From 74123e96869bdb55d3967036e2bc0c6f9e0550d6 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 22 Mar 2010 15:28:03 -0300 Subject: draft version of a generational mode for garbage collection. (Not well tested; no major collections; ...) --- lapi.c | 8 ++++++- lbaselib.c | 6 ++--- lgc.c | 81 +++++++++++++++++++++++++++++++++++++++++--------------------- lstate.h | 7 +++--- lua.h | 3 ++- 5 files changed, 70 insertions(+), 35 deletions(-) diff --git a/lapi.c b/lapi.c index b1439d1e..59dcb612 100644 --- a/lapi.c +++ b/lapi.c @@ -1,5 +1,5 @@ /* -** $Id: lapi.c,v 2.113 2010/02/09 11:55:37 roberto Exp roberto $ +** $Id: lapi.c,v 2.114 2010/03/08 16:55:52 roberto Exp roberto $ ** Lua API ** See Copyright Notice in lua.h */ @@ -928,6 +928,7 @@ LUA_API int lua_gc (lua_State *L, int what, int data) { break; } case LUA_GCRESTART: { + g->gckind = KGC_NORMAL; g->GCthreshold = g->totalbytes; break; } @@ -973,6 +974,11 @@ LUA_API int lua_gc (lua_State *L, int what, int data) { res = (g->GCthreshold != MAX_LUMEM); break; } + case LUA_GCGEN: { /* change collector to generational mode */ + luaC_runtilstate(L, bitmask(GCSpropagate)); + g->gckind = KGC_GEN; + break; + } default: res = -1; /* invalid option */ } lua_unlock(L); diff --git a/lbaselib.c b/lbaselib.c index 3af55a79..bba92816 100644 --- a/lbaselib.c +++ b/lbaselib.c @@ -1,5 +1,5 @@ /* -** $Id: lbaselib.c,v 1.237 2010/03/13 03:57:46 roberto Exp roberto $ +** $Id: lbaselib.c,v 1.238 2010/03/19 15:52:48 roberto Exp roberto $ ** Basic library ** See Copyright Notice in lua.h */ @@ -186,10 +186,10 @@ static int luaB_gcinfo (lua_State *L) { static int luaB_collectgarbage (lua_State *L) { static const char *const opts[] = {"stop", "restart", "collect", - "count", "step", "setpause", "setstepmul", "isrunning", NULL}; + "count", "step", "setpause", "setstepmul", "isrunning", "gen", NULL}; static const int optsnum[] = {LUA_GCSTOP, LUA_GCRESTART, LUA_GCCOLLECT, LUA_GCCOUNT, LUA_GCSTEP, LUA_GCSETPAUSE, LUA_GCSETSTEPMUL, - LUA_GCISRUNNING}; + LUA_GCISRUNNING, LUA_GCGEN}; int o = optsnum[luaL_checkoption(L, 1, "collect", opts)]; int ex = luaL_optint(L, 2, 0); int res = lua_gc(L, o, ex); diff --git a/lgc.c b/lgc.c index c2fd79a4..c245e3a9 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 2.66 2009/12/16 16:42:58 roberto Exp roberto $ +** $Id: lgc.c,v 2.67 2009/12/22 15:32:50 roberto Exp roberto $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -29,7 +29,7 @@ #define GCFINALIZECOST 100 -#define maskcolors cast_byte(~(bitmask(BLACKBIT)|WHITEBITS)) +#define maskcolors (~(bitmask(BLACKBIT)|WHITEBITS)) #define makewhite(g,x) \ (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g))) @@ -95,10 +95,10 @@ static int iscleared (const TValue *o, int iskey) { 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)); - lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause); + lua_assert(g->gckind == KGC_GEN || + (g->gcstate != GCSfinalize && g->gcstate != GCSpause)); lua_assert(gch(o)->tt != LUA_TTABLE); - /* must keep invariant? */ - if (g->gcstate == GCSpropagate) + if (g->gcstate == GCSpropagate) /* must keep invariant? */ reallymarkobject(g, v); /* restore invariant */ else /* don't mind */ makewhite(g, o); /* mark as white just to avoid other barriers */ @@ -109,7 +109,8 @@ void luaC_barrierback (lua_State *L, Table *t) { global_State *g = G(L); GCObject *o = obj2gco(t); lua_assert(isblack(o) && !isdead(g, o)); - lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause); + lua_assert(g->gckind == KGC_GEN || + (g->gcstate != GCSfinalize && g->gcstate != GCSpause)); black2gray(o); /* make table gray (again) */ t->gclist = g->grayagain; g->grayagain = o; @@ -234,7 +235,6 @@ static void markroot (lua_State *L) { markvalue(g, &g->l_registry); markmt(g); markbeingfnz(g); /* mark any finalizing object left from previous cycle */ - g->gcstate = GCSpropagate; } @@ -401,8 +401,9 @@ static void traversestack (global_State *g, lua_State *L) { /* -** traverse one gray object, turning it to black. -** Returns `quantity' traversed. +** traverse one gray object, turning it to black (except for threads, +** which are always gray). +** Returns 'quantity' traversed. */ static l_mem propagatemark (global_State *g) { GCObject *o = g->gray; @@ -547,13 +548,16 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) { GCObject *curr; global_State *g = G(L); int deadmask = otherwhite(g); + int gckind = g->gckind; while ((curr = *p) != NULL && count-- > 0) { int alive = (gch(curr)->marked ^ WHITEBITS) & deadmask; if (gch(curr)->tt == LUA_TTHREAD) sweepthread(L, gco2th(curr), alive); if (alive) { lua_assert(!isdead(g, curr) || testbit(gch(curr)->marked, FIXEDBIT)); - makewhite(g, curr); /* make it white (for next cycle) */ + /* in generational mode all live objects are kept black, which + means they grow to old generation */ + if (gckind != KGC_GEN) makewhite(g, curr); p = &gch(curr)->next; } else { /* must erase `curr' */ @@ -700,7 +704,6 @@ void luaC_freeallobjects (lua_State *L) { static void atomic (lua_State *L) { global_State *g = G(L); - g->gcstate = GCSatomic; lua_assert(!iswhite(obj2gco(g->mainthread))); markobject(g, L); /* mark running thread */ /* registry and global metatables may be changed by API */ @@ -725,8 +728,7 @@ static void atomic (lua_State *L) { cleartable(g->ephemeron); cleartable(g->allweak); g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ - g->sweepstrgc = 0; /* go to sweep phase */ - g->gcstate = GCSsweepstring; + g->sweepstrgc = 0; /* prepare sweep phase */ } @@ -736,13 +738,16 @@ static l_mem singlestep (lua_State *L) { switch (g->gcstate) { case GCSpause: { markroot(L); /* start a new collection */ + g->gcstate = GCSpropagate; return 0; } case GCSpropagate: { if (g->gray) return propagatemark(g); else { /* no more `gray' objects */ - atomic(L); /* finish mark phase */ + g->gcstate = GCSatomic; /* finish mark phase */ + atomic(L); + g->gcstate = GCSsweepstring; return 0; } } @@ -776,7 +781,33 @@ static l_mem singlestep (lua_State *L) { } -void luaC_step (lua_State *L) { +/* +** advances the garbage collector until it reaches a state allowed +** by 'statemask' +*/ +void luaC_runtilstate (lua_State *L, int statesmask) { + global_State *g = G(L); + while (!testbit(statesmask, g->gcstate)) + singlestep(L); +} + + +static void generationalcollection (lua_State *L) { +static int c = 0; +static int prev = 0; + global_State *g = G(L); +int a = g->totalbytes; + lua_assert(g->gcstate == GCSpropagate); + luaC_runtilstate(L, bitmask(GCSpause)); + g->gcstate = GCSpropagate; /* do not run 'markroot' */ + g->GCthreshold = (g->totalbytes/100) * g->gcpause; +/*printf("count: %d old: %d new: %d dif: %d\n", c++, a, g->totalbytes, +g->totalbytes - prev);*/ +prev = g->totalbytes; +} + + +static void step (lua_State *L) { global_State *g = G(L); l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul; /* how much to work */ lu_mem debt = g->totalbytes - g->GCthreshold; @@ -792,14 +823,9 @@ void luaC_step (lua_State *L) { } -/* -** advances the garbage collector until it reaches a state allowed -** by 'statemask' -*/ -void luaC_runtilstate (lua_State *L, int statesmask) { - global_State *g = G(L); - while (!testbit(statesmask, g->gcstate)) - singlestep(L); +void luaC_step (lua_State *L) { + if (G(L)->gckind == KGC_GEN) generationalcollection(L); + else step(L); } @@ -809,7 +835,8 @@ void luaC_runtilstate (lua_State *L, int statesmask) { */ void luaC_fullgc (lua_State *L, int isemergency) { global_State *g = G(L); - lua_assert(g->gckind == KGC_NORMAL); + int origkind = g->gckind; + lua_assert(origkind == KGC_NORMAL || origkind == KGC_GEN); g->gckind = isemergency ? KGC_EMERGENCY : KGC_FORCED; if (g->gcstate == GCSpropagate) { /* marking phase? */ /* must sweep all objects to turn them back to white @@ -819,12 +846,12 @@ void luaC_fullgc (lua_State *L, int isemergency) { } /* finish any pending sweep phase */ luaC_runtilstate(L, ~bit2mask(GCSsweepstring, GCSsweep)); - markroot(L); /* start a new collection */ + g->gcstate = GCSpause; /* start a new collection */ /* run collector up to finalizers */ luaC_runtilstate(L, bitmask(GCSfinalize)); - g->gckind = KGC_NORMAL; + g->gckind = origkind; if (!isemergency) /* do not run finalizers during emergency GC */ - luaC_runtilstate(L, ~bitmask(GCSfinalize)); + luaC_runtilstate(L, bitmask(GCSpause)); g->GCthreshold = (g->totalbytes/100) * g->gcpause; } diff --git a/lstate.h b/lstate.h index eb0068fe..ebf4e4af 100644 --- a/lstate.h +++ b/lstate.h @@ -1,5 +1,5 @@ /* -** $Id: lstate.h,v 2.53 2010/02/09 11:55:37 roberto Exp roberto $ +** $Id: lstate.h,v 2.54 2010/03/13 15:55:42 roberto Exp roberto $ ** Global State ** See Copyright Notice in lua.h */ @@ -58,6 +58,7 @@ struct lua_longjmp; /* defined in ldo.c */ #define KGC_NORMAL 0 #define KGC_FORCED 1 /* gc was forced by the program */ #define KGC_EMERGENCY 2 /* gc was forced by an allocation failure */ +#define KGC_GEN 3 /* generational collection */ typedef struct stringtable { @@ -142,9 +143,9 @@ typedef struct global_State { struct lua_State *mainthread; UpVal uvhead; /* head of double-linked list of all open upvalues */ const lua_Number *version; /* pointer to version number */ - struct Table *mt[NUM_TAGS]; /* metatables for basic types */ - TString *tmname[TM_N]; /* array with tag-method names */ TString *envn; /* environment variable name */ + TString *tmname[TM_N]; /* array with tag-method names */ + struct Table *mt[NUM_TAGS]; /* metatables for basic types */ } global_State; diff --git a/lua.h b/lua.h index 17852e08..a0f909a5 100644 --- a/lua.h +++ b/lua.h @@ -1,5 +1,5 @@ /* -** $Id: lua.h,v 1.262 2010/03/13 03:57:46 roberto Exp roberto $ +** $Id: lua.h,v 1.263 2010/03/19 21:04:17 roberto Exp roberto $ ** Lua - A Scripting Language ** Lua.org, PUC-Rio, Brazil (http://www.lua.org) ** See Copyright Notice at the end of this file @@ -267,6 +267,7 @@ LUA_API int (lua_status) (lua_State *L); #define LUA_GCSETPAUSE 6 #define LUA_GCSETSTEPMUL 7 #define LUA_GCISRUNNING 8 +#define LUA_GCGEN 9 LUA_API int (lua_gc) (lua_State *L, int what, int data); -- cgit v1.2.3-55-g6feb