Comments detailing the ages for generational GC

Plus other comments and small details.

5 files changed, 59 insertions, 16 deletions

diff --git a/lauxlib.c b/lauxlib.c
index 927e36f0..ab3c7c93 100644
--- a/lauxlib.c
+++ b/lauxlib.c
@@ -1139,12 +1139,11 @@ static unsigned int luai_makeseed (void) {
   unsigned int res;
   unsigned int i;
   time_t t = time(NULL);
-  void *h = buff;
   char *b = (char*)buff;
-  addbuff(b, h);  /* local variable's address */
+  addbuff(b, b);  /* local variable's address */
   addbuff(b, t);  /* time */
   /* fill (rare but possible) remain of the buffer with zeros */
-  memset(b, 0, BUFSEED * sizeof(int) - BUFSEEDB);
+  memset(b, 0, sizeof(buff) - BUFSEEDB);
   res = buff[0];
   for (i = 0; i < BUFSEED; i++)
     res ^= (res >> 3) + (res << 7) + buff[i];
diff --git a/lgc.c b/lgc.c
index 3884aad0..daee5707 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1121,6 +1121,7 @@ static GCObject **sweepgen (lua_State *L, global_State *g, GCObject **p,
         curr->marked = cast_byte(marked | G_SURVIVAL | white);
       }
       else {  /* all other objects will be old, and so keep their color */
+        lua_assert(getage(curr) != G_OLD1);  /* advanced in 'markold' */
         setage(curr, nextage[getage(curr)]);
         if (getage(curr) == G_OLD1 && *pfirstold1 == NULL)
           *pfirstold1 = curr;  /* first OLD1 object in the list */
@@ -1145,13 +1146,15 @@ static void whitelist (global_State *g, GCObject *p) {
 
 
 /*
-** Correct a list of gray objects. Return pointer to where rest of the
-** list should be linked.
+** Correct a list of gray objects. Return a pointer to the last element
+** left on the list, so that we can link another list to the end of
+** this one.
 ** Because this correction is done after sweeping, young objects might
 ** be turned white and still be in the list. They are only removed.
 ** 'TOUCHED1' objects are advanced to 'TOUCHED2' and remain on the list;
-** Non-white threads also remain on the list; 'TOUCHED2' objects become
-** regular old; they and anything else are removed from the list.
+** Non-white threads also remain on the list. 'TOUCHED2' objects and
+** anything else become regular old, are marked black, and are removed
+** from the list.
 */
 static GCObject **correctgraylist (GCObject **p) {
   GCObject *curr;
diff --git a/lgc.h b/lgc.h
index 959465ec..f06427c2 100644
--- a/lgc.h
+++ b/lgc.h
@@ -123,6 +123,43 @@
 #define changeage(o,f,t)  \
         check_exp(getage(o) == (f), (o)->marked ^= ((f)^(t)))
 
+/*
+** In generational mode, objects are created 'new'. After surviving one
+** cycle, they become 'survival'. Both 'new' and 'survival' can point
+** to any other object, as they are traversed at the end of the cycle.
+** We call them both 'young' objects.
+** If a survival object survives another cycle, it becomes 'old1'.
+** 'old1' objects can still point to survival objects (but not to
+** new objects), so they still must be traversed. After another cycle
+** (that, being old, 'old1' objects will "survive" no matter what)
+** finally the 'old1' object becomes really 'old', and then they
+** are no more traversed.
+**
+** To keep its invariants, the generational mode uses the same barriers
+** also used by the incremental mode. If a young object is caught in a
+** foward barrier, it cannot become old immediately, because it can
+** still point to other young objects. Instead, it becomes 'old0',
+** which in the next cycle becomes 'old1'. So, 'old0' objects is
+** old but can point to new and survival objects; 'old1' is old
+** but cannot point to new objects; and 'old' cannot point to any
+** young object.
+**
+** If any old object ('old0', 'old1', 'old') is caught in a back
+** barrier, it becomes 'touched1' and goes into a gray list, to be
+** visited at the end of the cycle.  There it evolves to 'touched2',
+** which can point to survivals but not to new objects. In yet another
+** cycle then it becomes 'old' again.
+**
+** The generational mode must also control the colors of objects,
+** because of the barriers.  While the mutator is running, young objects
+** are kept white. 'old', 'old1', and 'touched2' objects are kept black,
+** as they cannot point to new objects; exceptions are threads and open
+** upvalues, which age to 'old1' and 'old' but are kept gray. 'old0'
+** objects may be gray or black, as in the incremental mode. 'touched1'
+** objects are kept gray, as they must be visited again at the end of
+** the cycle.
+*/
+
 
 /* Default Values for GC parameters */
 
@@ -161,9 +198,10 @@
 ** (value * original parameter / 100).
 **
 ** For most parameters, which are typically larger than 100%, 2^n is
-** 16 (2^4), allowing maximum values up to 1599.  For the minor
-** multiplier, which is typically smaller, 2^n is 64 (2^6) to allow more
-** precision.
+** 16 (2^4), allowing maximum values up to ~1500%, with a granularity
+** of ~6%.  For the minor multiplier, which is typically smaller,
+** 2^n is 64 (2^6) to allow more precision. In that case, the maximum
+** value is ~400%, with a granularity of ~1.5%.
 */
 #define gcparamshift(p)  \
   (offsetof(global_State, p) == offsetof(global_State, genminormul) ? 6 : 4)
diff --git a/lstate.c b/lstate.c
index c01e53ed..1216db35 100644
--- a/lstate.c
+++ b/lstate.c
@@ -52,8 +52,9 @@ typedef struct LG {
 
 
 /*
-** set GCdebt to a new value keeping the value (totalobjs + GCdebt)
-** invariant (and avoiding underflows in 'totalobjs')
+** set GCdebt to a new value keeping the real number of allocated
+** objects (totalobjs - GCdebt) invariant and avoiding overflows in
+** 'totalobjs'.
 */
 void luaE_setdebt (global_State *g, l_obj debt) {
   l_obj tb = gettotalobjs(g);
diff --git a/ltests.c b/ltests.c
index bd4147f2..09c2e030 100644
--- a/ltests.c
+++ b/ltests.c
@@ -302,8 +302,8 @@ static int testobjref1 (global_State *g, GCObject *f, GCObject *t) {
   else {  /* generational mode */
     if ((getage(f) == G_OLD && isblack(f)) && !isold(t))
       return 0;
-    if (((getage(f) == G_OLD1 || getage(f) == G_TOUCHED2) && isblack(f)) &&
-          getage(t) == G_NEW)
+    if ((getage(f) == G_OLD1 || getage(f) == G_TOUCHED2) &&
+         getage(t) == G_NEW)
       return 0;
     return 1;
   }
@@ -510,7 +510,8 @@ static void checkrefs (global_State *g, GCObject *o) {
 **   * objects must be old enough for their lists ('listage').
 **   * old objects cannot be white.
 **   * old objects must be black, except for 'touched1', 'old0',
-** threads, and open upvalues.
+**     threads, and open upvalues.
+**   * 'touched1' objects must be gray.
 */
 static void checkobject (global_State *g, GCObject *o, int maybedead,
                          int listage) {
@@ -520,14 +521,15 @@ static void checkobject (global_State *g, GCObject *o, int maybedead,
     assert(g->gcstate != GCSpause || iswhite(o));
     if (g->gckind == KGC_GEN) {  /* generational mode? */
       assert(getage(o) >= listage);
-      assert(!iswhite(o) || !isold(o));
       if (isold(o)) {
+        assert(!iswhite(o));
         assert(isblack(o) ||
         getage(o) == G_TOUCHED1 ||
         getage(o) == G_OLD0 ||
         o->tt == LUA_VTHREAD ||
         (o->tt == LUA_VUPVAL && upisopen(gco2upv(o))));
       }
+      assert(getage(o) != G_TOUCHED1 || isgray(o));
     }
     checkrefs(g, o);
   }