Line | Branch | Decision | Exec | Source |
---|---|---|---|---|
1 | /* | |||
2 | ** $Id: lgc.c $ | |||
3 | ** Garbage Collector | |||
4 | ** See Copyright Notice in lua.h | |||
5 | */ | |||
6 | ||||
7 | #define lgc_c | |||
8 | #define LUA_CORE | |||
9 | ||||
10 | #include "lprefix.h" | |||
11 | ||||
12 | #include <stdio.h> | |||
13 | #include <string.h> | |||
14 | ||||
15 | ||||
16 | #include "lua.h" | |||
17 | ||||
18 | #include "ldebug.h" | |||
19 | #include "ldo.h" | |||
20 | #include "lfunc.h" | |||
21 | #include "lgc.h" | |||
22 | #include "lmem.h" | |||
23 | #include "lobject.h" | |||
24 | #include "lstate.h" | |||
25 | #include "lstring.h" | |||
26 | #include "ltable.h" | |||
27 | #include "ltm.h" | |||
28 | ||||
29 | ||||
30 | /* | |||
31 | ** Maximum number of elements to sweep in each single step. | |||
32 | ** (Large enough to dissipate fixed overheads but small enough | |||
33 | ** to allow small steps for the collector.) | |||
34 | */ | |||
35 | #define GCSWEEPMAX 100 | |||
36 | ||||
37 | /* | |||
38 | ** Maximum number of finalizers to call in each single step. | |||
39 | */ | |||
40 | #define GCFINMAX 10 | |||
41 | ||||
42 | ||||
43 | /* | |||
44 | ** Cost of calling one finalizer. | |||
45 | */ | |||
46 | #define GCFINALIZECOST 50 | |||
47 | ||||
48 | ||||
49 | /* | |||
50 | ** The equivalent, in bytes, of one unit of "work" (visiting a slot, | |||
51 | ** sweeping an object, etc.) | |||
52 | */ | |||
53 | #define WORK2MEM sizeof(TValue) | |||
54 | ||||
55 | ||||
56 | /* | |||
57 | ** macro to adjust 'pause': 'pause' is actually used like | |||
58 | ** 'pause / PAUSEADJ' (value chosen by tests) | |||
59 | */ | |||
60 | #define PAUSEADJ 100 | |||
61 | ||||
62 | ||||
63 | /* mask with all color bits */ | |||
64 | #define maskcolors (bitmask(BLACKBIT) | WHITEBITS) | |||
65 | ||||
66 | /* mask with all GC bits */ | |||
67 | #define maskgcbits (maskcolors | AGEBITS) | |||
68 | ||||
69 | ||||
70 | /* macro to erase all color bits then set only the current white bit */ | |||
71 | #define makewhite(g,x) \ | |||
72 | (x->marked = cast_byte((x->marked & ~maskcolors) | luaC_white(g))) | |||
73 | ||||
74 | /* make an object gray (neither white nor black) */ | |||
75 | #define set2gray(x) resetbits(x->marked, maskcolors) | |||
76 | ||||
77 | ||||
78 | /* make an object black (coming from any color) */ | |||
79 | #define set2black(x) \ | |||
80 | (x->marked = cast_byte((x->marked & ~WHITEBITS) | bitmask(BLACKBIT))) | |||
81 | ||||
82 | ||||
83 | #define valiswhite(x) (iscollectable(x) && iswhite(gcvalue(x))) | |||
84 | ||||
85 | #define keyiswhite(n) (keyiscollectable(n) && iswhite(gckey(n))) | |||
86 | ||||
87 | ||||
88 | /* | |||
89 | ** Protected access to objects in values | |||
90 | */ | |||
91 | #define gcvalueN(o) (iscollectable(o) ? gcvalue(o) : NULL) | |||
92 | ||||
93 | ||||
94 | #define markvalue(g,o) { checkliveness(g->mainthread,o); \ | |||
95 | if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); } | |||
96 | ||||
97 | #define markkey(g, n) { if keyiswhite(n) reallymarkobject(g,gckey(n)); } | |||
98 | ||||
99 | #define markobject(g,t) { if (iswhite(t)) reallymarkobject(g, obj2gco(t)); } | |||
100 | ||||
101 | /* | |||
102 | ** mark an object that can be NULL (either because it is really optional, | |||
103 | ** or it was stripped as debug info, or inside an uncompleted structure) | |||
104 | */ | |||
105 | #define markobjectN(g,t) { if (t) markobject(g,t); } | |||
106 | ||||
107 | static void reallymarkobject (global_State *g, GCObject *o); | |||
108 | static lu_mem atomic (lua_State *L); | |||
109 | static void entersweep (lua_State *L); | |||
110 | ||||
111 | ||||
112 | /* | |||
113 | ** {====================================================== | |||
114 | ** Generic functions | |||
115 | ** ======================================================= | |||
116 | */ | |||
117 | ||||
118 | ||||
119 | /* | |||
120 | ** one after last element in a hash array | |||
121 | */ | |||
122 | #define gnodelast(h) gnode(h, cast_sizet(sizenode(h))) | |||
123 | ||||
124 | ||||
125 | 63963 | static GCObject **getgclist (GCObject *o) { | ||
126 |
4/7✓ Branch 0 taken 23484 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 17304 times.
✓ Branch 3 taken 2781 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 20394 times.
✗ Branch 6 not taken.
|
63963 | switch (o->tt) { | |
127 |
1/1✓ Decision 'true' taken 23484 times.
|
23484 | case LUA_VTABLE: return &gco2t(o)->gclist; | |
128 | ✗ | case LUA_VLCL: return &gco2lcl(o)->gclist; | ||
129 |
1/1✓ Decision 'true' taken 17304 times.
|
17304 | case LUA_VCCL: return &gco2ccl(o)->gclist; | |
130 |
1/1✓ Decision 'true' taken 2781 times.
|
2781 | case LUA_VTHREAD: return &gco2th(o)->gclist; | |
131 | ✗ | case LUA_VPROTO: return &gco2p(o)->gclist; | ||
132 |
1/1✓ Decision 'true' taken 20394 times.
|
20394 | case LUA_VUSERDATA: { | |
133 | 20394 | Udata *u = gco2u(o); | ||
134 | lua_assert(u->nuvalue > 0); | |||
135 | 20394 | return &u->gclist; | ||
136 | } | |||
137 | ✗ | default: lua_assert(0); return 0; | ||
138 | } | |||
139 | } | |||
140 | ||||
141 | ||||
142 | /* | |||
143 | ** Link a collectable object 'o' with a known type into the list 'p'. | |||
144 | ** (Must be a macro to access the 'gclist' field in different types.) | |||
145 | */ | |||
146 | #define linkgclist(o,p) linkgclist_(obj2gco(o), &(o)->gclist, &(p)) | |||
147 | ||||
148 | 32445 | static void linkgclist_ (GCObject *o, GCObject **pnext, GCObject **list) { | ||
149 | lua_assert(!isgray(o)); /* cannot be in a gray list */ | |||
150 | 32445 | *pnext = *list; | ||
151 | 32445 | *list = o; | ||
152 | 32445 | set2gray(o); /* now it is */ | ||
153 | 32445 | } | ||
154 | ||||
155 | ||||
156 | /* | |||
157 | ** Link a generic collectable object 'o' into the list 'p'. | |||
158 | */ | |||
159 | #define linkobjgclist(o,p) linkgclist_(obj2gco(o), getgclist(o), &(p)) | |||
160 | ||||
161 | ||||
162 | ||||
163 | /* | |||
164 | ** Clear keys for empty entries in tables. If entry is empty, mark its | |||
165 | ** entry as dead. This allows the collection of the key, but keeps its | |||
166 | ** entry in the table: its removal could break a chain and could break | |||
167 | ** a table traversal. Other places never manipulate dead keys, because | |||
168 | ** its associated empty value is enough to signal that the entry is | |||
169 | ** logically empty. | |||
170 | */ | |||
171 | 11433 | static void clearkey (Node *n) { | ||
172 | lua_assert(isempty(gval(n))); | |||
173 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 11433 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 11433 times.
|
11433 | if (keyiscollectable(n)) |
174 | ✗ | setdeadkey(n); /* unused key; remove it */ | ||
175 | 11433 | } | ||
176 | ||||
177 | ||||
178 | /* | |||
179 | ** tells whether a key or value can be cleared from a weak | |||
180 | ** table. Non-collectable objects are never removed from weak | |||
181 | ** tables. Strings behave as 'values', so are never removed too. for | |||
182 | ** other objects: if really collected, cannot keep them; for objects | |||
183 | ** being finalized, keep them in keys, but not in values | |||
184 | */ | |||
185 | ✗ | static int iscleared (global_State *g, const GCObject *o) { | ||
186 | ✗ | if (o == NULL) return 0; /* non-collectable value */ | ||
187 | ✗ | else if (novariant(o->tt) == LUA_TSTRING) { | ||
188 | ✗ | markobject(g, o); /* strings are 'values', so are never weak */ | ||
189 | ✗ | return 0; | ||
190 | } | |||
191 | ✗ | else return iswhite(o); | ||
192 | } | |||
193 | ||||
194 | ||||
195 | /* | |||
196 | ** Barrier that moves collector forward, that is, marks the white object | |||
197 | ** 'v' being pointed by the black object 'o'. In the generational | |||
198 | ** mode, 'v' must also become old, if 'o' is old; however, it cannot | |||
199 | ** be changed directly to OLD, because it may still point to non-old | |||
200 | ** objects. So, it is marked as OLD0. In the next cycle it will become | |||
201 | ** OLD1, and in the next it will finally become OLD (regular old). By | |||
202 | ** then, any object it points to will also be old. If called in the | |||
203 | ** incremental sweep phase, it clears the black object to white (sweep | |||
204 | ** it) to avoid other barrier calls for this same object. (That cannot | |||
205 | ** be done is generational mode, as its sweep does not distinguish | |||
206 | ** whites from deads.) | |||
207 | */ | |||
208 | ✗ | void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) { | ||
209 | ✗ | global_State *g = G(L); | ||
210 | lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o)); | |||
211 | ✗ | if (keepinvariant(g)) { /* must keep invariant? */ | ||
212 | ✗ | reallymarkobject(g, v); /* restore invariant */ | ||
213 | ✗ | if (isold(o)) { | ||
214 | lua_assert(!isold(v)); /* white object could not be old */ | |||
215 | ✗ | setage(v, G_OLD0); /* restore generational invariant */ | ||
216 | } | |||
217 | } | |||
218 | else { /* sweep phase */ | |||
219 | lua_assert(issweepphase(g)); | |||
220 | ✗ | if (g->gckind == KGC_INC) /* incremental mode? */ | ||
221 | ✗ | makewhite(g, o); /* mark 'o' as white to avoid other barriers */ | ||
222 | } | |||
223 | ✗ | } | ||
224 | ||||
225 | ||||
226 | /* | |||
227 | ** barrier that moves collector backward, that is, mark the black object | |||
228 | ** pointing to a white object as gray again. | |||
229 | */ | |||
230 | ✗ | void luaC_barrierback_ (lua_State *L, GCObject *o) { | ||
231 | ✗ | global_State *g = G(L); | ||
232 | lua_assert(isblack(o) && !isdead(g, o)); | |||
233 | lua_assert((g->gckind == KGC_GEN) == (isold(o) && getage(o) != G_TOUCHED1)); | |||
234 | ✗ | if (getage(o) == G_TOUCHED2) /* already in gray list? */ | ||
235 | ✗ | set2gray(o); /* make it gray to become touched1 */ | ||
236 | else /* link it in 'grayagain' and paint it gray */ | |||
237 | ✗ | linkobjgclist(o, g->grayagain); | ||
238 | ✗ | if (isold(o)) /* generational mode? */ | ||
239 | ✗ | setage(o, G_TOUCHED1); /* touched in current cycle */ | ||
240 | ✗ | } | ||
241 | ||||
242 | ||||
243 | 15141 | void luaC_fix (lua_State *L, GCObject *o) { | ||
244 | 15141 | global_State *g = G(L); | ||
245 | lua_assert(g->allgc == o); /* object must be 1st in 'allgc' list! */ | |||
246 | 15141 | set2gray(o); /* they will be gray forever */ | ||
247 | 15141 | setage(o, G_OLD); /* and old forever */ | ||
248 | 15141 | g->allgc = o->next; /* remove object from 'allgc' list */ | ||
249 | 15141 | o->next = g->fixedgc; /* link it to 'fixedgc' list */ | ||
250 | 15141 | g->fixedgc = o; | ||
251 | 15141 | } | ||
252 | ||||
253 | ||||
254 | /* | |||
255 | ** create a new collectable object (with given type, size, and offset) | |||
256 | ** and link it to 'allgc' list. | |||
257 | */ | |||
258 | 73718 | GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) { | ||
259 | 73718 | global_State *g = G(L); | ||
260 | 73718 | char *p = cast_charp(luaM_newobject(L, novariant(tt), sz)); | ||
261 | 73718 | GCObject *o = cast(GCObject *, p + offset); | ||
262 | 73718 | o->marked = luaC_white(g); | ||
263 | 73718 | o->tt = tt; | ||
264 | 73718 | o->next = g->allgc; | ||
265 | 73718 | g->allgc = o; | ||
266 | 73718 | return o; | ||
267 | } | |||
268 | ||||
269 | ||||
270 | 73718 | GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) { | ||
271 | 73718 | return luaC_newobjdt(L, tt, sz, 0); | ||
272 | } | |||
273 | ||||
274 | /* }====================================================== */ | |||
275 | ||||
276 | ||||
277 | ||||
278 | /* | |||
279 | ** {====================================================== | |||
280 | ** Mark functions | |||
281 | ** ======================================================= | |||
282 | */ | |||
283 | ||||
284 | ||||
285 | /* | |||
286 | ** Mark an object. Userdata with no user values, strings, and closed | |||
287 | ** upvalues are visited and turned black here. Open upvalues are | |||
288 | ** already indirectly linked through their respective threads in the | |||
289 | ** 'twups' list, so they don't go to the gray list; nevertheless, they | |||
290 | ** are kept gray to avoid barriers, as their values will be revisited | |||
291 | ** by the thread or by 'remarkupvals'. Other objects are added to the | |||
292 | ** gray list to be visited (and turned black) later. Both userdata and | |||
293 | ** upvalues can call this function recursively, but this recursion goes | |||
294 | ** for at most two levels: An upvalue cannot refer to another upvalue | |||
295 | ** (only closures can), and a userdata's metatable must be a table. | |||
296 | */ | |||
297 | 80649 | static void reallymarkobject (global_State *g, GCObject *o) { | ||
298 |
3/5✓ Branch 0 taken 48513 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 10815 times.
✓ Branch 3 taken 21321 times.
✗ Branch 4 not taken.
|
80649 | switch (o->tt) { | |
299 |
1/1✓ Decision 'true' taken 48513 times.
|
48513 | case LUA_VSHRSTR: | |
300 | case LUA_VLNGSTR: { | |||
301 |
1/1✓ Decision 'true' taken 48513 times.
|
48513 | set2black(o); /* nothing to visit */ | |
302 | 48513 | break; | ||
303 | } | |||
304 | ✗ | case LUA_VUPVAL: { | ||
305 | ✗ | UpVal *uv = gco2upv(o); | ||
306 | ✗ | if (upisopen(uv)) | ||
307 | ✗ | set2gray(uv); /* open upvalues are kept gray */ | ||
308 | else | |||
309 | ✗ | set2black(uv); /* closed upvalues are visited here */ | ||
310 | ✗ | markvalue(g, uv->v.p); /* mark its content */ | ||
311 | ✗ | break; | ||
312 | } | |||
313 |
1/1✓ Decision 'true' taken 10815 times.
|
10815 | case LUA_VUSERDATA: { | |
314 | 10815 | Udata *u = gco2u(o); | ||
315 |
2/2✓ Branch 0 taken 618 times.
✓ Branch 1 taken 10197 times.
|
2/2✓ Decision 'true' taken 618 times.
✓ Decision 'false' taken 10197 times.
|
10815 | if (u->nuvalue == 0) { /* no user values? */ |
316 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 618 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
618 | markobjectN(g, u->metatable); /* mark its metatable */ | |
317 | 618 | set2black(u); /* nothing else to mark */ | ||
318 | 618 | break; | ||
319 | } | |||
320 | /* else... */ | |||
321 | } /* FALLTHROUGH */ | |||
322 | case LUA_VLCL: case LUA_VCCL: case LUA_VTABLE: | |||
323 | case LUA_VTHREAD: case LUA_VPROTO: { | |||
324 |
1/1✓ Decision 'true' taken 31518 times.
|
31518 | linkobjgclist(o, g->gray); /* to be visited later */ | |
325 | 31518 | break; | ||
326 | } | |||
327 | ✗ | default: lua_assert(0); break; | ||
328 | } | |||
329 | 80649 | } | ||
330 | ||||
331 | ||||
332 | /* | |||
333 | ** mark metamethods for basic types | |||
334 | */ | |||
335 | 1854 | static void markmt (global_State *g) { | ||
336 | int i; | |||
337 |
2/2✓ Branch 0 taken 16686 times.
✓ Branch 1 taken 1854 times.
|
2/2✓ Decision 'true' taken 16686 times.
✓ Decision 'false' taken 1854 times.
|
18540 | for (i=0; i < LUA_NUMTAGS; i++) |
338 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 16686 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
16686 | markobjectN(g, g->mt[i]); | |
339 | 1854 | } | ||
340 | ||||
341 | ||||
342 | /* | |||
343 | ** mark all objects in list of being-finalized | |||
344 | */ | |||
345 | 1854 | static lu_mem markbeingfnz (global_State *g) { | ||
346 | GCObject *o; | |||
347 | 1854 | lu_mem count = 0; | ||
348 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | for (o = g->tobefnz; o != NULL; o = o->next) { |
349 | ✗ | count++; | ||
350 | ✗ | markobject(g, o); | ||
351 | } | |||
352 | 1854 | return count; | ||
353 | } | |||
354 | ||||
355 | ||||
356 | /* | |||
357 | ** For each non-marked thread, simulates a barrier between each open | |||
358 | ** upvalue and its value. (If the thread is collected, the value will be | |||
359 | ** assigned to the upvalue, but then it can be too late for the barrier | |||
360 | ** to act. The "barrier" does not need to check colors: A non-marked | |||
361 | ** thread must be young; upvalues cannot be older than their threads; so | |||
362 | ** any visited upvalue must be young too.) Also removes the thread from | |||
363 | ** the list, as it was already visited. Removes also threads with no | |||
364 | ** upvalues, as they have nothing to be checked. (If the thread gets an | |||
365 | ** upvalue later, it will be linked in the list again.) | |||
366 | */ | |||
367 | 927 | static int remarkupvals (global_State *g) { | ||
368 | lua_State *thread; | |||
369 | 927 | lua_State **p = &g->twups; | ||
370 | 927 | int work = 0; /* estimate of how much work was done here */ | ||
371 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | while ((thread = *p) != NULL) { |
372 | ✗ | work++; | ||
373 | ✗ | if (!iswhite(thread) && thread->openupval != NULL) | ||
374 | ✗ | p = &thread->twups; /* keep marked thread with upvalues in the list */ | ||
375 | else { /* thread is not marked or without upvalues */ | |||
376 | UpVal *uv; | |||
377 | lua_assert(!isold(thread) || thread->openupval == NULL); | |||
378 | ✗ | *p = thread->twups; /* remove thread from the list */ | ||
379 | ✗ | thread->twups = thread; /* mark that it is out of list */ | ||
380 | ✗ | for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) { | ||
381 | lua_assert(getage(uv) <= getage(thread)); | |||
382 | ✗ | work++; | ||
383 | ✗ | if (!iswhite(uv)) { /* upvalue already visited? */ | ||
384 | lua_assert(upisopen(uv) && isgray(uv)); | |||
385 | ✗ | markvalue(g, uv->v.p); /* mark its value */ | ||
386 | } | |||
387 | } | |||
388 | } | |||
389 | } | |||
390 | 927 | return work; | ||
391 | } | |||
392 | ||||
393 | ||||
394 | 927 | static void cleargraylists (global_State *g) { | ||
395 | 927 | g->gray = g->grayagain = NULL; | ||
396 | 927 | g->weak = g->allweak = g->ephemeron = NULL; | ||
397 | 927 | } | ||
398 | ||||
399 | ||||
400 | /* | |||
401 | ** mark root set and reset all gray lists, to start a new collection | |||
402 | */ | |||
403 | 927 | static void restartcollection (global_State *g) { | ||
404 | 927 | cleargraylists(g); | ||
405 |
1/2✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
|
927 | markobject(g, g->mainthread); | |
406 |
2/4✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 927 times.
✗ Branch 3 not taken.
|
927 | markvalue(g, &g->l_registry); | |
407 | 927 | markmt(g); | ||
408 | 927 | markbeingfnz(g); /* mark any finalizing object left from previous cycle */ | ||
409 | 927 | } | ||
410 | ||||
411 | /* }====================================================== */ | |||
412 | ||||
413 | ||||
414 | /* | |||
415 | ** {====================================================== | |||
416 | ** Traverse functions | |||
417 | ** ======================================================= | |||
418 | */ | |||
419 | ||||
420 | ||||
421 | /* | |||
422 | ** Check whether object 'o' should be kept in the 'grayagain' list for | |||
423 | ** post-processing by 'correctgraylist'. (It could put all old objects | |||
424 | ** in the list and leave all the work to 'correctgraylist', but it is | |||
425 | ** more efficient to avoid adding elements that will be removed.) Only | |||
426 | ** TOUCHED1 objects need to be in the list. TOUCHED2 doesn't need to go | |||
427 | ** back to a gray list, but then it must become OLD. (That is what | |||
428 | ** 'correctgraylist' does when it finds a TOUCHED2 object.) | |||
429 | */ | |||
430 | 21939 | static void genlink (global_State *g, GCObject *o) { | ||
431 | lua_assert(isblack(o)); | |||
432 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 21939 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 21939 times.
|
21939 | if (getage(o) == G_TOUCHED1) { /* touched in this cycle? */ |
433 | ✗ | linkobjgclist(o, g->grayagain); /* link it back in 'grayagain' */ | ||
434 | } /* everything else do not need to be linked back */ | |||
435 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 21939 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 21939 times.
|
21939 | else if (getage(o) == G_TOUCHED2) |
436 | ✗ | changeage(o, G_TOUCHED2, G_OLD); /* advance age */ | ||
437 | 21939 | } | ||
438 | ||||
439 | ||||
440 | /* | |||
441 | ** Traverse a table with weak values and link it to proper list. During | |||
442 | ** propagate phase, keep it in 'grayagain' list, to be revisited in the | |||
443 | ** atomic phase. In the atomic phase, if table has any white value, | |||
444 | ** put it in 'weak' list, to be cleared. | |||
445 | */ | |||
446 | ✗ | static void traverseweakvalue (global_State *g, Table *h) { | ||
447 | ✗ | Node *n, *limit = gnodelast(h); | ||
448 | /* if there is array part, assume it may have white values (it is not | |||
449 | worth traversing it now just to check) */ | |||
450 | ✗ | int hasclears = (h->alimit > 0); | ||
451 | ✗ | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ | ||
452 | ✗ | if (isempty(gval(n))) /* entry is empty? */ | ||
453 | ✗ | clearkey(n); /* clear its key */ | ||
454 | else { | |||
455 | lua_assert(!keyisnil(n)); | |||
456 | ✗ | markkey(g, n); | ||
457 | ✗ | if (!hasclears && iscleared(g, gcvalueN(gval(n)))) /* a white value? */ | ||
458 | ✗ | hasclears = 1; /* table will have to be cleared */ | ||
459 | } | |||
460 | } | |||
461 | ✗ | if (g->gcstate == GCSatomic && hasclears) | ||
462 | ✗ | linkgclist(h, g->weak); /* has to be cleared later */ | ||
463 | else | |||
464 | ✗ | linkgclist(h, g->grayagain); /* must retraverse it in atomic phase */ | ||
465 | ✗ | } | ||
466 | ||||
467 | ||||
468 | /* | |||
469 | ** Traverse an ephemeron table and link it to proper list. Returns true | |||
470 | ** iff any object was marked during this traversal (which implies that | |||
471 | ** convergence has to continue). During propagation phase, keep table | |||
472 | ** in 'grayagain' list, to be visited again in the atomic phase. In | |||
473 | ** the atomic phase, if table has any white->white entry, it has to | |||
474 | ** be revisited during ephemeron convergence (as that key may turn | |||
475 | ** black). Otherwise, if it has any white key, table has to be cleared | |||
476 | ** (in the atomic phase). In generational mode, some tables | |||
477 | ** must be kept in some gray list for post-processing; this is done | |||
478 | ** by 'genlink'. | |||
479 | */ | |||
480 | ✗ | static int traverseephemeron (global_State *g, Table *h, int inv) { | ||
481 | ✗ | int marked = 0; /* true if an object is marked in this traversal */ | ||
482 | ✗ | int hasclears = 0; /* true if table has white keys */ | ||
483 | ✗ | int hasww = 0; /* true if table has entry "white-key -> white-value" */ | ||
484 | unsigned int i; | |||
485 | ✗ | unsigned int asize = luaH_realasize(h); | ||
486 | ✗ | unsigned int nsize = sizenode(h); | ||
487 | /* traverse array part */ | |||
488 | ✗ | for (i = 0; i < asize; i++) { | ||
489 | ✗ | if (valiswhite(&h->array[i])) { | ||
490 | ✗ | marked = 1; | ||
491 | ✗ | reallymarkobject(g, gcvalue(&h->array[i])); | ||
492 | } | |||
493 | } | |||
494 | /* traverse hash part; if 'inv', traverse descending | |||
495 | (see 'convergeephemerons') */ | |||
496 | ✗ | for (i = 0; i < nsize; i++) { | ||
497 | ✗ | Node *n = inv ? gnode(h, nsize - 1 - i) : gnode(h, i); | ||
498 | ✗ | if (isempty(gval(n))) /* entry is empty? */ | ||
499 | ✗ | clearkey(n); /* clear its key */ | ||
500 | ✗ | else if (iscleared(g, gckeyN(n))) { /* key is not marked (yet)? */ | ||
501 | ✗ | hasclears = 1; /* table must be cleared */ | ||
502 | ✗ | if (valiswhite(gval(n))) /* value not marked yet? */ | ||
503 | ✗ | hasww = 1; /* white-white entry */ | ||
504 | } | |||
505 | ✗ | else if (valiswhite(gval(n))) { /* value not marked yet? */ | ||
506 | ✗ | marked = 1; | ||
507 | ✗ | reallymarkobject(g, gcvalue(gval(n))); /* mark it now */ | ||
508 | } | |||
509 | } | |||
510 | /* link table into proper list */ | |||
511 | ✗ | if (g->gcstate == GCSpropagate) | ||
512 | ✗ | linkgclist(h, g->grayagain); /* must retraverse it in atomic phase */ | ||
513 | ✗ | else if (hasww) /* table has white->white entries? */ | ||
514 | ✗ | linkgclist(h, g->ephemeron); /* have to propagate again */ | ||
515 | ✗ | else if (hasclears) /* table has white keys? */ | ||
516 | ✗ | linkgclist(h, g->allweak); /* may have to clean white keys */ | ||
517 | else | |||
518 | ✗ | genlink(g, obj2gco(h)); /* check whether collector still needs to see it */ | ||
519 | ✗ | return marked; | ||
520 | } | |||
521 | ||||
522 | ||||
523 | 11742 | static void traversestrongtable (global_State *g, Table *h) { | ||
524 | 11742 | Node *n, *limit = gnodelast(h); | ||
525 | unsigned int i; | |||
526 | 11742 | unsigned int asize = luaH_realasize(h); | ||
527 |
2/2✓ Branch 0 taken 1854 times.
✓ Branch 1 taken 11742 times.
|
2/2✓ Decision 'true' taken 1854 times.
✓ Decision 'false' taken 11742 times.
|
13596 | for (i = 0; i < asize; i++) /* traverse array part */ |
528 |
3/4✓ Branch 0 taken 1854 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 927 times.
✓ Branch 3 taken 927 times.
|
1854 | markvalue(g, &h->array[i]); | |
529 |
2/2✓ Branch 0 taken 80340 times.
✓ Branch 1 taken 11742 times.
|
2/2✓ Decision 'true' taken 80340 times.
✓ Decision 'false' taken 11742 times.
|
92082 | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ |
530 |
2/2✓ Branch 0 taken 11433 times.
✓ Branch 1 taken 68907 times.
|
2/2✓ Decision 'true' taken 11433 times.
✓ Decision 'false' taken 68907 times.
|
80340 | if (isempty(gval(n))) /* entry is empty? */ |
531 | 11433 | clearkey(n); /* clear its key */ | ||
532 | else { | |||
533 | lua_assert(!keyisnil(n)); | |||
534 |
3/4✓ Branch 0 taken 68907 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48204 times.
✓ Branch 3 taken 20703 times.
|
68907 | markkey(g, n); | |
535 |
4/4✓ Branch 0 taken 29973 times.
✓ Branch 1 taken 38934 times.
✓ Branch 2 taken 21012 times.
✓ Branch 3 taken 8961 times.
|
68907 | markvalue(g, gval(n)); | |
536 | } | |||
537 | } | |||
538 | 11742 | genlink(g, obj2gco(h)); | ||
539 | 11742 | } | ||
540 | ||||
541 | ||||
542 | 11742 | static lu_mem traversetable (global_State *g, Table *h) { | ||
543 | const char *weakkey, *weakvalue; | |||
544 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 11742 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
11742 | const TValue *mode = gfasttm(g, h->metatable, TM_MODE); | |
545 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 11742 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
11742 | markobjectN(g, h->metatable); | |
546 |
1/6✗ Branch 0 not taken.
✓ Branch 1 taken 11742 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 11742 times.
|
11742 | if (mode && ttisstring(mode) && /* is there a weak mode? */ |
547 | ✗ | (cast_void(weakkey = strchr(svalue(mode), 'k')), | ||
548 | ✗ | cast_void(weakvalue = strchr(svalue(mode), 'v')), | ||
549 | ✗ | (weakkey || weakvalue))) { /* is really weak? */ | ||
550 | ✗ | if (!weakkey) /* strong keys? */ | ||
551 | ✗ | traverseweakvalue(g, h); | ||
552 | ✗ | else if (!weakvalue) /* strong values? */ | ||
553 | ✗ | traverseephemeron(g, h, 0); | ||
554 | else /* all weak */ | |||
555 | ✗ | linkgclist(h, g->allweak); /* nothing to traverse now */ | ||
556 | } | |||
557 | else /* not weak */ | |||
558 | 11742 | traversestrongtable(g, h); | ||
559 |
2/2✓ Branch 0 taken 10815 times.
✓ Branch 1 taken 927 times.
|
11742 | return 1 + h->alimit + 2 * allocsizenode(h); | |
560 | } | |||
561 | ||||
562 | ||||
563 | 10197 | static int traverseudata (global_State *g, Udata *u) { | ||
564 | int i; | |||
565 |
3/4✓ Branch 0 taken 2781 times.
✓ Branch 1 taken 7416 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2781 times.
|
10197 | markobjectN(g, u->metatable); /* mark its metatable */ | |
566 |
2/2✓ Branch 0 taken 10197 times.
✓ Branch 1 taken 10197 times.
|
2/2✓ Decision 'true' taken 10197 times.
✓ Decision 'false' taken 10197 times.
|
20394 | for (i = 0; i < u->nuvalue; i++) |
567 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 10197 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
10197 | markvalue(g, &u->uv[i].uv); | |
568 | 10197 | genlink(g, obj2gco(u)); | ||
569 | 10197 | return 1 + u->nuvalue; | ||
570 | } | |||
571 | ||||
572 | ||||
573 | /* | |||
574 | ** Traverse a prototype. (While a prototype is being build, its | |||
575 | ** arrays can be larger than needed; the extra slots are filled with | |||
576 | ** NULL, so the use of 'markobjectN') | |||
577 | */ | |||
578 | ✗ | static int traverseproto (global_State *g, Proto *f) { | ||
579 | int i; | |||
580 | ✗ | markobjectN(g, f->source); | ||
581 | ✗ | for (i = 0; i < f->sizek; i++) /* mark literals */ | ||
582 | ✗ | markvalue(g, &f->k[i]); | ||
583 | ✗ | for (i = 0; i < f->sizeupvalues; i++) /* mark upvalue names */ | ||
584 | ✗ | markobjectN(g, f->upvalues[i].name); | ||
585 | ✗ | for (i = 0; i < f->sizep; i++) /* mark nested protos */ | ||
586 | ✗ | markobjectN(g, f->p[i]); | ||
587 | ✗ | for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */ | ||
588 | ✗ | markobjectN(g, f->locvars[i].varname); | ||
589 | ✗ | return 1 + f->sizek + f->sizeupvalues + f->sizep + f->sizelocvars; | ||
590 | } | |||
591 | ||||
592 | ||||
593 | 8652 | static int traverseCclosure (global_State *g, CClosure *cl) { | ||
594 | int i; | |||
595 |
2/2✓ Branch 0 taken 8652 times.
✓ Branch 1 taken 8652 times.
|
2/2✓ Decision 'true' taken 8652 times.
✓ Decision 'false' taken 8652 times.
|
17304 | for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ |
596 |
3/4✓ Branch 0 taken 8652 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8034 times.
✓ Branch 3 taken 618 times.
|
8652 | markvalue(g, &cl->upvalue[i]); | |
597 | 8652 | return 1 + cl->nupvalues; | ||
598 | } | |||
599 | ||||
600 | /* | |||
601 | ** Traverse a Lua closure, marking its prototype and its upvalues. | |||
602 | ** (Both can be NULL while closure is being created.) | |||
603 | */ | |||
604 | ✗ | static int traverseLclosure (global_State *g, LClosure *cl) { | ||
605 | int i; | |||
606 | ✗ | markobjectN(g, cl->p); /* mark its prototype */ | ||
607 | ✗ | for (i = 0; i < cl->nupvalues; i++) { /* visit its upvalues */ | ||
608 | ✗ | UpVal *uv = cl->upvals[i]; | ||
609 | ✗ | markobjectN(g, uv); /* mark upvalue */ | ||
610 | } | |||
611 | ✗ | return 1 + cl->nupvalues; | ||
612 | } | |||
613 | ||||
614 | ||||
615 | /* | |||
616 | ** Traverse a thread, marking the elements in the stack up to its top | |||
617 | ** and cleaning the rest of the stack in the final traversal. That | |||
618 | ** ensures that the entire stack have valid (non-dead) objects. | |||
619 | ** Threads have no barriers. In gen. mode, old threads must be visited | |||
620 | ** at every cycle, because they might point to young objects. In inc. | |||
621 | ** mode, the thread can still be modified before the end of the cycle, | |||
622 | ** and therefore it must be visited again in the atomic phase. To ensure | |||
623 | ** these visits, threads must return to a gray list if they are not new | |||
624 | ** (which can only happen in generational mode) or if the traverse is in | |||
625 | ** the propagate phase (which can only happen in incremental mode). | |||
626 | */ | |||
627 | 1854 | static int traversethread (global_State *g, lua_State *th) { | ||
628 | UpVal *uv; | |||
629 | 1854 | StkId o = th->stack.p; | ||
630 |
3/4✓ Branch 0 taken 1854 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 927 times.
✓ Branch 3 taken 927 times.
|
2/2✓ Decision 'true' taken 927 times.
✓ Decision 'false' taken 927 times.
|
1854 | if (isold(th) || g->gcstate == GCSpropagate) |
631 | 927 | linkgclist(th, g->grayagain); /* insert into 'grayagain' list */ | ||
632 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | if (o == NULL) |
633 | ✗ | return 1; /* stack not completely built yet */ | ||
634 | lua_assert(g->gcstate == GCSatomic || | |||
635 | th->openupval == NULL || isintwups(th)); | |||
636 |
2/2✓ Branch 0 taken 3708 times.
✓ Branch 1 taken 1854 times.
|
2/2✓ Decision 'true' taken 3708 times.
✓ Decision 'false' taken 1854 times.
|
5562 | for (; o < th->top.p; o++) /* mark live elements in the stack */ |
637 |
4/4✓ Branch 0 taken 1854 times.
✓ Branch 1 taken 1854 times.
✓ Branch 2 taken 618 times.
✓ Branch 3 taken 1236 times.
|
3708 | markvalue(g, s2v(o)); | |
638 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | for (uv = th->openupval; uv != NULL; uv = uv->u.open.next) |
639 | ✗ | markobject(g, uv); /* open upvalues cannot be collected */ | ||
640 |
2/2✓ Branch 0 taken 927 times.
✓ Branch 1 taken 927 times.
|
2/2✓ Decision 'true' taken 927 times.
✓ Decision 'false' taken 927 times.
|
1854 | if (g->gcstate == GCSatomic) { /* final traversal? */ |
641 |
2/2✓ Branch 0 taken 39861 times.
✓ Branch 1 taken 927 times.
|
2/2✓ Decision 'true' taken 39861 times.
✓ Decision 'false' taken 927 times.
|
40788 | for (; o < th->stack_last.p + EXTRA_STACK; o++) |
642 | 39861 | setnilvalue(s2v(o)); /* clear dead stack slice */ | ||
643 | /* 'remarkupvals' may have removed thread from 'twups' list */ | |||
644 |
2/4✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 927 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | if (!isintwups(th) && th->openupval != NULL) { |
645 | ✗ | th->twups = g->twups; /* link it back to the list */ | ||
646 | ✗ | g->twups = th; | ||
647 | } | |||
648 | } | |||
649 |
1/2✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 927 times.
✗ Decision 'false' not taken.
|
927 | else if (!g->gcemergency) |
650 | 927 | luaD_shrinkstack(th); /* do not change stack in emergency cycle */ | ||
651 | 1854 | return 1 + stacksize(th); | ||
652 | } | |||
653 | ||||
654 | ||||
655 | /* | |||
656 | ** traverse one gray object, turning it to black. | |||
657 | */ | |||
658 | 32445 | static lu_mem propagatemark (global_State *g) { | ||
659 | 32445 | GCObject *o = g->gray; | ||
660 | 32445 | nw2black(o); | ||
661 | 32445 | g->gray = *getgclist(o); /* remove from 'gray' list */ | ||
662 |
4/7✓ Branch 0 taken 11742 times.
✓ Branch 1 taken 10197 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8652 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1854 times.
✗ Branch 6 not taken.
|
32445 | switch (o->tt) { | |
663 |
1/1✓ Decision 'true' taken 11742 times.
|
11742 | case LUA_VTABLE: return traversetable(g, gco2t(o)); | |
664 |
1/1✓ Decision 'true' taken 10197 times.
|
10197 | case LUA_VUSERDATA: return traverseudata(g, gco2u(o)); | |
665 | ✗ | case LUA_VLCL: return traverseLclosure(g, gco2lcl(o)); | ||
666 |
1/1✓ Decision 'true' taken 8652 times.
|
8652 | case LUA_VCCL: return traverseCclosure(g, gco2ccl(o)); | |
667 | ✗ | case LUA_VPROTO: return traverseproto(g, gco2p(o)); | ||
668 |
1/1✓ Decision 'true' taken 1854 times.
|
1854 | case LUA_VTHREAD: return traversethread(g, gco2th(o)); | |
669 | ✗ | default: lua_assert(0); return 0; | ||
670 | } | |||
671 | } | |||
672 | ||||
673 | ||||
674 | 3708 | static lu_mem propagateall (global_State *g) { | ||
675 | 3708 | lu_mem tot = 0; | ||
676 |
2/2✓ Branch 0 taken 927 times.
✓ Branch 1 taken 3708 times.
|
2/2✓ Decision 'true' taken 927 times.
✓ Decision 'false' taken 3708 times.
|
4635 | while (g->gray) |
677 | 927 | tot += propagatemark(g); | ||
678 | 3708 | return tot; | ||
679 | } | |||
680 | ||||
681 | ||||
682 | /* | |||
683 | ** Traverse all ephemeron tables propagating marks from keys to values. | |||
684 | ** Repeat until it converges, that is, nothing new is marked. 'dir' | |||
685 | ** inverts the direction of the traversals, trying to speed up | |||
686 | ** convergence on chains in the same table. | |||
687 | ** | |||
688 | */ | |||
689 | 1854 | static void convergeephemerons (global_State *g) { | ||
690 | int changed; | |||
691 | 1854 | int dir = 0; | ||
692 | do { | |||
693 | GCObject *w; | |||
694 | 1854 | GCObject *next = g->ephemeron; /* get ephemeron list */ | ||
695 | 1854 | g->ephemeron = NULL; /* tables may return to this list when traversed */ | ||
696 | 1854 | changed = 0; | ||
697 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | while ((w = next) != NULL) { /* for each ephemeron table */ |
698 | ✗ | Table *h = gco2t(w); | ||
699 | ✗ | next = h->gclist; /* list is rebuilt during loop */ | ||
700 | ✗ | nw2black(h); /* out of the list (for now) */ | ||
701 | ✗ | if (traverseephemeron(g, h, dir)) { /* marked some value? */ | ||
702 | ✗ | propagateall(g); /* propagate changes */ | ||
703 | ✗ | changed = 1; /* will have to revisit all ephemeron tables */ | ||
704 | } | |||
705 | } | |||
706 | 1854 | dir = !dir; /* invert direction next time */ | ||
707 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | } while (changed); /* repeat until no more changes */ |
708 | 1854 | } | ||
709 | ||||
710 | /* }====================================================== */ | |||
711 | ||||
712 | ||||
713 | /* | |||
714 | ** {====================================================== | |||
715 | ** Sweep Functions | |||
716 | ** ======================================================= | |||
717 | */ | |||
718 | ||||
719 | ||||
720 | /* | |||
721 | ** clear entries with unmarked keys from all weaktables in list 'l' | |||
722 | */ | |||
723 | 1854 | static void clearbykeys (global_State *g, GCObject *l) { | ||
724 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1854 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1854 times.
|
1854 | for (; l; l = gco2t(l)->gclist) { |
725 | ✗ | Table *h = gco2t(l); | ||
726 | ✗ | Node *limit = gnodelast(h); | ||
727 | Node *n; | |||
728 | ✗ | for (n = gnode(h, 0); n < limit; n++) { | ||
729 | ✗ | if (iscleared(g, gckeyN(n))) /* unmarked key? */ | ||
730 | ✗ | setempty(gval(n)); /* remove entry */ | ||
731 | ✗ | if (isempty(gval(n))) /* is entry empty? */ | ||
732 | ✗ | clearkey(n); /* clear its key */ | ||
733 | } | |||
734 | } | |||
735 | 1854 | } | ||
736 | ||||
737 | ||||
738 | /* | |||
739 | ** clear entries with unmarked values from all weaktables in list 'l' up | |||
740 | ** to element 'f' | |||
741 | */ | |||
742 | 3708 | static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { | ||
743 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3708 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 3708 times.
|
3708 | for (; l != f; l = gco2t(l)->gclist) { |
744 | ✗ | Table *h = gco2t(l); | ||
745 | ✗ | Node *n, *limit = gnodelast(h); | ||
746 | unsigned int i; | |||
747 | ✗ | unsigned int asize = luaH_realasize(h); | ||
748 | ✗ | for (i = 0; i < asize; i++) { | ||
749 | ✗ | TValue *o = &h->array[i]; | ||
750 | ✗ | if (iscleared(g, gcvalueN(o))) /* value was collected? */ | ||
751 | ✗ | setempty(o); /* remove entry */ | ||
752 | } | |||
753 | ✗ | for (n = gnode(h, 0); n < limit; n++) { | ||
754 | ✗ | if (iscleared(g, gcvalueN(gval(n)))) /* unmarked value? */ | ||
755 | ✗ | setempty(gval(n)); /* remove entry */ | ||
756 | ✗ | if (isempty(gval(n))) /* is entry empty? */ | ||
757 | ✗ | clearkey(n); /* clear its key */ | ||
758 | } | |||
759 | } | |||
760 | 3708 | } | ||
761 | ||||
762 | ||||
763 | 308 | static void freeupval (lua_State *L, UpVal *uv) { | ||
764 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 308 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 308 times.
|
308 | if (upisopen(uv)) |
765 | ✗ | luaF_unlinkupval(uv); | ||
766 | 308 | luaM_free(L, uv); | ||
767 | 308 | } | ||
768 | ||||
769 | ||||
770 | 73718 | static void freeobj (lua_State *L, GCObject *o) { | ||
771 |
8/10✓ Branch 0 taken 524 times.
✓ Branch 1 taken 308 times.
✓ Branch 2 taken 524 times.
✓ Branch 3 taken 6180 times.
✓ Branch 4 taken 7213 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 7731 times.
✓ Branch 7 taken 51123 times.
✓ Branch 8 taken 115 times.
✗ Branch 9 not taken.
|
73718 | switch (o->tt) { | |
772 |
1/1✓ Decision 'true' taken 524 times.
|
524 | case LUA_VPROTO: | |
773 | 524 | luaF_freeproto(L, gco2p(o)); | ||
774 | 524 | break; | ||
775 |
1/1✓ Decision 'true' taken 308 times.
|
308 | case LUA_VUPVAL: | |
776 | 308 | freeupval(L, gco2upv(o)); | ||
777 | 308 | break; | ||
778 |
1/1✓ Decision 'true' taken 524 times.
|
524 | case LUA_VLCL: { | |
779 | 524 | LClosure *cl = gco2lcl(o); | ||
780 | 524 | luaM_freemem(L, cl, sizeLclosure(cl->nupvalues)); | ||
781 | 524 | break; | ||
782 | } | |||
783 |
1/1✓ Decision 'true' taken 6180 times.
|
6180 | case LUA_VCCL: { | |
784 | 6180 | CClosure *cl = gco2ccl(o); | ||
785 | 6180 | luaM_freemem(L, cl, sizeCclosure(cl->nupvalues)); | ||
786 | 6180 | break; | ||
787 | } | |||
788 |
1/1✓ Decision 'true' taken 7213 times.
|
7213 | case LUA_VTABLE: | |
789 | 7213 | luaH_free(L, gco2t(o)); | ||
790 | 7213 | break; | ||
791 | ✗ | case LUA_VTHREAD: | ||
792 | ✗ | luaE_freethread(L, gco2th(o)); | ||
793 | ✗ | break; | ||
794 |
1/1✓ Decision 'true' taken 7731 times.
|
7731 | case LUA_VUSERDATA: { | |
795 | 7731 | Udata *u = gco2u(o); | ||
796 |
2/2✓ Branch 0 taken 7422 times.
✓ Branch 1 taken 309 times.
|
7731 | luaM_freemem(L, o, sizeudata(u->nuvalue, u->len)); | |
797 | 7731 | break; | ||
798 | } | |||
799 |
1/1✓ Decision 'true' taken 51123 times.
|
51123 | case LUA_VSHRSTR: { | |
800 | 51123 | TString *ts = gco2ts(o); | ||
801 | 51123 | luaS_remove(L, ts); /* remove it from hash table */ | ||
802 | 51123 | luaM_freemem(L, ts, sizelstring(ts->shrlen)); | ||
803 | 51123 | break; | ||
804 | } | |||
805 |
1/1✓ Decision 'true' taken 115 times.
|
115 | case LUA_VLNGSTR: { | |
806 | 115 | TString *ts = gco2ts(o); | ||
807 | 115 | luaM_freemem(L, ts, sizelstring(ts->u.lnglen)); | ||
808 | 115 | break; | ||
809 | } | |||
810 |
1/1✓ Decision 'true' taken 73718 times.
|
73718 | default: lua_assert(0); | |
811 | } | |||
812 | 73718 | } | ||
813 | ||||
814 | ||||
815 | /* | |||
816 | ** sweep at most 'countin' elements from a list of GCObjects erasing dead | |||
817 | ** objects, where a dead object is one marked with the old (non current) | |||
818 | ** white; change all non-dead objects back to white, preparing for next | |||
819 | ** collection cycle. Return where to continue the traversal or NULL if | |||
820 | ** list is finished. ('*countout' gets the number of elements traversed.) | |||
821 | */ | |||
822 | 4017 | static GCObject **sweeplist (lua_State *L, GCObject **p, int countin, | ||
823 | int *countout) { | |||
824 | 4017 | global_State *g = G(L); | ||
825 | 4017 | int ow = otherwhite(g); | ||
826 | int i; | |||
827 | 4017 | int white = luaC_white(g); /* current white */ | ||
828 |
4/4✓ Branch 0 taken 82194 times.
✓ Branch 1 taken 2781 times.
✓ Branch 2 taken 80958 times.
✓ Branch 3 taken 1236 times.
|
0/1? Decision couldn't be analyzed.
|
84975 | for (i = 0; *p != NULL && i < countin; i++) { |
829 | 80958 | GCObject *curr = *p; | ||
830 | 80958 | int marked = curr->marked; | ||
831 |
2/2✓ Branch 0 taken 309 times.
✓ Branch 1 taken 80649 times.
|
2/2✓ Decision 'true' taken 309 times.
✓ Decision 'false' taken 80649 times.
|
80958 | if (isdeadm(ow, marked)) { /* is 'curr' dead? */ |
832 | 309 | *p = curr->next; /* remove 'curr' from list */ | ||
833 | 309 | freeobj(L, curr); /* erase 'curr' */ | ||
834 | } | |||
835 | else { /* change mark to 'white' */ | |||
836 | 80649 | curr->marked = cast_byte((marked & ~maskgcbits) | white); | ||
837 | 80649 | p = &curr->next; /* go to next element */ | ||
838 | } | |||
839 | } | |||
840 |
2/2✓ Branch 0 taken 3090 times.
✓ Branch 1 taken 927 times.
|
2/2✓ Decision 'true' taken 3090 times.
✓ Decision 'false' taken 927 times.
|
4017 | if (countout) |
841 | 3090 | *countout = i; /* number of elements traversed */ | ||
842 |
2/2✓ Branch 0 taken 1236 times.
✓ Branch 1 taken 2781 times.
|
4017 | return (*p == NULL) ? NULL : p; | |
843 | } | |||
844 | ||||
845 | ||||
846 | /* | |||
847 | ** sweep a list until a live object (or end of list) | |||
848 | */ | |||
849 | 927 | static GCObject **sweeptolive (lua_State *L, GCObject **p) { | ||
850 | 927 | GCObject **old = p; | ||
851 | do { | |||
852 | 927 | p = sweeplist(L, p, 1, NULL); | ||
853 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | } while (p == old); |
854 | 927 | return p; | ||
855 | } | |||
856 | ||||
857 | /* }====================================================== */ | |||
858 | ||||
859 | ||||
860 | /* | |||
861 | ** {====================================================== | |||
862 | ** Finalization | |||
863 | ** ======================================================= | |||
864 | */ | |||
865 | ||||
866 | /* | |||
867 | ** If possible, shrink string table. | |||
868 | */ | |||
869 | 927 | static void checkSizes (lua_State *L, global_State *g) { | ||
870 |
1/2✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 927 times.
✗ Decision 'false' not taken.
|
927 | if (!g->gcemergency) { |
871 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | if (g->strt.nuse < g->strt.size / 4) { /* string table too big? */ |
872 | ✗ | l_mem olddebt = g->GCdebt; | ||
873 | ✗ | luaS_resize(L, g->strt.size / 2); | ||
874 | ✗ | g->GCestimate += g->GCdebt - olddebt; /* correct estimate */ | ||
875 | } | |||
876 | } | |||
877 | 927 | } | ||
878 | ||||
879 | ||||
880 | /* | |||
881 | ** Get the next udata to be finalized from the 'tobefnz' list, and | |||
882 | ** link it back into the 'allgc' list. | |||
883 | */ | |||
884 | 1860 | static GCObject *udata2finalize (global_State *g) { | ||
885 | 1860 | GCObject *o = g->tobefnz; /* get first element */ | ||
886 | lua_assert(tofinalize(o)); | |||
887 | 1860 | g->tobefnz = o->next; /* remove it from 'tobefnz' list */ | ||
888 | 1860 | o->next = g->allgc; /* return it to 'allgc' list */ | ||
889 | 1860 | g->allgc = o; | ||
890 | 1860 | resetbit(o->marked, FINALIZEDBIT); /* object is "normal" again */ | ||
891 |
2/4✓ Branch 0 taken 1860 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1860 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | if (issweepphase(g)) |
892 | ✗ | makewhite(g, o); /* "sweep" object */ | ||
893 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1860 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | else if (getage(o) == G_OLD1) |
894 | ✗ | g->firstold1 = o; /* it is the first OLD1 object in the list */ | ||
895 | 1860 | return o; | ||
896 | } | |||
897 | ||||
898 | ||||
899 | 1860 | static void dothecall (lua_State *L, void *ud) { | ||
900 | UNUSED(ud); | |||
901 | 1860 | luaD_callnoyield(L, L->top.p - 2, 0); | ||
902 | 1860 | } | ||
903 | ||||
904 | ||||
905 | 1860 | static void GCTM (lua_State *L) { | ||
906 | 1860 | global_State *g = G(L); | ||
907 | const TValue *tm; | |||
908 | TValue v; | |||
909 | lua_assert(!g->gcemergency); | |||
910 | 1860 | setgcovalue(L, &v, udata2finalize(g)); | ||
911 | 1860 | tm = luaT_gettmbyobj(L, &v, TM_GC); | ||
912 |
1/2✓ Branch 0 taken 1860 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 1860 times.
✗ Decision 'false' not taken.
|
1860 | if (!notm(tm)) { /* is there a finalizer? */ |
913 | int status; | |||
914 | 1860 | lu_byte oldah = L->allowhook; | ||
915 | 1860 | int oldgcstp = g->gcstp; | ||
916 | 1860 | g->gcstp |= GCSTPGC; /* avoid GC steps */ | ||
917 | 1860 | L->allowhook = 0; /* stop debug hooks during GC metamethod */ | ||
918 | 1860 | setobj2s(L, L->top.p++, tm); /* push finalizer... */ | ||
919 | 1860 | setobj2s(L, L->top.p++, &v); /* ... and its argument */ | ||
920 | 1860 | L->ci->callstatus |= CIST_FIN; /* will run a finalizer */ | ||
921 | 1860 | status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top.p - 2), 0); | ||
922 | 1860 | L->ci->callstatus &= ~CIST_FIN; /* not running a finalizer anymore */ | ||
923 | 1860 | L->allowhook = oldah; /* restore hooks */ | ||
924 | 1860 | g->gcstp = oldgcstp; /* restore state */ | ||
925 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1860 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | if (l_unlikely(status != LUA_OK)) { /* error while running __gc? */ |
926 | ✗ | luaE_warnerror(L, "__gc"); | ||
927 | ✗ | L->top.p--; /* pops error object */ | ||
928 | } | |||
929 | } | |||
930 | 1860 | } | ||
931 | ||||
932 | ||||
933 | /* | |||
934 | ** Call a few finalizers | |||
935 | */ | |||
936 | ✗ | static int runafewfinalizers (lua_State *L, int n) { | ||
937 | ✗ | global_State *g = G(L); | ||
938 | int i; | |||
939 | ✗ | for (i = 0; i < n && g->tobefnz; i++) | ||
940 | ✗ | GCTM(L); /* call one finalizer */ | ||
941 | ✗ | return i; | ||
942 | } | |||
943 | ||||
944 | ||||
945 | /* | |||
946 | ** call all pending finalizers | |||
947 | */ | |||
948 | 309 | static void callallpendingfinalizers (lua_State *L) { | ||
949 | 309 | global_State *g = G(L); | ||
950 |
2/2✓ Branch 0 taken 1860 times.
✓ Branch 1 taken 309 times.
|
2/2✓ Decision 'true' taken 1860 times.
✓ Decision 'false' taken 309 times.
|
2169 | while (g->tobefnz) |
951 | 1860 | GCTM(L); | ||
952 | 309 | } | ||
953 | ||||
954 | ||||
955 | /* | |||
956 | ** find last 'next' field in list 'p' list (to add elements in its end) | |||
957 | */ | |||
958 | 1236 | static GCObject **findlast (GCObject **p) { | ||
959 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1236 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1236 times.
|
1236 | while (*p != NULL) |
960 | ✗ | p = &(*p)->next; | ||
961 | 1236 | return p; | ||
962 | } | |||
963 | ||||
964 | ||||
965 | /* | |||
966 | ** Move all unreachable objects (or 'all' objects) that need | |||
967 | ** finalization from list 'finobj' to list 'tobefnz' (to be finalized). | |||
968 | ** (Note that objects after 'finobjold1' cannot be white, so they | |||
969 | ** don't need to be traversed. In incremental mode, 'finobjold1' is NULL, | |||
970 | ** so the whole list is traversed.) | |||
971 | */ | |||
972 | 1236 | static void separatetobefnz (global_State *g, int all) { | ||
973 | GCObject *curr; | |||
974 | 1236 | GCObject **p = &g->finobj; | ||
975 | 1236 | GCObject **lastnext = findlast(&g->tobefnz); | ||
976 |
2/2✓ Branch 0 taken 4641 times.
✓ Branch 1 taken 1236 times.
|
2/2✓ Decision 'true' taken 4641 times.
✓ Decision 'false' taken 1236 times.
|
5877 | while ((curr = *p) != g->finobjold1) { /* traverse all finalizable objects */ |
977 | lua_assert(tofinalize(curr)); | |||
978 |
3/4✓ Branch 0 taken 2781 times.
✓ Branch 1 taken 1860 times.
✓ Branch 2 taken 2781 times.
✗ Branch 3 not taken.
|
2/2✓ Decision 'true' taken 2781 times.
✓ Decision 'false' taken 1860 times.
|
4641 | if (!(iswhite(curr) || all)) /* not being collected? */ |
979 | 2781 | p = &curr->next; /* don't bother with it */ | ||
980 | else { | |||
981 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1860 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | if (curr == g->finobjsur) /* removing 'finobjsur'? */ |
982 | ✗ | g->finobjsur = curr->next; /* correct it */ | ||
983 | 1860 | *p = curr->next; /* remove 'curr' from 'finobj' list */ | ||
984 | 1860 | curr->next = *lastnext; /* link at the end of 'tobefnz' list */ | ||
985 | 1860 | *lastnext = curr; | ||
986 | 1860 | lastnext = &curr->next; | ||
987 | } | |||
988 | } | |||
989 | 1236 | } | ||
990 | ||||
991 | ||||
992 | /* | |||
993 | ** If pointer 'p' points to 'o', move it to the next element. | |||
994 | */ | |||
995 | 7440 | static void checkpointer (GCObject **p, GCObject *o) { | ||
996 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7440 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7440 times.
|
7440 | if (o == *p) |
997 | ✗ | *p = o->next; | ||
998 | 7440 | } | ||
999 | ||||
1000 | ||||
1001 | /* | |||
1002 | ** Correct pointers to objects inside 'allgc' list when | |||
1003 | ** object 'o' is being removed from the list. | |||
1004 | */ | |||
1005 | 1860 | static void correctpointers (global_State *g, GCObject *o) { | ||
1006 | 1860 | checkpointer(&g->survival, o); | ||
1007 | 1860 | checkpointer(&g->old1, o); | ||
1008 | 1860 | checkpointer(&g->reallyold, o); | ||
1009 | 1860 | checkpointer(&g->firstold1, o); | ||
1010 | 1860 | } | ||
1011 | ||||
1012 | ||||
1013 | /* | |||
1014 | ** if object 'o' has a finalizer, remove it from 'allgc' list (must | |||
1015 | ** search the list to find it) and link it in 'finobj' list. | |||
1016 | */ | |||
1017 | 1860 | void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) { | ||
1018 | 1860 | global_State *g = G(L); | ||
1019 |
2/4✓ Branch 0 taken 1860 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1860 times.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | if (tofinalize(o) || /* obj. is already marked... */ |
1020 |
2/4✓ Branch 0 taken 1860 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1860 times.
✗ Branch 4 not taken.
|
1860 | gfasttm(g, mt, TM_GC) == NULL || /* or has no finalizer... */ | |
1021 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1860 times.
|
1860 | (g->gcstp & GCSTPCLS)) /* or closing state? */ | |
1022 | ✗ | return; /* nothing to be done */ | ||
1023 | else { /* move 'o' to 'finobj' list */ | |||
1024 | GCObject **p; | |||
1025 |
2/4✓ Branch 0 taken 1860 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1860 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1860 times.
|
1860 | if (issweepphase(g)) { |
1026 | ✗ | makewhite(g, o); /* "sweep" object 'o' */ | ||
1027 | ✗ | if (g->sweepgc == &o->next) /* should not remove 'sweepgc' object */ | ||
1028 | ✗ | g->sweepgc = sweeptolive(L, g->sweepgc); /* change 'sweepgc' */ | ||
1029 | } | |||
1030 | else | |||
1031 | 1860 | correctpointers(g, o); | ||
1032 | /* search for pointer pointing to 'o' */ | |||
1033 |
2/2✓ Branch 0 taken 4017 times.
✓ Branch 1 taken 1860 times.
|
2/2✓ Decision 'true' taken 4017 times.
✓ Decision 'false' taken 1860 times.
|
5877 | for (p = &g->allgc; *p != o; p = &(*p)->next) { /* empty */ } |
1034 | 1860 | *p = o->next; /* remove 'o' from 'allgc' list */ | ||
1035 | 1860 | o->next = g->finobj; /* link it in 'finobj' list */ | ||
1036 | 1860 | g->finobj = o; | ||
1037 | 1860 | l_setbit(o->marked, FINALIZEDBIT); /* mark it as such */ | ||
1038 | } | |||
1039 | } | |||
1040 | ||||
1041 | /* }====================================================== */ | |||
1042 | ||||
1043 | ||||
1044 | /* | |||
1045 | ** {====================================================== | |||
1046 | ** Generational Collector | |||
1047 | ** ======================================================= | |||
1048 | */ | |||
1049 | ||||
1050 | ||||
1051 | /* | |||
1052 | ** Set the "time" to wait before starting a new GC cycle; cycle will | |||
1053 | ** start when memory use hits the threshold of ('estimate' * pause / | |||
1054 | ** PAUSEADJ). (Division by 'estimate' should be OK: it cannot be zero, | |||
1055 | ** because Lua cannot even start with less than PAUSEADJ bytes). | |||
1056 | */ | |||
1057 | 927 | static void setpause (global_State *g) { | ||
1058 | l_mem threshold, debt; | |||
1059 | 927 | int pause = getgcparam(g->gcpause); | ||
1060 | 927 | l_mem estimate = g->GCestimate / PAUSEADJ; /* adjust 'estimate' */ | ||
1061 | lua_assert(estimate > 0); | |||
1062 | 1854 | threshold = (pause < MAX_LMEM / estimate) /* overflow? */ | ||
1063 | 927 | ? estimate * pause /* no overflow */ | ||
1064 |
1/2✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
|
927 | : MAX_LMEM; /* overflow; truncate to maximum */ | |
1065 | 927 | debt = gettotalbytes(g) - threshold; | ||
1066 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | if (debt > 0) debt = 0; |
1067 | 927 | luaE_setdebt(g, debt); | ||
1068 | 927 | } | ||
1069 | ||||
1070 | ||||
1071 | /* | |||
1072 | ** Sweep a list of objects to enter generational mode. Deletes dead | |||
1073 | ** objects and turns the non dead to old. All non-dead threads---which | |||
1074 | ** are now old---must be in a gray list. Everything else is not in a | |||
1075 | ** gray list. Open upvalues are also kept gray. | |||
1076 | */ | |||
1077 | ✗ | static void sweep2old (lua_State *L, GCObject **p) { | ||
1078 | GCObject *curr; | |||
1079 | ✗ | global_State *g = G(L); | ||
1080 | ✗ | while ((curr = *p) != NULL) { | ||
1081 | ✗ | if (iswhite(curr)) { /* is 'curr' dead? */ | ||
1082 | lua_assert(isdead(g, curr)); | |||
1083 | ✗ | *p = curr->next; /* remove 'curr' from list */ | ||
1084 | ✗ | freeobj(L, curr); /* erase 'curr' */ | ||
1085 | } | |||
1086 | else { /* all surviving objects become old */ | |||
1087 | ✗ | setage(curr, G_OLD); | ||
1088 | ✗ | if (curr->tt == LUA_VTHREAD) { /* threads must be watched */ | ||
1089 | ✗ | lua_State *th = gco2th(curr); | ||
1090 | ✗ | linkgclist(th, g->grayagain); /* insert into 'grayagain' list */ | ||
1091 | } | |||
1092 | ✗ | else if (curr->tt == LUA_VUPVAL && upisopen(gco2upv(curr))) | ||
1093 | ✗ | set2gray(curr); /* open upvalues are always gray */ | ||
1094 | else /* everything else is black */ | |||
1095 | ✗ | nw2black(curr); | ||
1096 | ✗ | p = &curr->next; /* go to next element */ | ||
1097 | } | |||
1098 | } | |||
1099 | ✗ | } | ||
1100 | ||||
1101 | ||||
1102 | /* | |||
1103 | ** Sweep for generational mode. Delete dead objects. (Because the | |||
1104 | ** collection is not incremental, there are no "new white" objects | |||
1105 | ** during the sweep. So, any white object must be dead.) For | |||
1106 | ** non-dead objects, advance their ages and clear the color of | |||
1107 | ** new objects. (Old objects keep their colors.) | |||
1108 | ** The ages of G_TOUCHED1 and G_TOUCHED2 objects cannot be advanced | |||
1109 | ** here, because these old-generation objects are usually not swept | |||
1110 | ** here. They will all be advanced in 'correctgraylist'. That function | |||
1111 | ** will also remove objects turned white here from any gray list. | |||
1112 | */ | |||
1113 | ✗ | static GCObject **sweepgen (lua_State *L, global_State *g, GCObject **p, | ||
1114 | GCObject *limit, GCObject **pfirstold1) { | |||
1115 | static const lu_byte nextage[] = { | |||
1116 | G_SURVIVAL, /* from G_NEW */ | |||
1117 | G_OLD1, /* from G_SURVIVAL */ | |||
1118 | G_OLD1, /* from G_OLD0 */ | |||
1119 | G_OLD, /* from G_OLD1 */ | |||
1120 | G_OLD, /* from G_OLD (do not change) */ | |||
1121 | G_TOUCHED1, /* from G_TOUCHED1 (do not change) */ | |||
1122 | G_TOUCHED2 /* from G_TOUCHED2 (do not change) */ | |||
1123 | }; | |||
1124 | ✗ | int white = luaC_white(g); | ||
1125 | GCObject *curr; | |||
1126 | ✗ | while ((curr = *p) != limit) { | ||
1127 | ✗ | if (iswhite(curr)) { /* is 'curr' dead? */ | ||
1128 | lua_assert(!isold(curr) && isdead(g, curr)); | |||
1129 | ✗ | *p = curr->next; /* remove 'curr' from list */ | ||
1130 | ✗ | freeobj(L, curr); /* erase 'curr' */ | ||
1131 | } | |||
1132 | else { /* correct mark and age */ | |||
1133 | ✗ | if (getage(curr) == G_NEW) { /* new objects go back to white */ | ||
1134 | ✗ | int marked = curr->marked & ~maskgcbits; /* erase GC bits */ | ||
1135 | ✗ | curr->marked = cast_byte(marked | G_SURVIVAL | white); | ||
1136 | } | |||
1137 | else { /* all other objects will be old, and so keep their color */ | |||
1138 | ✗ | setage(curr, nextage[getage(curr)]); | ||
1139 | ✗ | if (getage(curr) == G_OLD1 && *pfirstold1 == NULL) | ||
1140 | ✗ | *pfirstold1 = curr; /* first OLD1 object in the list */ | ||
1141 | } | |||
1142 | ✗ | p = &curr->next; /* go to next element */ | ||
1143 | } | |||
1144 | } | |||
1145 | ✗ | return p; | ||
1146 | } | |||
1147 | ||||
1148 | ||||
1149 | /* | |||
1150 | ** Traverse a list making all its elements white and clearing their | |||
1151 | ** age. In incremental mode, all objects are 'new' all the time, | |||
1152 | ** except for fixed strings (which are always old). | |||
1153 | */ | |||
1154 | ✗ | static void whitelist (global_State *g, GCObject *p) { | ||
1155 | ✗ | int white = luaC_white(g); | ||
1156 | ✗ | for (; p != NULL; p = p->next) | ||
1157 | ✗ | p->marked = cast_byte((p->marked & ~maskgcbits) | white); | ||
1158 | ✗ | } | ||
1159 | ||||
1160 | ||||
1161 | /* | |||
1162 | ** Correct a list of gray objects. Return pointer to where rest of the | |||
1163 | ** list should be linked. | |||
1164 | ** Because this correction is done after sweeping, young objects might | |||
1165 | ** be turned white and still be in the list. They are only removed. | |||
1166 | ** 'TOUCHED1' objects are advanced to 'TOUCHED2' and remain on the list; | |||
1167 | ** Non-white threads also remain on the list; 'TOUCHED2' objects become | |||
1168 | ** regular old; they and anything else are removed from the list. | |||
1169 | */ | |||
1170 | ✗ | static GCObject **correctgraylist (GCObject **p) { | ||
1171 | GCObject *curr; | |||
1172 | ✗ | while ((curr = *p) != NULL) { | ||
1173 | ✗ | GCObject **next = getgclist(curr); | ||
1174 | ✗ | if (iswhite(curr)) | ||
1175 | ✗ | goto remove; /* remove all white objects */ | ||
1176 | ✗ | else if (getage(curr) == G_TOUCHED1) { /* touched in this cycle? */ | ||
1177 | lua_assert(isgray(curr)); | |||
1178 | ✗ | nw2black(curr); /* make it black, for next barrier */ | ||
1179 | ✗ | changeage(curr, G_TOUCHED1, G_TOUCHED2); | ||
1180 | ✗ | goto remain; /* keep it in the list and go to next element */ | ||
1181 | } | |||
1182 | ✗ | else if (curr->tt == LUA_VTHREAD) { | ||
1183 | lua_assert(isgray(curr)); | |||
1184 | ✗ | goto remain; /* keep non-white threads on the list */ | ||
1185 | } | |||
1186 | else { /* everything else is removed */ | |||
1187 | lua_assert(isold(curr)); /* young objects should be white here */ | |||
1188 | ✗ | if (getage(curr) == G_TOUCHED2) /* advance from TOUCHED2... */ | ||
1189 | ✗ | changeage(curr, G_TOUCHED2, G_OLD); /* ... to OLD */ | ||
1190 | ✗ | nw2black(curr); /* make object black (to be removed) */ | ||
1191 | ✗ | goto remove; | ||
1192 | } | |||
1193 | ✗ | remove: *p = *next; continue; | ||
1194 | ✗ | remain: p = next; continue; | ||
1195 | } | |||
1196 | ✗ | return p; | ||
1197 | } | |||
1198 | ||||
1199 | ||||
1200 | /* | |||
1201 | ** Correct all gray lists, coalescing them into 'grayagain'. | |||
1202 | */ | |||
1203 | ✗ | static void correctgraylists (global_State *g) { | ||
1204 | ✗ | GCObject **list = correctgraylist(&g->grayagain); | ||
1205 | ✗ | *list = g->weak; g->weak = NULL; | ||
1206 | ✗ | list = correctgraylist(list); | ||
1207 | ✗ | *list = g->allweak; g->allweak = NULL; | ||
1208 | ✗ | list = correctgraylist(list); | ||
1209 | ✗ | *list = g->ephemeron; g->ephemeron = NULL; | ||
1210 | ✗ | correctgraylist(list); | ||
1211 | ✗ | } | ||
1212 | ||||
1213 | ||||
1214 | /* | |||
1215 | ** Mark black 'OLD1' objects when starting a new young collection. | |||
1216 | ** Gray objects are already in some gray list, and so will be visited | |||
1217 | ** in the atomic step. | |||
1218 | */ | |||
1219 | ✗ | static void markold (global_State *g, GCObject *from, GCObject *to) { | ||
1220 | GCObject *p; | |||
1221 | ✗ | for (p = from; p != to; p = p->next) { | ||
1222 | ✗ | if (getage(p) == G_OLD1) { | ||
1223 | lua_assert(!iswhite(p)); | |||
1224 | ✗ | changeage(p, G_OLD1, G_OLD); /* now they are old */ | ||
1225 | ✗ | if (isblack(p)) | ||
1226 | ✗ | reallymarkobject(g, p); | ||
1227 | } | |||
1228 | } | |||
1229 | ✗ | } | ||
1230 | ||||
1231 | ||||
1232 | /* | |||
1233 | ** Finish a young-generation collection. | |||
1234 | */ | |||
1235 | ✗ | static void finishgencycle (lua_State *L, global_State *g) { | ||
1236 | ✗ | correctgraylists(g); | ||
1237 | ✗ | checkSizes(L, g); | ||
1238 | ✗ | g->gcstate = GCSpropagate; /* skip restart */ | ||
1239 | ✗ | if (!g->gcemergency) | ||
1240 | ✗ | callallpendingfinalizers(L); | ||
1241 | ✗ | } | ||
1242 | ||||
1243 | ||||
1244 | /* | |||
1245 | ** Does a young collection. First, mark 'OLD1' objects. Then does the | |||
1246 | ** atomic step. Then, sweep all lists and advance pointers. Finally, | |||
1247 | ** finish the collection. | |||
1248 | */ | |||
1249 | ✗ | static void youngcollection (lua_State *L, global_State *g) { | ||
1250 | GCObject **psurvival; /* to point to first non-dead survival object */ | |||
1251 | GCObject *dummy; /* dummy out parameter to 'sweepgen' */ | |||
1252 | lua_assert(g->gcstate == GCSpropagate); | |||
1253 | ✗ | if (g->firstold1) { /* are there regular OLD1 objects? */ | ||
1254 | ✗ | markold(g, g->firstold1, g->reallyold); /* mark them */ | ||
1255 | ✗ | g->firstold1 = NULL; /* no more OLD1 objects (for now) */ | ||
1256 | } | |||
1257 | ✗ | markold(g, g->finobj, g->finobjrold); | ||
1258 | ✗ | markold(g, g->tobefnz, NULL); | ||
1259 | ✗ | atomic(L); | ||
1260 | ||||
1261 | /* sweep nursery and get a pointer to its last live element */ | |||
1262 | ✗ | g->gcstate = GCSswpallgc; | ||
1263 | ✗ | psurvival = sweepgen(L, g, &g->allgc, g->survival, &g->firstold1); | ||
1264 | /* sweep 'survival' */ | |||
1265 | ✗ | sweepgen(L, g, psurvival, g->old1, &g->firstold1); | ||
1266 | ✗ | g->reallyold = g->old1; | ||
1267 | ✗ | g->old1 = *psurvival; /* 'survival' survivals are old now */ | ||
1268 | ✗ | g->survival = g->allgc; /* all news are survivals */ | ||
1269 | ||||
1270 | /* repeat for 'finobj' lists */ | |||
1271 | ✗ | dummy = NULL; /* no 'firstold1' optimization for 'finobj' lists */ | ||
1272 | ✗ | psurvival = sweepgen(L, g, &g->finobj, g->finobjsur, &dummy); | ||
1273 | /* sweep 'survival' */ | |||
1274 | ✗ | sweepgen(L, g, psurvival, g->finobjold1, &dummy); | ||
1275 | ✗ | g->finobjrold = g->finobjold1; | ||
1276 | ✗ | g->finobjold1 = *psurvival; /* 'survival' survivals are old now */ | ||
1277 | ✗ | g->finobjsur = g->finobj; /* all news are survivals */ | ||
1278 | ||||
1279 | ✗ | sweepgen(L, g, &g->tobefnz, NULL, &dummy); | ||
1280 | ✗ | finishgencycle(L, g); | ||
1281 | ✗ | } | ||
1282 | ||||
1283 | ||||
1284 | /* | |||
1285 | ** Clears all gray lists, sweeps objects, and prepare sublists to enter | |||
1286 | ** generational mode. The sweeps remove dead objects and turn all | |||
1287 | ** surviving objects to old. Threads go back to 'grayagain'; everything | |||
1288 | ** else is turned black (not in any gray list). | |||
1289 | */ | |||
1290 | ✗ | static void atomic2gen (lua_State *L, global_State *g) { | ||
1291 | ✗ | cleargraylists(g); | ||
1292 | /* sweep all elements making them old */ | |||
1293 | ✗ | g->gcstate = GCSswpallgc; | ||
1294 | ✗ | sweep2old(L, &g->allgc); | ||
1295 | /* everything alive now is old */ | |||
1296 | ✗ | g->reallyold = g->old1 = g->survival = g->allgc; | ||
1297 | ✗ | g->firstold1 = NULL; /* there are no OLD1 objects anywhere */ | ||
1298 | ||||
1299 | /* repeat for 'finobj' lists */ | |||
1300 | ✗ | sweep2old(L, &g->finobj); | ||
1301 | ✗ | g->finobjrold = g->finobjold1 = g->finobjsur = g->finobj; | ||
1302 | ||||
1303 | ✗ | sweep2old(L, &g->tobefnz); | ||
1304 | ||||
1305 | ✗ | g->gckind = KGC_GEN; | ||
1306 | ✗ | g->lastatomic = 0; | ||
1307 | ✗ | g->GCestimate = gettotalbytes(g); /* base for memory control */ | ||
1308 | ✗ | finishgencycle(L, g); | ||
1309 | ✗ | } | ||
1310 | ||||
1311 | ||||
1312 | /* | |||
1313 | ** Set debt for the next minor collection, which will happen when | |||
1314 | ** memory grows 'genminormul'%. | |||
1315 | */ | |||
1316 | ✗ | static void setminordebt (global_State *g) { | ||
1317 | ✗ | luaE_setdebt(g, -(cast(l_mem, (gettotalbytes(g) / 100)) * g->genminormul)); | ||
1318 | ✗ | } | ||
1319 | ||||
1320 | ||||
1321 | /* | |||
1322 | ** Enter generational mode. Must go until the end of an atomic cycle | |||
1323 | ** to ensure that all objects are correctly marked and weak tables | |||
1324 | ** are cleared. Then, turn all objects into old and finishes the | |||
1325 | ** collection. | |||
1326 | */ | |||
1327 | ✗ | static lu_mem entergen (lua_State *L, global_State *g) { | ||
1328 | lu_mem numobjs; | |||
1329 | ✗ | luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */ | ||
1330 | ✗ | luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ | ||
1331 | ✗ | numobjs = atomic(L); /* propagates all and then do the atomic stuff */ | ||
1332 | ✗ | atomic2gen(L, g); | ||
1333 | ✗ | setminordebt(g); /* set debt assuming next cycle will be minor */ | ||
1334 | ✗ | return numobjs; | ||
1335 | } | |||
1336 | ||||
1337 | ||||
1338 | /* | |||
1339 | ** Enter incremental mode. Turn all objects white, make all | |||
1340 | ** intermediate lists point to NULL (to avoid invalid pointers), | |||
1341 | ** and go to the pause state. | |||
1342 | */ | |||
1343 | ✗ | static void enterinc (global_State *g) { | ||
1344 | ✗ | whitelist(g, g->allgc); | ||
1345 | ✗ | g->reallyold = g->old1 = g->survival = NULL; | ||
1346 | ✗ | whitelist(g, g->finobj); | ||
1347 | ✗ | whitelist(g, g->tobefnz); | ||
1348 | ✗ | g->finobjrold = g->finobjold1 = g->finobjsur = NULL; | ||
1349 | ✗ | g->gcstate = GCSpause; | ||
1350 | ✗ | g->gckind = KGC_INC; | ||
1351 | ✗ | g->lastatomic = 0; | ||
1352 | ✗ | } | ||
1353 | ||||
1354 | ||||
1355 | /* | |||
1356 | ** Change collector mode to 'newmode'. | |||
1357 | */ | |||
1358 | 618 | void luaC_changemode (lua_State *L, int newmode) { | ||
1359 | 618 | global_State *g = G(L); | ||
1360 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 618 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 618 times.
|
618 | if (newmode != g->gckind) { |
1361 | ✗ | if (newmode == KGC_GEN) /* entering generational mode? */ | ||
1362 | ✗ | entergen(L, g); | ||
1363 | else | |||
1364 | ✗ | enterinc(g); /* entering incremental mode */ | ||
1365 | } | |||
1366 | 618 | g->lastatomic = 0; | ||
1367 | 618 | } | ||
1368 | ||||
1369 | ||||
1370 | /* | |||
1371 | ** Does a full collection in generational mode. | |||
1372 | */ | |||
1373 | ✗ | static lu_mem fullgen (lua_State *L, global_State *g) { | ||
1374 | ✗ | enterinc(g); | ||
1375 | ✗ | return entergen(L, g); | ||
1376 | } | |||
1377 | ||||
1378 | ||||
1379 | /* | |||
1380 | ** Does a major collection after last collection was a "bad collection". | |||
1381 | ** | |||
1382 | ** When the program is building a big structure, it allocates lots of | |||
1383 | ** memory but generates very little garbage. In those scenarios, | |||
1384 | ** the generational mode just wastes time doing small collections, and | |||
1385 | ** major collections are frequently what we call a "bad collection", a | |||
1386 | ** collection that frees too few objects. To avoid the cost of switching | |||
1387 | ** between generational mode and the incremental mode needed for full | |||
1388 | ** (major) collections, the collector tries to stay in incremental mode | |||
1389 | ** after a bad collection, and to switch back to generational mode only | |||
1390 | ** after a "good" collection (one that traverses less than 9/8 objects | |||
1391 | ** of the previous one). | |||
1392 | ** The collector must choose whether to stay in incremental mode or to | |||
1393 | ** switch back to generational mode before sweeping. At this point, it | |||
1394 | ** does not know the real memory in use, so it cannot use memory to | |||
1395 | ** decide whether to return to generational mode. Instead, it uses the | |||
1396 | ** number of objects traversed (returned by 'atomic') as a proxy. The | |||
1397 | ** field 'g->lastatomic' keeps this count from the last collection. | |||
1398 | ** ('g->lastatomic != 0' also means that the last collection was bad.) | |||
1399 | */ | |||
1400 | ✗ | static void stepgenfull (lua_State *L, global_State *g) { | ||
1401 | lu_mem newatomic; /* count of traversed objects */ | |||
1402 | ✗ | lu_mem lastatomic = g->lastatomic; /* count from last collection */ | ||
1403 | ✗ | if (g->gckind == KGC_GEN) /* still in generational mode? */ | ||
1404 | ✗ | enterinc(g); /* enter incremental mode */ | ||
1405 | ✗ | luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ | ||
1406 | ✗ | newatomic = atomic(L); /* mark everybody */ | ||
1407 | ✗ | if (newatomic < lastatomic + (lastatomic >> 3)) { /* good collection? */ | ||
1408 | ✗ | atomic2gen(L, g); /* return to generational mode */ | ||
1409 | ✗ | setminordebt(g); | ||
1410 | } | |||
1411 | else { /* another bad collection; stay in incremental mode */ | |||
1412 | ✗ | g->GCestimate = gettotalbytes(g); /* first estimate */; | ||
1413 | ✗ | entersweep(L); | ||
1414 | ✗ | luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ | ||
1415 | ✗ | setpause(g); | ||
1416 | ✗ | g->lastatomic = newatomic; | ||
1417 | } | |||
1418 | ✗ | } | ||
1419 | ||||
1420 | ||||
1421 | /* | |||
1422 | ** Does a generational "step". | |||
1423 | ** Usually, this means doing a minor collection and setting the debt to | |||
1424 | ** make another collection when memory grows 'genminormul'% larger. | |||
1425 | ** | |||
1426 | ** However, there are exceptions. If memory grows 'genmajormul'% | |||
1427 | ** larger than it was at the end of the last major collection (kept | |||
1428 | ** in 'g->GCestimate'), the function does a major collection. At the | |||
1429 | ** end, it checks whether the major collection was able to free a | |||
1430 | ** decent amount of memory (at least half the growth in memory since | |||
1431 | ** previous major collection). If so, the collector keeps its state, | |||
1432 | ** and the next collection will probably be minor again. Otherwise, | |||
1433 | ** we have what we call a "bad collection". In that case, set the field | |||
1434 | ** 'g->lastatomic' to signal that fact, so that the next collection will | |||
1435 | ** go to 'stepgenfull'. | |||
1436 | ** | |||
1437 | ** 'GCdebt <= 0' means an explicit call to GC step with "size" zero; | |||
1438 | ** in that case, do a minor collection. | |||
1439 | */ | |||
1440 | ✗ | static void genstep (lua_State *L, global_State *g) { | ||
1441 | ✗ | if (g->lastatomic != 0) /* last collection was a bad one? */ | ||
1442 | ✗ | stepgenfull(L, g); /* do a full step */ | ||
1443 | else { | |||
1444 | ✗ | lu_mem majorbase = g->GCestimate; /* memory after last major collection */ | ||
1445 | ✗ | lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul); | ||
1446 | ✗ | if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) { | ||
1447 | ✗ | lu_mem numobjs = fullgen(L, g); /* do a major collection */ | ||
1448 | ✗ | if (gettotalbytes(g) < majorbase + (majorinc / 2)) { | ||
1449 | /* collected at least half of memory growth since last major | |||
1450 | collection; keep doing minor collections. */ | |||
1451 | lua_assert(g->lastatomic == 0); | |||
1452 | } | |||
1453 | else { /* bad collection */ | |||
1454 | ✗ | g->lastatomic = numobjs; /* signal that last collection was bad */ | ||
1455 | ✗ | setpause(g); /* do a long wait for next (major) collection */ | ||
1456 | } | |||
1457 | } | |||
1458 | else { /* regular case; do a minor collection */ | |||
1459 | ✗ | youngcollection(L, g); | ||
1460 | ✗ | setminordebt(g); | ||
1461 | ✗ | g->GCestimate = majorbase; /* preserve base value */ | ||
1462 | } | |||
1463 | } | |||
1464 | lua_assert(isdecGCmodegen(g)); | |||
1465 | ✗ | } | ||
1466 | ||||
1467 | /* }====================================================== */ | |||
1468 | ||||
1469 | ||||
1470 | /* | |||
1471 | ** {====================================================== | |||
1472 | ** GC control | |||
1473 | ** ======================================================= | |||
1474 | */ | |||
1475 | ||||
1476 | ||||
1477 | /* | |||
1478 | ** Enter first sweep phase. | |||
1479 | ** The call to 'sweeptolive' makes the pointer point to an object | |||
1480 | ** inside the list (instead of to the header), so that the real sweep do | |||
1481 | ** not need to skip objects created between "now" and the start of the | |||
1482 | ** real sweep. | |||
1483 | */ | |||
1484 | 927 | static void entersweep (lua_State *L) { | ||
1485 | 927 | global_State *g = G(L); | ||
1486 | 927 | g->gcstate = GCSswpallgc; | ||
1487 | lua_assert(g->sweepgc == NULL); | |||
1488 | 927 | g->sweepgc = sweeptolive(L, &g->allgc); | ||
1489 | 927 | } | ||
1490 | ||||
1491 | ||||
1492 | /* | |||
1493 | ** Delete all objects in list 'p' until (but not including) object | |||
1494 | ** 'limit'. | |||
1495 | */ | |||
1496 | 618 | static void deletelist (lua_State *L, GCObject *p, GCObject *limit) { | ||
1497 |
2/2✓ Branch 0 taken 73409 times.
✓ Branch 1 taken 618 times.
|
2/2✓ Decision 'true' taken 73409 times.
✓ Decision 'false' taken 618 times.
|
74027 | while (p != limit) { |
1498 | 73409 | GCObject *next = p->next; | ||
1499 | 73409 | freeobj(L, p); | ||
1500 | 73409 | p = next; | ||
1501 | } | |||
1502 | 618 | } | ||
1503 | ||||
1504 | ||||
1505 | /* | |||
1506 | ** Call all finalizers of the objects in the given Lua state, and | |||
1507 | ** then free all objects, except for the main thread. | |||
1508 | */ | |||
1509 | 309 | void luaC_freeallobjects (lua_State *L) { | ||
1510 | 309 | global_State *g = G(L); | ||
1511 | 309 | g->gcstp = GCSTPCLS; /* no extra finalizers after here */ | ||
1512 | 309 | luaC_changemode(L, KGC_INC); | ||
1513 | 309 | separatetobefnz(g, 1); /* separate all objects with finalizers */ | ||
1514 | lua_assert(g->finobj == NULL); | |||
1515 | 309 | callallpendingfinalizers(L); | ||
1516 | 309 | deletelist(L, g->allgc, obj2gco(g->mainthread)); | ||
1517 | lua_assert(g->finobj == NULL); /* no new finalizers */ | |||
1518 | 309 | deletelist(L, g->fixedgc, NULL); /* collect fixed objects */ | ||
1519 | lua_assert(g->strt.nuse == 0); | |||
1520 | 309 | } | ||
1521 | ||||
1522 | ||||
1523 | 927 | static lu_mem atomic (lua_State *L) { | ||
1524 | 927 | global_State *g = G(L); | ||
1525 | 927 | lu_mem work = 0; | ||
1526 | GCObject *origweak, *origall; | |||
1527 | 927 | GCObject *grayagain = g->grayagain; /* save original list */ | ||
1528 | 927 | g->grayagain = NULL; | ||
1529 | lua_assert(g->ephemeron == NULL && g->weak == NULL); | |||
1530 | lua_assert(!iswhite(g->mainthread)); | |||
1531 | 927 | g->gcstate = GCSatomic; | ||
1532 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
|
927 | markobject(g, L); /* mark running thread */ | |
1533 | /* registry and global metatables may be changed by API */ | |||
1534 |
2/4✓ Branch 0 taken 927 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 927 times.
|
927 | markvalue(g, &g->l_registry); | |
1535 | 927 | markmt(g); /* mark global metatables */ | ||
1536 | 927 | work += propagateall(g); /* empties 'gray' list */ | ||
1537 | /* remark occasional upvalues of (maybe) dead threads */ | |||
1538 | 927 | work += remarkupvals(g); | ||
1539 | 927 | work += propagateall(g); /* propagate changes */ | ||
1540 | 927 | g->gray = grayagain; | ||
1541 | 927 | work += propagateall(g); /* traverse 'grayagain' list */ | ||
1542 | 927 | convergeephemerons(g); | ||
1543 | /* at this point, all strongly accessible objects are marked. */ | |||
1544 | /* Clear values from weak tables, before checking finalizers */ | |||
1545 | 927 | clearbyvalues(g, g->weak, NULL); | ||
1546 | 927 | clearbyvalues(g, g->allweak, NULL); | ||
1547 | 927 | origweak = g->weak; origall = g->allweak; | ||
1548 | 927 | separatetobefnz(g, 0); /* separate objects to be finalized */ | ||
1549 | 927 | work += markbeingfnz(g); /* mark objects that will be finalized */ | ||
1550 | 927 | work += propagateall(g); /* remark, to propagate 'resurrection' */ | ||
1551 | 927 | convergeephemerons(g); | ||
1552 | /* at this point, all resurrected objects are marked. */ | |||
1553 | /* remove dead objects from weak tables */ | |||
1554 | 927 | clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron tables */ | ||
1555 | 927 | clearbykeys(g, g->allweak); /* clear keys from all 'allweak' tables */ | ||
1556 | /* clear values from resurrected weak tables */ | |||
1557 | 927 | clearbyvalues(g, g->weak, origweak); | ||
1558 | 927 | clearbyvalues(g, g->allweak, origall); | ||
1559 | 927 | luaS_clearcache(g); | ||
1560 | 927 | g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ | ||
1561 | lua_assert(g->gray == NULL); | |||
1562 | 927 | return work; /* estimate of slots marked by 'atomic' */ | ||
1563 | } | |||
1564 | ||||
1565 | ||||
1566 | 5871 | static int sweepstep (lua_State *L, global_State *g, | ||
1567 | int nextstate, GCObject **nextlist) { | |||
1568 |
2/2✓ Branch 0 taken 3090 times.
✓ Branch 1 taken 2781 times.
|
2/2✓ Decision 'true' taken 3090 times.
✓ Decision 'false' taken 2781 times.
|
5871 | if (g->sweepgc) { |
1569 | 3090 | l_mem olddebt = g->GCdebt; | ||
1570 | int count; | |||
1571 | 3090 | g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX, &count); | ||
1572 | 3090 | g->GCestimate += g->GCdebt - olddebt; /* update estimate */ | ||
1573 | 3090 | return count; | ||
1574 | } | |||
1575 | else { /* enter next state */ | |||
1576 | 2781 | g->gcstate = nextstate; | ||
1577 | 2781 | g->sweepgc = nextlist; | ||
1578 | 2781 | return 0; /* no work done */ | ||
1579 | } | |||
1580 | } | |||
1581 | ||||
1582 | ||||
1583 | 42024 | static lu_mem singlestep (lua_State *L) { | ||
1584 | 42024 | global_State *g = G(L); | ||
1585 | lu_mem work; | |||
1586 | lua_assert(!g->gcstopem); /* collector is not reentrant */ | |||
1587 | 42024 | g->gcstopem = 1; /* no emergency collections while collecting */ | ||
1588 |
8/9✓ Branch 0 taken 927 times.
✓ Branch 1 taken 32445 times.
✓ Branch 2 taken 927 times.
✓ Branch 3 taken 2163 times.
✓ Branch 4 taken 1854 times.
✓ Branch 5 taken 1854 times.
✓ Branch 6 taken 927 times.
✓ Branch 7 taken 927 times.
✗ Branch 8 not taken.
|
42024 | switch (g->gcstate) { | |
1589 |
1/1✓ Decision 'true' taken 927 times.
|
927 | case GCSpause: { | |
1590 | 927 | restartcollection(g); | ||
1591 | 927 | g->gcstate = GCSpropagate; | ||
1592 | 927 | work = 1; | ||
1593 | 927 | break; | ||
1594 | } | |||
1595 |
1/1✓ Decision 'true' taken 32445 times.
|
32445 | case GCSpropagate: { | |
1596 |
2/2✓ Branch 0 taken 927 times.
✓ Branch 1 taken 31518 times.
|
2/2✓ Decision 'true' taken 927 times.
✓ Decision 'false' taken 31518 times.
|
32445 | if (g->gray == NULL) { /* no more gray objects? */ |
1597 | 927 | g->gcstate = GCSenteratomic; /* finish propagate phase */ | ||
1598 | 927 | work = 0; | ||
1599 | } | |||
1600 | else | |||
1601 | 31518 | work = propagatemark(g); /* traverse one gray object */ | ||
1602 | 32445 | break; | ||
1603 | } | |||
1604 |
1/1✓ Decision 'true' taken 927 times.
|
927 | case GCSenteratomic: { | |
1605 | 927 | work = atomic(L); /* work is what was traversed by 'atomic' */ | ||
1606 | 927 | entersweep(L); | ||
1607 | 927 | g->GCestimate = gettotalbytes(g); /* first estimate */; | ||
1608 | 927 | break; | ||
1609 | } | |||
1610 |
1/1✓ Decision 'true' taken 2163 times.
|
2163 | case GCSswpallgc: { /* sweep "regular" objects */ | |
1611 | 2163 | work = sweepstep(L, g, GCSswpfinobj, &g->finobj); | ||
1612 | 2163 | break; | ||
1613 | } | |||
1614 |
1/1✓ Decision 'true' taken 1854 times.
|
1854 | case GCSswpfinobj: { /* sweep objects with finalizers */ | |
1615 | 1854 | work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz); | ||
1616 | 1854 | break; | ||
1617 | } | |||
1618 |
1/1✓ Decision 'true' taken 1854 times.
|
1854 | case GCSswptobefnz: { /* sweep objects to be finalized */ | |
1619 | 1854 | work = sweepstep(L, g, GCSswpend, NULL); | ||
1620 | 1854 | break; | ||
1621 | } | |||
1622 |
1/1✓ Decision 'true' taken 927 times.
|
927 | case GCSswpend: { /* finish sweeps */ | |
1623 | 927 | checkSizes(L, g); | ||
1624 | 927 | g->gcstate = GCScallfin; | ||
1625 | 927 | work = 0; | ||
1626 | 927 | break; | ||
1627 | } | |||
1628 |
1/1✓ Decision 'true' taken 927 times.
|
927 | case GCScallfin: { /* call remaining finalizers */ | |
1629 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 927 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 927 times.
|
927 | if (g->tobefnz && !g->gcemergency) { |
1630 | ✗ | g->gcstopem = 0; /* ok collections during finalizers */ | ||
1631 | ✗ | work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST; | ||
1632 | } | |||
1633 | else { /* emergency mode or no more finalizers */ | |||
1634 | 927 | g->gcstate = GCSpause; /* finish collection */ | ||
1635 | 927 | work = 0; | ||
1636 | } | |||
1637 | 927 | break; | ||
1638 | } | |||
1639 | ✗ | default: lua_assert(0); return 0; | ||
1640 | } | |||
1641 | 42024 | g->gcstopem = 0; | ||
1642 | 42024 | return work; | ||
1643 | } | |||
1644 | ||||
1645 | ||||
1646 | /* | |||
1647 | ** advances the garbage collector until it reaches a state allowed | |||
1648 | ** by 'statemask' | |||
1649 | */ | |||
1650 | 927 | void luaC_runtilstate (lua_State *L, int statesmask) { | ||
1651 | 927 | global_State *g = G(L); | ||
1652 |
2/2✓ Branch 0 taken 24411 times.
✓ Branch 1 taken 927 times.
|
2/2✓ Decision 'true' taken 24411 times.
✓ Decision 'false' taken 927 times.
|
25338 | while (!testbit(statesmask, g->gcstate)) |
1653 | 24411 | singlestep(L); | ||
1654 | 927 | } | ||
1655 | ||||
1656 | ||||
1657 | ||||
1658 | /* | |||
1659 | ** Performs a basic incremental step. The debt and step size are | |||
1660 | ** converted from bytes to "units of work"; then the function loops | |||
1661 | ** running single steps until adding that many units of work or | |||
1662 | ** finishing a cycle (pause state). Finally, it sets the debt that | |||
1663 | ** controls when next step will be performed. | |||
1664 | */ | |||
1665 | 618 | static void incstep (lua_State *L, global_State *g) { | ||
1666 | 618 | int stepmul = (getgcparam(g->gcstepmul) | 1); /* avoid division by 0 */ | ||
1667 | 618 | l_mem debt = (g->GCdebt / WORK2MEM) * stepmul; | ||
1668 | 618 | l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem)) | ||
1669 | 618 | ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul | ||
1670 |
1/2✓ Branch 0 taken 618 times.
✗ Branch 1 not taken.
|
618 | : MAX_LMEM; /* overflow; keep maximum value */ | |
1671 | do { /* repeat until pause or enough "credit" (negative debt) */ | |||
1672 | 17613 | lu_mem work = singlestep(L); /* perform one single step */ | ||
1673 | 17613 | debt -= work; | ||
1674 |
3/4✓ Branch 0 taken 17613 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16995 times.
✓ Branch 3 taken 618 times.
|
0/1? Decision couldn't be analyzed.
|
17613 | } while (debt > -stepsize && g->gcstate != GCSpause); |
1675 |
1/2✓ Branch 0 taken 618 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 618 times.
✗ Decision 'false' not taken.
|
618 | if (g->gcstate == GCSpause) |
1676 | 618 | setpause(g); /* pause until next cycle */ | ||
1677 | else { | |||
1678 | ✗ | debt = (debt / stepmul) * WORK2MEM; /* convert 'work units' to bytes */ | ||
1679 | ✗ | luaE_setdebt(g, debt); | ||
1680 | } | |||
1681 | 618 | } | ||
1682 | ||||
1683 | /* | |||
1684 | ** Performs a basic GC step if collector is running. (If collector is | |||
1685 | ** not running, set a reasonable debt to avoid it being called at | |||
1686 | ** every single check.) | |||
1687 | */ | |||
1688 | 618 | void luaC_step (lua_State *L) { | ||
1689 | 618 | global_State *g = G(L); | ||
1690 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 618 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 618 times.
|
618 | if (!gcrunning(g)) /* not running? */ |
1691 | ✗ | luaE_setdebt(g, -2000); | ||
1692 | else { | |||
1693 |
2/4✓ Branch 0 taken 618 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 618 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 618 times.
|
618 | if(isdecGCmodegen(g)) |
1694 | ✗ | genstep(L, g); | ||
1695 | else | |||
1696 | 618 | incstep(L, g); | ||
1697 | } | |||
1698 | 618 | } | ||
1699 | ||||
1700 | ||||
1701 | /* | |||
1702 | ** Perform a full collection in incremental mode. | |||
1703 | ** Before running the collection, check 'keepinvariant'; if it is true, | |||
1704 | ** there may be some objects marked as black, so the collector has | |||
1705 | ** to sweep all objects to turn them back to white (as white has not | |||
1706 | ** changed, nothing will be collected). | |||
1707 | */ | |||
1708 | 309 | static void fullinc (lua_State *L, global_State *g) { | ||
1709 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 309 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 309 times.
|
309 | if (keepinvariant(g)) /* black objects? */ |
1710 | ✗ | entersweep(L); /* sweep everything to turn them back to white */ | ||
1711 | /* finish any pending sweep phase to start a new cycle */ | |||
1712 | 309 | luaC_runtilstate(L, bitmask(GCSpause)); | ||
1713 | 309 | luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */ | ||
1714 | /* estimate must be correct after a full GC cycle */ | |||
1715 | lua_assert(g->GCestimate == gettotalbytes(g)); | |||
1716 | 309 | luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ | ||
1717 | 309 | setpause(g); | ||
1718 | 309 | } | ||
1719 | ||||
1720 | ||||
1721 | /* | |||
1722 | ** Performs a full GC cycle; if 'isemergency', set a flag to avoid | |||
1723 | ** some operations which could change the interpreter state in some | |||
1724 | ** unexpected ways (running finalizers and shrinking some structures). | |||
1725 | */ | |||
1726 | 309 | void luaC_fullgc (lua_State *L, int isemergency) { | ||
1727 | 309 | global_State *g = G(L); | ||
1728 | lua_assert(!g->gcemergency); | |||
1729 | 309 | g->gcemergency = isemergency; /* set flag */ | ||
1730 |
1/2✓ Branch 0 taken 309 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 309 times.
✗ Decision 'false' not taken.
|
309 | if (g->gckind == KGC_INC) |
1731 | 309 | fullinc(L, g); | ||
1732 | else | |||
1733 | ✗ | fullgen(L, g); | ||
1734 | 309 | g->gcemergency = 0; | ||
1735 | 309 | } | ||
1736 | ||||
1737 | /* }====================================================== */ | |||
1738 | ||||
1739 | ||||
1740 |