From 63d68bd657b7386c9c58b4439a100ea0ccbd633e Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 29 Nov 2023 16:22:09 -0300 Subject: Comments detailing the ages for generational GC Plus other comments and small details. --- lauxlib.c | 5 ++--- lgc.c | 11 +++++++---- lgc.h | 44 +++++++++++++++++++++++++++++++++++++++++--- lstate.c | 5 +++-- ltests.c | 10 ++++++---- 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); } -- cgit v1.2.3-55-g6feb