Lua 5.1.4: lgc.c

L0001    /*
L0002    ** $Id: lgc.c,v 2.38.1.1 2007/12/27 13:02:25 roberto Exp $
L0003    ** Garbage Collector
L0004    ** See Copyright Notice in lua.h
L0005    */
L0006    
L0007    #include <string.h>
L0008    
L0009    #define lgc_c
L0010    #define LUA_CORE
L0011    
L0012    #include "lua.h"
L0013    
L0014    #include "ldebug.h"
L0015    #include "ldo.h"
L0016    #include "lfunc.h"
L0017    #include "lgc.h"
L0018    #include "lmem.h"
L0019    #include "lobject.h"
L0020    #include "lstate.h"
L0021    #include "lstring.h"
L0022    #include "ltable.h"
L0023    #include "ltm.h"
L0024    
L0025    
L0026    #define GCSTEPSIZE	1024u
L0027    #define GCSWEEPMAX	40
L0028    #define GCSWEEPCOST	10
L0029    #define GCFINALIZECOST	100
L0030    
L0031    
L0032    #define maskmarks	cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
L0033    
L0034    #define makewhite(g,x)	\
L0035       ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g)))
L0036    
L0037    #define white2gray(x)	reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
L0038    #define black2gray(x)	resetbit((x)->gch.marked, BLACKBIT)
L0039    
L0040    #define stringmark(s)	reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT)
L0041    
L0042    
L0043    #define isfinalized(u)		testbit((u)->marked, FINALIZEDBIT)
L0044    #define markfinalized(u)	l_setbit((u)->marked, FINALIZEDBIT)
L0045    
L0046    
L0047    #define KEYWEAK         bitmask(KEYWEAKBIT)
L0048    #define VALUEWEAK       bitmask(VALUEWEAKBIT)
L0049    
L0050    
L0051    
L0052    #define markvalue(g,o) { checkconsistency(o); \
L0053      if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
L0054    
L0055    #define markobject(g,t) { if (iswhite(obj2gco(t))) \
L0056    		reallymarkobject(g, obj2gco(t)); }
L0057    
L0058    
L0059    #define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)
L0060    
L0061    
L0062    static void removeentry (Node *n) {
L0063      lua_assert(ttisnil(gval(n)));
L0064      if (iscollectable(gkey(n)))
L0065        setttype(gkey(n), LUA_TDEADKEY);  /* dead key; remove it */
L0066    }
L0067    
L0068    
L0069    static void reallymarkobject (global_State *g, GCObject *o) {
L0070      lua_assert(iswhite(o) && !isdead(g, o));
L0071      white2gray(o);
L0072      switch (o->gch.tt) {
L0073        case LUA_TSTRING: {
L0074          return;
L0075        }
L0076        case LUA_TUSERDATA: {
L0077          Table *mt = gco2u(o)->metatable;
L0078          gray2black(o);  /* udata are never gray */
L0079          if (mt) markobject(g, mt);
L0080          markobject(g, gco2u(o)->env);
L0081          return;
L0082        }
L0083        case LUA_TUPVAL: {
L0084          UpVal *uv = gco2uv(o);
L0085          markvalue(g, uv->v);
L0086          if (uv->v == &uv->u.value)  /* closed? */
L0087            gray2black(o);  /* open upvalues are never black */
L0088          return;
L0089        }
L0090        case LUA_TFUNCTION: {
L0091          gco2cl(o)->c.gclist = g->gray;
L0092          g->gray = o;
L0093          break;
L0094        }
L0095        case LUA_TTABLE: {
L0096          gco2h(o)->gclist = g->gray;
L0097          g->gray = o;
L0098          break;
L0099        }
L0100        case LUA_TTHREAD: {
L0101          gco2th(o)->gclist = g->gray;
L0102          g->gray = o;
L0103          break;
L0104        }
L0105        case LUA_TPROTO: {
L0106          gco2p(o)->gclist = g->gray;
L0107          g->gray = o;
L0108          break;
L0109        }
L0110        default: lua_assert(0);
L0111      }
L0112    }
L0113    
L0114    
L0115    static void marktmu (global_State *g) {
L0116      GCObject *u = g->tmudata;
L0117      if (u) {
L0118        do {
L0119          u = u->gch.next;
L0120          makewhite(g, u);  /* may be marked, if left from previous GC */
L0121          reallymarkobject(g, u);
L0122        } while (u != g->tmudata);
L0123      }
L0124    }
L0125    
L0126    
L0127    /* move `dead' udata that need finalization to list `tmudata' */
L0128    size_t luaC_separateudata (lua_State *L, int all) {
L0129      global_State *g = G(L);
L0130      size_t deadmem = 0;
L0131      GCObject **p = &g->mainthread->next;
L0132      GCObject *curr;
L0133      while ((curr = *p) != NULL) {
L0134        if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
L0135          p = &curr->gch.next;  /* don't bother with them */
L0136        else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
L0137          markfinalized(gco2u(curr));  /* don't need finalization */
L0138          p = &curr->gch.next;
L0139        }
L0140        else {  /* must call its gc method */
L0141          deadmem += sizeudata(gco2u(curr));
L0142          markfinalized(gco2u(curr));
L0143          *p = curr->gch.next;
L0144          /* link `curr' at the end of `tmudata' list */
L0145          if (g->tmudata == NULL)  /* list is empty? */
L0146            g->tmudata = curr->gch.next = curr;  /* creates a circular list */
L0147          else {
L0148            curr->gch.next = g->tmudata->gch.next;
L0149            g->tmudata->gch.next = curr;
L0150            g->tmudata = curr;
L0151          }
L0152        }
L0153      }
L0154      return deadmem;
L0155    }
L0156    
L0157    
L0158    static int traversetable (global_State *g, Table *h) {
L0159      int i;
L0160      int weakkey = 0;
L0161      int weakvalue = 0;
L0162      const TValue *mode;
L0163      if (h->metatable)
L0164        markobject(g, h->metatable);
L0165      mode = gfasttm(g, h->metatable, TM_MODE);
L0166      if (mode && ttisstring(mode)) {  /* is there a weak mode? */
L0167        weakkey = (strchr(svalue(mode), 'k') != NULL);
L0168        weakvalue = (strchr(svalue(mode), 'v') != NULL);
L0169        if (weakkey || weakvalue) {  /* is really weak? */
L0170          h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
L0171          h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
L0172                                 (weakvalue << VALUEWEAKBIT));
L0173          h->gclist = g->weak;  /* must be cleared after GC, ... */
L0174          g->weak = obj2gco(h);  /* ... so put in the appropriate list */
L0175        }
L0176      }
L0177      if (weakkey && weakvalue) return 1;
L0178      if (!weakvalue) {
L0179        i = h->sizearray;
L0180        while (i--)
L0181          markvalue(g, &h->array[i]);
L0182      }
L0183      i = sizenode(h);
L0184      while (i--) {
L0185        Node *n = gnode(h, i);
L0186        lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
L0187        if (ttisnil(gval(n)))
L0188          removeentry(n);  /* remove empty entries */
L0189        else {
L0190          lua_assert(!ttisnil(gkey(n)));
L0191          if (!weakkey) markvalue(g, gkey(n));
L0192          if (!weakvalue) markvalue(g, gval(n));
L0193        }
L0194      }
L0195      return weakkey || weakvalue;
L0196    }
L0197    
L0198    
L0199    /*
L0200    ** All marks are conditional because a GC may happen while the
L0201    ** prototype is still being created
L0202    */
L0203    static void traverseproto (global_State *g, Proto *f) {
L0204      int i;
L0205      if (f->source) stringmark(f->source);
L0206      for (i=0; i<f->sizek; i++)  /* mark literals */
L0207        markvalue(g, &f->k[i]);
L0208      for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
L0209        if (f->upvalues[i])
L0210          stringmark(f->upvalues[i]);
L0211      }
L0212      for (i=0; i<f->sizep; i++) {  /* mark nested protos */
L0213        if (f->p[i])
L0214          markobject(g, f->p[i]);
L0215      }
L0216      for (i=0; i<f->sizelocvars; i++) {  /* mark local-variable names */
L0217        if (f->locvars[i].varname)
L0218          stringmark(f->locvars[i].varname);
L0219      }
L0220    }
L0221    
L0222    
L0223    
L0224    static void traverseclosure (global_State *g, Closure *cl) {
L0225      markobject(g, cl->c.env);
L0226      if (cl->c.isC) {
L0227        int i;
L0228        for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
L0229          markvalue(g, &cl->c.upvalue[i]);
L0230      }
L0231      else {
L0232        int i;
L0233        lua_assert(cl->l.nupvalues == cl->l.p->nups);
L0234        markobject(g, cl->l.p);
L0235        for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
L0236          markobject(g, cl->l.upvals[i]);
L0237      }
L0238    }
L0239    
L0240    
L0241    static void checkstacksizes (lua_State *L, StkId max) {
L0242      int ci_used = cast_int(L->ci - L->base_ci);  /* number of `ci' in use */
L0243      int s_used = cast_int(max - L->stack);  /* part of stack in use */
L0244      if (L->size_ci > LUAI_MAXCALLS)  /* handling overflow? */
L0245        return;  /* do not touch the stacks */
L0246      if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
L0247        luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
L0248      condhardstacktests(luaD_reallocCI(L, ci_used + 1));
L0249      if (4*s_used < L->stacksize &&
L0250          2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
L0251        luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
L0252      condhardstacktests(luaD_reallocstack(L, s_used));
L0253    }
L0254    
L0255    
L0256    static void traversestack (global_State *g, lua_State *l) {
L0257      StkId o, lim;
L0258      CallInfo *ci;
L0259      markvalue(g, gt(l));
L0260      lim = l->top;
L0261      for (ci = l->base_ci; ci <= l->ci; ci++) {
L0262        lua_assert(ci->top <= l->stack_last);
L0263        if (lim < ci->top) lim = ci->top;
L0264      }
L0265      for (o = l->stack; o < l->top; o++)
L0266        markvalue(g, o);
L0267      for (; o <= lim; o++)
L0268        setnilvalue(o);
L0269      checkstacksizes(l, lim);
L0270    }
L0271    
L0272    
L0273    /*
L0274    ** traverse one gray object, turning it to black.
L0275    ** Returns `quantity' traversed.
L0276    */
L0277    static l_mem propagatemark (global_State *g) {
L0278      GCObject *o = g->gray;
L0279      lua_assert(isgray(o));
L0280      gray2black(o);
L0281      switch (o->gch.tt) {
L0282        case LUA_TTABLE: {
L0283          Table *h = gco2h(o);
L0284          g->gray = h->gclist;
L0285          if (traversetable(g, h))  /* table is weak? */
L0286            black2gray(o);  /* keep it gray */
L0287          return sizeof(Table) + sizeof(TValue) * h->sizearray +
L0288                                 sizeof(Node) * sizenode(h);
L0289        }
L0290        case LUA_TFUNCTION: {
L0291          Closure *cl = gco2cl(o);
L0292          g->gray = cl->c.gclist;
L0293          traverseclosure(g, cl);
L0294          return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
L0295                               sizeLclosure(cl->l.nupvalues);
L0296        }
L0297        case LUA_TTHREAD: {
L0298          lua_State *th = gco2th(o);
L0299          g->gray = th->gclist;
L0300          th->gclist = g->grayagain;
L0301          g->grayagain = o;
L0302          black2gray(o);
L0303          traversestack(g, th);
L0304          return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
L0305                                     sizeof(CallInfo) * th->size_ci;
L0306        }
L0307        case LUA_TPROTO: {
L0308          Proto *p = gco2p(o);
L0309          g->gray = p->gclist;
L0310          traverseproto(g, p);
L0311          return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
L0312                                 sizeof(Proto *) * p->sizep +
L0313                                 sizeof(TValue) * p->sizek + 
L0314                                 sizeof(int) * p->sizelineinfo +
L0315                                 sizeof(LocVar) * p->sizelocvars +
L0316                                 sizeof(TString *) * p->sizeupvalues;
L0317        }
L0318        default: lua_assert(0); return 0;
L0319      }
L0320    }
L0321    
L0322    
L0323    static size_t propagateall (global_State *g) {
L0324      size_t m = 0;
L0325      while (g->gray) m += propagatemark(g);
L0326      return m;
L0327    }
L0328    
L0329    
L0330    /*
L0331    ** The next function tells whether a key or value can be cleared from
L0332    ** a weak table. Non-collectable objects are never removed from weak
L0333    ** tables. Strings behave as `values', so are never removed too. for
L0334    ** other objects: if really collected, cannot keep them; for userdata
L0335    ** being finalized, keep them in keys, but not in values
L0336    */
L0337    static int iscleared (const TValue *o, int iskey) {
L0338      if (!iscollectable(o)) return 0;
L0339      if (ttisstring(o)) {
L0340        stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
L0341        return 0;
L0342      }
L0343      return iswhite(gcvalue(o)) ||
L0344        (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
L0345    }
L0346    
L0347    
L0348    /*
L0349    ** clear collected entries from weaktables
L0350    */
L0351    static void cleartable (GCObject *l) {
L0352      while (l) {
L0353        Table *h = gco2h(l);
L0354        int i = h->sizearray;
L0355        lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
L0356                   testbit(h->marked, KEYWEAKBIT));
L0357        if (testbit(h->marked, VALUEWEAKBIT)) {
L0358          while (i--) {
L0359            TValue *o = &h->array[i];
L0360            if (iscleared(o, 0))  /* value was collected? */
L0361              setnilvalue(o);  /* remove value */
L0362          }
L0363        }
L0364        i = sizenode(h);
L0365        while (i--) {
L0366          Node *n = gnode(h, i);
L0367          if (!ttisnil(gval(n)) &&  /* non-empty entry? */
L0368              (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
L0369            setnilvalue(gval(n));  /* remove value ... */
L0370            removeentry(n);  /* remove entry from table */
L0371          }
L0372        }
L0373        l = h->gclist;
L0374      }
L0375    }
L0376    
L0377    
L0378    static void freeobj (lua_State *L, GCObject *o) {
L0379      switch (o->gch.tt) {
L0380        case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
L0381        case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
L0382        case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
L0383        case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
L0384        case LUA_TTHREAD: {
L0385          lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
L0386          luaE_freethread(L, gco2th(o));
L0387          break;
L0388        }
L0389        case LUA_TSTRING: {
L0390          G(L)->strt.nuse--;
L0391          luaM_freemem(L, o, sizestring(gco2ts(o)));
L0392          break;
L0393        }
L0394        case LUA_TUSERDATA: {
L0395          luaM_freemem(L, o, sizeudata(gco2u(o)));
L0396          break;
L0397        }
L0398        default: lua_assert(0);
L0399      }
L0400    }
L0401    
L0402    
L0403    
L0404    #define sweepwholelist(L,p)	sweeplist(L,p,MAX_LUMEM)
L0405    
L0406    
L0407    static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
L0408      GCObject *curr;
L0409      global_State *g = G(L);
L0410      int deadmask = otherwhite(g);
L0411      while ((curr = *p) != NULL && count-- > 0) {
L0412        if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
L0413          sweepwholelist(L, &gco2th(curr)->openupval);
L0414        if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
L0415          lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
L0416          makewhite(g, curr);  /* make it white (for next cycle) */
L0417          p = &curr->gch.next;
L0418        }
L0419        else {  /* must erase `curr' */
L0420          lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
L0421          *p = curr->gch.next;
L0422          if (curr == g->rootgc)  /* is the first element of the list? */
L0423            g->rootgc = curr->gch.next;  /* adjust first */
L0424          freeobj(L, curr);
L0425        }
L0426      }
L0427      return p;
L0428    }
L0429    
L0430    
L0431    static void checkSizes (lua_State *L) {
L0432      global_State *g = G(L);
L0433      /* check size of string hash */
L0434      if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
L0435          g->strt.size > MINSTRTABSIZE*2)
L0436        luaS_resize(L, g->strt.size/2);  /* table is too big */
L0437      /* check size of buffer */
L0438      if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) {  /* buffer too big? */
L0439        size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
L0440        luaZ_resizebuffer(L, &g->buff, newsize);
L0441      }
L0442    }
L0443    
L0444    
L0445    static void GCTM (lua_State *L) {
L0446      global_State *g = G(L);
L0447      GCObject *o = g->tmudata->gch.next;  /* get first element */
L0448      Udata *udata = rawgco2u(o);
L0449      const TValue *tm;
L0450      /* remove udata from `tmudata' */
L0451      if (o == g->tmudata)  /* last element? */
L0452        g->tmudata = NULL;
L0453      else
L0454        g->tmudata->gch.next = udata->uv.next;
L0455      udata->uv.next = g->mainthread->next;  /* return it to `root' list */
L0456      g->mainthread->next = o;
L0457      makewhite(g, o);
L0458      tm = fasttm(L, udata->uv.metatable, TM_GC);
L0459      if (tm != NULL) {
L0460        lu_byte oldah = L->allowhook;
L0461        lu_mem oldt = g->GCthreshold;
L0462        L->allowhook = 0;  /* stop debug hooks during GC tag method */
L0463        g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
L0464        setobj2s(L, L->top, tm);
L0465        setuvalue(L, L->top+1, udata);
L0466        L->top += 2;
L0467        luaD_call(L, L->top - 2, 0);
L0468        L->allowhook = oldah;  /* restore hooks */
L0469        g->GCthreshold = oldt;  /* restore threshold */
L0470      }
L0471    }
L0472    
L0473    
L0474    /*
L0475    ** Call all GC tag methods
L0476    */
L0477    void luaC_callGCTM (lua_State *L) {
L0478      while (G(L)->tmudata)
L0479        GCTM(L);
L0480    }
L0481    
L0482    
L0483    void luaC_freeall (lua_State *L) {
L0484      global_State *g = G(L);
L0485      int i;
L0486      g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
L0487      sweepwholelist(L, &g->rootgc);
L0488      for (i = 0; i < g->strt.size; i++)  /* free all string lists */
L0489        sweepwholelist(L, &g->strt.hash[i]);
L0490    }
L0491    
L0492    
L0493    static void markmt (global_State *g) {
L0494      int i;
L0495      for (i=0; i<NUM_TAGS; i++)
L0496        if (g->mt[i]) markobject(g, g->mt[i]);
L0497    }
L0498    
L0499    
L0500    /* mark root set */
L0501    static void markroot (lua_State *L) {
L0502      global_State *g = G(L);
L0503      g->gray = NULL;
L0504      g->grayagain = NULL;
L0505      g->weak = NULL;
L0506      markobject(g, g->mainthread);
L0507      /* make global table be traversed before main stack */
L0508      markvalue(g, gt(g->mainthread));
L0509      markvalue(g, registry(L));
L0510      markmt(g);
L0511      g->gcstate = GCSpropagate;
L0512    }
L0513    
L0514    
L0515    static void remarkupvals (global_State *g) {
L0516      UpVal *uv;
L0517      for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
L0518        lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
L0519        if (isgray(obj2gco(uv)))
L0520          markvalue(g, uv->v);
L0521      }
L0522    }
L0523    
L0524    
L0525    static void atomic (lua_State *L) {
L0526      global_State *g = G(L);
L0527      size_t udsize;  /* total size of userdata to be finalized */
L0528      /* remark occasional upvalues of (maybe) dead threads */
L0529      remarkupvals(g);
L0530      /* traverse objects cautch by write barrier and by 'remarkupvals' */
L0531      propagateall(g);
L0532      /* remark weak tables */
L0533      g->gray = g->weak;
L0534      g->weak = NULL;
L0535      lua_assert(!iswhite(obj2gco(g->mainthread)));
L0536      markobject(g, L);  /* mark running thread */
L0537      markmt(g);  /* mark basic metatables (again) */
L0538      propagateall(g);
L0539      /* remark gray again */
L0540      g->gray = g->grayagain;
L0541      g->grayagain = NULL;
L0542      propagateall(g);
L0543      udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
L0544      marktmu(g);  /* mark `preserved' userdata */
L0545      udsize += propagateall(g);  /* remark, to propagate `preserveness' */
L0546      cleartable(g->weak);  /* remove collected objects from weak tables */
L0547      /* flip current white */
L0548      g->currentwhite = cast_byte(otherwhite(g));
L0549      g->sweepstrgc = 0;
L0550      g->sweepgc = &g->rootgc;
L0551      g->gcstate = GCSsweepstring;
L0552      g->estimate = g->totalbytes - udsize;  /* first estimate */
L0553    }
L0554    
L0555    
L0556    static l_mem singlestep (lua_State *L) {
L0557      global_State *g = G(L);
L0558      /*lua_checkmemory(L);*/
L0559      switch (g->gcstate) {
L0560        case GCSpause: {
L0561          markroot(L);  /* start a new collection */
L0562          return 0;
L0563        }
L0564        case GCSpropagate: {
L0565          if (g->gray)
L0566            return propagatemark(g);
L0567          else {  /* no more `gray' objects */
L0568            atomic(L);  /* finish mark phase */
L0569            return 0;
L0570          }
L0571        }
L0572        case GCSsweepstring: {
L0573          lu_mem old = g->totalbytes;
L0574          sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
L0575          if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
L0576            g->gcstate = GCSsweep;  /* end sweep-string phase */
L0577          lua_assert(old >= g->totalbytes);
L0578          g->estimate -= old - g->totalbytes;
L0579          return GCSWEEPCOST;
L0580        }
L0581        case GCSsweep: {
L0582          lu_mem old = g->totalbytes;
L0583          g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
L0584          if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
L0585            checkSizes(L);
L0586            g->gcstate = GCSfinalize;  /* end sweep phase */
L0587          }
L0588          lua_assert(old >= g->totalbytes);
L0589          g->estimate -= old - g->totalbytes;
L0590          return GCSWEEPMAX*GCSWEEPCOST;
L0591        }
L0592        case GCSfinalize: {
L0593          if (g->tmudata) {
L0594            GCTM(L);
L0595            if (g->estimate > GCFINALIZECOST)
L0596              g->estimate -= GCFINALIZECOST;
L0597            return GCFINALIZECOST;
L0598          }
L0599          else {
L0600            g->gcstate = GCSpause;  /* end collection */
L0601            g->gcdept = 0;
L0602            return 0;
L0603          }
L0604        }
L0605        default: lua_assert(0); return 0;
L0606      }
L0607    }
L0608    
L0609    
L0610    void luaC_step (lua_State *L) {
L0611      global_State *g = G(L);
L0612      l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
L0613      if (lim == 0)
L0614        lim = (MAX_LUMEM-1)/2;  /* no limit */
L0615      g->gcdept += g->totalbytes - g->GCthreshold;
L0616      do {
L0617        lim -= singlestep(L);
L0618        if (g->gcstate == GCSpause)
L0619          break;
L0620      } while (lim > 0);
L0621      if (g->gcstate != GCSpause) {
L0622        if (g->gcdept < GCSTEPSIZE)
L0623          g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
L0624        else {
L0625          g->gcdept -= GCSTEPSIZE;
L0626          g->GCthreshold = g->totalbytes;
L0627        }
L0628      }
L0629      else {
L0630        lua_assert(g->totalbytes >= g->estimate);
L0631        setthreshold(g);
L0632      }
L0633    }
L0634    
L0635    
L0636    void luaC_fullgc (lua_State *L) {
L0637      global_State *g = G(L);
L0638      if (g->gcstate <= GCSpropagate) {
L0639        /* reset sweep marks to sweep all elements (returning them to white) */
L0640        g->sweepstrgc = 0;
L0641        g->sweepgc = &g->rootgc;
L0642        /* reset other collector lists */
L0643        g->gray = NULL;
L0644        g->grayagain = NULL;
L0645        g->weak = NULL;
L0646        g->gcstate = GCSsweepstring;
L0647      }
L0648      lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
L0649      /* finish any pending sweep phase */
L0650      while (g->gcstate != GCSfinalize) {
L0651        lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
L0652        singlestep(L);
L0653      }
L0654      markroot(L);
L0655      while (g->gcstate != GCSpause) {
L0656        singlestep(L);
L0657      }
L0658      setthreshold(g);
L0659    }
L0660    
L0661    
L0662    void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
L0663      global_State *g = G(L);
L0664      lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
L0665      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
L0666      lua_assert(ttype(&o->gch) != LUA_TTABLE);
L0667      /* must keep invariant? */
L0668      if (g->gcstate == GCSpropagate)
L0669        reallymarkobject(g, v);  /* restore invariant */
L0670      else  /* don't mind */
L0671        makewhite(g, o);  /* mark as white just to avoid other barriers */
L0672    }
L0673    
L0674    
L0675    void luaC_barrierback (lua_State *L, Table *t) {
L0676      global_State *g = G(L);
L0677      GCObject *o = obj2gco(t);
L0678      lua_assert(isblack(o) && !isdead(g, o));
L0679      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
L0680      black2gray(o);  /* make table gray (again) */
L0681      t->gclist = g->grayagain;
L0682      g->grayagain = o;
L0683    }
L0684    
L0685    
L0686    void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
L0687      global_State *g = G(L);
L0688      o->gch.next = g->rootgc;
L0689      g->rootgc = o;
L0690      o->gch.marked = luaC_white(g);
L0691      o->gch.tt = tt;
L0692    }
L0693    
L0694    
L0695    void luaC_linkupval (lua_State *L, UpVal *uv) {
L0696      global_State *g = G(L);
L0697      GCObject *o = obj2gco(uv);
L0698      o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
L0699      g->rootgc = o;
L0700      if (isgray(o)) { 
L0701        if (g->gcstate == GCSpropagate) {
L0702          gray2black(o);  /* closed upvalues need barrier */
L0703          luaC_barrier(L, uv, uv->v);
L0704        }
L0705        else {  /* sweep phase: sweep it (turning it into white) */
L0706          makewhite(g, o);
L0707          lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
L0708        }
L0709      }
L0710    }
L0711