/*** $Id: lgc.c,v 2.133 2012/05/31 21:28:59 roberto Exp $** Garbage Collector** See Copyright Notice in lua.h*/ #include <string.h> #define lgc_c#define LUA_CORE #include "lua.h" #include "ldebug.h"#include "ldo.h"#include "lfunc.h"#include "lgc.h"#include "lmem.h"#include "lobject.h"#include "lstate.h"#include "lstring.h"#include "ltable.h"#include "ltm.h"   /*** cost of sweeping one element (the size of a small object divided** by some adjust for the sweep speed)*/#define GCSWEEPCOST	((sizeof(TString) + 4) / 4) /* maximum number of elements to sweep in each single step */#define GCSWEEPMAX	(cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4)) /* maximum number of finalizers to call in each GC step */#define GCFINALIZENUM	4  /*** macro to adjust 'stepmul': 'stepmul' is actually used like** 'stepmul / STEPMULADJ' (value chosen by tests)*/#define STEPMULADJ		200 /*** macro to adjust 'pause': 'pause' is actually used like** 'pause / PAUSEADJ' (value chosen by tests)*/#define PAUSEADJ		200    /*** standard negative debt for GC; a reasonable "time" to wait before** starting a new cycle*/#define stddebtest(g,e)	(-cast(l_mem, (e)/PAUSEADJ) * g->gcpause)#define stddebt(g)	stddebtest(g, gettotalbytes(g))  /*** 'makewhite' erases all color bits plus the old bit and then** sets only the current white bit*/#define maskcolors	(~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS))#define makewhite(g,x)	\ (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g))) #define white2gray(x)	resetbits(gch(x)->marked, WHITEBITS)#define black2gray(x)	resetbit(gch(x)->marked, BLACKBIT)  #define isfinalized(x)		testbit(gch(x)->marked, FINALIZEDBIT) #define checkdeadkey(n)	lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n)))  #define checkconsistency(obj)  \  lua_longassert(!iscollectable(obj) || righttt(obj))  #define markvalue(g,o) { checkconsistency(o); \  if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); } #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \		reallymarkobject(g, obj2gco(t)); } static void reallymarkobject (global_State *g, GCObject *o);  /*** {======================================================** Generic functions** =======================================================*/  /*** one after last element in a hash array*/#define gnodelast(h)	gnode(h, cast(size_t, sizenode(h)))  /*** link table 'h' into list pointed by 'p'*/#define linktable(h,p)	((h)->gclist = *(p), *(p) = obj2gco(h))  /*** if key is not marked, mark its entry as dead (therefore removing it** from the table)*/static void removeentry (Node *n) {  lua_assert(ttisnil(gval(n)));  if (valiswhite(gkey(n)))    setdeadvalue(gkey(n));  /* unused and unmarked key; remove it */}  /*** tells whether a key or value can be cleared from a weak** table. Non-collectable objects are never removed from weak** tables. Strings behave as `values', so are never removed too. for** other objects: if really collected, cannot keep them; for objects** being finalized, keep them in keys, but not in values*/static int iscleared (global_State *g, const TValue *o) {  if (!iscollectable(o)) return 0;  else if (ttisstring(o)) {    markobject(g, rawtsvalue(o));  /* strings are `values', so are never weak */    return 0;  }  else return iswhite(gcvalue(o));}  /*** barrier that moves collector forward, that is, mark the white object** being pointed by a black object.*/void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {  global_State *g = G(L);  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));  lua_assert(isgenerational(g) || g->gcstate != GCSpause);  lua_assert(gch(o)->tt != LUA_TTABLE);  if (keepinvariant(g))  /* must keep invariant? */    reallymarkobject(g, v);  /* restore invariant */  else {  /* sweep phase */    lua_assert(issweepphase(g));    makewhite(g, o);  /* mark main obj. as white to avoid other barriers */  }}  /*** barrier that moves collector backward, that is, mark the black object** pointing to a white object as gray again. (Current implementation** only works for tables; access to 'gclist' is not uniform across** different types.)*/void luaC_barrierback_ (lua_State *L, GCObject *o) {  global_State *g = G(L);  lua_assert(isblack(o) && !isdead(g, o) && gch(o)->tt == LUA_TTABLE);  black2gray(o);  /* make object gray (again) */  gco2t(o)->gclist = g->grayagain;  g->grayagain = o;}  /*** barrier for prototypes. When creating first closure (cache is** NULL), use a forward barrier; this may be the only closure of the** prototype (if it is a "regular" function, with a single instance)** and the prototype may be big, so it is better to avoid traversing** it again. Otherwise, use a backward barrier, to avoid marking all** possible instances.*/LUAI_FUNC void luaC_barrierproto_ (lua_State *L, Proto *p, Closure *c) {  global_State *g = G(L);  lua_assert(isblack(obj2gco(p)));  if (p->cache == NULL) {  /* first time? */    luaC_objbarrier(L, p, c);  }  else {  /* use a backward barrier */    black2gray(obj2gco(p));  /* make prototype gray (again) */    p->gclist = g->grayagain;    g->grayagain = obj2gco(p);  }}  /*** check color (and invariants) for an upvalue that was closed,** i.e., moved into the 'allgc' list*/void luaC_checkupvalcolor (global_State *g, UpVal *uv) {  GCObject *o = obj2gco(uv);  lua_assert(!isblack(o));  /* open upvalues are never black */  if (isgray(o)) {    if (keepinvariant(g)) {      resetoldbit(o);  /* see MOVE OLD rule */      gray2black(o);  /* it is being visited now */      markvalue(g, uv->v);    }    else {      lua_assert(issweepphase(g));      makewhite(g, o);    }  }}  /*** create a new collectable object (with given type and size) and link** it to '*list'. 'offset' tells how many bytes to allocate before the** object itself (used only by states).*/GCObject *luaC_newobj (lua_State *L, int tt, size_t sz, GCObject **list,                       int offset) {  global_State *g = G(L);  char *raw = cast(char *, luaM_newobject(L, novariant(tt), sz));  GCObject *o = obj2gco(raw + offset);  if (list == NULL)    list = &g->allgc;  /* standard list for collectable objects */  gch(o)->marked = luaC_white(g);  gch(o)->tt = tt;  gch(o)->next = *list;  *list = o;  return o;} /* }====================================================== */   /*** {======================================================** Mark functions** =======================================================*/  /*** mark an object. Userdata, strings, and closed upvalues are visited** and turned black here. Other objects are marked gray and added** to appropriate list to be visited (and turned black) later. (Open** upvalues are already linked in 'headuv' list.)*/static void reallymarkobject (global_State *g, GCObject *o) {  lu_mem size;  white2gray(o);  switch (gch(o)->tt) {    case LUA_TSHRSTR:    case LUA_TLNGSTR: {      size = sizestring(gco2ts(o));      break;  /* nothing else to mark; make it black */    }    case LUA_TUSERDATA: {      Table *mt = gco2u(o)->metatable;      markobject(g, mt);      markobject(g, gco2u(o)->env);      size = sizeudata(gco2u(o));      break;    }    case LUA_TUPVAL: {      UpVal *uv = gco2uv(o);      markvalue(g, uv->v);      if (uv->v != &uv->u.value)  /* open? */        return;  /* open upvalues remain gray */      size = sizeof(UpVal);      break;    }    case LUA_TLCL: {      gco2lcl(o)->gclist = g->gray;      g->gray = o;      return;    }    case LUA_TCCL: {      gco2ccl(o)->gclist = g->gray;      g->gray = o;      return;    }    case LUA_TTABLE: {      linktable(gco2t(o), &g->gray);      return;    }    case LUA_TTHREAD: {      gco2th(o)->gclist = g->gray;      g->gray = o;      return;    }    case LUA_TPROTO: {      gco2p(o)->gclist = g->gray;      g->gray = o;      return;    }    default: lua_assert(0); return;  }  gray2black(o);  g->GCmemtrav += size;}  /*** mark metamethods for basic types*/static void markmt (global_State *g) {  int i;  for (i=0; i < LUA_NUMTAGS; i++)    markobject(g, g->mt[i]);}  /*** mark all objects in list of being-finalized*/static void markbeingfnz (global_State *g) {  GCObject *o;  for (o = g->tobefnz; o != NULL; o = gch(o)->next) {    makewhite(g, o);    reallymarkobject(g, o);  }}  /*** mark all values stored in marked open upvalues. (See comment in** 'lstate.h'.)*/static void remarkupvals (global_State *g) {  UpVal *uv;  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {    if (isgray(obj2gco(uv)))      markvalue(g, uv->v);  }}  /*** mark root set and reset all gray lists, to start a new** incremental (or full) collection*/static void markroot (global_State *g) {  g->gray = g->grayagain = NULL;  g->weak = g->allweak = g->ephemeron = NULL;  markobject(g, g->mainthread);  markvalue(g, &g->l_registry);  markmt(g);  markbeingfnz(g);  /* mark any finalizing object left from previous cycle */} /* }====================================================== */  /*** {======================================================** Traverse functions** =======================================================*/ static void traverseweakvalue (global_State *g, Table *h) {  Node *n, *limit = gnodelast(h);  /* if there is array part, assume it may have white values (do not     traverse it just to check) */  int hasclears = (h->sizearray > 0);  for (n = gnode(h, 0); n < limit; n++) {    checkdeadkey(n);    if (ttisnil(gval(n)))  /* entry is empty? */      removeentry(n);  /* remove it */    else {      lua_assert(!ttisnil(gkey(n)));      markvalue(g, gkey(n));  /* mark key */      if (!hasclears && iscleared(g, gval(n)))  /* is there a white value? */        hasclears = 1;  /* table will have to be cleared */    }  }  if (hasclears)    linktable(h, &g->weak);  /* has to be cleared later */  else  /* no white values */    linktable(h, &g->grayagain);  /* no need to clean */}  static int traverseephemeron (global_State *g, Table *h) {  int marked = 0;  /* true if an object is marked in this traversal */  int hasclears = 0;  /* true if table has white keys */  int prop = 0;  /* true if table has entry "white-key -> white-value" */  Node *n, *limit = gnodelast(h);  int i;  /* traverse array part (numeric keys are 'strong') */  for (i = 0; i < h->sizearray; i++) {    if (valiswhite(&h->array[i])) {      marked = 1;      reallymarkobject(g, gcvalue(&h->array[i]));    }  }  /* traverse hash part */  for (n = gnode(h, 0); n < limit; n++) {    checkdeadkey(n);    if (ttisnil(gval(n)))  /* entry is empty? */      removeentry(n);  /* remove it */    else if (iscleared(g, gkey(n))) {  /* key is not marked (yet)? */      hasclears = 1;  /* table must be cleared */      if (valiswhite(gval(n)))  /* value not marked yet? */        prop = 1;  /* must propagate again */    }    else if (valiswhite(gval(n))) {  /* value not marked yet? */      marked = 1;      reallymarkobject(g, gcvalue(gval(n)));  /* mark it now */    }  }  if (prop)    linktable(h, &g->ephemeron);  /* have to propagate again */  else if (hasclears)  /* does table have white keys? */    linktable(h, &g->allweak);  /* may have to clean white keys */  else  /* no white keys */    linktable(h, &g->grayagain);  /* no need to clean */  return marked;}  static void traversestrongtable (global_State *g, Table *h) {  Node *n, *limit = gnodelast(h);  int i;  for (i = 0; i < h->sizearray; i++)  /* traverse array part */    markvalue(g, &h->array[i]);  for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */    checkdeadkey(n);    if (ttisnil(gval(n)))  /* entry is empty? */      removeentry(n);  /* remove it */    else {      lua_assert(!ttisnil(gkey(n)));      markvalue(g, gkey(n));  /* mark key */      markvalue(g, gval(n));  /* mark value */    }  }}  static lu_mem traversetable (global_State *g, Table *h) {  const char *weakkey, *weakvalue;  const TValue *mode = gfasttm(g, h->metatable, TM_MODE);  markobject(g, h->metatable);  if (mode && ttisstring(mode) &&  /* is there a weak mode? */      ((weakkey = strchr(svalue(mode), 'k')),       (weakvalue = strchr(svalue(mode), 'v')),       (weakkey || weakvalue))) {  /* is really weak? */    black2gray(obj2gco(h));  /* keep table gray */    if (!weakkey)  /* strong keys? */      traverseweakvalue(g, h);    else if (!weakvalue)  /* strong values? */      traverseephemeron(g, h);    else  /* all weak */      linktable(h, &g->allweak);  /* nothing to traverse now */  }  else  /* not weak */    traversestrongtable(g, h);  return sizeof(Table) + sizeof(TValue) * h->sizearray +                         sizeof(Node) * sizenode(h);}  static int traverseproto (global_State *g, Proto *f) {  int i;  if (f->cache && iswhite(obj2gco(f->cache)))    f->cache = NULL;  /* allow cache to be collected */  markobject(g, f->source);  for (i = 0; i < f->sizek; i++)  /* mark literals */    markvalue(g, &f->k[i]);  for (i = 0; i < f->sizeupvalues; i++)  /* mark upvalue names */    markobject(g, f->upvalues[i].name);  for (i = 0; i < f->sizep; i++)  /* mark nested protos */    markobject(g, f->p[i]);  for (i = 0; i < f->sizelocvars; i++)  /* mark local-variable names */    markobject(g, f->locvars[i].varname);  return sizeof(Proto) + sizeof(Instruction) * f->sizecode +                         sizeof(Proto *) * f->sizep +                         sizeof(TValue) * f->sizek +                         sizeof(int) * f->sizelineinfo +                         sizeof(LocVar) * f->sizelocvars +                         sizeof(Upvaldesc) * f->sizeupvalues;}  static lu_mem traverseCclosure (global_State *g, CClosure *cl) {  int i;  for (i = 0; i < cl->nupvalues; i++)  /* mark its upvalues */    markvalue(g, &cl->upvalue[i]);  return sizeCclosure(cl->nupvalues);} static lu_mem traverseLclosure (global_State *g, LClosure *cl) {  int i;  markobject(g, cl->p);  /* mark its prototype */  for (i = 0; i < cl->nupvalues; i++)  /* mark its upvalues */    markobject(g, cl->upvals[i]);  return sizeLclosure(cl->nupvalues);

Lines 1–500 of 1205. Load more