generational collection: new attempt (still incomplete)

8 files changed, 195 insertions, 40 deletions

diff --git a/lapi.c b/lapi.c
index 1c4d07dd..494fce75 100644
--- a/lapi.c
+++ b/lapi.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lapi.c,v 2.258 2016/01/05 16:07:21 roberto Exp roberto $
+** $Id: lapi.c,v 2.259 2016/02/29 14:27:14 roberto Exp roberto $
 ** Lua API
 ** See Copyright Notice in lua.h
 */
@@ -1097,6 +1097,14 @@ LUA_API int lua_gc (lua_State *L, int what, int data) {
       res = g->gcrunning;
       break;
     }
+    case LUA_GCGEN: {
+      luaC_changemode(L, KGC_GEN);
+      break;
+    }
+    case LUA_GCINC: {
+      luaC_changemode(L, KGC_NORMAL);
+      break;
+    }
     default: res = -1;  /* invalid option */
   }
   lua_unlock(L);
diff --git a/lbaselib.c b/lbaselib.c
index 98602952..04fdd5c2 100644
--- a/lbaselib.c
+++ b/lbaselib.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lbaselib.c,v 1.313 2016/04/11 19:18:40 roberto Exp roberto $
+** $Id: lbaselib.c,v 1.314 2016/09/05 19:06:34 roberto Exp roberto $
 ** Basic library
 ** See Copyright Notice in lua.h
 */
