Clearer handling of gray lists when entering generational mode

When entering generational mode, all objects are old. So, the only
objects that need to be in a gray list are threads, which can be
assigned without barriers. Changes in anything else (e.g., weak
tables) will trigger barriers that, if needed, will add the object
to a gray list.

3 files changed, 79 insertions, 18 deletions

diff --git a/lgc.c b/lgc.c
index 9973c9db..5e8c02d3 100644
--- a/lgc.c
+++ b/lgc.c
@@ -368,12 +368,17 @@ static int remarkupvals (global_State *g) {
 }
 
 
+static void cleargraylists (global_State *g) {
+  g->gray = g->grayagain = NULL;
+  g->weak = g->allweak = g->ephemeron = NULL;
+}
+
+
 /*
 ** mark root set and reset all gray lists, to start a new collection
 */
 static void restartcollection (global_State *g) {
-  g->gray = g->grayagain = NULL;
-  g->weak = g->allweak = g->ephemeron = NULL;
+  cleargraylists(g);
   markobject(g, g->mainthread);
   markvalue(g, &g->l_registry);
   markmt(g);
@@ -1019,19 +1024,30 @@ static void setpause (global_State *g);
 
 
 /*
-** Sweep a list of objects, deleting dead ones and turning
-** the non dead to old (without changing their colors).
+** Sweep a list of objects to enter generational mode.  Deletes dead
+** objects and turns the non dead to old. All non-dead threads---which
+** are now old---must be in a gray list.  Everything else is not in a
+** gray list.
+**
 */
 static void sweep2old (lua_State *L, GCObject **p) {
   GCObject *curr;
+  global_State *g = G(L);
   while ((curr = *p) != NULL) {
     if (iswhite(curr)) {  /* is 'curr' dead? */
-      lua_assert(isdead(G(L), curr));
+      lua_assert(isdead(g, curr));
       *p = curr->next;  /* remove 'curr' from list */
       freeobj(L, curr);  /* erase 'curr' */
     }
     else {  /* all surviving objects become old */
       setage(curr, G_OLD);
+      if (curr->tt == LUA_VTHREAD) {  /* threads must be watched */
+        lua_State *th = gco2th(curr);
+        linkgclist(th, g->grayagain);  /* insert into 'grayagain' list */
+        black2gray(th);  /* OK if already gray */
+      }
+      else  /* everything else is black */
+        gray2black(curr);  /* OK if already black */
       p = &curr->next;  /* go to next element */
     }
   }
@@ -1221,7 +1237,14 @@ static void youngcollection (lua_State *L, global_State *g) {
 }
 
 
+/*
+** Clears all gray lists, sweeps objects, and prepare sublists to enter
+** generational mode. The sweeps remove dead objects and turn all
+** surviving objects to old. Threads go back to 'grayagain'; everything
+** else is turned black (not in any gray list).
+*/
 static void atomic2gen (lua_State *L, global_State *g) {
+  cleargraylists(g);
   /* sweep all elements making them old */
   g->gcstate = GCSswpallgc;
   sweep2old(L, &g->allgc);
@@ -1244,7 +1267,8 @@ static void atomic2gen (lua_State *L, global_State *g) {
 
 /*
 ** Enter generational mode. Must go until the end of an atomic cycle
-** to ensure that all threads and weak tables are in the gray lists.
+** to ensure that all objects are correctly marked and weak tables
+** are cleared.
 ** Then, turn all objects into old and finishes the collection.
 */
 static lu_mem entergen (lua_State *L, global_State *g) {
diff --git a/ltests.c b/ltests.c
index a13714d6..c0421781 100644
--- a/ltests.c
+++ b/ltests.c
@@ -186,7 +186,8 @@ typedef union Header {
 
 
 Memcontrol l_memcontrol =
-  {0UL, 0UL, 0UL, 0UL, (~0UL), {0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL}};
+  {0, 0UL, 0UL, 0UL, 0UL, (~0UL),
+   {0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL, 0UL}};
 
 
 static void freeblock (Memcontrol *mc, Header *block) {
@@ -225,6 +226,10 @@ void *debug_realloc (void *ud, void *b, size_t oldsize, size_t size) {
     freeblock(mc, block);
     return NULL;
   }
+  if (mc->failnext) {
+    mc->failnext = 0;
+    return NULL;  /* fake a single memory allocation error */
+  }
   if (mc->countlimit != ~0UL && size != oldsize) {  /* count limit in use? */
     if (mc->countlimit == 0)
       return NULL;  /* fake a memory allocation error */
@@ -513,10 +518,12 @@ static void checkobject (global_State *g, GCObject *o, int maybedead,
 }
 
 
-static void checkgraylist (global_State *g, GCObject *o) {
+static lu_mem checkgraylist (global_State *g, GCObject *o) {
+  int total = 0;  /* count number of elements in the list */
   ((void)g);  /* better to keep it available if we need to print an object */
   while (o) {
     lua_assert(isgray(o) || getage(o) == G_TOUCHED2);
+    total++;
     switch (o->tt) {
       case LUA_VTABLE: o = gco2t(o)->gclist; break;
       case LUA_VLCL: o = gco2lcl(o)->gclist; break;
@@ -530,40 +537,54 @@ static void checkgraylist (global_State *g, GCObject *o) {
       default: lua_assert(0);  /* other objects cannot be in a gray list */
     }
   }
+  return total;
 }
 
 
 /*
 ** Check objects in gray lists.
 */
-static void checkgrays (global_State *g) {
-  if (!keepinvariant(g)) return;
-  checkgraylist(g, g->gray);
-  checkgraylist(g, g->grayagain);
-  checkgraylist(g, g->weak);
-  checkgraylist(g, g->ephemeron);
+static lu_mem checkgrays (global_State *g) {
+  int total = 0;  /* count number of elements in all lists */
+  if (!keepinvariant(g)) return total;
+  total += checkgraylist(g, g->gray);
+  total += checkgraylist(g, g->grayagain);
+  total += checkgraylist(g, g->weak);
+  total += checkgraylist(g, g->allweak);
+  total += checkgraylist(g, g->ephemeron);
+  return total;
 }
 
 
-static void checklist (global_State *g, int maybedead, int tof,
+/* Increment 't' if 'o' should be in a gray list */
+#define incifingray(o,t)  \
+  if (isgray(o) || getage(o) == G_TOUCHED2) (t)++
+
+static lu_mem checklist (global_State *g, int maybedead, int tof,
   GCObject *newl, GCObject *survival, GCObject *old, GCObject *reallyold) {
   GCObject *o;
+  lu_mem total = 0;  /* number of object that should be in  gray lists */
   for (o = newl; o != survival; o = o->next) {
     checkobject(g, o, maybedead, G_NEW);
+    incifingray(o, total);
     lua_assert(!tof == !tofinalize(o));
   }
   for (o = survival; o != old; o = o->next) {
     checkobject(g, o, 0, G_SURVIVAL);
+    incifingray(o, total);
     lua_assert(!tof == !tofinalize(o));
   }
   for (o = old; o != reallyold; o = o->next) {
     checkobject(g, o, 0, G_OLD1);
+    incifingray(o, total);
     lua_assert(!tof == !tofinalize(o));
   }
   for (o = reallyold; o != NULL; o = o->next) {
     checkobject(g, o, 0, G_OLD);
+    incifingray(o, total);
     lua_assert(!tof == !tofinalize(o));
   }
+  return total;
 }
 
 
@@ -571,13 +592,15 @@ int lua_checkmemory (lua_State *L) {
   global_State *g = G(L);
   GCObject *o;
   int maybedead;
+  lu_mem totalin;  /* total of objects that are in gray lists */
+  lu_mem totalshould;  /* total of objects that should be in gray lists */
   if (keepinvariant(g)) {
     lua_assert(!iswhite(g->mainthread));
     lua_assert(!iswhite(gcvalue(&g->l_registry)));
   }
   lua_assert(!isdead(g, gcvalue(&g->l_registry)));
   lua_assert(g->sweepgc == NULL || issweepphase(g));
-  checkgrays(g);
+  totalin = checkgrays(g);
 
   /* check 'fixedgc' list */
   for (o = g->fixedgc; o != NULL; o = o->next) {
@@ -586,17 +609,22 @@ int lua_checkmemory (lua_State *L) {
 
   /* check 'allgc' list */
   maybedead = (GCSatomic < g->gcstate && g->gcstate <= GCSswpallgc);
-  checklist(g, maybedead, 0, g->allgc, g->survival, g->old1, g->reallyold);
+  totalshould = checklist(g, maybedead, 0, g->allgc,
+                             g->survival, g->old1, g->reallyold);
 
   /* check 'finobj' list */
-  checklist(g, 0, 1, g->finobj, g->finobjsur, g->finobjold1, g->finobjrold);
+  totalshould += checklist(g, 0, 1, g->finobj,
+                              g->finobjsur, g->finobjold1, g->finobjrold);
 
   /* check 'tobefnz' list */
   for (o = g->tobefnz; o != NULL; o = o->next) {
     checkobject(g, o, 0, G_NEW);
+    incifingray(o, totalshould);
     lua_assert(tofinalize(o));
     lua_assert(o->tt == LUA_VUSERDATA || o->tt == LUA_VTABLE);
   }
+  if (keepinvariant(g))
+    lua_assert(totalin == totalshould);
   return 0;
 }
 
@@ -807,6 +835,13 @@ static int alloc_count (lua_State *L) {
     l_memcontrol.countlimit = luaL_checkinteger(L, 1);
   return 0;
 }
+
+
+static int alloc_failnext (lua_State *L) {
+  UNUSED(L);
+  l_memcontrol.failnext = 1;
+  return 0;
+}
   
 
 static int settrick (lua_State *L) {
@@ -1864,6 +1899,7 @@ static const struct luaL_Reg tests_funcs[] = {
   {"makeCfunc", makeCfunc},
   {"totalmem", mem_query},
   {"alloccount", alloc_count},
+  {"allocfailnext", alloc_failnext},
   {"trick", settrick},
   {"udataval", udataval},
   {"unref", unref},
diff --git a/ltests.h b/ltests.h
index 1a2d8d28..e9219e29 100644
--- a/ltests.h
+++ b/ltests.h
@@ -51,6 +51,7 @@
 
 /* memory-allocator control variables */
 typedef struct Memcontrol {
+  int failnext;
   unsigned long numblocks;
   unsigned long total;
   unsigned long maxmem;