Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  1. /*
  2. ** $Id: lgc.c,v 2.38.1.2 2011/03/18 18:05:38 roberto Exp $
  3. ** Garbage Collector
  4. ** See Copyright Notice in lua.h
  5. */
  6.  
  7. #include <string.h>
  8.  
  9. #define lgc_c
  10. #define LUA_CORE
  11.  
  12. #include "lua.h"
  13.  
  14. #include "ldebug.h"
  15. #include "ldo.h"
  16. #include "lfunc.h"
  17. #include "lgc.h"
  18. #include "lmem.h"
  19. #include "lobject.h"
  20. #include "lstate.h"
  21. #include "lstring.h"
  22. #include "ltable.h"
  23. #include "ltm.h"
  24.  
  25.  
  26. #define GCSTEPSIZE      1024u
  27. #define GCSWEEPMAX      40
  28. #define GCSWEEPCOST     10
  29. #define GCFINALIZECOST  100
  30.  
  31.  
  32. #define maskmarks       cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
  33.  
  34. #define makewhite(g,x)  \
  35.    ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g)))
  36.  
  37. #define white2gray(x)   reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
  38. #define black2gray(x)   resetbit((x)->gch.marked, BLACKBIT)
  39.  
  40. #define stringmark(s)   reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT)
  41.  
  42.  
  43. #define isfinalized(u)          testbit((u)->marked, FINALIZEDBIT)
  44. #define markfinalized(u)        l_setbit((u)->marked, FINALIZEDBIT)
  45.  
  46.  
  47. #define KEYWEAK         bitmask(KEYWEAKBIT)
  48. #define VALUEWEAK       bitmask(VALUEWEAKBIT)
  49.  
  50.  
  51.  
  52. #define markvalue(g,o) { checkconsistency(o); \
  53.   if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
  54.  
  55. #define markobject(g,t) { if (iswhite(obj2gco(t))) \
  56.                 reallymarkobject(g, obj2gco(t)); }
  57.  
  58.  
  59. #define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)
  60.  
  61.  
  62. static void removeentry (Node *n) {
  63.   lua_assert(ttisnil(gval(n)));
  64.   if (iscollectable(gkey(n)))
  65.     setttype(gkey(n), LUA_TDEADKEY);  /* dead key; remove it */
  66. }
  67.  
  68.  
  69. static void reallymarkobject (global_State *g, GCObject *o) {
  70.   lua_assert(iswhite(o) && !isdead(g, o));
  71.   white2gray(o);
  72.   switch (o->gch.tt) {
  73.     case LUA_TSTRING: {
  74.       return;
  75.     }
  76.     case LUA_TUSERDATA: {
  77.       Table *mt = gco2u(o)->metatable;
  78.       gray2black(o);  /* udata are never gray */
  79.       if (mt) markobject(g, mt);
  80.       markobject(g, gco2u(o)->env);
  81.       return;
  82.     }
  83.     case LUA_TUPVAL: {
  84.       UpVal *uv = gco2uv(o);
  85.       markvalue(g, uv->v);
  86.       if (uv->v == &uv->u.value)  /* closed? */
  87.         gray2black(o);  /* open upvalues are never black */
  88.       return;
  89.     }
  90.     case LUA_TFUNCTION: {
  91.       gco2cl(o)->c.gclist = g->gray;
  92.       g->gray = o;
  93.       break;
  94.     }
  95.     case LUA_TTABLE: {
  96.       gco2h(o)->gclist = g->gray;
  97.       g->gray = o;
  98.       break;
  99.     }
  100.     case LUA_TTHREAD: {
  101.       gco2th(o)->gclist = g->gray;
  102.       g->gray = o;
  103.       break;
  104.     }
  105.     case LUA_TPROTO: {
  106.       gco2p(o)->gclist = g->gray;
  107.       g->gray = o;
  108.       break;
  109.     }
  110.     default: lua_assert(0);
  111.   }
  112. }
  113.  
  114.  
  115. static void marktmu (global_State *g) {
  116.   GCObject *u = g->tmudata;
  117.   if (u) {
  118.     do {
  119.       u = u->gch.next;
  120.       makewhite(g, u);  /* may be marked, if left from previous GC */
  121.       reallymarkobject(g, u);
  122.     } while (u != g->tmudata);
  123.   }
  124. }
  125.  
  126.  
  127. /* move `dead' udata that need finalization to list `tmudata' */
  128. size_t luaC_separateudata (lua_State *L, int all) {
  129.   global_State *g = G(L);
  130.   size_t deadmem = 0;
  131.   GCObject **p = &g->mainthread->next;
  132.   GCObject *curr;
  133.   while ((curr = *p) != NULL) {
  134.     if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
  135.       p = &curr->gch.next;  /* don't bother with them */
  136.     else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
  137.       markfinalized(gco2u(curr));  /* don't need finalization */
  138.       p = &curr->gch.next;
  139.     }
  140.     else {  /* must call its gc method */
  141.       deadmem += sizeudata(gco2u(curr));
  142.       markfinalized(gco2u(curr));
  143.       *p = curr->gch.next;
  144.       /* link `curr' at the end of `tmudata' list */
  145.       if (g->tmudata == NULL)  /* list is empty? */
  146.         g->tmudata = curr->gch.next = curr;  /* creates a circular list */
  147.       else {
  148.         curr->gch.next = g->tmudata->gch.next;
  149.         g->tmudata->gch.next = curr;
  150.         g->tmudata = curr;
  151.       }
  152.     }
  153.   }
  154.   return deadmem;
  155. }
  156.  
  157.  
  158. static int traversetable (global_State *g, Table *h) {
  159.   int i;
  160.   int weakkey = 0;
  161.   int weakvalue = 0;
  162.   const TValue *mode;
  163.   if (h->metatable)
  164.     markobject(g, h->metatable);
  165.   mode = gfasttm(g, h->metatable, TM_MODE);
  166.   if (mode && ttisstring(mode)) {  /* is there a weak mode? */
  167.     weakkey = (strchr(svalue(mode), 'k') != NULL);
  168.     weakvalue = (strchr(svalue(mode), 'v') != NULL);
  169.     if (weakkey || weakvalue) {  /* is really weak? */
  170.       h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
  171.       h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
  172.                              (weakvalue << VALUEWEAKBIT));
  173.       h->gclist = g->weak;  /* must be cleared after GC, ... */
  174.       g->weak = obj2gco(h);  /* ... so put in the appropriate list */
  175.     }
  176.   }
  177.   if (weakkey && weakvalue) return 1;
  178.   if (!weakvalue) {
  179.     i = h->sizearray;
  180.     while (i--)
  181.       markvalue(g, &h->array[i]);
  182.   }
  183.   i = sizenode(h);
  184.   while (i--) {
  185.     Node *n = gnode(h, i);
  186.     lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
  187.     if (ttisnil(gval(n)))
  188.       removeentry(n);  /* remove empty entries */
  189.     else {
  190.       lua_assert(!ttisnil(gkey(n)));
  191.       if (!weakkey) markvalue(g, gkey(n));
  192.       if (!weakvalue) markvalue(g, gval(n));
  193.     }
  194.   }
  195.   return weakkey || weakvalue;
  196. }
  197.  
  198.  
  199. /*
  200. ** All marks are conditional because a GC may happen while the
  201. ** prototype is still being created
  202. */
  203. static void traverseproto (global_State *g, Proto *f) {
  204.   int i;
  205.   if (f->source) stringmark(f->source);
  206.   for (i=0; i<f->sizek; i++)  /* mark literals */
  207.     markvalue(g, &f->k[i]);
  208.   for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
  209.     if (f->upvalues[i])
  210.       stringmark(f->upvalues[i]);
  211.   }
  212.   for (i=0; i<f->sizep; i++) {  /* mark nested protos */
  213.     if (f->p[i])
  214.       markobject(g, f->p[i]);
  215.   }
  216.   for (i=0; i<f->sizelocvars; i++) {  /* mark local-variable names */
  217.     if (f->locvars[i].varname)
  218.       stringmark(f->locvars[i].varname);
  219.   }
  220. }
  221.  
  222.  
  223.  
  224. static void traverseclosure (global_State *g, Closure *cl) {
  225.   markobject(g, cl->c.env);
  226.   if (cl->c.isC) {
  227.     int i;
  228.     for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
  229.       markvalue(g, &cl->c.upvalue[i]);
  230.   }
  231.   else {
  232.     int i;
  233.     lua_assert(cl->l.nupvalues == cl->l.p->nups);
  234.     markobject(g, cl->l.p);
  235.     for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
  236.       markobject(g, cl->l.upvals[i]);
  237.   }
  238. }
  239.  
  240.  
  241. static void checkstacksizes (lua_State *L, StkId max) {
  242.   int ci_used = cast_int(L->ci - L->base_ci);  /* number of `ci' in use */
  243.   int s_used = cast_int(max - L->stack);  /* part of stack in use */
  244.   if (L->size_ci > LUAI_MAXCALLS)  /* handling overflow? */
  245.     return;  /* do not touch the stacks */
  246.   if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
  247.     luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
  248.   condhardstacktests(luaD_reallocCI(L, ci_used + 1));
  249.   if (4*s_used < L->stacksize &&
  250.       2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
  251.     luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
  252.   condhardstacktests(luaD_reallocstack(L, s_used));
  253. }
  254.  
  255.  
  256. static void traversestack (global_State *g, lua_State *l) {
  257.   StkId o, lim;
  258.   CallInfo *ci;
  259.   markvalue(g, gt(l));
  260.   lim = l->top;
  261.   for (ci = l->base_ci; ci <= l->ci; ci++) {
  262.     lua_assert(ci->top <= l->stack_last);
  263.     if (lim < ci->top) lim = ci->top;
  264.   }
  265.   for (o = l->stack; o < l->top; o++)
  266.     markvalue(g, o);
  267.   for (; o <= lim; o++)
  268.     setnilvalue(o);
  269.   checkstacksizes(l, lim);
  270. }
  271.  
  272.  
  273. /*
  274. ** traverse one gray object, turning it to black.
  275. ** Returns `quantity' traversed.
  276. */
  277. static l_mem propagatemark (global_State *g) {
  278.   GCObject *o = g->gray;
  279.   lua_assert(isgray(o));
  280.   gray2black(o);
  281.   switch (o->gch.tt) {
  282.     case LUA_TTABLE: {
  283.       Table *h = gco2h(o);
  284.       g->gray = h->gclist;
  285.       if (traversetable(g, h))  /* table is weak? */
  286.         black2gray(o);  /* keep it gray */
  287.       return sizeof(Table) + sizeof(TValue) * h->sizearray +
  288.                              sizeof(Node) * sizenode(h);
  289.     }
  290.     case LUA_TFUNCTION: {
  291.       Closure *cl = gco2cl(o);
  292.       g->gray = cl->c.gclist;
  293.       traverseclosure(g, cl);
  294.       return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
  295.                            sizeLclosure(cl->l.nupvalues);
  296.     }
  297.     case LUA_TTHREAD: {
  298.       lua_State *th = gco2th(o);
  299.       g->gray = th->gclist;
  300.       th->gclist = g->grayagain;
  301.       g->grayagain = o;
  302.       black2gray(o);
  303.       traversestack(g, th);
  304.       return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
  305.                                  sizeof(CallInfo) * th->size_ci;
  306.     }
  307.     case LUA_TPROTO: {
  308.       Proto *p = gco2p(o);
  309.       g->gray = p->gclist;
  310.       traverseproto(g, p);
  311.       return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
  312.                              sizeof(Proto *) * p->sizep +
  313.                              sizeof(TValue) * p->sizek +
  314.                              sizeof(int) * p->sizelineinfo +
  315.                              sizeof(LocVar) * p->sizelocvars +
  316.                              sizeof(TString *) * p->sizeupvalues;
  317.     }
  318.     default: lua_assert(0); return 0;
  319.   }
  320. }
  321.  
  322.  
  323. static size_t propagateall (global_State *g) {
  324.   size_t m = 0;
  325.   while (g->gray) m += propagatemark(g);
  326.   return m;
  327. }
  328.  
  329.  
  330. /*
  331. ** The next function tells whether a key or value can be cleared from
  332. ** a weak table. Non-collectable objects are never removed from weak
  333. ** tables. Strings behave as `values', so are never removed too. for
  334. ** other objects: if really collected, cannot keep them; for userdata
  335. ** being finalized, keep them in keys, but not in values
  336. */
  337. static int iscleared (const TValue *o, int iskey) {
  338.   if (!iscollectable(o)) return 0;
  339.   if (ttisstring(o)) {
  340.     stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
  341.     return 0;
  342.   }
  343.   return iswhite(gcvalue(o)) ||
  344.     (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
  345. }
  346.  
  347.  
  348. /*
  349. ** clear collected entries from weaktables
  350. */
  351. static void cleartable (GCObject *l) {
  352.   while (l) {
  353.     Table *h = gco2h(l);
  354.     int i = h->sizearray;
  355.     lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
  356.                testbit(h->marked, KEYWEAKBIT));
  357.     if (testbit(h->marked, VALUEWEAKBIT)) {
  358.       while (i--) {
  359.         TValue *o = &h->array[i];
  360.         if (iscleared(o, 0))  /* value was collected? */
  361.           setnilvalue(o);  /* remove value */
  362.       }
  363.     }
  364.     i = sizenode(h);
  365.     while (i--) {
  366.       Node *n = gnode(h, i);
  367.       if (!ttisnil(gval(n)) &&  /* non-empty entry? */
  368.           (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
  369.         setnilvalue(gval(n));  /* remove value ... */
  370.         removeentry(n);  /* remove entry from table */
  371.       }
  372.     }
  373.     l = h->gclist;
  374.   }
  375. }
  376.  
  377.  
  378. static void freeobj (lua_State *L, GCObject *o) {
  379.   switch (o->gch.tt) {
  380.     case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
  381.     case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
  382.     case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
  383.     case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
  384.     case LUA_TTHREAD: {
  385.       lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
  386.       luaE_freethread(L, gco2th(o));
  387.       break;
  388.     }
  389.     case LUA_TSTRING: {
  390.       G(L)->strt.nuse--;
  391.       luaM_freemem(L, o, sizestring(gco2ts(o)));
  392.       break;
  393.     }
  394.     case LUA_TUSERDATA: {
  395.       luaM_freemem(L, o, sizeudata(gco2u(o)));
  396.       break;
  397.     }
  398.     default: lua_assert(0);
  399.   }
  400. }
  401.  
  402.  
  403.  
  404. #define sweepwholelist(L,p)     sweeplist(L,p,MAX_LUMEM)
  405.  
  406.  
  407. static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  408.   GCObject *curr;
  409.   global_State *g = G(L);
  410.   int deadmask = otherwhite(g);
  411.   while ((curr = *p) != NULL && count-- > 0) {
  412.     if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
  413.       sweepwholelist(L, &gco2th(curr)->openupval);
  414.     if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
  415.       lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
  416.       makewhite(g, curr);  /* make it white (for next cycle) */
  417.       p = &curr->gch.next;
  418.     }
  419.     else {  /* must erase `curr' */
  420.       lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
  421.       *p = curr->gch.next;
  422.       if (curr == g->rootgc)  /* is the first element of the list? */
  423.         g->rootgc = curr->gch.next;  /* adjust first */
  424.       freeobj(L, curr);
  425.     }
  426.   }
  427.   return p;
  428. }
  429.  
  430.  
  431. static void checkSizes (lua_State *L) {
  432.   global_State *g = G(L);
  433.   /* check size of string hash */
  434.   if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
  435.       g->strt.size > MINSTRTABSIZE*2)
  436.     luaS_resize(L, g->strt.size/2);  /* table is too big */
  437.   /* check size of buffer */
  438.   if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) {  /* buffer too big? */
  439.     size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
  440.     luaZ_resizebuffer(L, &g->buff, newsize);
  441.   }
  442. }
  443.  
  444.  
  445. static void GCTM (lua_State *L) {
  446.   global_State *g = G(L);
  447.   GCObject *o = g->tmudata->gch.next;  /* get first element */
  448.   Udata *udata = rawgco2u(o);
  449.   const TValue *tm;
  450.   /* remove udata from `tmudata' */
  451.   if (o == g->tmudata)  /* last element? */
  452.     g->tmudata = NULL;
  453.   else
  454.     g->tmudata->gch.next = udata->uv.next;
  455.   udata->uv.next = g->mainthread->next;  /* return it to `root' list */
  456.   g->mainthread->next = o;
  457.   makewhite(g, o);
  458.   tm = fasttm(L, udata->uv.metatable, TM_GC);
  459.   if (tm != NULL) {
  460.     lu_byte oldah = L->allowhook;
  461.     lu_mem oldt = g->GCthreshold;
  462.     L->allowhook = 0;  /* stop debug hooks during GC tag method */
  463.     g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
  464.     setobj2s(L, L->top, tm);
  465.     setuvalue(L, L->top+1, udata);
  466.     L->top += 2;
  467.     luaD_call(L, L->top - 2, 0);
  468.     L->allowhook = oldah;  /* restore hooks */
  469.     g->GCthreshold = oldt;  /* restore threshold */
  470.   }
  471. }
  472.  
  473.  
  474. /*
  475. ** Call all GC tag methods
  476. */
  477. void luaC_callGCTM (lua_State *L) {
  478.   while (G(L)->tmudata)
  479.     GCTM(L);
  480. }
  481.  
  482.  
  483. void luaC_freeall (lua_State *L) {
  484.   global_State *g = G(L);
  485.   int i;
  486.   g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
  487.   sweepwholelist(L, &g->rootgc);
  488.   for (i = 0; i < g->strt.size; i++)  /* free all string lists */
  489.     sweepwholelist(L, &g->strt.hash[i]);
  490. }
  491.  
  492.  
  493. static void markmt (global_State *g) {
  494.   int i;
  495.   for (i=0; i<NUM_TAGS; i++)
  496.     if (g->mt[i]) markobject(g, g->mt[i]);
  497. }
  498.  
  499.  
  500. /* mark root set */
  501. static void markroot (lua_State *L) {
  502.   global_State *g = G(L);
  503.   g->gray = NULL;
  504.   g->grayagain = NULL;
  505.   g->weak = NULL;
  506.   markobject(g, g->mainthread);
  507.   /* make global table be traversed before main stack */
  508.   markvalue(g, gt(g->mainthread));
  509.   markvalue(g, registry(L));
  510.   markmt(g);
  511.   g->gcstate = GCSpropagate;
  512. }
  513.  
  514.  
  515. static void remarkupvals (global_State *g) {
  516.   UpVal *uv;
  517.   for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
  518.     lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
  519.     if (isgray(obj2gco(uv)))
  520.       markvalue(g, uv->v);
  521.   }
  522. }
  523.  
  524.  
  525. static void atomic (lua_State *L) {
  526.   global_State *g = G(L);
  527.   size_t udsize;  /* total size of userdata to be finalized */
  528.   /* remark occasional upvalues of (maybe) dead threads */
  529.   remarkupvals(g);
  530.   /* traverse objects cautch by write barrier and by 'remarkupvals' */
  531.   propagateall(g);
  532.   /* remark weak tables */
  533.   g->gray = g->weak;
  534.   g->weak = NULL;
  535.   lua_assert(!iswhite(obj2gco(g->mainthread)));
  536.   markobject(g, L);  /* mark running thread */
  537.   markmt(g);  /* mark basic metatables (again) */
  538.   propagateall(g);
  539.   /* remark gray again */
  540.   g->gray = g->grayagain;
  541.   g->grayagain = NULL;
  542.   propagateall(g);
  543.   udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
  544.   marktmu(g);  /* mark `preserved' userdata */
  545.   udsize += propagateall(g);  /* remark, to propagate `preserveness' */
  546.   cleartable(g->weak);  /* remove collected objects from weak tables */
  547.   /* flip current white */
  548.   g->currentwhite = cast_byte(otherwhite(g));
  549.   g->sweepstrgc = 0;
  550.   g->sweepgc = &g->rootgc;
  551.   g->gcstate = GCSsweepstring;
  552.   g->estimate = g->totalbytes - udsize;  /* first estimate */
  553. }
  554.  
  555.  
  556. static l_mem singlestep (lua_State *L) {
  557.   global_State *g = G(L);
  558.   /*lua_checkmemory(L);*/
  559.   switch (g->gcstate) {
  560.     case GCSpause: {
  561.       markroot(L);  /* start a new collection */
  562.       return 0;
  563.     }
  564.     case GCSpropagate: {
  565.       if (g->gray)
  566.         return propagatemark(g);
  567.       else {  /* no more `gray' objects */
  568.         atomic(L);  /* finish mark phase */
  569.         return 0;
  570.       }
  571.     }
  572.     case GCSsweepstring: {
  573.       lu_mem old = g->totalbytes;
  574.       sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
  575.       if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
  576.         g->gcstate = GCSsweep;  /* end sweep-string phase */
  577.       lua_assert(old >= g->totalbytes);
  578.       g->estimate -= old - g->totalbytes;
  579.       return GCSWEEPCOST;
  580.     }
  581.     case GCSsweep: {
  582.       lu_mem old = g->totalbytes;
  583.       g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
  584.       if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
  585.         checkSizes(L);
  586.         g->gcstate = GCSfinalize;  /* end sweep phase */
  587.       }
  588.       lua_assert(old >= g->totalbytes);
  589.       g->estimate -= old - g->totalbytes;
  590.       return GCSWEEPMAX*GCSWEEPCOST;
  591.     }
  592.     case GCSfinalize: {
  593.       if (g->tmudata) {
  594.         GCTM(L);
  595.         if (g->estimate > GCFINALIZECOST)
  596.           g->estimate -= GCFINALIZECOST;
  597.         return GCFINALIZECOST;
  598.       }
  599.       else {
  600.         g->gcstate = GCSpause;  /* end collection */
  601.         g->gcdept = 0;
  602.         return 0;
  603.       }
  604.     }
  605.     default: lua_assert(0); return 0;
  606.   }
  607. }
  608.  
  609.  
  610. void luaC_step (lua_State *L) {
  611.   global_State *g = G(L);
  612.   l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  613.   if (lim == 0)
  614.     lim = (MAX_LUMEM-1)/2;  /* no limit */
  615.   g->gcdept += g->totalbytes - g->GCthreshold;
  616.   do {
  617.     lim -= singlestep(L);
  618.     if (g->gcstate == GCSpause)
  619.       break;
  620.   } while (lim > 0);
  621.   if (g->gcstate != GCSpause) {
  622.     if (g->gcdept < GCSTEPSIZE)
  623.       g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
  624.     else {
  625.       g->gcdept -= GCSTEPSIZE;
  626.       g->GCthreshold = g->totalbytes;
  627.     }
  628.   }
  629.   else {
  630.     setthreshold(g);
  631.   }
  632. }
  633.  
  634.  
  635. void luaC_fullgc (lua_State *L) {
  636.   global_State *g = G(L);
  637.   if (g->gcstate <= GCSpropagate) {
  638.     /* reset sweep marks to sweep all elements (returning them to white) */
  639.     g->sweepstrgc = 0;
  640.     g->sweepgc = &g->rootgc;
  641.     /* reset other collector lists */
  642.     g->gray = NULL;
  643.     g->grayagain = NULL;
  644.     g->weak = NULL;
  645.     g->gcstate = GCSsweepstring;
  646.   }
  647.   lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
  648.   /* finish any pending sweep phase */
  649.   while (g->gcstate != GCSfinalize) {
  650.     lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
  651.     singlestep(L);
  652.   }
  653.   markroot(L);
  654.   while (g->gcstate != GCSpause) {
  655.     singlestep(L);
  656.   }
  657.   setthreshold(g);
  658. }
  659.  
  660.  
  661. void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
  662.   global_State *g = G(L);
  663.   lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  664.   lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  665.   lua_assert(ttype(&o->gch) != LUA_TTABLE);
  666.   /* must keep invariant? */
  667.   if (g->gcstate == GCSpropagate)
  668.     reallymarkobject(g, v);  /* restore invariant */
  669.   else  /* don't mind */
  670.     makewhite(g, o);  /* mark as white just to avoid other barriers */
  671. }
  672.  
  673.  
  674. void luaC_barrierback (lua_State *L, Table *t) {
  675.   global_State *g = G(L);
  676.   GCObject *o = obj2gco(t);
  677.   lua_assert(isblack(o) && !isdead(g, o));
  678.   lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  679.   black2gray(o);  /* make table gray (again) */
  680.   t->gclist = g->grayagain;
  681.   g->grayagain = o;
  682. }
  683.  
  684.  
  685. void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  686.   global_State *g = G(L);
  687.   o->gch.next = g->rootgc;
  688.   g->rootgc = o;
  689.   o->gch.marked = luaC_white(g);
  690.   o->gch.tt = tt;
  691. }
  692.  
  693.  
  694. void luaC_linkupval (lua_State *L, UpVal *uv) {
  695.   global_State *g = G(L);
  696.   GCObject *o = obj2gco(uv);
  697.   o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
  698.   g->rootgc = o;
  699.   if (isgray(o)) {
  700.     if (g->gcstate == GCSpropagate) {
  701.       gray2black(o);  /* closed upvalues need barrier */
  702.       luaC_barrier(L, uv, uv->v);
  703.     }
  704.     else {  /* sweep phase: sweep it (turning it into white) */
  705.       makewhite(g, o);
  706.       lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  707.     }
  708.   }
  709. }
  710.  
  711.