@@ -173,10 +173,10 @@ static int luaB_rawset (lua_State *L) {
 static int luaB_collectgarbage (lua_State *L) {
   static const char *const opts[] = {"stop", "restart", "collect",
     "count", "step", "setpause", "setstepmul",
-    "isrunning", NULL};
+    "isrunning", "generational", "incremental", 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, LUA_GCINC};
   int o = optsnum[luaL_checkoption(L, 1, "collect", opts)];
   int ex = (int)luaL_optinteger(L, 2, 0);
   int res = lua_gc(L, o, ex);
diff --git a/lgc.c b/lgc.c
index de3f2a21..44e5dc31 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.214 2016/11/07 12:38:35 roberto Exp roberto $
+** $Id: lgc.c,v 2.215 2016/12/22 13:08:50 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -59,11 +59,10 @@
 #define PAUSEADJ                100
 
 
-/*
-** 'makewhite' erases all color bits then sets only the current white
-** bit
-*/
+/* mask to erase all color bits */
 #define maskcolors      (~(bitmask(BLACKBIT) | WHITEBITS))
+
+/* macro to erase all color bits then sets only the current white bit */
 #define makewhite(g,x)  \
  (x->marked = cast_byte((x->marked & maskcolors) | luaC_white(g)))
 
@@ -92,6 +91,7 @@
 #define markobjectN(g,t)        { if (t) markobject(g,t); }
 
 static void reallymarkobject (global_State *g, GCObject *o);
+static l_mem atomic (lua_State *L);
 
 
 /*
@@ -155,8 +155,11 @@ static int iscleared (global_State *g, const TValue *o) {
 void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
   global_State *g = G(L);
   lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
-  if (keepinvariant(g))  /* must keep invariant? */
+  if (keepinvariant(g)) {  /* must keep invariant? */
     reallymarkobject(g, v);  /* restore invariant */
+    if (isold(o))
+      l_setbit((v)->marked, OLDBIT);
+  }
   else {  /* sweep phase */
     lua_assert(issweepphase(g));
     makewhite(g, o);  /* mark main obj. as white to avoid other barriers */
@@ -186,8 +189,10 @@ void luaC_upvalbarrier_ (lua_State *L, UpVal *uv) {
   global_State *g = G(L);
   GCObject *o = gcvalue(uv->v);
   lua_assert(!upisopen(uv));  /* ensured by macro luaC_upvalbarrier */
-  if (keepinvariant(g))
+  if (keepinvariant(g)) {
     markobject(g, o);
+    l_setbit((o)->marked, OLDBIT);
+  }
 }
 
 
@@ -922,6 +927,121 @@ void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
 /* }====================================================== */
 
 
+/*
+** {======================================================
+** Generational Collector
+** =======================================================
+*/
+
+
+#if 0
+static int count (GCObject *p, GCObject *limit) {
+  int res = 0;
+  for (; p != NULL && p != limit; p = p->next)
+    res++;
+  return res;
+}
+#endif
+
+
+static GCObject **sweepgen (lua_State *L, GCObject **p, GCObject *limit,
+                            int zeromask, int onemask) {
+  global_State *g = G(L);
+  int ow = otherwhite(g);
+  GCObject *curr;
+  while ((curr = *p) != limit) {
+    int marked = curr->marked;
+    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
+      lua_assert(!isold(curr));
+      *p = curr->next;  /* remove 'curr' from list */
+      freeobj(L, curr);  /* erase 'curr' */
+    }
+    else {  /* correct mark */
+      if (!isold(curr))  /* don't change old objects */
+        curr->marked = cast_byte((marked & zeromask) | onemask);
+      p = &curr->next;  /* go to next element */
+    }
+  }
+  return p;
+}
+
+
+static void startgencycle (lua_State *L, global_State *g) {
+  propagateall(g);
+  atomic(L);
+}
+
+
+static void finishgencycle (lua_State *L, global_State *g, int mask) {
+  sweepgen(L, &g->finobj, NULL, ~0, mask);
+  sweepgen(L, &g->tobefnz, NULL, ~0, mask);
+  checkSizes(L, g);
+  g->gcstate = GCSpropagate;  /* skip restart */
+  callallpendingfinalizers(L);
+}
+
+
+static void youngcollection (lua_State *L, global_State *g) {
+  GCObject **psurvival;
+  lua_assert(g->gcstate == GCSpropagate);
+  startgencycle(L, g);
+  /* sweep nursery */
+  psurvival = sweepgen(L, &g->allgc, g->survival, maskcolors, luaC_white(g));
+  lua_assert(*psurvival == g->survival);
+  /* sweep 'survival' list, making elements old */
+  sweepgen(L, psurvival, g->old, ~0, bitmask(OLDBIT));
+  /* incorporate 'survival' list into old list */
+  g->old = *psurvival;
+  /* surviving young objects go to 'survival' list */
+  g->survival = g->allgc;
+  finishgencycle(L, g, 0);
+lua_checkmemory(L);
+}
+
+
+static void entergen (lua_State *L, global_State *g) {
+lua_checkmemory(L);
+  lua_assert(g->old == NULL && g->survival == NULL);
+  luaC_runtilstate(L, bitmask(GCSpause));  /* prepare to start a new cycle */
+  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
+  startgencycle(L, g);
+  /* sweep all ellements making them old */
+  sweepgen(L, &g->allgc, g->survival, ~0, bitmask(OLDBIT));
+  /* everything alive now is old; 'survival' is empty */
+  g->old = g->survival = g->allgc;
+  finishgencycle(L, g, bitmask(OLDBIT));
+lua_checkmemory(L);
+}
+
+
+void luaC_changemode (lua_State *L, int newmode) {
+  global_State *g = G(L);
+  if (newmode != g->gckind) {  /* otherwise, nothing to be done */
+    if (newmode == KGC_GEN)  /* entering generational mode? */
+      entergen(L, g);
+    else {  /* entering incremental mode */
+lua_checkmemory(L);
+      youngcollection(L, g);
+      g->old = g->survival = NULL;
+lua_checkmemory(L);
+    }
+    g->gckind = newmode;
+  }
+}
+
+
+static void genstep (lua_State *L, global_State *g) {
+  lu_mem mem;
+  youngcollection(L, g);
+  mem = gettotalbytes(g);
+  luaE_setdebt(g, -((mem / 100) * 20));
+}
+
+
+
+
+/* }====================================================== */
+
 
 /*
 ** {======================================================
@@ -963,17 +1083,24 @@ static void entersweep (lua_State *L) {
 }
 
 
+static void deletealllist (lua_State *L, GCObject *p) {
+  while (p) {
+    GCObject *next = p->next;
+    freeobj(L, p);
+    p = next;
+  }
+}
+
+
 void luaC_freeallobjects (lua_State *L) {
   global_State *g = G(L);
   separatetobefnz(g, 1);  /* separate all objects with finalizers */
   lua_assert(g->finobj == NULL);
   callallpendingfinalizers(L);
   lua_assert(g->tobefnz == NULL);
-  g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */
-  g->gckind = KGC_NORMAL;
-  sweepwholelist(L, &g->finobj);
-  sweepwholelist(L, &g->allgc);
-  sweepwholelist(L, &g->fixedgc);  /* collect fixed objects */
+  deletealllist(L, g->finobj);
+  deletealllist(L, g->allgc);
+  deletealllist(L, g->fixedgc);  /* collect fixed objects */
   lua_assert(g->strt.nuse == 0);
 }
 
