| 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 | 61479 | static GCObject **getgclist (GCObject *o) { | ||
| 126 |
4/7✓ Branch 0 taken 22572 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16632 times.
✓ Branch 3 taken 2673 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 19602 times.
✗ Branch 6 not taken.
|
61479 | switch (o->tt) { | |
| 127 |
1/1✓ Decision 'true' taken 22572 times.
|
22572 | case LUA_VTABLE: return &gco2t(o)->gclist; | |
| 128 | ✗ | case LUA_VLCL: return &gco2lcl(o)->gclist; | ||
| 129 |
1/1✓ Decision 'true' taken 16632 times.
|
16632 | case LUA_VCCL: return &gco2ccl(o)->gclist; | |
| 130 |
1/1✓ Decision 'true' taken 2673 times.
|
2673 | case LUA_VTHREAD: return &gco2th(o)->gclist; | |
| 131 | ✗ | case LUA_VPROTO: return &gco2p(o)->gclist; | ||
| 132 |
1/1✓ Decision 'true' taken 19602 times.
|
19602 | case LUA_VUSERDATA: { | |
| 133 | 19602 | Udata *u = gco2u(o); | ||
| 134 | lua_assert(u->nuvalue > 0); | |||
| 135 | 19602 | 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 | 31185 | static void linkgclist_ (GCObject *o, GCObject **pnext, GCObject **list) { | ||
| 149 | lua_assert(!isgray(o)); /* cannot be in a gray list */ | |||
| 150 | 31185 | *pnext = *list; | ||
| 151 | 31185 | *list = o; | ||
| 152 | 31185 | set2gray(o); /* now it is */ | ||
| 153 | 31185 | } | ||
| 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 | 10989 | static void clearkey (Node *n) { | ||
| 172 | lua_assert(isempty(gval(n))); | |||
| 173 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10989 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 10989 times.
|
10989 | if (keyiscollectable(n)) |
| 174 | ✗ | setdeadkey(n); /* unused key; remove it */ | ||
| 175 | 10989 | } | ||
| 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 | 14553 | void luaC_fix (lua_State *L, GCObject *o) { | ||
| 244 | 14553 | global_State *g = G(L); | ||
| 245 | lua_assert(g->allgc == o); /* object must be 1st in 'allgc' list! */ | |||
| 246 | 14553 | set2gray(o); /* they will be gray forever */ | ||
| 247 | 14553 | setage(o, G_OLD); /* and old forever */ | ||
| 248 | 14553 | g->allgc = o->next; /* remove object from 'allgc' list */ | ||
| 249 | 14553 | o->next = g->fixedgc; /* link it to 'fixedgc' list */ | ||
| 250 | 14553 | g->fixedgc = o; | ||
| 251 | 14553 | } | ||
| 252 | ||||
| 253 | ||||
| 254 | /* | |||
| 255 | ** create a new collectable object (with given type, size, and offset) | |||
| 256 | ** and link it to 'allgc' list. | |||
| 257 | */ | |||
| 258 | 70922 | GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) { | ||
| 259 | 70922 | global_State *g = G(L); | ||
| 260 | 70922 | char *p = cast_charp(luaM_newobject(L, novariant(tt), sz)); | ||
| 261 | 70922 | GCObject *o = cast(GCObject *, p + offset); | ||
| 262 | 70922 | o->marked = luaC_white(g); | ||
| 263 | 70922 | o->tt = tt; | ||
| 264 | 70922 | o->next = g->allgc; | ||
| 265 | 70922 | g->allgc = o; | ||
| 266 | 70922 | return o; | ||
| 267 | } | |||
| 268 | ||||
| 269 | ||||
| 270 | 70922 | GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) { | ||
| 271 | 70922 | 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 | 77517 | static void reallymarkobject (global_State *g, GCObject *o) { | ||
| 298 |
3/5✓ Branch 0 taken 46629 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 10395 times.
✓ Branch 3 taken 20493 times.
✗ Branch 4 not taken.
|
77517 | switch (o->tt) { | |
| 299 |
1/1✓ Decision 'true' taken 46629 times.
|
46629 | case LUA_VSHRSTR: | |
| 300 | case LUA_VLNGSTR: { | |||
| 301 |
1/1✓ Decision 'true' taken 46629 times.
|
46629 | set2black(o); /* nothing to visit */ | |
| 302 | 46629 | 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 10395 times.
|
10395 | case LUA_VUSERDATA: { | |
| 314 | 10395 | Udata *u = gco2u(o); | ||
| 315 |
2/2✓ Branch 0 taken 594 times.
✓ Branch 1 taken 9801 times.
|
2/2✓ Decision 'true' taken 594 times.
✓ Decision 'false' taken 9801 times.
|
10395 | if (u->nuvalue == 0) { /* no user values? */ |
| 316 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 594 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
594 | markobjectN(g, u->metatable); /* mark its metatable */ | |
| 317 | 594 | set2black(u); /* nothing else to mark */ | ||
| 318 | 594 | 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 30294 times.
|
30294 | linkobjgclist(o, g->gray); /* to be visited later */ | |
| 325 | 30294 | break; | ||
| 326 | } | |||
| 327 | ✗ | default: lua_assert(0); break; | ||
| 328 | } | |||
| 329 | 77517 | } | ||
| 330 | ||||
| 331 | ||||
| 332 | /* | |||
| 333 | ** mark metamethods for basic types | |||
| 334 | */ | |||
| 335 | 1782 | static void markmt (global_State *g) { | ||
| 336 | int i; | |||
| 337 |
2/2✓ Branch 0 taken 16038 times.
✓ Branch 1 taken 1782 times.
|
2/2✓ Decision 'true' taken 16038 times.
✓ Decision 'false' taken 1782 times.
|
17820 | for (i=0; i < LUA_NUMTAGS; i++) |
| 338 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 16038 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
16038 | markobjectN(g, g->mt[i]); | |
| 339 | 1782 | } | ||
| 340 | ||||
| 341 | ||||
| 342 | /* | |||
| 343 | ** mark all objects in list of being-finalized | |||
| 344 | */ | |||
| 345 | 1782 | static lu_mem markbeingfnz (global_State *g) { | ||
| 346 | GCObject *o; | |||
| 347 | 1782 | lu_mem count = 0; | ||
| 348 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | for (o = g->tobefnz; o != NULL; o = o->next) { |
| 349 | ✗ | count++; | ||
| 350 | ✗ | markobject(g, o); | ||
| 351 | } | |||
| 352 | 1782 | 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 | 891 | static int remarkupvals (global_State *g) { | ||
| 368 | lua_State *thread; | |||
| 369 | 891 | lua_State **p = &g->twups; | ||
| 370 | 891 | int work = 0; /* estimate of how much work was done here */ | ||
| 371 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | 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 | 891 | return work; | ||
| 391 | } | |||
| 392 | ||||
| 393 | ||||
| 394 | 891 | static void cleargraylists (global_State *g) { | ||
| 395 | 891 | g->gray = g->grayagain = NULL; | ||
| 396 | 891 | g->weak = g->allweak = g->ephemeron = NULL; | ||
| 397 | 891 | } | ||
| 398 | ||||
| 399 | ||||
| 400 | /* | |||
| 401 | ** mark root set and reset all gray lists, to start a new collection | |||
| 402 | */ | |||
| 403 | 891 | static void restartcollection (global_State *g) { | ||
| 404 | 891 | cleargraylists(g); | ||
| 405 |
1/2✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
|
891 | markobject(g, g->mainthread); | |
| 406 |
2/4✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 891 times.
✗ Branch 3 not taken.
|
891 | markvalue(g, &g->l_registry); | |
| 407 | 891 | markmt(g); | ||
| 408 | 891 | markbeingfnz(g); /* mark any finalizing object left from previous cycle */ | ||
| 409 | 891 | } | ||
| 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 | 21087 | static void genlink (global_State *g, GCObject *o) { | ||
| 431 | lua_assert(isblack(o)); | |||
| 432 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 21087 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 21087 times.
|
21087 | 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 21087 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 21087 times.
|
21087 | else if (getage(o) == G_TOUCHED2) |
| 436 | ✗ | changeage(o, G_TOUCHED2, G_OLD); /* advance age */ | ||
| 437 | 21087 | } | ||
| 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 | 11286 | static void traversestrongtable (global_State *g, Table *h) { | ||
| 524 | 11286 | Node *n, *limit = gnodelast(h); | ||
| 525 | unsigned int i; | |||
| 526 | 11286 | unsigned int asize = luaH_realasize(h); | ||
| 527 |
2/2✓ Branch 0 taken 1782 times.
✓ Branch 1 taken 11286 times.
|
2/2✓ Decision 'true' taken 1782 times.
✓ Decision 'false' taken 11286 times.
|
13068 | for (i = 0; i < asize; i++) /* traverse array part */ |
| 528 |
3/4✓ Branch 0 taken 1782 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 891 times.
✓ Branch 3 taken 891 times.
|
1782 | markvalue(g, &h->array[i]); | |
| 529 |
2/2✓ Branch 0 taken 77220 times.
✓ Branch 1 taken 11286 times.
|
2/2✓ Decision 'true' taken 77220 times.
✓ Decision 'false' taken 11286 times.
|
88506 | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ |
| 530 |
2/2✓ Branch 0 taken 10989 times.
✓ Branch 1 taken 66231 times.
|
2/2✓ Decision 'true' taken 10989 times.
✓ Decision 'false' taken 66231 times.
|
77220 | if (isempty(gval(n))) /* entry is empty? */ |
| 531 | 10989 | clearkey(n); /* clear its key */ | ||
| 532 | else { | |||
| 533 | lua_assert(!keyisnil(n)); | |||
| 534 |
3/4✓ Branch 0 taken 66231 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 46332 times.
✓ Branch 3 taken 19899 times.
|
66231 | markkey(g, n); | |
| 535 |
4/4✓ Branch 0 taken 28809 times.
✓ Branch 1 taken 37422 times.
✓ Branch 2 taken 20196 times.
✓ Branch 3 taken 8613 times.
|
66231 | markvalue(g, gval(n)); | |
| 536 | } | |||
| 537 | } | |||
| 538 | 11286 | genlink(g, obj2gco(h)); | ||
| 539 | 11286 | } | ||
| 540 | ||||
| 541 | ||||
| 542 | 11286 | static lu_mem traversetable (global_State *g, Table *h) { | ||
| 543 | const char *weakkey, *weakvalue; | |||
| 544 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 11286 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
11286 | const TValue *mode = gfasttm(g, h->metatable, TM_MODE); | |
| 545 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 11286 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
11286 | markobjectN(g, h->metatable); | |
| 546 |
1/6✗ Branch 0 not taken.
✓ Branch 1 taken 11286 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 11286 times.
|
11286 | 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 | 11286 | traversestrongtable(g, h); | ||
| 559 |
2/2✓ Branch 0 taken 10395 times.
✓ Branch 1 taken 891 times.
|
11286 | return 1 + h->alimit + 2 * allocsizenode(h); | |
| 560 | } | |||
| 561 | ||||
| 562 | ||||
| 563 | 9801 | static int traverseudata (global_State *g, Udata *u) { | ||
| 564 | int i; | |||
| 565 |
3/4✓ Branch 0 taken 2673 times.
✓ Branch 1 taken 7128 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2673 times.
|
9801 | markobjectN(g, u->metatable); /* mark its metatable */ | |
| 566 |
2/2✓ Branch 0 taken 9801 times.
✓ Branch 1 taken 9801 times.
|
2/2✓ Decision 'true' taken 9801 times.
✓ Decision 'false' taken 9801 times.
|
19602 | for (i = 0; i < u->nuvalue; i++) |
| 567 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 9801 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
9801 | markvalue(g, &u->uv[i].uv); | |
| 568 | 9801 | genlink(g, obj2gco(u)); | ||
| 569 | 9801 | 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 | 8316 | static int traverseCclosure (global_State *g, CClosure *cl) { | ||
| 594 | int i; | |||
| 595 |
2/2✓ Branch 0 taken 8316 times.
✓ Branch 1 taken 8316 times.
|
2/2✓ Decision 'true' taken 8316 times.
✓ Decision 'false' taken 8316 times.
|
16632 | for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ |
| 596 |
3/4✓ Branch 0 taken 8316 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7722 times.
✓ Branch 3 taken 594 times.
|
8316 | markvalue(g, &cl->upvalue[i]); | |
| 597 | 8316 | 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 | 1782 | static int traversethread (global_State *g, lua_State *th) { | ||
| 628 | UpVal *uv; | |||
| 629 | 1782 | StkId o = th->stack.p; | ||
| 630 |
3/4✓ Branch 0 taken 1782 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 891 times.
✓ Branch 3 taken 891 times.
|
2/2✓ Decision 'true' taken 891 times.
✓ Decision 'false' taken 891 times.
|
1782 | if (isold(th) || g->gcstate == GCSpropagate) |
| 631 | 891 | linkgclist(th, g->grayagain); /* insert into 'grayagain' list */ | ||
| 632 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | 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 3564 times.
✓ Branch 1 taken 1782 times.
|
2/2✓ Decision 'true' taken 3564 times.
✓ Decision 'false' taken 1782 times.
|
5346 | for (; o < th->top.p; o++) /* mark live elements in the stack */ |
| 637 |
4/4✓ Branch 0 taken 1782 times.
✓ Branch 1 taken 1782 times.
✓ Branch 2 taken 594 times.
✓ Branch 3 taken 1188 times.
|
3564 | markvalue(g, s2v(o)); | |
| 638 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | 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 891 times.
✓ Branch 1 taken 891 times.
|
2/2✓ Decision 'true' taken 891 times.
✓ Decision 'false' taken 891 times.
|
1782 | if (g->gcstate == GCSatomic) { /* final traversal? */ |
| 641 |
2/2✓ Branch 0 taken 38313 times.
✓ Branch 1 taken 891 times.
|
2/2✓ Decision 'true' taken 38313 times.
✓ Decision 'false' taken 891 times.
|
39204 | for (; o < th->stack_last.p + EXTRA_STACK; o++) |
| 642 | 38313 | setnilvalue(s2v(o)); /* clear dead stack slice */ | ||
| 643 | /* 'remarkupvals' may have removed thread from 'twups' list */ | |||
| 644 |
2/4✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 891 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | 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 891 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 891 times.
✗ Decision 'false' not taken.
|
891 | else if (!g->gcemergency) |
| 650 | 891 | luaD_shrinkstack(th); /* do not change stack in emergency cycle */ | ||
| 651 | 1782 | return 1 + stacksize(th); | ||
| 652 | } | |||
| 653 | ||||
| 654 | ||||
| 655 | /* | |||
| 656 | ** traverse one gray object, turning it to black. | |||
| 657 | */ | |||
| 658 | 31185 | static lu_mem propagatemark (global_State *g) { | ||
| 659 | 31185 | GCObject *o = g->gray; | ||
| 660 | 31185 | nw2black(o); | ||
| 661 | 31185 | g->gray = *getgclist(o); /* remove from 'gray' list */ | ||
| 662 |
4/7✓ Branch 0 taken 11286 times.
✓ Branch 1 taken 9801 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8316 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1782 times.
✗ Branch 6 not taken.
|
31185 | switch (o->tt) { | |
| 663 |
1/1✓ Decision 'true' taken 11286 times.
|
11286 | case LUA_VTABLE: return traversetable(g, gco2t(o)); | |
| 664 |
1/1✓ Decision 'true' taken 9801 times.
|
9801 | case LUA_VUSERDATA: return traverseudata(g, gco2u(o)); | |
| 665 | ✗ | case LUA_VLCL: return traverseLclosure(g, gco2lcl(o)); | ||
| 666 |
1/1✓ Decision 'true' taken 8316 times.
|
8316 | case LUA_VCCL: return traverseCclosure(g, gco2ccl(o)); | |
| 667 | ✗ | case LUA_VPROTO: return traverseproto(g, gco2p(o)); | ||
| 668 |
1/1✓ Decision 'true' taken 1782 times.
|
1782 | case LUA_VTHREAD: return traversethread(g, gco2th(o)); | |
| 669 | ✗ | default: lua_assert(0); return 0; | ||
| 670 | } | |||
| 671 | } | |||
| 672 | ||||
| 673 | ||||
| 674 | 3564 | static lu_mem propagateall (global_State *g) { | ||
| 675 | 3564 | lu_mem tot = 0; | ||
| 676 |
2/2✓ Branch 0 taken 891 times.
✓ Branch 1 taken 3564 times.
|
2/2✓ Decision 'true' taken 891 times.
✓ Decision 'false' taken 3564 times.
|
4455 | while (g->gray) |
| 677 | 891 | tot += propagatemark(g); | ||
| 678 | 3564 | 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 | 1782 | static void convergeephemerons (global_State *g) { | ||
| 690 | int changed; | |||
| 691 | 1782 | int dir = 0; | ||
| 692 | do { | |||
| 693 | GCObject *w; | |||
| 694 | 1782 | GCObject *next = g->ephemeron; /* get ephemeron list */ | ||
| 695 | 1782 | g->ephemeron = NULL; /* tables may return to this list when traversed */ | ||
| 696 | 1782 | changed = 0; | ||
| 697 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | 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 | 1782 | dir = !dir; /* invert direction next time */ | ||
| 707 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | } while (changed); /* repeat until no more changes */ |
| 708 | 1782 | } | ||
| 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 | 1782 | static void clearbykeys (global_State *g, GCObject *l) { | ||
| 724 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1782 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1782 times.
|
1782 | 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 | 1782 | } | ||
| 736 | ||||
| 737 | ||||
| 738 | /* | |||
| 739 | ** clear entries with unmarked values from all weaktables in list 'l' up | |||
| 740 | ** to element 'f' | |||
| 741 | */ | |||
| 742 | 3564 | static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { | ||
| 743 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3564 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 3564 times.
|
3564 | 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 | 3564 | } | ||
| 761 | ||||
| 762 | ||||
| 763 | 296 | static void freeupval (lua_State *L, UpVal *uv) { | ||
| 764 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 296 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 296 times.
|
296 | if (upisopen(uv)) |
| 765 | ✗ | luaF_unlinkupval(uv); | ||
| 766 | 296 | luaM_free(L, uv); | ||
| 767 | 296 | } | ||
| 768 | ||||
| 769 | ||||
| 770 | 70922 | static void freeobj (lua_State *L, GCObject *o) { | ||
| 771 |
8/10✓ Branch 0 taken 512 times.
✓ Branch 1 taken 296 times.
✓ Branch 2 taken 512 times.
✓ Branch 3 taken 5940 times.
✓ Branch 4 taken 6937 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 7431 times.
✓ Branch 7 taken 49179 times.
✓ Branch 8 taken 115 times.
✗ Branch 9 not taken.
|
70922 | switch (o->tt) { | |
| 772 |
1/1✓ Decision 'true' taken 512 times.
|
512 | case LUA_VPROTO: | |
| 773 | 512 | luaF_freeproto(L, gco2p(o)); | ||
| 774 | 512 | break; | ||
| 775 |
1/1✓ Decision 'true' taken 296 times.
|
296 | case LUA_VUPVAL: | |
| 776 | 296 | freeupval(L, gco2upv(o)); | ||
| 777 | 296 | break; | ||
| 778 |
1/1✓ Decision 'true' taken 512 times.
|
512 | case LUA_VLCL: { | |
| 779 | 512 | LClosure *cl = gco2lcl(o); | ||
| 780 | 512 | luaM_freemem(L, cl, sizeLclosure(cl->nupvalues)); | ||
| 781 | 512 | break; | ||
| 782 | } | |||
| 783 |
1/1✓ Decision 'true' taken 5940 times.
|
5940 | case LUA_VCCL: { | |
| 784 | 5940 | CClosure *cl = gco2ccl(o); | ||
| 785 | 5940 | luaM_freemem(L, cl, sizeCclosure(cl->nupvalues)); | ||
| 786 | 5940 | break; | ||
| 787 | } | |||
| 788 |
1/1✓ Decision 'true' taken 6937 times.
|
6937 | case LUA_VTABLE: | |
| 789 | 6937 | luaH_free(L, gco2t(o)); | ||
| 790 | 6937 | break; | ||
| 791 | ✗ | case LUA_VTHREAD: | ||
| 792 | ✗ | luaE_freethread(L, gco2th(o)); | ||
| 793 | ✗ | break; | ||
| 794 |
1/1✓ Decision 'true' taken 7431 times.
|
7431 | case LUA_VUSERDATA: { | |
| 795 | 7431 | Udata *u = gco2u(o); | ||
| 796 |
2/2✓ Branch 0 taken 7134 times.
✓ Branch 1 taken 297 times.
|
7431 | luaM_freemem(L, o, sizeudata(u->nuvalue, u->len)); | |
| 797 | 7431 | break; | ||
| 798 | } | |||
| 799 |
1/1✓ Decision 'true' taken 49179 times.
|
49179 | case LUA_VSHRSTR: { | |
| 800 | 49179 | TString *ts = gco2ts(o); | ||
| 801 | 49179 | luaS_remove(L, ts); /* remove it from hash table */ | ||
| 802 | 49179 | luaM_freemem(L, ts, sizelstring(ts->shrlen)); | ||
| 803 | 49179 | 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 70922 times.
|
70922 | default: lua_assert(0); | |
| 811 | } | |||
| 812 | 70922 | } | ||
| 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 | 3861 | static GCObject **sweeplist (lua_State *L, GCObject **p, int countin, | ||
| 823 | int *countout) { | |||
| 824 | 3861 | global_State *g = G(L); | ||
| 825 | 3861 | int ow = otherwhite(g); | ||
| 826 | int i; | |||
| 827 | 3861 | int white = luaC_white(g); /* current white */ | ||
| 828 |
4/4✓ Branch 0 taken 79002 times.
✓ Branch 1 taken 2673 times.
✓ Branch 2 taken 77814 times.
✓ Branch 3 taken 1188 times.
|
0/1? Decision couldn't be analyzed.
|
81675 | for (i = 0; *p != NULL && i < countin; i++) { |
| 829 | 77814 | GCObject *curr = *p; | ||
| 830 | 77814 | int marked = curr->marked; | ||
| 831 |
2/2✓ Branch 0 taken 297 times.
✓ Branch 1 taken 77517 times.
|
2/2✓ Decision 'true' taken 297 times.
✓ Decision 'false' taken 77517 times.
|
77814 | if (isdeadm(ow, marked)) { /* is 'curr' dead? */ |
| 832 | 297 | *p = curr->next; /* remove 'curr' from list */ | ||
| 833 | 297 | freeobj(L, curr); /* erase 'curr' */ | ||
| 834 | } | |||
| 835 | else { /* change mark to 'white' */ | |||
| 836 | 77517 | curr->marked = cast_byte((marked & ~maskgcbits) | white); | ||
| 837 | 77517 | p = &curr->next; /* go to next element */ | ||
| 838 | } | |||
| 839 | } | |||
| 840 |
2/2✓ Branch 0 taken 2970 times.
✓ Branch 1 taken 891 times.
|
2/2✓ Decision 'true' taken 2970 times.
✓ Decision 'false' taken 891 times.
|
3861 | if (countout) |
| 841 | 2970 | *countout = i; /* number of elements traversed */ | ||
| 842 |
2/2✓ Branch 0 taken 1188 times.
✓ Branch 1 taken 2673 times.
|
3861 | return (*p == NULL) ? NULL : p; | |
| 843 | } | |||
| 844 | ||||
| 845 | ||||
| 846 | /* | |||
| 847 | ** sweep a list until a live object (or end of list) | |||
| 848 | */ | |||
| 849 | 891 | static GCObject **sweeptolive (lua_State *L, GCObject **p) { | ||
| 850 | 891 | GCObject **old = p; | ||
| 851 | do { | |||
| 852 | 891 | p = sweeplist(L, p, 1, NULL); | ||
| 853 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | } while (p == old); |
| 854 | 891 | return p; | ||
| 855 | } | |||
| 856 | ||||
| 857 | /* }====================================================== */ | |||
| 858 | ||||
| 859 | ||||
| 860 | /* | |||
| 861 | ** {====================================================== | |||
| 862 | ** Finalization | |||
| 863 | ** ======================================================= | |||
| 864 | */ | |||
| 865 | ||||
| 866 | /* | |||
| 867 | ** If possible, shrink string table. | |||
| 868 | */ | |||
| 869 | 891 | static void checkSizes (lua_State *L, global_State *g) { | ||
| 870 |
1/2✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 891 times.
✗ Decision 'false' not taken.
|
891 | if (!g->gcemergency) { |
| 871 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | 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 | 891 | } | ||
| 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 | 1788 | static GCObject *udata2finalize (global_State *g) { | ||
| 885 | 1788 | GCObject *o = g->tobefnz; /* get first element */ | ||
| 886 | lua_assert(tofinalize(o)); | |||
| 887 | 1788 | g->tobefnz = o->next; /* remove it from 'tobefnz' list */ | ||
| 888 | 1788 | o->next = g->allgc; /* return it to 'allgc' list */ | ||
| 889 | 1788 | g->allgc = o; | ||
| 890 | 1788 | resetbit(o->marked, FINALIZEDBIT); /* object is "normal" again */ | ||
| 891 |
2/4✓ Branch 0 taken 1788 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1788 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | if (issweepphase(g)) |
| 892 | ✗ | makewhite(g, o); /* "sweep" object */ | ||
| 893 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1788 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | else if (getage(o) == G_OLD1) |
| 894 | ✗ | g->firstold1 = o; /* it is the first OLD1 object in the list */ | ||
| 895 | 1788 | return o; | ||
| 896 | } | |||
| 897 | ||||
| 898 | ||||
| 899 | 1788 | static void dothecall (lua_State *L, void *ud) { | ||
| 900 | UNUSED(ud); | |||
| 901 | 1788 | luaD_callnoyield(L, L->top.p - 2, 0); | ||
| 902 | 1788 | } | ||
| 903 | ||||
| 904 | ||||
| 905 | 1788 | static void GCTM (lua_State *L) { | ||
| 906 | 1788 | global_State *g = G(L); | ||
| 907 | const TValue *tm; | |||
| 908 | TValue v; | |||
| 909 | lua_assert(!g->gcemergency); | |||
| 910 | 1788 | setgcovalue(L, &v, udata2finalize(g)); | ||
| 911 | 1788 | tm = luaT_gettmbyobj(L, &v, TM_GC); | ||
| 912 |
1/2✓ Branch 0 taken 1788 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 1788 times.
✗ Decision 'false' not taken.
|
1788 | if (!notm(tm)) { /* is there a finalizer? */ |
| 913 | int status; | |||
| 914 | 1788 | lu_byte oldah = L->allowhook; | ||
| 915 | 1788 | int oldgcstp = g->gcstp; | ||
| 916 | 1788 | g->gcstp |= GCSTPGC; /* avoid GC steps */ | ||
| 917 | 1788 | L->allowhook = 0; /* stop debug hooks during GC metamethod */ | ||
| 918 | 1788 | setobj2s(L, L->top.p++, tm); /* push finalizer... */ | ||
| 919 | 1788 | setobj2s(L, L->top.p++, &v); /* ... and its argument */ | ||
| 920 | 1788 | L->ci->callstatus |= CIST_FIN; /* will run a finalizer */ | ||
| 921 | 1788 | status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top.p - 2), 0); | ||
| 922 | 1788 | L->ci->callstatus &= ~CIST_FIN; /* not running a finalizer anymore */ | ||
| 923 | 1788 | L->allowhook = oldah; /* restore hooks */ | ||
| 924 | 1788 | g->gcstp = oldgcstp; /* restore state */ | ||
| 925 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1788 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | 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 | 1788 | } | ||
| 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 | 297 | static void callallpendingfinalizers (lua_State *L) { | ||
| 949 | 297 | global_State *g = G(L); | ||
| 950 |
2/2✓ Branch 0 taken 1788 times.
✓ Branch 1 taken 297 times.
|
2/2✓ Decision 'true' taken 1788 times.
✓ Decision 'false' taken 297 times.
|
2085 | while (g->tobefnz) |
| 951 | 1788 | GCTM(L); | ||
| 952 | 297 | } | ||
| 953 | ||||
| 954 | ||||
| 955 | /* | |||
| 956 | ** find last 'next' field in list 'p' list (to add elements in its end) | |||
| 957 | */ | |||
| 958 | 1188 | static GCObject **findlast (GCObject **p) { | ||
| 959 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1188 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1188 times.
|
1188 | while (*p != NULL) |
| 960 | ✗ | p = &(*p)->next; | ||
| 961 | 1188 | 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 | 1188 | static void separatetobefnz (global_State *g, int all) { | ||
| 973 | GCObject *curr; | |||
| 974 | 1188 | GCObject **p = &g->finobj; | ||
| 975 | 1188 | GCObject **lastnext = findlast(&g->tobefnz); | ||
| 976 |
2/2✓ Branch 0 taken 4461 times.
✓ Branch 1 taken 1188 times.
|
2/2✓ Decision 'true' taken 4461 times.
✓ Decision 'false' taken 1188 times.
|
5649 | while ((curr = *p) != g->finobjold1) { /* traverse all finalizable objects */ |
| 977 | lua_assert(tofinalize(curr)); | |||
| 978 |
3/4✓ Branch 0 taken 2673 times.
✓ Branch 1 taken 1788 times.
✓ Branch 2 taken 2673 times.
✗ Branch 3 not taken.
|
2/2✓ Decision 'true' taken 2673 times.
✓ Decision 'false' taken 1788 times.
|
4461 | if (!(iswhite(curr) || all)) /* not being collected? */ |
| 979 | 2673 | p = &curr->next; /* don't bother with it */ | ||
| 980 | else { | |||
| 981 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1788 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | if (curr == g->finobjsur) /* removing 'finobjsur'? */ |
| 982 | ✗ | g->finobjsur = curr->next; /* correct it */ | ||
| 983 | 1788 | *p = curr->next; /* remove 'curr' from 'finobj' list */ | ||
| 984 | 1788 | curr->next = *lastnext; /* link at the end of 'tobefnz' list */ | ||
| 985 | 1788 | *lastnext = curr; | ||
| 986 | 1788 | lastnext = &curr->next; | ||
| 987 | } | |||
| 988 | } | |||
| 989 | 1188 | } | ||
| 990 | ||||
| 991 | ||||
| 992 | /* | |||
| 993 | ** If pointer 'p' points to 'o', move it to the next element. | |||
| 994 | */ | |||
| 995 | 7152 | static void checkpointer (GCObject **p, GCObject *o) { | ||
| 996 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7152 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7152 times.
|
7152 | if (o == *p) |
| 997 | ✗ | *p = o->next; | ||
| 998 | 7152 | } | ||
| 999 | ||||
| 1000 | ||||
| 1001 | /* | |||
| 1002 | ** Correct pointers to objects inside 'allgc' list when | |||
| 1003 | ** object 'o' is being removed from the list. | |||
| 1004 | */ | |||
| 1005 | 1788 | static void correctpointers (global_State *g, GCObject *o) { | ||
| 1006 | 1788 | checkpointer(&g->survival, o); | ||
| 1007 | 1788 | checkpointer(&g->old1, o); | ||
| 1008 | 1788 | checkpointer(&g->reallyold, o); | ||
| 1009 | 1788 | checkpointer(&g->firstold1, o); | ||
| 1010 | 1788 | } | ||
| 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 | 1788 | void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) { | ||
| 1018 | 1788 | global_State *g = G(L); | ||
| 1019 |
2/4✓ Branch 0 taken 1788 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1788 times.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | if (tofinalize(o) || /* obj. is already marked... */ |
| 1020 |
2/4✓ Branch 0 taken 1788 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1788 times.
✗ Branch 4 not taken.
|
1788 | gfasttm(g, mt, TM_GC) == NULL || /* or has no finalizer... */ | |
| 1021 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1788 times.
|
1788 | (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 1788 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1788 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1788 times.
|
1788 | 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 | 1788 | correctpointers(g, o); | ||
| 1032 | /* search for pointer pointing to 'o' */ | |||
| 1033 |
2/2✓ Branch 0 taken 3861 times.
✓ Branch 1 taken 1788 times.
|
2/2✓ Decision 'true' taken 3861 times.
✓ Decision 'false' taken 1788 times.
|
5649 | for (p = &g->allgc; *p != o; p = &(*p)->next) { /* empty */ } |
| 1034 | 1788 | *p = o->next; /* remove 'o' from 'allgc' list */ | ||
| 1035 | 1788 | o->next = g->finobj; /* link it in 'finobj' list */ | ||
| 1036 | 1788 | g->finobj = o; | ||
| 1037 | 1788 | 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 | 891 | static void setpause (global_State *g) { | ||
| 1058 | l_mem threshold, debt; | |||
| 1059 | 891 | int pause = getgcparam(g->gcpause); | ||
| 1060 | 891 | l_mem estimate = g->GCestimate / PAUSEADJ; /* adjust 'estimate' */ | ||
| 1061 | lua_assert(estimate > 0); | |||
| 1062 | 1782 | threshold = (pause < MAX_LMEM / estimate) /* overflow? */ | ||
| 1063 | 891 | ? estimate * pause /* no overflow */ | ||
| 1064 |
1/2✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
|
891 | : MAX_LMEM; /* overflow; truncate to maximum */ | |
| 1065 | 891 | debt = gettotalbytes(g) - threshold; | ||
| 1066 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | if (debt > 0) debt = 0; |
| 1067 | 891 | luaE_setdebt(g, debt); | ||
| 1068 | 891 | } | ||
| 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 | 594 | void luaC_changemode (lua_State *L, int newmode) { | ||
| 1359 | 594 | global_State *g = G(L); | ||
| 1360 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 594 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 594 times.
|
594 | 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 | 594 | g->lastatomic = 0; | ||
| 1367 | 594 | } | ||
| 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 | 891 | static void entersweep (lua_State *L) { | ||
| 1485 | 891 | global_State *g = G(L); | ||
| 1486 | 891 | g->gcstate = GCSswpallgc; | ||
| 1487 | lua_assert(g->sweepgc == NULL); | |||
| 1488 | 891 | g->sweepgc = sweeptolive(L, &g->allgc); | ||
| 1489 | 891 | } | ||
| 1490 | ||||
| 1491 | ||||
| 1492 | /* | |||
| 1493 | ** Delete all objects in list 'p' until (but not including) object | |||
| 1494 | ** 'limit'. | |||
| 1495 | */ | |||
| 1496 | 594 | static void deletelist (lua_State *L, GCObject *p, GCObject *limit) { | ||
| 1497 |
2/2✓ Branch 0 taken 70625 times.
✓ Branch 1 taken 594 times.
|
2/2✓ Decision 'true' taken 70625 times.
✓ Decision 'false' taken 594 times.
|
71219 | while (p != limit) { |
| 1498 | 70625 | GCObject *next = p->next; | ||
| 1499 | 70625 | freeobj(L, p); | ||
| 1500 | 70625 | p = next; | ||
| 1501 | } | |||
| 1502 | 594 | } | ||
| 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 | 297 | void luaC_freeallobjects (lua_State *L) { | ||
| 1510 | 297 | global_State *g = G(L); | ||
| 1511 | 297 | g->gcstp = GCSTPCLS; /* no extra finalizers after here */ | ||
| 1512 | 297 | luaC_changemode(L, KGC_INC); | ||
| 1513 | 297 | separatetobefnz(g, 1); /* separate all objects with finalizers */ | ||
| 1514 | lua_assert(g->finobj == NULL); | |||
| 1515 | 297 | callallpendingfinalizers(L); | ||
| 1516 | 297 | deletelist(L, g->allgc, obj2gco(g->mainthread)); | ||
| 1517 | lua_assert(g->finobj == NULL); /* no new finalizers */ | |||
| 1518 | 297 | deletelist(L, g->fixedgc, NULL); /* collect fixed objects */ | ||
| 1519 | lua_assert(g->strt.nuse == 0); | |||
| 1520 | 297 | } | ||
| 1521 | ||||
| 1522 | ||||
| 1523 | 891 | static lu_mem atomic (lua_State *L) { | ||
| 1524 | 891 | global_State *g = G(L); | ||
| 1525 | 891 | lu_mem work = 0; | ||
| 1526 | GCObject *origweak, *origall; | |||
| 1527 | 891 | GCObject *grayagain = g->grayagain; /* save original list */ | ||
| 1528 | 891 | g->grayagain = NULL; | ||
| 1529 | lua_assert(g->ephemeron == NULL && g->weak == NULL); | |||
| 1530 | lua_assert(!iswhite(g->mainthread)); | |||
| 1531 | 891 | g->gcstate = GCSatomic; | ||
| 1532 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
|
891 | markobject(g, L); /* mark running thread */ | |
| 1533 | /* registry and global metatables may be changed by API */ | |||
| 1534 |
2/4✓ Branch 0 taken 891 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 891 times.
|
891 | markvalue(g, &g->l_registry); | |
| 1535 | 891 | markmt(g); /* mark global metatables */ | ||
| 1536 | 891 | work += propagateall(g); /* empties 'gray' list */ | ||
| 1537 | /* remark occasional upvalues of (maybe) dead threads */ | |||
| 1538 | 891 | work += remarkupvals(g); | ||
| 1539 | 891 | work += propagateall(g); /* propagate changes */ | ||
| 1540 | 891 | g->gray = grayagain; | ||
| 1541 | 891 | work += propagateall(g); /* traverse 'grayagain' list */ | ||
| 1542 | 891 | convergeephemerons(g); | ||
| 1543 | /* at this point, all strongly accessible objects are marked. */ | |||
| 1544 | /* Clear values from weak tables, before checking finalizers */ | |||
| 1545 | 891 | clearbyvalues(g, g->weak, NULL); | ||
| 1546 | 891 | clearbyvalues(g, g->allweak, NULL); | ||
| 1547 | 891 | origweak = g->weak; origall = g->allweak; | ||
| 1548 | 891 | separatetobefnz(g, 0); /* separate objects to be finalized */ | ||
| 1549 | 891 | work += markbeingfnz(g); /* mark objects that will be finalized */ | ||
| 1550 | 891 | work += propagateall(g); /* remark, to propagate 'resurrection' */ | ||
| 1551 | 891 | convergeephemerons(g); | ||
| 1552 | /* at this point, all resurrected objects are marked. */ | |||
| 1553 | /* remove dead objects from weak tables */ | |||
| 1554 | 891 | clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron tables */ | ||
| 1555 | 891 | clearbykeys(g, g->allweak); /* clear keys from all 'allweak' tables */ | ||
| 1556 | /* clear values from resurrected weak tables */ | |||
| 1557 | 891 | clearbyvalues(g, g->weak, origweak); | ||
| 1558 | 891 | clearbyvalues(g, g->allweak, origall); | ||
| 1559 | 891 | luaS_clearcache(g); | ||
| 1560 | 891 | g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ | ||
| 1561 | lua_assert(g->gray == NULL); | |||
| 1562 | 891 | return work; /* estimate of slots marked by 'atomic' */ | ||
| 1563 | } | |||
| 1564 | ||||
| 1565 | ||||
| 1566 | 5643 | static int sweepstep (lua_State *L, global_State *g, | ||
| 1567 | int nextstate, GCObject **nextlist) { | |||
| 1568 |
2/2✓ Branch 0 taken 2970 times.
✓ Branch 1 taken 2673 times.
|
2/2✓ Decision 'true' taken 2970 times.
✓ Decision 'false' taken 2673 times.
|
5643 | if (g->sweepgc) { |
| 1569 | 2970 | l_mem olddebt = g->GCdebt; | ||
| 1570 | int count; | |||
| 1571 | 2970 | g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX, &count); | ||
| 1572 | 2970 | g->GCestimate += g->GCdebt - olddebt; /* update estimate */ | ||
| 1573 | 2970 | return count; | ||
| 1574 | } | |||
| 1575 | else { /* enter next state */ | |||
| 1576 | 2673 | g->gcstate = nextstate; | ||
| 1577 | 2673 | g->sweepgc = nextlist; | ||
| 1578 | 2673 | return 0; /* no work done */ | ||
| 1579 | } | |||
| 1580 | } | |||
| 1581 | ||||
| 1582 | ||||
| 1583 | 40392 | static lu_mem singlestep (lua_State *L) { | ||
| 1584 | 40392 | global_State *g = G(L); | ||
| 1585 | lu_mem work; | |||
| 1586 | lua_assert(!g->gcstopem); /* collector is not reentrant */ | |||
| 1587 | 40392 | g->gcstopem = 1; /* no emergency collections while collecting */ | ||
| 1588 |
8/9✓ Branch 0 taken 891 times.
✓ Branch 1 taken 31185 times.
✓ Branch 2 taken 891 times.
✓ Branch 3 taken 2079 times.
✓ Branch 4 taken 1782 times.
✓ Branch 5 taken 1782 times.
✓ Branch 6 taken 891 times.
✓ Branch 7 taken 891 times.
✗ Branch 8 not taken.
|
40392 | switch (g->gcstate) { | |
| 1589 |
1/1✓ Decision 'true' taken 891 times.
|
891 | case GCSpause: { | |
| 1590 | 891 | restartcollection(g); | ||
| 1591 | 891 | g->gcstate = GCSpropagate; | ||
| 1592 | 891 | work = 1; | ||
| 1593 | 891 | break; | ||
| 1594 | } | |||
| 1595 |
1/1✓ Decision 'true' taken 31185 times.
|
31185 | case GCSpropagate: { | |
| 1596 |
2/2✓ Branch 0 taken 891 times.
✓ Branch 1 taken 30294 times.
|
2/2✓ Decision 'true' taken 891 times.
✓ Decision 'false' taken 30294 times.
|
31185 | if (g->gray == NULL) { /* no more gray objects? */ |
| 1597 | 891 | g->gcstate = GCSenteratomic; /* finish propagate phase */ | ||
| 1598 | 891 | work = 0; | ||
| 1599 | } | |||
| 1600 | else | |||
| 1601 | 30294 | work = propagatemark(g); /* traverse one gray object */ | ||
| 1602 | 31185 | break; | ||
| 1603 | } | |||
| 1604 |
1/1✓ Decision 'true' taken 891 times.
|
891 | case GCSenteratomic: { | |
| 1605 | 891 | work = atomic(L); /* work is what was traversed by 'atomic' */ | ||
| 1606 | 891 | entersweep(L); | ||
| 1607 | 891 | g->GCestimate = gettotalbytes(g); /* first estimate */; | ||
| 1608 | 891 | break; | ||
| 1609 | } | |||
| 1610 |
1/1✓ Decision 'true' taken 2079 times.
|
2079 | case GCSswpallgc: { /* sweep "regular" objects */ | |
| 1611 | 2079 | work = sweepstep(L, g, GCSswpfinobj, &g->finobj); | ||
| 1612 | 2079 | break; | ||
| 1613 | } | |||
| 1614 |
1/1✓ Decision 'true' taken 1782 times.
|
1782 | case GCSswpfinobj: { /* sweep objects with finalizers */ | |
| 1615 | 1782 | work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz); | ||
| 1616 | 1782 | break; | ||
| 1617 | } | |||
| 1618 |
1/1✓ Decision 'true' taken 1782 times.
|
1782 | case GCSswptobefnz: { /* sweep objects to be finalized */ | |
| 1619 | 1782 | work = sweepstep(L, g, GCSswpend, NULL); | ||
| 1620 | 1782 | break; | ||
| 1621 | } | |||
| 1622 |
1/1✓ Decision 'true' taken 891 times.
|
891 | case GCSswpend: { /* finish sweeps */ | |
| 1623 | 891 | checkSizes(L, g); | ||
| 1624 | 891 | g->gcstate = GCScallfin; | ||
| 1625 | 891 | work = 0; | ||
| 1626 | 891 | break; | ||
| 1627 | } | |||
| 1628 |
1/1✓ Decision 'true' taken 891 times.
|
891 | case GCScallfin: { /* call remaining finalizers */ | |
| 1629 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 891 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 891 times.
|
891 | 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 | 891 | g->gcstate = GCSpause; /* finish collection */ | ||
| 1635 | 891 | work = 0; | ||
| 1636 | } | |||
| 1637 | 891 | break; | ||
| 1638 | } | |||
| 1639 | ✗ | default: lua_assert(0); return 0; | ||
| 1640 | } | |||
| 1641 | 40392 | g->gcstopem = 0; | ||
| 1642 | 40392 | return work; | ||
| 1643 | } | |||
| 1644 | ||||
| 1645 | ||||
| 1646 | /* | |||
| 1647 | ** advances the garbage collector until it reaches a state allowed | |||
| 1648 | ** by 'statemask' | |||
| 1649 | */ | |||
| 1650 | 891 | void luaC_runtilstate (lua_State *L, int statesmask) { | ||
| 1651 | 891 | global_State *g = G(L); | ||
| 1652 |
2/2✓ Branch 0 taken 23463 times.
✓ Branch 1 taken 891 times.
|
2/2✓ Decision 'true' taken 23463 times.
✓ Decision 'false' taken 891 times.
|
24354 | while (!testbit(statesmask, g->gcstate)) |
| 1653 | 23463 | singlestep(L); | ||
| 1654 | 891 | } | ||
| 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 | 594 | static void incstep (lua_State *L, global_State *g) { | ||
| 1666 | 594 | int stepmul = (getgcparam(g->gcstepmul) | 1); /* avoid division by 0 */ | ||
| 1667 | 594 | l_mem debt = (g->GCdebt / WORK2MEM) * stepmul; | ||
| 1668 | 594 | l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem)) | ||
| 1669 | 594 | ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul | ||
| 1670 |
1/2✓ Branch 0 taken 594 times.
✗ Branch 1 not taken.
|
594 | : MAX_LMEM; /* overflow; keep maximum value */ | |
| 1671 | do { /* repeat until pause or enough "credit" (negative debt) */ | |||
| 1672 | 16929 | lu_mem work = singlestep(L); /* perform one single step */ | ||
| 1673 | 16929 | debt -= work; | ||
| 1674 |
3/4✓ Branch 0 taken 16929 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16335 times.
✓ Branch 3 taken 594 times.
|
0/1? Decision couldn't be analyzed.
|
16929 | } while (debt > -stepsize && g->gcstate != GCSpause); |
| 1675 |
1/2✓ Branch 0 taken 594 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 594 times.
✗ Decision 'false' not taken.
|
594 | if (g->gcstate == GCSpause) |
| 1676 | 594 | 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 | 594 | } | ||
| 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 | 594 | void luaC_step (lua_State *L) { | ||
| 1689 | 594 | global_State *g = G(L); | ||
| 1690 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 594 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 594 times.
|
594 | if (!gcrunning(g)) /* not running? */ |
| 1691 | ✗ | luaE_setdebt(g, -2000); | ||
| 1692 | else { | |||
| 1693 |
2/4✓ Branch 0 taken 594 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 594 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 594 times.
|
594 | if(isdecGCmodegen(g)) |
| 1694 | ✗ | genstep(L, g); | ||
| 1695 | else | |||
| 1696 | 594 | incstep(L, g); | ||
| 1697 | } | |||
| 1698 | 594 | } | ||
| 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 | 297 | static void fullinc (lua_State *L, global_State *g) { | ||
| 1709 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 297 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 297 times.
|
297 | 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 | 297 | luaC_runtilstate(L, bitmask(GCSpause)); | ||
| 1713 | 297 | 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 | 297 | luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ | ||
| 1717 | 297 | setpause(g); | ||
| 1718 | 297 | } | ||
| 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 | 297 | void luaC_fullgc (lua_State *L, int isemergency) { | ||
| 1727 | 297 | global_State *g = G(L); | ||
| 1728 | lua_assert(!g->gcemergency); | |||
| 1729 | 297 | g->gcemergency = isemergency; /* set flag */ | ||
| 1730 |
1/2✓ Branch 0 taken 297 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 297 times.
✗ Decision 'false' not taken.
|
297 | if (g->gckind == KGC_INC) |
| 1731 | 297 | fullinc(L, g); | ||
| 1732 | else | |||
| 1733 | ✗ | fullgen(L, g); | ||
| 1734 | 297 | g->gcemergency = 0; | ||
| 1735 | 297 | } | ||
| 1736 | ||||
| 1737 | /* }====================================================== */ | |||
| 1738 | ||||
| 1739 | ||||
| 1740 |