1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/lua/src/lgc.c	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,711 @@
     1.4 +/*
     1.5 +** $Id: lgc.c,v 2.38.1.1 2007/12/27 13:02:25 roberto Exp $
     1.6 +** Garbage Collector
     1.7 +** See Copyright Notice in lua.h
     1.8 +*/
     1.9 +
    1.10 +#include <string.h>
    1.11 +
    1.12 +#define lgc_c
    1.13 +#define LUA_CORE
    1.14 +
    1.15 +#include "lua.h"
    1.16 +
    1.17 +#include "ldebug.h"
    1.18 +#include "ldo.h"
    1.19 +#include "lfunc.h"
    1.20 +#include "lgc.h"
    1.21 +#include "lmem.h"
    1.22 +#include "lobject.h"
    1.23 +#include "lstate.h"
    1.24 +#include "lstring.h"
    1.25 +#include "ltable.h"
    1.26 +#include "ltm.h"
    1.27 +
    1.28 +
    1.29 +#define GCSTEPSIZE	1024u
    1.30 +#define GCSWEEPMAX	40
    1.31 +#define GCSWEEPCOST	10
    1.32 +#define GCFINALIZECOST	100
    1.33 +
    1.34 +
    1.35 +#define maskmarks	cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
    1.36 +
    1.37 +#define makewhite(g,x)	\
    1.38 +   ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g)))
    1.39 +
    1.40 +#define white2gray(x)	reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
    1.41 +#define black2gray(x)	resetbit((x)->gch.marked, BLACKBIT)
    1.42 +
    1.43 +#define stringmark(s)	reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT)
    1.44 +
    1.45 +
    1.46 +#define isfinalized(u)		testbit((u)->marked, FINALIZEDBIT)
    1.47 +#define markfinalized(u)	l_setbit((u)->marked, FINALIZEDBIT)
    1.48 +
    1.49 +
    1.50 +#define KEYWEAK         bitmask(KEYWEAKBIT)
    1.51 +#define VALUEWEAK       bitmask(VALUEWEAKBIT)
    1.52 +
    1.53 +
    1.54 +
    1.55 +#define markvalue(g,o) { checkconsistency(o); \
    1.56 +  if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
    1.57 +
    1.58 +#define markobject(g,t) { if (iswhite(obj2gco(t))) \
    1.59 +		reallymarkobject(g, obj2gco(t)); }
    1.60 +
    1.61 +
    1.62 +#define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)
    1.63 +
    1.64 +
    1.65 +static void removeentry (Node *n) {
    1.66 +  lua_assert(ttisnil(gval(n)));
    1.67 +  if (iscollectable(gkey(n)))
    1.68 +    setttype(gkey(n), LUA_TDEADKEY);  /* dead key; remove it */
    1.69 +}
    1.70 +
    1.71 +
    1.72 +static void reallymarkobject (global_State *g, GCObject *o) {
    1.73 +  lua_assert(iswhite(o) && !isdead(g, o));
    1.74 +  white2gray(o);
    1.75 +  switch (o->gch.tt) {
    1.76 +    case LUA_TSTRING: {
    1.77 +      return;
    1.78 +    }
    1.79 +    case LUA_TUSERDATA: {
    1.80 +      Table *mt = gco2u(o)->metatable;
    1.81 +      gray2black(o);  /* udata are never gray */
    1.82 +      if (mt) markobject(g, mt);
    1.83 +      markobject(g, gco2u(o)->env);
    1.84 +      return;
    1.85 +    }
    1.86 +    case LUA_TUPVAL: {
    1.87 +      UpVal *uv = gco2uv(o);
    1.88 +      markvalue(g, uv->v);
    1.89 +      if (uv->v == &uv->u.value)  /* closed? */
    1.90 +        gray2black(o);  /* open upvalues are never black */
    1.91 +      return;
    1.92 +    }
    1.93 +    case LUA_TFUNCTION: {
    1.94 +      gco2cl(o)->c.gclist = g->gray;
    1.95 +      g->gray = o;
    1.96 +      break;
    1.97 +    }
    1.98 +    case LUA_TTABLE: {
    1.99 +      gco2h(o)->gclist = g->gray;
   1.100 +      g->gray = o;
   1.101 +      break;
   1.102 +    }
   1.103 +    case LUA_TTHREAD: {
   1.104 +      gco2th(o)->gclist = g->gray;
   1.105 +      g->gray = o;
   1.106 +      break;
   1.107 +    }
   1.108 +    case LUA_TPROTO: {
   1.109 +      gco2p(o)->gclist = g->gray;
   1.110 +      g->gray = o;
   1.111 +      break;
   1.112 +    }
   1.113 +    default: lua_assert(0);
   1.114 +  }
   1.115 +}
   1.116 +
   1.117 +
   1.118 +static void marktmu (global_State *g) {
   1.119 +  GCObject *u = g->tmudata;
   1.120 +  if (u) {
   1.121 +    do {
   1.122 +      u = u->gch.next;
   1.123 +      makewhite(g, u);  /* may be marked, if left from previous GC */
   1.124 +      reallymarkobject(g, u);
   1.125 +    } while (u != g->tmudata);
   1.126 +  }
   1.127 +}
   1.128 +
   1.129 +
   1.130 +/* move `dead' udata that need finalization to list `tmudata' */
   1.131 +size_t luaC_separateudata (lua_State *L, int all) {
   1.132 +  global_State *g = G(L);
   1.133 +  size_t deadmem = 0;
   1.134 +  GCObject **p = &g->mainthread->next;
   1.135 +  GCObject *curr;
   1.136 +  while ((curr = *p) != NULL) {
   1.137 +    if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
   1.138 +      p = &curr->gch.next;  /* don't bother with them */
   1.139 +    else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
   1.140 +      markfinalized(gco2u(curr));  /* don't need finalization */
   1.141 +      p = &curr->gch.next;
   1.142 +    }
   1.143 +    else {  /* must call its gc method */
   1.144 +      deadmem += sizeudata(gco2u(curr));
   1.145 +      markfinalized(gco2u(curr));
   1.146 +      *p = curr->gch.next;
   1.147 +      /* link `curr' at the end of `tmudata' list */
   1.148 +      if (g->tmudata == NULL)  /* list is empty? */
   1.149 +        g->tmudata = curr->gch.next = curr;  /* creates a circular list */
   1.150 +      else {
   1.151 +        curr->gch.next = g->tmudata->gch.next;
   1.152 +        g->tmudata->gch.next = curr;
   1.153 +        g->tmudata = curr;
   1.154 +      }
   1.155 +    }
   1.156 +  }
   1.157 +  return deadmem;
   1.158 +}
   1.159 +
   1.160 +
   1.161 +static int traversetable (global_State *g, Table *h) {
   1.162 +  int i;
   1.163 +  int weakkey = 0;
   1.164 +  int weakvalue = 0;
   1.165 +  const TValue *mode;
   1.166 +  if (h->metatable)
   1.167 +    markobject(g, h->metatable);
   1.168 +  mode = gfasttm(g, h->metatable, TM_MODE);
   1.169 +  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
   1.170 +    weakkey = (strchr(svalue(mode), 'k') != NULL);
   1.171 +    weakvalue = (strchr(svalue(mode), 'v') != NULL);
   1.172 +    if (weakkey || weakvalue) {  /* is really weak? */
   1.173 +      h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
   1.174 +      h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
   1.175 +                             (weakvalue << VALUEWEAKBIT));
   1.176 +      h->gclist = g->weak;  /* must be cleared after GC, ... */
   1.177 +      g->weak = obj2gco(h);  /* ... so put in the appropriate list */
   1.178 +    }
   1.179 +  }
   1.180 +  if (weakkey && weakvalue) return 1;
   1.181 +  if (!weakvalue) {
   1.182 +    i = h->sizearray;
   1.183 +    while (i--)
   1.184 +      markvalue(g, &h->array[i]);
   1.185 +  }
   1.186 +  i = sizenode(h);
   1.187 +  while (i--) {
   1.188 +    Node *n = gnode(h, i);
   1.189 +    lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
   1.190 +    if (ttisnil(gval(n)))
   1.191 +      removeentry(n);  /* remove empty entries */
   1.192 +    else {
   1.193 +      lua_assert(!ttisnil(gkey(n)));
   1.194 +      if (!weakkey) markvalue(g, gkey(n));
   1.195 +      if (!weakvalue) markvalue(g, gval(n));
   1.196 +    }
   1.197 +  }
   1.198 +  return weakkey || weakvalue;
   1.199 +}
   1.200 +
   1.201 +
   1.202 +/*
   1.203 +** All marks are conditional because a GC may happen while the
   1.204 +** prototype is still being created
   1.205 +*/
   1.206 +static void traverseproto (global_State *g, Proto *f) {
   1.207 +  int i;
   1.208 +  if (f->source) stringmark(f->source);
   1.209 +  for (i=0; i<f->sizek; i++)  /* mark literals */
   1.210 +    markvalue(g, &f->k[i]);
   1.211 +  for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
   1.212 +    if (f->upvalues[i])
   1.213 +      stringmark(f->upvalues[i]);
   1.214 +  }
   1.215 +  for (i=0; i<f->sizep; i++) {  /* mark nested protos */
   1.216 +    if (f->p[i])
   1.217 +      markobject(g, f->p[i]);
   1.218 +  }
   1.219 +  for (i=0; i<f->sizelocvars; i++) {  /* mark local-variable names */
   1.220 +    if (f->locvars[i].varname)
   1.221 +      stringmark(f->locvars[i].varname);
   1.222 +  }
   1.223 +}
   1.224 +
   1.225 +
   1.226 +
   1.227 +static void traverseclosure (global_State *g, Closure *cl) {
   1.228 +  markobject(g, cl->c.env);
   1.229 +  if (cl->c.isC) {
   1.230 +    int i;
   1.231 +    for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
   1.232 +      markvalue(g, &cl->c.upvalue[i]);
   1.233 +  }
   1.234 +  else {
   1.235 +    int i;
   1.236 +    lua_assert(cl->l.nupvalues == cl->l.p->nups);
   1.237 +    markobject(g, cl->l.p);
   1.238 +    for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
   1.239 +      markobject(g, cl->l.upvals[i]);
   1.240 +  }
   1.241 +}
   1.242 +
   1.243 +
   1.244 +static void checkstacksizes (lua_State *L, StkId max) {
   1.245 +  int ci_used = cast_int(L->ci - L->base_ci);  /* number of `ci' in use */
   1.246 +  int s_used = cast_int(max - L->stack);  /* part of stack in use */
   1.247 +  if (L->size_ci > LUAI_MAXCALLS)  /* handling overflow? */
   1.248 +    return;  /* do not touch the stacks */
   1.249 +  if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
   1.250 +    luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
   1.251 +  condhardstacktests(luaD_reallocCI(L, ci_used + 1));
   1.252 +  if (4*s_used < L->stacksize &&
   1.253 +      2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
   1.254 +    luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
   1.255 +  condhardstacktests(luaD_reallocstack(L, s_used));
   1.256 +}
   1.257 +
   1.258 +
   1.259 +static void traversestack (global_State *g, lua_State *l) {
   1.260 +  StkId o, lim;
   1.261 +  CallInfo *ci;
   1.262 +  markvalue(g, gt(l));
   1.263 +  lim = l->top;
   1.264 +  for (ci = l->base_ci; ci <= l->ci; ci++) {
   1.265 +    lua_assert(ci->top <= l->stack_last);
   1.266 +    if (lim < ci->top) lim = ci->top;
   1.267 +  }
   1.268 +  for (o = l->stack; o < l->top; o++)
   1.269 +    markvalue(g, o);
   1.270 +  for (; o <= lim; o++)
   1.271 +    setnilvalue(o);
   1.272 +  checkstacksizes(l, lim);
   1.273 +}
   1.274 +
   1.275 +
   1.276 +/*
   1.277 +** traverse one gray object, turning it to black.
   1.278 +** Returns `quantity' traversed.
   1.279 +*/
   1.280 +static l_mem propagatemark (global_State *g) {
   1.281 +  GCObject *o = g->gray;
   1.282 +  lua_assert(isgray(o));
   1.283 +  gray2black(o);
   1.284 +  switch (o->gch.tt) {
   1.285 +    case LUA_TTABLE: {
   1.286 +      Table *h = gco2h(o);
   1.287 +      g->gray = h->gclist;
   1.288 +      if (traversetable(g, h))  /* table is weak? */
   1.289 +        black2gray(o);  /* keep it gray */
   1.290 +      return sizeof(Table) + sizeof(TValue) * h->sizearray +
   1.291 +                             sizeof(Node) * sizenode(h);
   1.292 +    }
   1.293 +    case LUA_TFUNCTION: {
   1.294 +      Closure *cl = gco2cl(o);
   1.295 +      g->gray = cl->c.gclist;
   1.296 +      traverseclosure(g, cl);
   1.297 +      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
   1.298 +                           sizeLclosure(cl->l.nupvalues);
   1.299 +    }
   1.300 +    case LUA_TTHREAD: {
   1.301 +      lua_State *th = gco2th(o);
   1.302 +      g->gray = th->gclist;
   1.303 +      th->gclist = g->grayagain;
   1.304 +      g->grayagain = o;
   1.305 +      black2gray(o);
   1.306 +      traversestack(g, th);
   1.307 +      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
   1.308 +                                 sizeof(CallInfo) * th->size_ci;
   1.309 +    }
   1.310 +    case LUA_TPROTO: {
   1.311 +      Proto *p = gco2p(o);
   1.312 +      g->gray = p->gclist;
   1.313 +      traverseproto(g, p);
   1.314 +      return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
   1.315 +                             sizeof(Proto *) * p->sizep +
   1.316 +                             sizeof(TValue) * p->sizek + 
   1.317 +                             sizeof(int) * p->sizelineinfo +
   1.318 +                             sizeof(LocVar) * p->sizelocvars +
   1.319 +                             sizeof(TString *) * p->sizeupvalues;
   1.320 +    }
   1.321 +    default: lua_assert(0); return 0;
   1.322 +  }
   1.323 +}
   1.324 +
   1.325 +
   1.326 +static size_t propagateall (global_State *g) {
   1.327 +  size_t m = 0;
   1.328 +  while (g->gray) m += propagatemark(g);
   1.329 +  return m;
   1.330 +}
   1.331 +
   1.332 +
   1.333 +/*
   1.334 +** The next function tells whether a key or value can be cleared from
   1.335 +** a weak table. Non-collectable objects are never removed from weak
   1.336 +** tables. Strings behave as `values', so are never removed too. for
   1.337 +** other objects: if really collected, cannot keep them; for userdata
   1.338 +** being finalized, keep them in keys, but not in values
   1.339 +*/
   1.340 +static int iscleared (const TValue *o, int iskey) {
   1.341 +  if (!iscollectable(o)) return 0;
   1.342 +  if (ttisstring(o)) {
   1.343 +    stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
   1.344 +    return 0;
   1.345 +  }
   1.346 +  return iswhite(gcvalue(o)) ||
   1.347 +    (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
   1.348 +}
   1.349 +
   1.350 +
   1.351 +/*
   1.352 +** clear collected entries from weaktables
   1.353 +*/
   1.354 +static void cleartable (GCObject *l) {
   1.355 +  while (l) {
   1.356 +    Table *h = gco2h(l);
   1.357 +    int i = h->sizearray;
   1.358 +    lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
   1.359 +               testbit(h->marked, KEYWEAKBIT));
   1.360 +    if (testbit(h->marked, VALUEWEAKBIT)) {
   1.361 +      while (i--) {
   1.362 +        TValue *o = &h->array[i];
   1.363 +        if (iscleared(o, 0))  /* value was collected? */
   1.364 +          setnilvalue(o);  /* remove value */
   1.365 +      }
   1.366 +    }
   1.367 +    i = sizenode(h);
   1.368 +    while (i--) {
   1.369 +      Node *n = gnode(h, i);
   1.370 +      if (!ttisnil(gval(n)) &&  /* non-empty entry? */
   1.371 +          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
   1.372 +        setnilvalue(gval(n));  /* remove value ... */
   1.373 +        removeentry(n);  /* remove entry from table */
   1.374 +      }
   1.375 +    }
   1.376 +    l = h->gclist;
   1.377 +  }
   1.378 +}
   1.379 +
   1.380 +
   1.381 +static void freeobj (lua_State *L, GCObject *o) {
   1.382 +  switch (o->gch.tt) {
   1.383 +    case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
   1.384 +    case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
   1.385 +    case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
   1.386 +    case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
   1.387 +    case LUA_TTHREAD: {
   1.388 +      lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
   1.389 +      luaE_freethread(L, gco2th(o));
   1.390 +      break;
   1.391 +    }
   1.392 +    case LUA_TSTRING: {
   1.393 +      G(L)->strt.nuse--;
   1.394 +      luaM_freemem(L, o, sizestring(gco2ts(o)));
   1.395 +      break;
   1.396 +    }
   1.397 +    case LUA_TUSERDATA: {
   1.398 +      luaM_freemem(L, o, sizeudata(gco2u(o)));
   1.399 +      break;
   1.400 +    }
   1.401 +    default: lua_assert(0);
   1.402 +  }
   1.403 +}
   1.404 +
   1.405 +
   1.406 +
   1.407 +#define sweepwholelist(L,p)	sweeplist(L,p,MAX_LUMEM)
   1.408 +
   1.409 +
   1.410 +static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
   1.411 +  GCObject *curr;
   1.412 +  global_State *g = G(L);
   1.413 +  int deadmask = otherwhite(g);
   1.414 +  while ((curr = *p) != NULL && count-- > 0) {
   1.415 +    if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
   1.416 +      sweepwholelist(L, &gco2th(curr)->openupval);
   1.417 +    if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
   1.418 +      lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
   1.419 +      makewhite(g, curr);  /* make it white (for next cycle) */
   1.420 +      p = &curr->gch.next;
   1.421 +    }
   1.422 +    else {  /* must erase `curr' */
   1.423 +      lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
   1.424 +      *p = curr->gch.next;
   1.425 +      if (curr == g->rootgc)  /* is the first element of the list? */
   1.426 +        g->rootgc = curr->gch.next;  /* adjust first */
   1.427 +      freeobj(L, curr);
   1.428 +    }
   1.429 +  }
   1.430 +  return p;
   1.431 +}
   1.432 +
   1.433 +
   1.434 +static void checkSizes (lua_State *L) {
   1.435 +  global_State *g = G(L);
   1.436 +  /* check size of string hash */
   1.437 +  if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
   1.438 +      g->strt.size > MINSTRTABSIZE*2)
   1.439 +    luaS_resize(L, g->strt.size/2);  /* table is too big */
   1.440 +  /* check size of buffer */
   1.441 +  if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) {  /* buffer too big? */
   1.442 +    size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
   1.443 +    luaZ_resizebuffer(L, &g->buff, newsize);
   1.444 +  }
   1.445 +}
   1.446 +
   1.447 +
   1.448 +static void GCTM (lua_State *L) {
   1.449 +  global_State *g = G(L);
   1.450 +  GCObject *o = g->tmudata->gch.next;  /* get first element */
   1.451 +  Udata *udata = rawgco2u(o);
   1.452 +  const TValue *tm;
   1.453 +  /* remove udata from `tmudata' */
   1.454 +  if (o == g->tmudata)  /* last element? */
   1.455 +    g->tmudata = NULL;
   1.456 +  else
   1.457 +    g->tmudata->gch.next = udata->uv.next;
   1.458 +  udata->uv.next = g->mainthread->next;  /* return it to `root' list */
   1.459 +  g->mainthread->next = o;
   1.460 +  makewhite(g, o);
   1.461 +  tm = fasttm(L, udata->uv.metatable, TM_GC);
   1.462 +  if (tm != NULL) {
   1.463 +    lu_byte oldah = L->allowhook;
   1.464 +    lu_mem oldt = g->GCthreshold;
   1.465 +    L->allowhook = 0;  /* stop debug hooks during GC tag method */
   1.466 +    g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
   1.467 +    setobj2s(L, L->top, tm);
   1.468 +    setuvalue(L, L->top+1, udata);
   1.469 +    L->top += 2;
   1.470 +    luaD_call(L, L->top - 2, 0);
   1.471 +    L->allowhook = oldah;  /* restore hooks */
   1.472 +    g->GCthreshold = oldt;  /* restore threshold */
   1.473 +  }
   1.474 +}
   1.475 +
   1.476 +
   1.477 +/*
   1.478 +** Call all GC tag methods
   1.479 +*/
   1.480 +void luaC_callGCTM (lua_State *L) {
   1.481 +  while (G(L)->tmudata)
   1.482 +    GCTM(L);
   1.483 +}
   1.484 +
   1.485 +
   1.486 +void luaC_freeall (lua_State *L) {
   1.487 +  global_State *g = G(L);
   1.488 +  int i;
   1.489 +  g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
   1.490 +  sweepwholelist(L, &g->rootgc);
   1.491 +  for (i = 0; i < g->strt.size; i++)  /* free all string lists */
   1.492 +    sweepwholelist(L, &g->strt.hash[i]);
   1.493 +}
   1.494 +
   1.495 +
   1.496 +static void markmt (global_State *g) {
   1.497 +  int i;
   1.498 +  for (i=0; i<NUM_TAGS; i++)
   1.499 +    if (g->mt[i]) markobject(g, g->mt[i]);
   1.500 +}
   1.501 +
   1.502 +
   1.503 +/* mark root set */
   1.504 +static void markroot (lua_State *L) {
   1.505 +  global_State *g = G(L);
   1.506 +  g->gray = NULL;
   1.507 +  g->grayagain = NULL;
   1.508 +  g->weak = NULL;
   1.509 +  markobject(g, g->mainthread);
   1.510 +  /* make global table be traversed before main stack */
   1.511 +  markvalue(g, gt(g->mainthread));
   1.512 +  markvalue(g, registry(L));
   1.513 +  markmt(g);
   1.514 +  g->gcstate = GCSpropagate;
   1.515 +}
   1.516 +
   1.517 +
   1.518 +static void remarkupvals (global_State *g) {
   1.519 +  UpVal *uv;
   1.520 +  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
   1.521 +    lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
   1.522 +    if (isgray(obj2gco(uv)))
   1.523 +      markvalue(g, uv->v);
   1.524 +  }
   1.525 +}
   1.526 +
   1.527 +
   1.528 +static void atomic (lua_State *L) {
   1.529 +  global_State *g = G(L);
   1.530 +  size_t udsize;  /* total size of userdata to be finalized */
   1.531 +  /* remark occasional upvalues of (maybe) dead threads */
   1.532 +  remarkupvals(g);
   1.533 +  /* traverse objects cautch by write barrier and by 'remarkupvals' */
   1.534 +  propagateall(g);
   1.535 +  /* remark weak tables */
   1.536 +  g->gray = g->weak;
   1.537 +  g->weak = NULL;
   1.538 +  lua_assert(!iswhite(obj2gco(g->mainthread)));
   1.539 +  markobject(g, L);  /* mark running thread */
   1.540 +  markmt(g);  /* mark basic metatables (again) */
   1.541 +  propagateall(g);
   1.542 +  /* remark gray again */
   1.543 +  g->gray = g->grayagain;
   1.544 +  g->grayagain = NULL;
   1.545 +  propagateall(g);
   1.546 +  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
   1.547 +  marktmu(g);  /* mark `preserved' userdata */
   1.548 +  udsize += propagateall(g);  /* remark, to propagate `preserveness' */
   1.549 +  cleartable(g->weak);  /* remove collected objects from weak tables */
   1.550 +  /* flip current white */
   1.551 +  g->currentwhite = cast_byte(otherwhite(g));
   1.552 +  g->sweepstrgc = 0;
   1.553 +  g->sweepgc = &g->rootgc;
   1.554 +  g->gcstate = GCSsweepstring;
   1.555 +  g->estimate = g->totalbytes - udsize;  /* first estimate */
   1.556 +}
   1.557 +
   1.558 +
   1.559 +static l_mem singlestep (lua_State *L) {
   1.560 +  global_State *g = G(L);
   1.561 +  /*lua_checkmemory(L);*/
   1.562 +  switch (g->gcstate) {
   1.563 +    case GCSpause: {
   1.564 +      markroot(L);  /* start a new collection */
   1.565 +      return 0;
   1.566 +    }
   1.567 +    case GCSpropagate: {
   1.568 +      if (g->gray)
   1.569 +        return propagatemark(g);
   1.570 +      else {  /* no more `gray' objects */
   1.571 +        atomic(L);  /* finish mark phase */
   1.572 +        return 0;
   1.573 +      }
   1.574 +    }
   1.575 +    case GCSsweepstring: {
   1.576 +      lu_mem old = g->totalbytes;
   1.577 +      sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
   1.578 +      if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
   1.579 +        g->gcstate = GCSsweep;  /* end sweep-string phase */
   1.580 +      lua_assert(old >= g->totalbytes);
   1.581 +      g->estimate -= old - g->totalbytes;
   1.582 +      return GCSWEEPCOST;
   1.583 +    }
   1.584 +    case GCSsweep: {
   1.585 +      lu_mem old = g->totalbytes;
   1.586 +      g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
   1.587 +      if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
   1.588 +        checkSizes(L);
   1.589 +        g->gcstate = GCSfinalize;  /* end sweep phase */
   1.590 +      }
   1.591 +      lua_assert(old >= g->totalbytes);
   1.592 +      g->estimate -= old - g->totalbytes;
   1.593 +      return GCSWEEPMAX*GCSWEEPCOST;
   1.594 +    }
   1.595 +    case GCSfinalize: {
   1.596 +      if (g->tmudata) {
   1.597 +        GCTM(L);
   1.598 +        if (g->estimate > GCFINALIZECOST)
   1.599 +          g->estimate -= GCFINALIZECOST;
   1.600 +        return GCFINALIZECOST;
   1.601 +      }
   1.602 +      else {
   1.603 +        g->gcstate = GCSpause;  /* end collection */
   1.604 +        g->gcdept = 0;
   1.605 +        return 0;
   1.606 +      }
   1.607 +    }
   1.608 +    default: lua_assert(0); return 0;
   1.609 +  }
   1.610 +}
   1.611 +
   1.612 +
   1.613 +void luaC_step (lua_State *L) {
   1.614 +  global_State *g = G(L);
   1.615 +  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
   1.616 +  if (lim == 0)
   1.617 +    lim = (MAX_LUMEM-1)/2;  /* no limit */
   1.618 +  g->gcdept += g->totalbytes - g->GCthreshold;
   1.619 +  do {
   1.620 +    lim -= singlestep(L);
   1.621 +    if (g->gcstate == GCSpause)
   1.622 +      break;
   1.623 +  } while (lim > 0);
   1.624 +  if (g->gcstate != GCSpause) {
   1.625 +    if (g->gcdept < GCSTEPSIZE)
   1.626 +      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
   1.627 +    else {
   1.628 +      g->gcdept -= GCSTEPSIZE;
   1.629 +      g->GCthreshold = g->totalbytes;
   1.630 +    }
   1.631 +  }
   1.632 +  else {
   1.633 +    lua_assert(g->totalbytes >= g->estimate);
   1.634 +    setthreshold(g);
   1.635 +  }
   1.636 +}
   1.637 +
   1.638 +
   1.639 +void luaC_fullgc (lua_State *L) {
   1.640 +  global_State *g = G(L);
   1.641 +  if (g->gcstate <= GCSpropagate) {
   1.642 +    /* reset sweep marks to sweep all elements (returning them to white) */
   1.643 +    g->sweepstrgc = 0;
   1.644 +    g->sweepgc = &g->rootgc;
   1.645 +    /* reset other collector lists */
   1.646 +    g->gray = NULL;
   1.647 +    g->grayagain = NULL;
   1.648 +    g->weak = NULL;
   1.649 +    g->gcstate = GCSsweepstring;
   1.650 +  }
   1.651 +  lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
   1.652 +  /* finish any pending sweep phase */
   1.653 +  while (g->gcstate != GCSfinalize) {
   1.654 +    lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
   1.655 +    singlestep(L);
   1.656 +  }
   1.657 +  markroot(L);
   1.658 +  while (g->gcstate != GCSpause) {
   1.659 +    singlestep(L);
   1.660 +  }
   1.661 +  setthreshold(g);
   1.662 +}
   1.663 +
   1.664 +
   1.665 +void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
   1.666 +  global_State *g = G(L);
   1.667 +  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
   1.668 +  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
   1.669 +  lua_assert(ttype(&o->gch) != LUA_TTABLE);
   1.670 +  /* must keep invariant? */
   1.671 +  if (g->gcstate == GCSpropagate)
   1.672 +    reallymarkobject(g, v);  /* restore invariant */
   1.673 +  else  /* don't mind */
   1.674 +    makewhite(g, o);  /* mark as white just to avoid other barriers */
   1.675 +}
   1.676 +
   1.677 +
   1.678 +void luaC_barrierback (lua_State *L, Table *t) {
   1.679 +  global_State *g = G(L);
   1.680 +  GCObject *o = obj2gco(t);
   1.681 +  lua_assert(isblack(o) && !isdead(g, o));
   1.682 +  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
   1.683 +  black2gray(o);  /* make table gray (again) */
   1.684 +  t->gclist = g->grayagain;
   1.685 +  g->grayagain = o;
   1.686 +}
   1.687 +
   1.688 +
   1.689 +void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
   1.690 +  global_State *g = G(L);
   1.691 +  o->gch.next = g->rootgc;
   1.692 +  g->rootgc = o;
   1.693 +  o->gch.marked = luaC_white(g);
   1.694 +  o->gch.tt = tt;
   1.695 +}
   1.696 +
   1.697 +
   1.698 +void luaC_linkupval (lua_State *L, UpVal *uv) {
   1.699 +  global_State *g = G(L);
   1.700 +  GCObject *o = obj2gco(uv);
   1.701 +  o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
   1.702 +  g->rootgc = o;
   1.703 +  if (isgray(o)) { 
   1.704 +    if (g->gcstate == GCSpropagate) {
   1.705 +      gray2black(o);  /* closed upvalues need barrier */
   1.706 +      luaC_barrier(L, uv, uv->v);
   1.707 +    }
   1.708 +    else {  /* sweep phase: sweep it (turning it into white) */
   1.709 +      makewhite(g, o);
   1.710 +      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
   1.711 +    }
   1.712 +  }
   1.713 +}
   1.714 +