draft version of a generational mode for garbage collection. (Not well

tested; no major collections; ...)

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);