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