rpm
4.5
|
00001 /* 00002 ** $Id: lgc.c,v 1.2 2004/03/19 21:14:32 niemeyer Exp $ 00003 ** Garbage Collector 00004 ** See Copyright Notice in lua.h 00005 */ 00006 00007 #include <string.h> 00008 00009 #define lgc_c 00010 00011 #include "lua.h" 00012 00013 #include "ldebug.h" 00014 #include "ldo.h" 00015 #include "lfunc.h" 00016 #include "lgc.h" 00017 #include "lmem.h" 00018 #include "lobject.h" 00019 #include "lstate.h" 00020 #include "lstring.h" 00021 #include "ltable.h" 00022 #include "ltm.h" 00023 00024 00025 typedef struct GCState { 00026 /*@null@*/ 00027 GCObject *tmark; /* list of marked objects to be traversed */ 00028 /*@null@*/ 00029 GCObject *wk; /* list of traversed key-weak tables (to be cleared) */ 00030 /*@null@*/ 00031 GCObject *wv; /* list of traversed value-weak tables */ 00032 /*@null@*/ 00033 GCObject *wkv; /* list of traversed key-value weak tables */ 00034 /*@null@*/ 00035 global_State *g; 00036 } GCState; 00037 00038 00039 /* 00040 ** some userful bit tricks 00041 */ 00042 #define setbit(x,b) ((x) |= (1<<(b))) 00043 #define resetbit(x,b) ((x) &= cast(lu_byte, ~(1<<(b)))) 00044 #define testbit(x,b) ((x) & (1<<(b))) 00045 00046 #define unmark(x) resetbit((x)->gch.marked, 0) 00047 #define ismarked(x) ((x)->gch.marked & ((1<<4)|1)) 00048 00049 #define stringmark(s) setbit((s)->tsv.marked, 0) 00050 00051 00052 #define isfinalized(u) (!testbit((u)->uv.marked, 1)) 00053 #define markfinalized(u) resetbit((u)->uv.marked, 1) 00054 00055 00056 #define KEYWEAKBIT 1 00057 #define VALUEWEAKBIT 2 00058 #define KEYWEAK (1<<KEYWEAKBIT) 00059 #define VALUEWEAK (1<<VALUEWEAKBIT) 00060 00061 00062 00063 #define markobject(st,o) { checkconsistency(o); \ 00064 if (iscollectable(o) && !ismarked(gcvalue(o))) reallymarkobject(st,gcvalue(o)); } 00065 00066 #define condmarkobject(st,o,c) { checkconsistency(o); \ 00067 if (iscollectable(o) && !ismarked(gcvalue(o)) && (c)) \ 00068 reallymarkobject(st,gcvalue(o)); } 00069 00070 #define markvalue(st,t) { if (!ismarked(valtogco(t))) \ 00071 reallymarkobject(st, valtogco(t)); } 00072 00073 00074 00075 static void reallymarkobject (GCState *st, GCObject *o) 00076 /*@modifies st, o @*/ 00077 { 00078 lua_assert(!ismarked(o)); 00079 setbit(o->gch.marked, 0); /* mark object */ 00080 switch (o->gch.tt) { 00081 case LUA_TUSERDATA: { 00082 markvalue(st, gcotou(o)->uv.metatable); 00083 break; 00084 } 00085 case LUA_TFUNCTION: { 00086 gcotocl(o)->c.gclist = st->tmark; 00087 st->tmark = o; 00088 break; 00089 } 00090 case LUA_TTABLE: { 00091 gcotoh(o)->gclist = st->tmark; 00092 st->tmark = o; 00093 break; 00094 } 00095 case LUA_TTHREAD: { 00096 /*@-onlytrans@*/ 00097 gcototh(o)->gclist = st->tmark; 00098 /*@=onlytrans@*/ 00099 st->tmark = o; 00100 break; 00101 } 00102 case LUA_TPROTO: { 00103 gcotop(o)->gclist = st->tmark; 00104 st->tmark = o; 00105 break; 00106 } 00107 default: lua_assert(o->gch.tt == LUA_TSTRING); 00108 } 00109 } 00110 00111 00112 static void marktmu (GCState *st) 00113 /*@modifies st @*/ 00114 { 00115 GCObject *u; 00116 for (u = st->g->tmudata; u; u = u->gch.next) { 00117 unmark(u); /* may be marked, if left from previous GC */ 00118 reallymarkobject(st, u); 00119 } 00120 } 00121 00122 00123 /* move `dead' udata that need finalization to list `tmudata' */ 00124 size_t luaC_separateudata (lua_State *L) { 00125 size_t deadmem = 0; 00126 GCObject **p = &G(L)->rootudata; 00127 GCObject *curr; 00128 GCObject *collected = NULL; /* to collect udata with gc event */ 00129 GCObject **lastcollected = &collected; 00130 while ((curr = *p) != NULL) { 00131 lua_assert(curr->gch.tt == LUA_TUSERDATA); 00132 if (ismarked(curr) || isfinalized(gcotou(curr))) 00133 p = &curr->gch.next; /* don't bother with them */ 00134 00135 else if (fasttm(L, gcotou(curr)->uv.metatable, TM_GC) == NULL) { 00136 markfinalized(gcotou(curr)); /* don't need finalization */ 00137 p = &curr->gch.next; 00138 } 00139 else { /* must call its gc method */ 00140 deadmem += sizeudata(gcotou(curr)->uv.len); 00141 *p = curr->gch.next; 00142 curr->gch.next = NULL; /* link `curr' at the end of `collected' list */ 00143 *lastcollected = curr; 00144 lastcollected = &curr->gch.next; 00145 } 00146 } 00147 /* insert collected udata with gc event into `tmudata' list */ 00148 /*@-dependenttrans@*/ 00149 *lastcollected = G(L)->tmudata; 00150 /*@=dependenttrans@*/ 00151 G(L)->tmudata = collected; 00152 return deadmem; 00153 } 00154 00155 00156 static void removekey (Node *n) 00157 /*@modifies n @*/ 00158 { 00159 setnilvalue(gval(n)); /* remove corresponding value ... */ 00160 if (iscollectable(gkey(n))) 00161 setttype(gkey(n), LUA_TNONE); /* dead key; remove it */ 00162 } 00163 00164 00165 static void traversetable (GCState *st, Table *h) 00166 /*@modifies st, h @*/ 00167 { 00168 int i; 00169 int weakkey = 0; 00170 int weakvalue = 0; 00171 const TObject *mode; 00172 markvalue(st, h->metatable); 00173 lua_assert(h->lsizenode || h->node == st->g->dummynode); 00174 mode = gfasttm(st->g, h->metatable, TM_MODE); 00175 if (mode && ttisstring(mode)) { /* is there a weak mode? */ 00176 weakkey = (strchr(svalue(mode), 'k') != NULL); 00177 weakvalue = (strchr(svalue(mode), 'v') != NULL); 00178 if (weakkey || weakvalue) { /* is really weak? */ 00179 GCObject **weaklist; 00180 h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */ 00181 h->marked |= cast(lu_byte, (weakkey << KEYWEAKBIT) | 00182 (weakvalue << VALUEWEAKBIT)); 00183 weaklist = (weakkey && weakvalue) ? &st->wkv : 00184 (weakkey) ? &st->wk : 00185 &st->wv; 00186 h->gclist = *weaklist; /* must be cleared after GC, ... */ 00187 *weaklist = valtogco(h); /* ... so put in the appropriate list */ 00188 } 00189 } 00190 if (!weakvalue) { 00191 i = h->sizearray; 00192 while (i--) 00193 markobject(st, &h->array[i]); 00194 } 00195 i = sizenode(h); 00196 while (i--) { 00197 Node *n = gnode(h, i); 00198 if (!ttisnil(gval(n))) { 00199 lua_assert(!ttisnil(gkey(n))); 00200 condmarkobject(st, gkey(n), !weakkey); 00201 condmarkobject(st, gval(n), !weakvalue); 00202 } 00203 } 00204 } 00205 00206 00207 static void traverseproto (GCState *st, Proto *f) 00208 /*@modifies st, f @*/ 00209 { 00210 int i; 00211 stringmark(f->source); 00212 for (i=0; i<f->sizek; i++) { /* mark literal strings */ 00213 if (ttisstring(f->k+i)) 00214 stringmark(tsvalue(f->k+i)); 00215 } 00216 for (i=0; i<f->sizeupvalues; i++) /* mark upvalue names */ 00217 stringmark(f->upvalues[i]); 00218 for (i=0; i<f->sizep; i++) /* mark nested protos */ 00219 markvalue(st, f->p[i]); 00220 for (i=0; i<f->sizelocvars; i++) /* mark local-variable names */ 00221 stringmark(f->locvars[i].varname); 00222 lua_assert(luaG_checkcode(f)); 00223 } 00224 00225 00226 00227 static void traverseclosure (GCState *st, Closure *cl) 00228 /*@modifies st, cl @*/ 00229 { 00230 if (cl->c.isC) { 00231 int i; 00232 for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */ 00233 markobject(st, &cl->c.upvalue[i]); 00234 } 00235 else { 00236 int i; 00237 lua_assert(cl->l.nupvalues == cl->l.p->nups); 00238 markvalue(st, hvalue(&cl->l.g)); 00239 markvalue(st, cl->l.p); 00240 for (i=0; i<cl->l.nupvalues; i++) { /* mark its upvalues */ 00241 UpVal *u = cl->l.upvals[i]; 00242 if (!u->marked) { 00243 markobject(st, &u->value); 00244 u->marked = 1; 00245 } 00246 } 00247 } 00248 } 00249 00250 00251 static void checkstacksizes (lua_State *L, StkId max) 00252 /*@modifies L @*/ 00253 { 00254 int used = L->ci - L->base_ci; /* number of `ci' in use */ 00255 if (4*used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci) 00256 luaD_reallocCI(L, L->size_ci/2); /* still big enough... */ 00257 else condhardstacktests(luaD_reallocCI(L, L->size_ci)); 00258 used = max - L->stack; /* part of stack in use */ 00259 if (4*used < L->stacksize && 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize) 00260 luaD_reallocstack(L, L->stacksize/2); /* still big enough... */ 00261 else condhardstacktests(luaD_reallocstack(L, L->stacksize)); 00262 } 00263 00264 00265 static void traversestack (GCState *st, lua_State *L1) 00266 /*@modifies st, L1 @*/ 00267 { 00268 StkId o, lim; 00269 CallInfo *ci; 00270 markobject(st, gt(L1)); 00271 lim = L1->top; 00272 for (ci = L1->base_ci; ci <= L1->ci; ci++) { 00273 lua_assert(ci->top <= L1->stack_last); 00274 lua_assert(ci->state & (CI_C | CI_HASFRAME | CI_SAVEDPC)); 00275 if (lim < ci->top) 00276 lim = ci->top; 00277 } 00278 for (o = L1->stack; o < L1->top; o++) 00279 markobject(st, o); 00280 for (; o <= lim; o++) 00281 setnilvalue(o); 00282 checkstacksizes(L1, lim); 00283 } 00284 00285 00286 static void propagatemarks (GCState *st) 00287 /*@modifies st @*/ 00288 { 00289 while (st->tmark) { /* traverse marked objects */ 00290 switch (st->tmark->gch.tt) { 00291 case LUA_TTABLE: { 00292 Table *h = gcotoh(st->tmark); 00293 st->tmark = h->gclist; 00294 traversetable(st, h); 00295 break; 00296 } 00297 case LUA_TFUNCTION: { 00298 Closure *cl = gcotocl(st->tmark); 00299 st->tmark = cl->c.gclist; 00300 traverseclosure(st, cl); 00301 break; 00302 } 00303 case LUA_TTHREAD: { 00304 lua_State *th = gcototh(st->tmark); 00305 /*@-dependenttrans@*/ 00306 st->tmark = th->gclist; 00307 /*@=dependenttrans@*/ 00308 traversestack(st, th); 00309 break; 00310 } 00311 case LUA_TPROTO: { 00312 Proto *p = gcotop(st->tmark); 00313 st->tmark = p->gclist; 00314 traverseproto(st, p); 00315 break; 00316 } 00317 default: lua_assert(0); 00318 } 00319 } 00320 } 00321 00322 00323 static int valismarked (const TObject *o) 00324 /*@modifies o @*/ 00325 { 00326 if (ttisstring(o)) 00327 stringmark(tsvalue(o)); /* strings are `values', so are never weak */ 00328 return !iscollectable(o) || testbit(o->value.gc->gch.marked, 0); 00329 } 00330 00331 00332 /* 00333 ** clear collected keys from weaktables 00334 */ 00335 static void cleartablekeys (/*@null@*/ GCObject *l) 00336 /*@modifies l @*/ 00337 { 00338 while (l) { 00339 Table *h = gcotoh(l); 00340 int i = sizenode(h); 00341 lua_assert(h->marked & KEYWEAK); 00342 while (i--) { 00343 Node *n = gnode(h, i); 00344 if (!valismarked(gkey(n))) /* key was collected? */ 00345 removekey(n); /* remove entry from table */ 00346 } 00347 l = h->gclist; 00348 } 00349 } 00350 00351 00352 /* 00353 ** clear collected values from weaktables 00354 */ 00355 static void cleartablevalues (/*@null@*/ GCObject *l) 00356 /*@modifies l @*/ 00357 { 00358 while (l) { 00359 Table *h = gcotoh(l); 00360 int i = h->sizearray; 00361 lua_assert(h->marked & VALUEWEAK); 00362 while (i--) { 00363 TObject *o = &h->array[i]; 00364 if (!valismarked(o)) /* value was collected? */ 00365 setnilvalue(o); /* remove value */ 00366 } 00367 i = sizenode(h); 00368 while (i--) { 00369 Node *n = gnode(h, i); 00370 if (!valismarked(gval(n))) /* value was collected? */ 00371 removekey(n); /* remove entry from table */ 00372 } 00373 l = h->gclist; 00374 } 00375 } 00376 00377 00378 static void freeobj (lua_State *L, GCObject *o) 00379 /*@modifies L, o @*/ 00380 { 00381 switch (o->gch.tt) { 00382 case LUA_TPROTO: luaF_freeproto(L, gcotop(o)); break; 00383 case LUA_TFUNCTION: luaF_freeclosure(L, gcotocl(o)); break; 00384 case LUA_TUPVAL: luaM_freelem(L, gcotouv(o)); break; 00385 case LUA_TTABLE: luaH_free(L, gcotoh(o)); break; 00386 case LUA_TTHREAD: { 00387 lua_assert(gcototh(o) != L && gcototh(o) != G(L)->mainthread); 00388 luaE_freethread(L, gcototh(o)); 00389 break; 00390 } 00391 case LUA_TSTRING: { 00392 luaM_free(L, o, sizestring(gcotots(o)->tsv.len)); 00393 break; 00394 } 00395 case LUA_TUSERDATA: { 00396 luaM_free(L, o, sizeudata(gcotou(o)->uv.len)); 00397 break; 00398 } 00399 default: lua_assert(0); 00400 } 00401 } 00402 00403 00404 static int sweeplist (lua_State *L, GCObject **p, int limit) 00405 /*@modifies L, *p @*/ 00406 { 00407 GCObject *curr; 00408 int count = 0; /* number of collected items */ 00409 while ((curr = *p) != NULL) { 00410 if (curr->gch.marked > limit) { 00411 unmark(curr); 00412 p = &curr->gch.next; 00413 } 00414 else { 00415 count++; 00416 /*@-dependenttrans@*/ 00417 *p = curr->gch.next; 00418 /*@=dependenttrans@*/ 00419 freeobj(L, curr); 00420 } 00421 } 00422 return count; 00423 } 00424 00425 00426 static void sweepstrings (lua_State *L, int all) 00427 /*@modifies L @*/ 00428 { 00429 int i; 00430 for (i=0; i<G(L)->strt.size; i++) { /* for each list */ 00431 G(L)->strt.nuse -= sweeplist(L, &G(L)->strt.hash[i], all); 00432 } 00433 } 00434 00435 00436 static void checkSizes (lua_State *L, size_t deadmem) 00437 /*@modifies L @*/ 00438 { 00439 /* check size of string hash */ 00440 if (G(L)->strt.nuse < cast(ls_nstr, G(L)->strt.size/4) && 00441 G(L)->strt.size > MINSTRTABSIZE*2) 00442 luaS_resize(L, G(L)->strt.size/2); /* table is too big */ 00443 /* check size of buffer */ 00444 if (luaZ_sizebuffer(&G(L)->buff) > LUA_MINBUFFER*2) { /* buffer too big? */ 00445 size_t newsize = luaZ_sizebuffer(&G(L)->buff) / 2; 00446 luaZ_resizebuffer(L, &G(L)->buff, newsize); 00447 } 00448 G(L)->GCthreshold = 2*G(L)->nblocks - deadmem; /* new threshold */ 00449 } 00450 00451 00452 static void do1gcTM (lua_State *L, Udata *udata) 00453 /*@modifies L, udata @*/ 00454 { 00455 const TObject *tm = fasttm(L, udata->uv.metatable, TM_GC); 00456 if (tm != NULL) { 00457 setobj2s(L->top, tm); 00458 setuvalue(L->top+1, udata); 00459 L->top += 2; 00460 luaD_call(L, L->top - 2, 0); 00461 } 00462 } 00463 00464 00465 void luaC_callGCTM (lua_State *L) { 00466 lu_byte oldah = L->allowhook; 00467 L->allowhook = 0; /* stop debug hooks during GC tag methods */ 00468 L->top++; /* reserve space to keep udata while runs its gc method */ 00469 while (G(L)->tmudata != NULL) { 00470 GCObject *o = G(L)->tmudata; 00471 Udata *udata = gcotou(o); 00472 G(L)->tmudata = udata->uv.next; /* remove udata from `tmudata' */ 00473 udata->uv.next = G(L)->rootudata; /* return it to `root' list */ 00474 G(L)->rootudata = o; 00475 setuvalue(L->top - 1, udata); /* keep a reference to it */ 00476 unmark(o); 00477 markfinalized(udata); 00478 do1gcTM(L, udata); 00479 } 00480 L->top--; 00481 L->allowhook = oldah; /* restore hooks */ 00482 } 00483 00484 00485 void luaC_sweep (lua_State *L, int all) { 00486 if (all) all = 256; /* larger than any mark */ 00487 sweeplist(L, &G(L)->rootudata, all); 00488 sweepstrings(L, all); 00489 sweeplist(L, &G(L)->rootgc, all); 00490 } 00491 00492 00493 /* mark root set */ 00494 static void markroot (GCState *st, lua_State *L) 00495 /*@modifies st, L @*/ 00496 { 00497 global_State *g = st->g; 00498 markobject(st, defaultmeta(L)); 00499 markobject(st, registry(L)); 00500 traversestack(st, g->mainthread); 00501 if (L != g->mainthread) /* another thread is running? */ 00502 markvalue(st, L); /* cannot collect it */ 00503 } 00504 00505 00506 static size_t mark (lua_State *L) 00507 /*@modifies L @*/ 00508 { 00509 size_t deadmem; 00510 GCState st; 00511 GCObject *wkv; 00512 st.g = G(L); 00513 st.tmark = NULL; 00514 st.wkv = st.wk = st.wv = NULL; 00515 markroot(&st, L); 00516 propagatemarks(&st); /* mark all reachable objects */ 00517 cleartablevalues(st.wkv); 00518 cleartablevalues(st.wv); 00519 wkv = st.wkv; /* keys must be cleared after preserving udata */ 00520 st.wkv = NULL; 00521 st.wv = NULL; 00522 deadmem = luaC_separateudata(L); /* separate userdata to be preserved */ 00523 marktmu(&st); /* mark `preserved' userdata */ 00524 propagatemarks(&st); /* remark, to propagate `preserveness' */ 00525 cleartablekeys(wkv); 00526 /* `propagatemarks' may resuscitate some weak tables; clear them too */ 00527 cleartablekeys(st.wk); 00528 cleartablevalues(st.wv); 00529 cleartablekeys(st.wkv); 00530 cleartablevalues(st.wkv); 00531 return deadmem; 00532 } 00533 00534 00535 void luaC_collectgarbage (lua_State *L) { 00536 size_t deadmem = mark(L); 00537 luaC_sweep(L, 0); 00538 checkSizes(L, deadmem); 00539 luaC_callGCTM(L); 00540 } 00541 00542 00543 void luaC_link (lua_State *L, GCObject *o, lu_byte tt) { 00544 o->gch.next = G(L)->rootgc; 00545 G(L)->rootgc = o; 00546 o->gch.marked = 0; 00547 o->gch.tt = tt; 00548 } 00549