57 #define makewhite(g,x)	\  argument
58  (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g)))
73 #define markvalue(g,o) { checkconsistency(o); \  argument
74   if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
76 #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \  argument
77 		reallymarkobject(g, obj2gco(t)); }
79 static void reallymarkobject (global_State *g, GCObject *o);
119 static int iscleared (global_State *g, const TValue *o) {  in iscleared()  argument
122     markobject(g, rawtsvalue(o));  /* strings are `values', so are never weak */  in iscleared()
134   global_State *g = G(L);  in luaC_barrier_()  local
135   lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));  in luaC_barrier_()
136   lua_assert(g->gcstate != GCSpause);  in luaC_barrier_()
138   if (keepinvariantout(g))  /* must keep invariant? */  in luaC_barrier_()
139     reallymarkobject(g, v);  /* restore invariant */  in luaC_barrier_()
141     lua_assert(issweepphase(g));  in luaC_barrier_()
142     makewhite(g, o);  /* mark main obj. as white to avoid other barriers */  in luaC_barrier_()
154   global_State *g = G(L);  in luaC_barrierback_()  local
155   lua_assert(isblack(o) && !isdead(g, o) && gch(o)->tt == LUA_TTABLE);  in luaC_barrierback_()
157   gco2t(o)->gclist = g->grayagain;  in luaC_barrierback_()
158   g->grayagain = o;  in luaC_barrierback_()
171   global_State *g = G(L);  in luaC_barrierproto_()  local
178     p->gclist = g->grayagain;  in luaC_barrierproto_()
179     g->grayagain = obj2gco(p);  in luaC_barrierproto_()
188 void luaC_checkupvalcolor (global_State *g, UpVal *uv) {  in luaC_checkupvalcolor()  argument
192     if (keepinvariant(g)) {  in luaC_checkupvalcolor()
195       markvalue(g, uv->v);  in luaC_checkupvalcolor()
198       lua_assert(issweepphase(g));  in luaC_checkupvalcolor()
199       makewhite(g, o);  in luaC_checkupvalcolor()
212   global_State *g = G(L);  in luaC_newobj()  local
216     list = &g->allgc;  /* standard list for collectable objects */  in luaC_newobj()
217   gch(o)->marked = luaC_white(g);  in luaC_newobj()
241 static void reallymarkobject (global_State *g, GCObject *o) {  in reallymarkobject()  argument
252       markobject(g, mt);  in reallymarkobject()
253       markobject(g, gco2u(o)->env);  in reallymarkobject()
259       markvalue(g, uv->v);  in reallymarkobject()
266       gco2lcl(o)->gclist = g->gray;  in reallymarkobject()
267       g->gray = o;  in reallymarkobject()
271       gco2ccl(o)->gclist = g->gray;  in reallymarkobject()
272       g->gray = o;  in reallymarkobject()
276       linktable(gco2t(o), &g->gray);  in reallymarkobject()
280       gco2th(o)->gclist = g->gray;  in reallymarkobject()
281       g->gray = o;  in reallymarkobject()
285       gco2p(o)->gclist = g->gray;  in reallymarkobject()
286       g->gray = o;  in reallymarkobject()
292   g->GCmemtrav += size;  in reallymarkobject()
299 static void markmt (global_State *g) {  in markmt()  argument
302     markobject(g, g->mt[i]);  in markmt()
309 static void markbeingfnz (global_State *g) {  in markbeingfnz()  argument
311   for (o = g->tobefnz; o != NULL; o = gch(o)->next) {  in markbeingfnz()
312     makewhite(g, o);  in markbeingfnz()
313     reallymarkobject(g, o);  in markbeingfnz()
322 static void remarkupvals (global_State *g) {  in remarkupvals()  argument
324   for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {  in remarkupvals()
326       markvalue(g, uv->v);  in remarkupvals()
335 static void restartcollection (global_State *g) {  in restartcollection()  argument
336   g->gray = g->grayagain = NULL;  in restartcollection()
337   g->weak = g->allweak = g->ephemeron = NULL;  in restartcollection()
338   markobject(g, g->mainthread);  in restartcollection()
339   markvalue(g, &g->l_registry);  in restartcollection()
340   markmt(g);  in restartcollection()
341   markbeingfnz(g);  /* mark any finalizing object left from previous cycle */  in restartcollection()
353 static void traverseweakvalue (global_State *g, Table *h) {  in traverseweakvalue()  argument
364       markvalue(g, gkey(n));  /* mark key */  in traverseweakvalue()
365       if (!hasclears && iscleared(g, gval(n)))  /* is there a white value? */  in traverseweakvalue()
370     linktable(h, &g->weak);  /* has to be cleared later */  in traverseweakvalue()
372     linktable(h, &g->grayagain);  /* no need to clean */  in traverseweakvalue()
376 static int traverseephemeron (global_State *g, Table *h) {  in traverseephemeron()  argument
386       reallymarkobject(g, gcvalue(&h->array[i]));  in traverseephemeron()
394     else if (iscleared(g, gkey(n))) {  /* key is not marked (yet)? */  in traverseephemeron()
401       reallymarkobject(g, gcvalue(gval(n)));  /* mark it now */  in traverseephemeron()
404   if (g->gcstate != GCSatomic || prop)  in traverseephemeron()
405     linktable(h, &g->ephemeron);  /* have to propagate again */  in traverseephemeron()
407     linktable(h, &g->allweak);  /* may have to clean white keys */  in traverseephemeron()
409     linktable(h, &g->grayagain);  /* no need to clean */  in traverseephemeron()
414 static void traversestrongtable (global_State *g, Table *h) {  in traversestrongtable()  argument
418     markvalue(g, &h->array[i]);  in traversestrongtable()
425       markvalue(g, gkey(n));  /* mark key */  in traversestrongtable()
426       markvalue(g, gval(n));  /* mark value */  in traversestrongtable()
432 static lu_mem traversetable (global_State *g, Table *h) {  in traversetable()  argument
434   const TValue *mode = gfasttm(g, h->metatable, TM_MODE);  in traversetable()
435   markobject(g, h->metatable);  in traversetable()
442       traverseweakvalue(g, h);  in traversetable()
444       traverseephemeron(g, h);  in traversetable()
446       linktable(h, &g->allweak);  /* nothing to traverse now */  in traversetable()
449     traversestrongtable(g, h);  in traversetable()
455 static int traverseproto (global_State *g, Proto *f) {  in traverseproto()  argument
459   markobject(g, f->source);  in traverseproto()
461     markvalue(g, &f->k[i]);  in traverseproto()
463     markobject(g, f->upvalues[i].name);  in traverseproto()
465     markobject(g, f->p[i]);  in traverseproto()
467     markobject(g, f->locvars[i].varname);  in traverseproto()
477 static lu_mem traverseCclosure (global_State *g, CClosure *cl) {  in traverseCclosure()  argument
480     markvalue(g, &cl->upvalue[i]);  in traverseCclosure()
484 static lu_mem traverseLclosure (global_State *g, LClosure *cl) {  in traverseLclosure()  argument
486   markobject(g, cl->p);  /* mark its prototype */  in traverseLclosure()
488     markobject(g, cl->upvals[i]);  in traverseLclosure()
493 static lu_mem traversestack (global_State *g, lua_State *th) {  in traversestack()  argument
499     markvalue(g, o);  in traversestack()
500   if (g->gcstate == GCSatomic) {  /* final traversal? */  in traversestack()
519 static void propagatemark (global_State *g) {  in propagatemark()  argument
521   GCObject *o = g->gray;  in propagatemark()
527       g->gray = h->gclist;  /* remove from 'gray' list */  in propagatemark()
528       size = traversetable(g, h);  in propagatemark()
533       g->gray = cl->gclist;  /* remove from 'gray' list */  in propagatemark()
534       size = traverseLclosure(g, cl);  in propagatemark()
539       g->gray = cl->gclist;  /* remove from 'gray' list */  in propagatemark()
540       size = traverseCclosure(g, cl);  in propagatemark()
545       g->gray = th->gclist;  /* remove from 'gray' list */  in propagatemark()
546       th->gclist = g->grayagain;  in propagatemark()
547       g->grayagain = o;  /* insert into 'grayagain' list */  in propagatemark()
549       size = traversestack(g, th);  in propagatemark()
554       g->gray = p->gclist;  /* remove from 'gray' list */  in propagatemark()
555       size = traverseproto(g, p);  in propagatemark()
560   g->GCmemtrav += size;  in propagatemark()
564 static void propagateall (global_State *g) {  in propagateall()  argument
565   while (g->gray) propagatemark(g);  in propagateall()
569 static void propagatelist (global_State *g, GCObject *l) {  in propagatelist()  argument
570   lua_assert(g->gray == NULL);  /* no grays left */  in propagatelist()
571   g->gray = l;  in propagatelist()
572   propagateall(g);  /* traverse all elements from 'l' */  in propagatelist()
580 static void retraversegrays (global_State *g) {  in retraversegrays()  argument
581   GCObject *weak = g->weak;  /* save original lists */  in retraversegrays()
582   GCObject *grayagain = g->grayagain;  in retraversegrays()
583   GCObject *ephemeron = g->ephemeron;  in retraversegrays()
584   g->weak = g->grayagain = g->ephemeron = NULL;  in retraversegrays()
585   propagateall(g);  /* traverse main gray list */  in retraversegrays()
586   propagatelist(g, grayagain);  in retraversegrays()
587   propagatelist(g, weak);  in retraversegrays()
588   propagatelist(g, ephemeron);  in retraversegrays()
592 static void convergeephemerons (global_State *g) {  in convergeephemerons()  argument
596     GCObject *next = g->ephemeron;  /* get ephemeron list */  in convergeephemerons()
597     g->ephemeron = NULL;  /* tables will return to this list when traversed */  in convergeephemerons()
601       if (traverseephemeron(g, gco2t(w))) {  /* traverse marked some value? */  in convergeephemerons()
602         propagateall(g);  /* propagate changes */  in convergeephemerons()
623 static void clearkeys (global_State *g, GCObject *l, GCObject *f) {  in clearkeys()  argument
628       if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) {  in clearkeys()
641 static void clearvalues (global_State *g, GCObject *l, GCObject *f) {  in clearvalues()  argument
648       if (iscleared(g, o))  /* value was collected? */  in clearvalues()
652       if (!ttisnil(gval(n)) && iscleared(g, gval(n))) {  in clearvalues()
718   global_State *g = G(L);  in sweeplist()  local
719   int ow = otherwhite(g);  in sweeplist()
722   if (isgenerational(g)) {  /* generational mode? */  in sweeplist()
729     toset = luaC_white(g);  /* make object white */  in sweeplist()
777   global_State *g = G(L);  in checkSizes()  local
778   if (g->gckind != KGC_EMERGENCY) {  /* do not change sizes in emergency */  in checkSizes()
779     int hs = g->strt.size / 2;  /* half the size of the string table */  in checkSizes()
780     if (g->strt.nuse < cast(lu_int32, hs))  /* using less than that half? */  in checkSizes()
782     luaZ_freebuffer(L, &g->buff);  /* free concatenation buffer */  in checkSizes()
787 static GCObject *udata2finalize (global_State *g) {  in udata2finalize()  argument
788   GCObject *o = g->tobefnz;  /* get first element */  in udata2finalize()
790   g->tobefnz = gch(o)->next;  /* remove it from 'tobefnz' list */  in udata2finalize()
791   gch(o)->next = g->allgc;  /* return it to 'allgc' list */  in udata2finalize()
792   g->allgc = o;  in udata2finalize()
795   if (!keepinvariantout(g))  /* not keeping invariant? */  in udata2finalize()
796     makewhite(g, o);  /* "sweep" object */  in udata2finalize()
808   global_State *g = G(L);  in GCTM()  local
811   setgcovalue(L, &v, udata2finalize(g));  in GCTM()
816     int running  = g->gcrunning;  in GCTM()
818     g->gcrunning = 0;  /* avoid GC steps */  in GCTM()
824     g->gcrunning = running;  /* restore state */  in GCTM()
844   global_State *g = G(L);  in separatetobefnz()  local
845   GCObject **p = &g->finobj;  in separatetobefnz()
847   GCObject **lastnext = &g->tobefnz;  in separatetobefnz()
872   global_State *g = G(L);  in luaC_checkfinalizer()  local
875       gfasttm(g, mt, TM_GC) == NULL)                /* or has no finalizer? */  in luaC_checkfinalizer()
880     if (g->sweepgc == &ho->next) {  /* avoid removing current sweep object */  in luaC_checkfinalizer()
881       lua_assert(issweepphase(g));  in luaC_checkfinalizer()
882       g->sweepgc = sweeptolive(L, g->sweepgc, NULL);  in luaC_checkfinalizer()
885     for (p = &g->allgc; *p != o; p = &gch(*p)->next) { /* empty */ }  in luaC_checkfinalizer()
887     ho->next = g->finobj;  /* link it in list 'finobj' */  in luaC_checkfinalizer()
888     g->finobj = o;  in luaC_checkfinalizer()
890     if (!keepinvariantout(g))  /* not keeping invariant? */  in luaC_checkfinalizer()
891       makewhite(g, o);  /* "sweep" object */  in luaC_checkfinalizer()
911 static void setpause (global_State *g, l_mem estimate) {  in setpause()  argument
914   threshold = (g->gcpause < MAX_LMEM / estimate)  /* overflow? */  in setpause()
915             ? estimate * g->gcpause  /* no overflow */  in setpause()
917   debt = -cast(l_mem, threshold - gettotalbytes(g));  in setpause()
918   luaE_setdebt(g, debt);  in setpause()
935   global_State *g = G(L);  in entersweep()  local
937   g->gcstate = GCSsweepstring;  in entersweep()
938   lua_assert(g->sweepgc == NULL && g->sweepfin == NULL);  in entersweep()
940   g->sweepstrgc = 0;  in entersweep()
941   g->sweepfin = sweeptolive(L, &g->finobj, &n);  in entersweep()
942   g->sweepgc = sweeptolive(L, &g->allgc, &n);  in entersweep()
951   global_State *g = G(L);  in luaC_changemode()  local
952   if (mode == g->gckind) return;  /* nothing to change */  in luaC_changemode()
956     g->GCestimate = gettotalbytes(g);  in luaC_changemode()
957     g->gckind = KGC_GEN;  in luaC_changemode()
962     g->gckind = KGC_NORMAL;  in luaC_changemode()
973   global_State *g = G(L);  in callallpendingfinalizers()  local
974   while (g->tobefnz) {  in callallpendingfinalizers()
975     resetoldbit(g->tobefnz);  in callallpendingfinalizers()
982   global_State *g = G(L);  in luaC_freeallobjects()  local
985   lua_assert(g->finobj == NULL);  in luaC_freeallobjects()
987   g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */  in luaC_freeallobjects()
988   g->gckind = KGC_NORMAL;  in luaC_freeallobjects()
989   sweepwholelist(L, &g->finobj);  /* finalizers can create objs. in 'finobj' */  in luaC_freeallobjects()
990   sweepwholelist(L, &g->allgc);  in luaC_freeallobjects()
991   for (i = 0; i < g->strt.size; i++)  /* free all string lists */  in luaC_freeallobjects()
992     sweepwholelist(L, &g->strt.hash[i]);  in luaC_freeallobjects()
993   lua_assert(g->strt.nuse == 0);  in luaC_freeallobjects()
998   global_State *g = G(L);  in atomic()  local
999   l_mem work = -cast(l_mem, g->GCmemtrav);  /* start counting work */  in atomic()
1001   lua_assert(!iswhite(obj2gco(g->mainthread)));  in atomic()
1002   markobject(g, L);  /* mark running thread */  in atomic()
1004   markvalue(g, &g->l_registry);  in atomic()
1005   markmt(g);  /* mark basic metatables */  in atomic()
1007   remarkupvals(g);  in atomic()
1008   propagateall(g);  /* propagate changes */  in atomic()
1009   work += g->GCmemtrav;  /* stop counting (do not (re)count grays) */  in atomic()
1011   retraversegrays(g);  in atomic()
1012   work -= g->GCmemtrav;  /* restart counting */  in atomic()
1013   convergeephemerons(g);  in atomic()
1016   clearvalues(g, g->weak, NULL);  in atomic()
1017   clearvalues(g, g->allweak, NULL);  in atomic()
1018   origweak = g->weak; origall = g->allweak;  in atomic()
1019   work += g->GCmemtrav;  /* stop counting (objects being finalized) */  in atomic()
1021   markbeingfnz(g);  /* mark objects that will be finalized */  in atomic()
1022   propagateall(g);  /* remark, to propagate `preserveness' */  in atomic()
1023   work -= g->GCmemtrav;  /* restart counting */  in atomic()
1024   convergeephemerons(g);  in atomic()
1027   clearkeys(g, g->ephemeron, NULL);  /* clear keys from all ephemeron tables */  in atomic()
1028   clearkeys(g, g->allweak, NULL);  /* clear keys from all allweak tables */  in atomic()
1030   clearvalues(g, g->weak, origweak);  in atomic()
1031   clearvalues(g, g->allweak, origall);  in atomic()
1032   g->currentwhite = cast_byte(otherwhite(g));  /* flip current white */  in atomic()
1033   work += g->GCmemtrav;  /* complete counting */  in atomic()
1039   global_State *g = G(L);  in singlestep()  local
1040   switch (g->gcstate) {  in singlestep()
1043       g->GCmemtrav = g->strt.size * sizeof(GCObject*);  in singlestep()
1044       lua_assert(!isgenerational(g));  in singlestep()
1045       restartcollection(g);  in singlestep()
1046       g->gcstate = GCSpropagate;  in singlestep()
1047       return g->GCmemtrav;  in singlestep()
1050       if (g->gray) {  in singlestep()
1051         lu_mem oldtrav = g->GCmemtrav;  in singlestep()
1052         propagatemark(g);  in singlestep()
1053         return g->GCmemtrav - oldtrav;  /* memory traversed in this step */  in singlestep()
1058         g->gcstate = GCSatomic;  /* finish mark phase */  in singlestep()
1059         g->GCestimate = g->GCmemtrav;  /* save what was counted */  in singlestep()
1061         g->GCestimate += work;  /* estimate of total memory traversed */  in singlestep()
1068       for (i = 0; i < GCSWEEPMAX && g->sweepstrgc + i < g->strt.size; i++)  in singlestep()
1069         sweepwholelist(L, &g->strt.hash[g->sweepstrgc + i]);  in singlestep()
1070       g->sweepstrgc += i;  in singlestep()
1071       if (g->sweepstrgc >= g->strt.size)  /* no more strings to sweep? */  in singlestep()
1072         g->gcstate = GCSsweepudata;  in singlestep()
1076       if (g->sweepfin) {  in singlestep()
1077         g->sweepfin = sweeplist(L, g->sweepfin, GCSWEEPMAX);  in singlestep()
1081         g->gcstate = GCSsweep;  in singlestep()
1086       if (g->sweepgc) {  in singlestep()
1087         g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);  in singlestep()
1092         GCObject *mt = obj2gco(g->mainthread);  in singlestep()
1095         g->gcstate = GCSpause;  /* finish collection */  in singlestep()
1109   global_State *g = G(L);  in luaC_runtilstate()  local
1110   while (!testbit(statesmask, g->gcstate))  in luaC_runtilstate()
1116   global_State *g = G(L);  in generationalcollection()  local
1117   lua_assert(g->gcstate == GCSpropagate);  in generationalcollection()
1118   if (g->GCestimate == 0) {  /* signal for another major collection? */  in generationalcollection()
1120     g->GCestimate = gettotalbytes(g);  /* update control */  in generationalcollection()
1123     lu_mem estimate = g->GCestimate;  in generationalcollection()
1125     g->gcstate = GCSpropagate;  /* skip restart */  in generationalcollection()
1126     if (gettotalbytes(g) > (estimate / 100) * g->gcmajorinc)  in generationalcollection()
1127       g->GCestimate = 0;  /* signal for a major collection */  in generationalcollection()
1129       g->GCestimate = estimate;  /* keep estimate from last major coll. */  in generationalcollection()
1132   setpause(g, gettotalbytes(g));  in generationalcollection()
1133   lua_assert(g->gcstate == GCSpropagate);  in generationalcollection()
1138   global_State *g = G(L);  in incstep()  local
1139   l_mem debt = g->GCdebt;  in incstep()
1140   int stepmul = g->gcstepmul;  in incstep()
1148   } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause);  in incstep()
1149   if (g->gcstate == GCSpause)  in incstep()
1150     setpause(g, g->GCestimate);  /* pause until next cycle */  in incstep()
1153     luaE_setdebt(g, debt);  in incstep()
1162   global_State *g = G(L);  in luaC_forcestep()  local
1164   if (isgenerational(g)) generationalcollection(L);  in luaC_forcestep()
1167   for (i = 0; g->tobefnz && (i < GCFINALIZENUM || g->gcstate == GCSpause); i++)  in luaC_forcestep()
1176   global_State *g = G(L);  in luaC_step()  local
1177   if (g->gcrunning) luaC_forcestep(L);  in luaC_step()
1178   else luaE_setdebt(g, -GCSTEPSIZE);  /* avoid being called too often */  in luaC_step()
1188   global_State *g = G(L);  in luaC_fullgc()  local
1189   int origkind = g->gckind;  in luaC_fullgc()
1192     g->gckind = KGC_EMERGENCY;  in luaC_fullgc()
1194     g->gckind = KGC_NORMAL;  in luaC_fullgc()
1197   if (keepinvariant(g)) {  /* may there be some black objects? */  in luaC_fullgc()
1210   g->gckind = origkind;  in luaC_fullgc()
1211   setpause(g, gettotalbytes(g));  in luaC_fullgc()