2
** $Id: lgc.c,v 2.38.1.1 2007/12/27 13:02:25 roberto Exp $
4
** See Copyright Notice in lua.h
28
#define GCSTEPSIZE 1024u
30
#define GCSWEEPCOST 10
31
#define GCFINALIZECOST 100
34
#define maskmarks cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
36
#define makewhite(g,x) \
37
((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g)))
39
#define white2gray(x) reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
40
#define black2gray(x) resetbit((x)->gch.marked, BLACKBIT)
42
#define stringmark(s) reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT)
45
#define isfinalized(u) testbit((u)->marked, FINALIZEDBIT)
46
#define markfinalized(u) l_setbit((u)->marked, FINALIZEDBIT)
49
#define KEYWEAK bitmask(KEYWEAKBIT)
50
#define VALUEWEAK bitmask(VALUEWEAKBIT)
54
#define markvalue(g,o) { checkconsistency(o); \
55
if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
57
#define markobject(g,t) { if (iswhite(obj2gco(t))) \
58
reallymarkobject(g, obj2gco(t)); }
61
#define setthreshold(g) (g->GCthreshold = (g->estimate/100) * g->gcpause)
64
static void removeentry (Node *n) {
65
lua_assert(ttisnil(gval(n)));
66
if (iscollectable(gkey(n)))
67
setttype(gkey(n), LUA_TDEADKEY); /* dead key; remove it */
71
static void reallymarkobject (global_State *g, GCObject *o) {
72
lua_assert(iswhite(o) && !isdead(g, o));
79
Table *mt = gco2u(o)->metatable;
80
gray2black(o); /* udata are never gray */
81
if (mt) markobject(g, mt);
82
markobject(g, gco2u(o)->env);
86
UpVal *uv = gco2uv(o);
88
if (uv->v == &uv->u.value) /* closed? */
89
gray2black(o); /* open upvalues are never black */
93
gco2cl(o)->c.gclist = g->gray;
98
gco2h(o)->gclist = g->gray;
103
gco2th(o)->gclist = g->gray;
108
gco2p(o)->gclist = g->gray;
112
default: lua_assert(0);
117
static void marktmu (global_State *g) {
118
GCObject *u = g->tmudata;
122
makewhite(g, u); /* may be marked, if left from previous GC */
123
reallymarkobject(g, u);
124
} while (u != g->tmudata);
129
/* move `dead' udata that need finalization to list `tmudata' */
130
size_t luaC_separateudata (lua_State *L, int all) {
131
global_State *g = G(L);
133
GCObject **p = &g->mainthread->next;
135
while ((curr = *p) != NULL) {
136
if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
137
p = &curr->gch.next; /* don't bother with them */
138
else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
139
markfinalized(gco2u(curr)); /* don't need finalization */
142
else { /* must call its gc method */
143
deadmem += sizeudata(gco2u(curr));
144
markfinalized(gco2u(curr));
146
/* link `curr' at the end of `tmudata' list */
147
if (g->tmudata == NULL) /* list is empty? */
148
g->tmudata = curr->gch.next = curr; /* creates a circular list */
150
curr->gch.next = g->tmudata->gch.next;
151
g->tmudata->gch.next = curr;
160
static int traversetable (global_State *g, Table *h) {
166
markobject(g, h->metatable);
167
mode = gfasttm(g, h->metatable, TM_MODE);
168
if (mode && ttisstring(mode)) { /* is there a weak mode? */
169
weakkey = (strchr(svalue(mode), 'k') != NULL);
170
weakvalue = (strchr(svalue(mode), 'v') != NULL);
171
if (weakkey || weakvalue) { /* is really weak? */
172
h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */
173
h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
174
(weakvalue << VALUEWEAKBIT));
175
h->gclist = g->weak; /* must be cleared after GC, ... */
176
g->weak = obj2gco(h); /* ... so put in the appropriate list */
179
if (weakkey && weakvalue) return 1;
183
markvalue(g, &h->array[i]);
187
Node *n = gnode(h, i);
188
lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
189
if (ttisnil(gval(n)))
190
removeentry(n); /* remove empty entries */
192
lua_assert(!ttisnil(gkey(n)));
193
if (!weakkey) markvalue(g, gkey(n));
194
if (!weakvalue) markvalue(g, gval(n));
197
return weakkey || weakvalue;
202
** All marks are conditional because a GC may happen while the
203
** prototype is still being created
205
static void traverseproto (global_State *g, Proto *f) {
207
if (f->source) stringmark(f->source);
208
for (i=0; i<f->sizek; i++) /* mark literals */
209
markvalue(g, &f->k[i]);
210
for (i=0; i<f->sizeupvalues; i++) { /* mark upvalue names */
212
stringmark(f->upvalues[i]);
214
for (i=0; i<f->sizep; i++) { /* mark nested protos */
216
markobject(g, f->p[i]);
218
for (i=0; i<f->sizelocvars; i++) { /* mark local-variable names */
219
if (f->locvars[i].varname)
220
stringmark(f->locvars[i].varname);
226
static void traverseclosure (global_State *g, Closure *cl) {
227
markobject(g, cl->c.env);
230
for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */
231
markvalue(g, &cl->c.upvalue[i]);
235
lua_assert(cl->l.nupvalues == cl->l.p->nups);
236
markobject(g, cl->l.p);
237
for (i=0; i<cl->l.nupvalues; i++) /* mark its upvalues */
238
markobject(g, cl->l.upvals[i]);
243
static void checkstacksizes (lua_State *L, StkId max) {
244
int ci_used = cast_int(L->ci - L->base_ci); /* number of `ci' in use */
245
int s_used = cast_int(max - L->stack); /* part of stack in use */
246
if (L->size_ci > LUAI_MAXCALLS) /* handling overflow? */
247
return; /* do not touch the stacks */
248
if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
249
luaD_reallocCI(L, L->size_ci/2); /* still big enough... */
250
condhardstacktests(luaD_reallocCI(L, ci_used + 1));
251
if (4*s_used < L->stacksize &&
252
2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
253
luaD_reallocstack(L, L->stacksize/2); /* still big enough... */
254
condhardstacktests(luaD_reallocstack(L, s_used));
258
static void traversestack (global_State *g, lua_State *l) {
263
for (ci = l->base_ci; ci <= l->ci; ci++) {
264
lua_assert(ci->top <= l->stack_last);
265
if (lim < ci->top) lim = ci->top;
267
for (o = l->stack; o < l->top; o++)
269
for (; o <= lim; o++)
271
checkstacksizes(l, lim);
276
** traverse one gray object, turning it to black.
277
** Returns `quantity' traversed.
279
static l_mem propagatemark (global_State *g) {
280
GCObject *o = g->gray;
281
lua_assert(isgray(o));
287
if (traversetable(g, h)) /* table is weak? */
288
black2gray(o); /* keep it gray */
289
return sizeof(Table) + sizeof(TValue) * h->sizearray +
290
sizeof(Node) * sizenode(h);
292
case LUA_TFUNCTION: {
293
Closure *cl = gco2cl(o);
294
g->gray = cl->c.gclist;
295
traverseclosure(g, cl);
296
return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
297
sizeLclosure(cl->l.nupvalues);
300
lua_State *th = gco2th(o);
301
g->gray = th->gclist;
302
th->gclist = g->grayagain;
305
traversestack(g, th);
306
return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
307
sizeof(CallInfo) * th->size_ci;
313
return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
314
sizeof(Proto *) * p->sizep +
315
sizeof(TValue) * p->sizek +
316
sizeof(int) * p->sizelineinfo +
317
sizeof(LocVar) * p->sizelocvars +
318
sizeof(TString *) * p->sizeupvalues;
320
default: lua_assert(0); return 0;
325
static size_t propagateall (global_State *g) {
327
while (g->gray) m += propagatemark(g);
333
** The next function tells whether a key or value can be cleared from
334
** a weak table. Non-collectable objects are never removed from weak
335
** tables. Strings behave as `values', so are never removed too. for
336
** other objects: if really collected, cannot keep them; for userdata
337
** being finalized, keep them in keys, but not in values
339
static int iscleared (const TValue *o, int iskey) {
340
if (!iscollectable(o)) return 0;
342
stringmark(rawtsvalue(o)); /* strings are `values', so are never weak */
345
return iswhite(gcvalue(o)) ||
346
(ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
351
** clear collected entries from weaktables
353
static void cleartable (GCObject *l) {
356
int i = h->sizearray;
357
lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
358
testbit(h->marked, KEYWEAKBIT));
359
if (testbit(h->marked, VALUEWEAKBIT)) {
361
TValue *o = &h->array[i];
362
if (iscleared(o, 0)) /* value was collected? */
363
setnilvalue(o); /* remove value */
368
Node *n = gnode(h, i);
369
if (!ttisnil(gval(n)) && /* non-empty entry? */
370
(iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
371
setnilvalue(gval(n)); /* remove value ... */
372
removeentry(n); /* remove entry from table */
380
static void freeobj (lua_State *L, GCObject *o) {
382
case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
383
case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
384
case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
385
case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
387
lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
388
luaE_freethread(L, gco2th(o));
393
luaM_freemem(L, o, sizestring(gco2ts(o)));
396
case LUA_TUSERDATA: {
397
luaM_freemem(L, o, sizeudata(gco2u(o)));
400
default: lua_assert(0);
406
#define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM)
409
static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
411
global_State *g = G(L);
412
int deadmask = otherwhite(g);
413
while ((curr = *p) != NULL && count-- > 0) {
414
if (curr->gch.tt == LUA_TTHREAD) /* sweep open upvalues of each thread */
415
sweepwholelist(L, &gco2th(curr)->openupval);
416
if ((curr->gch.marked ^ WHITEBITS) & deadmask) { /* not dead? */
417
lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
418
makewhite(g, curr); /* make it white (for next cycle) */
421
else { /* must erase `curr' */
422
lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
424
if (curr == g->rootgc) /* is the first element of the list? */
425
g->rootgc = curr->gch.next; /* adjust first */
433
static void checkSizes (lua_State *L) {
434
global_State *g = G(L);
435
/* check size of string hash */
436
if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
437
g->strt.size > MINSTRTABSIZE*2)
438
luaS_resize(L, g->strt.size/2); /* table is too big */
439
/* check size of buffer */
440
if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) { /* buffer too big? */
441
size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
442
luaZ_resizebuffer(L, &g->buff, newsize);
447
static void GCTM (lua_State *L) {
448
global_State *g = G(L);
449
GCObject *o = g->tmudata->gch.next; /* get first element */
450
Udata *udata = rawgco2u(o);
452
/* remove udata from `tmudata' */
453
if (o == g->tmudata) /* last element? */
456
g->tmudata->gch.next = udata->uv.next;
457
udata->uv.next = g->mainthread->next; /* return it to `root' list */
458
g->mainthread->next = o;
460
tm = fasttm(L, udata->uv.metatable, TM_GC);
462
lu_byte oldah = L->allowhook;
463
lu_mem oldt = g->GCthreshold;
464
L->allowhook = 0; /* stop debug hooks during GC tag method */
465
g->GCthreshold = 2*g->totalbytes; /* avoid GC steps */
466
setobj2s(L, L->top, tm);
467
setuvalue(L, L->top+1, udata);
469
luaD_call(L, L->top - 2, 0);
470
L->allowhook = oldah; /* restore hooks */
471
g->GCthreshold = oldt; /* restore threshold */
477
** Call all GC tag methods
479
void luaC_callGCTM (lua_State *L) {
480
while (G(L)->tmudata)
485
void luaC_freeall (lua_State *L) {
486
global_State *g = G(L);
488
g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT); /* mask to collect all elements */
489
sweepwholelist(L, &g->rootgc);
490
for (i = 0; i < g->strt.size; i++) /* free all string lists */
491
sweepwholelist(L, &g->strt.hash[i]);
495
static void markmt (global_State *g) {
497
for (i=0; i<NUM_TAGS; i++)
498
if (g->mt[i]) markobject(g, g->mt[i]);
503
static void markroot (lua_State *L) {
504
global_State *g = G(L);
508
markobject(g, g->mainthread);
509
/* make global table be traversed before main stack */
510
markvalue(g, gt(g->mainthread));
511
markvalue(g, registry(L));
513
g->gcstate = GCSpropagate;
517
static void remarkupvals (global_State *g) {
519
for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
520
lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
521
if (isgray(obj2gco(uv)))
527
static void atomic (lua_State *L) {
528
global_State *g = G(L);
529
size_t udsize; /* total size of userdata to be finalized */
530
/* remark occasional upvalues of (maybe) dead threads */
532
/* traverse objects cautch by write barrier and by 'remarkupvals' */
534
/* remark weak tables */
537
lua_assert(!iswhite(obj2gco(g->mainthread)));
538
markobject(g, L); /* mark running thread */
539
markmt(g); /* mark basic metatables (again) */
541
/* remark gray again */
542
g->gray = g->grayagain;
545
udsize = luaC_separateudata(L, 0); /* separate userdata to be finalized */
546
marktmu(g); /* mark `preserved' userdata */
547
udsize += propagateall(g); /* remark, to propagate `preserveness' */
548
cleartable(g->weak); /* remove collected objects from weak tables */
549
/* flip current white */
550
g->currentwhite = cast_byte(otherwhite(g));
552
g->sweepgc = &g->rootgc;
553
g->gcstate = GCSsweepstring;
554
g->estimate = g->totalbytes - udsize; /* first estimate */
558
static l_mem singlestep (lua_State *L) {
559
global_State *g = G(L);
560
/*lua_checkmemory(L);*/
561
switch (g->gcstate) {
563
markroot(L); /* start a new collection */
568
return propagatemark(g);
569
else { /* no more `gray' objects */
570
atomic(L); /* finish mark phase */
574
case GCSsweepstring: {
575
lu_mem old = g->totalbytes;
576
sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
577
if (g->sweepstrgc >= g->strt.size) /* nothing more to sweep? */
578
g->gcstate = GCSsweep; /* end sweep-string phase */
579
lua_assert(old >= g->totalbytes);
580
g->estimate -= old - g->totalbytes;
584
lu_mem old = g->totalbytes;
585
g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
586
if (*g->sweepgc == NULL) { /* nothing more to sweep? */
588
g->gcstate = GCSfinalize; /* end sweep phase */
590
lua_assert(old >= g->totalbytes);
591
g->estimate -= old - g->totalbytes;
592
return GCSWEEPMAX*GCSWEEPCOST;
597
if (g->estimate > GCFINALIZECOST)
598
g->estimate -= GCFINALIZECOST;
599
return GCFINALIZECOST;
602
g->gcstate = GCSpause; /* end collection */
607
default: lua_assert(0); return 0;
612
void luaC_step (lua_State *L) {
613
global_State *g = G(L);
614
l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
616
lim = (MAX_LUMEM-1)/2; /* no limit */
617
g->gcdept += g->totalbytes - g->GCthreshold;
619
lim -= singlestep(L);
620
if (g->gcstate == GCSpause)
623
if (g->gcstate != GCSpause) {
624
if (g->gcdept < GCSTEPSIZE)
625
g->GCthreshold = g->totalbytes + GCSTEPSIZE; /* - lim/g->gcstepmul;*/
627
g->gcdept -= GCSTEPSIZE;
628
g->GCthreshold = g->totalbytes;
632
lua_assert(g->totalbytes >= g->estimate);
638
void luaC_fullgc (lua_State *L) {
639
global_State *g = G(L);
640
if (g->gcstate <= GCSpropagate) {
641
/* reset sweep marks to sweep all elements (returning them to white) */
643
g->sweepgc = &g->rootgc;
644
/* reset other collector lists */
648
g->gcstate = GCSsweepstring;
650
lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
651
/* finish any pending sweep phase */
652
while (g->gcstate != GCSfinalize) {
653
lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
657
while (g->gcstate != GCSpause) {
664
void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
665
global_State *g = G(L);
666
lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
667
lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
668
lua_assert(ttype(&o->gch) != LUA_TTABLE);
669
/* must keep invariant? */
670
if (g->gcstate == GCSpropagate)
671
reallymarkobject(g, v); /* restore invariant */
672
else /* don't mind */
673
makewhite(g, o); /* mark as white just to avoid other barriers */
677
void luaC_barrierback (lua_State *L, Table *t) {
678
global_State *g = G(L);
679
GCObject *o = obj2gco(t);
680
lua_assert(isblack(o) && !isdead(g, o));
681
lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
682
black2gray(o); /* make table gray (again) */
683
t->gclist = g->grayagain;
688
void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
689
global_State *g = G(L);
690
o->gch.next = g->rootgc;
692
o->gch.marked = luaC_white(g);
697
void luaC_linkupval (lua_State *L, UpVal *uv) {
698
global_State *g = G(L);
699
GCObject *o = obj2gco(uv);
700
o->gch.next = g->rootgc; /* link upvalue into `rootgc' list */
703
if (g->gcstate == GCSpropagate) {
704
gray2black(o); /* closed upvalues need barrier */
705
luaC_barrier(L, uv, uv->v);
707
else { /* sweep phase: sweep it (turning it into white) */
709
lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
added
removed
script/lua/lgc.c
