]>
git.proxmox.com Git - mirror_zfs.git/blob - module/lua/lgc.c
3 ** $Id: lgc.c,v 2.140.1.3 2014/09/01 16:55:08 roberto Exp $
5 ** See Copyright Notice in lua.h
11 #include <sys/lua/lua.h>
27 ** cost of sweeping one element (the size of a small object divided
28 ** by some adjust for the sweep speed)
30 #define GCSWEEPCOST ((sizeof(TString) + 4) / 4)
32 /* maximum number of elements to sweep in each single step */
33 #define GCSWEEPMAX (cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4))
35 /* maximum number of finalizers to call in each GC step */
36 #define GCFINALIZENUM 4
40 ** macro to adjust 'stepmul': 'stepmul' is actually used like
41 ** 'stepmul / STEPMULADJ' (value chosen by tests)
43 #define STEPMULADJ 200
47 ** macro to adjust 'pause': 'pause' is actually used like
48 ** 'pause / PAUSEADJ' (value chosen by tests)
54 ** 'makewhite' erases all color bits plus the old bit and then
55 ** sets only the current white bit
57 #define maskcolors (~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS))
58 #define makewhite(g,x) \
59 (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g)))
61 #define white2gray(x) resetbits(gch(x)->marked, WHITEBITS)
62 #define black2gray(x) resetbit(gch(x)->marked, BLACKBIT)
65 #define isfinalized(x) testbit(gch(x)->marked, FINALIZEDBIT)
67 #define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n)))
70 #define checkconsistency(obj) \
71 lua_longassert(!iscollectable(obj) || righttt(obj))
74 #define markvalue(g,o) { checkconsistency(o); \
75 if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
77 #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \
78 reallymarkobject(g, obj2gco(t)); }
80 static void reallymarkobject (global_State
*g
, GCObject
*o
);
84 ** {======================================================
86 ** =======================================================
91 ** one after last element in a hash array
93 #define gnodelast(h) gnode(h, cast(size_t, sizenode(h)))
97 ** link table 'h' into list pointed by 'p'
99 #define linktable(h,p) ((h)->gclist = *(p), *(p) = obj2gco(h))
103 ** if key is not marked, mark its entry as dead (therefore removing it
106 static void removeentry (Node
*n
) {
107 lua_assert(ttisnil(gval(n
)));
108 if (valiswhite(gkey(n
)))
109 setdeadvalue(gkey(n
)); /* unused and unmarked key; remove it */
114 ** tells whether a key or value can be cleared from a weak
115 ** table. Non-collectable objects are never removed from weak
116 ** tables. Strings behave as `values', so are never removed too. for
117 ** other objects: if really collected, cannot keep them; for objects
118 ** being finalized, keep them in keys, but not in values
120 static int iscleared (global_State
*g
, const TValue
*o
) {
121 if (!iscollectable(o
)) return 0;
122 else if (ttisstring(o
)) {
123 markobject(g
, rawtsvalue(o
)); /* strings are `values', so are never weak */
126 else return iswhite(gcvalue(o
));
131 ** barrier that moves collector forward, that is, mark the white object
132 ** being pointed by a black object.
134 void luaC_barrier_ (lua_State
*L
, GCObject
*o
, GCObject
*v
) {
135 global_State
*g
= G(L
);
136 lua_assert(isblack(o
) && iswhite(v
) && !isdead(g
, v
) && !isdead(g
, o
));
137 lua_assert(g
->gcstate
!= GCSpause
);
138 lua_assert(gch(o
)->tt
!= LUA_TTABLE
);
139 if (keepinvariantout(g
)) /* must keep invariant? */
140 reallymarkobject(g
, v
); /* restore invariant */
141 else { /* sweep phase */
142 lua_assert(issweepphase(g
));
143 makewhite(g
, o
); /* mark main obj. as white to avoid other barriers */
149 ** barrier that moves collector backward, that is, mark the black object
150 ** pointing to a white object as gray again. (Current implementation
151 ** only works for tables; access to 'gclist' is not uniform across
154 void luaC_barrierback_ (lua_State
*L
, GCObject
*o
) {
155 global_State
*g
= G(L
);
156 lua_assert(isblack(o
) && !isdead(g
, o
) && gch(o
)->tt
== LUA_TTABLE
);
157 black2gray(o
); /* make object gray (again) */
158 gco2t(o
)->gclist
= g
->grayagain
;
164 ** barrier for prototypes. When creating first closure (cache is
165 ** NULL), use a forward barrier; this may be the only closure of the
166 ** prototype (if it is a "regular" function, with a single instance)
167 ** and the prototype may be big, so it is better to avoid traversing
168 ** it again. Otherwise, use a backward barrier, to avoid marking all
169 ** possible instances.
171 LUAI_FUNC
void luaC_barrierproto_ (lua_State
*L
, Proto
*p
, Closure
*c
) {
172 global_State
*g
= G(L
);
173 lua_assert(isblack(obj2gco(p
)));
174 if (p
->cache
== NULL
) { /* first time? */
175 luaC_objbarrier(L
, p
, c
);
177 else { /* use a backward barrier */
178 black2gray(obj2gco(p
)); /* make prototype gray (again) */
179 p
->gclist
= g
->grayagain
;
180 g
->grayagain
= obj2gco(p
);
186 ** check color (and invariants) for an upvalue that was closed,
187 ** i.e., moved into the 'allgc' list
189 void luaC_checkupvalcolor (global_State
*g
, UpVal
*uv
) {
190 GCObject
*o
= obj2gco(uv
);
191 lua_assert(!isblack(o
)); /* open upvalues are never black */
193 if (keepinvariant(g
)) {
194 resetoldbit(o
); /* see MOVE OLD rule */
195 gray2black(o
); /* it is being visited now */
199 lua_assert(issweepphase(g
));
207 ** create a new collectable object (with given type and size) and link
208 ** it to '*list'. 'offset' tells how many bytes to allocate before the
209 ** object itself (used only by states).
211 GCObject
*luaC_newobj (lua_State
*L
, int tt
, size_t sz
, GCObject
**list
,
213 global_State
*g
= G(L
);
214 char *raw
= cast(char *, luaM_newobject(L
, novariant(tt
), sz
));
215 GCObject
*o
= obj2gco(raw
+ offset
);
217 list
= &g
->allgc
; /* standard list for collectable objects */
218 gch(o
)->marked
= luaC_white(g
);
220 gch(o
)->next
= *list
;
225 /* }====================================================== */
230 ** {======================================================
232 ** =======================================================
237 ** mark an object. Userdata, strings, and closed upvalues are visited
238 ** and turned black here. Other objects are marked gray and added
239 ** to appropriate list to be visited (and turned black) later. (Open
240 ** upvalues are already linked in 'headuv' list.)
242 static void reallymarkobject (global_State
*g
, GCObject
*o
) {
245 switch (gch(o
)->tt
) {
248 size
= sizestring(gco2ts(o
));
249 break; /* nothing else to mark; make it black */
251 case LUA_TUSERDATA
: {
252 Table
*mt
= gco2u(o
)->metatable
;
254 markobject(g
, gco2u(o
)->env
);
255 size
= sizeudata(gco2u(o
));
259 UpVal
*uv
= gco2uv(o
);
261 if (uv
->v
!= &uv
->u
.value
) /* open? */
262 return; /* open upvalues remain gray */
263 size
= sizeof(UpVal
);
267 gco2lcl(o
)->gclist
= g
->gray
;
272 gco2ccl(o
)->gclist
= g
->gray
;
277 linktable(gco2t(o
), &g
->gray
);
281 gco2th(o
)->gclist
= g
->gray
;
286 gco2p(o
)->gclist
= g
->gray
;
290 default: lua_assert(0); return;
293 g
->GCmemtrav
+= size
;
298 ** mark metamethods for basic types
300 static void markmt (global_State
*g
) {
302 for (i
=0; i
< LUA_NUMTAGS
; i
++)
303 markobject(g
, g
->mt
[i
]);
308 ** mark all objects in list of being-finalized
310 static void markbeingfnz (global_State
*g
) {
312 for (o
= g
->tobefnz
; o
!= NULL
; o
= gch(o
)->next
) {
314 reallymarkobject(g
, o
);
320 ** mark all values stored in marked open upvalues. (See comment in
323 static void remarkupvals (global_State
*g
) {
325 for (uv
= g
->uvhead
.u
.l
.next
; uv
!= &g
->uvhead
; uv
= uv
->u
.l
.next
) {
326 if (isgray(obj2gco(uv
)))
333 ** mark root set and reset all gray lists, to start a new
334 ** incremental (or full) collection
336 static void restartcollection (global_State
*g
) {
337 g
->gray
= g
->grayagain
= NULL
;
338 g
->weak
= g
->allweak
= g
->ephemeron
= NULL
;
339 markobject(g
, g
->mainthread
);
340 markvalue(g
, &g
->l_registry
);
342 markbeingfnz(g
); /* mark any finalizing object left from previous cycle */
345 /* }====================================================== */
349 ** {======================================================
350 ** Traverse functions
351 ** =======================================================
354 static void traverseweakvalue (global_State
*g
, Table
*h
) {
355 Node
*n
, *limit
= gnodelast(h
);
356 /* if there is array part, assume it may have white values (do not
357 traverse it just to check) */
358 int hasclears
= (h
->sizearray
> 0);
359 for (n
= gnode(h
, 0); n
< limit
; n
++) {
361 if (ttisnil(gval(n
))) /* entry is empty? */
362 removeentry(n
); /* remove it */
364 lua_assert(!ttisnil(gkey(n
)));
365 markvalue(g
, gkey(n
)); /* mark key */
366 if (!hasclears
&& iscleared(g
, gval(n
))) /* is there a white value? */
367 hasclears
= 1; /* table will have to be cleared */
371 linktable(h
, &g
->weak
); /* has to be cleared later */
372 else /* no white values */
373 linktable(h
, &g
->grayagain
); /* no need to clean */
377 static int traverseephemeron (global_State
*g
, Table
*h
) {
378 int marked
= 0; /* true if an object is marked in this traversal */
379 int hasclears
= 0; /* true if table has white keys */
380 int prop
= 0; /* true if table has entry "white-key -> white-value" */
381 Node
*n
, *limit
= gnodelast(h
);
383 /* traverse array part (numeric keys are 'strong') */
384 for (i
= 0; i
< h
->sizearray
; i
++) {
385 if (valiswhite(&h
->array
[i
])) {
387 reallymarkobject(g
, gcvalue(&h
->array
[i
]));
390 /* traverse hash part */
391 for (n
= gnode(h
, 0); n
< limit
; n
++) {
393 if (ttisnil(gval(n
))) /* entry is empty? */
394 removeentry(n
); /* remove it */
395 else if (iscleared(g
, gkey(n
))) { /* key is not marked (yet)? */
396 hasclears
= 1; /* table must be cleared */
397 if (valiswhite(gval(n
))) /* value not marked yet? */
398 prop
= 1; /* must propagate again */
400 else if (valiswhite(gval(n
))) { /* value not marked yet? */
402 reallymarkobject(g
, gcvalue(gval(n
))); /* mark it now */
405 if (g
->gcstate
!= GCSatomic
|| prop
)
406 linktable(h
, &g
->ephemeron
); /* have to propagate again */
407 else if (hasclears
) /* does table have white keys? */
408 linktable(h
, &g
->allweak
); /* may have to clean white keys */
409 else /* no white keys */
410 linktable(h
, &g
->grayagain
); /* no need to clean */
415 static void traversestrongtable (global_State
*g
, Table
*h
) {
416 Node
*n
, *limit
= gnodelast(h
);
418 for (i
= 0; i
< h
->sizearray
; i
++) /* traverse array part */
419 markvalue(g
, &h
->array
[i
]);
420 for (n
= gnode(h
, 0); n
< limit
; n
++) { /* traverse hash part */
422 if (ttisnil(gval(n
))) /* entry is empty? */
423 removeentry(n
); /* remove it */
425 lua_assert(!ttisnil(gkey(n
)));
426 markvalue(g
, gkey(n
)); /* mark key */
427 markvalue(g
, gval(n
)); /* mark value */
433 static lu_mem
traversetable (global_State
*g
, Table
*h
) {
434 const char *weakkey
, *weakvalue
;
435 const TValue
*mode
= gfasttm(g
, h
->metatable
, TM_MODE
);
436 markobject(g
, h
->metatable
);
437 if (mode
&& ttisstring(mode
) && /* is there a weak mode? */
438 ((weakkey
= strchr(svalue(mode
), 'k')),
439 (weakvalue
= strchr(svalue(mode
), 'v')),
440 (weakkey
|| weakvalue
))) { /* is really weak? */
441 black2gray(obj2gco(h
)); /* keep table gray */
442 if (!weakkey
) /* strong keys? */
443 traverseweakvalue(g
, h
);
444 else if (!weakvalue
) /* strong values? */
445 traverseephemeron(g
, h
);
447 linktable(h
, &g
->allweak
); /* nothing to traverse now */
450 traversestrongtable(g
, h
);
451 return sizeof(Table
) + sizeof(TValue
) * h
->sizearray
+
452 sizeof(Node
) * cast(size_t, sizenode(h
));
456 static int traverseproto (global_State
*g
, Proto
*f
) {
458 if (f
->cache
&& iswhite(obj2gco(f
->cache
)))
459 f
->cache
= NULL
; /* allow cache to be collected */
460 markobject(g
, f
->source
);
461 for (i
= 0; i
< f
->sizek
; i
++) /* mark literals */
462 markvalue(g
, &f
->k
[i
]);
463 for (i
= 0; i
< f
->sizeupvalues
; i
++) /* mark upvalue names */
464 markobject(g
, f
->upvalues
[i
].name
);
465 for (i
= 0; i
< f
->sizep
; i
++) /* mark nested protos */
466 markobject(g
, f
->p
[i
]);
467 for (i
= 0; i
< f
->sizelocvars
; i
++) /* mark local-variable names */
468 markobject(g
, f
->locvars
[i
].varname
);
469 return sizeof(Proto
) + sizeof(Instruction
) * f
->sizecode
+
470 sizeof(Proto
*) * f
->sizep
+
471 sizeof(TValue
) * f
->sizek
+
472 sizeof(int) * f
->sizelineinfo
+
473 sizeof(LocVar
) * f
->sizelocvars
+
474 sizeof(Upvaldesc
) * f
->sizeupvalues
;
478 static lu_mem
traverseCclosure (global_State
*g
, CClosure
*cl
) {
480 for (i
= 0; i
< cl
->nupvalues
; i
++) /* mark its upvalues */
481 markvalue(g
, &cl
->upvalue
[i
]);
482 return sizeCclosure(cl
->nupvalues
);
485 static lu_mem
traverseLclosure (global_State
*g
, LClosure
*cl
) {
487 markobject(g
, cl
->p
); /* mark its prototype */
488 for (i
= 0; i
< cl
->nupvalues
; i
++) /* mark its upvalues */
489 markobject(g
, cl
->upvals
[i
]);
490 return sizeLclosure(cl
->nupvalues
);
494 static lu_mem
traversestack (global_State
*g
, lua_State
*th
) {
498 return 1; /* stack not completely built yet */
499 for (; o
< th
->top
; o
++) /* mark live elements in the stack */
501 if (g
->gcstate
== GCSatomic
) { /* final traversal? */
502 StkId lim
= th
->stack
+ th
->stacksize
; /* real end of stack */
503 for (; o
< lim
; o
++) /* clear not-marked stack slice */
506 else { /* count call infos to compute size */
508 for (ci
= &th
->base_ci
; ci
!= th
->ci
; ci
= ci
->next
)
511 return sizeof(lua_State
) + sizeof(TValue
) * th
->stacksize
+
512 sizeof(CallInfo
) * n
;
517 ** traverse one gray object, turning it to black (except for threads,
518 ** which are always gray).
520 static void propagatemark (global_State
*g
) {
522 GCObject
*o
= g
->gray
;
523 lua_assert(isgray(o
));
525 switch (gch(o
)->tt
) {
528 g
->gray
= h
->gclist
; /* remove from 'gray' list */
529 size
= traversetable(g
, h
);
533 LClosure
*cl
= gco2lcl(o
);
534 g
->gray
= cl
->gclist
; /* remove from 'gray' list */
535 size
= traverseLclosure(g
, cl
);
539 CClosure
*cl
= gco2ccl(o
);
540 g
->gray
= cl
->gclist
; /* remove from 'gray' list */
541 size
= traverseCclosure(g
, cl
);
545 lua_State
*th
= gco2th(o
);
546 g
->gray
= th
->gclist
; /* remove from 'gray' list */
547 th
->gclist
= g
->grayagain
;
548 g
->grayagain
= o
; /* insert into 'grayagain' list */
550 size
= traversestack(g
, th
);
555 g
->gray
= p
->gclist
; /* remove from 'gray' list */
556 size
= traverseproto(g
, p
);
559 default: lua_assert(0); return;
561 g
->GCmemtrav
+= size
;
565 static void propagateall (global_State
*g
) {
566 while (g
->gray
) propagatemark(g
);
570 static void propagatelist (global_State
*g
, GCObject
*l
) {
571 lua_assert(g
->gray
== NULL
); /* no grays left */
573 propagateall(g
); /* traverse all elements from 'l' */
577 ** retraverse all gray lists. Because tables may be reinserted in other
578 ** lists when traversed, traverse the original lists to avoid traversing
579 ** twice the same table (which is not wrong, but inefficient)
581 static void retraversegrays (global_State
*g
) {
582 GCObject
*weak
= g
->weak
; /* save original lists */
583 GCObject
*grayagain
= g
->grayagain
;
584 GCObject
*ephemeron
= g
->ephemeron
;
585 g
->weak
= g
->grayagain
= g
->ephemeron
= NULL
;
586 propagateall(g
); /* traverse main gray list */
587 propagatelist(g
, grayagain
);
588 propagatelist(g
, weak
);
589 propagatelist(g
, ephemeron
);
593 static void convergeephemerons (global_State
*g
) {
597 GCObject
*next
= g
->ephemeron
; /* get ephemeron list */
598 g
->ephemeron
= NULL
; /* tables will return to this list when traversed */
600 while ((w
= next
) != NULL
) {
601 next
= gco2t(w
)->gclist
;
602 if (traverseephemeron(g
, gco2t(w
))) { /* traverse marked some value? */
603 propagateall(g
); /* propagate changes */
604 changed
= 1; /* will have to revisit all ephemeron tables */
610 /* }====================================================== */
614 ** {======================================================
616 ** =======================================================
621 ** clear entries with unmarked keys from all weaktables in list 'l' up
624 static void clearkeys (global_State
*g
, GCObject
*l
, GCObject
*f
) {
625 for (; l
!= f
; l
= gco2t(l
)->gclist
) {
627 Node
*n
, *limit
= gnodelast(h
);
628 for (n
= gnode(h
, 0); n
< limit
; n
++) {
629 if (!ttisnil(gval(n
)) && (iscleared(g
, gkey(n
)))) {
630 setnilvalue(gval(n
)); /* remove value ... */
631 removeentry(n
); /* and remove entry from table */
639 ** clear entries with unmarked values from all weaktables in list 'l' up
642 static void clearvalues (global_State
*g
, GCObject
*l
, GCObject
*f
) {
643 for (; l
!= f
; l
= gco2t(l
)->gclist
) {
645 Node
*n
, *limit
= gnodelast(h
);
647 for (i
= 0; i
< h
->sizearray
; i
++) {
648 TValue
*o
= &h
->array
[i
];
649 if (iscleared(g
, o
)) /* value was collected? */
650 setnilvalue(o
); /* remove value */
652 for (n
= gnode(h
, 0); n
< limit
; n
++) {
653 if (!ttisnil(gval(n
)) && iscleared(g
, gval(n
))) {
654 setnilvalue(gval(n
)); /* remove value ... */
655 removeentry(n
); /* and remove entry from table */
662 static void freeobj (lua_State
*L
, GCObject
*o
) {
663 switch (gch(o
)->tt
) {
664 case LUA_TPROTO
: luaF_freeproto(L
, gco2p(o
)); break;
666 luaM_freemem(L
, o
, sizeLclosure(gco2lcl(o
)->nupvalues
));
670 luaM_freemem(L
, o
, sizeCclosure(gco2ccl(o
)->nupvalues
));
673 case LUA_TUPVAL
: luaF_freeupval(L
, gco2uv(o
)); break;
674 case LUA_TTABLE
: luaH_free(L
, gco2t(o
)); break;
675 case LUA_TTHREAD
: luaE_freethread(L
, gco2th(o
)); break;
676 case LUA_TUSERDATA
: luaM_freemem(L
, o
, sizeudata(gco2u(o
))); break;
681 luaM_freemem(L
, o
, sizestring(gco2ts(o
)));
684 default: lua_assert(0);
689 #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM)
690 static GCObject
**sweeplist (lua_State
*L
, GCObject
**p
, lu_mem count
);
694 ** sweep the (open) upvalues of a thread and resize its stack and
695 ** list of call-info structures.
697 static void sweepthread (lua_State
*L
, lua_State
*L1
) {
698 if (L1
->stack
== NULL
) return; /* stack not completely built yet */
699 sweepwholelist(L
, &L1
->openupval
); /* sweep open upvalues */
700 luaE_freeCI(L1
); /* free extra CallInfo slots */
701 /* should not change the stack during an emergency gc cycle */
702 if (G(L
)->gckind
!= KGC_EMERGENCY
)
703 luaD_shrinkstack(L1
);
708 ** sweep at most 'count' elements from a list of GCObjects erasing dead
709 ** objects, where a dead (not alive) object is one marked with the "old"
710 ** (non current) white and not fixed.
711 ** In non-generational mode, change all non-dead objects back to white,
712 ** preparing for next collection cycle.
713 ** In generational mode, keep black objects black, and also mark them as
714 ** old; stop when hitting an old object, as all objects after that
715 ** one will be old too.
716 ** When object is a thread, sweep its list of open upvalues too.
718 static GCObject
**sweeplist (lua_State
*L
, GCObject
**p
, lu_mem count
) {
719 global_State
*g
= G(L
);
720 int ow
= otherwhite(g
);
721 int toclear
, toset
; /* bits to clear and to set in all live objects */
722 int tostop
; /* stop sweep when this is true */
723 if (isgenerational(g
)) { /* generational mode? */
724 toclear
= ~0; /* clear nothing */
725 toset
= bitmask(OLDBIT
); /* set the old bit of all surviving objects */
726 tostop
= bitmask(OLDBIT
); /* do not sweep old generation */
728 else { /* normal mode */
729 toclear
= maskcolors
; /* clear all color bits + old bit */
730 toset
= luaC_white(g
); /* make object white */
731 tostop
= 0; /* do not stop */
733 while (*p
!= NULL
&& count
-- > 0) {
735 int marked
= gch(curr
)->marked
;
736 if (isdeadm(ow
, marked
)) { /* is 'curr' dead? */
737 *p
= gch(curr
)->next
; /* remove 'curr' from list */
738 freeobj(L
, curr
); /* erase 'curr' */
741 if (testbits(marked
, tostop
))
742 return NULL
; /* stop sweeping this list */
743 if (gch(curr
)->tt
== LUA_TTHREAD
)
744 sweepthread(L
, gco2th(curr
)); /* sweep thread's upvalues */
746 gch(curr
)->marked
= cast_byte((marked
& toclear
) | toset
);
747 p
= &gch(curr
)->next
; /* go to next element */
750 return (*p
== NULL
) ? NULL
: p
;
755 ** sweep a list until a live object (or end of list)
757 static GCObject
**sweeptolive (lua_State
*L
, GCObject
**p
, int *n
) {
762 p
= sweeplist(L
, p
, 1);
768 /* }====================================================== */
772 ** {======================================================
774 ** =======================================================
777 static void checkSizes (lua_State
*L
) {
778 global_State
*g
= G(L
);
779 if (g
->gckind
!= KGC_EMERGENCY
) { /* do not change sizes in emergency */
780 int hs
= g
->strt
.size
/ 2; /* half the size of the string table */
781 if (g
->strt
.nuse
< cast(lu_int32
, hs
)) /* using less than that half? */
782 luaS_resize(L
, hs
); /* halve its size */
783 luaZ_freebuffer(L
, &g
->buff
); /* free concatenation buffer */
788 static GCObject
*udata2finalize (global_State
*g
) {
789 GCObject
*o
= g
->tobefnz
; /* get first element */
790 lua_assert(isfinalized(o
));
791 g
->tobefnz
= gch(o
)->next
; /* remove it from 'tobefnz' list */
792 gch(o
)->next
= g
->allgc
; /* return it to 'allgc' list */
794 resetbit(gch(o
)->marked
, SEPARATED
); /* mark that it is not in 'tobefnz' */
795 lua_assert(!isold(o
)); /* see MOVE OLD rule */
796 if (!keepinvariantout(g
)) /* not keeping invariant? */
797 makewhite(g
, o
); /* "sweep" object */
802 static void dothecall (lua_State
*L
, void *ud
) {
804 luaD_call(L
, L
->top
- 2, 0, 0);
808 static void GCTM (lua_State
*L
, int propagateerrors
) {
809 global_State
*g
= G(L
);
812 setgcovalue(L
, &v
, udata2finalize(g
));
813 tm
= luaT_gettmbyobj(L
, &v
, TM_GC
);
814 if (tm
!= NULL
&& ttisfunction(tm
)) { /* is there a finalizer? */
816 lu_byte oldah
= L
->allowhook
;
817 int running
= g
->gcrunning
;
818 L
->allowhook
= 0; /* stop debug hooks during GC metamethod */
819 g
->gcrunning
= 0; /* avoid GC steps */
820 setobj2s(L
, L
->top
, tm
); /* push finalizer... */
821 setobj2s(L
, L
->top
+ 1, &v
); /* ... and its argument */
822 L
->top
+= 2; /* and (next line) call the finalizer */
823 status
= luaD_pcall(L
, dothecall
, NULL
, savestack(L
, L
->top
- 2), 0);
824 L
->allowhook
= oldah
; /* restore hooks */
825 g
->gcrunning
= running
; /* restore state */
826 if (status
!= LUA_OK
&& propagateerrors
) { /* error while running __gc? */
827 if (status
== LUA_ERRRUN
) { /* is there an error object? */
828 const char *msg
= (ttisstring(L
->top
- 1))
831 luaO_pushfstring(L
, "error in __gc metamethod (%s)", msg
);
832 status
= LUA_ERRGCMM
; /* error in __gc metamethod */
834 luaD_throw(L
, status
); /* re-throw error */
841 ** move all unreachable objects (or 'all' objects) that need
842 ** finalization from list 'finobj' to list 'tobefnz' (to be finalized)
844 static void separatetobefnz (lua_State
*L
, int all
) {
845 global_State
*g
= G(L
);
846 GCObject
**p
= &g
->finobj
;
848 GCObject
**lastnext
= &g
->tobefnz
;
849 /* find last 'next' field in 'tobefnz' list (to add elements in its end) */
850 while (*lastnext
!= NULL
)
851 lastnext
= &gch(*lastnext
)->next
;
852 while ((curr
= *p
) != NULL
) { /* traverse all finalizable objects */
853 lua_assert(!isfinalized(curr
));
854 lua_assert(testbit(gch(curr
)->marked
, SEPARATED
));
855 if (!(iswhite(curr
) || all
)) /* not being collected? */
856 p
= &gch(curr
)->next
; /* don't bother with it */
858 l_setbit(gch(curr
)->marked
, FINALIZEDBIT
); /* won't be finalized again */
859 *p
= gch(curr
)->next
; /* remove 'curr' from 'finobj' list */
860 gch(curr
)->next
= *lastnext
; /* link at the end of 'tobefnz' list */
862 lastnext
= &gch(curr
)->next
;
869 ** if object 'o' has a finalizer, remove it from 'allgc' list (must
870 ** search the list to find it) and link it in 'finobj' list.
872 void luaC_checkfinalizer (lua_State
*L
, GCObject
*o
, Table
*mt
) {
873 global_State
*g
= G(L
);
874 if (testbit(gch(o
)->marked
, SEPARATED
) || /* obj. is already separated... */
875 isfinalized(o
) || /* ... or is finalized... */
876 gfasttm(g
, mt
, TM_GC
) == NULL
) /* or has no finalizer? */
877 return; /* nothing to be done */
878 else { /* move 'o' to 'finobj' list */
880 GCheader
*ho
= gch(o
);
881 if (g
->sweepgc
== &ho
->next
) { /* avoid removing current sweep object */
882 lua_assert(issweepphase(g
));
883 g
->sweepgc
= sweeptolive(L
, g
->sweepgc
, NULL
);
885 /* search for pointer pointing to 'o' */
886 for (p
= &g
->allgc
; *p
!= o
; p
= &gch(*p
)->next
) { /* empty */ }
887 *p
= ho
->next
; /* remove 'o' from root list */
888 ho
->next
= g
->finobj
; /* link it in list 'finobj' */
890 l_setbit(ho
->marked
, SEPARATED
); /* mark it as such */
891 if (!keepinvariantout(g
)) /* not keeping invariant? */
892 makewhite(g
, o
); /* "sweep" object */
894 resetoldbit(o
); /* see MOVE OLD rule */
898 /* }====================================================== */
902 ** {======================================================
904 ** =======================================================
909 ** set a reasonable "time" to wait before starting a new GC cycle;
910 ** cycle will start when memory use hits threshold
912 static void setpause (global_State
*g
, l_mem estimate
) {
913 l_mem debt
, threshold
;
914 estimate
= estimate
/ PAUSEADJ
; /* adjust 'estimate' */
915 threshold
= (g
->gcpause
< MAX_LMEM
/ estimate
) /* overflow? */
916 ? estimate
* g
->gcpause
/* no overflow */
917 : MAX_LMEM
; /* overflow; truncate to maximum */
918 debt
= -cast(l_mem
, threshold
- gettotalbytes(g
));
919 luaE_setdebt(g
, debt
);
923 #define sweepphases \
924 (bitmask(GCSsweepstring) | bitmask(GCSsweepudata) | bitmask(GCSsweep))
928 ** enter first sweep phase (strings) and prepare pointers for other
929 ** sweep phases. The calls to 'sweeptolive' make pointers point to an
930 ** object inside the list (instead of to the header), so that the real
931 ** sweep do not need to skip objects created between "now" and the start
932 ** of the real sweep.
933 ** Returns how many objects it swept.
935 static int entersweep (lua_State
*L
) {
936 global_State
*g
= G(L
);
938 g
->gcstate
= GCSsweepstring
;
939 lua_assert(g
->sweepgc
== NULL
&& g
->sweepfin
== NULL
);
940 /* prepare to sweep strings, finalizable objects, and regular objects */
942 g
->sweepfin
= sweeptolive(L
, &g
->finobj
, &n
);
943 g
->sweepgc
= sweeptolive(L
, &g
->allgc
, &n
);
951 void luaC_changemode (lua_State
*L
, int mode
) {
952 global_State
*g
= G(L
);
953 if (mode
== g
->gckind
) return; /* nothing to change */
954 if (mode
== KGC_GEN
) { /* change to generational mode */
955 /* make sure gray lists are consistent */
956 luaC_runtilstate(L
, bitmask(GCSpropagate
));
957 g
->GCestimate
= gettotalbytes(g
);
960 else { /* change to incremental mode */
961 /* sweep all objects to turn them back to white
962 (as white has not changed, nothing extra will be collected) */
963 g
->gckind
= KGC_NORMAL
;
965 luaC_runtilstate(L
, ~sweepphases
);
971 ** call all pending finalizers
973 static void callallpendingfinalizers (lua_State
*L
, int propagateerrors
) {
974 global_State
*g
= G(L
);
976 resetoldbit(g
->tobefnz
);
977 GCTM(L
, propagateerrors
);
982 void luaC_freeallobjects (lua_State
*L
) {
983 global_State
*g
= G(L
);
985 separatetobefnz(L
, 1); /* separate all objects with finalizers */
986 lua_assert(g
->finobj
== NULL
);
987 callallpendingfinalizers(L
, 0);
988 g
->currentwhite
= WHITEBITS
; /* this "white" makes all objects look dead */
989 g
->gckind
= KGC_NORMAL
;
990 sweepwholelist(L
, &g
->finobj
); /* finalizers can create objs. in 'finobj' */
991 sweepwholelist(L
, &g
->allgc
);
992 for (i
= 0; i
< g
->strt
.size
; i
++) /* free all string lists */
993 sweepwholelist(L
, &g
->strt
.hash
[i
]);
994 lua_assert(g
->strt
.nuse
== 0);
998 static l_mem
atomic (lua_State
*L
) {
999 global_State
*g
= G(L
);
1000 l_mem work
= -cast(l_mem
, g
->GCmemtrav
); /* start counting work */
1001 GCObject
*origweak
, *origall
;
1002 lua_assert(!iswhite(obj2gco(g
->mainthread
)));
1003 markobject(g
, L
); /* mark running thread */
1004 /* registry and global metatables may be changed by API */
1005 markvalue(g
, &g
->l_registry
);
1006 markmt(g
); /* mark basic metatables */
1007 /* remark occasional upvalues of (maybe) dead threads */
1009 propagateall(g
); /* propagate changes */
1010 work
+= g
->GCmemtrav
; /* stop counting (do not (re)count grays) */
1011 /* traverse objects caught by write barrier and by 'remarkupvals' */
1013 work
-= g
->GCmemtrav
; /* restart counting */
1014 convergeephemerons(g
);
1015 /* at this point, all strongly accessible objects are marked. */
1016 /* clear values from weak tables, before checking finalizers */
1017 clearvalues(g
, g
->weak
, NULL
);
1018 clearvalues(g
, g
->allweak
, NULL
);
1019 origweak
= g
->weak
; origall
= g
->allweak
;
1020 work
+= g
->GCmemtrav
; /* stop counting (objects being finalized) */
1021 separatetobefnz(L
, 0); /* separate objects to be finalized */
1022 markbeingfnz(g
); /* mark objects that will be finalized */
1023 propagateall(g
); /* remark, to propagate `preserveness' */
1024 work
-= g
->GCmemtrav
; /* restart counting */
1025 convergeephemerons(g
);
1026 /* at this point, all resurrected objects are marked. */
1027 /* remove dead objects from weak tables */
1028 clearkeys(g
, g
->ephemeron
, NULL
); /* clear keys from all ephemeron tables */
1029 clearkeys(g
, g
->allweak
, NULL
); /* clear keys from all allweak tables */
1030 /* clear values from resurrected weak tables */
1031 clearvalues(g
, g
->weak
, origweak
);
1032 clearvalues(g
, g
->allweak
, origall
);
1033 g
->currentwhite
= cast_byte(otherwhite(g
)); /* flip current white */
1034 work
+= g
->GCmemtrav
; /* complete counting */
1035 return work
; /* estimate of memory marked by 'atomic' */
1039 static lu_mem
singlestep (lua_State
*L
) {
1040 global_State
*g
= G(L
);
1041 switch (g
->gcstate
) {
1043 /* start to count memory traversed */
1044 g
->GCmemtrav
= g
->strt
.size
* sizeof(GCObject
*);
1045 lua_assert(!isgenerational(g
));
1046 restartcollection(g
);
1047 g
->gcstate
= GCSpropagate
;
1048 return g
->GCmemtrav
;
1050 case GCSpropagate
: {
1052 lu_mem oldtrav
= g
->GCmemtrav
;
1054 return g
->GCmemtrav
- oldtrav
; /* memory traversed in this step */
1056 else { /* no more `gray' objects */
1059 g
->gcstate
= GCSatomic
; /* finish mark phase */
1060 g
->GCestimate
= g
->GCmemtrav
; /* save what was counted */;
1061 work
= atomic(L
); /* add what was traversed by 'atomic' */
1062 g
->GCestimate
+= work
; /* estimate of total memory traversed */
1064 return work
+ sw
* GCSWEEPCOST
;
1067 case GCSsweepstring
: {
1069 for (i
= 0; i
< GCSWEEPMAX
&& g
->sweepstrgc
+ i
< g
->strt
.size
; i
++)
1070 sweepwholelist(L
, &g
->strt
.hash
[g
->sweepstrgc
+ i
]);
1072 if (g
->sweepstrgc
>= g
->strt
.size
) /* no more strings to sweep? */
1073 g
->gcstate
= GCSsweepudata
;
1074 return i
* GCSWEEPCOST
;
1076 case GCSsweepudata
: {
1078 g
->sweepfin
= sweeplist(L
, g
->sweepfin
, GCSWEEPMAX
);
1079 return GCSWEEPMAX
*GCSWEEPCOST
;
1082 g
->gcstate
= GCSsweep
;
1088 g
->sweepgc
= sweeplist(L
, g
->sweepgc
, GCSWEEPMAX
);
1089 return GCSWEEPMAX
*GCSWEEPCOST
;
1092 /* sweep main thread */
1093 GCObject
*mt
= obj2gco(g
->mainthread
);
1094 sweeplist(L
, &mt
, 1);
1096 g
->gcstate
= GCSpause
; /* finish collection */
1100 default: lua_assert(0); return 0;
1106 ** advances the garbage collector until it reaches a state allowed
1109 void luaC_runtilstate (lua_State
*L
, int statesmask
) {
1110 global_State
*g
= G(L
);
1111 while (!testbit(statesmask
, g
->gcstate
))
1116 static void generationalcollection (lua_State
*L
) {
1117 global_State
*g
= G(L
);
1118 lua_assert(g
->gcstate
== GCSpropagate
);
1119 if (g
->GCestimate
== 0) { /* signal for another major collection? */
1120 luaC_fullgc(L
, 0); /* perform a full regular collection */
1121 g
->GCestimate
= gettotalbytes(g
); /* update control */
1124 lu_mem estimate
= g
->GCestimate
;
1125 luaC_runtilstate(L
, bitmask(GCSpause
)); /* run complete (minor) cycle */
1126 g
->gcstate
= GCSpropagate
; /* skip restart */
1127 if (gettotalbytes(g
) > (estimate
/ 100) * g
->gcmajorinc
)
1128 g
->GCestimate
= 0; /* signal for a major collection */
1130 g
->GCestimate
= estimate
; /* keep estimate from last major coll. */
1133 setpause(g
, gettotalbytes(g
));
1134 lua_assert(g
->gcstate
== GCSpropagate
);
1138 static void incstep (lua_State
*L
) {
1139 global_State
*g
= G(L
);
1140 l_mem debt
= g
->GCdebt
;
1141 int stepmul
= g
->gcstepmul
;
1142 if (stepmul
< 40) stepmul
= 40; /* avoid ridiculous low values (and 0) */
1143 /* convert debt from Kb to 'work units' (avoid zero debt and overflows) */
1144 debt
= (debt
/ STEPMULADJ
) + 1;
1145 debt
= (debt
< MAX_LMEM
/ stepmul
) ? debt
* stepmul
: MAX_LMEM
;
1146 do { /* always perform at least one single step */
1147 lu_mem work
= singlestep(L
); /* do some work */
1149 } while (debt
> -GCSTEPSIZE
&& g
->gcstate
!= GCSpause
);
1150 if (g
->gcstate
== GCSpause
)
1151 setpause(g
, g
->GCestimate
); /* pause until next cycle */
1153 debt
= (debt
/ stepmul
) * STEPMULADJ
; /* convert 'work units' to Kb */
1154 luaE_setdebt(g
, debt
);
1160 ** performs a basic GC step
1162 void luaC_forcestep (lua_State
*L
) {
1163 global_State
*g
= G(L
);
1165 if (isgenerational(g
)) generationalcollection(L
);
1167 /* run a few finalizers (or all of them at the end of a collect cycle) */
1168 for (i
= 0; g
->tobefnz
&& (i
< GCFINALIZENUM
|| g
->gcstate
== GCSpause
); i
++)
1169 GCTM(L
, 1); /* call one finalizer */
1174 ** performs a basic GC step only if collector is running
1176 void luaC_step (lua_State
*L
) {
1177 global_State
*g
= G(L
);
1178 if (g
->gcrunning
) luaC_forcestep(L
);
1179 else luaE_setdebt(g
, -GCSTEPSIZE
); /* avoid being called too often */
1185 ** performs a full GC cycle; if "isemergency", does not call
1186 ** finalizers (which could change stack positions)
1188 void luaC_fullgc (lua_State
*L
, int isemergency
) {
1189 global_State
*g
= G(L
);
1190 int origkind
= g
->gckind
;
1191 lua_assert(origkind
!= KGC_EMERGENCY
);
1192 if (isemergency
) /* do not run finalizers during emergency GC */
1193 g
->gckind
= KGC_EMERGENCY
;
1195 g
->gckind
= KGC_NORMAL
;
1196 callallpendingfinalizers(L
, 1);
1198 if (keepinvariant(g
)) { /* may there be some black objects? */
1199 /* must sweep all objects to turn them back to white
1200 (as white has not changed, nothing will be collected) */
1203 /* finish any pending sweep phase to start a new cycle */
1204 luaC_runtilstate(L
, bitmask(GCSpause
));
1205 luaC_runtilstate(L
, ~bitmask(GCSpause
)); /* start new collection */
1206 luaC_runtilstate(L
, bitmask(GCSpause
)); /* run entire collection */
1207 if (origkind
== KGC_GEN
) { /* generational mode? */
1208 /* generational mode must be kept in propagate phase */
1209 luaC_runtilstate(L
, bitmask(GCSpropagate
));
1211 g
->gckind
= origkind
;
1212 setpause(g
, gettotalbytes(g
));
1213 if (!isemergency
) /* do not run finalizers during emergency GC */
1214 callallpendingfinalizers(L
, 1);
1217 /* }====================================================== */