@@ -996,6 +1123,7 @@ static l_mem atomic (lua_State *L) {
   propagateall(g);  /* propagate changes */
   work = g->GCmemtrav;  /* stop counting (do not recount 'grayagain') */
   g->gray = grayagain;
+  g->grayagain = NULL;
   propagateall(g);  /* traverse 'grayagain' list */
   g->GCmemtrav = 0;  /* restart counting */
   convergeephemerons(g);
@@ -1052,10 +1180,10 @@ static lu_mem singlestep (lua_State *L) {
     }
     case GCSpropagate: {
       g->GCmemtrav = 0;
-      lua_assert(g->gray);
-      propagatemark(g);
-       if (g->gray == NULL)  /* no more gray objects? */
+      if (g->gray == NULL)  /* no more gray objects? */
         g->gcstate = GCSatomic;  /* finish propagate phase */
+      else
+        propagatemark(g);  /* traverse one gray object */
       return g->GCmemtrav;  /* memory traversed in this step */
     }
     case GCSatomic: {
@@ -1123,15 +1251,10 @@ static l_mem getdebt (global_State *g) {
 }
 
 /*
-** performs a basic GC step when collector is running
+** performs a basic incremental step
 */
-void luaC_step (lua_State *L) {
-  global_State *g = G(L);
-  l_mem debt = getdebt(g);  /* GC deficit (be paid now) */
-  if (!g->gcrunning) {  /* not running? */
-    luaE_setdebt(g, -GCSTEPSIZE * 10);  /* avoid being called too often */
-    return;
-  }
+static void incstep (lua_State *L, global_State *g) {
+  l_mem debt = getdebt(g);  /* GC deficit (to be paid now) */
   do {  /* repeat until pause or enough "credit" (negative debt) */
     lu_mem work = singlestep(L);  /* perform one single step */
     debt -= work;
@@ -1145,6 +1268,19 @@ void luaC_step (lua_State *L) {
   }
 }
 
+/*
+** performs a basic GC step when collector is running
+*/
+void luaC_step (lua_State *L) {
+  global_State *g = G(L);
+  if (!g->gcrunning)  /* not running? */
+    luaE_setdebt(g, -GCSTEPSIZE * 10);  /* avoid being called too often */
+  else if (g->gckind == KGC_NORMAL)
+    incstep(L, g);
+  else
+    genstep(L, g);
+}
+
 
 /*
 ** Performs a full GC cycle; if 'isemergency', set a flag to avoid
@@ -1164,7 +1300,6 @@ void luaC_fullgc (lua_State *L, int isemergency) {
   }
   /* finish any pending sweep phase to start a new cycle */
   luaC_runtilstate(L, bitmask(GCSpause));
-  luaC_runtilstate(L, ~bitmask(GCSpause));  /* start new collection */
   luaC_runtilstate(L, bitmask(GCScallfin));  /* run up to finalizers */
   /* estimate must be correct after a full GC cycle */
   lua_assert(g->GCestimate == gettotalbytes(g));
diff --git a/lgc.h b/lgc.h
index 75f24bc0..e75ff85c 100644
--- a/lgc.h
+++ b/lgc.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.h,v 2.90 2015/10/21 18:15:15 roberto Exp roberto $
+** $Id: lgc.h,v 2.91 2015/12/21 13:02:14 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -79,7 +79,8 @@
 #define WHITE1BIT       1  /* object is white (type 1) */
 #define BLACKBIT        2  /* object is black */
 #define FINALIZEDBIT    3  /* object has been marked for finalization */
-/* bit 7 is currently used by tests (luaL_checkmemory) */
+#define OLDBIT          4  /* object is old (gen. mode) */
+#define TESTGRAYBIT     7  /* used by tests (luaL_checkmemory) */
 
 #define WHITEBITS       bit2mask(WHITE0BIT, WHITE1BIT)
 
@@ -88,11 +89,12 @@
 #define isblack(x)      testbit((x)->marked, BLACKBIT)
 #define isgray(x)  /* neither white nor black */  \
         (!testbits((x)->marked, WHITEBITS | bitmask(BLACKBIT)))
+#define isold(x)        testbit((x)->marked, OLDBIT)
 
 #define tofinalize(x)   testbit((x)->marked, FINALIZEDBIT)
 
 #define otherwhite(g)   ((g)->currentwhite ^ WHITEBITS)
-#define isdeadm(ow,m)   (!(((m) ^ WHITEBITS) & (ow)))
+#define isdeadm(ow,m)   ((m) & (ow))
 #define isdead(g,v)     isdeadm(otherwhite(g), (v)->marked)
 
 #define changewhite(x)  ((x)->marked ^= WHITEBITS)
@@ -142,6 +144,7 @@ LUAI_FUNC void luaC_barrierback_ (lua_State *L, Table *o);
 LUAI_FUNC void luaC_upvalbarrier_ (lua_State *L, UpVal *uv);
 LUAI_FUNC void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt);
 LUAI_FUNC void luaC_upvdeccount (lua_State *L, UpVal *uv);
+LUAI_FUNC void luaC_changemode (lua_State *L, int newmode);
 
 
 #endif
diff --git a/lstate.c b/lstate.c
index 11299d37..4900d724 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.c,v 2.132 2015/11/02 16:01:41 roberto Exp roberto $
+** $Id: lstate.c,v 2.133 2015/11/13 12:16:51 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -319,6 +319,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
   g->gcstate = GCSpause;
   g->gckind = KGC_NORMAL;
   g->allgc = g->finobj = g->tobefnz = g->fixedgc = NULL;
+  g->survival = g->old = NULL;
   g->sweepgc = NULL;
   g->gray = g->grayagain = NULL;
   g->weak = g->ephemeron = g->allweak = NULL;
diff --git a/lstate.h b/lstate.h
index 67efa7f2..51128db1 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.133 2016/12/22 13:08:50 roberto Exp roberto $
+** $Id: lstate.h,v 2.134 2017/02/15 18:52:13 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -70,7 +70,8 @@ struct lua_longjmp;  /* defined in ldo.c */
 
 /* kinds of Garbage Collection */
 #define KGC_NORMAL      0
-#define KGC_EMERGENCY   1       /* gc was forced by an allocation failure */
+#define KGC_GEN         1       /* generational gc */
+#define KGC_EMERGENCY   2       /* gc was forced by an allocation failure */
 
 
 typedef struct stringtable {
@@ -158,6 +159,9 @@ typedef struct global_State {
   GCObject *allweak;  /* list of all-weak tables */
   GCObject *tobefnz;  /* list of userdata to be GC */
   GCObject *fixedgc;  /* list of objects not to be collected */
+  /* fields for generational collector */
+  GCObject *old;  /* start of old objects */
+  GCObject *survival;  /* start of objects that survived one GC cycle */
   struct lua_State *twups;  /* list of threads with open upvalues */
   unsigned int gcfinnum;  /* number of finalizers to call in each GC step */
   int gcpause;  /* size of pause between successive GCs */
diff --git a/ltests.c b/ltests.c
index 6dba514a..ac177de8 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.210 2016/11/07 12:38:35 roberto Exp roberto $
+** $Id: ltests.c,v 2.211 2016/12/04 20:17:24 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -195,9 +195,13 @@ static int testobjref1 (global_State *g, GCObject *f, GCObject *t) {
 
 
 static void printobj (global_State *g, GCObject *o) {
-  printf("||%s(%p)-%c(%02X)||",
+  printf("||%s(%p)-%c%c(%02X)||",
            ttypename(novariant(o->tt)), (void *)o,
-           isdead(g,o)?'d':isblack(o)?'b':iswhite(o)?'w':'g', o->marked);
+           isdead(g,o) ? 'd' : isblack(o) ? 'b' : iswhite(o) ? 'w' : 'g',
+           testbit(o->marked, OLDBIT) ? 'o' : 'n',
+           o->marked);
+  if (o->tt == LUA_TSHRSTR || o->tt == LUA_TLNGSTR)
+    printf(" '%s'", getstr(gco2ts(o)));
 }
 
 
@@ -364,8 +368,6 @@ static void checkobject (global_State *g, GCObject *o, int maybedead) {
 }
 
 
-#define TESTGRAYBIT             7
-
 static void checkgraylist (global_State *g, GCObject *o) {
   ((void)g);  /* better to keep it available if we need to print an object */
   while (o) {
diff --git a/lua.h b/lua.h
index fc4e2388..d9962cec 100644
--- a/lua.h
+++ b/lua.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lua.h,v 1.331 2016/05/30 15:53:28 roberto Exp roberto $
+** $Id: lua.h,v 1.332 2016/12/22 15:51:20 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
@@ -308,6 +308,8 @@ LUA_API int (lua_isyieldable) (lua_State *L);
 #define LUA_GCSETPAUSE          6
 #define LUA_GCSETSTEPMUL        7
 #define LUA_GCISRUNNING         9
+#define LUA_GCGEN               10
+#define LUA_GCINC               11
 
 LUA_API int (lua_gc) (lua_State *L, int what, int data);