]>
git.proxmox.com Git - mirror_edk2.git/blob - AppPkg/Applications/Lua/src/lgc.c
2 ** $Id: lgc.c,v 2.140.1.2 2013/04/26 18:22:05 roberto Exp $
4 ** See Copyright Notice in lua.h
28 ** cost of sweeping one element (the size of a small object divided
29 ** by some adjust for the sweep speed)
31 #define GCSWEEPCOST ((sizeof(TString) + 4) / 4)
33 /* maximum number of elements to sweep in each single step */
34 #define GCSWEEPMAX (cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4))
36 /* maximum number of finalizers to call in each GC step */
37 #define GCFINALIZENUM 4
41 ** macro to adjust 'stepmul': 'stepmul' is actually used like
42 ** 'stepmul / STEPMULADJ' (value chosen by tests)
44 #define STEPMULADJ 200
48 ** macro to adjust 'pause': 'pause' is actually used like
49 ** 'pause / PAUSEADJ' (value chosen by tests)
55 ** 'makewhite' erases all color bits plus the old bit and then
56 ** sets only the current white bit
58 #define maskcolors (~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS))
59 #define makewhite(g,x) \
60 (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g)))
62 #define white2gray(x) resetbits(gch(x)->marked, WHITEBITS)
63 #define black2gray(x) resetbit(gch(x)->marked, BLACKBIT)
66 #define isfinalized(x) testbit(gch(x)->marked, FINALIZEDBIT)
68 #define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n)))
71 #define checkconsistency(obj) \
72 lua_longassert(!iscollectable(obj) || righttt(obj))
75 #define markvalue(g,o) { checkconsistency(o); \
76 if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
78 #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \
79 reallymarkobject(g, obj2gco(t)); }
81 static void reallymarkobject (global_State
*g
, GCObject
*o
);
85 ** {======================================================
87 ** =======================================================
92 ** one after last element in a hash array
94 #define gnodelast(h) gnode(h, cast(size_t, sizenode(h)))
98 ** link table 'h' into list pointed by 'p'
100 #define linktable(h,p) ((h)->gclist = *(p), *(p) = obj2gco(h))
104 ** if key is not marked, mark its entry as dead (therefore removing it
107 static void removeentry (Node
*n
) {
108 lua_assert(ttisnil(gval(n
)));
109 if (valiswhite(gkey(n
)))
110 setdeadvalue(gkey(n
)); /* unused and unmarked key; remove it */
115 ** tells whether a key or value can be cleared from a weak
116 ** table. Non-collectable objects are never removed from weak
117 ** tables. Strings behave as `values', so are never removed too. for
118 ** other objects: if really collected, cannot keep them; for objects
119 ** being finalized, keep them in keys, but not in values
121 static int iscleared (global_State
*g
, const TValue
*o
) {
122 if (!iscollectable(o
)) return 0;
123 else if (ttisstring(o
)) {
124 markobject(g
, rawtsvalue(o
)); /* strings are `values', so are never weak */
127 else return iswhite(gcvalue(o
));
132 ** barrier that moves collector forward, that is, mark the white object
133 ** being pointed by a black object.
135 void luaC_barrier_ (lua_State
*L
, GCObject
*o
, GCObject
*v
) {
136 global_State
*g
= G(L
);
137 lua_assert(isblack(o
) && iswhite(v
) && !isdead(g
, v
) && !isdead(g
, o
));
138 lua_assert(g
->gcstate
!= GCSpause
);
139 lua_assert(gch(o
)->tt
!= LUA_TTABLE
);
140 if (keepinvariantout(g
)) /* must keep invariant? */
141 reallymarkobject(g
, v
); /* restore invariant */
142 else { /* sweep phase */
143 lua_assert(issweepphase(g
));
144 makewhite(g
, o
); /* mark main obj. as white to avoid other barriers */
150 ** barrier that moves collector backward, that is, mark the black object
151 ** pointing to a white object as gray again. (Current implementation
152 ** only works for tables; access to 'gclist' is not uniform across
155 void luaC_barrierback_ (lua_State
*L
, GCObject
*o
) {
156 global_State
*g
= G(L
);
157 lua_assert(isblack(o
) && !isdead(g
, o
) && gch(o
)->tt
== LUA_TTABLE
);
158 black2gray(o
); /* make object gray (again) */
159 gco2t(o
)->gclist
= g
->grayagain
;
165 ** barrier for prototypes. When creating first closure (cache is
166 ** NULL), use a forward barrier; this may be the only closure of the
167 ** prototype (if it is a "regular" function, with a single instance)
168 ** and the prototype may be big, so it is better to avoid traversing
169 ** it again. Otherwise, use a backward barrier, to avoid marking all
170 ** possible instances.
172 LUAI_FUNC
void luaC_barrierproto_ (lua_State
*L
, Proto
*p
, Closure
*c
) {
173 global_State
*g
= G(L
);
174 lua_assert(isblack(obj2gco(p
)));
175 if (p
->cache
== NULL
) { /* first time? */
176 luaC_objbarrier(L
, p
, c
);
178 else { /* use a backward barrier */
179 black2gray(obj2gco(p
)); /* make prototype gray (again) */
180 p
->gclist
= g
->grayagain
;
181 g
->grayagain
= obj2gco(p
);
187 ** check color (and invariants) for an upvalue that was closed,
188 ** i.e., moved into the 'allgc' list
190 void luaC_checkupvalcolor (global_State
*g
, UpVal
*uv
) {
191 GCObject
*o
= obj2gco(uv
);
192 lua_assert(!isblack(o
)); /* open upvalues are never black */
194 if (keepinvariant(g
)) {
195 resetoldbit(o
); /* see MOVE OLD rule */
196 gray2black(o
); /* it is being visited now */
200 lua_assert(issweepphase(g
));
208 ** create a new collectable object (with given type and size) and link
209 ** it to '*list'. 'offset' tells how many bytes to allocate before the
210 ** object itself (used only by states).
212 GCObject
*luaC_newobj (lua_State
*L
, int tt
, size_t sz
, GCObject
**list
,
214 global_State
*g
= G(L
);
215 char *raw
= cast(char *, luaM_newobject(L
, novariant(tt
), sz
));
216 GCObject
*o
= obj2gco(raw
+ offset
);
218 list
= &g
->allgc
; /* standard list for collectable objects */
219 gch(o
)->marked
= luaC_white(g
);
220 gch(o
)->tt
= (lu_byte
)tt
;
221 gch(o
)->next
= *list
;
226 /* }====================================================== */
231 ** {======================================================
233 ** =======================================================
238 ** mark an object. Userdata, strings, and closed upvalues are visited
239 ** and turned black here. Other objects are marked gray and added
240 ** to appropriate list to be visited (and turned black) later. (Open
241 ** upvalues are already linked in 'headuv' list.)
243 static void reallymarkobject (global_State
*g
, GCObject
*o
) {
246 switch (gch(o
)->tt
) {
249 size
= sizestring(gco2ts(o
));
250 break; /* nothing else to mark; make it black */
252 case LUA_TUSERDATA
: {
253 Table
*mt
= gco2u(o
)->metatable
;
255 markobject(g
, gco2u(o
)->env
);
256 size
= sizeudata(gco2u(o
));
260 UpVal
*uv
= gco2uv(o
);
262 if (uv
->v
!= &uv
->u
.value
) /* open? */
263 return; /* open upvalues remain gray */
264 size
= sizeof(UpVal
);
268 gco2lcl(o
)->gclist
= g
->gray
;
273 gco2ccl(o
)->gclist
= g
->gray
;
278 linktable(gco2t(o
), &g
->gray
);
282 gco2th(o
)->gclist
= g
->gray
;
287 gco2p(o
)->gclist
= g
->gray
;
291 default: lua_assert(0); return;
294 g
->GCmemtrav
+= size
;
299 ** mark metamethods for basic types
301 static void markmt (global_State
*g
) {
303 for (i
=0; i
< LUA_NUMTAGS
; i
++)
304 markobject(g
, g
->mt
[i
]);
309 ** mark all objects in list of being-finalized
311 static void markbeingfnz (global_State
*g
) {
313 for (o
= g
->tobefnz
; o
!= NULL
; o
= gch(o
)->next
) {
315 reallymarkobject(g
, o
);
321 ** mark all values stored in marked open upvalues. (See comment in
324 static void remarkupvals (global_State
*g
) {
326 for (uv
= g
->uvhead
.u
.l
.next
; uv
!= &g
->uvhead
; uv
= uv
->u
.l
.next
) {
327 if (isgray(obj2gco(uv
)))
334 ** mark root set and reset all gray lists, to start a new
335 ** incremental (or full) collection
337 static void restartcollection (global_State
*g
) {
338 g
->gray
= g
->grayagain
= NULL
;
339 g
->weak
= g
->allweak
= g
->ephemeron
= NULL
;
340 markobject(g
, g
->mainthread
);
341 markvalue(g
, &g
->l_registry
);
343 markbeingfnz(g
); /* mark any finalizing object left from previous cycle */
346 /* }====================================================== */
350 ** {======================================================
351 ** Traverse functions
352 ** =======================================================
355 static void traverseweakvalue (global_State
*g
, Table
*h
) {
356 Node
*n
, *limit
= gnodelast(h
);
357 /* if there is array part, assume it may have white values (do not
358 traverse it just to check) */
359 int hasclears
= (h
->sizearray
> 0);
360 for (n
= gnode(h
, 0); n
< limit
; n
++) {
362 if (ttisnil(gval(n
))) /* entry is empty? */
363 removeentry(n
); /* remove it */
365 lua_assert(!ttisnil(gkey(n
)));
366 markvalue(g
, gkey(n
)); /* mark key */
367 if (!hasclears
&& iscleared(g
, gval(n
))) /* is there a white value? */
368 hasclears
= 1; /* table will have to be cleared */
372 linktable(h
, &g
->weak
); /* has to be cleared later */
373 else /* no white values */
374 linktable(h
, &g
->grayagain
); /* no need to clean */
378 static int traverseephemeron (global_State
*g
, Table
*h
) {
379 int marked
= 0; /* true if an object is marked in this traversal */
380 int hasclears
= 0; /* true if table has white keys */
381 int prop
= 0; /* true if table has entry "white-key -> white-value" */
382 Node
*n
, *limit
= gnodelast(h
);
384 /* traverse array part (numeric keys are 'strong') */
385 for (i
= 0; i
< h
->sizearray
; i
++) {
386 if (valiswhite(&h
->array
[i
])) {
388 reallymarkobject(g
, gcvalue(&h
->array
[i
]));
391 /* traverse hash part */
392 for (n
= gnode(h
, 0); n
< limit
; n
++) {
394 if (ttisnil(gval(n
))) /* entry is empty? */
395 removeentry(n
); /* remove it */
396 else if (iscleared(g
, gkey(n
))) { /* key is not marked (yet)? */
397 hasclears
= 1; /* table must be cleared */
398 if (valiswhite(gval(n
))) /* value not marked yet? */
399 prop
= 1; /* must propagate again */
401 else if (valiswhite(gval(n
))) { /* value not marked yet? */
403 reallymarkobject(g
, gcvalue(gval(n
))); /* mark it now */
407 linktable(h
, &g
->ephemeron
); /* have to propagate again */
408 else if (hasclears
) /* does table have white keys? */
409 linktable(h
, &g
->allweak
); /* may have to clean white keys */
410 else /* no white keys */
411 linktable(h
, &g
->grayagain
); /* no need to clean */
416 static void traversestrongtable (global_State
*g
, Table
*h
) {
417 Node
*n
, *limit
= gnodelast(h
);
419 for (i
= 0; i
< h
->sizearray
; i
++) /* traverse array part */
420 markvalue(g
, &h
->array
[i
]);
421 for (n
= gnode(h
, 0); n
< limit
; n
++) { /* traverse hash part */
423 if (ttisnil(gval(n
))) /* entry is empty? */
424 removeentry(n
); /* remove it */
426 lua_assert(!ttisnil(gkey(n
)));
427 markvalue(g
, gkey(n
)); /* mark key */
428 markvalue(g
, gval(n
)); /* mark value */
434 static lu_mem
traversetable (global_State
*g
, Table
*h
) {
435 const char *weakkey
, *weakvalue
;
436 const TValue
*mode
= gfasttm(g
, h
->metatable
, TM_MODE
);
437 markobject(g
, h
->metatable
);
438 if (mode
&& ttisstring(mode
) && /* is there a weak mode? */
439 ((weakkey
= strchr(svalue(mode
), 'k')),
440 (weakvalue
= strchr(svalue(mode
), 'v')),
441 (weakkey
|| weakvalue
))) { /* is really weak? */
442 black2gray(obj2gco(h
)); /* keep table gray */
443 if (!weakkey
) /* strong keys? */
444 traverseweakvalue(g
, h
);
445 else if (!weakvalue
) /* strong values? */
446 traverseephemeron(g
, h
);
448 linktable(h
, &g
->allweak
); /* nothing to traverse now */
451 traversestrongtable(g
, h
);
452 return sizeof(Table
) + sizeof(TValue
) * h
->sizearray
+
453 sizeof(Node
) * cast(size_t, sizenode(h
));
457 static int traverseproto (global_State
*g
, Proto
*f
) {
459 if (f
->cache
&& iswhite(obj2gco(f
->cache
)))
460 f
->cache
= NULL
; /* allow cache to be collected */
461 markobject(g
, f
->source
);
462 for (i
= 0; i
< f
->sizek
; i
++) /* mark literals */
463 markvalue(g
, &f
->k
[i
]);
464 for (i
= 0; i
< f
->sizeupvalues
; i
++) /* mark upvalue names */
465 markobject(g
, f
->upvalues
[i
].name
);
466 for (i
= 0; i
< f
->sizep
; i
++) /* mark nested protos */
467 markobject(g
, f
->p
[i
]);
468 for (i
= 0; i
< f
->sizelocvars
; i
++) /* mark local-variable names */
469 markobject(g
, f
->locvars
[i
].varname
);
470 return sizeof(Proto
) + sizeof(Instruction
) * f
->sizecode
+
471 sizeof(Proto
*) * f
->sizep
+
472 sizeof(TValue
) * f
->sizek
+
473 sizeof(int) * f
->sizelineinfo
+
474 sizeof(LocVar
) * f
->sizelocvars
+
475 sizeof(Upvaldesc
) * f
->sizeupvalues
;
479 static lu_mem
traverseCclosure (global_State
*g
, CClosure
*cl
) {
481 for (i
= 0; i
< cl
->nupvalues
; i
++) /* mark its upvalues */
482 markvalue(g
, &cl
->upvalue
[i
]);
483 return sizeCclosure(cl
->nupvalues
);
486 static lu_mem
traverseLclosure (global_State
*g
, LClosure
*cl
) {
488 markobject(g
, cl
->p
); /* mark its prototype */
489 for (i
= 0; i
< cl
->nupvalues
; i
++) /* mark its upvalues */
490 markobject(g
, cl
->upvals
[i
]);
491 return sizeLclosure(cl
->nupvalues
);
495 static lu_mem
traversestack (global_State
*g
, lua_State
*th
) {
499 return 1; /* stack not completely built yet */
500 for (; o
< th
->top
; o
++) /* mark live elements in the stack */
502 if (g
->gcstate
== GCSatomic
) { /* final traversal? */
503 StkId lim
= th
->stack
+ th
->stacksize
; /* real end of stack */
504 for (; o
< lim
; o
++) /* clear not-marked stack slice */
507 else { /* count call infos to compute size */
509 for (ci
= &th
->base_ci
; ci
!= th
->ci
; ci
= ci
->next
)
512 return sizeof(lua_State
) + sizeof(TValue
) * th
->stacksize
+
513 sizeof(CallInfo
) * n
;
518 ** traverse one gray object, turning it to black (except for threads,
519 ** which are always gray).
521 static void propagatemark (global_State
*g
) {
523 GCObject
*o
= g
->gray
;
524 lua_assert(isgray(o
));
526 switch (gch(o
)->tt
) {
529 g
->gray
= h
->gclist
; /* remove from 'gray' list */
530 size
= traversetable(g
, h
);
534 LClosure
*cl
= gco2lcl(o
);
535 g
->gray
= cl
->gclist
; /* remove from 'gray' list */
536 size
= traverseLclosure(g
, cl
);
540 CClosure
*cl
= gco2ccl(o
);
541 g
->gray
= cl
->gclist
; /* remove from 'gray' list */
542 size
= traverseCclosure(g
, cl
);
546 lua_State
*th
= gco2th(o
);
547 g
->gray
= th
->gclist
; /* remove from 'gray' list */
548 th
->gclist
= g
->grayagain
;
549 g
->grayagain
= o
; /* insert into 'grayagain' list */
551 size
= traversestack(g
, th
);
556 g
->gray
= p
->gclist
; /* remove from 'gray' list */
557 size
= traverseproto(g
, p
);
560 default: lua_assert(0); return;
562 g
->GCmemtrav
+= size
;
566 static void propagateall (global_State
*g
) {
567 while (g
->gray
) propagatemark(g
);
571 static void propagatelist (global_State
*g
, GCObject
*l
) {
572 lua_assert(g
->gray
== NULL
); /* no grays left */
574 propagateall(g
); /* traverse all elements from 'l' */
578 ** retraverse all gray lists. Because tables may be reinserted in other
579 ** lists when traversed, traverse the original lists to avoid traversing
580 ** twice the same table (which is not wrong, but inefficient)
582 static void retraversegrays (global_State
*g
) {
583 GCObject
*weak
= g
->weak
; /* save original lists */
584 GCObject
*grayagain
= g
->grayagain
;
585 GCObject
*ephemeron
= g
->ephemeron
;
586 g
->weak
= g
->grayagain
= g
->ephemeron
= NULL
;
587 propagateall(g
); /* traverse main gray list */
588 propagatelist(g
, grayagain
);
589 propagatelist(g
, weak
);
590 propagatelist(g
, ephemeron
);
594 static void convergeephemerons (global_State
*g
) {
598 GCObject
*next
= g
->ephemeron
; /* get ephemeron list */
599 g
->ephemeron
= NULL
; /* tables will return to this list when traversed */
601 while ((w
= next
) != NULL
) {
602 next
= gco2t(w
)->gclist
;
603 if (traverseephemeron(g
, gco2t(w
))) { /* traverse marked some value? */
604 propagateall(g
); /* propagate changes */
605 changed
= 1; /* will have to revisit all ephemeron tables */
611 /* }====================================================== */
615 ** {======================================================
617 ** =======================================================
622 ** clear entries with unmarked keys from all weaktables in list 'l' up
625 static void clearkeys (global_State
*g
, GCObject
*l
, GCObject
*f
) {
626 for (; l
!= f
; l
= gco2t(l
)->gclist
) {
628 Node
*n
, *limit
= gnodelast(h
);
629 for (n
= gnode(h
, 0); n
< limit
; n
++) {
630 if (!ttisnil(gval(n
)) && (iscleared(g
, gkey(n
)))) {
631 setnilvalue(gval(n
)); /* remove value ... */
632 removeentry(n
); /* and remove entry from table */
640 ** clear entries with unmarked values from all weaktables in list 'l' up
643 static void clearvalues (global_State
*g
, GCObject
*l
, GCObject
*f
) {
644 for (; l
!= f
; l
= gco2t(l
)->gclist
) {
646 Node
*n
, *limit
= gnodelast(h
);
648 for (i
= 0; i
< h
->sizearray
; i
++) {
649 TValue
*o
= &h
->array
[i
];
650 if (iscleared(g
, o
)) /* value was collected? */
651 setnilvalue(o
); /* remove value */
653 for (n
= gnode(h
, 0); n
< limit
; n
++) {
654 if (!ttisnil(gval(n
)) && iscleared(g
, gval(n
))) {
655 setnilvalue(gval(n
)); /* remove value ... */
656 removeentry(n
); /* and remove entry from table */
663 static void freeobj (lua_State
*L
, GCObject
*o
) {
664 switch (gch(o
)->tt
) {
665 case LUA_TPROTO
: luaF_freeproto(L
, gco2p(o
)); break;
667 luaM_freemem(L
, o
, sizeLclosure(gco2lcl(o
)->nupvalues
));
671 luaM_freemem(L
, o
, sizeCclosure(gco2ccl(o
)->nupvalues
));
674 case LUA_TUPVAL
: luaF_freeupval(L
, gco2uv(o
)); break;
675 case LUA_TTABLE
: luaH_free(L
, gco2t(o
)); break;
676 case LUA_TTHREAD
: luaE_freethread(L
, gco2th(o
)); break;
677 case LUA_TUSERDATA
: luaM_freemem(L
, o
, sizeudata(gco2u(o
))); break;
682 luaM_freemem(L
, o
, sizestring(gco2ts(o
)));
685 default: lua_assert(0);
690 #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM)
691 static GCObject
**sweeplist (lua_State
*L
, GCObject
**p
, lu_mem count
);
695 ** sweep the (open) upvalues of a thread and resize its stack and
696 ** list of call-info structures.
698 static void sweepthread (lua_State
*L
, lua_State
*L1
) {
699 if (L1
->stack
== NULL
) return; /* stack not completely built yet */
700 sweepwholelist(L
, &L1
->openupval
); /* sweep open upvalues */
701 luaE_freeCI(L1
); /* free extra CallInfo slots */
702 /* should not change the stack during an emergency gc cycle */
703 if (G(L
)->gckind
!= KGC_EMERGENCY
)
704 luaD_shrinkstack(L1
);
709 ** sweep at most 'count' elements from a list of GCObjects erasing dead
710 ** objects, where a dead (not alive) object is one marked with the "old"
711 ** (non current) white and not fixed.
712 ** In non-generational mode, change all non-dead objects back to white,
713 ** preparing for next collection cycle.
714 ** In generational mode, keep black objects black, and also mark them as
715 ** old; stop when hitting an old object, as all objects after that
716 ** one will be old too.
717 ** When object is a thread, sweep its list of open upvalues too.
719 static GCObject
**sweeplist (lua_State
*L
, GCObject
**p
, lu_mem count
) {
720 global_State
*g
= G(L
);
721 int ow
= otherwhite(g
);
722 int toclear
, toset
; /* bits to clear and to set in all live objects */
723 int tostop
; /* stop sweep when this is true */
724 if (isgenerational(g
)) { /* generational mode? */
725 toclear
= ~0; /* clear nothing */
726 toset
= bitmask(OLDBIT
); /* set the old bit of all surviving objects */
727 tostop
= bitmask(OLDBIT
); /* do not sweep old generation */
729 else { /* normal mode */
730 toclear
= maskcolors
; /* clear all color bits + old bit */
731 toset
= luaC_white(g
); /* make object white */
732 tostop
= 0; /* do not stop */
734 while (*p
!= NULL
&& count
-- > 0) {
736 int marked
= gch(curr
)->marked
;
737 if (isdeadm(ow
, marked
)) { /* is 'curr' dead? */
738 *p
= gch(curr
)->next
; /* remove 'curr' from list */
739 freeobj(L
, curr
); /* erase 'curr' */
742 if (testbits(marked
, tostop
))
743 return NULL
; /* stop sweeping this list */
744 if (gch(curr
)->tt
== LUA_TTHREAD
)
745 sweepthread(L
, gco2th(curr
)); /* sweep thread's upvalues */
747 gch(curr
)->marked
= cast_byte((marked
& toclear
) | toset
);
748 p
= &gch(curr
)->next
; /* go to next element */
751 return (*p
== NULL
) ? NULL
: p
;
756 ** sweep a list until a live object (or end of list)
758 static GCObject
**sweeptolive (lua_State
*L
, GCObject
**p
, int *n
) {
763 p
= sweeplist(L
, p
, 1);
769 /* }====================================================== */
773 ** {======================================================
775 ** =======================================================
778 static void checkSizes (lua_State
*L
) {
779 global_State
*g
= G(L
);
780 if (g
->gckind
!= KGC_EMERGENCY
) { /* do not change sizes in emergency */
781 int hs
= g
->strt
.size
/ 2; /* half the size of the string table */
782 if (g
->strt
.nuse
< cast(lu_int32
, hs
)) /* using less than that half? */
783 luaS_resize(L
, hs
); /* halve its size */
784 luaZ_freebuffer(L
, &g
->buff
); /* free concatenation buffer */
789 static GCObject
*udata2finalize (global_State
*g
) {
790 GCObject
*o
= g
->tobefnz
; /* get first element */
791 lua_assert(isfinalized(o
));
792 g
->tobefnz
= gch(o
)->next
; /* remove it from 'tobefnz' list */
793 gch(o
)->next
= g
->allgc
; /* return it to 'allgc' list */
795 resetbit(gch(o
)->marked
, SEPARATED
); /* mark that it is not in 'tobefnz' */
796 lua_assert(!isold(o
)); /* see MOVE OLD rule */
797 if (!keepinvariantout(g
)) /* not keeping invariant? */
798 makewhite(g
, o
); /* "sweep" object */
803 static void dothecall (lua_State
*L
, void *ud
) {
805 luaD_call(L
, L
->top
- 2, 0, 0);
809 static void GCTM (lua_State
*L
, int propagateerrors
) {
810 global_State
*g
= G(L
);
813 setgcovalue(L
, &v
, udata2finalize(g
));
814 tm
= luaT_gettmbyobj(L
, &v
, TM_GC
);
815 if (tm
!= NULL
&& ttisfunction(tm
)) { /* is there a finalizer? */
817 lu_byte oldah
= L
->allowhook
;
818 int running
= g
->gcrunning
;
819 L
->allowhook
= 0; /* stop debug hooks during GC metamethod */
820 g
->gcrunning
= 0; /* avoid GC steps */
821 setobj2s(L
, L
->top
, tm
); /* push finalizer... */
822 setobj2s(L
, L
->top
+ 1, &v
); /* ... and its argument */
823 L
->top
+= 2; /* and (next line) call the finalizer */
824 status
= luaD_pcall(L
, dothecall
, NULL
, savestack(L
, L
->top
- 2), 0);
825 L
->allowhook
= oldah
; /* restore hooks */
826 g
->gcrunning
= (lu_byte
)running
; /* restore state */
827 if (status
!= LUA_OK
&& propagateerrors
) { /* error while running __gc? */
828 if (status
== LUA_ERRRUN
) { /* is there an error object? */
829 const char *msg
= (ttisstring(L
->top
- 1))
832 luaO_pushfstring(L
, "error in __gc metamethod (%s)", msg
);
833 status
= LUA_ERRGCMM
; /* error in __gc metamethod */
835 luaD_throw(L
, status
); /* re-throw error */
842 ** move all unreachable objects (or 'all' objects) that need
843 ** finalization from list 'finobj' to list 'tobefnz' (to be finalized)
845 static void separatetobefnz (lua_State
*L
, int all
) {
846 global_State
*g
= G(L
);
847 GCObject
**p
= &g
->finobj
;
849 GCObject
**lastnext
= &g
->tobefnz
;
850 /* find last 'next' field in 'tobefnz' list (to add elements in its end) */
851 while (*lastnext
!= NULL
)
852 lastnext
= &gch(*lastnext
)->next
;
853 while ((curr
= *p
) != NULL
) { /* traverse all finalizable objects */
854 lua_assert(!isfinalized(curr
));
855 lua_assert(testbit(gch(curr
)->marked
, SEPARATED
));
856 if (!(iswhite(curr
) || all
)) /* not being collected? */
857 p
= &gch(curr
)->next
; /* don't bother with it */
859 l_setbit(gch(curr
)->marked
, FINALIZEDBIT
); /* won't be finalized again */
860 *p
= gch(curr
)->next
; /* remove 'curr' from 'finobj' list */
861 gch(curr
)->next
= *lastnext
; /* link at the end of 'tobefnz' list */
863 lastnext
= &gch(curr
)->next
;
870 ** if object 'o' has a finalizer, remove it from 'allgc' list (must
871 ** search the list to find it) and link it in 'finobj' list.
873 void luaC_checkfinalizer (lua_State
*L
, GCObject
*o
, Table
*mt
) {
874 global_State
*g
= G(L
);
875 if (testbit(gch(o
)->marked
, SEPARATED
) || /* obj. is already separated... */
876 isfinalized(o
) || /* ... or is finalized... */
877 gfasttm(g
, mt
, TM_GC
) == NULL
) /* or has no finalizer? */
878 return; /* nothing to be done */
879 else { /* move 'o' to 'finobj' list */
881 GCheader
*ho
= gch(o
);
882 if (g
->sweepgc
== &ho
->next
) { /* avoid removing current sweep object */
883 lua_assert(issweepphase(g
));
884 g
->sweepgc
= sweeptolive(L
, g
->sweepgc
, NULL
);
886 /* search for pointer pointing to 'o' */
887 for (p
= &g
->allgc
; *p
!= o
; p
= &gch(*p
)->next
) { /* empty */ }
888 *p
= ho
->next
; /* remove 'o' from root list */
889 ho
->next
= g
->finobj
; /* link it in list 'finobj' */
891 l_setbit(ho
->marked
, SEPARATED
); /* mark it as such */
892 if (!keepinvariantout(g
)) /* not keeping invariant? */
893 makewhite(g
, o
); /* "sweep" object */
895 resetoldbit(o
); /* see MOVE OLD rule */
899 /* }====================================================== */
903 ** {======================================================
905 ** =======================================================
910 ** set a reasonable "time" to wait before starting a new GC cycle;
911 ** cycle will start when memory use hits threshold
913 static void setpause (global_State
*g
, l_mem estimate
) {
914 l_mem debt
, threshold
;
915 estimate
= estimate
/ PAUSEADJ
; /* adjust 'estimate' */
916 threshold
= (g
->gcpause
< MAX_LMEM
/ estimate
) /* overflow? */
917 ? estimate
* g
->gcpause
/* no overflow */
918 : MAX_LMEM
; /* overflow; truncate to maximum */
919 debt
= -cast(l_mem
, threshold
- gettotalbytes(g
));
920 luaE_setdebt(g
, debt
);
924 #define sweepphases \
925 (bitmask(GCSsweepstring) | bitmask(GCSsweepudata) | bitmask(GCSsweep))
929 ** enter first sweep phase (strings) and prepare pointers for other
930 ** sweep phases. The calls to 'sweeptolive' make pointers point to an
931 ** object inside the list (instead of to the header), so that the real
932 ** sweep do not need to skip objects created between "now" and the start
933 ** of the real sweep.
934 ** Returns how many objects it swept.
936 static int entersweep (lua_State
*L
) {
937 global_State
*g
= G(L
);
939 g
->gcstate
= GCSsweepstring
;
940 lua_assert(g
->sweepgc
== NULL
&& g
->sweepfin
== NULL
);
941 /* prepare to sweep strings, finalizable objects, and regular objects */
943 g
->sweepfin
= sweeptolive(L
, &g
->finobj
, &n
);
944 g
->sweepgc
= sweeptolive(L
, &g
->allgc
, &n
);
952 void luaC_changemode (lua_State
*L
, int mode
) {
953 global_State
*g
= G(L
);
954 if (mode
== g
->gckind
) return; /* nothing to change */
955 if (mode
== KGC_GEN
) { /* change to generational mode */
956 /* make sure gray lists are consistent */
957 luaC_runtilstate(L
, bitmask(GCSpropagate
));
958 g
->GCestimate
= gettotalbytes(g
);
961 else { /* change to incremental mode */
962 /* sweep all objects to turn them back to white
963 (as white has not changed, nothing extra will be collected) */
964 g
->gckind
= KGC_NORMAL
;
966 luaC_runtilstate(L
, ~sweepphases
);
972 ** call all pending finalizers
974 static void callallpendingfinalizers (lua_State
*L
, int propagateerrors
) {
975 global_State
*g
= G(L
);
977 resetoldbit(g
->tobefnz
);
978 GCTM(L
, propagateerrors
);
983 void luaC_freeallobjects (lua_State
*L
) {
984 global_State
*g
= G(L
);
986 separatetobefnz(L
, 1); /* separate all objects with finalizers */
987 lua_assert(g
->finobj
== NULL
);
988 callallpendingfinalizers(L
, 0);
989 g
->currentwhite
= WHITEBITS
; /* this "white" makes all objects look dead */
990 g
->gckind
= KGC_NORMAL
;
991 sweepwholelist(L
, &g
->finobj
); /* finalizers can create objs. in 'finobj' */
992 sweepwholelist(L
, &g
->allgc
);
993 for (i
= 0; i
< g
->strt
.size
; i
++) /* free all string lists */
994 sweepwholelist(L
, &g
->strt
.hash
[i
]);
995 lua_assert(g
->strt
.nuse
== 0);
999 static l_mem
atomic (lua_State
*L
) {
1000 global_State
*g
= G(L
);
1001 l_mem work
= -cast(l_mem
, g
->GCmemtrav
); /* start counting work */
1002 GCObject
*origweak
, *origall
;
1003 lua_assert(!iswhite(obj2gco(g
->mainthread
)));
1004 markobject(g
, L
); /* mark running thread */
1005 /* registry and global metatables may be changed by API */
1006 markvalue(g
, &g
->l_registry
);
1007 markmt(g
); /* mark basic metatables */
1008 /* remark occasional upvalues of (maybe) dead threads */
1010 propagateall(g
); /* propagate changes */
1011 work
+= g
->GCmemtrav
; /* stop counting (do not (re)count grays) */
1012 /* traverse objects caught by write barrier and by 'remarkupvals' */
1014 work
-= g
->GCmemtrav
; /* restart counting */
1015 convergeephemerons(g
);
1016 /* at this point, all strongly accessible objects are marked. */
1017 /* clear values from weak tables, before checking finalizers */
1018 clearvalues(g
, g
->weak
, NULL
);
1019 clearvalues(g
, g
->allweak
, NULL
);
1020 origweak
= g
->weak
; origall
= g
->allweak
;
1021 work
+= g
->GCmemtrav
; /* stop counting (objects being finalized) */
1022 separatetobefnz(L
, 0); /* separate objects to be finalized */
1023 markbeingfnz(g
); /* mark objects that will be finalized */
1024 propagateall(g
); /* remark, to propagate `preserveness' */
1025 work
-= g
->GCmemtrav
; /* restart counting */
1026 convergeephemerons(g
);
1027 /* at this point, all resurrected objects are marked. */
1028 /* remove dead objects from weak tables */
1029 clearkeys(g
, g
->ephemeron
, NULL
); /* clear keys from all ephemeron tables */
1030 clearkeys(g
, g
->allweak
, NULL
); /* clear keys from all allweak tables */
1031 /* clear values from resurrected weak tables */
1032 clearvalues(g
, g
->weak
, origweak
);
1033 clearvalues(g
, g
->allweak
, origall
);
1034 g
->currentwhite
= cast_byte(otherwhite(g
)); /* flip current white */
1035 work
+= g
->GCmemtrav
; /* complete counting */
1036 return work
; /* estimate of memory marked by 'atomic' */
1040 static lu_mem
singlestep (lua_State
*L
) {
1041 global_State
*g
= G(L
);
1042 switch (g
->gcstate
) {
1044 /* start to count memory traversed */
1045 g
->GCmemtrav
= g
->strt
.size
* sizeof(GCObject
*);
1046 lua_assert(!isgenerational(g
));
1047 restartcollection(g
);
1048 g
->gcstate
= GCSpropagate
;
1049 return g
->GCmemtrav
;
1051 case GCSpropagate
: {
1053 lu_mem oldtrav
= g
->GCmemtrav
;
1055 return g
->GCmemtrav
- oldtrav
; /* memory traversed in this step */
1057 else { /* no more `gray' objects */
1060 g
->gcstate
= GCSatomic
; /* finish mark phase */
1061 g
->GCestimate
= g
->GCmemtrav
; /* save what was counted */;
1062 work
= atomic(L
); /* add what was traversed by 'atomic' */
1063 g
->GCestimate
+= work
; /* estimate of total memory traversed */
1065 return work
+ sw
* GCSWEEPCOST
;
1068 case GCSsweepstring
: {
1070 for (i
= 0; i
< GCSWEEPMAX
&& g
->sweepstrgc
+ i
< g
->strt
.size
; i
++)
1071 sweepwholelist(L
, &g
->strt
.hash
[g
->sweepstrgc
+ i
]);
1073 if (g
->sweepstrgc
>= g
->strt
.size
) /* no more strings to sweep? */
1074 g
->gcstate
= GCSsweepudata
;
1075 return i
* GCSWEEPCOST
;
1077 case GCSsweepudata
: {
1079 g
->sweepfin
= sweeplist(L
, g
->sweepfin
, GCSWEEPMAX
);
1080 return GCSWEEPMAX
*GCSWEEPCOST
;
1083 g
->gcstate
= GCSsweep
;
1089 g
->sweepgc
= sweeplist(L
, g
->sweepgc
, GCSWEEPMAX
);
1090 return GCSWEEPMAX
*GCSWEEPCOST
;
1093 /* sweep main thread */
1094 GCObject
*mt
= obj2gco(g
->mainthread
);
1095 sweeplist(L
, &mt
, 1);
1097 g
->gcstate
= GCSpause
; /* finish collection */
1101 default: lua_assert(0); return 0;
1107 ** advances the garbage collector until it reaches a state allowed
1110 void luaC_runtilstate (lua_State
*L
, int statesmask
) {
1111 global_State
*g
= G(L
);
1112 while (!testbit(statesmask
, g
->gcstate
))
1117 static void generationalcollection (lua_State
*L
) {
1118 global_State
*g
= G(L
);
1119 lua_assert(g
->gcstate
== GCSpropagate
);
1120 if (g
->GCestimate
== 0) { /* signal for another major collection? */
1121 luaC_fullgc(L
, 0); /* perform a full regular collection */
1122 g
->GCestimate
= gettotalbytes(g
); /* update control */
1125 lu_mem estimate
= g
->GCestimate
;
1126 luaC_runtilstate(L
, bitmask(GCSpause
)); /* run complete (minor) cycle */
1127 g
->gcstate
= GCSpropagate
; /* skip restart */
1128 if (gettotalbytes(g
) > (estimate
/ 100) * g
->gcmajorinc
)
1129 g
->GCestimate
= 0; /* signal for a major collection */
1131 g
->GCestimate
= estimate
; /* keep estimate from last major coll. */
1134 setpause(g
, gettotalbytes(g
));
1135 lua_assert(g
->gcstate
== GCSpropagate
);
1139 static void incstep (lua_State
*L
) {
1140 global_State
*g
= G(L
);
1141 l_mem debt
= g
->GCdebt
;
1142 int stepmul
= g
->gcstepmul
;
1143 if (stepmul
< 40) stepmul
= 40; /* avoid ridiculous low values (and 0) */
1144 /* convert debt from Kb to 'work units' (avoid zero debt and overflows) */
1145 debt
= (debt
/ STEPMULADJ
) + 1;
1146 debt
= (debt
< MAX_LMEM
/ stepmul
) ? debt
* stepmul
: MAX_LMEM
;
1147 do { /* always perform at least one single step */
1148 lu_mem work
= singlestep(L
); /* do some work */
1150 } while (debt
> -GCSTEPSIZE
&& g
->gcstate
!= GCSpause
);
1151 if (g
->gcstate
== GCSpause
)
1152 setpause(g
, g
->GCestimate
); /* pause until next cycle */
1154 debt
= (debt
/ stepmul
) * STEPMULADJ
; /* convert 'work units' to Kb */
1155 luaE_setdebt(g
, debt
);
1161 ** performs a basic GC step
1163 void luaC_forcestep (lua_State
*L
) {
1164 global_State
*g
= G(L
);
1166 if (isgenerational(g
)) generationalcollection(L
);
1168 /* run a few finalizers (or all of them at the end of a collect cycle) */
1169 for (i
= 0; g
->tobefnz
&& (i
< GCFINALIZENUM
|| g
->gcstate
== GCSpause
); i
++)
1170 GCTM(L
, 1); /* call one finalizer */
1175 ** performs a basic GC step only if collector is running
1177 void luaC_step (lua_State
*L
) {
1178 global_State
*g
= G(L
);
1179 if (g
->gcrunning
) luaC_forcestep(L
);
1180 else luaE_setdebt(g
, -GCSTEPSIZE
); /* avoid being called too often */
1186 ** performs a full GC cycle; if "isemergency", does not call
1187 ** finalizers (which could change stack positions)
1189 void luaC_fullgc (lua_State
*L
, int isemergency
) {
1190 global_State
*g
= G(L
);
1191 int origkind
= g
->gckind
;
1192 lua_assert(origkind
!= KGC_EMERGENCY
);
1193 if (isemergency
) /* do not run finalizers during emergency GC */
1194 g
->gckind
= KGC_EMERGENCY
;
1196 g
->gckind
= KGC_NORMAL
;
1197 callallpendingfinalizers(L
, 1);
1199 if (keepinvariant(g
)) { /* may there be some black objects? */
1200 /* must sweep all objects to turn them back to white
1201 (as white has not changed, nothing will be collected) */
1204 /* finish any pending sweep phase to start a new cycle */
1205 luaC_runtilstate(L
, bitmask(GCSpause
));
1206 luaC_runtilstate(L
, ~bitmask(GCSpause
)); /* start new collection */
1207 luaC_runtilstate(L
, bitmask(GCSpause
)); /* run entire collection */
1208 if (origkind
== KGC_GEN
) { /* generational mode? */
1209 /* generational mode must be kept in propagate phase */
1210 luaC_runtilstate(L
, bitmask(GCSpropagate
));
1212 g
->gckind
= (lu_byte
)origkind
;
1213 setpause(g
, gettotalbytes(g
));
1214 if (!isemergency
) /* do not run finalizers during emergency GC */
1215 callallpendingfinalizers(L
, 1);
1218 /* }====================================================== */